devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构初阶】链表（上）——无头单向非循环链表的实现_无头节点单向链表

作者：笔触狂放9 | 2024-05-19 16:37:56

赞

踩

无头节点单向链表

目录

一、链表

        1.链表的概念及结构

        2.链表的分类

                <2.1>单向链表和双向链表

                <2.2>带头节点链表和不带头节点链表

               <2.3>循环和非循环链表

二、无头单向非循环链表的实现

        1.创建无头单向非循环链表的节点

        2.为无头单向非循环链表添加数据

                <2.1>在链表尾部插入数据

                <2.2>在链表头部插入数据

                <2.3>在链表pos节点位置之后插入数据

        3.为无头单向非循环链表删除数据

                <3.1>在链表尾部删除数据

                <3.2>在链表头部删除数据 

                <3.3>在链表pos节点之后删除数据

        4.遍历链表

        5.在链表中查找数据

        6.销毁链表

 三、无头单向非循环链表实现完整代码

四、运行测试

经过上期博客的学习我们发现顺序表存在着一些缺陷：

        > 扩容时有一定的代价，尤其是异地扩容时。其次还会造成空间的浪费（空间碎片的产生）。

        > 从头部或中间插入（删除）数据时需要挪动其他数据，效率低下。

那我们是否有一种可以按需申请释放内存、在插入删除数据时不挪动数据的存储方式呢？

链表就很好的解决了以上问题：

一、链表

        1.链表的概念及结构

        概念:链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 

        下面是链表的模拟图：

        我们每次要存储要存储数据时需要向系统空间的堆区申请所存储数据外加一个指针的大小的空间（我们称这样一个大小的空间叫做节（结）点），其中指针空间所存的是下一个节点的地址（如果该节点后无节点该指针指向的地址则为空）。

从上图可看出：

        1.链式结构在逻辑上是连续的，但是在物理上不一定连续。

        2.现实中的结点一般都是从堆上申请出来的。

        3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

        2.链表的分类

                <2.1>单向链表和双向链表

                <2.2>带头节点链表和不带头节点链表

               <2.3>循环和非循环链表

         虽然链表的种类很多，但是我们最常用的是无头单向非循环链表和带头双向循环链表：

         无头单向非循环链表:结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

        带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

下面我们来对无头单向非循环链表来进行实现：

二、无头单向非循环链表的实现

在实现单链表之前我们先要确定节点类型：

  1. typedef int SLTDataType;//数据类型
  2. typedef struct SListNode//节点类型
  3. {
  4. 	SLTDataType Data;//数据
  5. 	struct SListNode* next;//节点指针
  6. }SListNode;

         注：这里的对int类型进行重定义是为了我们更好的看懂Data只是一种数据而不仅仅是int类型。所以我们在使用链表时存储的数据并不限制于int类型，这里仅仅是举例。

        1.创建无头单向非循环链表的节点

  1. SListNode* BuySListNode(SLTDataType x)//x传入要添加的数据
  2. {
  3. 	SListNode* p = (SListNode*)malloc(sizeof(SListNode));//为单链表创建一个节点的空间
  4. 	if (p == NULL)//判断堆区空间是否申请成功
  5. 	{
  6. 		perror("malloc");
  7. 		exit(-1);
  8. 	}
  9. 	p->Data = x;//拷贝数据
  10. 	p->next = NULL;//由于没有下一个节点，将节点指针置为空
  11. 	return p;
  12. }
  13.

        2.为无头单向非循环链表添加数据

                <2.1>在链表尾部插入数据

  1. void SListPushBack(SListNode** pplist, SLTDataType x)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  2. {
  3. 	SListNode* newplist = BuySListNode(x);//创建一个新节点为插入链表做准备
  4. 	if (*pplist == NULL)//如果传入的是个空链表就直接插入一个新节点
  5. 	{
  6. 		*pplist = newplist;
  7. 		return;
  8. 	}
  9. 	//传入的不是空链表就找到链表尾部
  10. 	SListNode* tail = *pplist;
  11. 	while (tail->next)
  12. 	{
  13. 		tail = tail->next;
  14. 	}
  15. 	tail->next = newplist;//在链表尾部插入数据
  16. }

                <2.2>在链表头部插入数据

  1. void SListPushFront(SListNode** pplist, SLTDataType x)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  2. {
  3. 	SListNode* newplist = BuySListNode(x);//创建一个新节点为插入链表做准备
  4. 	newplist->next = *pplist;//将节点插入到链表头部
  5. 	*pplist = newplist;//将链表的头指针指向插完节点后的新链表
  6. }

                <2.3>在链表pos节点位置之后插入数据

  1. void SListInsertAfter(SListNode** pos, SLTDataType x)//pos传入要插入其后的节点的位置的地址
  2. {
  3. 	assert(*pos);
  4. 	SListNode* newplist = BuySListNode(x);//创建一个新节点为插入链表做准备
  5. 	newplist->next = (*pos)->next;//将新节点之后指向的节点向插入
  6. 	(*pos)->next = newplist;//再将新节点插入pos节点之后的位置
  7. }

        3.为无头单向非循环链表删除数据

                <3.1>在链表尾部删除数据

  1. void SListPopBack(SListNode** pplist)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  2. {
  3. 	assert(*pplist);//传入的指针不能为空
  4. 	if ((*pplist)->next == NULL)//如果此链表只有一个节点,就直接直接释放
  5. 	{
  6. 		free(*pplist);
  7. 		*pplist = NULL;
  8. 		return;
  9. 	}
  10. 	SListNode* tail = *pplist;
  11. 	SListNode* temp = *pplist;//记录尾节点前一个节点的位置
  12. 	//找到链表尾部
  13. 	while (tail->next)
  14. 	{
  15. 		temp = tail;//记录尾节点前一个节点的位置
  16. 		tail = tail->next;
  17. 	}
  18. 	free(tail);//释放链表尾部节点的空间
  19. 	tail = NULL;//将节点置空防止野指针的产生
  20. 	temp->next = NULL;//将尾节点前一个节点的指针置空
  21. }
  22.

                <3.2>在链表头部删除数据 

  1. void SListPopFront(SListNode** pplist)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  2. {
  3. 	assert(*pplist);//传入的指针不能为空
  4. 	SListNode* Del = *pplist;//记录头节点的地址
  5. 	*pplist = (*pplist)->next;//将头节点从链表中销毁
  6. 	free(Del);
  7. 	Del = NULL;//防止野指针的产生
  8. }

                <3.3>在链表pos节点之后删除数据

  1. void SListEraseAfter(SListNode** pos)//pos传入要删除其后的节点的位置的地址
  2. {
  3. 	assert(*pos);//传入的指针不能为空
  4. 	SListNode* Del = (*pos)->next;//记录要删除节点的地址
  5. 	(*pos)->next = Del->next;//将要删除节点从链表中销毁
  6. 	Del->next = NULL;//防止free时释放整个链表空间
  7. 	free(Del);
  8. 	Del = NULL;//防止野指针的产生
  9. }

        4.遍历链表

  1. void SListPrint(SListNode* plist)
  2. {
  3. 	while (plist)//一直遍历到空为止
  4. 	{
  5. 		printf("%d->", plist->Data);
  6. 		plist = plist->next;
  7. 	}
  8. 	printf("NULL\n");
  9. }

        5.在链表中查找数据

  1. SListNode* SListFind(SListNode* plist, SLTDataType x)
  2. {
  3. 	SListNode* find = plist;
  4. 	while (find)
  5. 	{
  6. 		if (find->Data == x)
  7. 			return find;//找到返回其地址
  8. 		find = find->next;
  9. 	}
  10. 	return NULL;//没找到返回NULL
  11. }

        6.销毁链表

  1. void SListDestroy(SListNode** plist)
  2. {
  3. 	assert(*plist);//传入的指针不能为空
  4. 	SListNode* Del = *plist, * temp = *plist;
  5. 	while (Del)//释放整个链表
  6. 	{
  7. 		temp = temp->next;
  8. 		free(Del);
  9. 		Del = temp;
  10. 	}
  11. 	*plist = NULL;//置空指针防止野指针的产生
  12. }

 三、无头单向非循环链表实现完整代码

  1. typedef int SLTDataType;//数据类型
  2. typedef struct SListNode//节点类型
  3. {
  4. 	SLTDataType Data;//数据
  5. 	struct SListNode* next;//节点指针
  6. }SListNode;
  7.  
  8.  
  9. //创建一个单链表
  10. SListNode* BuySListNode(SLTDataType x)//x传入要添加的数据
  11. {
  12. 	SListNode* p = (SListNode*)malloc(sizeof(SListNode));//为单链表创建一个节点的空间
  13. 	if (p == NULL)//判断堆区空间是否申请成功
  14. 	{
  15. 		perror("malloc");
  16. 		exit(-1);
  17. 	}
  18. 	p->Data = x;//拷贝数据
  19. 	p->next = NULL;//由于没有下一个节点，将节点指针置为空
  20. 	return p;
  21. }
  22. // 单链表打印
  23. void SListPrint(SListNode* plist)
  24. {
  25. 	while (plist)
  26. 	{
  27. 		printf("%d->", plist->Data);
  28. 		plist = plist->next;
  29. 	}
  30. 	printf("NULL\n");
  31. }
  32. // 单链表尾插
  33. void SListPushBack(SListNode** pplist, SLTDataType x)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  34. {
  35. 	SListNode* newplist = BuySListNode(x);//创建一个新节点为插入链表做准备
  36. 	if (*pplist == NULL)//如果传入的是个空链表就直接插入一个新节点
  37. 	{
  38. 		*pplist = newplist;
  39. 		return;
  40. 	}
  41. 	//传入的不是空链表就找到链表尾部
  42. 	SListNode* tail = *pplist;
  43. 	while (tail->next)
  44. 	{
  45. 		tail = tail->next;
  46. 	}
  47. 	tail->next = newplist;//在链表尾部插入数据
  48. }
  49. // 单链表的头插
  50. void SListPushFront(SListNode** pplist, SLTDataType x)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  51. {
  52. 	SListNode* newplist = BuySListNode(x);//创建一个新节点为插入链表做准备
  53. 	newplist->next = *pplist;//将节点插入到链表头部
  54. 	*pplist = newplist;//将链表的头指针指向插完节点后的新链表
  55. }
  56. // 单链表的尾删
  57. void SListPopBack(SListNode** pplist)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  58. {
  59. 	assert(*pplist);//传入的指针不能为空
  60. 	if ((*pplist)->next == NULL)//如果此链表只有一个节点,就直接直接释放
  61. 	{
  62. 		free(*pplist);
  63. 		*pplist = NULL;
  64. 		return;
  65. 	}
  66. 	SListNode* tail = *pplist;
  67. 	SListNode* temp = *pplist;//记录尾节点前一个节点的位置
  68. 	//找到链表尾部
  69. 	while (tail->next)
  70. 	{
  71. 		temp = tail;//记录尾节点前一个节点的位置
  72. 		tail = tail->next;
  73. 	}
  74. 	free(tail);//释放链表尾部节点的空间
  75. 	tail = NULL;//将节点置空防止野指针的产生
  76. 	temp->next = NULL;//将尾节点前一个节点的指针置空
  77. }
  78.  
  79. // 单链表头删
  80. void SListPopFront(SListNode** pplist)//这里由于我们要改变链表指针的指向，需要使用二级指针来控制
  81. {
  82. 	assert(*pplist);//传入的指针不能为空
  83. 	SListNode* Del = *pplist;//记录头节点的地址
  84. 	*pplist = (*pplist)->next;//将头节点从链表中销毁
  85. 	free(Del);
  86. 	Del = NULL;//防止野指针的产生
  87. }
  88. // 单链表查找
  89. SListNode* SListFind(SListNode* plist, SLTDataType x)
  90. {
  91. 	assert(plist);
  92. 	SListNode* find = plist;
  93. 	while (find)
  94. 	{
  95. 		if (find->Data == x)
  96. 			return find;//找到返回其地址
  97. 		find = find->next;
  98. 	}
  99. 	return NULL;//没找到返回NULL
  100. }
  101. // 单链表在pos位置之后插入x
  102. void SListInsertAfter(SListNode** pos, SLTDataType x)//pos传入要插入其后的节点的位置
  103. {
  104. 	assert(*pos);
  105. 	SListNode* newplist = BuySListNode(x);//创建一个新节点为插入链表做准备
  106. 	newplist->next = (*pos)->next;//将新节点之后指向的节点向插入
  107. 	(*pos)->next = newplist;//再将新节点插入pos节点之后的位置
  108. }
  109. // 单链表删除pos位置之后的值
  110. void SListEraseAfter(SListNode** pos)//pos传入要删除其后的节点的位置
  111. {
  112. 	assert(*pos);//传入的指针不能为空
  113. 	SListNode* Del = (*pos)->next;//记录要删除节点的地址
  114. 	(*pos)->next = Del->next;//将要删除节点从链表中销毁
  115. 	Del->next = NULL;//防止free时释放整个链表空间
  116. 	free(Del);
  117. 	Del = NULL;//防止野指针的产生
  118. }
  119. // 单链表的销毁
  120. void SListDestroy(SListNode** plist)
  121. {
  122. 	assert(*plist);//传入的指针不能为空
  123. 	SListNode* Del = *plist, * temp = *plist;
  124. 	while (Del)//释放整个链表
  125. 	{
  126. 		temp = temp->next;
  127. 		free(Del);
  128. 		Del = temp;
  129. 	}
  130. 	*plist = NULL;//置空指针防止野指针的产生
  131. }

四、运行测试

测试代码：

  1. int main()
  2. {
  3. 	SListNode* plist = NULL;
  4. 	SListPushBack(&plist, 1);
  5. 	SListPrint(plist);
  6. 	SListPushBack(&plist, 2);
  7. 	SListPrint(plist);
  8. 	SListPushBack(&plist, 3);
  9. 	SListPrint(plist);
  10. 	SListPopBack(&plist);
  11. 	SListPrint(plist);
  12. 	SListPopFront(&plist);
  13. 	SListPrint(plist);
  14. 	SListPopBack(&plist);
  15. 	SListPrint(plist);
  16. 	SListPushBack(&plist, 10);
  17. 	SListPrint(plist);
  18. 	SListPushFront(&plist, 100);
  19. 	SListPrint(plist);
  20. 	SListPushBack(&plist, 200);
  21. 	SListPrint(plist);
  22. 	SListPushBack(&plist, 400);
  23. 	SListPrint(plist);
  24. 	SListNode* temp = SListFind(plist, 100);
  25. 	SListEraseAfter(&temp);
  26. 	SListPrint(plist);
  27. 	temp = SListFind(plist, 200);
  28. 	SListInsertAfter(&temp, 300);
  29. 	SListPrint(plist);
  30. 	SListDestroy(&plist);
  31. 	SListPrint(plist);
  32. 	return 0;
  33. }

运行效果：

        好了，本期博客到这里又要结束了，本期博客代码量多难免有不足之处，还请各位大佬们在评论区不吝赐教！

        下期还会对链表进行详细讲解，请各位看官敬请期待~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/593737
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号