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

数据结构之线性表（单链表的实现）

作者：运维做开发 | 2024-08-15 09:12:34

赞

踩

数据结构之线性表（单链表的实现）

目录

一、单链表的原理

二、单链表的实现

1.单链表的定义

2.单链表的初始化

3.清空单链表

4.单链表是否为空

5.单链表的长度

6.获取指定位置 i 的元素

7.获取指定元素 e 的位置  

8.向链表中插入指定位置的元素

9.向链表中删除指定位置的元素

10.遍历链表中的元素

三、打印测试功能

1.测试

2.结果输出

3.总代码

一、单链表的原理

        本章节紧跟上一篇文章《顺序表的实现》来继续讲述线性表的一种：单链表。

        前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

         要解决这个问题，我们就得考虑一下导致这个问题的原因。为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1，2，3，…，n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

        我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到它;在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到，而这就是单链表的特点，如下图所示。

         而链表的结构则如下图所示，第一个节点的指针由头节点所指，第二个节点的指针由第一个节点所指，以此类推。

二、单链表的实现

1.单链表的定义

        定义一些功能常量和单链表的结构。

        这里需要注意的是，我给链表起别名的是一个指针，后面我们在实现链表功能的时候，我们传递函数参数的时候要传递的是一个双指针（LinkList* L）。 这是因为链表的结构使然，因为链表存储的是其他链表的指针，它是一个地址，后面我们在进行链表的增加和删除的时候，会经常涉及到指针的变化。

        如果函数的参数是本身一级指针，那么在函数内部对指针的修改将不会反映到函数外部，因为函数接收到的是指针的一个副本。使用指针的指针作为参数，则可以确保在函数内部对指针的修改能够反映到原始的指针上。

typedef  struct  Node*  LinkList;

  1. #include <iostream>
  2.  
  3. #define MAX_SIZE 20
  4. #define OK 1
  5. #define ERROR 0
  6. #define TRUE 1
  7. #define FALSE 0
  8. typedef int Status;
  9. typedef int ElemType;
  10.  
  11. typedef struct Node
  12. {
  13. 	ElemType data;
  14. 	struct Node* next;
  15. }Node;
  16.  
  17. typedef struct Node* LinkList;
2.单链表的初始化

        链表的初始化主要是为头节点分配内存空间，使它的data 和 next 都指向为 NULL，方便我们后续的操作。

  1. Status InitList(LinkList* L)
  2. {
  3. 	*L = (LinkList)malloc(sizeof(Node));
  4. 	if (*L == NULL) return ERROR;
  5. 	(*L)->data = 0;
  6. 	(*L)->next = NULL;
  7. 	return OK;
  8. }
3.清空单链表

        对链表进行清空操作，因为是用 malloc 进行分配的空间，对堆中的空间进行释放操作。

  1. Status ClearList(LinkList* L)
  2. {
  3. 	LinkList p, q;
  4.  
  5. 	p = (*L)->next;
  6. 	while (p != NULL) 
  7. 	{	
  8. 		q = p->next;
  9. 		free(p);
  10. 		p = q;
  11. 	}
  12. 	(*L)->next = NULL;
  13. 	return OK;
  14. }
4.单链表是否为空

        判断头节点指向的元素是否为空。即 next 是否为 NULL。

  1. Status isListEmpty(LinkList L)
  2. {
  3. 	if (L->next  == NULL) return TRUE;
  4. 	return FALSE;
  5. }
5.单链表的长度

        求链表的长度，定义一个变量，然后用while循环遍历链表。

  1. int ListLength(LinkList L)
  2. {
  3. 	int num{ 0 };
  4. 	LinkList temp = L->next;
  5. 	while (temp != NULL)
  6. 	{
  7. 		temp = temp->next;
  8. 		num++;
  9. 	}
  10. 	return num;
  11. }
6.获取指定位置 i 的元素

        定义一个变量，进行while操作，判断是否与指定位置 i 相同，获取其节点值。

  1. Status GetElem(LinkList L, int i, ElemType* e)
  2. {
  3. 	int num{ 1 };
  4. 	LinkList temp = L->next;
  5. 	while (temp != NULL && num < i)
  6. 	{
  7. 		temp = temp->next;
  8. 		num++;
  9. 	}	
  10. 	if (temp == NULL || num > i) return ERROR;
  11. 	*e = temp->data;
  12. }
7.获取指定元素 e 的位置  

        和上述功能类似，返回值为 int 位置。

  1. int LocateElem(LinkList L, ElemType* e)
  2. {
  3. 	int num{ 0 };
  4. 	LinkList temp = L->next;
  5. 	while (temp != NULL)
  6. 	{
  7. 		num++;
  8. 		if (temp->data = *e)
  9. 		{
  10. 			return num;
  11. 		}
  12. 		temp = temp->next;
  13. 	}
  14. 	return 0;
  15. }
8.向链表中插入指定位置的元素

          此功能为链表的难点所在，需要根据图像理解实现，如下图所示。 

      

  1. Status LinkInsert(LinkList* L, int i, ElemType e)
  2. {
  3. 	int j;
  4. 	LinkList p, s;
  5. 	p = *L;
  6. 	j = 1;
  7.  
  8. 	while (p != NULL && j < i)
  9. 	{
  10. 		p = p->next;
  11. 		++j;
  12. 	}	
  13. 	if (!p || j > i) return ERROR;
  14.  
  15. 	s = (LinkList)malloc(sizeof(Node));
  16. 	if (s == NULL) return ERROR;
  17. 	s->data = e;
  18. 	
  19. 	s->next = p->next;
  20. 	p->next = s;
  21. 	
  22. 	return OK;
  23.  
  24. }
9.向链表中删除指定位置的元素

        和上功能类似，如图所示。

  1. Status LinkDelete(LinkList* L, int i, ElemType* e)
  2. {
  3. 	int j;
  4. 	LinkList p, s;
  5. 	j = 1;
  6. 	p = (*L);
  7.  	while (p != NULL && j < i)
  8. 	{
  9. 		p = p->next;
  10. 		++j;
  11. 	}
  12. 	if (!p || j > i) return ERROR;
  13.  
  14. 	s = p->next;
  15. 	p->next = s->next;
  16. 	*e = s->data;
  17. 	free(s);
  18. 	return OK;
  19. }
10.遍历链表中的元素

        功能比较简单，通过不断遍历打印其节点的data值。

  1. Status visit(ElemType e)
  2. {
  3. 	printf("%d->", e);
  4. 	return OK;
  5. }
  6. Status ListTraverse(LinkList L)
  7. {
  8. 	LinkList p = L->next;
  9. 	while (p != NULL)
  10. 	{
  11. 		visit(p->data);
  12. 		p = p->next;
  13. 	} 
  14. 	printf("\n");
  15. 	return OK;
  16. }

三、打印测试功能

1.测试

        测试主要为测试以上的功能是否可以实现。

  1. int TestSingleList()
  2. {
  3. 	LinkList L;
  4. 	ElemType e;
  5. 	Status ret;
  6. 	int j, k;
  7. 	// 初始化
  8. 	ret = InitList(&L);
  9. 	printf("初始化长度：%d\n", ListLength(L));
  10.  
  11. 	for(j = 1; j <= 5; j++)
  12. 	{
  13. 		ret = LinkInsert(&L, 1, j);
  14. 	}
  15. 	printf("插入5个元素后：");
  16. 	ListTraverse(L);
  17. 	ret = isListEmpty(L);
  18. 	printf("是否为空，%d\n", ret);
  19. 	ret = ClearList(&L);
  20. 	printf("清空后的长度：%d\n", ListLength(L));
  21. 	printf("是否为空，%d\n", ret);
  22. 	for (j = 1; j <= 10; j++)
  23. 	{
  24. 		ret = LinkInsert(&L, j, j);
  25. 	}
  26. 	printf("插入10个元素后：");
  27. 	ListTraverse(L);
  28.  
  29. 	LinkInsert(&L, 3, 100);
  30. 	printf("在第2个节点后面增加元素100：");
  31. 	ListTraverse(L);
  32.  
  33. 	LinkDelete(&L, 2, &e);
  34. 	printf("删除第二个节点,节点元素为%d :", e);
  35. 	ListTraverse(L);
  36.  
  37. 	ClearList(&L);
  38.  
  39. 	return 0;
  40. }
2.结果输出

           结果输出如图所示：

3.总代码

        总代码如下：

  1.  
  2.  
  3. #include <iostream>
  4.  
  5. #define MAX_SIZE 20
  6. #define OK 1
  7. #define ERROR 0
  8. #define TRUE 1
  9. #define FALSE 0
  10. typedef int Status;
  11. typedef int ElemType;
  12.  
  13. typedef struct Node
  14. {
  15. 	ElemType data;
  16. 	struct Node* next;
  17. }Node;
  18.  
  19. typedef struct Node* LinkList;
  20.  
  21. Status visit(ElemType e)
  22. {
  23. 	printf("%d->", e);
  24. 	return OK;
  25. }
  26.  
  27. Status InitList(LinkList* L)
  28. {
  29. 	*L = (LinkList)malloc(sizeof(Node));
  30. 	if (*L == NULL) return ERROR;
  31. 	(*L)->data = 0;
  32. 	(*L)->next = NULL;
  33. 	return OK;
  34. }
  35.  
  36. Status ClearList(LinkList* L)
  37. {
  38. 	LinkList p, q;
  39.  
  40. 	p = (*L)->next;
  41. 	while (p != NULL) 
  42. 	{	
  43. 		q = p->next;
  44. 		free(p);
  45. 		p = q;
  46. 	}
  47. 	(*L)->next = NULL;
  48. 	return OK;
  49. }
  50.  
  51. Status isListEmpty(LinkList L)
  52. {
  53. 	if (L->next  == NULL) return TRUE;
  54. 	return FALSE;
  55. }
  56.  
  57.  
  58. int ListLength(LinkList L)
  59. {
  60. 	int num{ 0 };
  61. 	LinkList temp = L->next;
  62. 	while (temp != NULL)
  63. 	{
  64. 		temp = temp->next;
  65. 		num++;
  66. 	}
  67. 	return num;
  68. }
  69.  
  70. Status GetElem(LinkList L, int i, ElemType* e)
  71. {
  72. 	int num{ 1 };
  73. 	LinkList temp = L->next;
  74. 	while (temp != NULL && num < i)
  75. 	{
  76. 		temp = temp->next;
  77. 		num++;
  78. 	}	
  79. 	if (temp == NULL || num > i) return ERROR;
  80. 	*e = temp->data;
  81. }
  82.  
  83. int LocateElem(LinkList L, ElemType* e)
  84. {
  85. 	int num{ 0 };
  86. 	LinkList temp = L->next;
  87. 	while (temp != NULL)
  88. 	{
  89. 		num++;
  90. 		if (temp->data = *e)
  91. 		{
  92. 			return num;
  93. 		}
  94. 		temp = temp->next;
  95. 	}
  96. 	return 0;
  97. }
  98.  
  99. Status LinkInsert(LinkList* L, int i, ElemType e)
  100. {
  101. 	int j;
  102. 	LinkList p, s;
  103. 	p = *L;
  104. 	j = 1;
  105.  
  106. 	while (p != NULL && j < i)
  107. 	{
  108. 		p = p->next;
  109. 		++j;
  110. 	}	
  111. 	if (!p || j > i) return ERROR;
  112.  
  113. 	s = (LinkList)malloc(sizeof(Node));
  114. 	if (s == NULL) return ERROR;
  115. 	s->data = e;
  116. 	
  117. 	s->next = p->next;
  118. 	p->next = s;
  119. 	
  120. 	return OK;
  121.  
  122. }
  123.  
  124. Status LinkDelete(LinkList* L, int i, ElemType* e)
  125. {
  126. 	int j;
  127. 	LinkList p, s;
  128. 	j = 1;
  129. 	p = (*L);
  130.  	while (p != NULL && j < i)
  131. 	{
  132. 		p = p->next;
  133. 		++j;
  134. 	}
  135. 	if (!p || j > i) return ERROR;
  136.  
  137. 	s = p->next;
  138. 	p->next = s->next;
  139. 	*e = s->data;
  140. 	free(s);
  141. 	return OK;
  142. }
  143.  
  144. Status ListTraverse(LinkList L)
  145. {
  146. 	LinkList p = L->next;
  147. 	while (p != NULL)
  148. 	{
  149. 		visit(p->data);
  150. 		p = p->next;
  151. 	} 
  152. 	printf("\n");
  153. 	return OK;
  154. }
  155.  
  156. Status CreateListHead(LinkList* L,int n)
  157. {
  158. 	LinkList p;
  159. 	srand((unsigned)time(0));
  160. 	*L = (LinkList)malloc(sizeof(Node));
  161. 	if (*L == NULL) return ERROR;
  162. 	(*L)->next = NULL;
  163. 	for (int i = 0; i < n; i++)
  164. 	{
  165. 		p = (LinkList)malloc(sizeof(Node));
  166. 		if (p == NULL) return ERROR;
  167. 		p->data = rand() % 100 + 1;
  168. 		p->next = (*L)->next;
  169. 		(*L)->next = p;
  170. 	}
  171. 	return OK;
  172. }
  173.  
  174. Status CreateListTail(LinkList* L,int n)
  175. {
  176. 	LinkList p, r;
  177. 	srand((unsigned)time(0));
  178. 	*L = (LinkList)malloc(sizeof(Node));
  179. 	if (*L == NULL) return ERROR;
  180. 	(*L)->next = NULL;
  181. 	r = (*L);
  182. 	for (int i = 0; i < n; i++)
  183. 	{
  184. 		p = (LinkList)malloc(sizeof(Node));
  185. 		if (p == NULL) return ERROR;
  186. 		p->data = rand() % 100 + 1;
  187. 		r->next = p;
  188. 		r = p;
  189. 	}
  190. 	return OK;
  191. }
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199. int TestSingleList()
  200. {
  201. 	LinkList L;
  202. 	ElemType e;
  203. 	Status ret;
  204. 	int j, k;
  205. 	// 初始化
  206. 	ret = InitList(&L);
  207. 	printf("初始化长度：%d\n", ListLength(L));
  208.  
  209. 	for(j = 1; j <= 5; j++)
  210. 	{
  211. 		ret = LinkInsert(&L, 1, j);
  212. 	}
  213. 	printf("插入5个元素后：");
  214. 	ListTraverse(L);
  215. 	ret = isListEmpty(L);
  216. 	printf("是否为空，%d\n", ret);
  217. 	ret = ClearList(&L);
  218. 	printf("清空后的长度：%d\n", ListLength(L));
  219. 	printf("是否为空，%d\n", ret);
  220. 	for (j = 1; j <= 10; j++)
  221. 	{
  222. 		ret = LinkInsert(&L, j, j);
  223. 	}
  224. 	printf("插入10个元素后：");
  225. 	ListTraverse(L);
  226.  
  227. 	LinkInsert(&L, 3, 100);
  228. 	printf("在第2个节点后面增加元素100：");
  229. 	ListTraverse(L);
  230.  
  231. 	LinkDelete(&L, 2, &e);
  232. 	printf("删除第二个节点,节点元素为%d :", e);
  233. 	ListTraverse(L);
  234.  
  235. 	ClearList(&L);
  236.  
  237. 	return 0;
  238. }
  239.  
  240. int main()
  241. {
  242. 	return TestSingleList();
  243. }
  244.  
  245.

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号