• [数据结构初阶]一文轻松学链表

    链表的概念及结构

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

     

     

    链表的分类

    实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

    单向或者双向

    带头或者不带头 

    循环或者非循环

    链表的实现  

    SList.h

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7. typedef struct SListNode
    8. {
    9. 	SLTDataType data;
    10. 	struct SListNode* next;
    11. }SLTNode;
    12.  
    13. void SListPrint(SLTNode* phead);
    14.  
    15. void SListPushBack(SLTDataType** phead, SLTDataType x);
    16. void SListPushFront(SLTDataType** phead, SLTDataType x);
    17.  
    18.  
    19. void SListPopBack(SLTNode** pphead);
    20. void SListPopFront(SLTNode** pphead);
    21.  
    22. SLTNode* BuySListNode(SLTDataType x);
    23.  
    24. SLTDataType* SListFind(SLTNode* phead, SLTDataType x);
    25. void SListModify(SLTNode* phead, SLTDataType x, SLTDataType y);
    26. void SListFrontPush(SLTNode** pphead, SLTDataType x, SLTDataType y);
    27. void SListBackPush(SLTNode** pphead, SLTDataType x, SLTDataType y);
    28.  
    29. void SListPop(SLTNode** pphead, SLTDataType x);
    30.  
    31. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
    32. void SListErase(SLTNode** pphead, SLTNode* pos);

    SList.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5. #include"SList.h"
    6. void SListPrint(SLTNode* phead)
    7. {
    8. 	SLTNode* cur = phead;
    9. 	while (cur != NULL)
    10. 	{
    11. 		printf("%d->", cur->data);
    12. 		cur = cur->next;
    13. 	}
    14.  
    15. 	printf("null\n");
    16. }
    17.  
    18.  
    19. void SListPushBack(SLTDataType** pphead, SLTDataType x)
    20. {
    21. 	assert(pphead);
    22. 	SLTNode* newnode = BuySListNode(x);
    23. 	
    24. 	if (*pphead == NULL)
    25. 	{
    26. 		*pphead = newnode;
    27. 	}
    28. 	else
    29. 	{
    30. 		SLTNode* tail = *pphead;
    31. 		while (tail->next != NULL)
    32. 		{
    33. 			tail = tail->next;
    34. 		}
    35. 		tail->next = newnode;
    36. 	}
    37. }
    38.  
    39. SLTNode* BuySListNode(SLTDataType x)
    40. {
    41. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    42. 	assert(newnode);
    43. 	newnode->data = x;
    44. 	newnode->next = NULL;
    45. 	return newnode;
    46. }
    47. void SListPushFront(SLTDataType** pphead, SLTDataType x)
    48. {
    49. 	assert(pphead);
    50. 	SLTNode* newnode = BuySListNode(x);
    51. 	newnode->next = *pphead;
    52. 	*pphead = newnode;
    53. }
    54.  
    55. void SListPopBack(SLTNode** pphead)
    56. {
    57. 	assert(pphead);
    58.  
    59. 	assert(*pphead);
    60. 	if ((*pphead)->next == NULL)
    61. 	{
    62. 		free(*pphead);
    63. 		*pphead = NULL;
    64. 	}
    65. 	else
    66. 	{
    67. 		SLTNode* tail = *pphead;
    68. 		/*SLTNode* tailPrev = NULL;
    70. 		while (tail->next != NULL)
    71. 		{
    72. 			tailPrev = tail;
    73. 			tail = tail->next;
    74. 		}
    75. 		free(tail);
    76. 		tailPrev->next = NULL;*/
    77. 		while (tail->next->next != NULL)
    78. 		{
    79. 			tail = tail->next;
    80. 		}
    81. 		free(tail->next);
    82. 		tail->next = NULL;
    83. 	}
    84. }
    85. void SListPopFront(SLTNode** pphead)
    86. {
    87. 	assert(pphead);
    88. 	assert(*pphead);
    89. 	SLTNode* next = (*pphead)->next;
    90. 	free(*pphead);
    91. 	*pphead = next;
    92. }
    93.  
    94. SLTDataType* SListFind(SLTNode* phead, SLTDataType x)
    95. {
    96. 	SLTNode* cur = phead;
    97. 	while (cur)
    98. 	{
    99. 		if (cur->data == x)
    100. 		{
    101. 			return cur;
    102. 		}
    103. 		cur = cur->next;
    104. 	}
    105. 	return NULL;
    106. }
    107. void SListModify(SLTNode* phead, SLTDataType x, SLTDataType y)
    108. {
    109. 	SLTNode* ret = SListFind(phead, x);
    110. 	if (ret)
    111. 	{
    112. 		ret->data = y;
    113. 	}
    114. }
    115. void SListFrontPush(SLTNode** pphead, SLTDataType x, SLTDataType y)
    116. {
    117. 	assert(pphead);
    118. 	assert(*pphead);
    119. 	SLTNode* pos = SListFind(*pphead, x);
    120. 	if (pos)
    121. 	{
    122. 		SListInsert(pphead, pos, y);
    123. 	}
    124. }
    125.  
    126. void SListBackPush(SLTNode** pphead, SLTDataType x, SLTDataType y)
    127. {
    128. 	assert(pphead);
    129. 	assert(*pphead);
    130. 	SLTNode* pos = SListFind(*pphead, x);
    131. 	if (pos)
    132. 	{
    133. 		if (pos == *pphead)
    134. 		{
    135. 			SListPushBack(pphead, x);
    136. 		}
    137. 		else
    138. 		{
    139. 			SLTNode* newnode = BuySListNode(x);
    140. 			newnode->next = pos->next;
    141. 			pos->next = newnode;
    142. 			newnode->data = y;
    143. 		}
    144. 	}
    145. }
    146.  
    147. void SListPop(SLTNode** pphead, SLTDataType x)
    148. {
    149. 	assert(pphead);
    150. 	assert(*pphead);
    151. 	SLTNode* pos = SListFind(*pphead, x);
    152. 	if (pos)
    153. 	{
    154. 		SListErase(pphead, pos);
    155. 	}
    156. }
    157.  
    158. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    159. {
    160. 	assert(pos);
    161. 	assert(pphead);
    162. 	if (pos == *pphead)
    163. 	{
    164. 		SListPushFront(pphead, x);
    165. 	}
    166. 	else
    167. 	{
    168. 		SLTNode* prev = *pphead;
    169. 		while (prev->next != pos )
    170. 		{
    171. 			prev = prev->next;
    172. 		}
    173. 		SLTNode* newnode = BuySListNode(x);
    174. 		prev->next = newnode;
    175. 		newnode->next = pos;		
    176. 	}
    177. }
    178. void SListErase(SLTNode** pphead, SLTNode* pos)
    179. {
    180. 	assert(pphead);
    181. 	assert(pos);
    182. 	if (*pphead == pos)
    183. 	{
    184. 		SListPopFront(pphead);
    185. 	}
    186. 	else
    187. 	{
    188. 		SLTNode* prev = *pphead;
    189. 		while (prev->next != pos)
    190. 		{
    191. 			prev = prev->next;
    192. 		}
    193. 		prev->next = pos->next;
    194. 		free(pos);
    195. 	}
    196. }

    Frist.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include"SList.h"
    4. #include
    5.  
    6. void menu()
    7. {
    8. 	printf("*****************************************************************\n");
    9. 	printf("1、尾插      2、头插\n");
    10. 	printf("3、尾删      4、头删\n");
    11. 	printf("5、前面插    6、后面插\n");
    12. 	printf("7、任意删    8、修改\n");
    13. 	printf("9、打印     -1、退出\n");
    14.  
    15. 	printf("*****************************************************************\n");
    16.  
    17. }
    18.  
    19. void TestSList1()
    20. {
    21. 	SLTNode* n1 = NULL;
    22. 	/*SLTNode* n1 = (SLTNode*)malloc(sizeof(SLTNode));
    23. 	assert(n1);*/
    24. 	//SLTNode* n2 = (SLTNode*)malloc(sizeof(SLTNode));
    25. 	//assert(n2);
    26. 	//SLTNode* n3 = (SLTNode*)malloc(sizeof(SLTNode));
    27. 	//assert(n3);
    28. 	//SLTNode* n4 = (SLTNode*)malloc(sizeof(SLTNode));
    29. 	//assert(n4);
    30. 	//n1->data = 1;
    31. 	//n2->data = 2;
    32. 	//n3->data = 3;
    33. 	//n4->data = 4;
    34. 	//n1->next = n2;
    35. 	//n2->next = n3;
    36. 	//n3->next = n4;
    37. 	//n4->next = NULL;
    38. 	SListPushFront(&n1, 1);
    39.  
    40. 	SListPushBack(&n1, 5);
    41.  
    42. 	SListPushBack(&n1, 2);
    43. 	SListPushFront(&n1, 1);
    44.  
    45. 	
    46.  
    47. 	SListPrint(n1);
    48. 	SLTNode* a = SListFind(n1, 5);
    49. 	SListModify(n1, 1, 6);
    50. 	SListPrint(n1);
    51. 	SListFrontPush(&n1, 1, 2);
    52.  
    53. 	SListPrint(n1);
    54. 	SListPrint(n1);
    55.  
    56. }
    57.  
    58.  
    59. int main()
    60. {
    61. 	SLTNode* n1 = NULL;
    62. 	int option;
    63. 	do {
    64. 		menu();
    65. 		if (scanf("%d", &option) == EOF)
    66. 		{
    67. 			printf("scanf输入错误\n");
    68. 			break;
    69. 		}
    70.  
    71. 		int val, pos;
    72. 		switch (option)
    73. 		{
    74. 		case -1:
    75. 			printf("退出\n");
    76. 			exit(0);
    77. 			break;
    78. 		case 1:
    79. 			printf("请连续输入你要尾插的数据，以0结束：\n");
    80. 			scanf("%d", &val);
    81. 			while (val != 0)
    82. 			{
    83. 				SListPushBack(&n1, val);
    84. 				scanf("%d", &val);
    85. 			}
    86. 			break;
    87. 		case 2: {
    88. 			printf("请连续输入你要头插的数据，以0结束：\n");
    89. 			scanf("%d", &val);
    90. 			while (val != 0)
    91. 			{
    92. 				SListPushFront(&n1, val);
    93. 				scanf("%d", &val);
    94. 			}
    95. 			break;
    96. 		}
    97. 		case 3:
    98. 			SListPopBack(&n1);
    99. 			break;
    100. 		case 4:
    101. 			SListPopFront(&n1);
    102. 			break;
    103. 		case 5:
    104. 		{
    105. 			int y;
    106. 			int x;
    107. 			printf("请输入你要的被插入的,和插入的值\n");
    108. 			scanf("%d%d", &x, &y);
    109. 			SListFrontPush(&n1, x, y);
    110. 			break;
    111. 		}
    112. 		case 6:
    113. 		{
    114. 			int y;
    115. 			int x;
    116. 			printf("请输入你要的被插入的,和插入的值\n");
    117. 			scanf("%d%d", &x, &y);
    118. 			SListBackPush(&n1, x, y);
    119. 			break;
    120. 		}
    121. 		case 7:
    122. 		{
    123. 			int x;
    124. 			printf("请输入你要删除的值\n");
    125. 			scanf("%d", &x);
    126. 			SListPop(&n1, x);
    127. 		}
    128. 		case 8:
    129. 		{
    130. 			int y;
    131. 			int x;
    132. 			printf("请输入你要修改的位置,和修改后的值\n");
    133. 			scanf("%d%d", &x, &y);
    134. 			SListModify(n1, x, y);
    135. 			break;
    136. 		}
    137. 		case 9:
    138. 			SListPrint(n1);
    139. 			break;
    140. 		default:
    141. 			exit(-1);
    142. 			break;
    143. 		}
    144. 	} while (option != -1);
    145. 	return 0;
    146. }

    链表面试题

    【LeetCode】203. 移除链表元素的三种方法_江湖第一深情的博客-CSDN博客

            给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

    【LeetCode】206. 反转链表—力扣_江湖第一深情的博客-CSDN博客

            给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

    【LeetCode】876. 链表的中间结点—力扣_江湖第一深情的博客-CSDN博客

            给定一个头结点为 head 的非空单链表，返回链表的中间结点。

            如果有两个中间结点，则返回第二个中间结点。        

    (3条消息) 剑指offer--链表中倒数第k个结点（jz22）_笨笨同学‍的博客-CSDN博客

            输入一个链表，输出该链表中倒数第k个结点。

    (3条消息) 【2016校招真题】OR36 链表的回文结构_笨笨同学‍的博客-CSDN博客

            对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

            给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

    (3条消息) 【程序员面试宝典】CM11 链表分割_笨笨同学‍的博客-CSDN博客

            现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

    (3条消息) 【LeetCode】21. 合并两个有序链表—力扣_笨笨同学‍的博客-CSDN博客 

            将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  

    (3条消息) 【LeetCode】160. 相交链表—力扣_笨笨同学‍的博客-CSDN博客

              给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。        

    (3条消息) 【LeetCode】141. 环形链表—力扣_笨笨同学‍的博客-CSDN博客 

            给你一个链表的头节点 head ，判断链表中是否有环。

            如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

            如果链表中存在环 ，则返回 true 。 否则，返回 false 。

    (3条消息) 【LeetCode】142. 环形链表 II—力扣_笨笨同学‍的博客-CSDN博客 

            给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

            如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

            不允许修改 链表。

    (3条消息) 【LeetCode】138. 复制带随机指针的链表—力扣_笨笨同学‍的博客-CSDN博客        

             给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

            构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

            例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

            返回复制链表的头节点。

            用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

            val：一个表示 Node.val 的整数。
            random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
            你的代码 只 接受原链表的头节点 head 作为传入参数。

  • 相关阅读:
    qiankun 乾坤主应用访问微应用css静态图片资源报404
    Kubernetes革命：云原生时代的应用编排和自动化
    ECharts与Excel的结合实战
    安全开发之碰撞检测与伤害计算逻辑
    【数据结构】二叉搜索树的原理及其实现
    iOS TestFlight 使用详解
    计算机网络概述及因特网
    APP 页面秒开优化方面总结~
    Linux 指令心法（十三）`mkdir` 创建新的目录（文件夹）
    angular基础总结
  • 原文地址：https://blog.csdn.net/qq_51581716/article/details/127613796