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

数据结构初阶--双向循环链表（讲解+类模板实现）_循环双链表

作者：羊村懒王 | 2024-05-19 16:39:22

赞

踩

循环双链表

看下面的图，就是我今天要给大家分享有结构——带头双向循环链表。这里的头是不存放任何数据的，就是一个哨兵卫的头结点。

用代码来表示每一个节点就是这样的：

  • 数据域和指针域
  • 两个指针，一个指向前驱结点，一个指向后继结点
  • 给定两个构造函数，有参和无参，分别对结点的指针域和数据域进行初始化
  1. template <class DateType>
  2. struct LinkNode
  3. {
  4.       //数据域
  5.       DateType data;
  6.       //两个指针
  7.       LinkNode<DateType>* prev;
  8.       LinkNode<DateType>* next;
  9.       LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next){}
  10.       LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next){}
  11. };

带头双向链表的接口实现

要实现的接口

  1. LinkList();//构造函数，初始化头节点
  2. LinkList(const LinkList<DateType>& list2);//拷贝构造，进行两个链表的拷贝
  3. ~LinkList();//析构函数，用来清除链表，释放结点空间
  4. int Length();//求双向循环链表的长度
  5. void CreateList(int n);//常见n个结点的双向循环链表
  6. bool GetElem(int pos,DateType& data);//得到pos位置结点的元素值
  7. LinkNode<DateType>* Locate(int i ,int back_pos);//定位元素，当back_pos=0的时候，从头节点向前查询第i个元素，back_pos！=0的时候，从头节点后查询第i个元素
  8. bool Insert(int pos, const DateType& data, int back_pos);//在pos的位置插入元素，当back_pos！=0的时候，在pos位置后插入元素，当back_pos=0的时候，在pos位置前插入元素
  9. void PrintList(int sign);//输出双向循环链表所有结点的元素值，当sign！=0时，正序打印元素值，当sign=0时，逆序打印
  10. bool Delete(int pos, DateType& data,int back_pos);//删除pos位置的结点

双向链表的小框架

  1. template<class DateType>
  2. class LinkList
  3. {
  4. public:
  5. private:
  6. 	LinkNode<DateType>* head;//头节点
  7. };

初始化双向链表

在初始化双链表的过程中，我们要开好一个头节点，作为哨兵卫的头节点，然后返回这个节点的指针，接口外面只要用一个节点指针接受这个返回值就好了，具体实现如下：

  1. //构造函数,初始化一个循环双链表
  2. 	LinkList()
  3. 	{
  4. 		head = new LinkNode<DateType>;
  5. 		if (head == NULL)
  6. 		{
  7. 			cout << "内存分配失败" << endl;
  8. 			exit(-1);
  9. 		}
  10. 		head->data = 0;
  11. 		head->next = head;
  12. 		head->prev = head;
  13. 	}

拷贝构造

在拷贝构造中，要注意一件事情，就是最后一个结点的next需要指向头节点，头节点的prev需要指向最后一个结点，形成双向循环链表

  1. //拷贝构造
  2. 	LinkList(const LinkList<DateType>& list2)
  3. 	{
  4. 		LinkNode<DateType>* p = list2.head->next;
  5. 		if (p == NULL)
  6. 		{
  7. 			cout << "内存分配失败" << endl;
  8. 			exit(-1);
  9. 		}
  10. 		head = new LinkNode<DateType>;
  11. 		LinkNode<DateType>* h = head;
  12. 		while (p!=list2.head)
  13. 		{
  14. 			LinkNode<DateType>* t = new LinkNode<DateType>;
  15. 			h->next = t;
  16. 			t->prev = h;
  17. 			t->data = p->data;
  18. 			p = p->next;
  19. 			h = h->next;
  20. 		}
  21. 		h->next = this->head;
  22. 		this->head->prev = h;
  23. 	}

定位结点

因为后面的在指定插入删除元素，需要定位pos位置结点的地址，所以这里旧封装一个函数，直接获取pos位置结点的地址

  1. //定位元素，back_pos=0时从头节点向前查第i个元素，d!=0时，从头节点向后找第i个元素
  2. 	LinkNode<DateType>* Locate(int i ,int back_pos)
  3. 	{
  4. 		if (head->next == head || i == 0) {
  5. 			return head;
  6. 		}
  7. 		int j = 0;
  8. 		LinkNode<DateType>* p = head;
  9. 		//从头节点往后找第i个元素
  10. 		if (back_pos)
  11. 		{
  12. 			while (p->next != head && j != i)
  13. 			{
  14. 				p = p->next;
  15. 				++j;
  16. 			}
  17. 			if (p->next == head && j != i)
  18. 			{
  19. 				return NULL;
  20. 			}
  21. 			else
  22. 			{
  23. 				return p;
  24. 			}
  25.  
  26. 		}//向前找
  27. 		else
  28. 		{
  29. 			while (p->prev != head && j != i)
  30. 			{
  31. 				p = p->prev;
  32. 				++j;
  33. 			}
  34. 			if (p->prev == head && j != i)
  35. 				return NULL;
  36. 			else
  37. 				return p;
  38. 		}
  39. 	}

创建双向链表

  1. //创建双循环链表
  2. 	void CreateList(int n)
  3. 	{
  4. 		DateType* nodetemp = new DateType[n];
  5. 		for (rsize_t i = 0; i < n; i++)
  6. 		{
  7. 			cout << "Enter the element:  " << endl;
  8. 			cin >> nodetemp[i];
  9. 			Insert(i, nodetemp[i], 1);
  10. 		}
  11. 		delete[] nodetemp;
  12. 		
  13. 	}

打印双向循环链表

因为是双向循环链表，可以很简单的实现正序打印和逆序打印，所以这里用一个标志sign，来指定正序还是逆序打印链表元素

  1. //输出双循环链表所有结点的元素值,分为正序打印和逆序打印
  2. 	void PrintList(int sign)
  3. 	{
  4. 		//正序打印
  5. 		if (sign)
  6. 		{
  7. 			cout << "head " ;
  8. 			LinkNode<DateType>* p = head;
  9. 			while (p->next != head)
  10. 			{
  11. 				p = p->next;
  12. 				cout << "-> " << p->data;
  13. 			}
  14. 			cout << "->over" << endl;
  15. 		}//逆序打印
  16. 		else
  17. 		{
  18. 			cout << "head " << endl;
  19. 			LinkNode<DateType>* p = head;
  20. 			while (p->prev != head)
  21. 			{
  22. 				p = p->prev;
  23. 				cout << "-> " << p->data;
  24. 			}
  25. 			cout << "->over" << endl;
  26. 		}
  27. 	}

指定位置插入结点

任意位置插入首先要开辟一个节点，然后就是按照所个位置，改变指针的指向来把这个节点连接上去，看具体代码实现如下：

  1. //在pos的位置插入元素
  2. 	bool Insert(int pos, const DateType& data, int back_pos)
  3. 	{
  4. 		LinkNode<DateType>* p = Locate(pos, back_pos);
  5. 		if (!p)
  6. 			return false;
  7. 		LinkNode<DateType>* new_node = new LinkNode<DateType>(data);
  8. 		if (NULL == new_node)
  9. 		{
  10. 			cout << "内存分配失败" << endl;
  11. 			exit(-1);
  12. 		}
  13. 		//p结点后插入
  14. 		if (back_pos)
  15. 		{
  16. 			p->next->prev = new_node;
  17. 			new_node->prev = p;
  18. 			new_node->next = p->next;
  19. 			p->next = new_node;
  20. 		}//p结点前插入
  21. 		else
  22. 		{
  23. 			p->prev->next = new_node;
  24. 			new_node->next = p;
  25. 			new_node->prev = p->prev;
  26. 			p->prev = new_node;
  27. 		}return true;
  28. 	}

指定位置删除结点

删除就要考虑链表是否为空，防止删除头节点

  1. //删除pos位置的结点
  2. 	bool Delete(int pos, DateType& data,int back_pos)
  3. 	{
  4. 		LinkNode<DateType>* p = Locate(pos, back_pos);
  5. 		if (!p)
  6. 		{
  7. 			return false;
  8. 		}
  9. 		if (p == head )
  10. 		{
  11. 			cout << "请不要删除头节点" << endl;
  12. 			return false;
  13. 		}
  14. 		data = p->data;
  15. 		p->prev->next = p->next;
  16. 		p->next->prev = p->prev;
  17. 		delete p;
  18. 		return true;
  19. 	}

获取链表长度

  1. int Length()
  2. 	{
  3. 		LinkNode<DateType>* p = head;
  4. 		int i = 0;
  5. 		while (p->next != head)
  6. 		{
  7. 			++i;
  8. 			p = p->next;
  9. 		}
  10. 		return i;
  11.  
  12. 	}

销毁链表

在析构函数中实现链表的销毁

  1. //析构函数
  2. 	~LinkList()
  3. 	{
  4. 		LinkNode<DateType>* p, * q = head->next;
  5. 		while (q != head)
  6. 		{
  7. 			p = q;
  8. 			q = q->next;
  9. 			delete p;
  10. 		}
  11. 	}

整体代码以及测试

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include<iostream> //引入头文件
  3. #include<string>//C++中的字符串
  4. using namespace std; //标准命名空间
  5. /*
  6. 双向循环链表
  7. */
  8. template <class DateType>
  9. struct LinkNode
  10. {
  11. 	//数据域
  12. 	DateType data;
  13. 	//两个指针
  14. 	LinkNode<DateType>* prev;
  15. 	LinkNode<DateType>* next;
  16. 	LinkNode(DateType _data, LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :data(_data), prev(_prev), next(_next)
  17. 	{}
  18. 	LinkNode(LinkNode<DateType>* _prev = NULL, LinkNode<DateType>* _next = NULL) :prev(_prev), next(_next)
  19. 	{}
  20. };
  21. template<class DateType>
  22. class LinkList
  23. {
  24. public:
  25. 	//构造函数,初始化一个循环双链表
  26. 	LinkList()
  27. 	{
  28. 		head = new LinkNode<DateType>;
  29. 		if (head == NULL)
  30. 		{
  31. 			cout << "内存分配失败" << endl;
  32. 			exit(-1);
  33. 		}
  34. 		head->data = 0;
  35. 		head->next = head;
  36. 		head->prev = head;
  37. 	}
  38. 	//拷贝构造
  39. 	LinkList(const LinkList<DateType>& list2)
  40. 	{
  41. 		LinkNode<DateType>* p = list2.head->next;
  42. 		if (p == NULL)
  43. 		{
  44. 			cout << "内存分配失败" << endl;
  45. 			exit(-1);
  46. 		}
  47. 		head = new LinkNode<DateType>;
  48. 		LinkNode<DateType>* h = head;
  49. 		while (p!=list2.head)
  50. 		{
  51. 			LinkNode<DateType>* t = new LinkNode<DateType>;
  52. 			h->next = t;
  53. 			t->prev = h;
  54. 			t->data = p->data;
  55. 			p = p->next;
  56. 			h = h->next;
  57. 		}
  58. 		h->next = this->head;
  59. 		this->head->prev = h;
  60. 	}
  61. 	//析构函数
  62. 	~LinkList()
  63. 	{
  64. 		LinkNode<DateType>* p, * q = head->next;
  65. 		while (q != head)
  66. 		{
  67. 			p = q;
  68. 			q = q->next;
  69. 			delete p;
  70. 		}
  71. 	}
  72. 	//求双循环链表的长度
  73. 	int Length()
  74. 	{
  75. 		LinkNode<DateType>* p = head;
  76. 		int i = 0;
  77. 		while (p->next != head)
  78. 		{
  79. 			++i;
  80. 			p = p->next;
  81. 		}
  82. 		return i;
  83.  
  84. 	}
  85. 	//创建双循环链表
  86. 	void CreateList(int n)
  87. 	{
  88. 		DateType* nodetemp = new DateType[n];
  89. 		for (rsize_t i = 0; i < n; i++)
  90. 		{
  91. 			cout << "Enter the element:  " << endl;
  92. 			cin >> nodetemp[i];
  93. 			Insert(i, nodetemp[i], 1);
  94. 		}
  95. 		delete[] nodetemp;
  96. 		
  97. 	}
  98. 	//得到位置为pos的结点元素值
  99. 	bool GetElem(int pos,DateType& data)
  100. 	{
  101. 		LinkNode<DateType>* p = head;
  102. 		if (pos<0 || pos>Length())
  103. 		{
  104. 			cout << "输入的位置不合法" << endl;
  105. 			return false;
  106. 		}
  107. 		else {
  108. 			p = Locate(pos, 1);
  109. 			data = p->data;
  110. 		}
  111. 		return true;
  112. 	}
  113. 	//定位元素，back_pos=0时从头节点向前查第i个元素，d!=0时，从头节点向后找第i个元素
  114. 	LinkNode<DateType>* Locate(int i ,int back_pos)
  115. 	{
  116. 		if (head->next == head || i == 0) {
  117. 			return head;
  118. 		}
  119. 		int j = 0;
  120. 		LinkNode<DateType>* p = head;
  121. 		//从头节点往后找第i个元素
  122. 		if (back_pos)
  123. 		{
  124. 			while (p->next != head && j != i)
  125. 			{
  126. 				p = p->next;
  127. 				++j;
  128. 			}
  129. 			if (p->next == head && j != i)
  130. 			{
  131. 				return NULL;
  132. 			}
  133. 			else
  134. 			{
  135. 				return p;
  136. 			}
  137.  
  138. 		}//向前找
  139. 		else
  140. 		{
  141. 			while (p->prev != head && j != i)
  142. 			{
  143. 				p = p->prev;
  144. 				++j;
  145. 			}
  146. 			if (p->prev == head && j != i)
  147. 				return NULL;
  148. 			else
  149. 				return p;
  150. 		}
  151. 	}
  152. 	//在pos的位置插入元素
  153. 	bool Insert(int pos, const DateType& data, int back_pos)
  154. 	{
  155. 		LinkNode<DateType>* p = Locate(pos, back_pos);
  156. 		if (!p)
  157. 			return false;
  158. 		LinkNode<DateType>* new_node = new LinkNode<DateType>(data);
  159. 		if (NULL == new_node)
  160. 		{
  161. 			cout << "内存分配失败" << endl;
  162. 			exit(-1);
  163. 		}
  164. 		//p结点后插入
  165. 		if (back_pos)
  166. 		{
  167. 			p->next->prev = new_node;
  168. 			new_node->prev = p;
  169. 			new_node->next = p->next;
  170. 			p->next = new_node;
  171. 		}//p结点前插入
  172. 		else
  173. 		{
  174. 			p->prev->next = new_node;
  175. 			new_node->next = p;
  176. 			new_node->prev = p->prev;
  177. 			p->prev = new_node;
  178. 		}return true;
  179. 	}
  180. 	//输出双循环链表所有结点的元素值,分为正序打印和逆序打印
  181. 	void PrintList(int sign)
  182. 	{
  183. 		//正序打印
  184. 		if (sign)
  185. 		{
  186. 			cout << "head " ;
  187. 			LinkNode<DateType>* p = head;
  188. 			while (p->next != head)
  189. 			{
  190. 				p = p->next;
  191. 				cout << "-> " << p->data;
  192. 			}
  193. 			cout << "->over" << endl;
  194. 		}//逆序打印
  195. 		else
  196. 		{
  197. 			cout << "head " << endl;
  198. 			LinkNode<DateType>* p = head;
  199. 			while (p->prev != head)
  200. 			{
  201. 				p = p->prev;
  202. 				cout << "-> " << p->data;
  203. 			}
  204. 			cout << "->over" << endl;
  205. 		}
  206. 	}
  207. 	//删除pos位置的结点
  208. 	bool Delete(int pos, DateType& data,int back_pos)
  209. 	{
  210. 		LinkNode<DateType>* p = Locate(pos, back_pos);
  211. 		if (!p)
  212. 		{
  213. 			return false;
  214. 		}
  215. 		if (p == head )
  216. 		{
  217. 			cout << "请不要删除头节点" << endl;
  218. 			return false;
  219. 		}
  220. 		data = p->data;
  221. 		p->prev->next = p->next;
  222. 		p->next->prev = p->prev;
  223. 		delete p;
  224. 		return true;
  225. 	}
  226. private:
  227. 	LinkNode<DateType>* head;//头节点
  228. };
  229. int main()
  230. {
  231. 	LinkList<int> list;
  232. 	list.CreateList(5);
  233. 	list.PrintList(1);
  234. 	cout << "-----------------------" << endl;
  235. 	LinkList<int> list2(list);
  236. 	list2.PrintList(1);
  237. 	cout << "-----------------------" << endl;
  238. 	list.Insert(0, 10, 1);
  239. 	list.PrintList(1);
  240. 	cout << list.Length() << endl;
  241. 	cout << "-----------------------" << endl;
  242. 	int b = 0;
  243. 	list.Delete(0, b, 1);
  244. 	cout << b << endl;
  245. 	list.PrintList(1);
  246. 	cout << list.Length() << endl;
  247. 	cout << "-----------------------" << endl;
  248. 	list.GetElem(3, b);
  249. 	cout << b << endl;
  250. 	cout <<"---------------------------" << endl;
  251. 	system("pause");
  252. 	return EXIT_SUCCESS;
  253. }

链表和顺序表的对比

参考下表：

不同点顺序表链表
存储空间上物理上连续逻辑上连续
随机访问支持不支持
任意位置插入删除要移动元素，O(N)只要改变指针指向
插入数据要考虑扩容，会带来一定的空间消耗没有容量这个概念，可以按需申请和释放
缓存利用率高低
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/593743
推荐阅读
相关标签

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

  

闽ICP备14008679号