数据结构之线性表
什么是线性表
线性表就是由n（n>0）个数据元素a1,a2….组成的有限序列
- 数据元素的个数为n，表长度，当n=0时为空表
- 一个线性表为非空表，既n>0，则可以简单记为（a1,a2….,an)
- 数据元素ai表示了各个元素，在不同场合含义不同
逻辑结构特点 - 有且仅有一个开始结点a1,没有直接前驱结点,有且仅有一个后继结点a2
- 有且仅有一个终结点an,没有直接后继结点，有且仅有一个前驱结点an-1
- 其余内部结点ai（2<=i<=n-1）都有且仅有一个前驱结点和一个后继结点
- 同一个线性表，各个数据元素ai必须具有相同的数据类型
线性表的基本运算
- 初始化
- 计算表表长
- 获取结点
- 查找结点
- 插入结点
- 删除结点
顺序表
- 顺序表就是按照顺序存储方式存储的线性表，该线性表的结点按照逻辑次依次存放在计算机的一组连续的存储单元中
- 结点ai存储地址的LOC(ai)计算式：LOC(ai)=a1+(i-1)*c (0<=i<=n)
- 重点
- 插入结点：先判断结点数量是否已满，以及插入结点序号是否正确，满足，将顺序表的数据后移，同时插入节点，更新结点数量表长度
- 删除结点：先判断待删除结点序号是否正确，然后开始移动数据，并更新结点数量
- 顺序表缺点
- 在插入和删除节点的时候，往往需要移动大量的数据
- 如果表比较大，有时比较难分配足够的连续存储空间，往往导致内存分配失败，而无法存储
链表结构
- 链表结构是一种动态存储分配的结构形式，可以根据需要动态申请内存单元
- 链表中每个结点都包含如下两部分
- 数据部分，保存的是该节点的实际数据
- 地址部分，保存的是下一个节点的地址
- 采用引用来指示下一个数据的地址，因此在链表结构中，逻辑上相邻的结点在内存中并不一定相邻，逻辑上相邻关系通过地址部分的引用变量来实现。
- 链表结构分类
- 单链表
- 双链表:每个结点包含两个引用，一个指向下一个结点，一个指向上一个结点
- 单循环链表:在单链表中，将终端结点的引用域null改为指向表头结点或者开始结点
- 多重链的循环表：将表中结点链在多个环上
- 重点
- 追加结点
- 头引用head