C语言数据结构(一)

发表于 更新于 分类于 阅读次数：

C语言数据结构

version : v1.0 「2022.8.20」 最后补充


author： Y.Z.T.

摘要： 简单记录几种个人在嵌入式开发中常用的数据结构


简介： 之前关于数据结构的学习都是比较碎片化，趁有空简单复习一下






1️⃣ 常用数据结构概况

数据结构=逻辑结构（对象怎么表示）+存储结构（对象怎么存到计算机里）+算法（对计算机中的对象怎么增删查改等）


数据结构大致包含以下几种存储结构：

  • 线性表

    • 顺序表
    • 链表
    • 栈
    • 队列

  • 树结构

    • 普通树
    • 二叉树
    • 线索二叉树

  • 图储存结构


1.1 线性表

线性表结构存储的数据往往是可以依次排列的，具备==“一对一”关系的数据就可以使用线性表==来存储。


例如，存储类似 {1,3,5,7,9} 这样的数据时，各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（除首元素和尾元素），因此可以使用线性表存储。


线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。


1.1.1 顺序表

顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}

image-20220811215039010


1.1.2 链表

  • 我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的，

  • 链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。

链表结构

1.1.3 栈和队列

栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。


1.1.3.1 栈

栈中的元素只能从线性表的一端进出（另一端封死），且要遵循==“先入后出”==的原则，即先进栈的元素后出栈。

栈结构示意图


如图所示：

  • 栈中含有 3 个元素，分别是 A、B 和 C，从在栈中的状态可以看出 是A 、B、C。
  • 根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 、B、 A。



1.1.3.2 队列

队列中的元素只能从线性表的一端进，从另一端出，且要遵循==“先入先出”==的特点，即先进队列的元素也要先出队列。


队列结构示意图


如图所示：

  • 队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是A、B、C。
  • 根据“先进先出”的原则，3 个元素出队列的顺序应该是A、B、C。


1.2 树结构

树存储结构适合存储具有==“一对多”==关系的数据。


树

1.3 图结构

图存储结构适合存储具有==“多对多”==关系的数据。

图存储结构示意图

如图所示：

  • 从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，这就是“多对多”的关系
  • 满足这种关系的数据可以使用图存储结构。

1.4 数据结构基本概念

1.4.1 数据

数据（Data）是信息的载体，是可以被计算机识别，存储并加工处理的描述客观事物的信息符号的总称。数据不仅仅包括了整形，浮点数等数值类型，还包括了字符甚至声音，视频，图像等非数值的类型。


1.4.2 数据元素

数据元素（Data Element）是描述数据的基本单位，也被称为记录。一个数据元素有若干个数据项组成。

如禽类，鸡鸭都属于禽类的数据元素。


1.4.3 数据项

数据项（Data Item）是描述数据的最小单位，其可以分为组合项和原子项：

  • 组合项： 如果数据元素可以再度分割，则每一个独立处理单元就是数据项，数据元素就是数据项的集合。
  • 原子项： 如果数据元素不能再度分割，则每一个独立处理的单元就是原子项。

如日期2019年4月25日就是一个组合项，其表示日期，但如果单独拿25日这个数据出来观测，这就是一个原子项，因为其不可以再分割。


1.4.4 数据对象

数据对象（Data Object）是性质相同的一类数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。


1.4.5 数据结构

数据结构（Data Structures）主要是指数据和关系的集合，数据指的是计算机中需要处理的数据，而关系指的是这些数据相关的前后逻辑，这些逻辑与计算机储存的位置无关，其主要包含以下四大逻辑结构。


1.5 嵌入式系统中的数据结构特点


嵌入式系统比较流行的定义是，以应用为中心，以计算机技术为基础，软件硬件可裁剪，适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。其数据结构一般具备以下特点：


  • 数据规模较小、采用简单数据结构（线性表）
  • 采用RAM资源占用较少的算法（可能导致算法效率下降，能实现功能）
  • 采用程序代码简单的算法，可以减小ROM开销

1.6 时空复杂度

1.6.1 时间复杂度

1.6.1.1 定义

  • 时间复杂度表示一个程序运行所需要的时间，我们一般并不需要得到详细的值，只是需要比较快慢的区别即可，为此，我们需要引入==时间频度（语句频度）==的概念。

  • 时间频度中，n称为问题的规模，当n不断变化时,时间频度T(n)也会不断变化。

  • 一般情况下，算法中的基本操作重复次数的是问题规模n的某个函数，用==T(n)==表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作

    T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

  • 一般来说，f(n)是和算法执行次数增长率相同（理解为算法执行次数表达式中最快上升的函数项）的关于n的函数


1.6.1.2 衡量方法

事先统计法采取在计算机编译程序前对该算法进行预估的方式估算。我们可以通过利用时间频度以及函数的思维进行对时间复杂度的解析。


例为预估一个算法运行时间：

先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。


以一段简单的 C 语言程序为例，预估出此段程序的运行时间：

1
2
3
4
for(int i = 0 ; i < n ; i++)     //<- 从 0 到 n，执行 n+1 次
{   
	a++;                         //<- 从 0 到 n-1，执行 n 次
}

可以看到，这段程序中仅有 2 行代码，其中：

  • for 循环从 i 的值为 0 一直逐增至 n（注意，循环退出的时候 i 值为 n），因此 for 循环语句执行了 n+1 次；
  • 而循环内部仅有一条语句，a++ 从 i 的值为 0 就开始执行，i 的值每增 1 该语句就执行一次，一直到 i 的值为 n-1，因此，a++ 语句一共执行了 n 次。

因此，整段代码中所有语句共执行了 (n+1)+n 次，即 2n+1 次。数据结构中，每条语句的执行次数，又被称为该语句的频度。整段代码的总执行次数，即整段代码的频度。



再举一个例子：

1
2
3
4
5
6
7
for(int i = 0 ; i < n ; i++)           // n+1
{ 
    for(int j = 0 ; j < m ; j++)       // n*(m+1)
    {
        num++;                         // n*m
    }
}

注意： 此段程序的频度为：(n+1)+n*(m+1)+n*m，简化后得 2*n*m+2*n+1


比较可得：

比较 2n+1 和 2n2+2n+1 的大小，显然当 n 无限大时，前者要远远小于后者

不同程序运行时间的比较
1.6.1.3 表示方法

频度表达式可以这样简化：

  • 去掉频度表达式中，所有的加法常数式子。例如 2n2+2n+1 简化为 2n2+2n ；
  • 如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如 2n2+2n 简化为 2n2
  • 如果最高项存在系数，且不为 1，直接去掉系数。例如 2n2 系数为 2，直接简化为 n2 ；

  • 事实上，对于一个算法（或者一段程序）来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数。
  • 例如 2n+1 最简为 n，实际上就是 a++ 语句的执行次数；
  • 同样 2n2+2n+1 简化为 n2，实际上就是最内层循环中 num++ 语句的执行次数。

数据结构推出了大 O 记法（注意，是大写的字母 O，不是数字 0）来表示算法（程序）的运行时间:


大 O 记法的表示方法也很简单，格式如下：

1
O(频度)

其中，这里的频度为最简之后所得的频度。


例如，用大 O 记法表示上面 2 段程序的运行时间，则上面第一段程序的时间复杂度为 O(n)，第二段程序的时间复杂度为 O(n2)。


如下列举了常用的几种时间复杂度，以及它们之间的大小关系：

1
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

注意，这里仅介绍了以最坏情况下的频度作为时间复杂度，而在某些实际场景中，还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的平均时间复杂度。


1.6.2 空间复杂度

1.6.2.1 定义

一个程序的空间复杂度是指运行完一个程序所需内存的大小，其包括两个部分。

  • 固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
  • 可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

1.6.2.2 表示方法

和时间复杂度类似，一个算法的空间复杂度，也常用大 O 记法表示

如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为 O(1)；反之，如果有关，则需要进一步判断它们之间的关系：

  • 如果随着输入值 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示;
  • 如果随着输入值 n 的增大，程序申请的临时空间成 n2 关系增长，则程序的空间复杂度用 O(n2) 表示；
  • 如果随着输入值 n 的增大，程序申请的临时空间成 n3 关系增长，则程序的空间复杂度用 O(n3) 表示；
  • 等等。

在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。



2️⃣ 线性表

特别注意： 使用线性表存储的数据，如同向数组中存储数据那样，要求 数据类型必须一致 ，也就是说，线性表存储的数据，要么全部都是整形，要么全部都是字符串。一半是整形，另一半是字符串的一组数据无法使用线性

表存储。


2.1 顺序储存和链式储存

线性表，全名为线性存储结构。使用线性表存储数据的方式可以这样理解，即 “把所有数据用一根线儿串起来，再

存储到物理空间中”。



这是一组具有 “一对一” 关系的数据，我们接下来采用线性表将其储存到 物理空间 中。


首先，把它们按照顺序“串”起来：

img


如上图所示，左侧是“串”起来的数据，右侧是空闲的物理空间。把这“一串儿”数据放置到物理空间，我们可以选择

以下两种方式：

image-20220812233506400

​ 数据集中存放 数据分散存放


如上图所示 ，线性表存储数据可细分为以下 2 种：


  • 将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表）；
  • 数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）；

[ 也就是说，线性表存储结构可细分为顺序存储结构和链式存储结构。]



2.2 顺序表

2.2.1 顺序表初始化

使用顺序表存储数据之前，除了要申请足够大小的物理空间之外，为了方便后期使用表中的数据，顺序表还需要实时记录以下 2 项数据：

  1. 顺序表申请的存储容量；
  2. 顺序表的长度，也就是表中存储数据元素的个数；

特别注意： 正常状态下，顺序表申请的存储容量要大于顺序表的长度。


自定义顺序表：

1
2
3
4
5
typedef struct Table{
    int * head;//声明了一个名为head的长度不确定的数组，也叫“动态数组”
    int length;//记录当前顺序表的长度
    int size;//记录顺序表分配的存储容量
}table;

注意： head 是我们声明的一个未初始化的动态数组，不要只把它看做是普通的指针。


建立顺序表需要做如下工作：

  • 给 head 动态数据申请足够大小的物理空间；

    1
    #define maxsize 1024 // 线性表中可能的最大节点数

  • 给 size 和 length 赋初值；


初始化函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
table initTable()
{
    table t;
    t.head=(int*)malloc(maxsize*sizeof(int));//构造一个空的顺序表，动态申请存储空间
    if (!t.head) 						  //如果申请失败，作出提示并直接退出程序
    {
        printf("初始化失败");
        return(-1);						//申请失败，返回-1
    }
    t.length=0;							//空表的长度初始化为0
    t.size=maxsize;						//空表的初始存储空间为Size
    return t;							// 创建成功，返回一个已经初始化完成的顺序表
}

main.c

1
2
3
4
5
6
7
8
9
10
void main()
{
    table t = initTable();	// 创建顺序表
   
    for (int i=1; i<=maxsize; i++)  //向顺序表中添加元素，这里为举例
    {
        t.head[i-1]=i;
        t.length++;
    }
}

2.2.2 顺序表的基本操作

2.2.2.1 顺序表插入元素
2.2.2.1.1 操作思路

向已有顺序表中插入数据元素，根据插入位置的不同，可分为以下 3 种情况：

  1. 插入到顺序表的表头；
  2. 在表的中间位置插入元素；
  3. 尾随顺序表中已有元素，作为顺序表中的最后一个元素；

虽然数据元素插入顺序表中的位置有所不同，但是都使用的是同一种方式去解决，即：通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

  • 将要插入位置元素以及后续的元素整体向后移动一个位置；
  • 将元素放到腾出来的位置上；

 例：

在 {1,2,3,4,5} 的第 3 个位置上插入元素 6，实现过程如下：


  • 遍历至顺序表存储第 3 个数据元素的位置

找到目标元素位置


  • 将元素 3 以及后续元素 4 和 5 整体向后移动一个位置

    将插入位置腾出

  • 将新元素 6 放入腾出的位置

插入目标元素



2.2.2.1.2 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
  * @brief      顺序表插入操作函数
  * @param[in]  t	 ： 要操作的表
  * @param[in]  elem ： 插入的元素
  * @param[in]  add  ： 插入到顺序表的位置
  * @retval     返回操作后的结果
  * @attention  none
  */
table addTable(table t,int elem,int add)
{
    //判断插入本身是否存在问题（如果插入元素位置比整张表的长度+1还大（如果相等，是尾随的情况），或者插入	的位置本身不存在，程序作为提示并自动退出）
    if (add>t.length+1||add<1) 
    {
        printf("插入位置有问题\n");
        return t;
    }
    //做插入操作时，首先需要看顺序表是否有多余的存储空间提供给插入的元素，如果没有，需要申请
    if (t.length==t.size) 
    {
        t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));	// 重新调整调用的malloc指																 //	向的内存块的大小
        if (!t.head) 	// 分配失败
        {
            printf("存储分配失败\n");
            return t;
        }
        t.size+=1;
    } 
    //插入操作，需要将从插入位置开始的后续元素，逐个后移
    for (int i=t.length-1; i>=add-1; i--) 
    {
        t.head[i+1]=t.head[i];
    }
    //后移完成后，直接将所需插入元素，添加到顺序表的相应位置
    t.head[add-1]=elem;
    //由于添加了元素，所以长度+1
    t.length++;
    return t;
}

2.2.2.2 顺序表删除元素
2.2.2.2.1 操作思路

从顺序表中删除指定元素，实现起来非常简单，只需找到目标元素，并将其后续所有元素整体前移 1 个位置即可。

后续元素整体前移一个位置，会直接将目标元素删除，可间接实现删除元素的目的。


例：

例如，从 {1,2,3,4,5} 中删除元素 3：

img


2.2.2.2.2 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
  * @brief      顺序表删除操作函数
  * @param[in]  t	 ： 要操作的表
  * @param[in]  add  ： 删除顺序表的位置
  * @retval     返回操作后的结果
  * @attention  none
  */
table delTable(table t,int add)
{
    if (add>t.length || add<1)  // 删除元素位置大于表长度，或删除位置不存在
    {
        printf("被删除元素的位置有误\n");
        return t;
    }
    //删除操作，将删除位置后续元素整天前移一位
    for (int i=add; i<t.length; i++) 
    {
        t.head[i-1]=t.head[i];
    }
    t.length--;	//删除后长度减一
    return t;
}


2.2.2.3 顺序表查找元素

顺序表中查找目标元素，可以使用多种查找算法实现，比如说二分查找算法、插值查找算法等


例：

用顺序查找法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
  * @brief      顺序表查找元素
  * @param[in]  t	 ： 要操作的表
  * @param[in]  elem ： 要查找的数据元素的值
  * @retval     返回操作后的结果
  * @attention  none
  */
int selectTable(table t,int elem)
{
    for (int i=0; i<t.length; i++)  // 遍历查找
    {
        if (t.head[i]==elem)
        {
            return i+1;
        }
    }
    return -1;//如果查找失败，返回-1
}

2.2.2.4 顺序表更改元素

顺序表更改元素：

  • 找到目标元素；
  • 直接修改该元素的值；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
  * @brief      顺序表更改元素
  * @param[in]  t	 ： 要操作的表
  * @param[in]  elem ： 要更改的元素
  * @param[in]  newElem  ： 新的数据元素
  * @retval     返回操作后的结果
  * @attention  none
  */
table amendTable(table t,int elem,int newElem)
{
    int add=selectTable(t, elem); // 用查找函数查找要更改元素的位置
    t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
    return t;
}

2.2.3 顺序表的特点与缺点

顺序表的特点是：

存储结构的顺序与逻辑结构的顺序完全一致,因此顺序表的最大优点是可以方便地随机存取表中任一个结点。


缺点：

  • 插入或删除运算不方便,除表尾的位置以外,其他位置上的操作都必须移动大量的结点,平均要移动表中约一半的结点,平均时间复杂度为O(n), 其效率较低。
  • 由于顺序表所占空间必须是连续空间,而结点数并不固定,只能预先分配空间(静态分配)。因此,难以确定合适的存储空间,空间过大会造成浪费,空间过小会造成表溢出。


2.3 链表

2.3.1 链表概念


  • 一个或多个结点 组合而成的数据结构称为链表
  • 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
  • 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的

image-20220816184532849

​ 单链表储存示意图


2.3.1.1 结点

结点 一般由两部分内容构成：

  • 数据域：存储真实数据元素

    (可以为你想要储存的任何数据格式，可以是数组，可以是int，甚至可以是结构体)

  • ==指针域：==存储下一个结点的地址（指针）

    (链表的尾部NEXT指向NULL（空），因为尾部没有任何可以指向的空间了)


img


结点结构代码实现：

1
2
3
4
5
6
typedef int datatype;			// 结点的数据类型定义为datatype，方便更改，此处为int
typedef struct node 			// 结点类型定义
{
    datatype data;				// 结点的数据域类型
    struct node *next;			// 结点的指针域类型
}linklist;						// linklist为结点名，每个节点都是一个linklist结构体

特别注意： 由于指针域中的指针要指向的也是一个节点，因此要声明为 node 类型

（这里要写成 struct node* 的形式）。



2.3.1.2 头指针、头结点和首元结点

一个完整的链表需要由以下几部分构成：


  • 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据。
  • 节点： 链表中的节点又细分为头节点、首元节点和其他节点：
  • 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
  • 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
  • 其他节点： 链表中其他的节点；

 例： 一个存储 {1,2,3} 的完整链表结构如图所示：

完整的链表示意图

头结点好处：

  • 便于首元结点的处理

    首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;

  • 便于空表和非空表的统一处理

    无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

  • 头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值

 特别注意： 链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。


2.3.2单链表

2.3.1.1 链表初始化

创建一个链表需要做如下工作：

  • 声明一个头指针（如果有必要，可以声明一个头节点）；
  • 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；

一般来说，我们所谓的初始化单链表一般指的是申请结点的空间，同时对一个结点辅以空值(NULL)


代码实现：

1
2
3
4
5
6
7
8
9
10
11
// 初始化链表
linklist *listinit()
{
    linklist * p;								// 创建头结点
    p = (linklist*)malloc(sizeof(linklist));	// 开辟空间
    if(p == NULL)					//开辟失败，返回-1
    {
        return -1;
    }
    p->next = NULL;					// 指针指向空
}




2.3.1.2 建立单链表

建立单链表的两种方法：头插法建表和尾插法建表。
（两者并无本质上的不同，都是利用指针指向下一个结点元素的方式进行逐个创建，只不过使用头插入法最终得到的结果是逆序的。）

2.3.1.2.1 头插入法

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。

过程特点：

  • 开始链表的头指针head指向空;
  • 然后每增加一个结点,头指针head指向新增加的结点地址
  • 同时新增结点的指针域指向原链表头指针。

头插法创建单链表过程

​ 头插法创建单链表过程


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 用头插入法建立单链表（有头结点）
linklist *CreatList1()
{
    linklist *head;
    head = (linklist*)malloc(sizeof(linklist));	// 申请头结点空间
    head ->next = NULL;							// 初始化一个空链表
    
    char ch = getchar();			// ch为链表数据域中的数据
    while(ch != '#')	// 当不是结束符时，就增加节点
    {
        linklist *p;
        p = (linklist*)malloc(sizeof(linklist));	// 申请新的结点
        p ->data = ch;								// 将输入的值放在数据域中
        p ->next = head ->next						// 将新结点指向原首元结点
        head -> next = p;    						// 头结点指向新结点
        ch = getchar();								// 输入下一个结点的值
    }  
    
    return (head);				// 返回头指针
}


2.3.1.2.2 尾插入法

尾插法建表时按照节点的顺序逐渐将节点插入到链表的尾部，实现步骤如下：

  • 链表的头结点head指向空，然后头head始终指向第1个节点的地址。
  • 新增节点的指针总是指向空，
  • 原链表中的最后一个节点的指针总是指向新增的节点。

尾插法创建单链表过程

​ 尾插法创建单链表过程

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 用尾插入法建立单链表(有头结点)
linklist *CreatList2()
{
    linklist *head;
    head = (linklist*)malloc(sizeof(linklist));	// 申请头结点空间
    head ->next = NULL;							// 初始化一个空链表
    
    linklist *e;								// 尾指针
    e = head;									// e开始时指向头节点，之后指向尾节点
    
    char ch = getchar();			// ch为链表数据域中的数据
    while(ch != '#')	// 当不是结束符时，就增加节点
    {
        linklist *p;
        p = (linklist*)malloc(sizeof(linklist));	// 申请新的结点
        p ->data =ch;								// 结点数据域赋值
        e ->next = p; 						// 新节点插入表尾Head-->|1|-->|2|-->NULL
        e = p;								// 尾指针e指向新的表尾
        ch = getchar();	
    }
    e -> next = NULL;
    return(head);
}


2.3.1.3 单链表基本操作
2.3.1.3.1 遍历单链表

遍历单链表，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可。

1️⃣按序号查找

在链表中,如果知道结点的序号,并不能像顺序表那样直接通过序号访问到结点,而必须从链表的头指针开始,经过各结点的指针域,逐个结点进行搜索,直到搜索到指定序号结点为止

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
  * @brief     	遍历寻找特定序号的结点
  * @param[in]  head ： 指向链表的头结点
  * @param[in]	i    :  所查找结点的序号
  * @retval    返回所查结点的值，如未找到返回空
  * @attention  none
  */
linklist *ListFine1(linkedList *head , int i)
{
       linklist *p; int j = 1; 			// 定义指向当前结点的结点p ； 计数器j
       p = head -> next;
       while (j < i && p ->next != NULL)// 小于i标号的数都得过一遍
       {
           p = p -> next;
           j++;    						// 已查找的结点数
       }
       if ( j == i) return(p);
       else return(NULL);    
}


2️⃣按值查找

用于在链表中查找给定结点值的结点存储地址

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
  * @brief     	遍历寻找特定值的结点
  * @param[in]  head ： 指向链表的头结点
  * @param[in]	e    :  所查找结点的值
  * @param[in]  *i	 ： 结点序号的指针变量，用于返回已查找到的结点的序号
  * @retval    返回所查结点的储存地址，未找到返回空
  * @attention  none
  */
linklist *ListFine2(linkedList *head , datatype e, int *i)
{
    linklist *p;			// 定义结点p总是指向当前搜索的结点
    p = head ->next;		// p指向第1个结点	
    *i = 1;     			// 记录查找节点的序号
    while ( p != NULL)		// 遍历所有结点
    {
    	if( p->data != e)   //在循环中判断是不是对应的节点
      	{
          p = p->next;
          * i = * i + 1;
        }else break;		// 找到结点，退出循环
    } 
    return(p);
}



2.3.1.3.2 插入元素

向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：

  • 插入到链表的头部（头节点之后），作为首元节点；
  • 插入到链表中间的某个位置；
  • 插入到链表的最末端，作为链表中最后一个数据元素；

链表插入新元素步骤：

  • 将新结点的 next 指针指向插入位置后的结点；
  • 将插入位置前结点的 next 指针指向插入结点；

例： 在链表 {1,2,3,4} 的基础上分别实现在头部、中间部位、尾部插入新元素 5

链表中插入元素的 3 种情况示意图


 注意： 链表插入元素的操作必须是先步骤 1，再步骤 2；反之，若先执行步骤 2，除非再添加一个指针，作为插入位置后续链表的头指针，否则会导致插入位置后的这部分链表丢失，无法再实现步骤 1。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
  * @brief     	在特定位置插入元素
  * @param[in]  head ： 指向链表的头结点
  * @param[in]	elem :  新的数据元素
  * @param[in]  add	 ： 要插入的位置
  * @retval    返回插入后的链表头结点
  * @attention  none
  */
linklist *List_Insert(linklist *head , int elem , int add)
{
    linklist *temp = head;  //temp 用于指向搜索的节点
    
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
        if (temp == NULL) 
        {
            printf("插入位置无效\n");
            return head;
        }
    }
    
    // 创建插入结点c
     linklist *c = (linklist*)malloc(sizeof(linklist)); 			// 分配空间
     c -> data = elem;				// 写入新数据
     c -> next = temp -> next;		// 将待插入节点连接其后继节点
     temp->next = c;				// 将待插入的节点连接其前趋节点
    
    return head
}


2.3.1.3.3 删除元素

从链表中删除指定数据元素时，需要进行以下 2 步操作：

  • 将结点从链表中摘下来;
  • 手动释放掉结点，回收被结点占用的存储空间;

链表删除元素示意图


代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
  * @brief     	在特定位置删除元素
  * @param[in]  head ： 指向链表的头结点
  * @param[in]  add	 ： 要删除结点的序号
  * @retval    返回插入后的链表头结点
  * @attention  none
  */
linklist *LinkDelete(linklist *head,int add)
{
    linklist * temp = head;		//temp 用于指向搜索的节点
    /*遍历到被删除结点的上一个结点*/
    for(int i = 1; i < add; i++)
    {
        temp = temp->next;			// 向后查找
        if (temp->next == NULL) 	// 找不到该结点序号
        {
            printf("没有该结点\n");
            return head;
        }        
    }
    linklist * del = temp->next;	//单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next;	//删除某个结点的方法就是更改前一个结点的指针域（del->next）
    free(del);					    //手动释放该结点，防止内存泄漏
    
    return head;
}


2.3.3 静态链表

2.3.3.1 静态链表概念

静态链表的优点和不足：

  • 优点

    • 高效的查找操作（顺序表）
    • 高效的删除、插入操作（链表）

  • 不足

    • 需要提前申请内存，不能动态增加链表容量
    • 维护两条链表，一条保存已使用的节点，一条保存未使用的节点
    • 失去顺序存储结构随机存取的特性

使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。

在这里插入图片描述


例： 使用静态链表存储 {1,2,3}:

  • 创建一个足够大的数组，假设大小为 6
  • 接着，在将数据存放到数组中时，给各个数据元素配备一个整形变量，此变量用于指明各个元素的直接后继元素所在数组中的位置下标

静态链表存储数据

​ 静态链表储存数据

通常，静态链表会将第一个数据元素放到数组下标为 1 的位置（a[1]）中。

如上图所示：

  • 从 a[1] 存储的数据元素 1 开始，通过存储的游标变量 3，就可以在 a[3] 中找到元素 1 的直接后继元素 2；
  • 同样，通过元素 a[3] 存储的游标变量 5，可以在 a[5] 中找到元素 2 的直接后继元素 3，这样的循环过程直到某元素的游标变量为 0 截止（因为 a[0] 默认不存储数据元素）。


2.3.3.2 数据表与备用表

静态链表需要维护两条链路：

  • 一条是维护已使用的节点链路（有效数据链路），称为数据表。

  • 一条是维护未使用的节点链路（数据元素为空的备用链路），称为备用表。

    对于备用表，元素节点的游标存储的是下一空节点的地址。


 注意： 为了简化链表维护过程，一般是使用带头结点的静态链表。


维护静态链表的两个表：

  • 通常我们会使用头尾元素节点作为两个表的头结点。
  • 元素第首节点作为备用表的头结点，元素末尾节点作为有效数据表的节点。
    • 这样的好处是，空表从首节点开始变量，有效数据表从末尾节点开始遍历；
    • 插入数据时只需访问首节点即可快速获取空闲链表地址。


静态链表空表特点：

  • 备用链表节点游标值存储下一空闲节点的数组下标，如图所示灰色区域就是空闲节点
  • 备用表最后节点游标值为0，如上图中的“a6”节点
  • 数据表头指针游标值为0

在这里插入图片描述

​ 静态链表空表


静态链表非空表特点：

  • 数据表头指针游标为值为第一个有效节点
  • 最后一个有效数据节点游标值为0，如“a2”节点

在这里插入图片描述

注意： 备用链表表头通常是使用首节点；有效数据链表表头可以使用任意节点，为了方便管理，一般使用末尾节点或者第二个节点。



2.3.3.3 静态链表创建
2.3.3.3.1 静态链表结点

用静态结构体数组实现的链表，其中元素节点是一个结构体变量，包含了数据域（data）和游标（cur）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 静态链表节点 */
typedef struct _static_link_list_node
{
  	int data;			// 数据域
	int cur;			// 游标
}list_node_type_t;

/* 链表数据，包括长度和各个结点信息等 */
typedef struct _static_link_list
{
	int capacity;				// 容积
  	list_node_type_t *node;		// 各结点信息
}static_link_list_t;



2.3.3.3.2 静态链表创建

静态链表创建，一般是创建一个空的链表，这里我们创建一个带头节点的空静态链表。这里通过malloc申请一块连续内存作为静态链表存储空间。

注意：

  • 多申请两个节点作为备用表和数据表头节点，不存储有效数据
  • 备用表节点游标赋值
  • 备用表最后节点游标值为0
  • 数据表头节点游标值为0

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
  * @brief     	创建静态链表
  * @param[in]  capacity ： 表长度（不包括2个头结点）
  * @retval    返回创建完成的静态链表
  * @attention  none
  */
static_link_list_t *create_static_link_list(int capacity)
{
	static_link_list_t *list = NULL;
	int i = 0;
    
	// 构造一个空的顺序表，动态申请存储空间
	if (capacity >= 0)
    {
        list = (static_link_list_t*)malloc(sizeof(static_link_list_t) + 
											sizeof(list_node_type_t) * (capacity+2));   /* 多申请2节点作头节点 */
    }
    
	if (list != NULL)	// 创建成功
	{
		list->capacity = capacity;
		list->node = (list_node_type_t*)(list+1);//指向分配的数组空间的地址(首地址储存容积)
		for (i=0; i<capacity+2; i++)
		{
			list->node[i].data = 0;		/* 备用表节点数据赋值 */
			list->node[i].cur = i+1;	/* 将每个数组分量链接到一起 */
		}
		list->node[capacity].cur = 0;	/* 备用表最后一个节点游标值为0 */
		list->node[capacity+1].cur = 0;	/* 数据表头节点游标值为0 */
	}

	return list;					/* 返回创建后的静态链表
}


2.3.3.4 静态链表基本操作
2.3.3.4.1 静态链表的清空与销毁
  • 静态链表清空指的是删除链表有效元素节点，释放节点内存空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
  * @brief     	清空静态链表
  * @param[in]  list ： 被清空的静态链表
  * @retval    清空成功返回0
  * @attention  none
  */
int clear_static_link_list(static_link_list_t *list)
{
	int i = 0;
	
	if (list==NULL)
	{
		return 0;
	}
    if (get_static_link_list_occupy(list) == 0)		// 有效结点为0（即为空表）
	{
		return 0;
	}
	for (i=0; i<list->capacity+2; i++)		// 遍历整个链表
	{
		list->node[i].data = 0;
		list->node[i].cur = i+1;
	}
	list->node[list->capacity].cur = 0;			/* 备用表最后一个节点游标值为0 */
	list->node[list->capacity+1].cur = 0;		/* 数据表头节点游标值为0 */
	return 0;
}

  • 静态链表销毁指的是删除所有节点，包括头结点，并释放节点内存空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
  * @brief     	销毁静态链表
  * @param[in]  list ： 被销毁的静态链表
  * @retval    清空成功返回0
  * @attention  none
  */
int destory_static_link_list(static_link_list_t *list)
{
	static_link_list_t *p = NULL;
	
	if (list==NULL)
	{
		return 0;
	}
	free(list);
	list = NULL;
	return 0;
}


2.3.3.4.2 静态链表查找

静态链表的查找方式有两种：

  • 根据元素节点索引号（数组下标）
  • 根据节点数据元素值查找
  • 这两种方式都需要从链表头开始遍历链表，直至查找到指定节点。

注意： 对于元素值查找，只适用于链表中存储的元素值都是唯一的情况，否则只能使用节点索引号查找。


例： 假设需查找“a3”节点，遍历过程如下：

  • 首先根据头节点游标值1找到a1
  • 根据节点a1游标值2找到a2
  • 根据节点a2游标值3找到a3

image-20220825235146696


代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
  * @brief     	静态链表查找
  * @param[in]  list ： 被查找的静态链表
  * @param[in]  pos  :  被查元素索引值（数组下标）
  * @param[in]  rnode:	记录被查找索引值的结点 对应的数据域和游标内容
  * @retval     成功返回0 失败返回-1
  * @attention  none
  */
int get_static_link_list_node(static_link_list_t *list, int pos, list_node_type_t *rnode)  
{
	int index,i;						// index 为结点索引值， i为游标值
	list_node_type_t *p = NULL;
    
	if ((list == NULL)||(pos<1))		// 被查链表不存在 或 索引号不合法
	{
		return -1;
	}
	if (get_static_link_list_occupy(list) == 0)	// 静态链表有效结点为0 （即是空表）
	{
		return -1;
	}
    
	index = (list->capacity+2) - 1;		// 获取数据表头结点的索引号（数组下标），即最后一个结点
    
    // 遍历数组 找到对应结点的前一结点的位置（index为前一结点位置）
	for (i=1; i<pos; i++)
	{
		index = list->node[index].cur;	
	}
	i = list->node[index].cur;         // 被查结点的位置
	rnode->data = list->node[i].data;  // 记录被查元素的数据域
	rnode->cur = list->node[i].cur;	   // 记录被查元素的游标
	return 0;	
}


2.3.3.4.3 静态链表插入

静态链表插入 时间复杂度为O(1) 插入操作首先需遍历查找到目标位置的前一节点，大体步骤如下：

【1】申请存储节点，从备用表获取一个空闲节点空间并赋数据值

【2】遍历查找到插入位置前一节点

【3】插入节点，插入位置前一节点游标赋值给待插入节点游标

【4】更改游标关系，待插入节点数组下标赋值给插入位置前一节点游标


例： 在“a2”的位置插入一个数据值为d的有效节点。（插入后数据表为 d0—>d—>d1）

image-20220819222817737

​ 插入后数据表


代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
  * @brief     	静态链表pos位置插入value
  * @param[in]  list ： 被查找的静态链表
  * @param[in]  value:  插入元素的数据
  * @param[in]  pos  :  插入元素索引值（数组下标）
  * @retval     成功返回0，失败返回-1
  * @attention  none
  */
int insert_static_link_list_node(static_link_list_t *list, int value, int pos)
{
	int findex,iindex,i,j,k;
	
	if(pos<1 || (pos>list->capacity))   // 可用索引值为（1 ~ capacity） 
	{
		return -1;						// 索引号不合法 返回-1
	}
    
	findex = get_static_link_list_free_index(list);   /* 获取备用链表可用索引号 */
	if (findex <= 0)
	{
		return -1;	/* 链表已满 */
	}
    
	iindex = (list->capacity+2) - 1;			// 数据表头结点索引号（数组下标）
  
    // 遍历数组 找到插入结点的前一结点位置（iindex为前一结点位置）
	for (i=1; i<pos; i++)
	{
		iindex = list->node[iindex].cur; 
	}
    
	list->node[findex].data = value;			// 将value赋予从备用表找到的空闲结点
	list->node[findex].cur = list->node[iindex].cur; // 将待插入节点连接其后继节点（即将插入位置前一节点游标赋值给待插入节点游标）
	list->node[iindex].cur = findex;   // 将待插入的节点连接其前趋节点（即将待插入节点数组下标赋值给插入位置前一节点游标）

	return 0;
}

静态链表的插入操作与单链表一样，也是需查找到插入目标位置的前一节点。这也是单向链表的特性，双向链表则可以直接操作插入目标位置。




2.3.3.4.4 静态链表删除

静态链表删除时间复杂度为O(1)。静态链表删除与插入是一个相反的的过程，删除操作首先需遍历查找到目标位置的前一节点，大体步骤如下：

【1】遍历查找到插入位置前一节点

【2】删除节点，插入位置节点游标值赋给前一节点游标

【3】标记为空闲节点，备用表头结点游标值赋给插入位置节点游标

【4】更改备用头结点，插入位置节点索引号（数组下标）值赋给备用表头结点游标


例： 删除“a2”节点数据 (删除后数据表为 d0—>d2)


image-20220819231754544

​ 删除后数据表


代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
  * @brief     	静态链表pos位置删除元素
  * @param[in]  list ： 被操作的静态链表
  * @param[in]  pos  :  删除元素索引号（数组下标）
  * @retval     成功返回0，失败返回-1
  * @attention  none
  */
int delete_static_link_list_node(static_link_list_t *list, int pos)
{
	int i,j,index;
	list_node_type_t node;       
	
	if (list==NULL)				// 链表不存在
	{
		return -1;
	}
    
    /* 删除位置超出范围 */
	if (pos<1 || (pos>=get_static_link_list_occupy(list)))	// 位置大于有效结点数
	{
		return -1;   
	}

	index = (list->capacity+2) - 1;              // 数据表头结点索引号（数组下标）
    
    /* 遍历数组 找到删除结点的前一结点位置（index为前一结点位置）*/
	for (i=1; i<pos; i++)
	{
		index = list->node[index].cur;
	}
	
	j = list->node[index].cur;     				// 获取目标位置 
	list->node[index].cur = list->node[j].cur;	// 删除节点，删除位置节点游标值赋给前一节点游标
	
	/* 设置备用链表 */
	list->node[j].cur = list->node[0].cur; // 标记为空闲节点，备用表头结点游标值赋给插入位置节点游标（即把后续空闲结点索引号，赋给删除结点游标）
	list->node[0].cur = j;				   // 更改备用头结点，删除位置节点索引号（数组下标）值赋给备用表头结点游标
	
	return 0;
}


2.3.3.5 其他操作
2.3.3.5.1 获取备用链表可用索引号

只需访问首节点即可快速获取空闲链表地址 （空闲结点的索引号储存在备用表头结点的 游标中）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * @brief     	获取备用链表可用索引号
  * @param[in]  list ： 被操作的静态链表
  * @retval     成功返回可用结点索引号，失败返回-1
  * @attention  none
  */
int get_static_link_list_free_index(static_link_list_t *list)
{
	int i;
	/* 链表不存在 */
	if (list==NULL)
	{
		return -1;
	}
	
	i = list->node[0].cur;			// 获取备用表头结点的游标值（即空闲结点索引号）
    /* 链表未满 */
	if (i>0)
	{
		list->node[0].cur = list->node[i].cur;		// 备用表头结点的游标值 指向 下一个空闲结点索引号
	}
	return i;
}


2.3.3.5.2 获取有效结点数

最后一个有效结点的游标值为0，遍历链表直到游标值为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
  * @brief     	获取静态链表有效节点数，不包括头节点
  * @param[in]  list ： 被操作的静态链表
  * @retval     成功返回有效结点数
  * @attention  none
  */
int get_static_link_list_occupy(static_link_list_t *list)
{
	int i = 0;
	int j = 0;

	i = list->node[list->capacity+2-1].cur;		// 获取数据表头结点游标值（即第一个元素node[1]的索引号）
	
    /*  获取有效结点个数（j为有效结点个数） */
    while (i > 0)		// 不是最后一个有效结点
	{
		j++;
		i = list->node[i].cur;
	}
	return j;
}


2.3.3.5.3 输出链表有效数据

输出链表有效数据，即按数组下标输出数组的内容。

大概思路与获取有效结点数类似，也是遍历链表直到游标值为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
  * @brief     	打印有效结点
  * @param[in]  list ： 被操作的静态链表
  * @retval     none
  * @attention  none
  */
void printf_static_link_list_data_node(static_link_list_t *list)
{
	int index = 0;

	index = (list->capacity+2) - 1;					// 数据表头结点索引号（数组下标）
	printf("[head,%d] ", list->node[index].cur);	// 打印数据表头结点的信息
	while (list->node[index].cur > 0)
	{
		index = list->node[index].cur;
		printf("[%d, %d] ", list->node[index].data, list->node[index].cur);
	}
	printf("\n");
}


2.3.3.6 总结实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define SLINK_LIST_SIZE 10   // 有效数据容积（即数组长度，不包括头结点）

int main(int argc, char *argv[]) 
{
	static_link_list_t *linklist = NULL;
	static_link_list_t *ptemp;
	list_node_type_t  node;
	int elem = 0;
	int i;
	
	/* 创建静态链表 */
	linklist = create_static_link_list(SLINK_LIST_SIZE);	

	/* 插入操作 */
	insert_static_link_list_node(linklist, 1, 1);			// 在node[1]位置插入“1”
	insert_static_link_list_node(linklist, 2, 2);			// 同理插入其他值
	insert_static_link_list_node(linklist, 3, 1);
	insert_static_link_list_node(linklist, 5, 1);			// 最后数组结果{5,3,1,2}

	printf("输出静态链表全部结点\n");
	printf_static_link_list_all_node(linklist);
	printf("静态链表有效结点数:[%d]\n", get_static_link_list_occupy(linklist));
	printf("输出静态链表有效结点： \n");
	printf_static_link_list_data_node(linklist);

	/* 查找操作 */
	get_static_link_list_node(linklist, 2, &node);
	printf("node[2]的数据为： , value:[%d, %d]\n", node.data, node.cur);

	/* 删除操作 */
	printf("删除结点node[2]\n");
	delete_static_link_list_node(linklist, 2);

	printf("输出静态链表全部结点:\n");
	printf_static_link_list_all_node(linklist);
	printf("静态链表有效结点数 :[%d]\n", get_static_link_list_occupy(linklist));
	printf("输出静态链表有效结点：\n");
	printf_static_link_list_data_node(linklist);
	destory_static_link_list(linklist);	/* 销毁静态链表 */
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//输出静态链表全部结点:
node0[0, 5] node1[1, 2] node2[2, 0] node3[3, 1] node4[5, 3] node5[0, 6] node6[0, 7] node7[0, 8] node8[0, 9] node9[0, 10] node10[0, 0] node11[0, 4] 

静态链表有效结点数:[4]    

//输出静态链表有效结点：
[head,4] [5, 3] [3, 1] [1, 2] [2, 0] 

node[2]的数据为：, value:[3, 1]

删除结点node[2]

// 输出静态链表全部结点:
node0[0, 3] node1[1, 2] node2[2, 0] node3[3, 5] node4[5, 1] node5[0, 6] node6[0, 7] node7[0, 8] node8[0, 9] node9[0, 10] node10[0, 0] node11[0, 4] 
静态链表有效结点数:[3]


2.3.4 双向链表

2.3.4.1 双向链表概念

双向链表的概念： 在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表。

它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。


双链表示意图

​ 双向链表示意图

一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。



2.3.4.2 与单链表的异同

相同点：

  • 都属于链表一种

  • 插入、删除时间复杂度都是O(1)

  • 支持链式访问

  • 支持带头节点和不带头节点


不同点：

  • 组成结构不同，双向链表带前驱和后继指针；单链表只有后继指针
  • 访问方向不同，双向链表支持前驱、后继访问；单链表支持后继访问
  • 访问效率不同， 单链表节点无法直接访问其前驱节点，逆序访问单链表时效率低
  • 空表判断方式不同
1
2
3
4
5
6
7
8
9
10
11
/* 带头节点双向链表判断空表 */
if ((head->font==NULL) && (head->next==NULL))
{
    /* todo */
}

/* 不带头节点双向链表判断空表，与单链表判断方式相同 */
if (head->font==NULL)
{
    /* todo */
}


2.3.4.3 双向链表创建
2.3.4.3.1 双向链表结点

双向链表中各节点包含以下 3 部分信息：

  • 指针域：用于指向当前节点的直接前驱节点；
  • 数据域：用于存储数据元素。
  • 指针域：用于指向当前节点的直接后继节点；

双向链表的节点构成


代码实现：

1
2
3
4
5
6
7
typedef int datatype;			// 结点的数据类型定义为datatype，方便更改，此处为int
struct _doubly_link_list
{
  	datatype data;					 // 有效数据 
	struct _doubly_link_list *pnext; // 后继指针域 
	struct _doubly_link_list *pfront;// 前驱指针域 
};


2.3.4.3.2 双向链表创建

与单链表不同，双链表创建过程中，每创建一个新节点，都要与其前驱节点建立两次联系，分别是：

  • 将新节点的 pfront指针指向直接前驱节点；
  • 将直接前驱节点的 pnext 指针指向新节点；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
  * @brief     	创建双向链表结点
  * @param[in]  none
  * @retval     返回创建成功的链表
  * @attention  none
  */
doubly_link_list_t* create_doubly_link_list(void)
{
	doubly_link_list_t* head = NULL;
    
    head = (doubly_link_list_t*)malloc(sizeof(doubly_link_list_t));
    
    if (head != NULL)
    {
        head->data=0;			/* 头结数据域为空 */
		head->pnext = NULL;		
		head->pfont = NULL;
    }
    return head;
}


2.3.4.4 双向链表基本操作
2.3.4.4.1 双向链表清空与销毁
  • 链表清空指的是删除链表有效节点，释放节点内存空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * @brief     	双向链表清空操作
  * @param[in]  被操作的链表
  * @retval     none
  * @attention  none
  */
int clear_doubly_link_list(doubly_link_list_t *list)
{
	doubly_link_list_t *p = NULL;
	doubly_link_list_t *q = NULL;
	
	p = list->pnext;
    /*  遍历链表删除有效结点 */
	while(p != NULL)		// 不是空表
	{
		q = p->pnext;
		free(p);
		p = q;
	}
	list->pnext=NULL;

	return 0;
}

  • 链表销毁指的是删除所有节点，包括头结点，并释放节点内存空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
  * @brief     	双向链表清空操作
  * @param[in]  被操作的链表
  * @retval     none
  * @attention  none
  */
int destory_doubly_link_list(doubly_link_list_t *list)
{
	doubly_link_list_t *p = NULL;
	while(list != NULL)		// 还存在结点
	{
		p = list->pnext;
		free(list);
		list = p;
	}
	list = NULL;

	return 0;
}


2.3.4.4.2 双向链表查找

双向链表与单链表的查找方式一样，有两种方式:

  • 根据元素索引号查找
  • 根据节点数据元素值查找

这两种方式都需要从链表头开始遍历链表，直至查找到指定节点。(对于元素值查找，只适用于链表中存储的元素值都是唯一的情况，否则只能使用节点索引号查找。)


例如： 查找一个带头节点双向链表的第二个节点，可以通过索节点引号[1]查找或者通过唯一的节点数据元素[a1]查找。

image-20220821000645158



代码实现:

1️⃣ 通过节点索引号查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
  * @brief     	双向链表通过节点索引号查找
  * @param[in]  list : 被操作的链表
  * @param[in]  pos  : 查找结点索引号
  * @retval     返回所查结点地址
  * @attention  none
  */
doubly_link_list_t *get_doubly_link_list_node_pos(doubly_link_list_t *list, int pos)  
{
	doubly_link_list_t *p = NULL;
	/* 链表不存在或插入位置不合法  */
	if ((list==NULL) || (pos<0))
	{
		return NULL;
	}

	p = list;
    /* 遍历索引号 */
	while(pos>=0)
	{
		p = p->pnext;
		if (p == NULL)
		{
			break;
		}
		pos--;
	}
	return p;
}

2️⃣ 通过节点数据元素查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
  * @brief     	双向链表通过节点数据元素值查找
  * @param[in]  list : 被操作的链表
  * @param[in]  elem : 结点数据元素
  * @retval     返回所查结点地址
  * @attention  none
  */
doubly_link_list_t *get_doubly_link_list_node_elem(doubly_link_list_t *list, int elem)  
{
	doubly_link_list_t *p = NULL;
	/* 链表不存在或是空表 */
	if ((list==NULL) || (list->pnext==NULL))
	{
		return NULL;
	}

	p = list->pnext;	// 首元结点
    /* 遍历元素值 */
	while(p!=NULL)
	{
		if (p->data == elem)
		{
			return p;
		}
		p = p->pnext;
	}
	return NULL;
}


2.3.4.4.3 双向链表插入

双向链表插入时间复杂度为O(1)。与单链表的插入类型一样，分为三种:

  • 表头插入，无需遍历链表
  • 表尾插入，无需遍历链表
  • 表中间插入，需遍历链表，即是查找操作

双向链表插入步骤与单链表稍有不同，主要区别是需处理前驱指针的指向：

【1】查找到插入位置节点的前一节点，可通过节点索引号或者唯一节点数据元素查找

【2】申请待插入新节点内存并赋值

【3】新节点后继指针域指向插入位置的原节点，如下图第1步

【4】新节点前驱指针域指向插入位置原节点的前一节点，如下图第2步

【5】插入位置原节点的前驱指针域指向新节点，如下图第3步

【6】插入位置原节点的前一节点的后继节指针域指向新节点，如下图第4步


在这里插入图片描述


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
  * @brief     	双向链表在pos位置插入value
  * @param[in]  list  :被操作的链表
  * @param[in]	value :数据域的值
  * @param[in]  pos	  :插入位置
  * @retval     成功返回0; 失败返回-1
  * @attention  none
  */
int insert_doubly_link_list_node_pos(doubly_link_list_t *list, int value, int pos)  
{
	doubly_link_list_t *p = NULL;				// 插入位置前一结点
	doubly_link_list_t *node = NULL;			// 新增插入结点

    /* 链表不存在或插入位置不合法 */
	if ((list==NULL) || (pos<0))			
	{
		return -1;
	}
    
	/*  获取前驱结点 */
	if (pos == 0)	// 表头插入
	{
		p = list;	// 插入第一个节点位置
	}
    else
    {
    	p = get_doubly_link_list_node_pos(list, pos-1);			// 获取插入位置的前一结点
    }   
    /* 前驱结点不存在 */
	if (p == NULL)
	{
		return -1;
	}
    
	node = (doubly_link_list_t*)malloc(sizeof(doubly_link_list_t));  // 申请待插入新节点内存
    /* 申请失败 */
	if (node == NULL)
	{
		return -1;
	}
    
	node->data = value;					// 新结点数据域赋值
	node->pnext = p->pnext;				// 新结点连接其后继结点 (即后继指针域指向插入位置的原节点)
	node->pfront = p;					// 新结点连接其前驱节点 (即新节点前驱指针域 指向 插入位置原节点的前一节点)
   
    /* 非表尾插入 */
	if (p->pnext != NULL)
	{
		p->pnext->pfront = node;		// 插入位置原节点 连接 新结点(即插入位置原节点的前驱指针域指向新节点)
	}	
	p->pnext = node;					// 插入位置原节点的前驱结点 连接 新结点 (即插入位置原节点的前一节点的后继节指针域指向新节点)
	
    return 0;
}


2.3.4.4.4 双向链表删除

双向链表删除时间复杂度为O(1)。双向链表删除与插入是一个相反的的过程，删除类型有三种:

  • 表头删除
  • 表尾删除
  • 表中间删除

(这三种类型,实现方式一样)


双向链表删除步骤与单链表稍有不同，主要区别是需处理前驱指针的指向：

【1】查找到删除位置的节点，可通过节点索引号或者唯一节点数据元素查找

【2】删除位置节点的前一节点的后继指针域 , 指向其后一节点，如下图第1步

【3】删除位置节点的后一节点的前驱指针域 , 指向其前一节点，如下图第2步

【4】释放删除节点内存

在这里插入图片描述


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
  * @brief     	双向链表在pos位置删除一个结点
  * @param[in]  list  :被操作的链表
  * @param[in]  pos	  :删除位置
  * @retval     成功返回0; 失败返回-1
  * @attention  none
  */
int delete_doubly_link_list_node_pos(doubly_link_list_t *list, int pos) 
{
	doubly_link_list_t *p = NULL;
	/* 链表不存在或插入位置不合法 */
	if ((list==NULL) || (pos<0))
	{
		return -1;
	}
    /* 检测是否是空表  */
	if (check_doubly_link_list_empty(list))
	{
		return -1;
	}
	p = get_doubly_link_list_node_pos(list, pos);	/* 获取删除位置的结点 */
	if (p!=NULL)
	{
		p->pfront->pnext = p->pnext;				// 删除位置 节点的前一节点的后继指针域,指向后一结点
		/* 非表尾删除 */
        if (p->pnext != NULL)
		{
			p->pnext->pfront = p->pfront;			// 删除位置节点的后一节点的前驱指针域,指向前一结点
		}
		free(p);									// 释放结点内存
	}
	else
	{
		return -1;
	}
    return 0 ;
}


2.3.4.5 其他简单操作
2.3.4.5.1 检查是否空表

带头节点的双向链表空表，头节点的前驱指针域和后继指针域都指向NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 检查是否是空表 */
bool check_doubly_link_list_empty(doubly_link_list_t *list)
{
	if (list == NULL)
	{
		return true;
	}
	if ((list->pfront==NULL) && (list->pnext==NULL))	
	{
		return true;
	}
	else
	{
		return false;
	}
}


2.3.4.5.2 获取链表长度

遍历链表获取有效结点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 获取链表长度 */
int get_doubly_link_list_capacity(doubly_link_list_t *list)
{
	doubly_link_list_t *p = NULL;
	int size = 0;
	
	if (list == NULL)
	{
		return 0;
	}
	p = list->pnext;
	while(p != NULL)
	{
		size++;
		p = p->pnext;
	}
	return size;
}


2.3.4.6 总结实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int main(int argc, char *argv[]) 
{
	doubly_link_list_t *linklist = NULL;
	doubly_link_list_t *ptemp;
	int elem = 0;
	int i;
	
	/* 创建双向链表 */
	linklist = create_doubly_link_list();	

	/* 插入操作 */
	insert_doubly_link_list_node_pos(linklist, 0, 0);
	insert_doubly_link_list_node_pos(linklist, 1, 1);
	insert_doubly_link_list_node_pos(linklist, 3, 0);
	insert_doubly_link_list_node_pos(linklist, 5, 1);

	printf("双向链表长度:[%d]\n", get_doubly_link_list_capacity(linklist));
    /* 打印所有结点 */
	for(i=0; i<get_doubly_link_list_capacity(linklist); i++)
    {
        ptemp = get_doubly_link_list_node_pos(linklist, i);			// 查找操作
        printf("双向链表结点 node[%d]=%d\n", i, ptemp->data);
    }

	/* 删除操作 */
	printf("删除双向链表 node[2]\n");
	delete_doubly_link_list_node_pos(linklist, 2);
	printf("双向链表长度:[%d]\n", get_doubly_link_list_capacity(linklist));
    /* 打印所有结点 */
	for(i=0; i<get_doubly_link_list_capacity(linklist); i++)
    {
        ptemp = get_doubly_link_list_node_pos(linklist, i);		// 查找操作
        printf("doubly link list node[%d]=%d\n", i, ptemp->data);
    }
	destory_doubly_link_list(linklist);	// 销毁双向链表 
}

运行结果:

1
2
3
4
5
6
7
8
9
10
双向链表长度:[4]
双向链表结点 node[0]=3
双向链表结点 node[1]=5
双向链表结点 node[2]=0
双向链表结点 node[3]=1
删除双向链表结点 node[2]
双向链表长度:[3]
双向链表结点 node[0]=3
双向链表结点t node[1]=5
双向链表结点 node[2]=1


2.3.5 循环链表

首尾相接的链表称为循环链表

  • 单链表和双向链表都支持循环形式，分别称为循环单链表和循环双向链表。
  • 循环链表同样地支持带头节点和不带头节点的形式
  • 对于带头结点的循环链表，单链表的末尾节点后继指针域指向的是头节点；(形成一个链路环)
  • 双链表的末尾节点后继指针域指向头节点，头节点前驱指针域指向末尾节点。(形成两个链路环)

在这里插入图片描述

​ 带头结点的循环单链表

在这里插入图片描述

​ 带头结点的循环双链表


循环链表优点:

  • 从表中任一结点出发均可找到表中其他结点，遍历灵活性提高
  • 可以无需增加存储空间，重复利用空间，类似于“队列”

循环链表的创建、插入、删除、查找、清空、销毁等操作，与非循环链表基本一致。只是在空表检查上的差异以及注意头节点和末尾节点的指针域处理。



2.3.5.1 循环链表空表判断

  • 对于不带头节点的循环链表，判断方式与非循环链表一致，都是头指针指向NULL。

    1
    2
    3
    4
    if (head == NULL)
    {
    	/* 不带头结点空表判断 */
    }

  • 带头节点的循环链表，由于头、尾相连，检查链表是为空表的条件是前驱和后继指针域指向是否相等。


image-20220821225057395


1
2
3
4
5
6
7
8
9
10
11
/* 循环单链表空表判断 */
if (head == head->pnext)
{
    /* 带头结点空表判断 */
}

/* 循环双向链表空表判断 */
if (head->pfront == head->pnext)
{
    /* 带头结点空表判断 */
}


2.3.5.2 循环链表创建

以双向链表为例 , 循环双向链表创建，一般是创建一个空的链表，这里我们创建一个带头节点的空链表。循环双向链表的空表，前驱和后继指针域都指向头结点本身。


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
  * @brief     	创建双向循环链表头结点
  * @param[in]  none
  * @retval     返回创建成功的带头结点的空链表
  * @attention  none
  */
doubly_link_list_t* create_doubly_link_list(void)
{
	doubly_link_list_t* head = NULL;
    
    head = (doubly_link_list_t*)malloc(sizeof(doubly_link_list_t));
    
    if (head != NULL)
    {
        head->data=0;			// 头结数据域为空
		head->pnext = head;		// 后继指针域都指向头结点本身(非循环链表指向NULL)
		head->pfront = head;	// 前驱指针域都指向头结点本身(非循环链表指向NULL)
    }
    return head;
}


2.3.5.3 双向循环链表基本操作
2.3.5.3.1 双向循环链表的清空与销毁

循环双向链表清空与销毁与普通双向链表操作一致，都是遍历整个链表，只是遍历的结束条件不同。


1️⃣ 链表清空指的是删除链表有效元素节点，释放节点内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
  * @brief     	双向循环链表清空操作
  * @param[in]  被操作的链表
  * @retval     none
  * @attention  none
  */
int clear_doubly_link_list(doubly_link_list_t *list)
{
	doubly_link_list_t *p = NULL;
	doubly_link_list_t *q = NULL;
	/* 链表不存在 */
	if (list==NULL)
	{
		return 0;
	}
    /* 检查是否是空表  */
	if (check_doubly_link_list_empty(list))
	{
		return 0;
	}
    
	p = list->pnext;
	while(p != list)	// 遍历结束条件
	{
		q = p->pnext;
		free(p);
		p = q;
	}
	list->pnext=NULL;

	return 0;
}

2️⃣ 链表销毁指的是删除所有节点，包括头结点，并释放节点内存空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
  * @brief     	双向链表销毁操作
  * @param[in]  被操作的链表
  * @retval     none
  * @attention  none
  */
int destory_doubly_link_list(doubly_link_list_t *list)
{
	doubly_link_list_t *p = NULL;
	doubly_link_list_t *q = NULL;
	/* 链表不存在 */
	if (list==NULL)
	{
		return 0;
	}
    /* 检查是否是空表  */
	if (check_doubly_link_list_empty(list))
	{
		free(list);
		list = NULL;
		return 0;
	}
	p = list->pnext;
	while(p != list)	// 遍历结束条件
	{
		q = p->pnext;
		free(p);
		p = q;
	}
	free(list);			// 释放头结点内存
	list = NULL;		

	return 0;
}


2.3.5.3.2 双向循环链表的查找

循环双向链表与普通双向链表的查找方式一样，有两种方式:

  • 根据元素索引号查找
  • 根据节点数据元素值查找

这两种方式都需要从链表头开始遍历链表，直至查找到指定节点。(对于元素值查找，只适用于链表中存储的元素值都是唯一的情况，否则只能使用节点索引号查找。)


例如： 查找一个带头节点双向链表的第二个节点，可以通过索节点引号[1]查找或者通过唯一的节点数据元素[a1]查找。

image-20220821000645158



代码实现:

1️⃣ 通过节点索引号查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
  * @brief     	循环双向链表通过节点索引号查找
  * @param[in]  list : 被操作的链表
  * @param[in]  pos  : 查找结点索引号
  * @retval     返回所查结点地址
  * @attention  none
  */
doubly_link_list_t *get_doubly_link_list_node_pos(doubly_link_list_t *list, int pos)  
{
	doubly_link_list_t *p = NULL;
	/* 链表不存在或插入位置不合法  */
	if ((list==NULL) || (pos<0))
	{
		return NULL;
	}
	/*  判断是否空表 */
	if (check_doubly_link_list_empty(list))
	{
		return NULL;
	}
	
	p = list;
	while(pos>=0)
	{
		p = p->pnext;
		if (p == list)  // 重新回到头结点(这里与普通双向链表不同)
		{
			p = NULL;	// 未找到目标节点 
			break;
		}
		pos--;
	}
	return p;
}

2️⃣ 通过节点数据元素查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
  * @brief     	循环双向链表通过节点数据元素值查找
  * @param[in]  list : 被操作的链表
  * @param[in]  elem : 结点数据元素
  * @retval     返回所查结点地址
  * @attention  none
  */
doubly_link_list_t *get_doubly_link_list_node_elem(doubly_link_list_t *list, int elem)  
{
	doubly_link_list_t *p = NULL;
	/* 链表不存在 */
	if (list==NULL)
	{
		return NULL;
	}
	/* 判断是否空表 */
	if (check_doubly_link_list_empty(list))
	{
		return NULL;
	}
	
	p = list->pnext;		// 首元结点
	while(p!=list)
	{
		if (p->data == elem)
		{
			return p;
		}
		p = p->pnext;
	}
	return NULL;
}


2.3.5.3.3 双向循环链表插入

循环双向链表插入时间复杂度为O(1)。与普通双向链表的插入类型一样，分为三种:

  • 表头插入，无需遍历链表
  • 表尾插入，无需遍历链表
  • 表中间插入，需遍历链表，即是查找操作

因为此时链表是一个”环“, 因此，表头、表尾、表中间插入操作实现方法都是都相同。

【1】查找到插入位置节点的前一节点，可通过节点索引号或者唯一节点数据元素查找

【2】申请待插入新节点内存并赋值

【3】新节点后继指针域指向插入位置的原节点，如下图第1步

【4】新节点前驱指针域指向插入位置原节点的前一节点，如下图第2步

【5】插入位置原节点的前驱指针域指向新节点，如下图第3步

【6】插入位置原节点的前一节点的后继节指针域指向新节点，如下图第4步


在这里插入图片描述


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
  * @brief     	循环双向链表在pos位置插入value
  * @param[in]  list  :被操作的链表
  * @param[in]	value :数据域的值
  * @param[in]  pos	  :插入位置
  * @retval     成功返回0; 失败返回-1
  * @attention  none
  */
int insert_doubly_link_list_node_pos(doubly_link_list_t *list, int value, int pos)  
{
	doubly_link_list_t *p = NULL;
	doubly_link_list_t *node = NULL;
	doubly_link_list_t  *temp;
     /* 链表不存在或插入位置不合法 */
	if ((list==NULL) || (pos<0))
	{
		return -1;
	}
    
	/*  获取前驱结点 */
	if (pos == 0)
	{
		p = list;	// 插入第一个节点位置 
	}
    else
    {
    	p = get_doubly_link_list_node_pos(list, pos-1);	// 获取插入位置的前一结点 
    }
    
	/* 空表，插入第一个节点位置  */
	if (p == NULL)
	{
		p = list;
	}
    
	node = (doubly_link_list_t*)malloc(sizeof(doubly_link_list_t));  // 申请待插入新节点内存
     /* 申请失败 */
	if (node == NULL)
	{
		return -1;
	}
	node->data = value;					// 新结点数据域赋值
	node->pnext = p->pnext;				// 新结点连接其后继结点 (即后继指针域指向插入位置的原节点)
	node->pfront = p;					// 新结点连接其前驱节点 (即新节点前驱指针域 指向 插入位置原节点的前一节点)
	p->pnext->pfront = node;			// 插入位置原节点 连接 新结点(即插入位置原节点的前驱指针域指向新节点)
	p->pnext = node;					// 插入位置原节点的前驱结点 连接 新结点 (即插入位置原节点的前一节点的后继节指针域指向新节点)

    return 0;
}


2.3.5.3.4 双向循环链表删除

循环双向链表删除时间复杂度为O(1)。双向链表删除与插入是一个相反的的过程，删除类型有三种:

  • 表头删除
  • 表尾删除
  • 表中间删除

(这三种类型,实现方式一样)


循环双向链表删除步骤与普通双向链表操作步骤一样，因为此时链表是一个”环“。因此，表头、表尾、表中间删除操作实现方法都是都相同的。

【1】查找到删除位置的节点，可通过节点索引号或者唯一节点数据元素查找

【2】删除位置节点的前一节点的后继指针域指向其后一节点，如下图第1步

【3】删除位置节点的后一节点的前驱指针域指向其前一节点，如下图第2步

【4】释放删除节点内存


在这里插入图片描述


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
  * @brief     	双向循环链表在pos位置删除一个结点
  * @param[in]  list  :被操作的链表
  * @param[in]  pos	  :删除位置
  * @retval     成功返回0; 失败返回-1
  * @attention  none
  */
int delete_doubly_link_list_node_pos(doubly_link_list_t *list, int pos) 
{
	doubly_link_list_t *p = NULL;
	/* 链表不存在或插入位置不合法 */
	if ((list==NULL) || (pos<0))
	{
		return -1;
	}
    /* 检测是否是空表  */
	if (check_doubly_link_list_empty(list))
	{
		return -1;
	}
	p = get_doubly_link_list_node_pos(list, pos);	// 获取删除位置的结点 
	if (p!=NULL)
	{
		p->pfront->pnext = p->pnext;				// 删除位置 节点的前一节点的后继指针域,指向后一结点
		p->pnext->pfront = p->pfront;				// 删除位置节点的后一节点的前驱指针域,指向前一结点
		free(p);									// 释放结点内存
	}
	else
	{
		return -1;
	}
}


2.3.5.4 总结实例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int main(int argc, char *argv[]) 
{
	doubly_link_list_t *linklist = NULL;
	doubly_link_list_t *ptemp;
	int elem = 0;
	int i;
	
	/* 创建双向链表 */
	linklist = create_doubly_link_list();	

	/* 插入操作 */
	insert_doubly_link_list_node_pos(linklist, 0, 0);
	insert_doubly_link_list_node_pos(linklist, 1, 1);
	insert_doubly_link_list_node_pos(linklist, 3, 0);
	insert_doubly_link_list_node_pos(linklist, 5, 1);

	printf("双向链表长度:[%d]\n", get_doubly_link_list_capacity(linklist));
    /* 打印所有结点 */
	for(i=0; i<get_doubly_link_list_capacity(linklist); i++)
    {
        ptemp = get_doubly_link_list_node_pos(linklist, i);			// 查找操作
        printf("双向链表结点 node[%d]=%d\n", i, ptemp->data);
    }

	/* 删除操作 */
	printf("删除双向链表 node[2]\n");
	delete_doubly_link_list_node_pos(linklist, 2);
	printf("双向链表长度:[%d]\n", get_doubly_link_list_capacity(linklist));
    /* 打印所有结点 */
	for(i=0; i<get_doubly_link_list_capacity(linklist); i++)
    {
        ptemp = get_doubly_link_list_node_pos(linklist, i);		// 查找操作
        printf("doubly link list node[%d]=%d\n", i, ptemp->data);
    }
	destory_doubly_link_list(linklist);	// 销毁双向链表 
}

运行结果:

1
2
3
4
5
6
7
8
9
10
双向链表长度:[4]
双向链表结点 node[0]=3
双向链表结点 node[1]=5
双向链表结点 node[2]=0
双向链表结点 node[3]=1
删除双向链表结点 node[2]
双向链表长度:[3]
双向链表结点 node[0]=3
双向链表结点t node[1]=5
双向链表结点 node[2]=1

2.3.5.5 循环单链表实现

循环单链表只是循环双向链表中的一个“正向环路” ; 以下为循环单链表实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
typedef struct _link_list
{
  	int data;
	struct _link_list *pnext;/* 下一节点 */
}link_list_t;

link_list_t* create_link_list(void)
{
	link_list_t* head = NULL;
    
    head = (link_list_t*)malloc(sizeof(link_list_t));
    
    if (head != NULL)
    {
        head->data=0;		/* 头结数据域为空 */
		head->pnext = head;
    }

    return head;
}

bool check_link_list_empty(link_list_t *list)
{
	if (list == NULL)
	{
		return true;
	}
	if (list->pnext == list)	
	{
		return true;
	}
	else
	{
		return false;
	}
}

int clear_link_list(link_list_t *list)
{
	link_list_t *p = NULL;
	link_list_t *q = NULL;
	
	if (list==NULL)
	{
		return 0;
	}
	if (check_link_list_empty(list))
	{
		return 0;
	}
		
	p = list->pnext;
	while(p != list)
	{
		q = p->pnext;
		free(p);
		p = q;
	}
	list->pnext=NULL;

	return 0;
}


int destory_link_list(link_list_t *list)
{
	link_list_t *p = NULL;
	link_list_t *q = NULL;
	
	if (list==NULL)
	{
		return 0;
	}
	if (check_link_list_empty(list))
	{
		free(list);
		list = NULL;
		return 0;
	}
	p = list->pnext;
	while(p != list)
	{
		q = p->pnext;
		free(p);
		p = q;
	}
	free(list);
	list = NULL;

	return 0;
}

int get_link_list_capacity(link_list_t *list)
{
	link_list_t *p = NULL;
	int size = 0;
	
	if (list == NULL)
	{
		return 0;
	}
	
	if (check_link_list_empty(list))
	{
		return 0;
	}
	
	p = list->pnext;
	while(p != list)
	{
		size++;
		p = p->pnext;
	}
	return size;
}

link_list_t *get_link_list_node_pos(link_list_t *list, int pos)  
{
	link_list_t *p = NULL;
	
	if ((list==NULL) || (pos<0))
	{
		return NULL;
	}

	if (check_link_list_empty(list))
	{
		return NULL;
	}
	
	p = list;
	while(pos>=0)
	{
		p = p->pnext;
		if (p == list)
		{
			p = NULL;
			break;
		}
		pos--;
	}
	return p;
}

link_list_t *get_link_list_node_elem_per(link_list_t *list, int elem)  
{
	link_list_t *p = NULL;
	
	if (list==NULL)
	{
		return NULL;
	}
	if (check_link_list_empty(list))
	{
		return NULL;
	}
	
	p = list->pnext;
	while(p!=list)
	{
		if (p->pnext->data == elem)
		{
			return p;
		}
		p = p->pnext;
	}
	return NULL;
}

int insert_link_list_node_pos(link_list_t *list, int value, int pos)  
{
	link_list_t *p = NULL;
	link_list_t *node = NULL;

	if ((list==NULL) || (pos<0))
	{
		return -1;
	}

	if (pos == 0)
	{
		p = list;	/* 插入第一个节点位置 */
	}
    else
    {
    	p = get_link_list_node_pos(list, pos-1);	/* 获取插入位置的前一节点 */
    }

	if (p == NULL)
	{/* 空表，插入第一个节点位置  */
		p = list;
	}
	node = (link_list_t*)malloc(sizeof(link_list_t));
	if (node == NULL)
	{
		return -1;
	}
	node->data = value;
	node->pnext = p->pnext;
	p->pnext = node;

    return 0;
}

int insert_link_list_node_elem(link_list_t *list, int value, int elem)  
{
	link_list_t *p = NULL;
	link_list_t *node = NULL;

	if (list==NULL)
	{
		return -1;
	}

    p = get_link_list_node_elem_per(list, elem);	/* 获取插入位置的前一节点 */

	if (p == NULL)
	{/* 空表，插入第一个节点位置  */
		p = list;
	}
	node = malloc(sizeof(link_list_t));
	if (node == NULL)
	{
		return -1;
	}
	node->data = value;
	node->pnext = p->pnext;
	p->pnext = node;
    return 0;
}

int delete_link_list_node_pos(link_list_t *list, int pos) 
{
	link_list_t *p = NULL;
	link_list_t *node = NULL;

	if ((list==NULL) || (pos<0))
	{
		return -1;
	}
	if (pos == 0)
	{
		p = list;	/* 删除第一个节点 */
	}
	else	
	{
		p = get_link_list_node_pos(list, pos-1);	/* 获取删除位置的前一节点 */
	}
	if ((p!=NULL) && (p->pnext!=list))
	{
		node = p->pnext;
		p->pnext = node->pnext;
		free(node);
	}
	else
	{
		return -1;
	}
}

int delete_link_list_node_elem(link_list_t *list, int elem) 
{
	link_list_t *p = NULL;
	link_list_t *node = NULL;

	if (list==NULL)
	{
		return -1;
	}
	p = get_link_list_node_elem_per(list, elem);	/* 获取删除位置的前一节点 */
	if ((p!=NULL) && (p->pnext!=list))
	{
		node = p->pnext;
		p->pnext = node->pnext;
		free(node);
	}
	else
	{
		return -1;
	}
}


int main(int argc, char *argv[]) 
{
	link_list_t *linklist = NULL;
	link_list_t *ptemp;
	int elem = 0;
	int i;
	
	/* 创建循环单链表 */
	linklist = create_link_list();	

	/* 插入操作 */
	insert_link_list_node_pos(linklist, 0, 0);
	insert_link_list_node_pos(linklist, 1, 1);
	insert_link_list_node_pos(linklist, 3, 0);
	insert_link_list_node_pos(linklist, 5, 1);

	printf("link list capacity:[%d]\n", get_link_list_capacity(linklist));
	for(i=0; i<get_link_list_capacity(linklist); i++)
    {/* 查找操作 */
        ptemp = get_link_list_node_pos(linklist, i);
        printf("link list node[%d]=%d\n", i, ptemp->data);
    }

	/* 删除操作 */
	printf("delete link list node[2]\n");
	delete_link_list_node_pos(linklist, 2);
	printf("link list capacity:[%d]\n", get_link_list_capacity(linklist));
	for(i=0; i<get_link_list_capacity(linklist); i++)
    {/* 查找操作 */
        ptemp = get_link_list_node_pos(linklist, i);
        printf("link list node[%d]=%d\n", i, ptemp->data);
    }
	destory_link_list(linklist);	/* 销毁循环单链表 */
}


2.4 几类线性表总结

2.4.1 各类线性表特点

  • 顺序表，高效的查找操作
  • 单链表，高效的插入/删除操作
  • 双向链表，双向遍历，遍历效率高
  • 循环链表，任一节点开始，可以遍历整个链表，遍历灵活性高
  • 静态链表，综合了顺序表和链表特点，既有高效的查找操作，又能快速增删元素节点


2.4.2 线性表特点比较


存储地址 存储空间 存储密度 存取结构 空间长度 查找 删除/插入
顺序表 连续 静态 =1 顺序/随机 定长 O(1) O(n)
单链表 非连续 动态 <1 顺序 动态增加 O(n) O(1)
双向链表 非连续 动态 <1 顺序 动态增加 O(n) O(1)
循环链表 非连续 动态 <1 顺序 动态增加 O(n) O(1)
静态链表 非连续 静态 <1 顺序 定长 O(1) O(1)


2.4.3 线性表适用场景参考


应用场景 线性表选择
固定表长度 顺序表/静态链表
频繁查找操作 顺序表/静态链表
频繁插入/删除操作 链表
复用缓冲队列 循环链表
双向遍历 双向链表
兼顾查找/插入/删除效率 静态链表
约瑟夫环问题 循环链表
LRU 缓存淘汰算法 循环链表


3️⃣ 栈与队列

3.1 栈

3.1.1 栈的概念

栈 是线性表的特例，其具备先进后出 FILO 特性

栈的定义: 栈是一个线性的数据结构，规定这个数据结构只允许在其中一端进行操作，并禁止直接访问除这一端以外的数据。


栈对数据 “存” 和 “取” 的过程有特殊的要求：

  • 栈只能从表的一端存取数据，另一端是封闭的.
  • 在栈中，无论是存数据还是取数据，都必须遵循=="先进后出=="的原则，即最先进栈的元素最后出栈。

栈存储结构示意图


通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素。


例如： 如图所示 , 栈顶元素为元素 4；栈底元素为元素 1。

栈顶和栈底



3.1.2 顺序栈


顺序栈：可以使线性表的顺序存储结构（即数组）实现栈，将之称之为 顺序栈

用数组下标表示的栈顶指针top(相对指针)完成各种操作; top 初始值为 -1，表示栈中没有存储任何数据元素，及栈是"空栈"。一旦有数据元素进栈，则 top 就做 +1 操作；反之，如果数据元素出栈，top 就做 -1 操作。


特点:

  • 顺序栈需要事先确定一个固定的长度（数组长度）
  • 可能存在内存空间浪费问题，但它的优势是存取时定位很方便

3.1.2.1 顺序栈定义

image-20220823202403725


定义方式:

1
2
3
4
5
6
7
typedef int data_t; //定义栈中数据元素的数据类型,此处为int

typedef struct{
  data_t *data; 	//用指针指向栈的存储空间
  int maxlen; 		//当前栈的最大元素大小
  int top;  		//只是栈顶元素位置
}sqstack;

顺序栈创建:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
  * @brief     	顺序栈创建
  * @param[in]  len	  :最大长度
  * @retval     成功返回创建后的栈
  * @attention  none
  */
sqstack * stack_create(int len)
{
       sqstack * s;
    	/* 申请结构体内存 */
       if ((s = (sqstack *)malloc(sizeof(sqstack)))== NULL)
       {
               printf("sqstack 内存分配失败\n");
               return NULL;
       }
    	/* 申请数据域内存(即数组内存) */
       if((s->data = (data_t *)malloc(sizeof(data_t) * len))==NULL)
       {
               printf("数据域内存分配失败\n");
               free(s);
               return NULL;
       }
    	/* 初始化结构体成员 */
       memset(s->data, 0 , len * sizeof(data_t));		// 数据域全部写入0
       s->maxlen = len;									// 初始化长度
       s->top = -1;										// top 初始值为 -1,表示空栈
       return s;
}


3.1.2.2 顺序栈基本操作

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：

  • 向栈中添加元素，此过程被称为 “进栈” （入栈或压栈）；
  • 从栈中提取出指定元素，此过程被称为 “出栈” （或弹栈）；

3.1.2.2.1 顺序栈入栈

入栈操作很简单，只需要先将top加1，然后将元素放入数组即可。特别要注意检查此时栈是否已满。

img


代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * @brief     	顺序栈入栈
  * @param[in]  s	  :被操作的栈
  * @param[in]  value :压栈元素
  * @retval     成功返回0;失败返回-1
  * @attention  none
  */
int stack_push(sqstack * s, data_t value){
       if(s == NULL)
       {
               printf("stack is null");
               return -1;
       }
    	/* 判断栈是否已满 */
        if(s->top == s->maxlen - 1)
        {  
                printf("stack is full");
                return -1;
        }
       s->top++;					// 栈顶top +1
       s->data[s->top] = value;		// 元素放入数组
       return 0;
}


3.1.2.2.2 顺序栈出栈

出栈操作: 先访问元素，然后将top减1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * @brief     	顺序栈出栈
  * @param[in]  s	  :被操作的栈
  * @param[in]  *value :返回栈顶元素
  * @retval     成功返回0;失败返回-1
  * @attention  none
  */
int stack_pop(sqstack * s , data_t *value)
{
	if (s == NULL)
    {
		printf("stack is null\n");
		return -1;
	}
    /* 判断栈是否为空 */
    if(stack_empty(s))
    {
        return -1
    }
	s->top--;						// top减1
    *value = s->data[s->top];		// 返回栈顶元素
	return 0;		
}


3.1.2.3 其他操作
3.1.2.3.1 访问栈顶元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
  * @brief     	顺序栈返回栈顶元素
  * @param[in]  s	  :被操作的栈
  * @param[in]  *value :返回栈顶元素
  * @retval     成功返回0;失败返回-1
  * @attention  none
  */
int stack_top(sqstack * s , data_t *value)
{
   	if (s == NULL)
    {
		printf("stack is null\n");
		return -1;
	}
     /* 判断栈是否为空 */
    if(stack_empty(s))
    {
        return -1
    }
    *value = s->data[s->top];		// 返回栈顶元素
    return 0;
}


3.1.2.3.2 判断栈是否满
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
  * @brief     	判断栈是否满
  * @param[in]  s	  :被操作的栈
  * @retval     已满返回1;未满返回0
  * @attention  none
  */
int stack_full(sqstack *s)
{
     if (s == NULL)
    {
		printf("stack is null\n");
		return -1;
	}
    return (s->top == s->maxlen - 1 ? 1 : 0);
}

3.1.2.3.3 判断栈是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
  * @brief     	判断栈是否空
  * @param[in]  s	  :被操作的栈
  * @retval     空返回1;非空返回0
  * @attention  none
  */
int stack_empty(sqstack *s)
{
     if (s == NULL)
    {
		printf("stack is null\n");
		return -1;
	}
   return (s->top == -1 ? 1 : 0);
}


3.1.3 链式栈

链栈: 可以使用单链表结构实现栈， 将之称之为 链栈

链式栈可以动态扩容，基本没有长度限制（受限于内存）。注意:在入栈以及出栈的时候需要申请或者释放内存。


特点:

  • 要求每个元素都要配套一个指向下个结点的指针域
  • 增大了内存开销，但好处是栈的长度无限

3.1.3.1 链栈定义

插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针。

img


栈结构定义:

1
2
3
4
5
6
7
typedef int data_t;			//定义栈中数据元素的数据类型,此处为int

typedef struct StackInfo		// 结点类型定义
{
  data_t value;					// 记录栈顶位置
  struct StackInfo *next;		// 指向栈的下一个元素
}StackInfo_st;

链栈创建:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
  * @brief     	顺序栈创建
  * @param[in]  none
  * @retval     成功返回创建后的栈
  * @attention  none
  */
StackInfo_st *stack_create(void)
{
        StackInfo_st *s = malloc(sizeof(StackInfo_st));		// 分配头结点内存;
        
    	/* 分配失败 */
        if(s == NULL)
        {
                printf("malloc failed");
                return NULL;
        }
    	/* 初始化 */
        s->value = 0;			
        s->next = NULL;		// stack-next为栈顶指针
        return s;   
}


3.1.3.2 链栈基本操作
3.1.3.2.1 链栈入栈

入栈只需要为新的元素申请内存空间，并将栈顶指针指向新的节点即可。

image-20220823212616414

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
  * @brief     	链栈入栈
  * @param[in]  s	  :头结点
  * @param[in]  value :压栈元素
  * @retval     成功返回0;失败返回-1
  * @attention  none
  */
int stack_push(StackInfo_st * s, data_t value)
{
    StackInfo_st *temp = malloc(sizeof(StackInfo_st));			// 新的元素结点
    if(NULL == temp)
    {
     	printf("malloc failed\n");
      	return -1;
    }
     
    temp->value = value;
    temp->next = s->next;			// 将新的节点添加s->next前，使得s->next永远指向栈顶
    s->next = temp;
}


3.1.3.2.2 链栈出栈

出栈时，将栈顶指针指向下下个节点，返回元素值，并释放栈顶指针下个节点的内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
  * @brief     	链栈出栈
  * @param[in]  s	  :头结点
  * @param[in]  value :出栈元素
  * @retval     成功返回0;失败返回-1
  * @attention  none
  */
int stack_pop(StackInfo_st *s,data_t *value)
{
    /*首先判断栈是否为空*/
    if(stack_is_empty(s))
    {
        return -1;
    }
    
    /*找出栈顶元素*/
    *value = s->next->value;				// 出栈元素
    StackInfo_st *temp = s->next;				
    s->next = s->next->next;				// 栈顶指针指向下下个元素
    	
    /*释放栈顶节点内存*/
    free(temp);
    temp = NULL;
    
    return 0;
}


3.1.3.3 其他操作
3.1.3.3.1 访问栈顶元素

访问栈顶元素只需要返回栈顶指针指向节点的元素值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
  * @brief     	链栈访问栈顶元素
  * @param[in]  s	  :头结点
  * @param[in]  value :用于返回栈顶元素
  * @retval     成功返回0;失败返回-1
  * @attention  none
  */
int stack_top(StackInfo_st *s,data_t *value)
{
    /*首先判断栈是否为空*/
    if(stack_is_empty(s))
    {
        return -1;
    }
    *value = s->next->value;
    return 0;
}


3.1.3.3.2 判断栈是否为空

判断栈顶指针是否为空即可。

1
2
3
4
5
6
7
8
9
10
/*判断栈是否为空，空返回1，未空返回0*/
int stack_is_empty(StackInfo_st *s)
{
   if(s == NULL)
   {
      return -1;
   }
    /*栈顶指针为空，则栈为空*/
   return (s->next == NULL ? 1 : 0);
}



3.2 队列

3.2.1 队列的概念


定义: 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表


队列存储结构


特点:

  • 队列 是一种 先进先出（FIFO） 的线性表
  • 对头：允许删除的一端称为对头
  • 队尾： 允许插入的一端称为队尾
  • 空队: 当线性表中没有元素时，成为空队

队列的常规操作:

  • 创建队列
  • 清空队列
  • 判断队列空
  • 判断队列满
  • 入队
  • 出队

队列储存结构:

  • 顺序队列：在顺序表的基础上实现的队列结构；
  • 链队列：在链表的基础上实现的队列结构；

两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。


队列实现方式:

  • 静态数组，容量固定，操作简便，效率高

  • 动态数组，容量可自定义，操作简便，因为涉及内存的申请与释放，因此实现比静态数组稍微复杂一点点

  • 链表，容量理论上只受限于内存，实现也较为复杂



3.2.2 顺序队列

顺序队列实现思路:

  • 当有数据元素进队列时，对应的实现操作是将其存储在指针 rear(尾指针) 指向的数组位置，然后 rear+1；
  • 当需要队头元素出队时，仅需做 front+1 (头指针) 操作

image-20220825214743180

顺序队列在数据不断地进队出队过程中，在顺序表中的位置不断后移; 导致空间浪费或数组溢出等问题.


因此： 通常在设计队列时,会使用更为优秀的结构—-循环队列



3.2.2.1 循环队列

循环队列实现思路:

  • 就是给定我们队列的大小范围;
  • 在原有队列的基础上，只要队列的后方满了，就从这个队列的前面开始进行插入，以达到重复利用空间的效果

image-20220825215900928

特别注意：

  • 其不是一个真正的环，循环队列依旧是单线性的。

3.2.2.2 循环队列结构

image-20220825220906512

  • data表示一个数据域
  • rear代表尾指针，入队时移动。
  • front代表头指针，出队时移动。

循环队列结构:

1
2
3
4
5
6
7
8
9
10
typedef int DataType;
#define MAX_SIZE 10;
/*定义队列结构*/
typedef struct QueueInfo
{
    int front; 			//队头位置
    int rear;  			//队尾位置
    DataType queueArr[MAX_SIZE]; //队列数组

}QueueInfo;

3.2.2.3 循环队列操作
3.2.2.3.1 循环队列创建

初始化循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
  * @brief         	循环队列的初始化
  * @param[in]      pfifo: 将循环缓冲区初始化
  * @param[in]      size: 缓冲区的大小
  * @retval         成功返回0
  * @attention
  */
int queue_init(QueueInfo *pfifo,  int size)
{
    if (NULL == pfifo) 
    {
        return -1;
    }

    pfifo->front = 0;
    pfifo->rear = 0;

    return 0;
}


3.2.2.3.2 循环队列入列

记得判断队列是否已满, 同时如果rear超过size,则直接将其从a[0]重新开始存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
  * @brief          循环队列入列
  * @param[in]      queue: 操作队列
  * @param[in]      value: 入列元素
  * @retval         成功返回0
  * @attention
  */
int queue_insert(QueueInfo *queue,DataType value)
{
    /* 判断队列是否满 */
   if(queue_is_full(queue))
   {
       return -1;
   }
    
    queue->rear = (queue->rear + 1) % MAX_SIZE;			// rear超过size,则直接将其从a[0]重新开始存储
    queue->queueArr[queue->rear] = value;				// 入列
    printf("insert %d  to %d\n",value,queue->rear);
    return 0;
}


3.2.2.3.3 循环队列出列

出列判断队列是否为空 , 同时 front指针+1后超过size,则直接将其从a[0]重新开始存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
  * @brief          循环队列出列
  * @param[in]      queue: 操作队列
  * @param[in]      value: 出列元素
  * @retval         成功返回0
  * @attention
  */
int queue_insert(QueueInfo *queue,DataType *value)
{	
    /* 判断队列是否为空 */
    if(queue_is_empty(queue))
   {
       return -1;
   }
    *value = queue->queueArr[queue->front];				// 返回出列元素值
    printf("get  value from front %d  is %d\n",queue->front,*value);
    queue->front = (queue->front + 1) % MAX_SIZE;		// 出列
}


3.2.2.3.4 判断循环队列是否已满

如果rear+1和front重合，则表示数组已满

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
  * @brief           判断循环队列是否已满
  * @param[in]      queue: 操作队列
  * @retval         已满返回1,未满返回0
  * @attention
  */
int queue_is_full(QueueInfo *queue)
{
    if((queue->rear + 1) % MAX_SIZE == queue->front)
    {
        printf("queue is full\n");
        return 1;
    }
    else 
        return 0;
}


3.2.2.3.5 判断循环队列是否为空

如果rear==front 表示队列为空

1
2
3
4
5
6
7
8
9
10
/**
  * @brief           判断循环队列是否为空
  * @param[in]      queue: 操作队列
  * @retval         空返回1,非空返回0
  * @attention
  */
int queue_is_empty(QueueInfo *queue)
{
	return (queue->front == queue->rear ? 1: 0);
}


3.2.2.3.6 使用示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void main(void)
{
   /*队列初始化*/
    QueueInfo queue;
   	memset(&queue,0,sizeof(queue));			// 数组初始化为0
    queue.front = 1;
    queue.rear = 0;
    
        /*入队6个数据，最后两个入队失败*/
    queue_insert(&queue,5);
    queue_insert(&queue,4);
    queue_insert(&queue,3);
    queue_insert(&queue,2);
    queue_insert(&queue,1);
    queue_insert(&queue,0);

    /*出队6个数据，最后两个出队失败*/
    DataType a = 0;
    queue_delete(&queue,&a);
    queue_delete(&queue,&a);
    queue_delete(&queue,&a);
    queue_delete(&queue,&a);
    queue_delete(&queue,&a);
    queue_delete(&queue,&a);
    return 0;
}

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
insert 5  to 1
insert 4  to 2
insert 3  to 3
insert 2  to 4
queue is full
queue is full
get  value from front 1  is 5
get  value from front 2  is 4
get  value from front 3  is 3
get  value from front 4  is 2
queue is empty
queue is empty

3.2.3 队列使用总结


  • 队列的实现相对比栈复杂一些,因为它需要考虑队空和对满的区别，以及考虑数据搬移的性能影响.
  • 一般使用队列都是使用循环队列,同时由于循环对列给定了数据范围的大小，则不需要使用链式的动态创建方法了

使用场景：

  • 一般在嵌入式系统中,环形队列的使用是比较多的
  • 可以用于配合DMA接收串口数据、can的发送队列等
  • 只要是涉及频繁数据收发的都可以用的上

(👇 实现过程可以参这篇文章)

stm32 高效串口收发



最后的话

因为目前个人水平还比较低，平时接触和用到的都些比较基础的，暂时先对平时常用到的进行一个复兴；后续再慢慢重新复习后续内容


参考链接

c语言数据结构

静态链表操作详解及C语言实现

数据结构

【从零开始的嵌入式生活】数据结构4——栈与队列（1）

stm32 高效串口收发

《嵌入式系统软件设计中的数据结构》

-------------已经到底啦！ -------------