第3章 线性表

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

线性表的定义

线性表(List):零个或多个数据元素的有限序列。

线性表元素的个数 n (n>=0) 定义为线性表的长度，当 n = 0时，称为空表。

线性表的抽象数据类型

ADT 线性表(List)
Data
​ 线性表的数据对象集合为{a₁,a₂,……,a_n},每个元素的类型均为DataType。其中，除第一个元素a₁外，每一个元素有且只有一个直接前驱元素，除了最后一个元素a_n外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation

​ InitList (*L):初始化操作，建立一个空的线性表L。

​ ListEmpty(L)：若线性表为空，返回true，否则返回false。

​ ClearList(*L)：将线性表清空。

​ GetElem(L,i,*e)：在线性表L中的第i个位置元素值返回给e。

​ LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中的序号表示成功；否则，返回0表示失败。

​ ListInsert(*L,i,e)：在线性表L中的第i个位置插入新元素e。

​ ListDelete(L,i, e)：删除线性表L中的第i个位置元素，并用e返回其值。

​ ListLength(L)：返回线性表L的元素个数。

endADT

线性表的顺序存储结构

顺序存储定义

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

顺序存储方式

一维数组来实现顺序存储结构。

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

数组的长度是存放线性表的存储空间的长度。线性表的长度是线性表中数据元素的个数。在任意时刻，线性表的长度应该小于等于数组的长度。

地址计算方法

存储器中每个存储单元都有自己的编号，这个编号称为地址。

LOC(a_i) = LOC(a₁) + (i-1)*c

存取的时间性能为O(1)。

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

获得元素操作

只要i的数值在数组的下标范围内，就是把数组的第i-1下标的值返回即可。

插入操作

插入算法的思路：

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

删除操作

删除算法的思路：

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

插入和删除的时间复杂度，最好情况为O(1)，最坏情况为O(n)，平均时间复杂度为O(n)。

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

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
• 可以快速地存取表中任一位置的元素。

缺点：

• 插入和删除操作需要移动大量元素。
• 当线性表长度变化较大时，难以确定存储空间的容量。
• 造成存储空间的”碎片”。

线性表的链式存储结构

线性表链式存储结构定义

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

​ n个结点(a_i的存储映像)链结成一个链表，即为线性表(a₁,a₂,…,a_n)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

​ 链表中的第一个结点的存储位置叫做头指针。在单链表的第一个结点前附设一个结点，称为头结点。头结点的指针域存储指向第一个结点的指针。

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

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

1
2
3
4
5
6
7

/*线性表的单链表存储结构*/
typedef struct Node
{
  ElemType data;
  struct Node *next;
} Node;
typedef struct Node *LinkList; /*定义LinkList*/

单链表的读取

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

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

单链表的插入与删除

单链表的插入

单链表第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. 返回成功。

单链表的删除

单链表第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. 返回成功。

单链表的整表创建

头插法

尾插法

单链表的整表删除

单链表整表删除的算法思路如下：

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

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

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表中的元素。

时间性能

• 查找 顺序存储结构O(1) 单链表O(n)
• 插入和删除 顺序存储结构需要平均移动表长一半的元素，时间为O(n) 单链表在显出某位置的指针后，插入和删除时间仅为O(1)

空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢。
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

静态链表

用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

静态链表优缺点

优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：

• 没有解决连续存储分配带来的表长难以确定的问题。
• 失去了顺序存储结构随机性存取的特性。

循环链表

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

双向链表

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