【数据结构】动图详解单向链表
创始人
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电脑开机之后无线重启怎么重装系统？

相关内容

热门资讯

五年级一单元作文大全450字... 五年级一单元作文大全450字 篇一我的暑假生活暑假到了，我有了一个美妙的假期。在这个假期里，我不仅玩...
小学生五年级作文700字（实... 小学生五年级作文700字 篇一我喜欢的动物我喜欢的动物是猫咪。猫咪有着柔软的毛发和灵活的身体，总是给...
去湖北玩作文四年级（通用6篇... 去湖北玩作文四年级 篇一我去湖北玩的经历我上个暑假去了湖北旅游，度过了一个难忘的假期。湖北是一个美丽...
第一次学游泳四年级作文（精选... 第一次学游泳四年级作文 篇一第一篇内容我一直都很害怕水，每次看到水就觉得自己会被淹死。可是，我知道学...
走走停停五年级作文【精简3篇... 走走停停五年级作文 篇一：我的暑假生活暑假已经到来了，我迫不及待地计划着如何度过这个美好的假期。我和...
教室里的掌声作文600字四年... 教室里的掌声作文600字四年级 篇一教室里的掌声今天，当我走进教室的时候，一阵热烈的掌声迎接着我。我...
四年级写景作文【通用6篇】 四年级写景作文 篇一秋天的森林今天我来到了一个美丽的森林，这是我第一次来到这里，我迫不及待地想探索一...
美丽的校园就像我的家四年级作... 篇一：美丽的校园就像我的家在我眼中，学校就像我的第二个家。它不仅给予了我学习的机会和知识的智慧，更重...
优秀文章《童年趣事》【最新5... 优秀文章《童年趣事》 篇一小时候，我和爷爷奶奶住在一个小村庄里。那里的生活简单而宁静，我们的童年充满...
四年级200字校园作文大全【... 四年级200字校园作文大全 篇一我的校园生活我是一名四年级的学生，我喜欢我的校园生活。在校园里，我有...
寒假里的新鲜事四年级作文50... 篇一：寒假里的新鲜事寒假里的新鲜事四年级作文500字 篇一寒假终于来了，我和爸爸妈妈一起去了北京旅游...
描写春天的四年级作文400字... 描写春天的四年级作文400字 篇一春天的颜色春天是一个充满色彩的季节。当冬天的寒冷逐渐消散，春姑娘轻...
登碧云峰四年级作文（优秀3篇... 登碧云峰四年级作文 篇一我的暑假生活暑假来临了，我迫不及待地来到了碧云峰。碧云峰是一个美丽的山脉，被...
我爱我家四年级优秀满分作文（... 我爱我家四年级优秀满分作文 篇一家，是我最温暖的港湾家是一个人最亲近的地方，我也不例外。我爱我家，因...
我也有犯错的时候小学生作文（... 我也有犯错的时候小学生作文 篇一我也有犯错的时候我是一个小学生，虽然我还小，但是我也会犯错。每个人都...
向你介绍我400字作文四年级... 向你介绍我400字作文四年级作文 篇一我叫小明，是一个四年级的学生。今天我要向你介绍一下我自己。首先...
四年级上册第六单元作文记一次... 四年级上册第六单元作文记一次游戏 篇一我最喜欢的游戏是“捉迷藏”。这个游戏非常有趣，不仅能锻炼我们的...
低头族作文四年级【通用6篇】 低头族作文四年级 篇一低头族的危害如今，低头族成为了一个非常流行的词汇。低头族指的是那些长时间低头看...
四年级上册作文新学期新鲜事（... 四年级上册作文新学期新鲜事 篇一新学期开始了，我迫不及待地走进了教室，发现自己的座位旁边多了一个新同...
博饼四年级作文【最新3篇】 博饼四年级作文 篇一我的博饼经历今天是中秋节，我参加了学校举办的博饼活动。这是我第一次参加博饼，我非...