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

C++双向链表

作者：很楠不爱3 | 2024-05-01 01:25:04

赞

踩

c++双向链表

C++双向链表

双向链表顾名思义就是每个结点具有两个指针，一个指向前一个结点，一个指向后一个结点，我们不必拘束与单链表的创建遍历操作等，这样大大减少了使用中存在的效率问题。

在单链表中，我们有一个数据域还有一个指针域，数据域用来存储相关数据，而指针域负责链表之间的“联系”，双向链表具有两个指针域，一个负责向后连接，一个负责向前连接。

  1. //单链表结构
  2. template<class T>
  3. struct List{
  4.     T data;
  5.     struct List* next;
  6. };
  7. //双向链表结构
  8. template<class T>
  9. struct DNode{
  10. 	public:
  11. 		T value;
  12. 		DNode *prev;
  13. 		DNode *next;
  14. };

同单链表一样，对双向链表的操作也有创建，插入，遍历，删除，销毁。

双向链表的创建

  1. struct DNode{
  2. 	public:
  3. 		T value;
  4. 		DNode *prev;
  5. 		DNode *next;
  6. 	public:
  7. 		DNode(){
  8. 		}
  9. 		DNode(T t,DNode *prev,DNode *next){
  10. 			this->value=t;
  11. 			this->prev=prev;
  12. 			this->next=next;
  13. 		}
  14. };

在创建双向链表的时候，我们需要初始化的有两个指针。同单链表一样，我们需要一个头指针来标志链表的信息。因此我们可以写出该函数的定义：运用构造函数创建双向链表

双向链表具体操作：

  1. template<class T>
  2. class DoubleCircleList{
  3. 	public:
  4. 		DoubleCircleList();  //构造函数 创建链表 
  5. 		~DoubleCircleList();  //析构函数 销毁链表 	
  6. 		int size();	//长度 
  7. 		int is_empty();//判断是否为空 
  8. 		T get(int index); //返回index值的位置 
  9. 		T get_first();//返回第一个位置 
  10. 		T get_last();//返回最后一个位置 
  11. 		int insert(int index,T t);//在index位置后插入数值 
  12. 		int insert_first(T t);//在头插入 
  13. 		int append_last(T t);//在尾插入 
  14. 		int Delete(int index);//删除index值 
  15. 		int Delete_first();//删除头结点 
  16. 		int Delete_last();//删除尾结点 
  17. 	private:
  18. 		int count;
  19. 		DNode<T>* phead;
  20. 		DNode<T>* get_node(int index);
  21. };

1.计算链表的长度

  1. template<class T>
  2. DoubleCircleList<T>::DoubleCircleList():count(0){
  3. 	//创建“表头 ，注意：表头没有存储数据！ 
  4. 	phead=new DNode<T>();
  5. 	phead->prev=phead->next=phead;
  6. 	//设置链表计数为0
  7. 	//cout=0; 
  8. }

2.销毁链表

  1. //析构函数   销毁链表
  2. template<class T>
  3. DoubleCircleList<T>::~DoubleCircleList(){
  4. 	DNode<T>* ptmp;   
  5. 	DNode<T>* pnode=phead->next;	
  6. 	while(pnode!=phead){	//一直循环往后找 
  7. 		ptmp=pnode;	//
  8. 		pnode=pnode->next;
  9. 		delete ptmp;
  10. 	}
  11. 	delete phead;
  12. 	phead=NULL;
  13. }

3.计算结点的数目

  1. //返回结点数目
  2. template<class T>
  3. int DoubleCircleList<T>::size(){
  4. 	return count;
  5. }

4.判断链表是否为空

  1. template<class T>
  2. int DoubleCircleList<T>::is_empty(){
  3. 	return count==0;
  4. }

5.寻找结点位置

  1. template<class T>
  2. DNode<T>* DoubleCircleList<T>::get_node(int index){
  3. 	//判断参数有效性
  4. 	if(index<0||index>=count){
  5. 		cout<<"get node failed! the index in out of bound!"<<endl;
  6. 		return NULL;
  7. 	} 
  8. 	//正向查找 
  9. 	if(index<=count/2){
  10. 		int i=0;
  11. 		DNode<T>* pindex=phead->next;
  12. 		while(i++<index){
  13. 			pindex=pindex->next;
  14. 		}
  15. 		return pindex;
  16. 	}
  17. 	//反向查找
  18. 	 int j=0;
  19. 	 int rindex=count-index-1;
  20. 	 DNode<T>* prindex=phead->prev;
  21. 	 while(j++<rindex){
  22. 	 	prindex=prindex->prev;
  23. 	 }
  24. 	 return prindex;
  25. }

6.返回结点位置的值

  1. template<class T>
  2. T DoubleCircleList<T>::get(int index){
  3. 	return get_node(index)->value;
  4. }

7.获取第一个结点的值

  1. template<class T>
  2. T DoubleCircleList<T>::get_first(){
  3. 	return get_node(0)->value;
  4. }

8.获取最后一个结点的值

  1. template<class T>
  2. T DoubleCircleList<T>::get_last(){
  3. 	return get_node(count-1)->value;
  4. }

9.将结点插入index之后

  1. template<class T>
  2. int DoubleCircleList<T>::insert(int index,T t){
  3. 	if(index==0)
  4. 		return insert_first(t);
  5. 	DNode<T>* pindex=get_node(index);
  6. 	DNode<T>* pnode=new DNode<T>(t,pindex->prev,pindex);
  7. 	pindex->prev->next=pnode;
  8. 	pindex->prev=pnode;
  9. 	count++;
  10. 	return 0;
  11.  
  12. }

10.结点插入到第一个位置

  1. //将结点插入到第一个结点处
  2. template<class T>
  3. int DoubleCircleList<T>::insert_first(T t){
  4. 	DNode<T>* pnode=new DNode<T>(t,phead,phead->next);
  5. 	phead->next->prev=pnode;
  6. 	phead->next=pnode;
  7. 	count++;
  8. 	return 0;
  9. }

11.结点插入到最后一个位置

  1. template<class T>
  2. int DoubleCircleList<T>::append_last(T t){
  3. 	DNode<T>* pnode=new DNode<T>(t,phead->prev,phead);
  4. 	phead->prev->next=pnode;
  5. 	phead->prev=pnode;
  6. 	count++;
  7. 	return 0;
  8. }

12.删除index结点.

  1. template<class T>
  2. int DoubleCircleList<T>::Delete(int index){
  3. 	DNode<T>* pindex=get_node(index);
  4. 	pindex->next->prev=pindex->prev;
  5. 	pindex->prev->next=pindex->next;
  6. 	delete pindex;
  7. 	count--;
  8. 	return 0;
  9. }

13.删除第一个结点

  1. template<class T>
  2. int DoubleCircleList<T>::Delete_first(){
  3. 	return Delete(0);
  4. }

14.删除最后一个结点

  1. template<class T>
  2. int DoubleCircleList<T>::Delete_last(){
  3. 	return Delete(count-1);
  4. }

完整代码：

  1. //DoubleCircleList.h
  2. #include<iostream>
  3. using namespace std;
  4. template<class T>
  5. struct DNode{
  6. 	public:
  7. 		T value;
  8. 		DNode *prev;
  9. 		DNode *next;
  10. 	public:
  11. 		DNode(){
  12. 		}
  13. 		DNode(T t,DNode *prev,DNode *next){
  14. 			this->value=t;
  15. 			this->prev=prev;
  16. 			this->next=next;
  17. 		}
  18. };
  19. template<class T>
  20. class DoubleCircleList{
  21. 	public:
  22. 		DoubleCircleList();  //构造函数 创建链表 
  23. 		~DoubleCircleList();  //析构函数 销毁链表 	
  24. 		int size();	//长度 
  25. 		int is_empty();//判断是否为空 
  26. 		T get(int index); //返回index值的位置 
  27. 		T get_first();//返回第一个位置 
  28. 		T get_last();//返回最后一个位置 
  29. 		int insert(int index,T t);//在index位置后插入数值 
  30. 		int insert_first(T t);//在头插入 
  31. 		int append_last(T t);//在尾插入 
  32. 		int Delete(int index);//删除index值 
  33. 		int Delete_first();//删除头结点 
  34. 		int Delete_last();//删除尾结点 
  35. 	private:
  36. 		int count;
  37. 		DNode<T>* phead;
  38. 		DNode<T>* get_node(int index);
  39. };
  40. template<class T>
  41. DoubleCircleList<T>::DoubleCircleList():count(0){
  42. 	//创建“表头 ，注意：表头没有存储数据！ 
  43. 	phead=new DNode<T>();
  44. 	phead->prev=phead->next=phead;
  45. 	//设置链表计数为0
  46. 	//cout=0; 
  47. }
  48. //析构函数 
  49. template<class T>
  50. DoubleCircleList<T>::~DoubleCircleList(){
  51. 	DNode<T>* ptmp;   
  52. 	DNode<T>* pnode=phead->next;	
  53. 	while(pnode!=phead){	//一直循环往后找 
  54. 		ptmp=pnode;	//
  55. 		pnode=pnode->next;
  56. 		delete ptmp;
  57. 	}
  58. 	delete phead;
  59. 	phead=NULL;
  60. }
  61. //返回结点数目
  62. template<class T>
  63. int DoubleCircleList<T>::size(){
  64. 	return count;
  65. }
  66. template<class T>
  67. int DoubleCircleList<T>::is_empty(){
  68. 	return count==0;
  69. } 
  70. template<class T>
  71. DNode<T>* DoubleCircleList<T>::get_node(int index){
  72. 	//判断参数有效性
  73. 	if(index<0||index>=count){
  74. 		cout<<"get node failed! the index in out of bound!"<<endl;
  75. 		return NULL;
  76. 	} 
  77. 	//正向查找 
  78. 	if(index<=count/2){
  79. 		int i=0;
  80. 		DNode<T>* pindex=phead->next;
  81. 		while(i++<index){
  82. 			pindex=pindex->next;
  83. 		}
  84. 		return pindex;
  85. 	}
  86. 	//反向查找
  87. 	 int j=0;
  88. 	 int rindex=count-index-1;
  89. 	 DNode<T>* prindex=phead->prev;
  90. 	 while(j++<rindex){
  91. 	 	prindex=prindex->prev;
  92. 	 }
  93. 	 return prindex;
  94. }
  95. template<class T>
  96. T DoubleCircleList<T>::get(int index){
  97. 	return get_node(index)->value;
  98. }
  99. //获取第1个结点值
  100. template<class T>
  101. T DoubleCircleList<T>::get_first(){
  102. 	return get_node(0)->value;
  103. } 
  104. //获取最后一个结点值
  105. template<class T>
  106. T DoubleCircleList<T>::get_last(){
  107. 	return get_node(count-1)->value;
  108. } 
  109. //将结点插入到index位置之前
  110. template<class T>
  111. int DoubleCircleList<T>::insert(int index,T t){
  112. 	if(index==0)
  113. 		return insert_first(t);
  114. 	DNode<T>* pindex=get_node(index);
  115. 	DNode<T>* pnode=new DNode<T>(t,pindex->prev,pindex);
  116. 	pindex->prev->next=pnode;
  117. 	pindex->prev=pnode;
  118. 	count++;
  119. 	return 0;
  120.  
  121. }
  122. //将结点插入到第一个结点处
  123. template<class T>
  124. int DoubleCircleList<T>::insert_first(T t){
  125. 	DNode<T>* pnode=new DNode<T>(t,phead,phead->next);
  126. 	phead->next->prev=pnode;
  127. 	phead->next=pnode;
  128. 	count++;
  129. 	return 0;
  130. } 
  131. //结点追加到链表末尾
  132. template<class T>
  133. int DoubleCircleList<T>::append_last(T t){
  134. 	DNode<T>* pnode=new DNode<T>(t,phead->prev,phead);
  135. 	phead->prev->next=pnode;
  136. 	phead->prev=pnode;
  137. 	count++;
  138. 	return 0;
  139. } 
  140. //删除index位置结点
  141. template<class T>
  142. int DoubleCircleList<T>::Delete(int index){
  143. 	DNode<T>* pindex=get_node(index);
  144. 	pindex->next->prev=pindex->prev;
  145. 	pindex->prev->next=pindex->next;
  146. 	delete pindex;
  147. 	count--;
  148. 	return 0;
  149. }
  150. //删除第一个结点
  151. template<class T>
  152. int DoubleCircleList<T>::Delete_first(){
  153. 	return Delete(0);
  154. } 
  155. //删除最后一个结点
  156. template<class T>
  157. int DoubleCircleList<T>::Delete_last(){
  158. 	return Delete(count-1);
  159. } 
  160.  
  161. //DoubleCircleList.cpp
  162. #include <iostream>
  163. #include "DoubleCircleList.h"
  164. /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  165. using namespace std;
  166. void int_test()
  167. {
  168. 	int iarr[4] = {10, 20, 30, 40};//定义一个数组
  169.  
  170. 	cout << "\n开始测试 int数据" << endl;
  171. 	// 创建双向链表
  172. 	DoubleCircleList<int>* pdlink = new DoubleCircleList<int>();
  173.  
  174. 	pdlink->insert(0, 20);        // 将 20 插入到第一个位置
  175. 	pdlink->append_last(10);    // 将 10 追加到链表末尾
  176. 	pdlink->insert_first(30);    // 将 30 插入到第一个位置
  177.  
  178. 	// 双向链表是否为空
  179. 	cout << "is_empty()=" << pdlink->is_empty() <<endl;
  180. 	// 双向链表的大小
  181. 	cout << "size()=" << pdlink->size() <<endl;
  182.  
  183. 	// 打印双向链表中的全部数据
  184. 	int sz = pdlink->size();
  185. 	for (int i=0; i<sz; i++)
  186. 		cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;
  187. }
  188.  
  189. int main(int argc, char** argv) {
  190. 	int_test();
  191. 	return 0;
  192. }

双向循环链表：

  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #include<malloc.h>  
  4. typedef struct DOUBLE_LIST  
  5. {  
  6.     int data;  
  7.     struct DOUBLE_LIST *prev;  
  8.     struct DOUBLE_LIST *next;  
  9. }double_list;  
  10. double_list *createlist()       //创建有n个元素的双向链表 并输入元素  
  11. {  
  12.     double_list *head, *p, *q;  
  13.     int n,x;  
  14.     head = (double_list *)malloc(sizeof(double_list));  
  15.     head->prev = head;  
  16.     head->next = head;  
  17.     p = head;  
  18.     printf("输入要创建双向链表的元素的个数：\n");  
  19.     scanf("%d",&n);  
  20.     for(int i=0;i<n;i++)  
  21.     {  
  22.         scanf("%d", &x);  
  23.         q = (double_list *)malloc(sizeof(double_list));  
  24.         q->data = x;  
  25.         p->next = q;  
  26.         head->prev = q;  
  27.         q->prev = p;  
  28.         q->next = head;  
  29.         p = q;  
  30.     }  
  31.     return head;  
  32. }  
  33. //遍历并且输出这些元素  
  34. void printlist(double_list *head)  
  35. {  
  36.     double_list *p;  
  37.     p = head;  
  38.     p = p->next;  
  39.     while(p!=head)  
  40.     {  
  41.         printf("%d  ", p->data);  
  42.         p = p->next;  
  43.     }  
  44.     printf("\n");  
  45. }  
  46. //得到现在双向链表中的元素的个数  
  47. int lengthlist(double_list *head)  
  48. {  
  49.     double_list *p;  
  50.     p = head;  
  51.     p = p->next;  
  52.     int coun = 0;  
  53.     while(p!=head)  
  54.     {  
  55.         coun++;  
  56.         p = p->next;  
  57.     }  
  58.     return coun;  
  59. }  
  60. //在第i个元素之前插入数据data  
  61. void insertlist_f(double_list *head, int i, int data)  
  62. {  
  63.     double_list *p = head, *q;  
  64.     p = p->next;  
  65.     i--;  
  66.     while(i--)  
  67.         p = p->next;  
  68.     q = (double_list *)malloc(sizeof(double_list));  
  69.     q->data = data;  
  70.     (p->prev)->next = q;  
  71.     q->prev = p->prev;  
  72.     q->next = p;  
  73.     p->prev = q;  
  74. }  
  75. //删除第i个位置的元素  
  76. void deletelist_i(double_list *head, int i)  
  77. {  
  78.     double_list *p = head;  
  79.     p = p->next;  
  80.     i--;  
  81.     while(i--)  
  82.         p = p->next;  
  83.     (p->prev)->next = p->next;  
  84.     (p->next)->prev = p->prev;  
  85.     free(p);  
  86. }  
  87. //删除值为x的元素  
  88. void deletelist_x(double_list *head, int x)  
  89. {  
  90.     double_list *p = head, *q;  
  91.     p = p->next;  
  92.     while(p!=head)  
  93.         if(p->data == x)  
  94.         {  
  95.             q = p->next;  
  96.             (p->prev)->next = p->next;  
  97.             (p->next)->prev = p->prev;  
  98.             free(p);  
  99.             p = q;  
  100.         }  
  101.         else  
  102.             p = p->next;  
  103. }  
  104. //对双向链表进行排序  
  105. void sortlist(double_list *head)  //升序  
  106. {  
  107.     double_list *p = head, *q, *t;  
  108.     p = p->next;  
  109.     for(;p!=head;p=p->next)  
  110.         for(t = p->next;t!=head;t=t->next)  
  111.         {  
  112.             if(p->data > t->data)  
  113.             {  
  114.                 int a = p->data;  
  115.                 p->data = t->data;  
  116.                 t->data = a;  
  117.             }  
  118.         }  
  119. }  
  120. int main()  
  121. {  
  122.     double_list *head;  
  123.     head = createlist();  
  124.     deletelist_x(head, 2);  
  125.     //sortlist(head);  
  126.     printlist(head);  
  127.     insertlist_f(head, 2, 2);  
  128.     printlist(head);  
  129.   
  130.     return 0;  
  131. }

双向链表的遍历来说我只给出了前序遍历的代码，没有写后序遍历的代码，这其实是差不多的，但是因为双向链表可以进行两个方向的遍历，这给我们带来了很大的方便。

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

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

  

闽ICP备14008679号