【数据结构初阶】之单链表

【数据结构初阶】之链表

• 1. 链表是什么
• • 2. 单链表的逻辑结构和物理结构
  • 3.如何创建一个单链表的自定义类型
  • 4.单链表的增删查改及各种功能的实现
  • • 4.1 单链表创建一个节点
    • 4.2 单链表的头插
    • • 4.2.1 头插的函数设计（参数类型及其返回值）
      • 4.2.1 头插的函数实现
      • 4.3 单链表的头删
      • 4.4 单链表的尾插
      • 4.5 单链表的尾删
      • 4.6单链表的打印
      • 4.7单链表的在pos之前和之后插入数据
      • • 4.7.1单链表在pos位置之前插入
        • 4.7.2单链表在pos位置之后插入
        • 4.8 单链表在pos位置和pos位置之后删除数据
        • • 4.8.1 在pos位置删除数据
          • 4.8.2在pos位置之后删除数据
          • 4.9单链表查找数据
          • 4.10单链表销毁
          • 5.单链表各种功能的测试
          • • 5.1 测试头插头删
            • 5.2 测试尾插尾删

              

              ❤️博客主页： 小镇敲码人

              🍏 欢迎关注：👍点赞 👂🏽留言 😍收藏

              🌞任尔江湖满血骨，我自踏雪寻梅香。 万千浮云遮碧月，独傲天下百坚强。 男儿应有龙腾志，盖世一意转洪荒。 莫使此生无痕度，终归人间一捧黄。🍎🍎🍎

              ❤️ 什么？你问我答案，少年你看，下一个十年又来了 💞 💞 💞

              1. 链表是什么

              链表是数据结构里面一种常见的数据结构，主要用于数据的存储和管理，常见的功能是增删查改，依据是否有头节点、单向还是双向、循环还是不循环，通常有6种链表。

              

              我们下面主要讲一下不带头不循环单链表，以下都简称单链表。

              2. 单链表的逻辑结构和物理结构

              

              

              从以上两幅图我们可以知道，单链表在物理结构上的存储其实是不连续的，而是因为它的当前节点中保存了下一个节点的地址，我们通过这个地址可以访问到下一个节点里面的内容，所以我们在分析问题的时候假想是连续的就像一个链子一样把节点串在一起。

              3.如何创建一个单链表的自定义类型

              那应该如何实现创建一个单链表的类型呢？我们在C语言里面知道是没有单链表这个类的，所以自定义类型一般使用struct创建一个结构体，结构体里面有两个成员，一个是数据域，一个是指针域（保存），那小伙伴可能就要问了，为什么我们不直接保存下一个节点，而是要保存它的地址呢？因为会出现如下问题：

              typedef struct SListNode
              {
              	SLTDateType data;
              	struct SListNode next;
              }SListNode;
              

              这样创建单链表的类型，正确与否先不论，你该如何计算这个结构体所占空间的大小呢，我们知道结构体有内存对齐的规则，那问题来了你的一个成员是同一个自定义类型的结构体对象，你如何知道它的大小呢？就出现了一系列的问题，但是如果使用结构体指针，指针的大小是固定的，就不会出现这种问题。

              所以正确的创建单链表这个自定义类型的代码应该是这样的：

              typedef int SLTDateType;
              typedef struct SListNode
              {
              	SLTDateType data;
              	struct SListNode* next;
              }SListNode;
              

              由于我们不清楚之后要存放的是什么类型的数据，所以使用typedef为我们的数据类型取个别名，之后的代码都将使用这个别名来代表我们单链表中存放的数据类型，因为如果之后数据类型发生变化只更改这一个地方就可以了。

              4.单链表的增删查改及各种功能的实现

              4.1 单链表创建一个节点

              由于我们进行头插，或者尾插操作都需要创建新的节点，所以写一个创建节点的函数避免重复代码。

              // 动态申请一个节点
              SListNode* BuySListNode(SLTDateType x)
              {
              	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
              	if(newnode == NULL)
              	{
              			perror("malloc Failed\n");
              			exit(-1);
              	}
              	newnode->data = x;
              	newnode->next = NULL;
              	return newnode;
              }
              

              为什么要使用malloc动态申请一个空间呢？因为我们动态开辟的空间是在堆上申请的，堆上申请的空间有一个特点，想要释放它的空间只有两种办法：1.手动free函数释放。2.main函数执行到return 0,也就是程序运行结束。也就是说我们在堆上开空间，即使出了这个函数的作用域，这片空间也不会被销毁，不然我们如果创建一个节点刚出这个函数还没和链表连接起来它的空间就被系统回收了，我们就无法成功创建链表了，除非你所有的代码只写在main函数里面，这显然是不现实的。

              

              上图的代码是加一个判断，防止malloc申请空间失败，程序莫名其妙的挂了，而程序员不知道原因，这段代码可以增加代码的健壮性，perror是一个函数，它负责报错，我们在C语言字符串函数中有过较为详细的讲解，这里不再做过多的阐述，exit(-1)可以直接结束程序，与return 0的区别是后者只是退出某个函数，而前者是直接结束程序，并显示代码为-1，也就是下图箭头所指的地方:

              

              这也是为了增加代码的健壮性。

              动态申请一个节点时要对它进行初始化，包括两个部分，数据域和指针域，数据域好说，直接赋我们传过来的数据，指针域我们只需要给它赋值为NULL就行，防止出现野指针的问题，至于后续怎么处理，这个函数不负责。

              4.2 单链表的头插

              头插顾名思义，就是在链表的头节点之前插入一个新的节点。

              4.2.1 头插的函数设计（参数类型及其返回值）

              那应该如何设计这个函数呢？

              1. 参数类型

                 首先我们想改变结构体的数据，函数传参应该如何设计呢？直接传结构体对象过去可以吗？显然是不行的，因为如果形参也是一个结构体类型的话，形参就只是它的一个拷贝，改变形参不会影响实参，所以我们首先想改变结构体里的数据，即在函数里给数据域赋值，可以影响到外面的结构体，就必须传结构体指针过去，它保存的是结构体的地址，改变它就是改变函数外面的结构体，但是这样就可以了吗？因为我们是不带头的单链表，如果头插遇见了刚好一个节点都没有的情况该怎么办呢？这个时候那个新开的节点就是我们的头节点，它的地址就是我们头节点的地址，所以我们改变原先头节点的地址，我们现在传的是结构体的地址，参数是一级指针，外面是结构体的地址也相当于是一级指针，我们想要在函数体里改变一级指针的值就必须用到二级指针，因为这两个一级指针除了保存的地址是一样的，其它都不一样，你在函数体里面改变这个一级指针，是无法影响到外面的一级指针的。

                 至于返回值，头插不需要返回任何东西，所以类型是void.

              4.2.1 头插的函数实现

              // 单链表的头插
              void SListPushFront(SListNode** pplist, SLTDateType x)
              {
              	SListNode* newnode = BuySListNode(x);
              	newnode->next = (*pplist);
              	*pplist = newnode;
              }
              

              因为要传结构体类型的二级指针我们在外面初始化结构体对象时，应该直接创建一个结构体指针，并将其初始化为NULL防止出现野指针的情况。

              

              4.3 单链表的头删

              有增加数据，自然就有删除数据，头删就是删除头节点。

              既然删除了头节点，后面一个就是新的头节点，那我们就要改变头节点的地址，由于我们传的是头节点的地址，想改变它就还得用二级指针，但是头删补需要传数据域。

              代码实现：

              // 单链表头删
              void SListPopFront(SListNode** pplist)
              {
              	//空
              	assert(*pplist);
              	//非空
              	SListNode* newhead = (*pplist)->next;
              	free(*pplist);
              	*pplist = newhead;
              }
              

              assert函数可以强制判空，如果链表已经为空了，就不能继续删了如果没有这句话，我们就可能对NULL进行->操作，这是非法的，另外我们要先保存好下一个节点的地址，然后再去释放头节点的地址，如果不释放，程序只要不结束，这段空间就不会被系统回收，就会造成内存泄漏，顺序如果反了也不行，先释放头节点的空间，我们就无法找到头节点后面的节点了。

              4.4 单链表的尾插

              尾插也存在链表为空的情况，这个时候就需要改变头节点的地址，也需要用到结构体二级指针。

              // 单链表尾插
              void SListPushBack(SListNode** pplist, SLTDateType x)
              {
              	SListNode* newnode = BuySListNode(x);
              	SListNode* tail = (*pplist);
              	if (tail == NULL)
              		*pplist = newnode;
              	else
              	{
              		while (tail->next)
              		{
              			tail = tail->next;
              		}
              		tail->next = newnode;
              	}
              }
              

              但是单链表没有保存尾节点的地址，所以需要我们自己遍历去找，一直到节点的next保存的是NULL为止，注意每次循环都要对tail指针进行更新，否则就成死循环了，找到后将尾节点的next指针指向新的节点就完成了尾插，注意空链表的情况要单独考虑。

              4.5 单链表的尾删

              尾删和头删对应，是删除尾节点，和尾插一样要循环找尾节点。

              // 单链表的尾删
              void SListPopBack(SListNode** pplist)
              {
              	assert(*pplist);
              	SListNode* tail = *pplist;
              	SListNode* prevtail = *pplist;
              	while (tail->next)
              	{
              		prevtail = tail;
              		tail = tail->next;
              	}
              	if (prevtail->next)
              		prevtail->next = NULL;
              	else
              		*pplist = NULL;
              	free(tail);
              }
              

              assert函数帮助我们强制的规避链表为空的情况。当链表不为空时，我们遍历链表，保存尾节点和尾节点的前一个节点，因为我们需要将新的尾节点的next指针置为空，否则释放尾节点的空间之后，新的尾节点的next指针就变成野指针了，由于链表只存在一个节点时，尾节点和尾节点前面的一个节点相同，所以需要分情况讨论，区别就在于prevtail的下一个节点是否为空，只有只存在一个节点时才会为空，这个时候直接把头节点置为NULL,然后释放tail。

              4.6单链表的打印

              我们在写好单链表的各种功能后，经常要把单链表直观的打印出来以便我们查看功能是否正确，所以肯定会使用很多次打印，为避免代码重复，我们将其单独写成函数。由于我们有些地方要传二级指针，所以我们是直接创建的结构体指针，打印链表不存在更改头节点的地址，所以我们直接传一级指针就可以了。

              // 单链表打印
              void SListPrint(SListNode* plist)
              {
              	SListNode* cur = plist;
              	while (cur)
              	{
              		printf("%d->", cur->data);
              		cur = cur->next;
              	}
              	printf("NULL\n");
              }
              

              4.7单链表的在pos之前和之后插入数据

              4.7.1单链表在pos位置之前插入

              在pos位置之前插入较为复杂，因为我们需要把节点链接到pos位置和pos位置之前的节点之间，就需要遍历链表寻找pos位置之前的节点。

              // 在pos位置之前插入
              void SLTInsert(SListNode** plist, SListNode* pos, SLTDateType x)
              {
              	assert(plist);
              	assert(pos);
              	if (pos == *plist)
              		SListPushFront(plist, x);
              	else
              	{
              		SListNode* newnode = BuySListNode(x);
              		SListNode* prevpos = *plist;
              		while (prevpos->next != pos)
              		{
              			prevpos = prevpos->next;
              		}
              		prevpos->next = newnode;
              		newnode->next = pos;
              	}
              }
              

              可以看到上述代码依然是分了两种情况，如果pos就是头节点，直接复用头插。另外一种情况就是要遍历找到pos位置的前一个节点，当前节点的下一个节点为pos时，就代表找到了，循环结束。

              4.7.2单链表在pos位置之后插入

              这种相对来说比较简单，我们先将新节点的next指针指向pos节点的next指针，然后在更新pos节点的指针域就插入完成了。

              void SListInsertAfter(SListNode* pos, SLTDateType x)
              {
              	assert(pos);
              	SListNode* newnode = BuySListNode(x);
              	SListNode* after = pos->next;
              	pos->next = newnode;
              	newnode->next = after;
              }
              

              如果采用上面那种方法先后顺序是不能变的，否则就无法将新节点和链表后面的节点连接在一起了，但是如果我们直接把pos后一个位置的节点指针用一个同类型的指针变量保存起来就不存在这种问题，无论你顺序怎么变，它都不会出错。

              4.8 单链表在pos位置和pos位置之后删除数据

              4.8.1 在pos位置删除数据

              和在pos之前插入类似，我们需要循环找到pos位置之前的节点，让它和pos位置后一个节点链接起来。

              //删除pos位置
              void SLTErase(SListNode** plist, SListNode* pos)
              {
              	assert(plist);
              	assert(pos);
              	if (pos == *plist)
              	{
              		SListPopFront(plist);
              	}
              	else
              	{
              		SListNode* prevpos = *plist;
              		while (prevpos->next != pos)
              		{
              			prevpos = prevpos->next;
              		}
              		prevpos->next = pos->next;
              		free(pos);
              	}
              }
              

              依然分两种情况,如果pos节点和头节点相同，那么就复用头删。其它的情况则需要遍历找到pos位置前一个节点，然后先链接后释放空间。

              4.8.2在pos位置之后删除数据

              这种情况没有什么特殊的地方，就是注意对只有一个节点的情况进行处理。

              void SListEraseAfter(SListNode* pos)
              {
              	assert(pos);
              	assert(pos->next);
              	SListNode* after = pos->next->next;
              	free(pos->next);
              	pos->next = after;
              }
              

              4.9单链表查找数据

              这个函数主要用来查找某个值所在的节点位置，并返回其节点地址，如果没找到就返回空指针，使用简单的遍历就可以实现。

              // 单链表查找
              SListNode* SListFind(SListNode* plist, SLTDateType x)
              {
              	SListNode* cur = plist;
              	while (cur)
              	{
              		if (cur->data == x)
              			return cur;
              		cur = cur->next;
              	}
              	return NULL;
              }
              

              4.10单链表销毁

              单链表既然创建了，就会有销毁的函数，手动回收其在堆上开的空间，主要利用free函数和遍历实现，具体代码如下：

              // 单链表的销毁
              void SListDestroy(SListNode** plist)//传二级指针，因为后面需要将头节点的地址赋值为NULL
              {
              	assert(*plist);//如果链表已经为空，就不用继续销毁了。
              	SListNode* cur = *plist;
              	SListNode* after = (*plist)->next;
              	while (cur)
              	{
              		free(cur);
              		cur = after;
              		if(after)
              		after = after->next;
              	}
              	*plist = NULL;
              }
              

              • 注意：*和->,->的优先级更高,所以我们在解引用结构体二级指针时应该加上小括号，让其先与*结合，否则就会报错。

                5.单链表各种功能的测试

                5.1 测试头插头删

                #include"slist.h"
                //单链表测试--头插头删
                void SListNodeTest1()
                {
                	SListNode* SL = NULL;
                	SListPushFront(&SL, 2);
                	SListPrint(SL);
                	SListPushFront(&SL, 3);
                	SListPrint(SL);
                	SListPushFront(&SL, 4);
                	SListPrint(SL);
                	SListPushFront(&SL, 5);
                	SListPrint(SL);
                	SListPushFront(&SL, 6);
                	SListPrint(SL);
                	SListPushFront(&SL, 7);
                	SListPrint(SL);
                	SListNode* pos = SListFind(SL, 3);
                	SListInsertAfter(pos, 100);
                	SListPrint(SL);
                	SLTInsert(&SL, pos, 200);
                	SListPrint(SL);
                	pos = SListFind(SL, 100);
                	SListEraseAfter(pos);
                	SListPrint(SL);
                	SLTErase(&SL, pos);
                	SListPrint(SL);
                	SListPopFront(&SL);
                	SListPrint(SL);
                	SListPopFront(&SL);
                	SListPrint(SL);
                	SListPopFront(&SL);
                	SListPrint(SL);
                	SListPopFront(&SL);
                	SListPrint(SL);
                	SListPopFront(&SL);
                	SListPrint(SL);
                	SListPopFront(&SL);
                	SListPrint(SL);
                }
                int main()
                {
                	SListNodeTest1();
                	return 0;
                }
                

                运行截图：

                

                5.2 测试尾插尾删

                #include"slist.h"
                //测试尾插尾删
                void SListNodeTest2()
                {
                	SListNode* SL = NULL;
                	SListPushBack(&SL, 2);
                	SListPrint(SL);
                	SListPushBack(&SL, 3);
                	SListPrint(SL);
                	SListPushBack(&SL, 4);
                	SListPrint(SL);
                	SListPushBack(&SL, 5);
                	SListPrint(SL);
                	SListPushBack(&SL, 6);
                	SListPrint(SL);
                	SListPushBack(&SL, 7);
                	SListNode* pos = SListFind(SL, 3);
                	SListInsertAfter(pos, 100);
                	SListPrint(SL);
                	SLTInsert(&SL, pos, 200);
                	SListPrint(SL);
                	pos = SListFind(SL, 100);
                	SListEraseAfter(pos);
                	SListPrint(SL);
                	SLTErase(&SL, pos);
                	SListPrint(SL);
                	SListPopBack(&SL);
                	SListPrint(SL);
                	SListPopBack(&SL);
                	SListPrint(SL);
                	SListDestroy(&SL);
                	SListPrint(SL);
                }
                int main()
                {
                	//SListNodeTest1();
                	SListNodeTest2();
                	
                	return 0;
                }
                

                运行结果：

                

                • 注意：这里所有的功能都已经测试完毕，一切正常，我们在学习单链表时，要有建立工程的意识，函数声明及自定义类型的创建放在头文件，函数的定义放在一个.c文件，测试放在另一个.c文件，这样不仅仅有利于我们后续的复习，而且能使工程更加的健壮。