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

【数据结构】链表(单链表实现+测试+原码)

作者：编程冒险家 | 2024-01-31 17:35:44

赞

踩

【数据结构】链表(单链表实现+测试+原码)

1.链表

1.1 链表的概念及结构

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

现实中：链表就像是一列动车，一节连着一节
数据结构中的链表

 注意:
1.从上图可看出，链式结构在逻辑上是连续的。但是在物理上不一定连续

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

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

2  链表的实现

SList.h(头文件引用)

  1. #pragma once
  2. #define _CRT_SECURE_NO_WARNINGS 1
  3. #include <stdio.h>
  4. #include <malloc.h>
  5. #include <assert.h>
  6.  
  7. typedef int SLTDataType;
  8.  
  9. typedef struct SListNode
  10. {
  11. 	SLTDataType data;
  12. 	struct SListNode* next;
  13. }SLTNode;
  14.  
  15. void SLTPrint(SLTNode* phead);
  16.  
  17. SLTNode* BuySListNode(SLTDataType x);
  18. void SLTPushBack(SLTNode ** pphead,SLTDataType x);
  19. void SLTPushFront(SLTNode** pphead, SLTDataType x);
  20. void SLTPopBack(SLTNode** pphead);
  21. void SLTPopFront(SLTNode** pphead);
  22.  
  23. //作业
  24. SLTNode* SLTFind(SLTNode* pphead,SLTDataType x);
  25.  
  26. //在pos之前插入x
  27. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
  28. //在之后插入x
  29. void SLTInsertAfter( SLTNode* pos, SLTDataType x);
  30. //删除pos位置
  31. void SLTErase(SLTNode** pphead, SLTNode* pos);
  32. //删除pos后一个位置
  33. void SLTEraseAfter(SLTNode* phead,SLTNode* pos);

SList.c(函数功能的实现)

  1. #include "SList.h"
  2.  
  3. void SLTPrint(SLTNode* phead)
  4. {
  5. 	SLTNode* cur = phead;
  6. 	while (cur != NULL)
  7. 	{
  8. 		printf("%d->", cur->data);
  9. 		cur = cur->next;
  10. 	}
  11. 	printf("NULL\n");
  12. }
  13.   
  14.  
  15. SLTNode* BuySListNode(SLTDataType x)
  16. {
  17. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
  18. 	if (newnode == NULL)
  19. 	{
  20. 		perror("malloc fail");
  21. 		exit(-1);
  22. 	}
  23. 	newnode->data = x;
  24. 	newnode->next = NULL;
  25. 	return newnode;
  26. }
  27.  
  28. void SLTPushBack(SLTNode** pphead,SLTDataType x) //尾插
  29. 	//需要用二级指针，结构体指针（地址），传递实参
  30. {
  31. 	assert(pphead);	//空地址不正确
  32. 	//assert(*pphead);//空链表可以尾插
  33.  
  34. 	SLTNode* newnode = BuySListNode(x);
  35. 	if (*pphead == NULL)	//如果为空，则指向新创建元素
  36. 	{
  37. 		  *pphead = newnode;
  38. 	}
  39. 	else	//不为空则遍历到尾部插入数据
  40. 	{
  41. 		//需要用指针结构体指针，改变结构体，传递形参
  42. 		SLTNode* tail = *pphead;
  43. 		while (tail->next != 0)
  44. 		{
  45. 			tail = tail->next;
  46. 		}
  47. 		tail->next = newnode;
  48. 	}
  49. }
  50.  
  51. void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
  52. {
  53. 	assert(pphead);	//空地址不正确
  54. 	assert(*pphead);//空链表不可以前删
  55.  
  56. 	SLTNode* newnode = BuySListNode(x);
  57.  
  58. 	newnode->next = *pphead;
  59. 	*pphead = newnode;
  60. }
  61.  
  62. void SLTPopBack(SLTNode** pphead)	//尾删
  63. {
  64. 	// 1.空
  65. 	assert(*pphead != NULL);
  66. 	//	2.一个节点
  67. 	if ((*pphead)->next == NULL)
  68. 	{
  69. 		free(*pphead);
  70. 		*pphead = NULL;
  71. 	}
  72. 	//	3.多个节点
  73. 	else
  74. 	{
  75. 		SLTNode* tail = *pphead;
  76. 		while (tail->next->next)
  77. 		{
  78. 			tail = tail->next;
  79. 		} 
  80. 		free(tail->next);
  81. 		tail->next = NULL;
  82. 	}
  83. }
  84.  
  85. void SLTPopFront(SLTNode** pphead)	//头删
  86. {
  87. 	assert(pphead);
  88. 	assert(*pphead);
  89.  
  90. 	SLTNode* newhead = (*pphead)->next;
  91. 	free(*pphead);
  92. 	*pphead = newhead;
  93. }
  94.  
  95. SLTNode* SLTFind(SLTNode*phead, SLTDataType x)
  96. {
  97. 	assert(phead);
  98. 	SLTNode* tail = phead;
  99. 	while (tail)
  100. 	{
  101. 		if (tail->data == x)
  102. 		{
  103. 			return tail;
  104. 		}
  105. 		tail = tail->next;
  106. 	}
  107. 	return NULL;
  108. 	while (tail->data != x)
  109. 	{
  110. 		tail = tail->next;
  111. 		if (tail->next==NULL&&tail->data!=x)
  112. //下一个元素的值指向NULL并且数据值不等于要查找的数，既已遍历查找完毕并且没有找到数据
  113. 		{
  114. 			printf(" 输入错误，找不到输入值\n");
  115. 			return 0;
  116. 		}
  117. 	}
  118. 	printf("已找到：%d\n", x);
  119. 	return tail;
  120. }
  121.  
  122. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
  123. {
  124. 	//有错误版本 ，地址近似一样(bug)find函数调试就好了
  125.  
  126. 	assert(pos);    
  127. 	assert(*pphead);
  128. 	if (pos == *pphead)
  129. 	{
  130. 		SLTPushFront(pphead, x); 
  131. 	}
  132. 	else
  133. 	{
  134. 		SLTNode* tail = *pphead;
  135. 		//在pos之前插入x
  136. 		while (tail->next != pos)
  137. 		{
  138. 			tail =  tail->next;
  139. 		}
  140. 		SLTNode* newnode = BuySListNode(x);
  141. 		tail->next = newnode;
  142. 		newnode->next = pos;
  143. 	}
  144.  
  145. } 
  146.  
  147. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
  148. {
  149. 	assert(pos);
  150. 	assert(pos->next);
  151.  
  152. 	SLTNode* newnode = BuySListNode(x);
  153. 	//注意顺序，不然会照成死循环（画图）
  154. 	newnode->next = pos->next;
  155. 	pos->next = newnode;
  156.  
  157. }
  158.  
  159. void SLTErase(SLTNode** pphead, SLTNode* pos)
  160. {
  161. 	assert(pos);
  162.  
  163. 	if (pos == *pphead)
  164. 	{
  165. 		SLTPopFront(pphead);
  166. 	}
  167. 	else
  168. 	{
  169. 		SLTNode* prev = *pphead;
  170. 		while (prev->next != pos)
  171. 		{
  172. 			prev = prev->next;
  173. 		}
  174.  
  175. 		prev->next = pos->next;
  176. 		free(pos);
  177. 	}
  178.  
  179. }
  180.  
  181. void SLTEraseAfter(SLTNode* phead,SLTNode* pos)
  182. {
  183. 	//assert(pos);
  184. 	//检查是否为尾节点
  185. 	//assert(pos->next);
  186. 	SLTNode* posNext;	//纪录要删除的节点
  187. 	//避免丢失无法Free
  188. 	posNext = pos->next;
  189. 	//pos->next = pos->next->next;
  190. 	pos->next = posNext->next;
  191. 	free(posNext);
  192. 	posNext = NULL;
  193. }

Test_1_16(各种功能的调试、函数、以及面试OJ题的接口实现)

  1. #include "SList.h"
  2.  
  3. void TestSList1()
  4. {
  5. 	int n;
  6. 	printf("请输入链表长度：");
  7. 	scanf("%d", &n);
  8. 	printf("\n请依次输入每个节点的值：");
  9. 	SLTNode* plist = NULL;	//第一个元素的地址 
  10. 	for (size_t i = 0; i < n; i++)
  11. 	{
  12. 		int val;
  13. 		scanf("%d", &val);
  14. 		SLTNode* newnode = BuySListNode(val);
  15.  
  16. 		//头插
  17. 		newnode->next = plist;
  18. 		plist = newnode;
  19. 	}
  20. 	SLTPrint(plist);
  21. 	SLTPushBack(&plist, 5);
  22. 	SLTPrint(plist);
  23. }
  24.  
  25. void TestSList()
  26. {
  27. 	SLTNode* plist = NULL;
  28. 	SLTPushBack(&plist, 1);
  29. 	SLTPushBack(&plist, 2);
  30. 	SLTPushBack(&plist, 3);
  31. 	SLTPushBack(&plist, 4);
  32. 	SLTPushBack(&plist, 5);
  33. 	SLTPrint(plist);
  34.  
  35. 	SLTPushFront(&plist, 10);
  36. 	SLTPushFront(&plist, 20);
  37. 	SLTPushFront(&plist, 30);
  38. 	SLTPushFront(&plist, 40);
  39. 	SLTPrint(plist);
  40.  
  41. }
  42.  
  43. void TestSList3()
  44. {
  45. 	SLTNode* plist = NULL;
  46. 	SLTPushBack(&plist, 1);
  47. 	SLTPushBack(&plist, 2);
  48. 	SLTPushBack(&plist, 3);
  49. 	SLTPushBack(&plist, 4);
  50. 	SLTPushBack(&plist, 5);
  51. 	SLTPrint(plist);
  52.  
  53. 	SLTPopBack(&plist);
  54. 	SLTPrint(plist);
  55. 	SLTPopBack(&plist);
  56. 	SLTPrint(plist);
  57. 	SLTPopBack(&plist);
  58. 	SLTPrint(plist);
  59. 	SLTPopBack(&plist);
  60. 	SLTPrint(plist);
  61. 	SLTPopBack(&plist);
  62. 	SLTPrint(plist);
  63. 	SLTPopBack(&plist);
  64. 	SLTPrint(plist);
  65.  
  66. }
  67.  
  68. void TestSList4()
  69. {
  70. 	SLTNode* plist = NULL;
  71. 	SLTPushBack(&plist, 1);
  72. 	SLTPushBack(&plist, 2);
  73. 	SLTPushBack(&plist, 3);
  74. 	SLTPushBack(&plist, 4);
  75. 	SLTPushBack(&plist, 5);
  76. 	SLTPrint(plist);
  77. 	//SLTPopFront(&plist);
  78. 	//SLTPopFront(&plist);
  79. 	//SLTPrint(plist);
  80. 	SLTFind(plist, 1);
  81. 	SLTFind(plist, 2);
  82. 	SLTFind(plist, 3);
  83. 	SLTFind(plist, 4);
  84. 	SLTFind(plist, 5);
  85. 	SLTFind(plist, 0);
  86. }
  87.  
  88. void TestSlist5()
  89. {
  90. 	SLTNode* plist = NULL;
  91. 	SLTPushBack(&plist, 1);
  92. 	SLTPushBack(&plist, 2);
  93. 	SLTPushBack(&plist, 3);
  94. 	SLTPushBack(&plist, 4);
  95. 	SLTPushBack(&plist, 5);
  96. 	SLTPrint(plist);
  97.  
  98.  
  99. 	SLTNode* pos = SLTFind(plist,4);
  100. 	if (pos)
  101. 		pos->data = 20;
  102. 	//在pos之前插入x
  103. 	//SLTInsert(&plist, pos, 5);
  104. 	SLTPrint(plist);
  105.  
  106. }
  107.  
  108. void TestSlist6()
  109. {
  110. 	SLTNode* plist = NULL;
  111. 	SLTPushBack(&plist, 1);
  112. 	SLTPushBack(&plist, 2);
  113. 	SLTPushBack(&plist, 3);
  114. 	SLTPushBack(&plist, 4);
  115. 	SLTPushBack(&plist, 5);
  116. 	SLTPrint(plist);
  117.  
  118.  
  119. 	SLTNode* pos = SLTFind(plist, 4);
  120. 	SLTInsert(&plist, pos, 90);
  121. 	SLTPrint(plist);
  122. }
  123.  
  124. void TestSlist7()
  125. {
  126. 	SLTNode* plist = NULL;
  127. 	SLTPushBack(&plist, 1);
  128. 	SLTPushBack(&plist, 2);
  129. 	SLTPushBack(&plist, 3);
  130. 	SLTPushBack(&plist, 4);
  131. 	SLTPushBack(&plist, 5);
  132. 	SLTPrint(plist);
  133.  
  134. 	SLTNode* pos = SLTFind(plist, 4);
  135. 	SLTInsertAfter(pos, 90);
  136. 	SLTPrint(plist);
  137. }
  138.  
  139. void TestSlist8()
  140. {
  141. 	SLTNode* plist = NULL;
  142. 	SLTPushBack(&plist, 1);
  143. 	SLTPushBack(&plist, 2);
  144. 	SLTPushBack(&plist, 3);
  145. 	SLTPushBack(&plist, 4);
  146. 	SLTPushBack(&plist, 5);
  147. 	SLTPrint(plist);
  148.  
  149. 	SLTNode* pos = SLTFind(plist, 4);
  150. 	SLTErase(&plist,pos);
  151. 	SLTPrint(plist);
  152. }
  153.  
  154. void TestSlist9()
  155. {
  156. 	SLTNode* plist = NULL;
  157. 	SLTPushBack(&plist, 1);
  158. 	SLTPushBack(&plist, 2);
  159. 	SLTPushBack(&plist, 3);
  160. 	SLTPushBack(&plist, 4);
  161. 	SLTPushBack(&plist, 5);
  162. 	SLTPrint(plist);
  163.  
  164. 	SLTNode* pos = SLTFind(plist, 4);
  165. 	SLTEraseAfter(&plist, pos);
  166. 	SLTPrint(plist);
  167. }
  168.  
  169. struct SListNode* removeElement()
  170. {
  171. 	;
  172. }
  173.  
  174. struct ListNode {
  175. 	int val;
  176. 	struct ListNode* next;
  177. 	
  178. };
  179.  
  180. //
  181. //struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
  182. //{
  183. //	struct ListNode* first = pListHead;
  184. //	struct ListNode* tail = pListHead;
  185. //
  186. //	while (first->next)
  187. //	{
  188. //		while (k>0&&first->next)
  189. //		{
  190. //			k--;
  191. //			first = first->next;
  192. //		}
  193. //		if (first->next==NULL)
  194. //		{
  195. //			return tail;
  196. //		}
  197. //		tail = tail->next;
  198. //		first = first->next;
  199. //	}
  200. //	//tail=tail->next;
  201. //	return tail->next;
  202. //}
  203.  
  204. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
  205. {
  206. 	if (pListHead == NULL)
  207. 	{
  208. 		return pListHead;
  209. 	}
  210. 	struct ListNode* first = pListHead;
  211. 	struct ListNode* tail = pListHead;
  212.  
  213. 	while (first->next)
  214. 	{
  215. 		while (k > 0 && first->next)
  216. 		{
  217. 			k--;
  218. 			first = first->next;
  219. 			//if (first->next == NULL && k > 0)
  220. 			//{
  221. 			//	return NULL;
  222. 			//}
  223. 		}
  224. 		if (first->next == NULL&&k==1)
  225. 		{
  226. 			return tail;
  227. 		}
  228. 		else
  229. 		{
  230. 			return NULL;
  231. 		}
  232. 		tail = tail->next;
  233. 		first = first->next;
  234. 	}
  235. 	//tail=tail->next;
  236. 	return tail->next;
  237. }
  238.  
  239. int main()
  240. {
  241. 	struct SListNode* n1 = (struct ListNode*)malloc(sizeof(struct SListNode));
  242. 	struct SListNode* n2 = (struct ListNode*)malloc(sizeof(struct SListNode));
  243. 	struct SListNode* n3 = (struct ListNode*)malloc(sizeof(struct SListNode));
  244. 	struct SListNode* n4 = (struct ListNode*)malloc(sizeof(struct SListNode));
  245. 	struct SListNode* n5 = (struct ListNode*)malloc(sizeof(struct SListNode));
  246.  
  247. 	n1->data = 1;
  248. 	n2->data = 2;
  249. 	n3->data = 3;
  250. 	n4->data = 4;
  251. 	n5->data = 5;
  252.  
  253. 	n1->next = n2;
  254. 	n2->next = n3;
  255. 	n3->next = n4;
  256. 	n4->next = n5;
  257. 	n5->next = NULL;
  258.  
  259. 	FindKthToTail(n1, 6);
  260. 	//TestSList1();
  261. 	//TestSList3();
  262. 	//TestSlist5();
  263. 	//TestSlist7();
  264. 	//TestSlist8();
  265. 	//TestSlist9();
  266.  
  267. 	/*struct SListNode* n1 = (struct ListNode*)malloc(sizeof(struct SListNode));
  268. 	struct SListNode* n2 = (struct ListNode*)malloc(sizeof(struct SListNode));
  269. 	struct SListNode* n3 = (struct ListNode*)malloc(sizeof(struct SListNode));
  270. 	struct SListNode* n4 = (struct ListNode*)malloc(sizeof(struct SListNode));
  272. 	n1->data = 7;
  273. 	n2->data = 7;
  274. 	n3->data = 7;
  275. 	n4->data = 7;
  277. 	n1->next = n2;
  278. 	n2->next = n3;
  279. 	n3->next = n4;
  280. 	n4->next = NULL;
  282. 	struct SListNode* head = removeElement(n1, 7);
  283. 	return 0;*/
  284.  
  285. }
  286.  
  287. // 
  288. // 
  289. // 
  290. // 
  291. //int nums1[6] = { 1,2,3,0,0,0 };
  292. //int nums1Size = 6;
  293. //int m = 3;
  294. //int nums2[3] = { 2,5,6 };
  295. //int nums2Size = 3;
  296. //int n = 3;
  297.  
  298. int nums1[1];
  299. int m = 0;
  300. int nums2[1] = {1};
  301. int n = 1;
  302. //	int p1 = m - 1, p2 = n - 1;
  303. //	int tail = m + n - 1;
  304. //	int cur;
  305. //	while (p1 > -1 || p2 > -1)
  306. //	{
  307. //		if (p1 == -1)
  308. //		{
  309. //			cur = nums2[p2--];
  310. //		}
  311. //		else if (p2 == -1)
  312. //		{
  313. //			cur = nums1[p1--];
  314. //		}
  315. //		else if (nums1[p1] > nums2[p2])
  316. //		{
  317. //			cur = nums1[p1--];
  318. //		}
  319. //		else
  320. //		{
  321. //			cur = nums2[p2--];
  322. //		}
  323. //		nums1[tail--] = cur;
  324. //	}

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

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

  

闽ICP备14008679号