• 数据结构记录（一）

    文章目录

    先放一个小技巧，这里vscode是可以进行正则匹配的，可以方便我们处理一些代码移植的问题，正则匹配的使用如下：
    在这里插入图片描述
    另外说明：本文参考

    http://c.biancheng.net/data_structure/

    本文更多的是一个学习记录过程，代码均源自上述链接，非常感谢！

    1、基本概述

    数据存储的目的在于方便后期的使用，使用完之后可以对齐销毁掉，没有必要一直占用内存空间，如果是存储一些常见的变量可以直接进行，但如果存储一些特别的变量，主要是指这些变量之间存在一些关系，这个时候单独存储就无法体现出这种关系了，针对这一类的变量，数据结构中提供专门的树结构来储存这一类数据。

    数据结构包含的存储结构有：

    • 线性表，细分为顺序表，链表，栈和队列；
    • 树结构，包括普通树，二叉树，线索二叉树等；
    • 图存储结构；

    换另一种方式进行分类，可以概括为：逻辑结构和储存结构（又称物理结构）

    2、时间复杂度和空间复杂度

    运用时间复杂度和空间复杂度可以衡量一个算法的运行效率

    • 时间复杂度：表示一个算法所编程序运行时间的多少
    • 空间复杂度：表示一个算法云顶过程中对内存的占用情况

    以下面的代码为例：注释中写明了语句的执行次数：

    for (int i = 0; i < n; i++) // n+1
{
    for (int j = 0; j < m; j++) // n*(m+1)
    {
        num++; // n*m
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    计算这段语句的总次数为： (n+1)+n*(m+1)+nm，简化后得 2nm+2n+1。这里可以近似将mn都认为是一个无穷大的数，这个时候又可以认为m=n，再次简化为： 2*n2+2 *n+1

    这里可以在用高等数学的知识可知这个最终的结果由n2（n的平方来决定），一般用大O法来表示时间复杂度，因此这里就是O（n2）

    几种常用的时间复杂度之间的大小关系如下：

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

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

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

    3、线性表

    1、基本概念

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

    上面说的一串可以有两种方式来实现，分别是数据集中存放和数据分散存放，如下所示：
    在这里插入图片描述
    如上图所示，我们只要把这根线从头到尾拉直，他们就是同样的一串数据。这样将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构（简称线性表）。

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

    2、顺序储存结构和链式储存结构

    上面的两张图还可衍生出顺序储存结构和链式储存结构出来，将数据依次存储在连续的整块物理空间中，这种存储结构称为顺序存储结构（简称顺序表），数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系，这种存储结构称为链式存储结构（简称链表）。

    3、前驱和后继

    在数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。这样排列的元素我们称呼的时候称为，元素前面和元素后面，前驱和后继就是用来描述这些关系的，某一元素前面的称为直接前驱，前面的所有元素为前驱元素，后面的一个元素称为直接后继，后面的所有称为后继元素。

    4、顺序表

    1、基本概念

    顺序表也是描述一对一逻辑关系的数据按照次序连续储存到一整块物理空间的一种描述，不过顺序表要求元素之间是相邻的，就是一整块的内存空间，因此顺序表在储存数据时，会提前申请一块足够大小的物理空间，然后将数据依次存储起来。（本质上就是用数组在存储的）
    在这里插入图片描述
    创建一个顺序表如下所示：
    在这里插入图片描述
    下面来对这个顺序表初始化，如下所示：

    #include "stdio.h"

#define Size 5

typedef struct Table
{
    int *head;  //动态数组
    int length; //记录长度
    int size;   //记录大小
}table;

table initTable()
{
    table t;
    t.head = (int*)malloc(Size*sizeof(int));//申请空间

    if(!t.head)
    {
        printf("初始化失败");
        exit(0);
    }
    t.length = 0;
    t.size = Size;
    return t;
}

void displayTable(table t)
{
    for(int i=0;i<t.length;i++)
    {
        printf("%d ",t.head[i]);
    }
    printf("\n");
}

int main()
{
    table t = initTable();
    //下面向顺序表添加元素
    for(int i = 0;i<Size;i++)
    {
        t.head[i] = i;
        t.length++;
    }
    printf("下面打印链表数据\n");
    displayTable(t);

    return 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    这里重点关注一下顺序表的初始化过程：
    在这里插入图片描述

    之后还添加了顺序表的输出和赋值操作，也都是通过顺序表的一些元素来实现的，之后我们运行结果，可以看到是OK的：
    在这里插入图片描述

    2、顺序表插入元素

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

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

    这些操作的共同之处在于，通过遍历，找到数据元素要插入的位置，然后做如下两步工作：

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

    示例代码如下：

    table addTable(table t, int elem, int add)
{
    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));
        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;
}

    • 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

    插入效果如下：（这里再第三个位置插入100）
    在这里插入图片描述

    3、顺序表删除元素

    删除元素的逻辑为，找到目标元素，然后将其后续的元素整体前移一个位置即可。

    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    4、顺序表查找元素

    示例代码如下：

    //查找函数，其中， elem 表示要查找的数据元素的值
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
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    5、顺序表更改元素

    示例代码如下：

    //更改函数，其中， elem 为要更改的元素， newElem 为新的数据元素
table amendTable(table t, int elem, int newElem)
{
    int add = selectTable(t, elem);
    t.head[add - 1] = newElem; //由于返回的是元素在顺序表中的位置，所以-1 就是该元素在数组中的下标
    return t;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    5、单链表

    1、基本概念

    链表对应之前说的另一种线性结构，链表，别名链式存储结构或单链表，用于存储逻辑关系为 “一对一” 的数据。 与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

    那么链表是如何解决这样一个混乱的情况的，链表会在每个数据元素存储时都配备一个指针，用于指向自己的直接后继元素，因此链表中的每个数据存储都由以下两个部分组成：

    1. 数据元素本身，其所在的区域称为数据域；
    2. 指向直接后继元素的指针，所在的区域称为指针域；
      在这里插入图片描述

    上述就是链表中的一个个节点，链表的排列如下图所示：
    在这里插入图片描述
    创建一个链表如下所示：
    在这里插入图片描述

    2、头节点相关

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

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

    一个储存｛1,2,3｝的完整链表结构如下图所示：
    在这里插入图片描述
    链表中有头结点时，头指针指向头结点，如果没有就指向首元节点。

    3、链表的创建和初始化

    创建一个链表需要：

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

    下面是创建一个无头节点链表的示例：

    link *initLink()
{
    link *p = NULL;                            //创建头指针
    link *temp = (link *)malloc(sizeof(link)); //创建首元节点
    //首元节点先初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp; //头指针指向首元节点
    //从第二个节点开始创建
    for (int i = 2; i < 5; i++)
    {
        //创建一个新节点并初始化
        link *a = (link *)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        //将 temp 节点与新建立的 a 节点建立逻辑关系
        temp->next = a;
        //指针 temp 每次都指向新链表的最后一个节点，其实就是 a 节点，这里写 temp=a 也对
        temp = temp->next;
    }
    //返回建立的节点，只返回头指针 p 即可，通过头指针即可找到整个链表
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    创建一个含有首元节点的链表如下所示：

    link *initLink()
{
    link *p = (link *)malloc(sizeof(link)); //创建一个头结点
    link *temp = p;                         //声明一个指针指向头结点，
    //生成链表
    for (int i = 1; i < 5; i++)
    {
        link *a = (link *)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    下面通过一个打印函数显示链表的内容：

    void display(link *p)
{
    link* temp = p;
    while (temp)
    {
        printf("%d ",temp->elem);
        temp=temp->next;
    }
    printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    打印结果如下：
    在这里插入图片描述

    4、单链表的基本操作

    首先还是先创建一个链表，下面的操作都基于这个链表来进行：

    #include "stdio.h"
#include "stdlib.h"

//声明节点结构
typedef struct Link
{
    int elem;          //存储整形元素
    struct Link *next; //指向直接后继元素的指针
} link;
//创建链表的函数
link *initLink()
{
    link *p = (link *)malloc(sizeof(link)); //创建一个头结点
    link *temp = p;                         //声明一个指针指向头结点，用于遍历链表
    //生成链表
    for (int i = 1; i < 5; i++)
    {
        //创建节点并初始化
        link *a = (link *)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        //建立新节点与直接前驱节点的逻辑关系
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

void display(link *p)
{
    link* temp = p;
    while (temp)
    {
        printf("%d ",temp->elem);
        temp=temp->next;
    }
    printf("\n");
}

int main()
{
    link *p = initLink();
    display(p);
    return 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
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    插入元素

    这里和顺序表一样，要区分插入元素的位置在链表的头部还是中间位置还是在链表的最末端，插入的操作可以概括为：

    1. 将新结点的 next 指针指向插入位置后的结点；
    2. 将插入位置前结点的 next 指针指向插入结点；
    link *insertElem(link *p, int elem, int add)
{
    link *temp = p; //创建临时结点 temp
    //首先找到要插入位置的上一个结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
        if (temp == NULL)
        {
            printf("插入位置无效\n");
            return p;
        }
    }
    //创建插入结点 c
    link *c = (link *)malloc(sizeof(link));
    c->elem = elem;
    //向链表中插入结点
    c->next = temp->next;
    temp->next = c;
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    删除元素

    删除元素就是要注意对不再利用的储存空间及时释放，因此从列表中删除数据元素的操作如下：

    1. 将结点从链表中摘下来;
    2. 手动释放掉结点，回收被结点占用的存储空间;
    temp->next=temp->next->next;

    • 1

    下面是删除的c程序样例：

    link *delElem(link *p, int add)
{
    link *temp = p;
    //遍历到被删除结点的上一个结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
        if (temp->next == NULL)
        {
            printf("没有该结点\n");
            return p;
        }
    }
    link *del = temp->next;        //单独设置一个指针指向被删除结点，以防丢失
    temp->next = temp->next->next; //删除某个结点的方法就是更改前一个结点的指针域
    free(del);                     //手动释放该结点，防止内存泄漏
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    查找元素

    查找元素的一般操作还是从表头遍历表中节点，通过和存储的数据进行比对，直到比对到最末端的UNLL，这个表示比对结束。

    int selectElem(link *p, int elem)
{
    //新建一个指针 t，初始化为头指针 p
    link *t = p;
    int i = 1;
    //由于头节点的存在，因此 while 中的判断为 t->next
    while (t->next)
    {
        t = t->next;
        if (t->elem == elem)
        {
            return i;
        }
        i++;
    }
    //程序执行至此处，表示查找失败
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    更新元素

    和查找元素很像，也是一一进行遍历，不过就是遍历到了之后要对元素进行改写操作

    link *amendElem(link *p, int add, int newElem)
{
    link *temp = p;
    temp = temp->next; //在遍历之前， temp 指向首元结点
    //遍历到待更新结点
    for (int i = 1; i < add; i++)
    {
        temp = temp->next;
    }
    temp->elem = newElem;
    return p;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    5、单链表反转

    这个过程又称反转链表，原来的链表如下所示：
    在这里插入图片描述
    经过反转后，如下所示
    在这里插入图片描述
    具体有以下几种方式来实现：

    1、迭代反转链表

    思想为：从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的
    指针域，另其指向前一个节点。

    图示如下所示：

    初始状态
    在这里插入图片描述
    第一步
    在这里插入图片描述
    第二步
    在这里插入图片描述
    第三步
    在这里插入图片描述
    最终反转结果如下
    在这里插入图片描述
    代码实现如下：

    link *iteration_reverse(link *head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    else
    {
        link *beg = NULL;
        link *mid = head;
        link *end = head->next;
        //一直遍历
        while (1)
        {
            //修改 mid 所指节点的指向
            mid->next = beg;
            //此时判断 end 是否为 NULL，如果成立则退出循环
            if (end == NULL)
            {
                break;
            }
            //整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

    • 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

    2、递归反转链表

    递归每次深入一层，依次将节点2，3，4的指针作为参数参与递归，根据递归出口的判断条件，当函数参数 head 指向的是节点 4 时满足 head->next == NULL，递归过程不再深入，并返回指向节点 4 的指针，这就是反转链表的新头指针。过程如下：

    递归首次退出一层时， new_head 指向的是节点 4 ，而 head 由于退出一层，指向的是节点 3，如下图所示：
    在这里插入图片描述
    执行后将 new_head 的指向继续作为函数的返回值，传给上一层的 new_head
    在这里插入图片描述
    再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 2。在此基础上再次递归，最终将new_head 的指向作为函数返回值，继续传给上一层的 new_head
    在这里插入图片描述
    最后一步
    在这里插入图片描述

    代码如下所示：

    link *recursive_reverse(link *head)
{
    //递归的出口
    if (head == NULL || head->next == NULL) // 空链或只有一个结点，直接返回头指针
    {
        return head;
    }
    else
    {
        //一直递归，找到链表中最后一个节点
        link *new_head = recursive_reverse(head->next);

        //当逐层退出时， new_head 的指向都不变，一直指向原链表中最后一个节点；
        //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。

        //每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
        head->next->next = head;
        head->next = NULL;
        //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
        return new_head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    3、头插法反转链表

    头插法就是指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转，流程如下所示：

    首先创建一个空链表：
    在这里插入图片描述
    将这个链表的头部节点1摘除，并以头部插入的方式将该节点添加到新链表中：
    在这里插入图片描述
    继续这个过程直到最后就完成了一个反转：
    在这里插入图片描述

    最终代码如下：

    link *head_reverse(link *head)
{
    link *new_head = NULL;
    link *temp = NULL;
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    while (head != NULL)
    {
        temp = head;
        //将 temp 从 head 中摘除
        head = head->next;

        //将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    4、就地逆置法反转链表

    从思想上和上面的头插法比较像，区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。

    需要注意在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 beg 和 end）如下图所示：
    在这里插入图片描述
    将 end 所指节点 2 从链表上摘除，然后再添加至当前链表的头部
    在这里插入图片描述
    将 end 指向 beg->next，然后将 end 所指节点 3 从链表摘除，再添加到当前链表的头部
    在这里插入图片描述
    沿着这个过程最终就完成了链表的反转，代码如下：

    link *local_reverse(link *head)
{
    link *beg = NULL;
    link *end = NULL;
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    beg = head;
    end = head->next;
    while (end != NULL)
    {
        //将 end 从链表中摘除
        beg->next = end->next;
        //将 end 移动至链表头
        end->next = head;
        head = end;
        //调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
        end = beg->next;
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    上述运行的结果都是一眼的，这里就不每个都截图了，结果如下：

    int main()
{
    link *p = initLink();
    p = local_reverse(p);
    display(p);
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    运行结果如下：
    在这里插入图片描述

    6、判断两个单链表是否相交

    链表相交是指有公共的节点，这个公共节点的数目可以是一个或者多个，常见的相交方式有以下几种：
    在这里插入图片描述

    一般判断链表是否相交常用的方法为：

    分别遍历链表 1 和链表 2，对于链表 1 中的每个节点，依次和链表 2 中的各节点进行比对，查看它们的存储地址是否相同，如果相同，则表明它们相交；反之，如果链表 1 中各节点的存储地址，和链表 2 中的各个节点都不相同，则表明它们不相交。

    7、顺序表和链表的优缺点概述

    上述两种方式的基本特征如下所示：

    • 顺序表存储数据，需预先申请一整块足够大的存储空间，然后将数据按照次序逐一存储，数据之间紧密贴合，不留一丝空隙；
    • 链表的存储方式与顺序表截然相反，什么时候存储数据，什么时候才申请存储空间，数据之间的逻辑关系依靠每个数据元素携带的指针维持；

    下面从不同的角度对顺序表和链表进行对比：

    • 开辟空间的方式
      顺序表存储数据实行的是 “一次开辟，永久使用”，即存储数据之前先开辟好足够的存储空间，空间一旦开辟后期无法改变大小（使用动态数组的情况除外）。
      而链表则不同，链表存储数据时一次只开辟存储一个节点的物理空间，如果后期需要还可以再申请。因此，若只从开辟空间方式的角度去考虑，当存储数据的个数无法提前确定，又或是物理空间使用紧张以致无法一次性申请到足够大小的空间时，使用链表更有助于问题的解决。

    • 空间利用率
      顺序表的空间利用率明显高于链表，因为顺序表申请内存的方式会造成很多目录，这样一定程度上造成了空间的浪费，同时每个元素需要带一个指针，等于多申请了内存空间，因此空间利用率不高。

    • 时间复杂度
      元素操作比较少的时候适合使用顺序表。这是因为，顺序表中存储的元素可以使用数组下标直接访问，无需遍历整个表，因此使用顺序表访问元素的时间复杂度为 O(1)；而在链表中访问数据元素，需要从表头依次遍历，直到找到指定节点，花费的时间复杂度为 O(n);
      元素操作比较多的时候适合使用链表。链表中数据元素之间的逻辑关系靠的是节点之间的指针，当需要在链表中某处插入或删除节点时，只需改变相应节点的指针指向即可，无需大量移动元素，因此链表中插入、删除或移动数据所耗费的时间复杂度为 O(1)；而顺序表中，插入、删除和移动数据可能会牵涉到大量元素的整体移动， 因此时间复杂度至少为 O(n);

    8、储存结构和存取结构

    所谓存储结构，指的是数据在内存中真实的存储状态，具体可分为 2 类，即顺序存储结构和链式存储结构。而存取结构，指的是存取数据的方式，具体也可以分为 2 类，分别为顺序存取结构和随机存取结构。

    下面对前面说的顺序表和线性表的概念进一步概括：线性表的顺序存储结构是随机存取结构，而不是顺序存取结构；线性表的链式存储结构，又可以称为顺序存取结构，而不是随机存取结构。

    9、静态链表及其创建

    1、基本创建

    静态链表，也是线性存储结构的一种，它兼顾了顺序表和链表的优点于一身，可以看做是顺序表和链表的升级版。使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。

    创建一个静态链表需要包含两部分信息：

    • 数据域：用于存储数据元素的值；
    • 游标：其实就是数组下标，表示直接后继元素所在数组中的位置；

    代码如下：

    typedef struct
{
    int data; //数据域
    int cur;  //游标
} component;

    • 1
    • 2
    • 3
    • 4
    • 5

    静态链表中，除了数据本身通过游标组成的链表外，还需要有一条连接各个空闲位置的链表，称为备用链表。备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。 也就是说，静态链表使用数组申请的物理空间中，存有两个链表，一条连接数据，另一条连接数组中未使用的空间。

    通常，备用链表的表头位于数组下标为 a[0] 的位置，而数据链表的表头位于数组下标为 a[1]的位置。

    创建一个静态链表的完整代码如下：

    #include 

#define maxSize 6
typedef struct
{
    int data;
    int cur;
} component;
//将结构体数组中所有分量链接到备用链表中
void reserveArr(component *array);
//初始化静态链表
int initArr(component *array);
//输出函数
void displayArr(component *array, int body);
//从备用链表上摘下空闲节点的函数
int mallocArr(component *array);

int main()
{
    component array[maxSize];
    int body = initArr(array);
    printf("静态链表为：\n");
    displayArr(array, body);
    return 0;
}
//创建备用链表
void reserveArr(component *array)
{
    for (int i = 0; i < maxSize; i++)
    {
        array[i].cur = i + 1; //将每个数组分量链接到一起
        array[i].data = -1;
    }
    array[maxSize - 1].cur = 0; //链表最后一个结点的游标值为0
}
//提取分配空间
int mallocArr(component *array)
{
    //若备用链表非空，则返回分配的结点下标，否则返回 0（当分配最后一个结点时，该结点的游标值为 0）
    int i = array[0].cur;
    if (array[0].cur)
    {
        array[0].cur = array[i].cur;
    }
    return i;
}
//初始化静态链表
int initArr(component *array)
{
    reserveArr(array);
    int body = mallocArr(array);
    //声明一个变量，把它当指针使，指向链表的最后的一个结点，因为链表为空，所以和头结点重合
    int tempBody = body;
    for (int i = 1; i < 4; i++)
    {
        int j = mallocArr(array); //从备用链表中拿出空闲的分量
        array[tempBody].cur = j;  //将申请的空闲分量链接在链表的最后一个结点后面
        array[j].data = i;        //给新申请的分量的数据域初始化
        tempBody = j;             //将指向链表最后一个结点的指针后移
    }
    array[tempBody].cur = 0; //新的链表最后一个结点的指针设置为0
    return body;
}
void displayArr(component *array, int body)
{
    int tempBody = body; // tempBody准备做遍历使用
    while (array[tempBody].cur)
    {
        printf("%d,%d ", array[tempBody].data, array[tempBody].cur);
        tempBody = array[tempBody].cur;
    }
    printf("%d,%d\n", array[tempBody].data, array[tempBody].cur);
}

    • 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

    2、添加元素

    下面的几种对静态链表的操作都是基于上述模版进行的，首先是添加元素，一般是先从备用链表上摘除一个节点用于储存元素，找到表中添加位置的前一个节点将元素的游标赋值给新元素，然后将元素所在数组中的下标赋值给前面添加位置元素的游标，代码如下所示：

    void insertArr(component *array, int body, int add, char a)
{
    int tempBody = body;
    for (int i = 1; i < add; i++)
    {
        tempBody = array[tempBody].cur;
    }
    int insert = mallocArr(array);
    array[insert].cur = array[tempBody].cur;
    array[insert].data = a;
    array[tempBody].cur = insert;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    3、查找元素

    查找元素需要我们逐个遍历静态列表，找到存有指定数据元素的节点

    int selectElem(component *array, int body, char elem)
{
    int tempBody = body;
    //当游标值为0时，表示链表结束
    while (array[tempBody].cur != 0)
    {
        if (array[tempBody].data == elem)
        {
            return tempBody;
        }
        tempBody = array[tempBody].cur;
    }
    return -1; //返回-1，表示在链表中没有找到该元素
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    4、删除元素

    删除元素的步骤为：

    1. 将存有目标元素的节点从数据链表中摘除；
    2. 将摘除节点添加到备用链表，以便下次再用；

    代码如下：

    void deletArr(component *array, int body, char a)
{
    int tempBody = body;
    //找到被删除结点的位置
    while (array[tempBody].data != a)
    {
        tempBody = array[tempBody].cur;
        //当tempBody为0时，表示链表遍历结束，说明链表中没有存储该数据的结点
        if (tempBody == 0)
        {
            printf("链表中没有此数据");
            return;
        }
    }
    //运行到此，证明有该结点
    int del = tempBody;
    tempBody = body;
    //找到该结点的上一个结点，做删除操作
    while (array[tempBody].cur != del)
    {
        tempBody = array[tempBody].cur;
    }
    //将被删除结点的游标直接给被删除结点的上一个结点
    array[tempBody].cur = array[del].cur;

    freeArr(array, del);
}

    • 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

    5、更改元素

    更改元素的步骤为找到目标元素的节点后更改节点中元素的数据域

    void amendElem(component *array, int body, char oldElem, char newElem)
{
    int add = selectElem(array, body, oldElem);
    if (add == -1)
    {
        printf("无更改元素");
        return;
    }
    array[add].data = newElem;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
  • 相关阅读:
    微服务解码：揭示API的优势挑战与最佳实践
    Python常用库(六):科学计算库-Numpy[上篇]:创建、访问、赋值
    健身房信息管理系统/健身房管理系统
    SPC5777CDK3MMO4 IC MCU 32BIT,SPC5777CDK3MME3
    Git工具的使用
    从 iPhone 15/15 Pro 恢复丢失数据的 3 种方法
    Coovally模型探索：高效下载并使用Hugging Face Transformers预训练模型
    Vue3开发最佳实践和实用技巧（上）
    curl快速学习指南：从新手到专家
    Minifilter过滤驱动与R3程序通讯实现文件保护
  • 原文地址：https://blog.csdn.net/m0_51220742/article/details/126375918