数据结构》第 2 章：线性表 - 2.3 链表
最编程
2024-03-13 07:45:10
...
2.3.1 单链表的基本概念
- 单链表：用链式存储实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。
-
特点：
优点：不要求大片连续空间，改变容量方便。
缺点：不可随机存取，要耗费一定空间存放指针。 -
两种实现方式：
带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
不带头结点，麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。
2.3.2 单链表的实现
不带头结点的单链表：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L = NULL; //空表，暂时还没有任何结点
return true;
}
void test(){
LinkList L; //声明一个指向单链表的头指针
//初始化一个空表
InitList(L);
...
}
//判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL)
}
带头结点的单链表：
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 = NULL; //头结点之后暂时还没有结点
return true;
}
void test(){
LinkList L; //声明一个指向单链表的头指针
//初始化一个空表
InitList(L);
...
}
//判断单链表是否为空
bool Empty(LinkList L){
if (L->next == NULL)
return true;
else
return false;
}
2.3.3 单链表的插入
- 按位序插入（带头结点）：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
return False;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh，p最后会等于NULL
p = p->next;
j++;
}
//p值为NULL说明i值不合法
if (p==NULL)
return false;
//在第i-1个结点后插入新结点
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
//将结点s连到p后
return true;
}
时间复杂度：
- 最好时间复杂度：O ( 1 )
- 最坏时间复杂度：O ( n )
- 平均时间复杂度：O ( n )
- 按位序插入（不带头结点）：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//在第i个位置插入元素e
bool ListInsert(LinkList &L, int i, ElemType e){
//判断i的合法性
if(i<1)
return false;
//需要判断插入的位置是否是第1个
if(i==1){
LNode *s = (LNode *)malloc(size of(LNode));
s->data =e;
s->next =L;
L=s; //头指针指向新结点
return true;
}
//i>1的情况与带头结点一样，唯一区别是j的初始值为1
LNode *p; //指针p指向当前扫描到的结点
int j=1; //当前p指向的是第几个结点
p = L;
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh，p最后会等于NULL
p = p->next;
j++;
}
//p值为NULL说明i值不合法
if (p==NULL)
return false;
//在第i-1个结点后插入新结点
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
时间复杂度：
- 最好时间复杂度：O ( 1 )
- 最坏时间复杂度：O ( n )
- 平均时间复杂度：O ( n )
除非特别声明，否则之后的代码都默认为带头结点！
3. 指定结点的后插操作：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
// 在结点p后插入元素e
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;
p->next = s;
return true;
}
// 按位序插入的函数中可以直接调用后插操作
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
return False;
LNode *p;
//指针p指向当前扫描到的结点
int j=0;
//当前p指向的是第几个结点
p = L;
//循环找到第i-1个结点
while(p!=NULL && j<i-1){
//如果i>lengh, p最后会等于NULL
p = p->next;
j++;
}
return InsertNextNode(p, e)
}
时间复杂度：O ( 1 )
- 指定结点的前插操作：
如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对q进行后插操作；
如果不传入头指针，可以在指定结点p后插入一个结点s，并交换两个结点所保存的数据，从而变相实现指定结点的前插操作。
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
// 在结点p前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){
if(p==NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
// 内存不足分配失败
if(s==NULL)
return false;
// 将s插入结点p之后
s->next = p->next;
p->next = s;
// 交换两个结点中的数据
s->data = p->data;
p->data = e;
return true;
}
时间复杂度：O ( 1 )
2.3.4. 单链表的删除
- 按位序删除：
typedef struct LNode{
ElemType data;
struct LNode *next;}LNode, *LinkList;
// 删除第i个结点并将其所保存的数据存入e
bool ListDelete(LinkList &L, int i, ElemType &e){
if(i<1)
return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L;
//循环找到第i-1个结点
while(p!=NULL && j<i-1){
//如果i>lengh，p和p的后继结点会等于NULL
p = p->next;
j++;
}
if(p==NULL)
return false;
if(p->next == NULL)
return false;
//令q暂时保存被删除的结点
LNode *q = p->next;
e = q->data;
p->next = q->next;
free(q)
return true;
}
时间复杂度：
最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )
- 删除指定结点：
- 如果传入头指针，就可以循环整个链表找到指定结点p的前驱结点q，再对p进行删除操作；
- 如果不传入头指针，可以把指定结点p的后继结点q删除，并使结点p保存结点q存储的数据，从而变相实现删除指定结点的操作。但是如果指定结点p没有后继结点，这么做会报错。
// 删除指定结点p
bool DeleteNode(LNode *p){
if(p==NULL)
return false;
LNode *q = p->next; // 令q指向p的后继结点
// 如果p是最后一个结点，则q指向NULL，继续执行就会报错
p->data = q->data;
p->next = q->next;
free(q);
return true;
}
时间复杂度：O ( 1 )
2.3.5. 单链表的查找
- 按位查找：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
// 查找指定位序i的结点并返回
LNode * GetElem(LinkList L, int i){
if(i<0)
return NULL;
LNode *p;
int j=0;
p = L;
while(p!=NULL && j<i){
p = p->next;
j++;
}
return p;
}
// 封装后的插入操作，在第i个位置插入元素e，可以调用查询操作和后插操作
bool ListInsert(LinkList &L, int i, ElemType e){
if(i<1)
return False;
// 找到第i-1个元素
LNode *p = GetElem(L, i-1);
// 在p结点后插入元素e
return InsertNextNode(p, e)
}
时间复杂度：
最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )
- 按值查找：
// 查找数据域为e的结点指针，否则返回NULL
LNode * LocateElem(LinkList L, ElemType e){
LNode *P = L->next;
// 从第一个结点开始查找数据域为e的结点
while(p!=NULL && p->data != e){
p = p->next;
}
return p;
}
时间复杂度：
最好时间复杂度：O ( 1 )
最坏时间复杂度：O ( n )
平均时间复杂度：O ( n )
- 计算单链表长度：
// 计算单链表的长度
int Length(LinkList L){
int len=0; //统计表长
LNode *p = L;
while(p->next != NULL){
p = p->next;
len++;
}
return len;
}
时间复杂度：O ( n )
2.3.6. 单链表的建立
- 尾插法建立单链表：
// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){
int x; //设ElemType为整型int
L = (LinkList)malloc(sizeof(LNode)); //建立头结点(初始化空表)
LNode *s, *r = L; //r为表尾指针
scanf("%d", &x); //输入要插入的结点的值
while(x!=9999){ //输入9999表示结束
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指针指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置空
return L;
}
时间复杂度：O（n）
- 头插法建立单链表：
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
L->next = NULL; //初始为空链表,这步很关键
scanf("%d", &x); //输入要插入的结点的值
while(x!=9999){ //输入9999表结束
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
//将新结点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}
头插法实现链表的逆置：
// 将链表L中的数据逆置并返回
LNode *Inverse(LNode *L){
LNode *p, *q;
p = L->next; //p指针指向第一个结点
L->next = NULL; //头结点置空
// 依次判断p结点中的数据并采用头插法插到L链表中
while (p != NULL){
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
return L;
}
2.3.7. 双链表
- 双链表的定义：双链表也是链表的一种。双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点。
- 双链表的实现：
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinklist;
- 双链表的初始化 (带头结点)：
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 = NULL; //头结点的prior指针永远指向NULL
L->next = NULL; //头结点之后暂时还没有结点，置空
return true;
}
void testDLinkList(){
DLinklist L;
InitDLinkList(L);
...
}
// 判断双链表是否为空
bool Empty(DLinklist L){
if(L->next == NULL)
return true;
else
return false;
}
- 双链表的后插操作：
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinklist;
// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){
if(p==NULL || s==NULL)
return false;
s->next = p->next;
// 判断结点p之后是否有后继结点
if (p->next != NULL)
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
双链表的前插操作、按位序插入操作都可以转换成后插操作
- 双链表的删除操作：
// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){
if(p==NULL)
return false;
// 找到p的后继结点q
DNode *q =p->next;
if(q==NULL)
return false;
p->next = q->next;
if(q->next != NULL)
q->next->prior=p;
free(q);
return true;
}
// 销毁一个双链表
bool DestoryList(DLinklist &L){
// 循环释放各个数据结点
while(L->next != NULL){
DeletNextDNode(L);
free(L);
// 头指针置空
L=NULL;
}
}
- 双链表的遍历：
// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){
if(p==NULL)
return false;
// 找到p的后继结点q
DNode *q =p->next;
if(q==NULL)
return false;
p->next = q->next;
if(q->next != NULL)
q->next->prior=p;
free(q);
return true;
}
// 销毁一个双链表
bool DestoryList(DLinklist &L){
// 循环释放各个数据结点
while(L->next != NULL){
DeletNextDNode(L);
free(L);
// 头指针置空
L=NULL;
}
}
双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。
2.3.8 循环链表
- 循环链表的定义： 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
- 循环单链表的实现：
typedef struct LNode{
ElemType data;
struct LNode *next;
}DNode, *Linklist;
// 初始化循环单链表
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode));
if(L==NULL)
return false;
// 最后一个结点的next指针指向头结点
L->next = L;
return true;
}
// 判断循环单链表是否为空
bool Empty(LinkList L){
if(L->next == L)
return true;
else
return false;
}
// 判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
if(p->next == L)
return true;
else
return false;
}
- 循环双链表的实现：
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;
// 头结点的prior指针指向最后一个结点，最后一个结点的next指针指向头结点
L->prior = L;
L->next = L;
}
// 判断循环双链表是否为空
bool Empty(DLinklist L){
if(L->next == L)
return true;
else
return false;
}
// 判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){
if(p->next == L)
return true;
else
return false;
}
- 循环双链表的插入和删除操作：
// 将结点s插入到结点p之后
bool InsertNextDNode(DNode *p, DNode *s){
s->next = p->next;
//循环双链表不用担心p结点的下一个结点为空
p->next->prior = s;
s->prior = p;
p->next = s;
}
// 删除p结点的后继结点
bool DeletNextDNode(DNode *p){
// 找到p的后继结点q
DNode *q =p->next;
//循环双链表不用担心q结点的下一个结点为空
p->next = q->next;
q->next->prior=p;
free(q);
return true;
}
2.3.9. 静态链表
-
静态链表的定义：用数组的方式实现的链表。分配一整片连续的内存空间，各个结点集中安置，每个结点包括了数据元素和下一个结点的数组下标。
-
特点：
- 优点：增、删操作不需要大量移动元素。
- 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！
-
静态链表的定义：
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标
};
// 用数组定义多个连续存放的结点
void testSLinkList(){
struct Node a[MaxSize]; //数组a作为静态链表, 每一个数组元素的类型都是struct Node
...
}
也可以这么定义：
#define MaxSize 10 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ELemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
void testSLinkList(){
SLinkList a;
}
第一种是我们更加熟悉的写法，第二种写法则更加侧重于强调 a 是一个静态链表而非数组。
-
静态链表的注意点：
- 初始化静态链表时，需要把a[0]的next设为-1，并将空闲结点的next设置为某个特殊值，比如-2。
- 按位序查找结点时，从头结点出发挨个往后遍历结点，时间复杂度 O = ( n ) O=(n)O=(n)。
- 按位序插入结点的步骤：①找到一个空的结点，存入数据元素；②从头结点出发找到位序为 i-1 的结点；③修 改新结点的next 为 -1；④修改 i-1 号结点的next为新结点的下标；
2.3.10. 顺序表和链表的比较
-
逻辑结构：顺序表和链表都属于线性表，都是线性结构。
-
存储结构：
-
顺序表：顺序存储
优点：支持随机存取，存储密度高。
缺点：大片连续空间分配不方便，改变容量不方便。 -
链表：链式存储
优点：离散的小空间分配方便，改变容量方便。
缺点：不可随机存取，存储密度低。
-
-
基本操作 - 创建：
-
顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。
- 静态分配：静态数组，容量不可改变。
- 动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（使用malloc()、free()）。
- 链表：只需要分配一个头结点或者只声明一个头指针。
-
顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。
-
基本操作 - 销毁：
-
顺序表：修改 Length = 0
静态分配：静态数组——系统自动回收空间。
动态分配：动态数组——需要手动free()。 - 链表：依次删除各个结点 free()。
-
顺序表：修改 Length = 0
-
基本操作 - 增/删：
- 顺序表：插入 / 删除元素要将后续元素后移 / 前移；时间复杂度：O ( n ) O(n)O(n)，时间开销主要来自于移动元素。
- 链表：插入 / 删除元素只需要修改指针；时间复杂度：O ( n ) O(n)O(n)，时间开销主要来自查找目标元素。
-
基本操作 - 查找：
- 顺序表
- 按位查找：O ( 1 ) O(1)O(1)
- 按值查找：O ( n ) O(n)O(n)，若表内元素有序，可在 O ( l o g 2 n ) O(log2n)O(log2n) 时间内找到（二分法）
- 链表：
- 按位查找：O ( n ) O(n)O(n)
- 按值查找：O ( n ) O(n)O(n)
- 顺序表
上一篇： cmake初识
下一篇： 计算机系统结构[1]--流水线作业原理