线性表的顺序结构
定义
用一段地址连续的存储单元一次存储线性表的数据元素
在内存中找了块地，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。
描述顺序存储结构需要三个属性
- 存储空间的起始位置
- 线性表的最大存储容量
- 线性表的当前长度
数据的长度是存放线性表的存储空间的长度，线性表长度是线性表中数据元素的个数
地址计算方法
数数是从1开始，可下标是从0开始，元素的序号和存放它的数组下表之间存在对应关系
存储器中的每个存储单元都有自己的编号，这个编号称为地址。（LOC表示获得存储位置的函数）
第i个数据元素的存储位置
LOC(ai)=LOC(a1)+(i-1)*C
可以随时算出线性表中任意位置的地址，存取时间性能为O（1），把具有这一特点的存储结构称为随机存取结构
顺序存储结构的插入与删除
获得元素
只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回
插入操作
- 如果插入位置不合理，抛出异常
- 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
- 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
- 将要插入元素填入位置i处
- 表长加1
删除操作
- 如果删除位置不合理，抛出异常
- 取出删除元素
- 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
- 表长减1
在存、读数据时，不管是哪个位置，时间复杂度都是O（1）；而插入或删除时，时间复杂度都是O（n）
优缺点
优点
- 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”
线性表的链式存储结构
线性表链式存储定义
特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。
现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。
为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为节点。
n个节点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
头指针
-
链表中的第一个节点的存储位置叫做头指针
-
头指针具有标识作用，所以常用头指针冠以链表的名字
-
无论链表是否为空，头指针均不为空。头指针是链表的必要元素
头结点
- 在单链表的第一个结点前附设一个结点，称为头节点。头节点的数据域可以不存储任何信息
- 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
- 头结点不一定是链表必须要素
单链表的读取
- 声明一个结点P指向链表第一个结点，初始化j从1开始
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
- 若链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，返回结点p的数据
最坏时间复杂度O（n），主要核心思想“工作指针后移”
单链表的插入
- 声明一结点P指向链表第一个结点，初始化j从1开始
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
- 若链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，在系统中生成一个空结点s
- 将数据元素e赋值给s->data
- 单链表的插入标准语句：s->next=p-next; p->next-s;
- 返回成功
单链表的删除
- 声明一结点p指向链表第一个结点，初始化j从1开始
- 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
- 若链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，将欲删除的结点p->next赋值给q
- 单链表的删除标准语句p->next=q->next
- 将q结点中的数据赋值给e，作为返回
- 释放q结点
单链表插入和删除算法，第一部分是遍历查找第i个元素，第二部分是插入和删除元素。时间复杂度都是O（n）。在不知道第i个元素指针的位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构没有太大优势，但对于插入或删除数据越频繁的操作，单链表的优势就越明显
单链表的整表创建
对于每个链表来说，它所占用空间的大小和位置都不需要预先分配，根据系统的情况和实际的需求即时生成。
创建单链表的过程就是一个动态生成链表的过程，即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表
单链表结构与顺序存储结构优缺点
存储分配方式
- 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
- 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能
- 查找
- 顺序存储结构O（1）
- 单链表O（n）
- 插入和删除
- 顺序存储结构需要平均移动表长一半的元素，时间为O（n）
- 单链表在找出某位置的指针后，插入和删除时间仅为O（1）
- 空间性能
- 顺序存储结构需要预分配存储空间，分大了，浪费，分小了，易发生上溢
- 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使得整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表
循环链表解决了一个很麻烦的问题，如何从当中一个结点出发，访问到链表的全部结点。
为了使空链表与非空链表处理一致，通常设一个头结点。
可以用O（1）的时间访问第一个结点，但对于要访问到最后一个结点，却需要O（n）时间。使用尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。
终端结点用尾指针rear指示，则查找终端结点是O（1），而开始结点，其实就是rear->next->next，其时间复杂也为O（1）
双向链表
在单链表的每个结点中，再设置一个指向其前驱结点的指针域
插入
先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继
删除
- 把p->next 赋值给p->prior的后继
- 把p->prior赋值给p->next的前驱
双向链表相对于单链表来说，要更复杂一些，毕竟它多了prior指针，对于插入和删除时，需要格外小心。另外由于每个结点都需要记录两份指针，所以在空间上时要占用略多一些的。不过，由于它的良好对称性，使得对某个结点的前后结点操作，带来了方便，用空间换了时间