第二章 线性表

一 线性表的逻辑结构

1 线性表定义

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列。其中n为表长。当n=0时线性表是一个空表

线性表中第一个元素称为表头元素；最后一个元素称为表尾元素。

除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

二 线性表的顺序存储结构

1 顺序表定义

线性表的顺序存储又称为顺序表。

它是用一组地址连续的存储单元（比如C语言里面的数组），依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的在具体的题目中需要分辨清楚

2 建立顺序表的三个属性

1.存储空间的起始位置（数组名data）

2.顺序表最大存储容量（MaxSize）

注意：动态分配并不是链式存储，同样还是属于顺序存储结构，只是分配的空间大小可以在运行时决定。

顺序表当前的长度（length）

总结

顺序表最主要的特点是随机访问（C语言中基于数组），即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。

顺序表的存储密度高，每个结点只存储数据元素。无需给表中元素花费空间建立它们之间的逻辑关系（因为物理位置相邻特性决定）

顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

三 顺序表的操作

1 插入算法思路

判断i的值是否正确

判断表长是否超过数组长度

从后向前到第i个位置，分别将这些元素都向后移动一位

将该元素插入位置i并修改表长

最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)。

最坏情况：在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O(n)。

平均情况：假设pi（pi=1/(n+1) ）是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为

$$\sum _{i=1}^{n+1}{P}_i\left(n-i+1\right)=\sum _{i=1}^{n+1}\frac{1}{n+1}\left(n-i+1\right)=\frac{1}{n+1}\sum _{i=1}^{n+1}\left(n-i+1\right)=\frac{1}{n+1}\bullet \frac{n\left(n+1\right)}{2}=\frac{n}{2}$$

线性表插入算法的平均时间复杂度为O(n)

2 删除算法思路

判断i的值是否正确

取删除的元素

将被删元素后面的所有元素都依次向前移动一位

修改表长

最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)。

最坏情况：删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)。

平均情况：假设pi(pi=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为

$$\sum _{i=1}^n{P}_i\left(n-i\right)=\sum _{i=1}^n\frac{1}{n}\left(n-i\right)=\frac{1}{n}\sum _{i=1}^n\left(n-i\right)=\frac{1}{n}\bullet \frac{n\left(n-1\right)}{2}=\frac{n-1}{2}$$

线性表删除算法的平均时间复杂度为O(n)

四 线性表的链式存储结构

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。

为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。

1 单链表

通常用“头指针”来标识一个单链表，例如LinklistL那么头指针L就代指一个单链表，头指针为“NULL”时则表示一个空表。

单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点

2 头结点和头指针的区别？

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息

3 为什么要设置头结点？

1.处理操作起来方便例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了

2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

五 单链表的操作

1 头插法建立单链表

建立新的结点分配内存空间，将新结点插入到当前链表的表头

2 尾插法建立单链表

建立新的结点分配内存空间，将新结点插入到当前链表的表尾

需要增加一个指向表尾元素的尾指针

3 按序号查找结点

在单链表中从第一个结点出发，顺指针next域逐个往下搜索，直到找到第i个结点为止,否则返回最后一个结点指针域NULL。

4 按值查找结点

从单链表第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。

5 插入

插入操作是将值为x的新结点插入到单链表的第i个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i−1个结点，再在其后插入新结点。

算法思路

1.取指向插入位置的前驱结点的指针

①p=GetElem(L,i-1);

2.令新结点*s的指针域指向*p的后继结点

②s->next=p->next;

3.令结点*p的指针域指向新插入的结点*s

③p->next=s;

6删除

删除操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i−1个结点，即被删结点的前驱结点，再将其删除。

算法思路

1.取指向删除位置的前驱结点的指针p=GetElem(L,i-1);

2.取指向删除位置的指针q=p->next;

3.p指向结点的后继指向被删除结点的后继p->next=q->next

4.释放删除结点free(q);

六 双链表

1 插入(方法不唯一)

①s->next=p->next;

②p->next->prior=s;

③s->prior=p;

④p->next=s;

2 删除

①p->next=q->next;

②q->next->prior=p;

③free(q);

七 循环链表和静态链表

（一） 循环链表

1 循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环

循环单链表的判空条件不是头结点的后继指针是否为空，而是它是否等于头指针

2 循环双链表

类比循环单链表，循环双链表区别于双链表就是首尾结点构成环

当循环双链表为空表时，其头结点的prior域和next域都等于Head。

（二） 静态链表

1 静态链表定义

静态链表是用数组来描述线性表的链式存储结构。

静态链表仍然包含数据域和指针域（数组下标），又称游标。

数组第一个元素不存储数据，它的指针域存储第一个元素所在的数组下标。

链表最后一个元素的指针域值为-1。