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

【数据结构】多图警告！单链表的操作实现以及原理_单链表的基本操作实验原理

作者：码创造者 | 2024-07-15 13:35:39

赞

踩

单链表的基本操作实验原理

仙人有待乘黄鹤，海客无心随白鸥。                                                                      ——李白

目录

一、单链表的基本知识

1.1单链表

​编辑 

1.2单链表的基本操作

二、单链表的实现

2.1单链表的打印

2.2单链表的头插尾插

2.3单链表的头删尾删

2.4单链表的查找

2.5单链表的特定位置增删

2.6完整实现代码

一、单链表的基本知识

1.1单链表

单链表是一种线性的数据结构，相较于顺序表，单链表进行数据操作的效率会优化很多。单链表使用任意一组存储单元来保存线性的数据，并不需要使用连续地址的存储位置，仅通过指针进行访问下一元素，。因此，单链表的物理结构并不要求像逻辑结构一样连续。

单链表的定义可以使用结构体完成

  1. typedef int SLTDataType;//数据类型
  2.  
  3. typedef struct SListNode
  4. {
  5. 	SLTDataType data;
  6. 	struct SListNode* next;//指向结构体的下一个位置，使数据链式连接
  7. }SLTNode;

1.2单链表的基本操作

单链表作为一种链式数据存储结构，能实现的操作有查看数据（打印）、增加数据（头插尾插）、删除数据（头删尾删）、插入数据、查找特定数据、删除特定位置的数据等操作。

相较于由数组模拟的顺序表而言，结构体形成的单链表无需在意容量大小，并且在插入数据的时候也不用一次次遍历整个链表。

二、单链表的实现

2.1单链表的打印

由单链表的逻辑结构可知，单链表是通过next指针指向下一个元素的，那么一个指针从头开始遍历整个链表一直到NULL，即可完成单链表的打印。话不多说，上代码

  1. void SLTPrint(SLTNode* phead)
  2. {
  3. 	SLTNode* cur = phead;//头指针
  4. 	//遍历链表打印
  5. 	while (cur)
  6. 	{
  7. 		printf("%d->", cur->data);
  8. 		cur = cur->next;
  9. 	}
  10. 	printf("NULL\n");
  11. }

2.2单链表的头插尾插

如何在原有链式结构上添加新数据？答案是看物理结构。那么到底怎么实现呢？答案还是看物理结构。

既然链表是由结构体实现的，那么对于一个要插入的数据data，我们首先要为它开辟一块结构体空间。

此时再来观察链表的物理结构，很显然我们只需改变箭头的方向（即next指向的位置）便可完成数据的插入。 

 上代码

  1. SLTNode* BuySLTNode(SLTDataType x)
  2. {
  3. 	//为新数据开辟空间
  4. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  5. 	if (newnode == NULL)
  6. 	{
  7. 		perror("malloc fail");
  8. 		return NULL;//开辟失败
  9. 	}
  10. 	newnode->data = x;
  11. 	newnode -> next = NULL;
  12. 	return newnode;
  13. }
  14.  
  15. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  16. {
  17. 	assert(pphead);
  18. 	SLTNode* newnode = BuySLTNode(x);
  19. 	//case1：空链表
  20. 	if (*pphead == NULL)
  21. 	{
  22. 		*pphead = newnode;
  23. 	}
  24. 	//case2：非空链表
  25. 	else
  26. 	{
  27. 		//找尾
  28. 		SLTNode* tail = *pphead;
  29. 		while (tail->next != NULL)
  30. 		{
  31. 			tail = tail->next;
  32. 		}
  33. 		tail->next = newnode;
  34. 	}
  35. }
  36.  
  37. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  38. {
  39. 	assert(pphead);
  40. 	SLTNode* newnode = BuySLTNode(x);
  41. 	newnode -> next = *pphead;//头插
  42. 	*pphead= newnode;//换头
  43. }

2.3单链表的头删尾删

有了上面头插尾插的经验，相信大家对头删尾删也有了初步的想法。没错，将next跳过下一个位置即可完成链表的删除，但是仍有一些细节需要注意。

特别注意的是，由于尾删时需要先找到尾节点的位置，如果我们直接将尾节点置为空，则会形成尾指针为野指针的现象，因此我们要找尾节点的上一个next并将其置为空。

看代码

  1. void SLTPopFront(SLTNode** pphead)
  2. {
  3. 	assert(*pphead);
  4. 	assert(pphead);
  5. 	SLTNode* first = *pphead;
  6. 	*pphead = first->next;
  7. 	free(first);
  8. 	first = NULL;
  9. }
  10.  
  11. void SLTPopBack(SLTNode** pphead)
  12. {
  13. 	assert(*pphead);
  14. 	assert(pphead);
  15. 	//case1:一个节点
  16. 	if ((*pphead)->next == NULL)
  17. 	{
  18. 		free(*pphead);
  19. 		*pphead = NULL;
  20. 	}
  21. 	//case2:多个节点
  22. 	else
  23. 	{
  24. 		//找尾
  25. 		SLTNode* tail = *pphead;
  26. 		//尾节点的上一个节点的next置空 不然尾节点则为野指针
  27. 		while (tail->next->next != NULL)
  28. 		{
  29. 			tail = tail->next;
  30. 		}
  31. 		free(tail->next);
  32. 		tail -> next = NULL;
  33.  
  34. 	}
  35. }

2.4单链表的查找

查找即简单遍历链表，与打印相似，在此不过多介绍，直接看代码吧。

  1. SLTNode* SListFind(SLTNode* phead, SLTDataType x)
  2. {
  3. 	SLTNode* cur = phead;
  4. 	while (cur)
  5. 	{
  6. 		if (cur->data == x)
  7. 		{
  8. 			return cur;
  9. 		}
  10. 		cur = cur->next;
  11. 	}
  12. 	return NULL;
  13. }

2.5单链表的特定位置增删

对于给定的pos位置进行增删，原理与头尾的操作相似，但是如果pos在链表中间位置，则需调整pos位置的前一个的next，当然如果pos本身就是头尾，那其实与上面的操作无异。

  1. //pos位置插入
  2. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  3. {
  4. 	assert(pphead);
  5. 	assert(pos);
  6. 	if (pos == *pphead)
  7. 	{
  8. 		SLTPushFront(pphead, x);
  9. 	}
  10. 	else
  11. 	{
  12. 		//pos的前一个位置
  13. 		SLTNode* prev = *pphead;
  14. 		while (prev->next != pos)
  15. 		{
  16. 			prev = prev->next;
  17. 		}
  18. 		SLTNode* newnode = BuySLTNode(x);
  19. 		prev->next = newnode;
  20. 		newnode->next = pos;
  21. 	}
  22. }
  23.  
  24. //pos位置删除
  25. void SListErase(SLTNode** pphead, SLTNode* pos)
  26. {
  27. 	assert(pphead);
  28. 	assert(pos);
  29. 	if (pos == *pphead)
  30. 	{
  31. 		SLTPopFront(pphead);
  32. 	}
  33. 	else
  34. 	{
  35. 		SLTNode* prev = *pphead;
  36. 		while (prev->next != pos)
  37. 		{
  38. 			prev = prev->next;
  39. 		}
  40. 		prev->next = pos->next;
  41. 		free(pos);
  42. 		pos = NULL;
  43. 	}
  44. }
  45.  
  46. //pos位置的后一个插入
  47. void SListInsertAfter(SLTNode* pos, SLTDataType x)
  48. {
  49. 	assert(pos);
  50. 	SLTNode* newnode = BuySLTNode(x);
  51. 	newnode->next = pos->next;
  52. 	pos->next = newnode;
  53. }
  54.  
  55. //pos位置的后一个删除
  56. void SListEraseAfter(SLTNode* pos)
  57. {
  58. 	assert(pos);
  59. 	assert(pos->next);
  60. 	SLTNode* del = pos->next;
  61. 	pos->next = del->next;
  62. 	free(del);
  63. 	del = NULL;
  64. }

2.6完整实现代码

  1. //SList.h 头文件
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5.  
  6. typedef int SLTDataType;
  7.  
  8. typedef struct SListNode
  9. {
  10. 	SLTDataType data;
  11. 	struct SListNode* next;
  12. }SLTNode;
  13.  
  14.  
  15. void SLTPrint(SLTNode* phead);
  16. void SLTPushBack(SLTNode** pphead, SLTDataType x);
  17. void SLTPushFront(SLTNode** pphead, SLTDataType x);
  18.  
  19. void SLTPopBack(SLTNode** pphead);
  20. void SLTPopFront(SLTNode** pphead);
  21.  
  22. SLTNode* SListFind(SLTNode* pead, SLTDataType x);
  23. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
  24. void SListErase(SLTNode** pphead, SLTNode* pos);
  25. void SListInsertAfter(SLTNode* pos, SLTDataType x);
  26. void SListEraseAfter(SLTNode* pos);
  1. //Slist.c源文件
  2.  
  3. #include "SList.h"
  4.  
  5. void SLTPrint(SLTNode* phead)
  6. {
  7. 	SLTNode* cur = phead;
  8. 	//遍历链表打印
  9. 	while (cur)
  10. 	{
  11. 		printf("%d->", cur->data);
  12. 		cur = cur->next;
  13. 	}
  14. 	printf("NULL\n");
  15. }
  16.  
  17. SLTNode* BuySLTNode(SLTDataType x)
  18. {
  19. 	//开辟空间
  20. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  21. 	if (newnode == NULL)
  22. 	{
  23. 		perror("malloc fail");
  24. 		return NULL;
  25. 	}
  26. 	newnode->data = x;
  27. 	newnode -> next = NULL;
  28. 	return newnode;
  29. }
  30.  
  31. void SLTPushBack(SLTNode** pphead, SLTDataType x)
  32. {
  33. 	assert(pphead);
  34. 	SLTNode* newnode = BuySLTNode(x);
  35. 	//case1：空链表
  36. 	if (*pphead == NULL)
  37. 	{
  38. 		*pphead = newnode;
  39. 	}
  40. 	//case2：非空链表
  41. 	else
  42. 	{
  43. 		//找尾
  44. 		SLTNode* tail = *pphead;
  45. 		while (tail->next != NULL)
  46. 		{
  47. 			tail = tail->next;
  48. 		}
  49. 		tail->next = newnode;
  50. 	}
  51. }
  52.  
  53. void SLTPushFront(SLTNode** pphead, SLTDataType x)
  54. {
  55. 	assert(pphead);
  56. 	SLTNode* newnode = BuySLTNode(x);
  57. 	newnode -> next = *pphead;//头插
  58. 	*pphead= newnode;//换头
  59. }
  60.  
  61. void SLTPopBack(SLTNode** pphead)
  62. {
  63. 	assert(*pphead);
  64. 	assert(pphead);
  65. 	//case1:一个节点
  66. 	if ((*pphead)->next == NULL)
  67. 	{
  68. 		free(*pphead);
  69. 		*pphead = NULL;
  70. 	}
  71. 	//case2:多个节点
  72. 	else
  73. 	{
  74. 		//找尾
  75. 		SLTNode* tail = *pphead;
  76. 		//尾节点的上一个节点的next置空 不然尾节点则为野指针
  77. 		while (tail->next->next != NULL)
  78. 		{
  79. 			tail = tail->next;
  80. 		}
  81. 		free(tail->next);
  82. 		tail -> next = NULL;
  83.  
  84. 	}
  85. }
  86.  
  87. void SLTPopFront(SLTNode** pphead)
  88. {
  89. 	assert(*pphead);
  90. 	assert(pphead);
  91. 	SLTNode* first = *pphead;
  92. 	*pphead = first->next;
  93. 	free(first);
  94. 	first = NULL;
  95. }
  96.  
  97. SLTNode* SListFind(SLTNode* phead, SLTDataType x)
  98. {
  99. 	SLTNode* cur = phead;
  100. 	while (cur)
  101. 	{
  102. 		if (cur->data == x)
  103. 		{
  104. 			return cur;
  105. 		}
  106. 		cur = cur->next;
  107. 	}
  108. 	return NULL;
  109. }
  110.  
  111. //pos位置插入
  112. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  113. {
  114. 	assert(pphead);
  115. 	assert(pos);
  116. 	if (pos == *pphead)
  117. 	{
  118. 		SLTPushFront(pphead, x);
  119. 	}
  120. 	else
  121. 	{
  122. 		//pos的前一个位置
  123. 		SLTNode* prev = *pphead;
  124. 		while (prev->next != pos)
  125. 		{
  126. 			prev = prev->next;
  127. 		}
  128. 		SLTNode* newnode = BuySLTNode(x);
  129. 		prev->next = newnode;
  130. 		newnode->next = pos;
  131. 	}
  132. }
  133.  
  134. //pos位置删除
  135. void SListErase(SLTNode** pphead, SLTNode* pos)
  136. {
  137. 	assert(pphead);
  138. 	assert(pos);
  139. 	if (pos == *pphead)
  140. 	{
  141. 		SLTPopFront(pphead);
  142. 	}
  143. 	else
  144. 	{
  145. 		SLTNode* prev = *pphead;
  146. 		while (prev->next != pos)
  147. 		{
  148. 			prev = prev->next;
  149. 		}
  150. 		prev->next = pos->next;
  151. 		free(pos);
  152. 		pos = NULL;
  153. 	}
  154. }
  155.  
  156. //pos位置的后一个插入
  157. void SListInsertAfter(SLTNode* pos, SLTDataType x)
  158. {
  159. 	assert(pos);
  160. 	SLTNode* newnode = BuySLTNode(x);
  161. 	newnode->next = pos->next;
  162. 	pos->next = newnode;
  163. }
  164.  
  165. //pos位置的后一个删除
  166. void SListEraseAfter(SLTNode* pos)
  167. {
  168. 	assert(pos);
  169. 	assert(pos->next);
  170. 	SLTNode* del = pos->next;
  171. 	pos->next = del->next;
  172. 	free(del);
  173. 	del = NULL;
  174. }

本章到此就结束了，希望大家可以对单链表有一个清晰的认识。

（最近压力有些大，这几天有隐隐摆烂的痕迹，要从现在找回状态，加油！）

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

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

  

闽ICP备14008679号