【数据结构】动图详解单向链表
创始人
2024-05-21 13:17:20
0次

目录

1.什么是链表

        1.问题引入

        2. 链表的概念及结构

        3. 问题解决

2.单向链表接口的实现

        1.接口1，2---头插，尾插

        2. 接口3，4---头删，尾删

        3. 接口5---查找

         4. 接口6，7---插入，删除

        5. 接口8---打印

         6. 注意事项总结

3.完整代码及效果展示 

1.什么是链表

        1.问题引入

        上期我们讲解了顺序表的基本概念和实现方法（传送门：详解顺序表）。但是顺序表存在着如下三个问题：

  1. 顺序表中间及头部的插入与删除，需要对原有数据进行移动，时间复杂度为O(N),成本较高
  2. 使用realloc进行增容时需要申请新空间，释放旧空间，拷贝数据，消耗较高。
  3. 由于我们无法知道用户实际需要多少空间，在增容时往往可能会有大量的空间剩余。例如在容量为100时满了进行2倍增容到200，如果后续只需插入5个数据，则会浪费95个数据空间；而如果我们每次只扩大1个数据空间，当需要插入95个数据时，就需要进行realloc操作95次，成本较高。

        那么这些问题要如何解决呢？通过链表， 我们就可以很轻松的解决以上问题。下面，就让我们感受链表的魅力吧！

        2. 链表的概念及结构

        链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。它的结构如下所示(以单向链表为例)：

        我们把date和next形成的结构体称为链表的一个结点，我们可以看到，链表就是由一个个结点链接起来的非连续线性结构，不同结点通过next指针连接的，最后一个结点的next指针指向空。链表也是线性表中的一种。

当然，在实际应用中，链表的结构多种多样，通过以下几种情况组合而成的就有8种链表结构：

1. 单 向 、 双 向

2. 带 头结点 、 不 带 头结点

3. 循 环 、 非 循 环

本期我们讲解的是实际应用中最常用的两种结构之一：单向不带头非循环链表。（另外一种是带头双向循环链表）

        3. 问题解决

        通过以上链表结构，我们就能很好地解决顺序表的局限：

  1. 每当我们需要新增数据时，我们只需申请一个新结点用来保存数据，然后用指针将链表与新结点链接起来即可，并不需要进行数据拷贝。
  2. 由于使用链表存储数据总是处于满载状态，每个结点都是有效数据，需要插入时则申请新结点并与链表连接，因此就不存在空间浪费的问题。
  3. 链表的结构是线性非连续的，各结点通过指针连接。如果需要在头部或中间插入数据，只需改变结点指针的指向即可，无需再移动数据。

2.单向链表接口的实现

        首先，在实现各种接口函数前，我们需要定义一个结构体来代表每一个结点，用date保存结点中的数据，用next保存下一结点的地址。同样的，我们采取typedef的方式将类型重命名方便代码的编写与维护。如下：

由于我们实现的单向链表是不带头结点的，所以我们还需要定义一个指针指向链表的第一个结点(下面称为头指针)。

        1.接口1，2---头插，尾插

        对于头插，我们只需要创建新结点保存数据，然后将头指针指向新结点，新结点指向原来头指针指向的结点即可，动态效果如下：

        具体代码如下：

//用于创建新结点
SLNode* CreateNode(SLDateType x)
{SLNode* cur = (SLNode*)malloc(sizeof(SLNode));cur->date = x;cur->next = NULL;return cur;
}//头插
void SListPushFront(SLNode** pphead, SLDateType x)
{SLNode* NewNode = CreateNode(x); //获取新结点NewNode->next = *pphead; *pphead = NewNode; //修改头指针
}

值得注意的是，函数中我们传入的是头指针的地址。这是由于我们需要修改头指针使其指向新的结点，因此需要采用址传递的方式，用二级指针接收，否则只会修改临时变量造成出错。

         对于尾插，我们需要先找到链表的尾结点，然后将尾结点的next指向新结点，动态效果如下：

        代码如下： 

//尾插，初稿
void SListPushBack(SLNode** pphead, SLDateType x)
{SLNode* NewNode = CreateNode(x);SLNode* tail = *pphead;while (tail->next != NULL) //不为尾结点{tail = tail->next; //tail指向下一结点}//找到尾结点tail->next = NewNode;
}

        但是，上述代码是存在问题的。我们知道->相当于是一种解引用，当链表为空时，即tail==NULL时，此时我们进行tail->next操作显然是非法的，所以我们还需对链表为空的情况做出讨论，最终代码如下：

//尾插，终稿
void SListPushBack(SLNode** pphead, SLDateType x)
{SLNode* NewNode = CreateNode(x);if (*pphead == NULL){*pphead = NewNode; //为空就直接修改头指针指向新结点，因此需要传二级指针}else{SLNode* tail = *pphead;while (tail->next != NULL) //不为尾结点{tail = tail->next; //指向下一结点}//找到尾结点tail->next = NewNode; }
}

        2. 接口3，4---头删，尾删

        对于头删，我们只需要将头指针指向下一个位置，然后将原来指向的空间free()掉即可。如果链表为空，我们就让函数直接返回，具体动态效果如下：

        在代码实现中，我们需要先创建一个临时变量next来保存下一个结点的地址，这是因为free()后就无法通过->得到下一个结点的地址了。具体代码如下：

//头删
void SListPopFront(SLNode** pphead)
{if (*pphead == NULL){return;  //链表为空直接返回}else{SLNode* next = (*pphead)->next; //存储下一个结点地址free(*pphead);*pphead = next; //改变头指针指向，因此需要传二级指针}
}

        对于尾删，我们同样需要找到尾结点。这里和尾插不同的是，我们除了要找到尾结点，还需找到尾结点的前一个结点并使其next置为空，因此我们可以使用两个指针prev和tail进行移动，prev指向tail的上一个结点，具体动图如下：

        具体代码如下：

//尾删，初稿
void SListPopBack(SLNode** pphead)
{if (*pphead == NULL) //没有结点{return;}else  //一个以上结点{SLNode* tail = *pphead;SLNode* prev = NULL;while (tail->next != NULL) //tail不为尾结点{prev = tail;tail = tail->next; //tail指向下一结点}//tail为尾结点，此时prev为尾结点的前一个结点free(tail); //释放掉尾结点tail=NULL;prev->next = NULL;}
}

        这里和头删一样，当链表为空时直接让函数返回。但是以上代码依旧存在着一个问题，就是当链表只有一个结点时，tail直接指向尾结点，此时prev为NULL，禁止对其进行->操作。所以我们还需要对只有一个结点的情况进行讨论，最终代码如下：

//尾删，终稿
void SListPopBack(SLNode** pphead)
{if (*pphead == NULL) //没有结点{return;}else if ((*pphead)->next == NULL)  //只有一个结点{free(*pphead);*pphead = NULL; //直接将结点释放掉，头指针改为NULL，因此需要传二级指针}else  //一个以上结点{SLNode* tail = *pphead;SLNode* prev = NULL;while (tail->next != NULL) //tail不为尾结点{prev = tail;tail = tail->next; //tail指向下一结点}//tail为尾结点，此时prev为尾结点的前一个结点free(tail); //释放掉尾结点tail=NULL;prev->next = NULL;}
}

        3. 接口5---查找

        对于查找，我们只需遍历链表的所有结点即可，故不需要头指针，只需传一级指针即可。当找到需要查找的date时，返回对应结点的指针，若没找到或者链表为空时，返回NULL，代码如下：

//查找
SLNode* SListFind(SLNode* phead, SLDateType x)
{while (phead){if (phead->date == x){return phead; //找到了，返回结点指针}phead = phead->next; //向后查找}//没有找到，返回空指针return NULL;
}

         4. 接口6，7---插入，删除

        对于插入，我们可以实现一个在指定结点前插入一个新结点的接口，而这个指定结点我们可以通过查找接口来获取。相同的，在进行插入操作时我们还需要得到前一个结点的地址，我们用prev来存储，然后将prev->next改为新结点地址，新结点的next为我们传入的结点的地址。动态效果如下：

//插入，初稿
void SListInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{if (pos == NULL) //指定结点为空直接返回{return;}SLNode* NewNode = CreateNode(x); //获取新结点SLNode* prev = *pphead;while (prev->next != pos) //prev不指向pos上一结点{prev = prev->next; //prev指向下一结点}//当prev指向pos上一结点，插入新结点prev->next = NewNode;NewNode->next = pos;
}

         (嘿嘿，我又来了qwq)，上述的代码其实还是存在bug的，就是当我们传入的指定结点为头结点时，prev->next永远不可能等于pos，prev不断向后更新，最终为NULL导致程序崩溃。动态分析如下：

         因此我们需要进行分类讨论，而我们发现如果pos指向头结点，那在其前面插入不就相当于头插吗？所以我们可以直接调用头插接口，改进后的代码如下：

//插入，终稿
void SListInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{if (pos == NULL) //指定结点为空直接返回{return;}if (*pphead==pos) //pos为头结点指针，直接头插{SListPushFront(pphead,x);}else{SLNode* NewNode = CreateNode(x); //获取新结点SLNode* prev = *pphead;while (prev->next != pos) //prev不指向pos上一结点{prev = prev->next; //prev指向下一结点}//当prev指向pos上一结点，插入新结点prev->next = NewNode;NewNode->next = pos;}
}

        对于删除，我们同样可以实现一个删除指定结点的接口，而这个指定结点我们依旧可以通过查找接口来获取。同样，除了将指定的结点free()掉，还需将其上一个结点的next指向pos的下一结点。与插入一样都需要找到上一个结点的位置，在这过程中可能引发的问题也是一样的，这里就不再赘述了，直接上代码：

//删除
void SListErase(SLNode** pphead, SLNode* pos)
{if (pos == NULL) //指定结点为空直接返回{return;}if (*pphead == pos) //pos为头结点指针，直接头删{SListPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos) //prev不指向pos上一结点{prev = prev->next; //使prev指向下一个结点}//当prev指向pos上一结点，删除pos指向结点，更新prev->nextprev->next = pos->next;free(pos);}
}

        5. 接口8---打印

        对于打印，只需从头结点开始，向后遍历链表，打印每个结点的date直到走到链表尾即可，此时指针指向NULL。由于不修改头指针指向，因此采用值传递即可，用一级指针接收。代码如下：

//打印
void SListPrint(SLNode* phead)
{while (phead != NULL) //遍历链表直到链表尾{printf("%d->", phead->date);phead = phead->next;}//到达链表尾，打印NULLprintf("NULL");
}

         6. 注意事项总结

通过上面一个个接口的实现，我们得出以下两个值得注意的地方：

  1. 当我们需要修改头指针时，如插入删除操作时，需要使用址传递，用二级指针来接收头指针的地址。而如果我们不需要修改头指针时，如打印，查找等，建议使用值传递，用一级指针来接收，避免头指针被意外修改。
  2. 在实现链表接口时，需要时刻考虑到当链表为空，链表只有一个结点，对头结点进行操作，对尾结点进行操作等特殊情况是否会出现bug。

3.完整代码及效果展示 

        我们可以采用多文件编写的形式，将上述接口的定义实现放在SList.c文件中，然后将接口的声明和结构体的定义放于SList.h头文件中，以达到封装的效果。这样我们如果需要使用单向链表，就只需要在文件中包含对应的头文件SList.h就可以使用我们上面定义的各种接口。以下为本文实现的单向链表完整代码以及效果展示：

//SList.h文件，用于声明接口函数，定义结构体
#pragma once
#include
#include
typedef int SLDateType;
struct SListNode
{SLDateType date;struct SListNode* next;
};
typedef struct SListNode SLNode;// 不会改变链表的头指针，传一级指针
void SListPrint(SLNode* phead);
SLNode* SListFind(SLNode* phead, SLDateType x);// 可能会改变链表的头指针，传二级指针
void SListPushBack(SLNode** pphead, SLDateType x);
void SListPushFront(SLNode** pphead, SLDateType x);
void SListPopFront(SLNode** pphead);
void SListPopBack(SLNode** pphead);
// 在pos的前面插入x
void SListInsert(SLNode** phead, SLNode* pos, SLDateType x);
// 删除pos位置的值
void SListErase(SLNode** phead, SLNode* pos);
//SList.c文件，用于定义接口函数
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SListPrint(SLNode* phead)
{while (phead != NULL){printf("%d->", phead->date);phead = phead->next;}printf("NULL");
}
SLNode* CreateNode(SLDateType x)
{SLNode* cur = (SLNode*)malloc(sizeof(SLNode));cur->date = x;cur->next = NULL;return cur;
}void SListPushBack(SLNode** pphead, SLDateType x)
{SLNode* NewNode = CreateNode(x);if (*pphead == NULL){*pphead = NewNode; //为空就直接修改头指针指向新结点，因此需要传二级指针}else{SLNode* tail = *pphead;while (tail->next != NULL) //不为尾结点{tail = tail->next; //指向下一结点}//找到尾结点tail->next = NewNode;}
}void SListPushFront(SLNode** pphead, SLDateType x)
{SLNode* NewNode = CreateNode(x); //获取新结点NewNode->next = *pphead;*pphead = NewNode; //修改头指针
}void SListPopFront(SLNode** pphead)
{if (*pphead == NULL){return;  //链表为空直接返回}else{SLNode* next = (*pphead)->next; //存储下一个结点地址free(*pphead);*pphead = next; //改变头指针指向，因此需要传二级指针}
}void SListPopBack(SLNode** pphead)
{if (*pphead == NULL) //没有结点{return;}else if ((*pphead)->next == NULL)  //只有一个结点{free(*pphead);*pphead = NULL; //直接将结点释放掉，头指针改为NULL，因此需要传二级指针}else  //一个以上结点{SLNode* tail = *pphead;SLNode* prev = NULL;while (tail->next != NULL) //tail不为尾结点{prev = tail;tail = tail->next; //tail指向下一结点}//tail为尾结点，此时prev为尾结点的前一个结点free(tail); //释放掉尾结点tail = NULL;prev->next = NULL;}
}SLNode* SListFind(SLNode* phead, SLDateType x)
{while (phead){if (phead->date == x){return phead; //找到了，返回结点指针}phead = phead->next; //向后查找}//没有找到，返回空指针return NULL;
}void SListInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{if (pos == NULL) //指定结点为空直接返回{return;}if (*pphead == pos) //pos为头结点指针，直接头插{SListPushFront(pphead, x);}else{SLNode* NewNode = CreateNode(x); //获取新结点SLNode* prev = *pphead;while (prev->next != pos) //prev不指向pos上一结点{prev = prev->next; //prev指向下一结点}//prev指向pos上一结点，插入新结点prev->next = NewNode;NewNode->next = pos;}
}void SListErase(SLNode** pphead, SLNode* pos)
{if (pos == NULL) //指定结点为空直接返回{return;}if (*pphead == pos){SListPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}
}

       最后， 我们在text.c文件调用单向链表各个接口进行测试，如下：

//text.c文件，用于测试
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void SListText()
{SLNode* phead = NULL;printf("起始数据: \n");SListPrint(phead);//头插SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);printf("\n头插入数据后: \n");SListPrint(phead);//尾插SListPushBack(&phead, 4);SListPushBack(&phead, 5);SListPushBack(&phead, 6);printf("\n尾插入数据后: \n");SListPrint(phead);//头删SListPopFront(&phead);printf("\n头删数据后: \n");SListPrint(phead);//尾删SListPopBack(&phead);printf("\n尾删数据后: \n");SListPrint(phead);//找出数据为5的结点并在其前面插入8SLNode* cur1 = SListFind(phead, 5);if (cur1){SListInsert(&phead, cur1, 8);}printf("\n5前面插入数据后: \n");SListPrint(phead);//删除数据为1的结点SLNode* cur2 = SListFind(phead, 1);if (cur2){SListErase(&phead, cur2);}printf("\n删除数据1的结点后: \n");SListPrint(phead);
}
int main()
{SListText();return 0;
}

        以下就是测试的最终效果：

 以上，就是本期的全部内容。

制作不易，能否点个赞再走呢qwq

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：微信小程序使用canvas生成分享海报功能复盘

下一篇：ThinkPad R490电脑开机之后无线重启怎么重装系统？

相关内容

热门资讯

新春的主持稿 新春的主持稿　　在日常生活和工作中，需要使用主持稿的情况越来越多，主持稿是主持人在会议或是节目当中串...
五四青年节的致辞 五四青年节的致辞（通用20篇）　　在平日的学习、工作和生活里，大家总少不了要接触或使用致辞吧，致辞是...
新年年会简短优秀致辞 新年年会简短优秀致辞（通用8篇）　　在生活、工作和学习中，大家都不可避免地会接触到致辞吧，致辞具有很...
剪彩仪式主持词
告别仪式的主持词 告别仪式的主持词3篇　　告别主持词篇一：　　男：离别，是一个沉重的动词。　　女：离别，一个让人一生难...
喜爱夜蒲2经典台词 喜爱夜蒲2经典台词　　1、做要做到最好，玩要玩到最尽。　　2、我们明知不能相爱，可还是相爱了，未曾绽...
领导年会致辞 领导年会致辞　　无论在学习、工作或是生活中，大家对致辞都不陌生吧，致辞是指在举行会议或某种仪式时具有...
关于保险公司年会主持词 关于保险公司年会主持词　　公司的类型有哪些　　根据《中华人民共和国公司法》公司的主要形式为无限责任公...
在年会上的致辞 在年会上的致辞范文（精选5篇）　　在平时的学习、工作或生活中，大家都写过致辞吧，致辞是指在举行会议或...
企业开工仪式致辞 企业开工仪式致辞（精选7篇）　　在平时的学习、工作或生活中，大家都不可避免地会接触到致辞吧，致辞是指...
小学第二学期的开学典礼主持词 小学第二学期的开学典礼主持词　　主持词已成为各种演出活动和集会中不可或缺的一部分。在当今中国社会，各...
升学宴主持词 升学宴主持词3篇　　高考过后考生及家长需要考虑举办升学宴会酒席的事宜了，升学宴主持词怎么写?下面是小...
同学聚会致辞 同学聚会致辞（精选6篇）　　在生活、工作和学习中，大家都尝试过写致辞吧，在各种重大的庆典、外交、纪念...
升学宴会主持词 升学宴会主持词9篇　　主持人在台上表演的灵魂就表现在主持词中。在当今社会中，各种场合中活跃现场气氛的...
早会主持词 早会主持词范文4篇　　早会能对一天或是一周亦或是一个月的工作作出及时的总结和临时性的调整，在工作中有...
服装展示主持词示例 服装展示主持词示例　　篇一：服装展示串词　　龙 蓓　　1、现在出场的是宾馆总台接待，为大家作展示的是...
重阳节主持词 重阳节主持词（精选13篇）　　主持词分为会议主持词、晚会主持词、活动主持词、婚庆主持词等。在人们越来...
商场活动主持词 　　商场活动主持词　　亲爱的顾客朋友：　　大家下午好!　　“金猪报捷去，玉鼠送春来”。欢迎大家在这个...
主婚人简短婚礼致辞 主婚人简短婚礼致辞　　结婚是件大事，那么主婚人如何向新人们致辞呢?怎么做致辞才简短又大气呢?下面我们...
六一儿童节活动主持词 六一儿童节活动主持词集锦　　众所周知，六一儿童节是孩子们开心玩耍的节日。小编今天为大家带来六一儿童节...