顺序表和链表

1，线性表的定义

首先，数据结构中的顺序表和链表都属于线性表。何为线性表？线性表可以描述为：具有相同数据类型的n个数据元素的有限序列。

形象理解线性表的要素：

• 幼儿园小朋友放学，需要在校内站成一队，等待家长来接。这是一个有限的序列。

• 总共有几个小朋友，称之为线性表的长度。特别地，当队伍长度为0时，线性表为空表；

• 孩子在第几位，称之为位序。

• 除了队伍最前面的小朋友，其他每个小朋友前面都有一位同学，称之为直接前驱元素；除了队伍最后面的小朋友，其他每个小朋友后面都有一位同学，称之为直接后继元素。

• 玛卡巴卡同学去上厕所，拿自己的书包占了一个位置，此时该队伍就不再是线性表，因为书包和小朋友不是相同的数据类型。

• 每个小朋友都带着自己的书包、玩具、水杯…这些内容可称之为数据项，较复杂的线性表中，一个数据元素可以由若干个数据项构成。

2，说明

2.1，参数的引用符号—“&”

线性表的主要基本操作：

• InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
• DestoryList(&L)：销毁线性表，并释放线性表L所占用的内存空间。
• ListInsert(&L,i,e)：在表L中的第i个位置上插入指定元素e。
• ListDelete(&L,i,&e)：删除表L中第i个位置的元素，并用e返回删除元素的值。
• LocateElem(L,e)：按值查找。在表L中查找元素e。
• GetElem(L,i)：按位查找。获取表L中第i个位置的元素的值。
• …

上述部分基本操作需要传入参数的引用“&”，对参数的修改结果需要“带回来”的时候需要传入。

代码理解：

#include<stdio.h>
void test(int x){
	x=1024;
	printf("test函数内部 x=%d\n",x);
}
int main(){
	int x=1;
	printf("调用test函数前 x=%d\n",x);
	test(x);
	printf("调用test函数后 x=%d\n",x);
}

运行结果：

注意：上述程序，没有在test(x)内部没有使用参数引用符“&”，因此test函数内部的x和main函数内部声明的x不同，二者各占一份内存空间。

加上引用“&”后，查看运行效果：

#include<stdio.h>
void test(int &x){
	x=1024;
	printf("test函数内部 x=%d\n",x);
}
int main(){
	int x=1;
	printf("调用test函数前 x=%d\n",x);
	test(x);
	printf("调用test函数后 x=%d\n",x);
}

此时加上了参数的引用符“&”，test函数内操作的x就是main()中的x，对x的修改就带了回来。

2.2，malloc()函数和free()函数

• malloc()：用于申请内存空间，返回一个指向分配好的一整片存储空间起始地址的指针；*

• 注意malloc()返回的指针类型需要强制转换为你定义的数据元素指针类型，这个后续会提到。

• free()：释放内存空间。

malloc()和free()都包含在stdlib.h头文件内，因此使用到malloc()或free()的程序需要加上#include <stdlib.h>

2.3，typedef关键字

C语言中使用typedef关键字进行数据类型的重命名。
typedef <数据类型> <别名>

typedef int ElemType; —将int类型起别名为ElemType。

如此一来，int i = 0 就等价于ElemType i = 0；

3，顺序表

顺序表，即使用顺序存储方式实现的线性表。把逻辑上相邻的元素存储在物理上也相邻的存储单元中，其中重要的三个属性包括：

• 存储空间的起始位置。
• 最大容量
• 当前长度

顺序表使用数组存储元素。顺序表的实现方式有静态分配和动态分配。，静态分配在定义时就确定了数组的大小，而动态分配可以在程序运行时根据需要动态地分配内存空间。下面一一展开。

3.1，静态分配和动态分配

静态分配中，数组的大小和空间都是事先固定好的。

顺序表静态分配代码描述：

#include <stdio.h>
#define MAXSIZE 20    //定义线性表的最大长度
typedef int ElemType;
typedef struct{
	ElemType data[MAXSIZE];
	int length;     //顺序表的当前长度
}SqList;

void InitList(SqList &L){
	L.length=0;   //顺序表初始长度为0
}

int main(){
	SqList L;
	InitList(L);  //初始化顺序表
	return 0;
}

静态分配中数组的大小和空间都是事先固定，因此空间占满时插入元素会导致溢出，进而导致程序崩溃，存在弊端。而动态分配可以完美解决这一问题。下面详细学习动态分配。

动态分配：程序运行时根据需要动态地分配内存空间

顺序表动态分配代码描述：

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10  //默认的最大长度
typedef struct {
	int *data;       //指示动态分配数组的指针
	int maxsize;     //顺序表的最大容量
	int length;      //顺序表当前长度
}SeqList;

void InitList(SeqList &L){
	//使用malloc函数申请一片连续的存储空间
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.maxsize=InitSize;
}
 
void IncreaseSize(SeqList &L, int len){   //len表示需要增加的长度
	int *p=L.data;  //p指针指向原先未扩容数组的起始地址
	L.data=(int *)malloc((L.maxsize+len)*sizeof(int));  //分配新空间
	for(int i=0; i<L.length; i++){
		L.data[i]=p[i];  //将原始数据复制到新区域
	}
	L.maxsize=L.maxsize+len;  //顺序表最大长度增加len
	free(p);  //释放掉原来的内存空间
}

int main(){
	SeqList L;
	InitList(L);
	/*
	省略操作...：往顺序表中插入一些元素
	*/
	printf("顺序表当前最大容量为%d\n",L.maxsize);  //运行，输出为10
	IncreaseSize(L,5);  //扩容
	printf("顺序表当前最大容量为%d\n",L.maxsize);  //运行，输出为15，扩容成功
	return 0;
}

3.2，顺序表的插入

ListInsert(&L,i,e)：插入操作。在表L的第i个位置上插入指定元素e。

根据顺序表的性质，元素e插入之后第i个位置元素和第i个位置元素后面的元素都需要依次后移。这就好比食堂里一群人排队买饭，如果前面队伍里有人插队，后面的排队的每一个人就相当于向后移了一个位置。

因此顺序表插入算法的思想可以概括为以下几点：

• 插入位置不合理时，需要有报错信息；
• 如果顺序表长度大于等于数组的最大长度，需要用报错信息；
• 从最后一个元素开始向前遍历到第i个位置，分别将它们向后移动一个位置（第i个位置之后的元素和第i个元素元素都要向后移动）；
• 将要插入的元素填入位置i处；
• 表长加1。

顺序表插入的代码实现如下（此处使用静态分配方式实现，动态分配方式雷同）：

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
typedef int ElemType;
typedef struct {
	ElemType data[MaxSize]; //使用静态数组存放数据元素
	int length;  //顺序表的当前长度
}SqList;  //顺序表类型定义

void InitList(SqList &L){
	L.length=0;   //顺序表初始长度为0
}

bool ListInsert(SqList &L,int i,int e){
	if(i<1||i>L.length+1){ //校验i值合法性
		return false;
	}
	if(L.length>=MaxSize){ //顺序表已存满，无法插入元素
		return false;
	}

	for(int j=L.length;j>=i;j--){         //将第i个元素及第i个元素后面的元素向后移动
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;  //在顺序表的第i个位置（即下表为i-1的位置）上放入元素e
	L.length++; //插入一个元素，顺序表长度增加1
	return true;
}

int main(){
	SqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	ListInsert(L,4,4);
	ListInsert(L,5,5);
	ListInsert(L,3,520);
	for(int i=0;i<L.length;i++){
		printf("data[%d]=%d\n",i,L.data[i]);  //将顺序表打印输出
	}
	return 0;
}

运行结果为：

对顺序表插入的时间复杂度进行分析，第i个位置元素及其后面的元素都要移动位置（表内n个元素，第i个位置插入新元素，则需要移动元素n-i+1次）。很显然，问题规模和表长有关，时间主要花费在元素的移动上面。因此顺序表插入元素操作的时间复杂度为O(n)。

3.3，顺序表的删除

ListDelete(&L,i,&e)：删除操作。删除表L的第i个位置上的元素，并用e返回删除元素的值。

根据顺序表的性质，删除表L的第i个位置上的元素之后，第i个位置元素后面的元素都需要依次前移。如插队的人受不了后面排队人群的谴责，从队伍中离开，后面排队的人群向前移动一个位置。

因此顺序表删除算法的思想可以概括为以下几点：

• 如果删除的位置不合理，需要有报错信息；
• 取出删除元素；
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置；
• 表长减1；

顺序表删除操作核心代码：

bool ListDelete(SqList &L,int i,int &e){
	if(i<1||i>L.length+1){
		return false;
	}
	e=L.data[i-1];
	for(int j=i;j<L.length;j++){
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return true;
}

同样地，对顺序表插入的时间复杂度进行分析，第i个位置后面的元素都要移动位置（表中有n个元素，删除第i个位置的元素之后，需要移动n-i个元素）。很显然，问题规模也和表长有关，时间主要花费在元素的移动上面。因此顺序表删除元素操作的时间复杂度为O(n)。

3.4，顺序表的查找

顺序表的查找分为按位查找和按值查找。

3.4.1，按位查找

GetElem(L,i)：按位查找操作。获取表L中第i个位置元素的值。

顺序表按位查找代码实现（直接返回第i个位置元素的值）：

ElemType GetElem(SqList L,int i){
	return L.data[i-1];    //第i个位置元素的数组下表为（i-1）
}

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，因此顺序表按位查找时间复杂度为O(1)。这就是顺序表的 “随机存取” 特性。

3.4.2，按值查找

LocateElem(L,e)：按值查找操作。获取表L中值为e的元素。

顺序表按值查找代码实现：

//在顺序表L中查找第一个元素值为e的元素，并返回其位序
int LocateElem(SqList L,ElemType e){
	for(int i=0;i<L.length-1;i++){
		if(L.data[i]==e){
			return i+1;  //返回其位序
		}
	}
	return 0;  //退出循环，说明查找失败
}

显然，顺序表按值查找的时间复杂度为O(n)，主要时间花费在了元素的遍历上。

4，链表

由于顺序表中的插入、删除元素操作，需要移动大量元素。因此对于需要频繁插入删除的应用场景，运行效率会很低。因此引入链式存储。

链表，使用一组任意的存储单元存储线性表的数据元素。这些存储单元可以连续，也可以不连续。也就是说，链表不要求逻辑上相邻的元素在物理上也相邻。

形象理解

上世纪的银行，办理业务时需要客户排成一队，依次办理。随着前面客户办理结束，队伍也会向前移动。同样的有人插队时，插入位置之后的队伍相当于向后移动，这就是顺序表。显然这不太合理，大家都站在一起，耗时耗精力。这种排队方式可以理解为顺序表。

于是后来慢慢优化成了如今的样子：客户来银行办理业务时，先去取号，取完之后不必排队等候，可以随便找个位置坐下休息，等到广播叫到自己的号时前去办理业务，实际上这就是链表的思想。

4.1，单链表的定义

单链表中，其每个结点除了要存储数据元素，还需要存储指向下一个结点的指针（相当于例子中银行客户取到的号）。

单链表的定义：

typedef struct LNode{     //定义单链表结点类型
	ElemType data;        //数据域。结点存放数据元素
	struct LNode *next;   //指针域。存放指向下一个结点的指针
}LNode,*LinkList;

//要表示一个单链表，只需要一个头指针，指向单链表的第一个结点
LNode *L;   //声明一个指向单链表第一个结点的指针（强调结点）
LinkList L; //声明一个指向单链表第一个结点的指针（强调单链表）

4.2，单链表的初始化

首先要理解何为头结点，何为头指针？

• 头结点是放在链表第一个元素结点之前的结点，其数据域一般无意义（也可以用来存放链表的长度）。
• 头结点是链表的非必需要素，但引入头结点后，写代码更方便。有头结点时，第一个元素结点前插入节点和删除第一结点操作就和其他结点统一起来了（后续提到），就可以实现一套逻辑搞定所有结点。
• 头指针是链表的必需要素，是指向第一个结点的指针。若单链表有头结点，则是指向头结点的指针。
• 头指针具有标志作用，所有常用头指针冠以链表的名字。

单链表初始化分两种情况：带头结点的单链表和不带头结点的单链表。下面分别进行实现：

①初始化不带头结点的单链表：

typedef int ElemType;    
typedef struct LNode{     //定义单链表结点类型
	ElemType data;        //数据域。结点存放数据元素
	struct LNode *next;   //指针域。存放指向下一个结点的指针
}LNode,*LinkList;

//初始化不带头结点的单链表
bool InitList(LinkList &L){
	L=NULL;       //空表，暂时还没有任何结点（防止脏数据）
	return true;
}

//不带头结点的单链表的判空操作
bool Empty(LinkList L){
	if(L==NULL){
		return true;
	}else{
		return false;
	}
}

②初始化带头结点的单链表：

//初始化带头结点单链表
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));  //给头结点分配空间
	if(L==NULL){
		return false;   //内存不足，分配失败
	}
	L->next=NULL;   //头结点之后暂时无其他结点
	return true;
}
//带头结点的单链表的判空操作
bool Empty(LinkList L){
	if(L->next==NULL){
		return true;
	}else{
		return false;
	}
}

不难看出，判空时，不带头结点的单链表直接根据头指针是否指向空，判断表是否为空。而带头结点的单链表则是通过判断头结点下一个位置是否为空。

4.3，单链表的插入

单链表的插入操作分为按位序插入、指定节点的后插、指定节点的前插。接下来对三种插入操作一一进行实现。

4.3.1，按位序插入

ListInsert(&L,i,e)：按位序插入操作，在链表L中的第i个结点位置插入元素e。（头结点可以看作是第0个结点）

单链表按位序插入具体实现思路如下：

• 声明一指针p指向链表的头结点，初始化 j（计数器变量，表示当前p指向第几个结点）从0开始；
• 当 j<i-1 时，让p指针向后移动，不断指向下一个结点，j累加1；
• 若到链表末尾p为空，则说明第i个结点不存在；
• 否则查找成功，在系统中生成一个空结点s；
• 将数据元素e赋值给 s->data;
• 单链表插入的标准语句：s->next=p->next; p->next=s;（先后顺序不可颠倒。要先过河才能拆桥，如果先拆桥就没办法过河）；
• 返回成功；

单链表按位序插入代码实现（带头结点）：

//初始化带头结点单链表
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL){
		return false;   //内存不足，分配失败
	}
	L->next=NULL;   //头结点之后暂时无其他结点
	return true;
}

//单链表按位序插入
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1){
		return false;
	}
	LNode *p;  //指针，用来指向当前扫描到的结点
	int j=0;   //计数器，用来表示当前p指向第几个结点，头结点是第0个结点
	p=L;        //指针指向头结点
	while(p!=NULL && j<i-1){    //循环找到第（i-1）个结点
		p=p->next;
		j++;
	}
	if(p=NULL){
		return false;    //说明第（i-1）个结点不存在
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));

	//将结点s连接在p之后
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;  //走到这里，表示插入成功
}

以上是带头结点的单链表的按位序插入操作。思考不带头结还能使用如上代码进行按位序插入吗？

答案是不能。

带头结点的单链表，进行按位序插入时，是先找到第（i-1）个结点，然后将新结点插入其后，如果要在第一个结点位置进行插入元素，就会先找到第0个结点（头结点）。但不带头结点的单链表没有第0个结点。走如上代码逻辑是行不通的，因此需要额外针对插入位置为1的情况进行特殊处理。

单链表按位序插入代码实现（不带头结点）：

//单链表按位序插入（不带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1){
		return false;
	}
	if(i==1){      //不带头结点的单链表需要针对第一个位置进行特殊处理
		LNode *s=(LNode *)malloc(sizeof(LNode));   //新结点
		s->data=e;
		s->next=L;
		L=s;   //头指针指向新结点
		return true;
	}

	//处理其余结点
	LNode *p;  //指针，用来指向当前扫描到的结点
	int j=1;   //指向第一个结点！！！
	p=L;        //指针指向第一个结点
	while(p!=NULL && j<i-1){    //循环找到第（i-1）个结点
		p=p->next;
		j++;
	}
	if(p=NULL){
		return false;    //i值不合法
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));

	//将结点s连接在p之后
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;  //走到这里，表示插入成功
}

4.3.2，指定结点后插

InsertNextNode(LNode *p, ElemType e)：指定结点的后插操作。将元素e插入到p结点之后

单链表指定结点的后插操作实现如下：

//单链表指定结点的后插操作
bool InsertNextNode(LNode *p, ElemType e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));   //新结点
	if(s==NULL){
		return false;    //内存分配失败的情况。比如内存空间不足
	}
	s->data=e;
	s->next=p->next;      //将结点s连接到p之后
	p->next=s;
	return true;
}

我们可以发现按位序插入操作内，也包含了指定节点的后插操作的逻辑（对第i-1个结点进行后插）。因此可以使用封装好的代码对按位序插入操作的代码进行简化，如下为简化后的代码：

//单链表按位序插入（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1){
		return false;
	}
	LNode *p;  //指针，用来指向当前扫描到的结点
	int j=0;   //计数器，用来表示当前p指向第几个结点，头结点是第0个结点
	p=L;        //指针指向头结点
	while(p!=NULL && j<i-1){    //循环找到第（i-1）个结点
		p=p->next;
		j++;
	}
	return InsertNextNode(p,e);
}

4.3.3，指定结点前插

InsertPriorNode(LNode *p, ElemType e)：指定结点的前插操作。在p结点之前插入元素e。

对于单链表，但每个结点都是向后指，前一个元素是不可知的，除非从链表头部开始遍历。那如何对指定的结点进行前插，难不成要从头指针开始遍历整个链表，找到指定结点的前驱元素吗？

对指定p结点要想把元素e插入到他的前面，我们可以通过节点不动，让数据跑路的骚操作巧妙完成。具体思路如下：

• 先对p结点进行后插操作，将新结点s插入到p结点后；
• 将结点p中的元素值复制到s中；
• 再将p中的元素值使用e覆盖。

单链表指定结点单独前插操作代码实现如下：

//单链表前插操作
bool InsertPriorNode(LNode *p, LNode *s){
	if(p==NULL || s==NULL){
		return false;
	}
	s->next=p->next;
	p->next=s;           //将s连接到p结点之后

	ElemType temp=p->data;    //交换数据域部分
	p->data=s->data;
	s->data=temp;
	return true;
}

4.4，单链表的删除

单链表的删除操作分为按位序删除和指定结点删除。接下来一一进行实现。

4.4.1，按位序删除

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

实现时可以先找到第（i-1）个结点，将其next指针指向第（i+1）个结点，并释放第i个结点。

单链表按位序删除操作（带头结点）具体实现思路如下：

• 声明一指针p指向链表头结点，初始化j从０开始；
• 当 j<i-1 时，遍历链表，让ｐ指针向后移动，不断指向下一个结点，ｊ进行累加；
• 若到链表末尾ｐ为空，则说明第（i-1）个结点不存在；
• 若第(ｉ-1)个节点存在，声明一结点q指向被删除结点（q=p->next）；
• 将q结点从单链表中断开：p->next=q->next；
• 将q结点中的数据赋值给e，作为返回；
• 释放结点q；
• 返回成功。

单链表按位序删除操作（带头结点）具体代码实现如下：

//单链表按位序删除（带头结点）
bool ListDelete(LinkList &L, int i, ElemType &e){
	if(i<1){
		return false;
	}
	LNode *p;  //指针指向当前扫描到的结点
	int j=0;   //计数器
	p=L;    //指向头结点

	while(p!=NULL && j<i-1){     //循环找到第i-1个结点
		p=p->next;
		j++;
	}

	if(p==NULL){      //i值不合法
		return false;
	}

	LNode *q;
	q=p->next;
	p->next=q->next;
	free(q);   
	return true;
}

4.4.2，指定结点的删除

DeleteNode(LNode *p)：删除指定结点p。

由于p结点之前的结点不好找，可以通过指定结点前插操作中的节点不动，让数据跑路的思想：把结点p->next的数据域部分赋值给p，然后将p->next删除。

• 声明一结点q指向p的下一个结点（即p->next）;
• q结点的数据域部分赋值给p结点的数据域部分；
• 将q结点从单链表中断开；
• 释放q结点。

单链表指定结点删除操作（带头结点）具体代码实现如下：

//指定结点的删除操作（带头结点）
bool DeleteNode(LNode *p){
	if(p==NULL){
		return false;
	}

	LNode *q=p->next;     //令q指向p的后继结点
	p->data=p->next->data;       //更新p结点数据域为后继结点数据域
	p->next=q->next;       //将后继结点从链表内断开
	free(q);        //释放后继结点的存储空间
	return true;
}

但上述代码存在一个问题：如果要删掉的结点p是最后一个结点，p->next就是NULL，如此一来p->next->data就会出现空指针错误。那就只能针对表尾元素进行特殊处理：通过从表头开始遍历的方法，找到p结点的前驱元素，然后进行删除。代码完善之后如下：

//指定结点的删除操作
bool DeleteNode(LinkList &L, LNode *p){
	if(p==NULL){
		return false;
	}

	if(p->next==NULL){       //p结点为单链表最后一个结点时
		LNode *s=L;     //s指向表头
		while(s->next!=p){   //从表头开始循环找到p结点的前驱结点
			s=s->next;
		}
		s->next=NULL;  //p结点的前驱结点指向NULL
		free(p);
		return true;
	}else{        //p结点不是最后单链表一个结点时
		LNode *q=p->next;     //令q指向p的后继结点
		p->data=p->next->data;       //更新p结点数据域为后继结点数据域
		p->next=q->next;       //将后继结点从链表内断开
		free(q);        //释放后继结点的存储空间
		return true;
	}
}

上述代码。如果删除的结点不是最后一个结点，时间复杂度为O(1)；如果删除的结点是最后一个结点，时间复杂度为O(n)，时间主要花费在从表头开始遍历寻找p结点前驱上。

4.5，单链表的查找

和顺序表一样，单链表的查找同样分为按位查找和按值查找。

4.5.1，单链表按位查找

GetElem(L,i)：按位查找操作。获取表L中第i个位元素的值；

实际上前面的单链表按位序插入和按位序删除操作中已经包含了单链表的按位查找。按位序插入和按位序删除都需要先找到第（i-1）个结点。此即为按位查找第（i-1）个元素的操作。

单链表按位查找具体实现代码实现如下：

//单链表按位查找，返回第i个元素（带头结点）
LNode *GetElem(LinkList L,int i){
	if(i<0){    //i值不合法
		return NULL;
	}
	LNode *p;   //指针p指向当前扫描到的结点
	int j=0;    //计数器
	p=L;        //指向头结点
	while(p!=NULL && j<i){   //循环找到第i个结点
		p=p->next;
		j++;
	}
	return p;
}

单链表按位序插入操作平均时间复杂度为O(n)，主要花费在循环找第i个结点上面。

4.5.1，单链表按值查找

LocateElem(L,e)：按值查找操作。获取表L中值为e的元素。

单链表按值查找。从表头开始依次查找数据域为e的结点，代码实现如下：

//单链表按值查找，找到数据域为e的结点
LNode *LocateElem(LinkList L,ElemType e){
	LNode *p=L->next;    
	//从第一个结点开始查找数据域为e的结点
	while(p!=NULL && p->data!=e){
		p=p->next;
	}
	return p;         //找到后返回该结点的指针，否则返回NULL
}

4.6，单链表的建立

拿到很多个数据元素，如何把它们存到一个单链表里呢？

创建单链表的过程是一个动态生成链表的过程，先初始化一个单链表，然后每次取一个数据元素，插入到表头或者表尾。因此单链表的建立有两种分别是头插法和尾插法。

4.6.1，尾插法建立单链表

尾插法建立单链表思路：

• 声明一个指针r 始终指向表尾元素；
• 对表尾元素进行后插操作；
• 插入完成后让指针r继续指向新的表尾结点；

尾插法建立单链表代码实现如下：

//尾插法建立单链表（带头结点）
LinkList List_TailInsert(LinkList &L){
	LNode *r;
	L=(LinkList)malloc(sizeof(LNode));    //初始化空的单链表（带头结点）
	LNode *r=L;
	int x;      //用来接收键盘输入的值
	scanf("%d",&x);
	while(x!=9999){       //输入9999表示结束
		//在r结点之后插入结点x（指定结点的后插操作）
		LNode *s=(LNode *)malloc(sizeof(LNode));  
		s->data=x;
		r->next=s;
		r=s;  //r指针继续指向新的表尾结点
		scanf("%d",&x);      //继续输入下一个值
	}
	r->next=NULL;
	return L;
}

如上代码实现： 手动输入值，插入相应结点元素到单链表表尾，插入完成后输入下一个值，如果输入的值为9999，则程序运行结束。

4.6.2，头插法建立单链表

尾插法建立单链表是通过对表尾结点进行后插操作，不难想到头插法建立单链表就是对头结点进行后插操作。

头插法建立单链表代码实现如下：

//头插法建立单链表（带头结点）
LinkList List_HeadInsert(LinkList &L){
	//①初始化一个空的单链表
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	//②输入结点的值
	int x;
	scanf("%d",x);
	while(x!=9999){
		//③对头结点进行后插
		LNode *s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);    //继续输入下一个待插入值
	}
	return L;
}

比较头插法和尾插法可以发现，如果插入数据域为1，2，3的三个结点，头插法插入后元素是逆序的，因此头插法建立单链表的一个重要的应用就是链表的逆置。

4.7，双向链表

通过前面的学习可以知道，对于单链表，只有一个指针域，指向后继结点。因此想要找到某结点的后继结点可以直接通过指针找到，但找前驱结点则比较麻烦，需要从表头遍历。双向链表则可以完美解决这一问题。

双向链表相当于在单链表的每个结点中，在设置一个指向前驱结点的指针域。因此双向链表中的结点都有两个指针域，一个指向直接后继，一个指向直接前驱。结构如下图所示：

双向链表结点的代码定义为：

typedef struct DNode{
	ElemType data;       //数据域
	struct DNode *prior,*next;    //前驱和后继指针
}DNode,*DLinkList;

4.7.1，双向链表的初始化

双向链表初始化操作思想：

• 给头结点分配空间；
• 头结点的prior指针（前驱指针）永远指向NULL；
• 头结点的next指针（后继指针）在双链表没有元素时指向NULL；

双向链表初始化操作代码实现如下：

//双向链表的初始化操作（带头结点）
bool InitDlinkList(DLinkList &L){
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL){
		return false;  //内存不足，分配失败
	}
	L->prior=NULL; //头结点的prior指针指向NULL
	L->next=NULL;   //头结点的next指针指向NULL
	return true;
}

4.7.2，双向链表的插入

想要实现指定结点的后插操作，如在双向链表的p结点之后插入s结点，核心在于修改指针。

• s->next=p->next; —新结点的后继指针指向p结点的后继结点
• p->next->prior=s; —p结点的后继结点的前驱指针指向新结点
• s->prior=p; —新结点的前驱指针指向p结点
• p->next=s; —p结点的后继指针指向新结点
• 如果p是最后一个结点需进行特殊处理，否则执行p->next->prior=s时会报空指针错误（因为此时p->next为NULL）；

双向链表的插入操作（指定结点后插）代码实现如下：

//双链表指定结点的后插操作（带头结点）
bool InsertNextNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL){  //非法参数
		return false;    
	}
	
	//双链表元素插入
	s->next=p->next;
	if(p->next!=NULL){      
		p->next->prior=s;     //p结点不是双向链表内最后一个结点时执行
	}
	s->prior=p;
	p->next=s;
	return true;
}

4.7.3，双向链表的元素删除和整表销毁

①双向链表的元素删除操作，一般是删除指定结点的后继结点。并核心也是修改指针，实现思路如下：

• 假设要删除的结点为p，p的后继结点为q；
• 修改指针p->next=q->next；
• q->next如果不为空则说明p不是最后一个元素，此时执行操作q->next->prior=p；q->next如果不为空则不执行；
• 释放结点q的空间。

双向链表元素删除操作代码实现如下：

//双向链表删除p结点的后继结点
bool DeleteNextNode(DNode *p){
	if(p==NULL){
		return false;  //参数不合法
	}
	DNode *q=p->next;  //找到p的后继结点q
	if(q==NULL){       //p结点没有后继结点
		return false;   
	}

	//删除结点
	p->next=q->next;  
	if(q->next!=NULL){  //q结点不是最后一个结点时
		q->next->prior=p;
	}
	return true;
}

②双向链表的整表销毁操作可以循环执行元素删除操作实现，具体实现思路如下：

• 循环删除头结点后的各结点；
• 删除各结点之后释放头结点空间；
• 使头指针指向NULL；

双向链表整表销毁操作代码实现如下：

//双向链表整表销毁
void DestoryList(DLinkList &L){
	//循环释放各个数据结点
	while(L->next!=NULL){
		//双链表删除指定结点的后继结点操作（前面已定义）
		DeleteNextNode(L);
	}
	free(L); //删除完成，释放头结点
	L=NULL;  //头指针指向NULL
}

4.7.4，双向链表的遍历

双向链表的遍历方式分为前向遍历和后向遍历。其中前向遍历又分为带头结点和不带头结点两种实现方式。具体代码逻辑如下

//不带头结点的双向链表的前向遍历
while(p!=NULL){
	/*对结点p做相应的操作，此处省略*/
	p=p->prior;  //p指针指向前驱结点
}

//带头结点的双向链表的前向遍历
while(p->prior!=NULL){
	/*对结点p做相应的操作，此处省略*/
	p=p->prior;  //p指针指向前驱结点
}

//双向链表后向遍历
while(p->next!=NULL){
	/*对结点p做相应的操作，此处省略*/
	p=p->next;  //p指针指向后继结点
}

此外，由于双向链表不可随机存取，按位查找，按值查找操作都只能通过遍历的方式实现。因此时间复杂度均为O(n)。

4.8，循环链表

循环链表有循环单链表和循环双链表。

4.8.1，循环单链表

前面学习到的普通单链表的表尾结点的next指针是指向NULL的，而循环单链表的表尾结点的next指针是指向头结点的。图示如下：

那么循环单链表来说，它的初始化状态（空表状态）如下图所示：

因此循环单链表的结点定义和初始化操作代码实现如下：

//循环单链表的结点定义（同单链表）
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

//循环单链表的初始化操作
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL){  //内存不足，分配失败
		return false;
	}
	L->next=L;  //循环单链表初始化时头结点的next指针指向头结点！！！
	return true;
}

已知空表的状态，则循环单链表的判空操作即看头指针是否指向头结点； 代码实现如下：

//循环单链表判空操作
bool Empty(LinkList L){
	if(L->next==L){
		return true;
	}else {
		return false;
	}
}

同理，若要判断结点p是否为循环单链表的表尾结点，则只需要判断p->next是否为L。

对于单链表，给定一个结点，只能找到该结点的后续的各结点；
而对于循环单链表而言，给定一个结点，可以找到表中其他任何一个结点。

拓展思考：
在很多情况下，我们对链表的操作都是在链表的头部或尾部。那么对于一个循环单链表，若头指针指向头结点，那么查找表头的时间复杂度为O(1)，而查找表尾的时间复杂度为O(n)。这种情况能不能进行优化呢？

实际上，只需要让头指针指向表尾元素即可，这样的话可以通过指针直接访问表尾元素，若要访问循环单链表的表头元素，可以直接访问表尾元素的下一个结点即可，对表头和表尾元素查找的时间复杂度均为O(1)；

4.8.2，循环双链表

前面学习到的普通双链表的表尾结点的next指针和表头结点的prior指针都是指向NULL的，而循环双链表的表尾结点的next指针是指向头结点的，表头结点的prior指针是指向表尾结点的。图示如下：

那么循环双链表来说，它的初始化状态（空表状态）如下图所示：

因此循环双链表的结点定义和初始化操作代码实现如下：

//循环双链表的结点定义（同双链表）
typedef struct DNode{
	ElemType data;       //数据域
	struct DNode *prior,*next;    //前驱和后继指针
}DNode,*DLinkList;

//循环双链表的初始化操作
bool InitDLinkList(DLinkList &L){
	L=(DNode *)malloc(sizeof(DNode));  //分配一个头结点
	if(L==NULL){
		return false;  //内存不足，分配失败
	} 
	L->prior=L;  //头结点的prior指针指向头结点
	L->next=L;   //头结点的next指针指向头结点
	return true;
}

同理，循环双链表的判空操作和判断指定结点是否为表尾结点的代码如下：

//循环双链表判空
bool Empty(DLinkList L){
	if(L->next==L){
		return true;
	}else{
		return false;
	}
}

//判断指定结点是否为循环双链表表尾结点
bool isTail(DLinkList L,DNode *p){
	if(p->next==L){      //看该结点的下一个结点是否为表头结点
		return true;
	}else{
		return false; 
	}
}

循环双链表的插入操作

回顾普通双链表，p结点的后插操作中，需要判断p结点是否为表尾结点，若为非表尾结点则需要修改其后继结点p->next的指针。因为在普通双链表内，表尾结点next指针指向NULL，需要特殊处理。而循环双链表内，表尾元素的next指针指向头结点，无需特殊处理，无需判断p结点是否为最后一个结点。逻辑较普通双链表更简单。

循环双链表指定结点后插操作的代码实现如下：

//在p结点之后插入s结点
bool InsertNextNode(DNode *p, DNode *s){
	s->next=p->next;
	p->next->prior=s;   //循环双链表表尾结点next指针指向表头，不会出现空指针错误
	s->prior=p;
	p->next=s;
	return true;
}

同理，循环双链表的删除（指定结点后删操作），也无需判断是否为表尾结点，核心代码逻辑如下：

//删除p的后继结点q
bool deleteNode(DNode *p){
	DNode *q=p->next;   
	p->next=q->next;
	q->next->prior=p;  //循环双链表此处不会出现空指针错误
}

4.9，静态链表

• 静态链表是用数组方式实现的链表；
• 某个结点存放的游标如果为-1，则说明该结点为表尾结点；
• 为了方便，也可以将空闲结点位置的游标设置为-2，这样就可以覆盖脏数据，并且可以通过判断游标是否为-2来判断该结点是否为空；
• 静态链表的优点是增删操作无需移动大量元素；
• 静态链表的缺点是不能随机存取，只能头结点开始依次向后查找；且容量固定不变；
• 适用于不支持指针的语言以及数据元素固定不变的场景；

静态链表的两种初始化方式：

#define MaxSize 10
typedef int ElemType;

//初始化方式一
typedef struct{
	ElemType data;  //数据域
	int next;  //游标
}SLinkLisk[MaxSize];

//初始化方式二
struct Node{
	ElemType data;
	int next;
};
typedef struct Node SLinkList[MaxSize];  //这样就可以使用SLinkList定义一个长度为MaxSize的Node型数组（SLinkList List;）

静态链表的插入（位序i的位置上插入结点）：

• 先在静态链表内找到一个空的结点，存入数据元素；
• 从头结点循环找到位序为（i-1）的结点；
• 修改新结点的游标；
• 修改（i-1）号结点的游标；

静态链表删除某个结点：

• 从头结点出发找到该结点的前驱结点；
• 修改前驱结点的游标；
• 被删除结点的游标可以设置为-2；

4.10，顺序表和链表的总结

4.10.1，逻辑结构

从逻辑结构来看，顺序表和链表都是线性结构，元素之间为一对一关系。

4.10.2，存储结构

从存储结构来看二者各有优缺点。

因此当表长难以预估，并且需要频繁插入删除元素的场景下，使用链表更合适。比如实现奶茶店的排队取号功能；
当表长可预估，且查询操作比较多的场景下，使用顺序表更合适。比如实现课堂上的学生点名功能。

文章来源地址https://www.toymoban.com/news/detail-460522.html

到了这里，关于顺序表和链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！