考研数据结构与算法（二）线性表¶
一、线性表定义¶
线性表是最常用且最简单的一种数据结构，简言之，一个线性表是 \(n\) 个数据元素的有限序列，当 \(n\) 为 \(0\) 的时候线性表是一个空表，用 \(L\) 命名线性表，则一般表示为：
其中， \(a_1\) 表示表首元素， \(a_n\) 表示表尾元素，除了表首元素外其余元素皆有直接后继节点，除了表尾元素其余元素皆有直接前驱节点。
线性表是一个相当灵活的数据结构，他的长度可根据需要增长或缩短，即对线性表的元素不仅可以访问，还可以进行插入和删除等
于是我们能得出线性表的特点如下：
- 表中元素的个数 有限 ，但是可以扩张和删减
- 表中元素具有逻辑上的顺序性 表中元素有其先后次序。
- 表中元素都是数据元素，每个元素都是单个元素。
- 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间
- 表中元素具有抽象性， 即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
二、线性表基本操作¶
一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其 本操作来实现。线性表的主要操作如下
| name | operation |
|---|---|
InitList(&L) |
初始化表，构造一个空的线性表 |
Length(L) |
求表长，返回线性表 \(L\) 的长度，即 \(L\) 中数据元素的个数。 |
LocateElem(L,e) |
按值查找操作，在表 \(L\) 中查找具有给定关键宇值的元素。 |
GetElem(L,i) |
按位查找操作，获取表 \(L\) 中第 \(i\) 个位置的元素的值 |
Listinsert(&L,i,e) |
插入操作，在表 \(L\) 中的第 \(i\) 个位置上插入指定元素 |
ListDelete(&L,i,&e) |
删除操作，删除表 \(L\) 中第 \(i\) 个位置的元素，并用 \(e\) 返回删除元素的值。 |
PrintList(L) |
输出操作 ，按前后顺序输出线性表 \(L\) 的所有元素值 |
Empty(L) |
判空操作，若 \(L\) 为空表， 则返回 \(true\) ，否则返回 \(false\) |
DestroyList(&L) |
销毁操作 ,销毁线性表，井释放线性表 \(L\) 所占用的内存空间。 |
三、线性表的顺序表示¶
这个顺序表示是从物理上定义的，线性表的顺序存储 称顺序表 它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得 逻辑上相邻的两个元素在物理位置上也相邻 。这个可以简单理解为就是数组。
由于顺序表在逻辑和物理上都是连续的特点，我们很容易通过物理位置的间隔长度和单个元素的大小推断出这个间隔的元素个数，或者反过来计算出一定元素占用的空间，假设每一个元素占用 \(l\) 的物理空间，\(LOC(a_i)\) 表示 \(a_i\) 元素的物理位置，那么可以得到：
以及从第一个元素物理位置推出第 \(i\) 个元素的物理位置：
简单的一张图来表示：
这里需要注意的是，数组下表是从 \(0\) 开始的，而顺序表下表是从 \(1\) 开始的
一维数组可以是静态分配的，比如一开始就设定好数组的大小，当然也可以是动态分配的，例如C语言中使用 malloc 分配内存，注意的是这里的动态分配并不是链式存储，仍然是顺序存储，物理结构并未发生改变，只不过分配的空间大小是由程序运行的时候决定。
3.1 顺序表特点¶
由此我们能得到顺序表的一些特点：
- 顺序表最主要的特点是 随机访问 ，即通过首地址和元素序号可在时间 \(0(1)\)内找到指定的元素。
- 顺序表的 存储密度高 ，结点只存储 数据元素 。
- 顺序表逻辑上相邻的元素物理上也相邻，所以 插入和删除 操作需要 移动大量元素
3.2 操作实现¶
这里提前先说一下，假设表的元素下标是从 \(1\) 开始的，下面展示的是一些基础或者说常用的操作函数
3.2.1 插入操作¶
在顺序表 \(L\) 的第 \(i\) 个位置（假设表的元素从1开始）插入新元素 \(e\) 。若插入失败返回 false ，否则将顺序表中第 \(i\) 个元素以及后面所有元素往后移动一个位置，然后将新元素放在第 \(i\) 个位置上
bool Listinsert(List &L,int i,ElemType e) {
int len = L.length;
if(i < 1 || i > len + 1) return false;//判断插入的位置是否合法
if(len == L.MaxSize) return false;//判断表中的空间是否占满
for(int j = len;j >= i ; --j)//将i以及后面的元素全部往后移动一位
L.data[j + 1] = L.data[j];
L[i] = e;//将元素e放到第i个位置
L.length++;
return true;
}
3.2.2 删除操作¶
删除操作和插入操作类似，先判断删除的条件是否合法，然后直接第 \(i\) 个元素之后的元素往前覆盖即可
bool ListDelete(List &L,int i,ElemType &e) {
int len = L.length;
if(i < 1 || i > len) return false;//判断删除的位置是否合法
e = L.data[i];
for(int j = i;j < len; ++j)
L.data[j] = L.data[j+1]；
L.length++;
return true;
}
3.2.3 查找操作¶
这里就实现一下按值查找吧，我们从前往后，或者从后往前不断的比对顺序表中的元素和我们查找的元素的值是否相等，如果相等的话，那么我们就返回当前的位置，如果没查找到，那么就返回 -1
int LocateElem(List &L,ElemType e) {
int len = L.length;
for(int i = 1;i <= len; ++i)
if(L.data[i] == e)
return i;
return -1;
}
这里最好的情况就是查找的元素在第一个位置，复杂度就为 \(O(1)\) ，最坏的情况在最后一个位置，复杂度为 \(O(n)\) ，平均复杂度就是 \(\frac{O(n) + O(1)}{2}= O(n)\)
3.3 顺序表合并¶
问题：给定两个非递减的顺序表，然后将这两个表合并成一个新的表，同样希望按照非递减排列
其实思路很简单，我们同时遍历两个顺序表，然后将两个表的当前元素进行比较，直到其中一个表遍历完成，然后我们再将另一个表剩下的元素一次加入即可。不难得到如下代码
void MergeList(List &a,List &b,List &c){
int lena = a.length,lenb = b.length;
c.length = lena + lenb;
c.data = (ElemType*)malloc(c.length * sizeof(ElemType));//给c表申请空间
int i = 1,j = 1,k = 1;
while(i <= lena && j <= lenb) {//不断的比对两表中当前位置的元素的大小
if(a.data[i] < b.data[j])//如果a表中元素较小，则插入a表当前的元素
c.data[k++] = a.data[i++];
else //如果b表当前元素较小，则插入b表当前的元素
c.data[k++] = b.data[j++];
}
while(i <= lena) c.data[k++] = a.data[i++];//插入a顺序表剩下的元素
while(j <= lenb) c.data[k++] = b.data[j++];//插入b顺序表剩下的元素
}
四、线性表的链式表示¶
我们上面谈了关于顺序存储的优点和缺点，其中最明显的就是如果发生插入和删除的操作，需要移动大量的元素，导致了效率非常的低效，那么链式存储就帮我们解决了这一问题，让我们从 \(O(n)\) 的复杂度降低到了 \(O(1)\) 的复杂度
在链式存储中最为简单的结构便是 单链表 ，它是通过每一个结点（数据元素）存储的一个后继节点指针串联起来，形成了一个在逻辑上连续，而空间 不一定 连续的链式结构，对于每一个数据元素我们称其为 结点 ，一个结点包括两个域。其中存储数据元素信息的域称为 数据域 ，存储直接 后继 存储位置（一般用指针存储）的域称为指针域，多个结点连接在一起就构成了一个链表，即线性表的链式存储
一个常见的链表的结构如下：
typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
}Node;
关于头指针部分：
头指针的数据与可以不存放数据，只需要指针域指向第一个结点元素即可，但是也是可以存放数据的，即头指针就是整个链表的第一个元素结点，这里头指针不存放数据是为了方便 统一化管理 ，加入我们的链表删除所有的元素，当前链表为空了，这时我们如果需要添加元素，在头指针不为空的版本的话那么就需要特判一下，而如果头指针置空那么则直接往后加入元素即可，换句话说， 头指针数据域为空是为了空链表和非空链表的统一化操作
关于尾结点部分：
尾部的结点其实就是最后一个结点元素，我们只需要将其指针域置为 NULL 即可
4.1 链式表特点¶
由此我们能得到关于链式表的一些特点：
- 在插入和删除操作的时候我们只需要修改两个结点的指向复杂度为 \(O(1)\)
- 因为存储空间不连续，不能随机访问，每次查找的效率只能遍历链表，效率非常低下
- 能够大大提高空间的利用率
4.2 操作实现¶
4.2.1 下标找值¶
我们只需要遍历这个链表，找到第 \(i\) 个下标（从0开始）的元素，如果链表长度不够则返回 NULL 否则找到元素则返回元素的指针
Node *GetElem(Node *Lhead,int i) {
Node p = Lhead->next;
int j = 0;
while(p && j < i){
p = p->next;
j++;
}
if(p) return p;
return NULL;
}
4.2.2 按值查找¶
与按照下标查找相对应的就是按值查找了，我们同样的遍历这个链表，然后如果发现值相同，然后返回当前的指针，如果找不到则返回 NULL
Node *LocateElem(Node *Lhead,ElemType e) {
Node p = Lhead->next;
while(p && p->data != e)
p = p->next;
return p;
}
4.2.3 头部插入¶
我们每次只需要操作头指针和第一个结点的指针，我们让当前新的元素的后继指针指向头指针后继结点指向的元素，然后再让头指针的后继指针指向当前结点，这样就完成了结点的头部插入
void List_Head_Insert(Node *Lhead,ElemType e){
Node *t = (Node *)malloc(sizeof(Node));
t->data = e;
t->next = Lhead->next;
Lhead->next = t;
}
4.2.4 尾部插入¶
尾部插入实际上是和头部插入相对应的一个方法，就是每次插入到链表的末尾，我们只需要先遍历链表，然后找到最末尾的位置，最后直接将最末尾的结点指向新的结点即可
void List_Tail_Insert(Node *Lhead,ElemType e){
Node *t = (Node *)malloc(sizeof(Node));
t->data = e;
t->next = NULL;
Node *p = Lhead;
while(p->next) p = p->next;
p->next = t;
}
4.2.4 中间插入¶
如果说想将当前的元素值 \(e\) 插入到链表的第 \(i\) 个位置，我们需要先找到第 \(i-1\) 个位置
- 如果当前位置是尾结点，那么直接将当前位置的后继指针指向新元素结点即可
- 如果当前位置是中间结点，那么我们就将第 \(i-1\) 个结点当初头结点元素，然后头插法就好了
- 如果当前位置超过了链表的长度，那么就不能插入
那么我们如果成功插入就返回 true 否则就返回 false
bool ListInsert(Node *Lhead,int i,ElemType e){
Node *t = (Node *)malloc(sizeof(Node));
t->data = e;
t->next = NULL;
Node *p = Lhead;
int j = 0;
while(p && j < i - 1){
p = p->next;
j++;
}
if(p == NULL) return false;
if(p->next == NULL) {
p->next = t;
return true;
}
t->next = p->next;
p->next = t;
return true;
}
4.2.5 删除操作¶
如果我们要删除第 \(i\) 个位置的元素，那么我们同样的需要先遍历链表来判断删除的位置是否有效，我们需要先找到第 \(i-1\) 个元素的位置，然后再来将当前元素的后继指针直接指向第 \(i\) 个元素的后继结点。之后 free 掉第 \(i\) 个结点即可
bool ListDelete(Node *Lhead,int i){
Node *p = Lhead;
int j = 0;
while(p && j < i - 1){
p = p->next;
j++;
}
if(p == NULL) return false;
if(p->next == NULL) return false;
Node *t = p->next;
p->next = t->next;
free(t);
return true;
}
4.3 链式表合并¶
问题：给定两个非递减的链式表，然后将这两个表合并成一个新的表，同样希望按照非递减排列
思路：和上面的顺序表的思路相同，只不过在数据插入方面就没有上面的方便了
void List_Tail_Insert(Node *Lhead,ElemType e){
Node *t = (Node *)malloc(sizeof(Node));
t->data = e;
t->next = NULL;
Node *p = Lhead;
while(p->next) p = p->next;
p->next = t;
}
void MergeList(Node *a,List *b,List *c){
Node *pa = a, *pb = b, *pc = c;
while(pa && pb) {
if(pa->data < pb->data) {
List_Tail_Insert(pc,pa->data);
pa = pa->next;
}
else {
List_Tail_Insert(pc,pb->data);
pb = pb->next;
}
}
while(pa) {
List_Tail_Insert(pc,pa->data);
pa = pa->next;
}
while(pb) {
List_Tail_Insert(pc,pb->data);
pb = pb->next;
}
}
优化1¶
这里我们发现我们的内存其实是使用了两倍的空间的，每次在C链表插入元素的时候都是重新 malloc 申请的一块空间，好处就是 数据隔离 了，不会因为A链表和B链表的结点释放导致C链表结点消失，但是如果我们需要提高 空间利用率 的话我们直接将当前结点的指针传入，并让C链表指向即可，不难得到如下代码：
void List_Tail_Insert(Node *Lhead,Node *e){
e->next = NULL;
Node *p = Lhead;
while(p->next) p = p->next;
p->next = t;
}
void MergeList(Node *a,List *b,List *c){
Node *pa = a, *pb = b, *pc = c;
while(pa && pb) {
if(pa->data < pb->data) {
List_Tail_Insert(pc,pa->data);
pa = pa->next;
}
else {
List_Tail_Insert(pc,pb->data);
pb = pb->next;
}
}
while(pa) {
List_Tail_Insert(pc,pa->data);
pa = pa->next;
}
while(pb) {
List_Tail_Insert(pc,pb->data);
pb = pb->next;
}
free(pa);
free(pb);
}
优化2¶
我们发现我们每次指针都是从头遍历到尾部，然后新增，那么我们是不是可以搞一个尾指针呢，在我们的数据结构的定义里面，我们定义一个 tail 指针，一直指向的是最后一个结点，当链表为空的时候指向的就是头指针，这样的话，我们每次尾插的时候更新一下尾指针就能实现 \(O(1)\) 的复杂度插入了，于是我们的数据结构变为了：
typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
struct Node *tail;//指针域
}Node;
不难得出代码
void List_Tail_Insert(Node *Lhead,Node *e){
e->next = NULL;
Lhead->tail->next = e;
Lhead->tail = e;//或者说 Lhead->tail = Lhead->tail->next
}
void MergeList(Node *a,List *b,List *c){
Node *pa = a, *pb = b, *pc = c;
while(pa && pb) {
if(pa->data < pb->data) {
List_Tail_Insert(pc,pa);
pa = pa->next;
}
else {
List_Tail_Insert(pc,pb);
pb = pb->next;
}
}
while(pa) {
List_Tail_Insert(pc,pa);
pa = pa->next;
}
while(pb) {
List_Tail_Insert(pc,pb);
pb = pb->next;
}
free(pa);
free(pb);
}
五、静态链表¶
静态链表借助数组来描述线性表的链式存储结构，每一个结点也有数据域和指针域，只不过现在的指针域从指针变为了 游标 （可以简单理解为数组下标），和顺序表一样需要提前分配一块连续的空间，每一个结点之间通过游标串联
静态链表的结构如下：
#define N 100
struct SList{
ElemType data;
int next;
}SLinkList[N];
结尾标志一般用 next=-1 结束。静态链表的插入 、删除操作与动态链表的相同， 只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语 （如 Basic ）中，这是 种非常巧妙的设计方法
注意的是，这里 SLinkList 数组的下标就不再是和顺序表一样的意义了，而是当作一个 “地址指针” 换句话说，元素并不是从数组下标的 \(0\) 开始一次往后存放的，他的顺序可能是乱的，例如下标为 \(3\) 的元素的下一个位置可能是下标为 \(1\) ，这个思想其实也是我们在算法竞赛中常用的 链式前向星
注意：与之前的动态链表不同的是，对于结点哪些被使用了，哪些没有被使用（对于没有使用的所有空间，我们将其统称为 备用链表 ），需要我们自己完成实现
malloc和free两个操作函数，我们可以先将未使用的结点串在一起，然后每次申请使用结点的时候，就将当前未使用的结点分配一个给它（如果不为空的话）
5.1 操作实现¶
这里就简单实现一下基础的三个操作，初始化、分配结点、回收结点
5.1.1 初始化¶
因为开始分配的元素个数为 \(N\) 个，我们只需要从前往后将相邻元素串联起来即可，一开始的话整个分配的静态空间都是
void Init_space(SList SLinkList[]) {
for(int i = 0;i < N - 1; ++i) {
SLinkList[i].next = i + 1;
}
SLinkList[N - 1].next = -1;
}
5.1.2 申请结点¶
我们去看备用链表中是否还存在，如果存在的话，我们就直接返回表头的位置，然后表头往后移动一位即可
int Malloc_space(SList SLinkList[]) {
int i = SLinkList[0].next;
if(SLinkList[0].next) //如果备用链表长度不小于等于2那么我们就将头指针指向下一个位置
SLinkList[0].next = SLinkList[i].next;
return i;
}
5.1.3 释放结点¶
释放结点就是将当前释放的结点接到备用链表上面去，为了方便可以使用头插法
void Free_space(SList SLinkList[],int k) {
SLinkList[k].next = SLinkList[0].next;
SLinkList[0].next = k;
}
六、循环链表¶
6.1 循环单链表¶
循环单链表和单链表唯一的区别就在于，循环单链表将其单链表的尾指针指向了头节点，使其构成一个环形结构，而非链状，此时我们如果想完整的遍历一圈的话，应当是从头节点的下一个结点出发，一直再遇到头节点为止，那么遍历的条件从 p != NULL 变为了 p != Lhead
大概长成这样：
- 循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同 ，以让单链表继续保持循环的性质。当然，正是因为循环单链表是 个“环”，因此在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。
- 单链表只能从头到尾才能完整遍历，而循环单链表则可以随便从一处位置开始往后遍历，直到再次遍历到当前结点也能完成一次完整遍历
- 有的时候我们对循环单链表的操作是在表头和表尾进行的，这样我们 不设头指针而设尾指针 更为方便，因为如果是头指针那么我们如果进行一遍尾插法，则需要遍历到末尾结点才行，而如果有尾指针，那么我们直接将新元素指向头节点，然后让尾指针指向新元素即可在 \(O(1)\) 复杂度内完成操作
七、双向链表¶
双向链表在结构上其实变化不大，只不过多了一个指向前一个结点的指针 pre， 新增的好处就是我们如果相对某一个结点进行一些操作，不需要先遍历到这个结点之前的结点的位置，因为我们有一个指向前一个结点的指针，我们直接对这个结点进行一些操作即可
那么双向链表的数据结构如下所示：
typedef struct Node{
ElemType data;//数据域
struct Node *next,*pre;//指针域
}Node;
7.1 操作实现¶
这里只实现插入和删除的操作，因为其他的操作也大差不差
7.1.1 插入操作¶
我们在结点值为k的结点后面插入新元素
bool ListInsert(Node *Lhead,ElemType k,ElemType e){
Node *t = (Node *)malloc(sizeof(Node));
t->data = e;
t->next = NULL;
t->pre = NULL;
Node *p = Lhead;
while(p && p->data != k) p = p->next;
if(p == NULL) return false;
if(p->next == NULL) {
p->next = t;
t->pre = p;
return true;
}
t->next = p->next;
p->next->pre = t;
t->pre = p;
p->next = t;
return true;
}
7.1.2 删除操作¶
删除结点值为 \(k\) 的第一个结点，我们从前往后一一比较，找到第一个值为 \(k\) 的结点然后删除
bool ListDelete(Node *Lhead,ElemType k,ElemType e){
while(p && p->data != k) p = p->next;
if(p == NULL) return false;
if(p->next == NULL) {
p->pre->next = NULL;
free(p);
return true;
}
p->next->pre = p->pre;
p->pre->next = p->next;
free(p);
return true;
}
7.2 双向循环链表¶
从单向循环链表不难得出双向循环循环链表的结构，只不过多了一条 pre 指针需要指向尾结点，结果如下图所示
当链表长度为空的时候，前后指针都是指向头指针结点即：Lhead->next = Lhead->pre = Lhead
八、顺序表和链表的比较¶
8.1 存取方式¶
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第 \(i\) 个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需要从表头开始依次访 \(i\) 次
8.2 逻辑结构与物理结构¶
采用顺序存储时，逻辑上相邻的元素 ，对应的物理存储位置也相邻。 采用链式存储 ，逻辑上相邻的元素 ，物理存储位置则不一定相邻，对应的逻辑关系是通过指针连接来表示的。
8.3 查找、插入和删除操作¶
- 对于 按值查找 ，顺序表无序时 两者的时间复杂度均为 \(O(N)\) ；顺序表有序时，可采用折半查找，此时的时间复杂度 \(O(log_2N)\)
- 对于 按序号查找 ，顺序表支持随机访问，时间复杂度仅为 \(O(1)\) ，而链表的平均时间复杂度为 \(O(N)\) 序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需要修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大
8.4 空间分配¶
- 顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充若再加入新元素 ，则会现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出
- 动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间 ，则会导致分配失败
- 链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。