700字范文 > 线性表详解(静态链表单链表双向链表循环链表)

线性表详解(静态链表单链表双向链表循环链表)

时间：2022-03-23 14:04:31

申明1. 线性表的定义2. 线性表的抽象数据类型3. 线性表的顺序存储结构3. 1 顺序存储定义3. 2 顺序存储方式3. 3 数据长度与线性表长度区别3. 4 地址计算方法4. 顺序存储结构的插入与删除4.1 获得元素操作4.2 插入操作4.3 删除操作4.4 线性表顺序存储结构的优缺点5. 线性表的链式存储结构5.1 顺序存储结构不足的解决方法5.2 线性表链式存储结构定义5.3 头指针与头节点的异同5.4 线性表链式存储结构代码描述6. 单链表的读取7. 单链表的插入与删除7.1 单链表的插入7.2 单链表的删除8. 单链表的整表创建9. 单链表的整表删除10. 单链表结构与顺序存储结构优缺点11. 静态链表11.1 静态链表的插入操作11.2 静态链表的删除操作11.3 静态链表优缺点12. 循环链表13. 双向链表14. 总结回顾15. 专栏知识链接

申明

本文章属于原创，其中参考了程杰老师《大话数据结构》行文结构和内容，侵删。

1. 线性表的定义

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

这里需要强调几个关键的地方。

首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。

然后，线性表强调是有限的，事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

所以线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，称为空表。

在非空表中的每个数据元素都有一个确定的位置，如a1时第一个数据元素，an时最后一个元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

2. 线性表的抽象数据类型

ADT 线性表（List）
Data
线性表的数据对象集合为（a1，a2，…，an），每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
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

对于不同应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

比如，要实现两个线性表A和B的并集操作。即要使得集合A=A∪B。说白了，就是把存在集合B中但不存在A中的元素插入到A中即可。

仔细分析一下这个操作，发现我们只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。

我们假设La表示集合A，Lb表示集合B，则代码实现如下：

/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/void unionL(SqList *La,SqList Lb){int La_len,Lb_len,i;ElemType e; /*声明与La和Lb相同的数据元素e*/La_len=ListLength(*La); /*求线性表的长度 */Lb_len=ListLength(Lb);for (i=1;i<=Lb_len;i++){GetElem(Lb,i,&e); /*取Lb中第i个数据元素赋给e*/if (!LocateElem(*La,e)) /*La中不存在和e相同数据元素*/ListInsert(La,++La_len,e); /*插入*/}}

3. 线性表的顺序存储结构

3. 1 顺序存储定义

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

线性表（a1,a2,…,an）的顺序存储示意图如下：

3. 2 顺序存储方式

即在内存中找一段空间，通过占位的方式，把一定的内存空间占据，然后把相同数据类型的数据元素依次放在这块空地中。既然线性表的每个数据元素的类型都相同，所以可以用C语言的**一位数组来实现顺序存储结构，**即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

来看线性表的顺序存储的代码。

#define MAXSIZE 20/* 存储空间初始分配量 */typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */typedef struct{ElemType data[MAXSIZE]; /* 数组，存储数据元素 */int length; /* 线性表当前长度 */}SqList;

这里，我们就发现描述顺序存储结构需要三个属性：

1. 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

2. 线性表的最大存储容量：数组长度MaxSize。

3. 线性表的当前长度： length。

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

这里有两个概念“数组的长度”和“线性表的长度”需要区分一下。

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。

线性表的长度是线性表中数据元素的个数，随着线性表的插入和删除操作的进行，这个量是变化的。

在任意时刻，线性表的长度应该小于等于数组的长度。

3. 4 地址计算方法

由于我们数数都是从1开始数的，线性表的定义也不能免俗，起始也是1，但是C语言中数组却是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置。

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

存储器中的每个存储单元都有自己的编号，这个编号称为地址。假设占用的是c个单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获得存储位置的函数）。

LOC(ai+1) = LOC(ai) + c

所以对于第i个数据元素ai的存储位置可以由a1推算得出：

LOC(ai) = LOC(a1) + (I - 1) * c

通过这个公式，你可以随时酸楚线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说，都是相等的时间，也就是一个常数，因此我们用算法中学到的时间复杂度的概念来说，它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

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

4.1 获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，即将线性表L中的第i个位置元素值返回，其实是非常简单的。就程序而言，只要i的数值在数组下标范围内，就是把数组第i-1下标的值返回即可。来看代码：

#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) *//* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */Status GetElem(SqList L,int i,ElemType *e){if(L.length==0 || i<1 || i>L.length)return ERROR;*e=L.data[i-1];return OK;}

注意这里返回值类型Status是一个整型，返回OK代表1，ERROR代表0。之后代码中出现就不再赘述。

4.2 插入操作

刚才我们也谈到了，这里的时间复杂度为O(1)。我们现在来考虑，如果我们要实现ListInsert（^L,i,e），即在线性表L中的第i个位置插入新元素e，在插入数据时的实现过程如图所示。

插入算法的思路：

1. 如果插入的位置不合适，抛出异常；

2. 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量。

3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置。

4. 将要插入元素填入位置i处。

5. 表长加1.

实现代码如下：

/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， *//* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */Status ListInsert(SqList *L,int i,ElemType e){int k;if (L->length==MAXSIZE) /* 顺序线性表已经满 */return ERROR;if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */return ERROR;if (i<=L->length) /* 若插入数据位置不在表尾 */{for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */L->data[k+1]=L->data[k];}L->data[i-1]=e;/* 将新元素插入 */L->length++;return OK;}

4.3 删除操作

删除算法的思路：

1. 如果删除位置不合理，抛出异常。

2. 取出删除元素。

3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置。

4. 表长减1.

实现代码如下：

/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) *//* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */Status ListDelete(SqList *L,int i,ElemType *e) {int k;if (L->length==0)/* 线性表为空 */return ERROR;if (i<1 || i>L->length) /* 删除位置不正确 */return ERROR;*e=L->data[i-1];if (i<L->length)/* 如果删除不是最后位置 */{for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */L->data[k-1]=L->data[k];}L->length--;return OK;}

我们来分析一下，插入和删除的时间复杂度。

先来看最好的情况，如果元素要插入到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)，因为不需要移动元素的。

最坏的情况呢，如果元素要插入到第一个位置或者删除第一个元素，那就意味着要移动所有的元素向后或者向前。所以这个时间复杂度为O(n)。

至于平均的情况，由于元素插入到第i个位置，或者删除第i个元素，需要移动n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就是说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素移动次数相等，为（n-1）/2。

我们前面讨论过时间复杂度的推导（具体请看文末链接算法概论），可以得出，平均时间复杂度还是O(n)。

这说明了线性表的顺序存取结构，存取、读取数据时，不管是哪个位置，时间复杂度都是O(1)，而插入和删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多的是读取数据的应用。

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

5. 线性表的链式存储结构

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

这里提供一个链式存储结构的思路，因为没法正确的留出足够的空间在相邻元素之间，所以干脆所有的元素都不要考虑相邻位置了，哪里有空位就停哪里，而只是让每个元素知道它下一个元素的位置在哪里，这样我们就可以在第一个元素时，就知道第二个元素的位置(内存地址)，以此类推。这样所有的元素我们就都可以通过遍历而找到。

5.2 线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置，如图所示。

以前在顺序结构中，每个数据元素只需要存储数据元素信息就可以了。现在链式结构中，除了要存储数据元素信息外，还要存储它的后续元素的存储地址。

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

n个节点（ai的存储映像）链结成一个链表，即为线性表（a1,a2,…,an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起，如图所示。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行链。

我们规定，线性表的最后一个结点指针为“空”（通常用NULL或“^”符号表示）。

有时，我们为了更加方便地对链表进行操作，会在链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如图。

5.3 头指针与头节点的异同

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

若线线性表为空表，则头结点的指针域为“空”，如图所示。

这里我们大概地用图表达了内存中单链表的存储状态。我们真正关心的：它是在内存中的实际位置吗？不是的，这只是它所表示的线性表中的数据元素及数据元素之间的逻辑关系。所以我们改用更方便的存储示意图来表示单链表，如图所示。

若带有头结点的单链表，则如图所示。

空链表如图所示。

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

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

从这个结构定义中，我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针，即指向ai+1的指针。也就是说，如果p->data=ai，那么p->next->data=ai+1，如图所示。

6. 单链表的读取

在线性表的存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪没有办法一开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作GetElem，在算法上，相对要麻烦一些。

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

1. 声明一个指针p指向链表第一个结点，初始化j从1开始；

2. 当j<I时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；

3. 若到链表末尾p为空，则说明第i个结点不存在；

4. 否则查找成功，返回结点p的数据。

实现代码算法如下：

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) *//* 操作结果：用e返回L中第i个数据元素的值 */Status GetElem(LinkList L,int i,ElemType *e){int j;LinkList p;/* 声明一结点p */p = L->next;/* 让p指向链表L的第一个结点 */j = 1;/* j为计数器 */while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */{p = p->next; /* 让p指向下一个结点 */++j;}if ( !p || j>i ) return ERROR; /* 第i个元素不存在 */*e = p->data; /* 取第i个元素的数据 */return OK;}

说白了，就是从头开始找，知道第i个结点为止。由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需要遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度时O(n)。

由于单链表的结构没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是**“工作指针后移”** ，这其实也是很多算法的常用技术。

7. 单链表的插入与删除

7.1 单链表的插入

先来看单链表的插入。假设存储元素e的结点为s，要实现结点p、p->next和s之间逻辑关系的变化，只需将结点p和p->next之间即可，如图所示。

只需要让s->next和p->next的指针做一点改变即可。

s->next = p->next;p->next = s;

解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点，如图所示。

考虑一下这两句顺序能不能交换？

如果先让p->next=s;再s->next=p->next;会怎么杨？因为第一句会使得将p->next给覆盖成s的地址来。那么s-next=p->next，其实就等于s->next=s,这样真正的拥有ai+1数据元素的结点就没了上级。这样的插入操作就是失败的，造成了临场掉链子的尴尬局面。所以这两句是无论如何不能反的。

插入结点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. 返回成功。

实现代码算法如下：

/* 初始条件：链式线性表L已存在,1≤i≤ListLength(L)， *//* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */Status ListInsert(LinkList *L,int i,ElemType e){int j;LinkList p,s;p = *L; j = 1;while (p && j < i)/* 寻找第i个结点 */{p = p->next;++j;} if (!p || j > i) return ERROR; /* 第i个元素不存在 */s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */s->data = e; s->next = p->next;/* 将p的后继结点赋值给s的后继 */p->next = s;/* 将s赋值给p的后继 */return OK;}

在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放数据e的s结点。

7.2 单链表的删除

现在我们再来看单链表的删除。设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可，如图所示。

我们所要做的，实际上就是一步，p->next=p->next->next，用q来取代p->next，即是

q=p->next;p->next=q->next;

解读这两句代码，也就是说把p的后继结点改成p的后继的后继结点。

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

实现代码算法如下：

/* 初始条件：链式线性表L已存在，1≤i≤ListLength(L) *//* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */Status ListDelete(LinkList *L,int i,ElemType *e) {int j;LinkList p,q;p = *L;j = 1;while (p->next && j < i)/* 遍历寻找第i个元素 */{p = p->next;++j;}if (!(p->next) || j > i) return ERROR; /* 第i个元素不存在 */q = p->next;p->next = q->next;/* 将q的后继赋值给p的后继 */*e = q->data;/* 将q结点中的数据给e */free(q);/* 让系统回收此结点，释放内存 */return OK;}

这段算法代码里，我们又用到了另一个c语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。

分析一下我们刚才说到的单链表插入和删除算法，我们发现，它们其实都是由两部分组成：第一部分就是遍历查找第i个结点；第二部分就是插入和删除结点。

从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个结点的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个结点，对于顺序存储结构意味着，每一次插入都需要移动n-i个结点，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是O(1)。显然，对于插入和删除数据越频繁的操作，单链表的效率优势就越明显。

8. 单链表的整表创建

回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

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

1. 声明一指针p和计数器变量i；

2. 初始化一空链表L；

3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；

4. 循环：

生成一个新结点赋值给p；

随机生成一数字赋值给p的数据域p->data；

将p插入到头结点与前一新结点之间。

实现代码算法如下：

/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */void CreateListHead(LinkList *L, int n) {LinkList p;int i;srand(time(0));/* 初始化随机数种子 */*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL; /* 先建立一个带头结点的单链表 */for (i=0; i<n; i++) {p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */p->data = rand()%100+1; /* 随机生成100以内的数字 */p->next = (*L)->next; (*L)->next = p;/* 插入到表头 */}}

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。可以把这种算法简称为头插法，如图所示。

可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队的正常思维，所谓先来后到。我们把每次新结点都插在终端结点的后面，这种方法称为尾插法。

实现代码算法如下：

/* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */void CreateListTail(LinkList *L, int n) {LinkList p,r;int i;srand(time(0)); /* 初始化随机数种子 */*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */r=*L; /* r为指向尾部的结点 */for (i=0; i<n; i++) {p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */p->data = rand()%100+1; /* 随机生成100以内的数字 */r->next=p; /* 将表尾终端结点的指针指向新结点 */r = p; /* 将当前的新结点定义为表尾终端结点 */}r->next = NULL; /* 表示当前链表结束 */}

注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。

这里需要解释一下，r->next=p；的意思，其实就是将刚才的表尾终端结点r的指针指向新结点p，如果所示，当中1位置的连线就是表示这个意思。

r->next=p；这一句应该不难理解，但是后一句r=p；是什么意思？如图所示。

它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai，所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。

循环结束后，那么应该让这个节点的指针域尾空，因此有了“r->next=NULL；”，以便以后遍历时可以确认其时尾部。

9. 单链表的整表删除

当我们不打算使用这个单链表时，我们需要把他销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

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

1. 声明一节点p和q；

2. 将第一个结点赋值给p；

3. 循环：

将下一节点赋值给q；

释放p；

将q赋值给p。

实现代码算法如下：

/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */Status ClearList(LinkList *L){LinkList p,q;p=(*L)->next; /* p指向第一个结点 */while(p)/* 没到表尾 */{q=p->next;free(p);p=q;}(*L)->next=NULL; /* 头结点指针域为空 */return OK;}

这段算法代码里，常见的错误就是有人会觉得q变量没有存在的变量。在循环体内直接写free§; p=p->next;即可。可这样会带来什么问题？

要知道p是一个结点，它除了有数据域，还有指针域。在做free§;时，其实是在对他整个结点进行删除和内存释放的工作。如果不保证能正确的访问到要删除结点的后继结点，那么删除操作之后整个链表的删除工作岂不是因为找不到后继结点而出错？

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

简单地对单链表结构和顺序存储结构做对比：

通过上面的对比，我们可以得出一些经验性的结论：

1. 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑采用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能随时增加或者删除，此时再采用顺序存储结构就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。

2. 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样就可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天，这种用顺序存储结构效率会高很多。

总之，线性表的顺序存储结构和单链表结构各有其优缺点，不能简单的说哪个好，哪个不好，需要根据实际情况，来综合平衡采用哪种数据结构更能满足和达到需求和性能。

11. 静态链表

C语言具有指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。后来的面向对象语言，如Java、C#等，虽不使用指针，但因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。但对于一些语言，如Basic、Fortran等早期的编程高级语言，由于没有指针，链表结构按照我们的讲法，它就没法实现了。

有人就想出来用数组来代替指针，来描述单链表。

首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们把cur叫做游标。

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

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。

/* 线性表的静态链表存储结构 */#define MAXSIZE 1000 /* 存储空间初始分配量 */typedef struct {ElemType data;int cur; /* 游标(Cursor) ，为0时表示无指向 */} Component,StaticLinkList[MAXSIZE];

另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为02。如图所示。

此时的图示相当于初始化的数组状态，见以下代码：

/* 将一维数组space中各分量链成一个备用链表 *//* space[0].cur为头指针，"0"表示空指针 */Status InitList(StaticLinkList space) {int i;for (i=0; i<MAXSIZE-1; i++) space[i].cur = i+1;space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */return OK;}

假设我们已经将数据存入静态链表，比如分别存放着“甲”、“乙”、“丁”、“戊”、“己”、“庚”等数据，则它将处于如图所示这种状态。

此时“甲”这里就存有下一元素“乙”的游标2，“乙”则存有下一元素“丁”的游标3。而“庚”是最后一个有值元素，所以它的cur设置为0。而最后一个元素的cur则因“甲”是第一个有值元素而存有它的下标为1。而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7。

11.1 静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

我们前面说过，在动态链表中，结点的申请和释放分别借用malloc（）和free（）两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现两个函数，才可以做插入和删除操作。

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

/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */int Malloc_SSL(StaticLinkList space) {int i = space[0].cur; /* 当前数组第一个元素的cur存的值 *//* 就是要返回的第一个备用空闲的下标 */if (space[0]. cur) space[0]. cur = space[i].cur; /* 由于要拿出一个分量来使用了， *//* 所以我们就得把它的下一个 *//* 分量用来做备用 */return i;}

这段代码一方面它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标。从上面的图示例子来看，其实就是返回7。

那么既然下标7的分量准备要使用了，就得有接替者，所以就把分量7的cur值赋值给头元素，也就是把8给space[0].cur，之后就可以继续分配新的空闲分量，实现类似malloc（）函数的作用。

现在我们如果需要在“乙”和“丁”之间，插入一个值为“丙”的元素，按照以前顺序存储结构的做法，应该要把“丁”、“戊”、“己”、“庚”这些元素都往后移一位。但目前不需要，因为我们有了新的手段。

新元素“丙”想插队，可以让它在队伍最后一排第7个游标位置待着，然后找到“乙”，将它的游标cur由3改为7。此时再回到“丙”那里，将它的游标cur改为3。就这样，在绝大多数人都不知道的情况下，整个排队的次序发生了改变，如图所示。

实现代码如下。

/* 在L中第i个元素之前插入新的数据元素e */Status ListInsert(StaticLinkList L, int i, ElemType e) {int j, k, l; k = MAXSIZE - 1; /* 注意k首先是最后一个元素的下标 */if (i < 1 || i > ListLength(L) + 1) return ERROR; j = Malloc_SSL(L); /* 获得空闲分量的下标 */if (j) {L[j].data = e; /* 将数据赋值给此分量的data */for(l = 1; l <= i - 1; l++) /* 找到第i个元素之前的位置 */k = L[k].cur; L[j].cur = L[k].cur; /* 把第i个元素之前的cur赋值给新元素的cur */L[k].cur = j; /* 把新元素的下标赋值给第i个元素之前元素的ur */return OK; } return ERROR; }

当我们执行插入语句时，我们的目的是要在“乙”和“丁”之间插入“丙”。调用代码时，输入i值为3。

第4行让k=MAX_SIZE-1=999。

第7行，j=Malloc_SSL（L）=7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8。

第11～12行，for循环l由1到2，执行2次。代码k=L[k].cur;使得k=999，得到k=L[999].cur=1，再得到k=L[1].cur=2。

第13行，L[j].cur = L[k].cur；因j=7，而k=2得到L[7].cur=L[2].cur=3。这就时刚才提到的让“丙”把它的cur改为3的意思。

第14行，L[k].cur=j；意思就是L[2].cur=7。也就是让“乙”把它的cur改为指向“丙”的下标7。

就这样，我们实现了再数组中，不移动元素，缺插入了数据的操作。

11.2 静态链表的删除操作

如果此时要删除“甲”，那么就意味着第一位空出来了，那么自然“乙”就成了第一位。

和前面一样，删除元素时，原来是需要释放结点的函数free（）。现在我们也得自己实现它：

有了刚才的基础，这段代码就很容易理解了。前面代码都一样，for循环因为i=1而不操作，j=L[999].cur=1，L[k].cur=L[j].cur 也就是L[999].cur=L[1].cur=2。这其实就是告诉计算机现在“甲”已经离开了，“乙”才是第一个元素。Free_SSL（L，j）;是什么意思呢？来看代码：

/* 将下标为k的空闲结点回收到备用链表 */void Free_SSL(StaticLinkList space, int k) {space[k].cur = space[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */space[0].cur = k;/* 把要删除的分量下标赋值给第一个元素的cur */}

意思就是“甲”现在要走，这个位置就空出来了，也就是，未来如果有新人来，最优先考虑这里，所以原来的第一个空位分量，即下标是8的分量，它降级了，把8给“甲”所在下标为1的分量的cur，也就是space[1].cur=space[0].cur=8，而space[0].cur=k=1 其实就是让这个删除的位置成为第一个优先空位，把它存入第一个元素的cur中，如图所示。

当然，静态链表也有相应的其他操作的相关实现，比如我们代码中的ListLength就是一个，来看代码。

/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */int ListLength(StaticLinkList L){int j=0;int i=L[MAXSIZE-1].cur;while(i){i=L[i].cur;j++;}return j;}

另外一些操作和线性表的基本操作相同，实现上也不复杂。

11.3 静态链表优缺点

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

12. 循环链表

对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就像我们前面讲到的，不能回到从前。

比如，你是一个业务员，家在上海。需要经常出差，行程就是上海到北京一路上的城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留后，再乘飞机返回上海，此后，每隔一段时间，你基本还要按照这样的行程开展业务，如图所示。

有一次，你先到南京开会，接下来要对以上的城市走一遍，此时有人对你说，不行，你得从上海开始，因为上海时第一站。其实直接回上海没有必要，你可以从南京开始，下一站蚌埠，直到北京，之后再考虑走完上海及苏南的几个城市。显然这表示你是从当中一结点开始遍历整个链表，这都是原来的单链表结构解决不了的问题。

事实上，把北京和上海之间连接起来，形成一个环就解决了前面所面临的困难。这就是我们现在要讲的循环链表。

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

从刚才的例子，可以总结出，循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表全部的结点。

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如图所示。

对于非空的循环链表就如图所示。

其实循环链表和单链表主要差异就在于循环的条件判断上，原来是判断p->next是否为空，现在是p->next不等于头结点，则循环未结束。

在单链表中，我们有了头结点时，我们可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描一遍。

有没有可能用O(1)的时间由链表指针访问到最后一个结点呢？当然可以。

不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了，如图所示。

从上图中可以看到，终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点，其实就是rear->next->next，其时间复杂也为O(1)。

举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别时rearA和rearB，如图所示。

要想把它们合并，只需要如下操作即可，如图所示。

p=rearA->next; /* 保存A表的头结点，即① */rearA->next=rearB->next->next;/* 将本是指向B表的第一个结点（不是头结点）*//* 赋值给reaA->next，即② */q=rearB->next;rearB->next=p; /* 将原A表的头结点赋值给rearB->next，即③ */free（q）; /* 释放q */

13. 双向链表

继续我们刚才的例子，你平时都是从上海一路停留到北京的，可是这一次，你得先到北京开会，谁叫北京是首都呢，会就是多。开完会后，你需要例行公事，走访各个城市，此时你怎么办？

有人又出主意了，你可以先飞回上海，一路再乘火车走遍这几个城市，到了北京后，你再飞回上海。

其实哪用的着这么麻烦，一路从北京坐火车或汽车回去不就可以了。

我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗？当然可以，只不过需要加点东西而已。

我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头开始遍历查找。

为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

/*线性表的双向链表存储结构*/typedef struct DulNode{ElemType data;struct DuLNode *prior; /*直接前驱指针*/struct DuLNode *next;/*直接后继指针*/} DulNode, *DuLinkList;

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

双向链表的循环带头结点的空链表如图所示。

非空的循环的带头结点的双向链表如图所示。

由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是谁？当然还是它自己。它的前驱的后继自然也是它自己，即

p->next->prior = p = p->prior->next

这就如同上海的下一站是苏州，那么上海的下一站的前一站是哪里，自然就是上海。

双向链表是单链表中扩展出来的结构，所以它的很多操作时和单链表相同的，比如求长度的ListLength，查找元素的GetElem，获取元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

双向链表既然时比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。

插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。

我们现在假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间需要下面几步，如图所示。

s - >prior = p; /*把p赋值给s的前驱，如图中①*/s -> next = p -> next;/*把p->next赋值给s的后继，如图中②*/p -> next -> prior = s;/*把s赋值给p->next的前驱，如图中③*/p -> next = s;

关键在于它们的顺序，由于第2步和第3步都用到了p->next。如果第4步先执行，则会使得p->next提前变成了s，使得插入的工作完不成。所以我们不妨把上面这张图在理解的基础上记忆，顺序是先搞定s的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继。

如果插入操作理解了，那么删除操作，就比较简单了。

若要删除结点p，只需要下面两个步骤，如图所示。

p->prior->next=p->next; /*把p->next赋值给p->prior的后继，如图中①*/p->next->prior=p->prior;/*把p->prior赋值给p->next的前驱，如图中②*/free（p）;/*释放结点*/

好了，简单总结一下，双向链表相对于单链表来说，要更复杂一些，毕竟它多了prior指针，对于插入和删除操作时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上上要占用略多一些的。不过，由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间换时间。