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

[手撕数据结构] 链表及其基本操作_手撕一个链表数据结构,完成链表的crud。

作者：神奇cpp | 2024-07-24 20:53:10

赞

踩

手撕一个链表数据结构,完成链表的crud。

链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相比于数组这种连续性的储存结构，链表对于插入及删除等操作将更为方便。

单链表

  1. #include<stdlib.h>
  2. #include<stdbool.h>
  3. #include<iostream>
  4. using namespace std;
  5. struct student
  6. {
  7. 	int score;
  8. 	struct student* next;
  9. };
  10. typedef struct student stu;
  11. stu* Creat_Node(int x)//申请结点
  12. {
  13. 	stu* new_node = new stu;
  14. 	new_node->score = x;
  15. 	new_node->next = NULL;
  16. 	return new_node;
  17. }
  18. void Initlist(stu*& L)//初始化 stu* &L表示对一个指针的引用
  19. {
  20. 	L = new stu;
  21. 	L->next = NULL;
  22. }
  23.  
  24. void Insert(int i, int k, stu* L)//在第i个位置插入k；Insert(Get_length(L)+1, 2, L)实现尾插；Insert(1, 2, L);实现头插
  25. {
  26. 	stu* o = L;
  27. 	for (int j = 1; j < i; j++)
  28. 	{
  29. 		o = o->next;
  30. 	}
  31. 	stu* p = new stu;
  32. 	p->score = k;
  33. 	p->next = o->next;
  34. 	o->next = p;
  35. }
  36. void Print_list(stu* head)//遍历打印链表
  37. {
  38. 	if (head->next == NULL)
  39. 	{
  40. 		cout << "空表" << endl;
  41. 		return;
  42. 	}
  43. 	head = head->next;
  44. 	while (head)
  45. 	{
  46. 		cout << head->score << "->";
  47. 		head = head->next;
  48. 	}
  49. 	cout << "NULL" << endl;
  50. 	return;
  51. }
  52. void Delete_Kth(stu* list, int k)//删除第k个结点
  53. {
  54. 	for (int i = 1; i < k; i++)
  55. 	{
  56. 		list = list->next;
  57. 	}
  58. 	stu* p = new stu;
  59. 	p = list->next;
  60. 	list->next = list->next->next;
  61. 	delete p;
  62. 	return;
  63. }
  64. int Get_length(stu* list)//获得链表长度
  65. {
  66. 	stu* p = list;
  67. 	if (p->next == NULL)
  68. 	{
  69. 		return 0;
  70. 	}
  71. 	int j = 0;
  72. 	p = p->next;
  73. 	while (p != NULL)
  74. 	{
  75. 		p = p->next;
  76. 		j++;
  77. 	}
  78. 	return j;
  79. }
  80. void Find_first(int k, stu* list)//寻找出现值的第一个结点
  81. {
  82. 	stu* p = list;
  83. 	p = p->next;
  84. 	for (int i = 1; i <= Get_length(list); i++)
  85. 	{
  86. 		if (p->score == k)
  87. 		{
  88. 			cout << k << "第一次出现的位置为" << i << endl;
  89. 			return;
  90. 		}
  91. 		else
  92. 			p = p->next;
  93. 	}
  94. 	cout << "表中无此值" << endl;
  95. 	return;
  96. }
  97. void Find_Kth(int k, stu* list)//寻找第K个结点的值
  98. {
  99. 	stu* p = list;
  100. 	p = p->next;
  101. 	int i = 1;
  102. 	while (p->next != NULL && i < k)//p->next==NULL的时候说明此时p已经是最后一个结点
  103. 	{
  104. 		i++;
  105. 		p = p->next;
  106. 	}
  107. 	if (i == k)
  108. 	{
  109. 		cout << "第" << k << "个结点的值为" << p->score << endl;
  110. 		return;
  111. 	}
  112. 	else
  113. 	{
  114. 		cout << "没有第" << k << "个结点" << endl;
  115. 		return;
  116. 	}
  117.  
  118. }
  119. void Delete_k(int k, stu* list)//删除所有元素为K的结点
  120. {
  121. 	stu* p = list;
  122. 	while (p->next)
  123. 	{
  124. 		if (p->next->score == k)
  125. 		{
  126. 			stu* q = new stu;
  127. 			q = p->next;
  128. 			p->next = p->next->next;
  129. 			delete q;
  130. 		}
  131. 		else
  132. 			p = p->next;
  133. 	}
  134. 	return;
  135. }
  136. void sort_list(stu* head)//排序
  137. {
  138. 	for (int i = 1; i <= Get_length(head); i++)
  139. 	{
  140. 		stu* p = head->next;
  141. 		for (int j = 1; j < Get_length(head); j++)
  142. 		{
  143. 			if (p->score > p->next->score)
  144. 			{
  145. 				int a = p->score;
  146. 				p->score = p->next->score;
  147. 				p->next->score = a;
  148. 			}
  149. 			p = p->next;
  150. 		}
  151. 	}
  152. }
  153. void Merge_list(stu* L, stu* M)//合并链表于L
  154. {
  155. 	stu* p = L;
  156. 	for (int i = 0; i < Get_length(L); i++)
  157. 	{
  158. 		p = p->next;
  159. 	}
  160. 	p->next = M->next;//表尾下接表头
  161. }
  162. void Remove_DupliCation(stu* head)//除去重复元素
  163. {
  164. 	stu* p = head->next;
  165. 	for (int i = 1; i <Get_length(head); i++)
  166. 	{
  167. 		if (p->score == p->next->score)
  168. 		{
  169. 			stu* q = p->next;
  170. 			p->next = p->next->next;
  171. 			delete q;
  172. 		}
  173. 		else
  174. 			p = p->next;
  175. 	}
  176. }
  177. int main()
  178. {
  179. 	stu* L;
  180. 	Initlist(L);
  181. 	stu* M;
  182. 	Initlist(M);
  183. 	Insert(1, 12, L);
  184. 	Insert(1, 7, L);
  185. 	Insert(1, 6, L);
  186. 	Insert(1, 5, L);
  187. 	cout << "L链表: ";
  188. 	Print_list(L);
  189. 	Insert(1, 11, M);
  190. 	Insert(1, 7, M);
  191. 	Insert(1, 6, M);
  192. 	Insert(1, 3, M);
  193. 	Insert(1, 1, M);
  194. 	cout << "M链表: ";
  195. 	Print_list(M);
  196. 	Merge_list(L, M);
  197. 	cout << "合并后的链表为:";
  198. 	Print_list(L);
  199. 	sort_list(L);
  200. 	cout << "排序后的链表为：";
  201. 	Print_list(L);
  202. 	Remove_DupliCation(L);
  203. 	cout << "去重后的链表为: ";
  204. 	Print_list(L);
  205. 	return 0;
  206. }
  207. //嗨害嗨

双向链表

  1. #include<stdlib.h>
  2. #include<stdbool.h>
  3. #include<iostream>
  4. using namespace std;
  5. #define OK 1;
  6. #define ERROR 0;
  7. #define ElemType int;
  8. #define TRUE  1
  9. #define FALSE 0
  10. #define INFEASIBLE  -1
  11. typedef int Status;
  12. struct student
  13. {
  14. 	int score;
  15. 	struct student* next;
  16. 	struct student* last;
  17. };
  18. typedef struct student stu;
  19. Status Initlist(stu* &L)//初始化 stu* &L表示对一个指针的引用
  20. {
  21. 	L = new stu;
  22. 	L->next = NULL;
  23. 	L->last = NULL;
  24. 	return OK;
  25. }
  26. Status Insert(int i, int k, stu* L)//在第i个位置插入k；Insert(Get_length(L)+1, 2, L)实现尾插；Insert(1, 2, L);实现头插
  27. {
  28. 	stu* o = L;
  29. 	for (int j = 1; j < i; j++)
  30. 	{
  31. 		o = o->next;
  32. 	}
  33. 	stu* p = new stu;
  34. 	p->score = k;
  35. 	p->next = o->next;
  36. 	p->last = o;
  37. 	o->next = p;
  38. 	if (p->next != NULL)
  39. 	{
  40.       p ->next->last = p;
  41. 	}
  42. 	
  43. 	return OK;
  44. }
  45. Status Print_link(stu* head)//遍历打印链表
  46. {
  47. 	if (head->next == NULL)
  48. 	{
  49. 		cout << "空表" << endl;
  50. 		return ERROR;
  51. 	}
  52. 	head = head->next;
  53. 	while (head)
  54. 	{
  55. 		cout << head->score << endl;
  56. 		head = head->next;
  57. 	}
  58. 	cout << "遍历结束" << endl;
  59. 	return OK;
  60. }
  61. Status Delete_Kth(stu* list, int k)//删除第k个结点
  62. {
  63. 	for (int i = 1; i < k; i++)
  64. 	{
  65. 		list = list->next;
  66. 	}
  67. 	stu* p = new stu;
  68. 	p = list->next;
  69. 	list->next = list->next->next;
  70. 	list->next->last = list;
  71.     delete p;
  72. 	return OK;
  73. }
  74. Status Get_length(stu* list)//获得链表长度
  75. {
  76. 	stu* p = list;
  77. 	if (p->next == NULL)
  78. 	{
  79. 		return ERROR;
  80. 	}
  81. 	int j = 0;
  82. 	p = p->next;
  83. 	while (p!=NULL)
  84. 	{
  85. 		p = p->next;
  86. 		j++;
  87. 	}
  88. 	return j;
  89. }
  90. Status Find_first(int k, stu* list)//寻找出现值的第一个结点
  91. {
  92. 	stu* p = list;
  93. 	p = p->next;
  94. 	for (int i = 1; i <= Get_length(list); i++)
  95. 	{
  96. 		if (p->score == k)
  97. 		{
  98. 			cout << k << "第一次出现的位置为" << i << endl;
  99.            return OK;
  100. 		}
  101. 			
  102. 		else
  103. 			p = p->next;
  104. 	}
  105. 	return ERROR;
  106. }
  107. Status  Find_Kth(int k, stu* list)//寻找第K个结点的值
  108. {
  109. 	stu* p = list;
  110. 	p = p->next;
  111. 	int i = 1;
  112. 	while (p->next!=NULL && i < k)//p->next==NULL的时候说明此时p已经是最后一个结点
  113. 	{
  114.         i++;
  115.         p = p->next;
  116. 	}
  117. 	if (i == k)
  118. 	{ 
  119. 		cout << "第" << k << "个结点的值为" << p->score << endl;
  120. 		return OK;
  121. 	}
  122. 	else
  123. 	{
  124. 		cout << "没有第" << k << "个结点" << endl;
  125.        return ERROR;
  126. 	}
  127. 		
  128. }
  129. Status Delete_k(int k, stu* list)//删除所有元素为K的结点
  130. {
  131. 	stu* p = list;
  132. 	while (p->next)
  133. 	{
  134. 		if (p->next->score == k)
  135. 		{
  136. 			stu* q = new stu;
  137. 			q = p->next; 
  138. 			p->next = p->next->next;
  139. 			p->next->last = p;
  140. 			delete q;
  141. 		}
  142. 		else
  143. 		p = p->next;
  144. 	}
  145. return OK;
  146. }
  147. Status Clear_link(stu* head)
  148. {
  149. 	if (head == NULL)
  150. 	{
  151. 		return ERROR;
  152. 	}
  153. 	stu* p = head;
  154. 	p = p->next;
  155. 	while (p != NULL)
  156. 	{
  157. 		stu* tmp = p;
  158. 		p = p->next;
  159. 		free(tmp);
  160. 	}
  161. 	head->next = NULL;
  162. 	cout << "链表已清空" << endl;
  163. 	return OK;
  164. } 
  165. int main()
  166. {
  167. 	stu* L;
  168. 	Initlist(L);
  169. 	Insert(1, 3, L);
  170. 	Insert(1, 3, L);
  171. 	Insert(1, 3, L);
  172. 	Insert(2, 8, L);
  173. 	Insert(1, 3, L);
  174. 	Insert(1, 2, L);
  175. 	Insert(Get_length(L)+1, 2, L);
  176. 	Print_link(L);
  177. 	Delete_k(3, L);
  178. 	Print_link(L);
  179. 	return 0;
  180. }
  181. //嗨害嗨

双向循环链表

  1. #include<stdlib.h>
  2. #include<stdbool.h>
  3. #include<iostream>
  4. using namespace std;
  5. struct student
  6. {
  7. 	int score;
  8. 	struct student* next;
  9. 	struct student* last;
  10. };
  11. typedef struct student stu;
  12. void Initlist(stu*& L)//初始化 stu* &L表示对一个指针的引用
  13. {
  14. 	L = new stu;
  15. 	L->next = L;
  16. 	L->last = L;
  17. }
  18.  
  19. stu* Creat_Node(int x)//申请结点
  20. {
  21. 	stu* new_node = new stu;
  22. 	new_node->score = x;
  23. 	new_node->next = NULL;
  24. 	new_node->last = NULL;
  25. 	return new_node;
  26. }
  27.  
  28. void Print(stu* head)//打印
  29. {
  30. 	if (head->next == head)
  31. 	{
  32. 		cout << "空表" << endl;
  33. 		return;
  34. 	}
  35. 	stu* current = head->next;
  36. 	while (current != head)
  37. 	{
  38. 		cout << current->score << endl;
  39. 		current = current->next;
  40. 	}
  41. }
  42.  
  43. void Tail_Plug(stu* head, int x)//尾插
  44. {
  45. 	stu* new_node = Creat_Node(x);
  46. 	new_node->next = head;
  47. 	new_node->last = head->last;
  48. 	head->last->next = new_node;
  49. 	head->last = new_node;
  50. }
  51.  
  52. void Delete_tail(stu* head)//尾删
  53. {
  54. 	stu* p = head->last;
  55. 	p->last->next = head;
  56. 	head->last = p->last;
  57. 	delete p;
  58. }
  59.  
  60. void Head_Plug(stu* head, int x)//头插
  61. {
  62. 	stu* p = Creat_Node(x);
  63. 	p->next = head->next;
  64. 	head->next->last = p;
  65. 	p->last = head;
  66. 	head->next = p;
  67. }
  68.  
  69. void Delete_head(stu* head)//头删
  70. {
  71. 	stu* p = head->next;
  72. 	head->next = p->next;
  73. 	p->next->last = head;
  74. 	delete p;
  75. }
  76.  
  77. int Get_length(stu* head)//获得链表长度
  78. {
  79. 	stu* p = head;
  80. 	if (p->next == NULL)
  81. 	{
  82. 		return 0;
  83. 	}
  84. 	int j = 0;
  85. 	while (p->next != head)
  86. 	{
  87. 		p = p->next;
  88. 		j++;
  89. 	}
  90. 	return j;
  91. }
  92.  
  93. void Insert(int i, int k, stu* L)//在第i个位置插入k;
  94. {
  95. 	if (i <= Get_length(L))
  96. 	{
  97. 		stu* o = L;
  98. 		for (int j = 1; j < i; j++)
  99. 		{
  100. 			o = o->next;
  101. 		}
  102. 		stu* p = Creat_Node(k);
  103. 		p->next = o->next;
  104. 		p->last = o;
  105. 		o->next = p;
  106. 	}
  107. 	else
  108. 		cout << "第" << i << "个位置不合法" << endl;
  109. }
  110.  
  111. void Delete_Kth(stu* list, int k)//删除第k个结点
  112. {
  113. 	if (k > Get_length(list) || k < 1)
  114. 	{
  115. 		cout << "没有第" << k << "个结点" << endl;
  116. 		return;
  117. 	}
  118. 	for (int i = 1; i < k; i++)
  119. 	{
  120. 		list = list->next;
  121. 	}
  122. 	stu* p = list->next;
  123. 	list->next = list->next->next;
  124. 	list->next->last = list;
  125. 	delete p;
  126. }
  127.  
  128. void Find_first(int k, stu* list)//寻找出现值的第一个结点
  129. {
  130. 	stu* p = list;
  131. 	p = p->next;
  132. 	for (int i = 1; i <= Get_length(list); i++)
  133. 	{
  134. 		if (p->score == k)
  135. 		{
  136. 			cout << k << "第一次出现的位置为" << i << endl;
  137. 			return;
  138. 		}
  139. 		else
  140. 			p = p->next;
  141. 	}
  142. 	cout << "表中没有值为" << k << "的结点" << endl;
  143. }
  144.  
  145. void Find_Kth(int k, stu* head)//寻找第K个结点的值
  146. {
  147. 	int i = k;
  148. 	if (k <= Get_length(head))
  149. 	{
  150. 		stu* p = head;
  151. 		while (i--)
  152. 		{
  153. 			p = p->next;
  154. 		}
  155. 		cout << "第" << k << "个结点的值为" << p->score << endl;
  156. 		return;
  157. 	}
  158. 	else
  159. 	{
  160. 		cout << "没有第" << k << "个结点" << endl;
  161. 		return;
  162. 	}
  163. }
  164.  
  165. void Delete_k(int k, stu* list)//删除所有元素为K的结点
  166. {
  167. 	stu* p = list;
  168. 	while (p->next != list)
  169. 	{
  170. 		if (p->next->score == k)
  171. 		{
  172. 			stu* q = new stu;
  173. 			q = p->next;
  174. 			p->next = p->next->next;
  175. 			p->next->last = p;
  176. 			delete q;
  177. 		}
  178. 		else
  179. 			p = p->next;
  180. 	}
  181. }
  182.  
  183. void Clear_link(stu* head)//清空链表
  184. {
  185. 	int k = Get_length(head);
  186. 	for (int i = 1; i <= k; i++)
  187. 	{
  188. 		Delete_Kth(head, 1);
  189. 	}
  190. 	cout << "链表已清空" << endl;
  191. }
  192.  
  193. int main()
  194. {
  195. 	stu* L;
  196. 	Initlist(L);
  197. 	Tail_Plug(L, 1);
  198. 	Tail_Plug(L, 2);
  199. 	Tail_Plug(L, 3);
  200. 	Tail_Plug(L, 4);
  201. 	Head_Plug(L, 8);
  202. 	Insert(2, 8, L);
  203. 	Insert(2, 8, L);
  204. 	Insert(2, 8, L);
  205. 	Insert(2, 8, L);
  206. 	Insert(108, 5, L);
  207. 	Print(L);
  208. 	Clear_link(L);
  209. 	Print(L);
  210. 	return 0;
  211. }
  212. //嗨害嗨

有何不足欢迎批评指正

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

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

  

闽ICP备14008679号