第二章 线性表
线性表的基本概念
线性表是由 n 个数据元素（结点）组成的 有限序列。
数据元素的个数 n 定位为表的长度：
- n = 0 时，称为 空表，记作 () 或
；
- 将非空的线性表（n > 0），记作：
；
线性表的 描述：
-
为 起始结点，
为 终端结点；
- 对任意相邻结点
和
，
- 数据元素
线性表的 逻辑结构特征：
- 线性表中结点具有 一对一 的关系；
- 有且 仅有一个起始结点
- 有且 仅有一个终端结点
，没有直接前驱，有且仅有一个直接前驱
；
- 其余的内部结点
和一个直接后继
线性表的 基本运算：
| 命令 | 含义 | 描述 |
|---|---|---|
Initiate(L) |
初始化 | 建立 一个空表L |
Length(L) |
求表长度 | 返回线性表L的 长度 |
Get(L,i) |
取表元 | 返回线性表 第 i 个 元素，当 i 不满足 1<=i<=Length(L) 时，返回一个特殊值 |
Locate(L,x) |
定位 | 查找 元素值等于 x 的结点，存在多个值时返回结点中最小序号的值，找不到则返回 0 |
Insert(L,x,i) |
插入 | 在线性表 第 i 个 元素前 插入 一个值为 x 的新数据元素 |
Delete(L,i) |
删除 | 删除 线性表 第 i 个 元素 |
线性表的顺序存储
线性表的顺序存储的方法是：将表中的结点依次存放在计算机内存中 一组连续的存储单元 中，数据元素在线性表中的邻接关系决定它们在存储中间的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。
用顺序存储实现的线性表称为 顺序表。一般使用 数组 来表示顺序表。
顺序表是用 一维数组 实现的线性表，数组下标可以看成是元素的相对地址。
线性表顺序存储的类型定义
顺序存储线性表时，需要存储：存储单元大小、数据个数 。
- 线性表大小：MaxSize
- 线性表长度：Length
- 所存放数据的类型：DateType
顺序存储结构的特点：
- 线性表的逻辑结构与存储结构一致；
- 可以对数据元素实现随机读取；
线性表的基本运算在顺序表上的实现
顺序表的插入
插入算法的注意点：
- 当表空间已满，不可再做插入操作；
- 当插入位置为非法位置，不可做正常插入操作；
合法位置：1 <= i <= n+1
插入算法的分析：
假设线性表中含有 个数据元素
在进行插入操作时，有 个位置可插入
在每个位置插入数据的概率是：
在 位置插入时，要移动
个数据
假定在 个位置上插入元素的可能性相等，则平均移动元素的个数为：
平均时间复杂度为：
顺序表的删除
删除算法的注意点：
- 当要删除第 i 个元素的位置不在表长范围内时，为非法位置，不能做正常的删除操作；
合法位置：1 <= i <= n
删除算法的分析：
假设线性表中含有 个数据元素
在进行删除操作时，有 个位置可删除
在每个位置删除数据的概率是：
在 位置删除时，要移动
个数据
假定在 个位置上删除元素的可能性相等，则平均移动元素的个数为：
平均时间复杂度为：
顺序表的定位
定位算法 LocateSeqlist(L,X) 的功能是：求L中值等于X的结点的 最小序号，当不存在这种结点时结果为0。
序号：指第几个。
定位算法的分析：
假定在 个位置上定位元素的可能性相等，则平均移动元素的个数为：
平均时间复杂度为：
顺序表实现算法的分析
在分析线性表的顺序表实现算法时，一个重要指标就是数据元素的比较和移动的次数。
条件：假设表的长度 length=n
顺序表的 优点：
- 无需增加额外的存储空间（为表示结点间的逻辑关系）；
- 可以 方便地随机存取 表中的任一结点；
顺序表的 缺点：
- 插入和删除运算不方便，必须移动大量的结点；
- 顺序表要求占用连续的空间，存储分配只能预先斤进行，因此 当表长度变化较大时，难以确定合适的存储规模；
线性表的链接存储
链接方式存储的线性表简称为 链表。
链表的具体存储方式：
- 用一组 任意 的存储单元来存放；
- 链表中结点的逻辑次序和物理次序 不一定相同。还必须存储指示其后继结点的地址信息；
单链表
结点结构分析：
- data 域：存放结点值的 数据域；
- next 域：存放结点的直接后继的地址的 指针域（链域）；
所有结点通过指针链接而组成单链表。其中：
- NULL：称为 空指针；
- Head：称为 头指针变量，存放链表中第一个结点的地址；
单链表的一般图示法：
使用 箭头 来表示链域中的指针，单链表可以表示为下图形式。
单链表中 第一个 结点内一般 不存数据，称为 头结点，利用头指针存放该结点地址。
头结点的结点结构：
- data 域，不存数据；
- next 域，存放 首结点 的地址，或者是空指针；
为什么加设头结点？：为了方便运算。
单链表的类型定义：
typedef struct node
{
DataType data;
struct node *next;
} Node, *LinkList;
线性表的基本运算在单链表上的实现
单链表的初始化
空表由一个头指针和一个头结点组成，算法描述如下：
LinkList InitiateLinkList()
{
LinkList head;
head = malloc(sizeof(Node)); // 动态创建一个结点，它是头结点
head -> next = NULL;
return head;
};
// malloc(size)：开辟空间
在算法中，变量 head 是链表的头指针，它指向新创建的结点，即头结点。一个空单链表仅有一个头结点，它的指针域为NULL。
单链表的求表长
int lengthLinkList(LinkList head)
{
Node *p = head;
int j = 0;
while(p -> next != NULL)
{
p = p -> next;
j ++;
};
return j;
};
单链表的读表元素
Node *GetLinkList(LinkList head, int i)
{
Node *p = head -> next;
int c = 1;
while((c < i) && (p != NULL))
{
p = p -> next;
c ++;
};
if(i == c) return p;
else return NULL;
};
单链表的定位
在定位运算中，找到需要的结点，则返回其对应的 序号。若为找到，则返回 0。
int locateLinkList(LinkList head, DateType x)
{
Node *p = head -> next;
int i = 1;
while(p != NULL && p -> data != x)
{
p = p -> next;
i ++;
};
if (p != NULL) return i;
else retrun 0;
};
单链表的插入
void InsertLinkList(LinkList head, DataType x, int i)
{
Node *p, *q;
if (i == 1) q = head;
else q = GetLinkList(head, i - 1);
if (q == NULL) exit("找不到插入的位置");
else
{
p = malloc(sizeof(Node));
p -> data = x;
p -> next = q -> next;
q -> next = p;
};
};
单链表的删除
void DeleteLinkList(LinkList head, int i)
{
Node *p, *q;
if (i == 1) q = head;
else q = GetLinkList(head, i - 1);
if (q != NULL && q -> next != NULL)
{
p = q -> next;
q -> next = p -> next;
free(p);
}
else exit("找不到删除的结点");
}
// free()，释放内存空间
其他链表
循环链表
普通链表的 终端结点 的 next 值为 NULL。
循环链表的 终端结点 的 next 指向 头结点。在循环链表中，从任一结点出发都能够扫描整个链表。
在循环链表中附设一个 rear 指针指向尾结点。
双向循环链表
在链表中设置 两个 指针域，一个指向后继结点，一个指向前驱结点。这样的链表叫做 双向循环链表。
双向循环链表的 结构定义：
typedef struct dbnode {
DataType data;
struct dbnode *prior, *next;
}DlinkList, *dbpointer;
双向循环链表适合应用在 需要经常查找结点的前驱和后继的场合。找前驱和后继的复杂度均为： 。
假设双向循环链表中 p 指向某结点，则有：p -> next -> prior 与 p -> prior -> next 相等。
双向循环链表的结点删除
- p -> next -> prior = p -> prior;
- p -> prior -> next = p -> next;
- free(p);
双向循环链表的结点插入
在 p 所指向的结点的后面插入一个新结点 *t，需要修改四个指针：
- t -> prior = p;
- t -> next = p -> next;
- p -> next -> prior = t;
- p -> next = t;
顺序实现和链式实现的比较
单链表的每个结点包括 数据域 与 指针域，指针域需要占用额外空间。
顺序表 要 预先分配内存空间，如果预先分配得过大，将造成浪费，若分配得过小，又将发生上溢。
单链表 不需要 预先分配内存空间，只要内容空概念没有耗尽，单链表中的结点个数就没有限制。
时间性能的比较
| 顺序表 | 链表 | |
|---|---|---|
| 读表元 | O(1) | O(n) |
| 定位 | O(n) | O(n) |
| 插入 | O(n) | O(n) |
| 删除 | O(n) | O(n) |
