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

使用C++实现双链表_c++双向链表

作者：weixin_40725706 | 2024-04-15 10:45:05

赞

踩

c++双向链表

使用C++实现双链表

一、什么是双链表？

由下图就是一个双链表节点以及c++定义双链表节点！

                        

  1. typedef struct DNode {//定义双链表节点结构体
  2. 	DNode* pre;//前驱指针
  3. 	int data;//数据域
  4. 	DNode* next;//后继指针
  5. }DNode,*LinkList;//定义双链表节点和双链表

提示：以下是本篇文章正文内容，下面案例可供参考

二、双链表的初始化

  1. //1.初始化双链表节点
  2. bool InitList(LinkList& L) {
  3. 	L = new DNode;
  4. 	if (!L) {
  5. 		cout << "申请节点失败！" << endl;
  6. 		return false;
  7. 	}
  8. 	else {
  9. 		L->next = NULL;//初始化后继指针
  10. 		L->pre = NULL;//初始化前驱指针
  11. 		//cout << "申请节点成功！" << endl;
  12. 		return true;
  13. 	}
  14. }

三、打印双链表

  1. //2.打印双链表
  2. bool PrintList(LinkList& L) {
  3. 	if (L->next == NULL) { 
  4. 		cout << "该双链表不存在！" << endl;
  5. 		return false; }//判断是否是空链表
  6. 	DNode* p = L->next;
  7. 		while (p)
  8. 		{
  9. 			cout << p->data << " ";//打印数据
  10. 			p = p->next;//向后移动指针
  11. 		}
  12. 		cout << endl;
  13. 	return true;
  14. }

四、获取有效长度

  1. //3.获取有效长度
  2. int Length(LinkList& L) {
  3. 	DNode* p = L->next;//申请一个新节点
  4. 	int lenth = 0;//该变量用来保存长度
  5. 	while (p) {//p不为空时执行
  6. 		lenth++;//长度加1
  7. 		p = p->next;//节点向后移动
  8. 	}
  9. 	cout << endl;//只是为了换行
  10. 	return lenth;
  11. }

五、使用头插法创建双链表

  1. bool ListHeadInsert(LinkList& L) {
  2. 	int x;
  3. 	cout << "请输入元素的个数:" ;
  4. 	cin >> x;
  5. 	if (x <= 0) {
  6. 		cout << "您输入的值无意义!" << endl;
  7. 		return false;
  8. 	}
  9. 	cout << "请依次输入元素的值！"<<endl;
  10. 	while (x) {
  11. 		DNode* p = new DNode;//申请一个新节点
  12. 		cin >> p->data;//为新节点输入数据
  13. 		p->next = L->next;//将头节点的后继指针赋给新节点
  14. 		p->pre = L;//再让新节点的前驱指针指向头节点
  15. 		L->next = p;//移动头节点
  16. 		x--;//判断循环条件
  17. 	}
  18. 	cout << "采用头插法成功创建的双链表结果为：";
  19. 	PrintList(L);//打印双链表
  20. 	return true;
  21. }

六、使用尾插法创建双链表

  1. bool TailInsert(LinkList& L) {
  2. 	DNode* p = new DNode;//申请一个节点
  3. 	InitList(p);//初始化新节点
  4. 	L= p;//让新节点赋给头节点
  5. 	int x;
  6. 	cout << "请输入元素的个数:";
  7. 	cin >> x;
  8. 	if (x <= 0) {
  9. 		cout << "您输入的值无意义!" << endl;
  10. 		return false;
  11. 	}
  12. 	cout << "请依次输入元素的值！" << endl;
  13. 	while (x) {
  14. 		DNode* r = new DNode;//再申请一个新节点
  15. 		InitList(r);//初始化这个新节点
  16. 		cin >> r->data;//为这个新节点添加数据
  17. 		p->next = r;//让头节点之后的第一个节点指向这个新节点
  18. 		r->pre = p;//让新节点的前驱指针指向头节点
  19. 		p = p->next;//让头节点向后移动，目的是为了连接所有的节点
  20. 		x--;//判断循环并退出
  21. 	}
  22. 	cout << "采用尾插法成功创建的双链表结果为：";
  23. 	PrintList(L);//打印双链表
  24. 	return true;
  25. }

七、按值查找双链表

  1. bool GetValueElem(LinkList& L) {
  2. 	DNode* p = L->next;
  3. 	int x;
  4. 	cout << "请输入你要查找的值！" << endl;
  5. 	cin >> x;
  6. 	while (p) {
  7. 		if (p->data == x) {
  8. 			cout << "您要查找的值"<<x<<"存在!" << endl;
  9. 			return true;
  10. 		}
  11. 		p = p->next;
  12. 	}
  13. 	cout << "抱歉！您要查找的值"<<x<<"不存在!" << endl;
  14. 	return false;
  15. }

八、按位查找双链表

  1. bool GetBitElem(LinkList& L) {
  2. 	DNode* p = L->next;
  3. 	int x;
  4. 	cout << "请输入你要查找的位：";
  5. 	cin >> x;
  6. 	int t = Length(L);
  7. 	if (x<1 || x>t) {
  8. 		cout << "你要查的位不存在或无意义！" << endl;
  9. 		return false;
  10. 	}
  11. 	else {
  12. 		while (p)
  13. 		{
  14. 			x--;
  15. 			p = p->next;
  16. 			if (x == 1) {
  17. 				cout << "按位查找成功！且该数据为：" << p->data << endl;
  18. 				return true;
  19. 			}
  20. 		}
  21. 	}
  22. }

九、在双链表中插入数据

  1. bool Insert(LinkList& L) {
  2. 	int x;
  3. 	cout << "请输入你要插入的位数！" << endl;
  4. 	cin >> x;
  5. 	if (x<1 || x>Length(L)) {
  6. 		cout << "你要插入的位数不存在或无意义！" << endl;
  7. 		return false;
  8. 	}
  9. 		int Value;
  10. 		cout << "请输入你要插入的值：" ;
  11. 		cin >> Value;
  12. 		DNode* p = L;
  13. 		DNode* r;
  14. 		InitList(r);
  15. 		while (x) {
  16. 			if (x == 1) {//成功找到了要插入的节点的前一个节点
  17. 				r->data = Value;//将数据保存到新节点中
  18. 				r->next = p->next;//让新节点指向第一个节点
  19. 				p->next->pre = r;//让第二个节点的前驱指针指向新节点
  20. 				r->pre = p;//让新节点的前驱指针指向第一个节点
  21. 				p->next = r;//让第一个节点的后继指针指向新节点
  22. 				cout << "添加成功后的双链表是";
  23. 				PrintList(L);//打印单链表
  24. 			}
  25. 			else p = p->next;//没有找到想要插入的节点，向后移动节点
  26. 			x--;
  27. 		}
  28. 		return false;
  29. }

十、删除节点

  1. bool Delete(LinkList& L) {
  2. 	int x;
  3. 	cout << "请输入你要删除的节点;";
  4. 	cin >> x;
  5. 	if (x<1 || x>Length(L)) {
  6. 		cout << "您想删除的节点不存在或无意义！" << endl;
  7. 		return false;
  8. 	}
  9. 	else {
  10. 		DNode* p = L;
  11. 		DNode* r;
  12. 		InitList(r);
  13. 		while (x)
  14. 		{
  15. 			if (x == 1) {
  16. 				r->next = p->next;//新节点指向要删除的节点
  17. 				p->next->pre = r;//让要删除节点的前驱指针指向新节点
  18. 				p->next = r->next->next;//让被删除节点的前一个指向要删除的后一个节点
  19. 				free(r);
  20. 				cout << "删除成功！" << endl;
  21. 				cout << "删除后的双链表是"  ;
  22. 				PrintList(L);//打印单链表
  23. 				return true;
  24. 			}
  25. 			p = p->next;//没有找到想要插入的节点，向后移动节点
  26. 			x--;
  27. 		}
  28. 		return false;
  29. 	}
  30. }
  31.

完整代码

以下代码运行在Visual Studio2019编译器下运行成功！

  1. #include<iostream>
  2. #include <stdio.h>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. typedef struct DNode {//定义双链表节点结构体
  8. 	DNode* pre;//前驱指针
  9. 	int data;//数据域
  10. 	DNode* next;//后继指针
  11. }DNode,*LinkList;//定义双链表节点和双链表
  12.  
  13. //1.初始化双链表节点
  14. bool InitList(LinkList& L) {
  15. 	L = new DNode;
  16. 	if (!L) {
  17. 		cout << "申请节点失败！" << endl;
  18. 		return false;
  19. 	}
  20. 	else {
  21. 		L->next = NULL;//初始化后继指针
  22. 		L->pre = NULL;//初始化前驱指针
  23. 		//cout << "申请节点成功！" << endl;
  24. 		return true;
  25. 	}
  26. }
  27. //2.打印双链表
  28. bool PrintList(LinkList& L) {
  29. 	if (L->next == NULL) { 
  30. 		cout << "该双链表不存在！" << endl;
  31. 		return false; }//判断是否是空链表
  32. 	DNode* p = L->next;
  33. 		while (p)
  34. 		{
  35. 			cout << p->data << " ";//打印数据
  36. 			p = p->next;//向后移动指针
  37. 		}
  38. 		cout << endl;
  39. 	return true;
  40. }
  41. //3.获取有效长度
  42. int Length(LinkList& L) {
  43. 	DNode* p = L->next;//申请一个新节点
  44. 	int lenth = 0;//该变量用来保存长度
  45. 	while (p) {//p不为空时执行
  46. 		lenth++;//长度加1
  47. 		p = p->next;//节点向后移动
  48. 	}
  49. 	cout << endl;//只是为了换行
  50. 	return lenth;
  51. }
  52. //4.创建双链表
  53. //（1）采用头插入法
  54. bool ListHeadInsert(LinkList& L) {
  55. 	int x;
  56. 	cout << "请输入元素的个数:" ;
  57. 	cin >> x;
  58. 	if (x <= 0) {
  59. 		cout << "您输入的值无意义!" << endl;
  60. 		return false;
  61. 	}
  62. 	cout << "请依次输入元素的值！"<<endl;
  63. 	while (x) {
  64. 		DNode* p = new DNode;//申请一个新节点
  65. 		cin >> p->data;//为新节点输入数据
  66. 		p->next = L->next;//将头节点的后继指针赋给新节点
  67. 		p->pre = L;//再让新节点的前驱指针指向头节点
  68. 		L->next = p;//移动头节点
  69. 		x--;//判断循环条件
  70. 	}
  71. 	cout << "采用头插法成功创建的双链表结果为：";
  72. 	PrintList(L);//打印双链表
  73. 	return true;
  74. }
  75. //（2）尾插入法
  76. bool TailInsert(LinkList& L) {
  77. 	DNode* p = new DNode;//申请一个节点
  78. 	InitList(p);//初始化新节点
  79. 	L= p;//让新节点赋给头节点
  80. 	int x;
  81. 	cout << "请输入元素的个数:";
  82. 	cin >> x;
  83. 	if (x <= 0) {
  84. 		cout << "您输入的值无意义!" << endl;
  85. 		return false;
  86. 	}
  87. 	cout << "请依次输入元素的值！" << endl;
  88. 	while (x) {
  89. 		DNode* r = new DNode;//再申请一个新节点
  90. 		InitList(r);//初始化这个新节点
  91. 		cin >> r->data;//为这个新节点添加数据
  92. 		p->next = r;//让头节点之后的第一个节点指向这个新节点
  93. 		r->pre = p;//让新节点的前驱指针指向头节点
  94. 		p = p->next;//让头节点向后移动，目的是为了连接所有的节点
  95. 		x--;//判断循环并退出
  96. 	}
  97. 	cout << "采用尾插法成功创建的双链表结果为：";
  98. 	PrintList(L);//打印双链表
  99. 	return true;
  100. }
  101. // 5.查找双链表
  102. //（1）按值查找
  103. bool GetValueElem(LinkList& L) {
  104. 	DNode* p = L->next;
  105. 	int x;
  106. 	cout << "请输入你要查找的值！" << endl;
  107. 	cin >> x;
  108. 	while (p) {
  109. 		if (p->data == x) {
  110. 			cout << "您要查找的值"<<x<<"存在!" << endl;
  111. 			return true;
  112. 		}
  113. 		p = p->next;
  114. 	}
  115. 	cout << "抱歉！您要查找的值"<<x<<"不存在!" << endl;
  116. 	return false;
  117. }
  118. //（2）按位查找
  119. bool GetBitElem(LinkList& L) {
  120. 	DNode* p = L->next;
  121. 	int x;
  122. 	cout << "请输入你要查找的位：";
  123. 	cin >> x;
  124. 	int t = Length(L);
  125. 	if (x<1 || x>t) {
  126. 		cout << "你要查的位不存在或无意义！" << endl;
  127. 		return false;
  128. 	}
  129. 	else {
  130. 		while (p)
  131. 		{
  132. 			x--;
  133. 			p = p->next;
  134. 			if (x == 1) {
  135. 				cout << "按位查找成功！且该数据为：" << p->data << endl;
  136. 				return true;
  137. 			}
  138. 		}
  139. 	}
  140. }
  141. bool Insert(LinkList& L) {
  142. 	int x;
  143. 	cout << "请输入你要插入的位数！" << endl;
  144. 	cin >> x;
  145. 	if (x<1 || x>Length(L)) {
  146. 		cout << "你要插入的位数不存在或无意义！" << endl;
  147. 		return false;
  148. 	}
  149. 		int Value;
  150. 		cout << "请输入你要插入的值：" ;
  151. 		cin >> Value;
  152. 		DNode* p = L;
  153. 		DNode* r;
  154. 		InitList(r);
  155. 		while (x) {
  156. 			if (x == 1) {//成功找到了要插入的节点的前一个节点
  157. 				r->data = Value;//将数据保存到新节点中
  158. 				r->next = p->next;//让新节点指向第一个节点
  159. 				p->next->pre = r;//让第二个节点的前驱指针指向新节点
  160. 				r->pre = p;//让新节点的前驱指针指向第一个节点
  161. 				p->next = r;//让第一个节点的后继指针指向新节点
  162. 				cout << "添加成功后的双链表是";
  163. 				PrintList(L);//打印单链表
  164. 			}
  165. 			else p = p->next;//没有找到想要插入的节点，向后移动节点
  166. 			x--;
  167. 		}
  168. 		return false;
  169. }
  170. //7.删除节点
  171. bool Delete(LinkList& L) {
  172. 	int x;
  173. 	cout << "请输入你要删除的节点;";
  174. 	cin >> x;
  175. 	if (x<1 || x>Length(L)) {
  176. 		cout << "您想删除的节点不存在或无意义！" << endl;
  177. 		return false;
  178. 	}
  179. 	else {
  180. 		DNode* p = L;
  181. 		DNode* r;
  182. 		InitList(r);
  183. 		while (x)
  184. 		{
  185. 			if (x == 1) {
  186. 				r->next = p->next;//新节点指向要删除的节点
  187. 				p->next->pre = r;//让要删除节点的前驱指针指向新节点
  188. 				p->next = r->next->next;//让被删除节点的前一个指向要删除的后一个节点
  189. 				free(r);
  190. 				cout << "删除成功！" << endl;
  191. 				cout << "删除后的双链表是"  ;
  192. 				PrintList(L);//打印单链表
  193. 				return true;
  194. 			}
  195. 			p = p->next;//没有找到想要插入的节点，向后移动节点
  196. 			x--;
  197. 		}
  198. 		return false;
  199. 	}
  200. }
  201.  
  202.  
  203. int main(){
  204. 	LinkList L;//定义一个双链表L
  205. 	InitList(L);//为链表L初始化
  206. 	ListHeadInsert(L);//使用头插法创建双链表
  207. 	TailInsert(L);//使用尾插法创建双链表
  208. 	GetValueElem(L);//按值查找
  209. 	GetBitElem(L);	//按位查找
  210. 	Insert(L);	//插入数据
  211. 	Delete(L);		//删除数据
  212. 	
  213. }

代码运行截图

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

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

  

闽ICP备14008679号