线性表：零个或多个数据元素的有限序列

• 首先它是一个序列
• 其次它是有限的:
  若将线性表记为(a1,...,ai-1,ai,ai+1,...,an)，则表中ai-1领先于ai，ai领先于ai+1,称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...,n-1时，ai有且仅有一个直接后继，当i=1,2,...,n-1时，ai有且仅有一个直接前驱
• 所以线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表
• 在非空表中的每个数据元素都有一个确定的位置，ai是第i个数据元素，称i为数据元素ai在线性表中的位序
• 在较复杂的线性表中，一个数据元素可以由若干个数据项组成

线性表的抽象数据类型

eg：要实现两个线性表集合A和B的并集操作，说白了就是把存在集合B中但并不存在A中的元素差到A中即可
操作举例：循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中

线性表的顺序存储结构

顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

顺序存储方式

• 线性表的顺序存储结构，说白了就是在内存中找了一块地方，通过占位的形式，把一块内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地上
• C语言的一维数组来实现顺序存储结构：
  把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置
• 线性表的顺序存储的结构代码
  
• 描述顺序存储结构需要三个基本属性：
  1. 存储空间的起始位置：数组date，它的存储位置就是存储空间的存储位置
  2. 线性表的最大存储容量：数组长度MaxSize
  3. 线性表的当前长度：length

数据长度与线性表长度区别

• 数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般不变的
• 线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的
• 在任意时刻，线性表的长度应该小于等于数组的长度

地址计算方法

• C语言中的数组是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系
• 用数组存储顺序意味着要分配固定长度的数组空间
  由于线性表中可以进行插入和删除操作，因而分配的数组空间要大于等于当前线性表的长度
• 存储器中的每个存储单元都有自己的编号，这个编号被称为地址
• 由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的
  eg：假设占用c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足（LOC表示获得存储位置的函数）: LOC(ai+1)=LOC(ai)+c
• 第i个数据元素ai的存储位置可以由a1推算出：LOC(ai)=LOC(a1)+(i-1)c
• 这个公式的存储时间性能为O(1),我们通常把具有这一特点的存储结构称为随机存储结构

顺序存储结构的插入和删除

获得元素操作

插入操作

插入算法的思路：

1. 如果插入位置不合理，抛出异常
2. 如果线性表的长度大于等于数组长度，则抛出异常或动态增加容量
3. 从最后一个元素向前遍历到第i个位置，分别将它们都向后移动一个位置
4. 将要插入元素填入位置i处
5. 表长加一

实现代码：

删除操作

删除算法的思路：

1. 如果删除位置不合理，抛出异常
2. 取出删除元素
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置
4. 表长减1

实现代码如下：

时间复杂度

1. 最好情况，插入最后一个位置或者删除最后一个元素，时间复杂度为O(1)
2. 最坏情况，插入到第一个位置或者删除第一个元素，时间复杂度为O(n)
3. 平均时间复杂度还是O(n)

线性表顺序存储结构的优缺点

1. 优点：
   • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
   • 可以快速地存取表中任一位置的元素
2. 缺点：
   • 插入和删除操作需要移动大量元素
   • 当线性表长度变化较大时，难以确定存储空间的容量
   • 造成存储空间的“碎片”

线性表的链式存储结构

顺序存储结构不足的解决办法

• 不考虑相邻位置，哪里有空位就去哪，只需要让每个元素知道它下一个元素的位置(内存地址)

线性表链式存储结构定义

• 特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的
• 在链式结构中，除了要存放数据元素信息外，还要存储它的后继元素的存储地址

为了表示每个数据元素 ai 与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 a1 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点

n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2,...,an)的链式存储结构，因为此链表的每一个结点只包含一个指针域，所以叫做单链表

我们把链表中第一个结点的存储位置叫做头指针，整个链表的存储就必须是从头指针开始进行，之后的每一个结点，其实就是上一个的后继指针指向的位置

线性链表的最后一个结点指针为“空”(通常用NULL或"^"符号表示)

为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点，头结点的数据域可以不存储任何信息

头指针和头结点的异同

1. 头指针：
   • 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
   • 头指针具有标识作用，所以常用头指针冠以链表的名字
   • 无论链表是否为空，头指针均不为空，头指针是链表的必要元素
2. 头结点：
   • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可以存放链表的长度)
   • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
   • 头结点不一定是链表必要要素

线性表链式存储结构代码描述

单链表中，我们在C语言中可用结构指针来描述

• 结点由存放数据元素的数据域、存放后继结点地址的指针域组成
  eg：假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->date来表示，结点ai的指针域可以用p->next来表示，p->next指向第i+1个元素，即指向ai+1数据域的指针

单链表的读取

获得链表第i个数据的算法思路：

1. 声明一个结点p指向链表第一个结点，初始化j从1开始
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，返回结点p的数据
   实现代码算法如下：
   

• 最坏情况的时间复杂度是O(n)
• 由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此主要核心思想就是"工作指针后移"

单链表的插入与删除

单链表的插入

• s->next = p->next p->next=s
• 如果顺序调换，则出现s->next=s

单链表第i个数据插入结点的算法思路：

1. 声明一结点p指向链表第一个结点，初始化j从1开始
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，在系统中生成一个空结点s
5. 将数据元素e赋值给s->data
6. 单链表的插入标准语句s->next = p->next p->next = s
7. 返回成功
   代码实现：
   

单链表的删除

• p->next=p->next->next也可以q=p->next p->next=q->next

单链表第i个数据删除结点的算法思路:

1. 声明一结点p指向链表的第一个结点，初始化j从1开始
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
3. 若到链表末尾p为空，则说明第i个元素不存在
4. 否则查找成功，将欲删除的结点p->next赋值给q
5. 单链表的删除标准语句p->next=q->next
6. 将q结点中的数据赋值给e，作为返回
7. 释放q结点
8. 返回成功

单链表第i个数据删除结点的算法思路：

• 单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势
• 单链表插入和删除算法，时间复杂度都是O(n)
• 对于插入或删除数据越频繁的操作，单链表的效率优势就越明显

单链表的整表创建

单链表整表创建的算法思路：

1. 声明一结点p和计数器变量i
2. 初始化一空链表L
3. 让L的头结点的指针指向NULL
4. 循环：
   • 生成一新结点赋值给p
   • 随机生成一数字赋值给p的数据域p->date
   • 将p插入到头结点与前一新结点之前

实现代码：
这种算法称为头插法

---

这种为尾插法

单链表的整表删除

算法思路：

1. 声明一结点p和q
2. 将第一个结点赋给p
3. 循环：
   • 将下一个结点赋给q
   • 释放p
   • 将q赋值给p

实现代码算法：

单链表结构与顺序存储结构的优缺点

• 存储分配方式
  1. 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
  2. 单链表采用链式存储结构，用一组任意的存储元素存放线性表的元素
• 时间性能
  • 查找
    1. 顺序存储结构O(1)
    2. 单链表O(n)
  • 插入和删除
    1. 顺序存储结构需要平均移动表长一般的元素，时间为O(n)
    2. 单链表在找出某位置的指针后，插入和删除时间仅为O(1)
• 空间性能
  1. 顺序存储结构需要预分配存储空间，分大了，浪费；分小了易发生上溢
  2. 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

静态链表

数组的元素都是由两个数据域组成，data和cur，data用来存放数据元素，cur相当于指针，存放该元素的后继在数组中的下标

• 这种用数组描述的链表叫做静态链表
• 为了我们方便插入数据，我们通常会把数组建立得大一些

静态链表的插入操作

• 为了辨明数组中哪些分量未被使用，解决的办法时将所有未被使用的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，从备用链表上取得第一个结点作为待插入的新结点
• 修改cur值

静态链表的删除操作

• 先把最后一个元素的cur的值改为删除后的第一个元素的下标值，最后一个元素的cur值为起始的下标0,起始下标0的cur值改为删除元素的下标值，删除元素的cur改为之前要填充的位置的下标值

静态链表的优缺点

• 优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
• 缺点：
  1. 没有解决连续储存分配带来的表长难以确定的问题
  2. 失去了顺序存储结构随机存取的特性

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环列表

• 用指向终端结点的尾指针来表示循环链表，这样查找的时间复杂度就变成O(1)

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域

总结