【数据结构与算法】双链表&循环链表&静态链表

深碍√TFBOYSˉ_ 2024-04-26 02:19 134阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年9月22日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  单链表 VS 双链表
 *  双链表
 *   *  双链表的初始化（带头结点）
     *  双链表的插入
     *  双链表的删除
     *  双链表的遍历
 *  循环单链表
 *  循环双链表
 *   *  循环双链表的初始化
     *  循环双链表的插入
     *  循环双链表的删除
 *  静态链表
 *   *  什么是静态链表
     *  定义静态链表
     *  基本操作的实现
     *   *  初始化
         *  查找
         *  插入位序为 i 的结点
         *  删除某个结点
 *  顺序表和链表的比较

## 单链表 VS 双链表 ##

我们都知道，单链表只有一个指向下一个结点的指针，当我们想要找到前一个结点时就比较麻烦，而双链表拥有两个指针

总的来说：

*  单链表 —— 无法逆向检索，有时候不太方便
 *  双链表 —— 可进可退，存储密度更低一丢丢

**定义双链表结点类型**

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

## 双链表 ##

### 双链表的初始化（带头结点） ###

定义一个 **InitLinklist** 函数，参数为双链表的引用，加引用是因为要改变这个双链表

注意：头结点的前驱指针永远指向 **NULL**

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElemType;
    
    typedef struct DNode{
        
    	ElemType data;				//数据域
    	struct DNode *prior, *next;	//前驱和后继指针
    }DNode, *DLinklist;
    
    //初始化双链表
    bool InitLinklist(DLinklist &L) {
        
    	L = (DNode *)malloc(sizeof(DNode));		//分配一个头结点
    	if (L == NULL) return false;			//内存不足，分配失败
    	L->prior = NULL;						//头结点的 prior 永远指向 NULL
    	L->next = NULL;							//头结点之后暂时还没有结点
    	return true;
    }
    
    //判断双链表是否为空（带头结点）
    bool Empty(DLinklist L) {
        
    	if (L->next == NULL)
    		return true;
    	else
    		return false;
    }
    
    void testDLinklist() {
        
    	//初始化双链表
    	DLinklist L;
    	InitLinklist(L);
    }

### 双链表的插入 ###

**后插法**

//在p结点之后插入s结点
    bool InsertNextDNode(DNode *p, DNode *s) {
        
    	if (p == NULL || s == NULL) return false;	//非法参数
    
    	s->next = p->next;
    	if (p->next != NULL)		//如果p结点有后继结点
    		p->next->prior = s;
    	s->prior = p;
    	p->next = s; 
    	return true;
    }

学会了后插操作，我们也就学会了按位序插入和前插法，大概思路为找到目标结点的前驱结点，然后对其进行后插操作

### 双链表的删除 ###

//删除p结点的后继结点
    bool DeleteNextDNode(DNode *p) {
        
    	if (p == NULL) return false;
    
    	DNode *q = p->next;				//找到p结点的后继结点q
    	if (q == NULL) return false;	//p没有后继
    	
    	p->next = q->next;
    	if (q->next != NULL)			//q结点不是最后一个结点
    		q->next->prior = p;
    	free(p);						//释放结点空间
    	return true;
    }
    
    //销毁双链表
    void DestoryList(DLinklist &L) {
        
    	//循环释放各个数据结点
    	while (L->next != NULL) {
        
    		DeleteNextDNode(L);
    	}
    	free(L);	//释放头结点
    	L = NULL;	//头指针指向NULL
    }

### 双链表的遍历 ###

由于双链表不可随机存取，所以按位查找、按值查找等操作都只能用遍历的方式实现，时间复杂度为 **O(n)**

//后向遍历
    while (p != NULL) {
        
    	//对结点p做相应处理，比如打印
    	p = p->next;
    }
    
    //前向遍历
    while (p != NULL) {
        
    	//对结点p做相应处理
    	p = p->prior;
    }
    
    //前向遍历（跳过头结点）
    while (p->prior != NULL) {
        
    	//对结点p做相应处理
    	p = p->prior;
    }

## 循环单链表 ##

我们都知道，单链表的表尾结点的 **next** 指针是指向 **NULL**，顾名思义，循环单链表的表尾结点的 **next** 指针就是指向头结点的

循环单链表的优点：从一个结点出发可以找到其他任何一个结点

typedef int ElemType;
    
    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是否为循环单链表的表尾结点
    bool isTail(LinkList L, LNode *p) {
        
    	if (p->next == L)
    		return true;
    	else 
    		return false;
    }

## 循环双链表 ##

双链表：

*  表头结点的 **prior** 指向 **NULL**
 *  表尾结点的 **next** 指向 **NULL**

循环双链表

*  表头结点的 **prior** 指向表尾结点
 *  表尾结点的 **next** 指向头结点

### 循环双链表的初始化 ###

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElemType;
    
    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;
    }
    
    //判断结点p是否为循环双链表的表尾结点
    bool isTail(DLinklist L, DNode *p) {
        
    	if (p->next = L)
    		return true;
    	else
    		return false;
    }
    
    void testDLinklist() {
        
    	//初始化双链表
    	DLinklist L;
    	InitDLinklist(L);
    }

### 循环双链表的插入 ###

//在p结点之后插入s节点
    bool InsertNextDNode(DNode *p, DNode *s) {
        
    	s->next = p->next;
    	p->next->prior = s;
    	s->prior = p;
    	p->next = s;
    	return true;
    }

### 循环双链表的删除 ###

//删除p的后继结点q
    p->next = q->next;
    q->next->prior = p;
    free(q);

## 静态链表 ##

### 什么是静态链表 ###

单链表：各个结点在内存中星罗棋布、散落天涯

静态链表：分配一整片连续的内存空间，各个结点集中安置，**0** 号结点充当 “头结点”，下一个结点的数组下标（也称为游标）充当 “指针”，游标为 **-1** 时表示已经到达表尾

静态链表是用数组的方式来实现的链表，其优点为 —— 增、删操作不需要大量移动元素；缺点为 —— 不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

### 定义静态链表 ###

#define MaxSize 10			//静态链表的最大长度
    struct Node{
        
    	ElemType data;			//存储数据元素
    	int next;				//下一个元素的数组下标
    };

或者

#define MaxSize 10			//静态链表的最大长度
    typedef struct {
        
    	ElemType data;			//存储数据元素
    	int next;				//下一个元素的数组下标
    } SLinkList[MaxSize];

`SLinkList a` 相当于 `struct Node a[MaxSize]`

### 基本操作的实现 ###

#### 初始化 ####

*  把 **a\[0\]** 的 **next** 设置为 **-1**
 *  把空的结点的 **next** 设置为 **-2**

#### 查找 ####

从头结点出发依次往后遍历结点

#### 插入位序为 i 的结点 ####

1.  找到一个空的结点，存入数据元素
2.  从头结点出发找到位序为 **i-1** 的结点
3.  修改新结点的 **next**
4.  修改 **i-1** 号结点的 **next**

#### 删除某个结点 ####

1.  从头结点出发找到前驱结点
2.  修改前驱结点的游标
3.  被删除结点的 **next** 设置为 **-2**

## 顺序表和链表的比较 ##

从逻辑结构来说，顺序表和链表都属于线性表，都是线性结构

从存储结构来说，顺序表采用顺序存储，而链表采用链式存储

顺序表

*  优点：支持随机存取，存取密度高
 *  缺点：大片连续空间分配不方便，改变容量不方便

链表：

*  优点：离散的小空间分配方便，改变容量方便
 *  缺点：不可随机存取，存储密度低

从基本操作来看

**创**

*  顺序表需要预分配大片连续空间，若分配空间过小，则之后不方便扩展容量；若分配空间过大，则浪费内存资源。如果采取静态分配的方式，则容量不可改变；如果采取动态分配的方式，则容量可改变，但需要移动大量元素，时间代价高
 *  链表只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

**销**

*  对链表来说，你只需扫描整个链表，依次删除（**free**）各个结点即可
 *  对顺序表来说，首先你需要修改 **length = 0**，如果是采用静态分配的方式，当静态数组的生命周期结束时，系统会自动回收空间；如果是采用动态分配的方式，用 **malloc** 申请的空间是属于内存中的堆区，在堆区的内存空间不会由系统自动回收，需要我们手动 **free**

**增删**

*  对顺序表来说，插入或删除都要讲后续元素全部后移或前移，时间复杂度为 **O(n)**，时间开销主要来自移动元素
 *  对链表来说，插入或删除元素只需要修改指针即可，时间复杂度为 **O(n)**，时间开销主要来自查找目标元素
 *  虽然时间复杂度一样，但是结合实际因素，链表增删的效率要比顺序表高得多

**查**

*  对顺序表来说，按位查找的时间复杂度为 **O(1)**；按值查找的时间复杂度为 **O(n)**，如果表内元素有序，可采用折半查找等方法在 **O(log2n)** 时间内找到
 *  对链表来说，按位查找的时间复杂度为 **O(n)**；按值查找的时间复杂度也为 **O(n)**

综上所述

*  表长难以预估、经常要增加或删除元素 —— 链表
 *  表长可预估、查询操作较多 —— 顺序表

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482