C++双向循环链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++双向循环链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7316字，纯文字阅读大概需要11分钟。

内容图文

先说一说双向循环链表的逆置，网上搜了一箩筐，用VS2017，基本上不成功，尽管明白道理是怎么回事，但是总感觉，不像c++的类，感觉用起来还得传指针啊，传链表啊等参数，不太像双向循环链表类的专属函数。虽然c语言写出来双向循环链表最好，但是既然学了c++，就尽量用一下c++的特点，能用多少是多少，也有利于对c++理解。好了废话不多说，凉一凉自己写的一般一般的双向循环链表吧。

  1 #include<iostream>
  2 
  3 using namespace std;
  4 
  5 template<class T> class DoubleLinkedList;
  6 
  7 template<class T>
  8 class MyNode    
  9 {
 10     friend class DoubleLinkedList<T>;
 11 private:
 12     T elem;
 13     MyNode *prev;
 14     MyNode *next;
 15     MyNode(){}
 16     MyNode(const T &theelem)
 17         :elem(theelem) {
 18         prev = NULL;
 19         next = NULL;
 20     }
 21 };
 22 
 23 template<class T>
 24 class DoubleLinkedList
 25 {
 26 public:
 27     DoubleLinkedList() 
 28     {
 29         first = new MyNode<T>(); 
 30         first->prev = first->next = first;
 31     }
 32     ~DoubleLinkedList(){ makeEmpty(); }
 33 
 34     bool IsEmpty(); // 判断链表是否为空
 35     void makeEmpty(); // 清空链表
 36     int  Length(); // 计算链表的长度
 37     void Insert(int index, const T &x); // 按照索引插入值（节点）
 38     void Push_head(const T &x); // 向链表的头部插入值  头插法
 39     void Push_back(const T &x); // 向链表的尾部插入值  尾插法
 40     void Delete(T x); // 按值删除节点
 41     void Index_Delete(const int &n); // 按索引删除节点
 42     void Invert(); // 逆置
 43     void Concatenate(DoubleLinkedList<T> &b); // 连接链表
 44     void show(); // 显示链表，这只是方便，一般得做成迭代器
 45 private:
 46     MyNode<T> *first;
 47 };
 48 template<class T>
 49 bool DoubleLinkedList<T>::IsEmpty()
 50 {
 51     return first == NULL;
 52 }
 53 
 54 template<class T>
 55 void DoubleLinkedList<T>::makeEmpty()
 56 {
 57     MyNode<T> *p;
 58     MyNode<T> *pNode = first->next;
 59     while (pNode != first)
 60     {
 61         p = pNode;
 62         pNode = pNode->next;
 63         delete p;
 64     }
 65     delete first;
 66     first = NULL;
 67 }
 68 
 69 template<class T>
 70 int  DoubleLinkedList<T>::Length()
 71 {
 72     int size = 0;
 73     MyNode<T> * p = first->next;
 74     if (IsEmpty()) cout << "The size is 0" << endl;
 75     else
 76     {
 77         while (p != first)
 78         {
 79             size++;
 80             p = p->next;
 81         }
 82     }
 83     return size;
 84 }
 85 
 86 template<class T>
 87 void DoubleLinkedList<T>::Insert(int index, const T &x)
 88 {
 89     MyNode<T> * insertNode = new MyNode<T>(x);
 90     MyNode<T> * p = first->next;
 91     if (Length() < index) {
 92         Push_back(x);
 93         return;
 94     }
 95     if (index < 1) {
 96         Push_head(x);
 97         return;
 98     }
 99     int count = 1;
100     while (count < index && p != first)
101     {
102         count++;
103         p = p->next;
104     }
105     insertNode->next = p;
106     p->prev->next = insertNode;
107     insertNode->prev = p->prev;
108     p->prev = insertNode;
109     return;
110 }
111 
112 template<class T>
113 void DoubleLinkedList<T>::Push_head(const T &x)
114 {
115     MyNode<T>* newNode = new MyNode<T>(x);
116     newNode->prev = first;
117     newNode->next = first->next;
118     first->next->prev = newNode;
119     first->next = newNode;
120 }
121 
122 template<class T>
123 void DoubleLinkedList<T>::Push_back(const T &x)
124 {
125     MyNode<T>* newNode = new MyNode<T>(x);
126     newNode->prev = first->prev;
127     newNode->next = first;
128     first->prev->next = newNode;
129     first->prev = newNode;
130 }
131 
132 template<class T>
133 void DoubleLinkedList<T>::Delete(T x)
134 {
135     MyNode<T>* p = first->next;
136     while (p->elem != x && p != first)
137     {
138         p = p->next;
139     }
140     p->next->prev = p->prev;
141     p->prev->next = p->next;
142     delete p;
143     return;
144 }
145 
146 template<class T>
147 void DoubleLinkedList<T>::Index_Delete(const int &n)
148 {
149     MyNode<T>* del = NULL;
150     MyNode<T>* p = first->next;
151     int count = 0;
152     if (n < 0)
153     {
154         del = p;
155         p->next->prev = first;
156         first->next = p->next;
157         delete del;
158         return;
159     }
160     else if(n > Length())
161     {
162         del = first->prev;
163         first->prev = del->prev;
164         del->prev->next = first;
165         delete del;
166         return;
167     }
168     while (count < n && p != first)
169     {
170         count++;
171         p = p->next;
172     }
173     del = p;
174     p->next->prev = p->prev;
175     p->prev->next = p->next;
176     delete del;
177 }
178 
179 template<class T>
180 void DoubleLinkedList<T>::Invert()
181 {
182         // 我这里只考虑链表至少有一个实数节点的情况
183         // 让p指向下一个节点，再把首节点与第一个实数节点做成一个循环链表，
184     MyNode<T>* p = first->next;
185     MyNode<T>* q = p;
186     p = p->next;
187     first->prev = q;
188     q->next = first;
189 
190        // 只要把接下来的节点一个一个放到头部就行了
191     while (p != first)
192     {
193         MyNode<T> *r;
194         r = p;
195         p = p->next;
196         r->prev = first;
197         r->next = first->next;
198         first->next->prev = r;
199         first->next = r;
200     }
201 }
202 
203 // 我选择将循环链表b的数值直接放到所连接链表的后面，这样改变b就不会改变连接后的链表
204 
205 template<class T>
206 void DoubleLinkedList<T>::Concatenate(DoubleLinkedList<T> &b)
207 {
208     MyNode<T>* p = b.first;
209     
210     if(IsEmpty())
211     {
212         first = p;
213     }
214     else if(b.IsEmpty())
215     {
216         return;
217     }
218     else {
219         while (p->next != b.first)
220         {
221             p = p->next;
222             Push_back(p->elem);
223         }
224         return;
225     }
226     return;
227 }
228 
229 template<class T>
230 void DoubleLinkedList<T>::show()
231 {
232     if (IsEmpty())
233     {
234         return;
235     }
236     MyNode<T>* p=first->next;
237     while (p != first)
238     {
239         cout << p->elem << " ";
240         p = p->next;
241     }
242     cout << endl;
243 
244 }
245 
246 // 下面测试的代码没啥可看的
247 
248 int main()
249 {
250     cout << "hello world!" << endl;
251 
252     DoubleLinkedList<int> a;
253     a.Push_head(30);
254     a.Push_head(20);
255     a.Push_head(10);
256     a.Push_back(40);
257     a.Push_back(50);
258     a.Push_back(60);
259     a.Index_Delete(2);
260     a.show();
261     a.Insert(1, 35);
262     a.Insert(-1, 100);
263     a.show();
264     int size;
265     
266     a.Delete(100);
267     size = a.Length();
268     a.Index_Delete(20);
269     a.show();
270     cout << "size: " << size << endl;
271 
272     DoubleLinkedList<int> intList;
273     DoubleLinkedList<int> intList1;
274 
275     intList.Push_back(1);
276     intList.Push_back(2);
277     intList.Push_back(3);
278     intList.Push_back(4);
279 
280     intList1.Push_back(5);
281     intList1.Push_back(6);
282     intList1.Push_back(7);
283     intList1.Push_back(8);
284     intList.Concatenate(intList1);
285     intList.show();
286     intList.Invert();
287     intList.show();
288     intList.Push_head(125);
289     intList.Push_back(21);
290     intList.Invert();
291     intList.show();
292     intList1.Delete(5);
293     intList1.Delete(6);
294     intList1.Delete(7);
295     intList1.Delete(8);
296     intList1.show();
297     return 0;
298 }

内容总结

以上是互联网集市为您收集整理的C++双向循环链表全部内容，希望文章能够帮你解决C++双向循环链表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/634598.html

来源：【匿名】

【上一篇】哈夫曼编解码压缩解压文件—C++实现【下一篇】c++有个库什么的吗?

更多 ►

【C++双向循环链表】教程文章相关的互联网学习教程文章

C++的另一种for循环写法，和C#的foreach语法很类似，不需要知道数组的类型；C++：for（auto& item:items)C#:foreach(var item in items) 1int ages [10] = {0};2//常规for循环 3for(int i=0;i<(sizeof(ages)/sizeof(ages[0]));i++)4 { 5 ages[i]=i;6 cout<<ages[i]<<endl;7 }8//for(auto 赋值操作 9for(auto& age :ages) 10 { 11 age+=10; 12 } 13 cout<<"----------"<<endl; ...

c++ 智能指针及循环引用问题

c++智能指针介绍由于 C++ 语言没有自动内存回收机制，程序员每次 new 出来的内存都要手动 delete，比如流程太复杂，最终导致没有 delete，异常导致程序过早退出，没有执行 delete 的情况并不罕见，并造成内存泄露。如此c++引入智能指针，智能指针即是C++ RAII的一种应用，可用于动态资源管理，资源即对象的管理策略。智能指针在 <memory> 标头文件的 std 命名空间中定义。它们对 RAII 或获取资源即初始化编程惯用法至关重要。RAI...

C++ 循环缓冲类【代码】【图】

昨天看到博客园有个面试者笔试出现此题，昨天大概给出思路，今天经过思考将实现，并做出优化改进，逻辑易懂，基本都可以看懂，经过初步测试正确。代码如下： 1// MindryBuffer.cpp : 定义控制台应用程序的入口点。2//3 4 #include "stdafx.h" 5 #include <iostream>6 #include <string.h>7usingnamespace std;8 9class CMindryBuffer10{11public:12 CMindryBuffer(int iBufLenth = MindryBufferLenth);13 ~CMindryBu...

[c/c++奇技淫巧]不用循环判断输出5到1【代码】【图】

偶尔看到的一道题，和哥们几个讨论了一下，这玩意，不是循环就是递归了么，当然，只要达到目的，管他什么循环递归，对吧。现在总结一下我们能想到的所有的方法，大家有新的想法欢迎跟帖讨论~~ ok，开工。第一条，最简单的，直接输出。（因为输出结果都差不多，就不一个一个截图了）printf("5 4 3 2 1\n"); 第二条，简单的循环。 // for 循环 for(int =5; i !=0; i--) { printf("%d\n",i); } // while 循环 ...

循环链表简单操作 C++【代码】【图】

带有头节点的循环链表。头节点的数据域为空，在查找某元素是否在链表中时，可用与存放该元素。头节点的next指针指向第一个元素。最后一个元素指向头节点。如图： //CircularList.h文件#pragma once template<class T> struct listNode{T element;listNode<T>* next;listNode(){}listNode(const T&theElement){ this->element = theElement; }listNode(const T&theElement, listNode<T>*theNext){ this->element = theElement; th...

约瑟夫问题的C++简单实现（循环链表）

[code=C++] /* author:jiangxin Blog:http://blog.csdn.net/jiangxinnju Function:method of Josephus question */ #include <iostream>using namespace std;struct node { int seq; node *next; }; typedef struct node NODE;void test_Josephus() { /*假设共有n人，从第s个人开始数数，每数到m该人出列，后面的人重新开始数，知道全部人出列*/ int n,s,m; NODE *head,*last,*current,*prev; ...

循环链表的创建、插入、删除、逆序、显示（C++实现）【图】

对于单链表，因为每一个结点仅仅存储了向后的指针。到了尾标志就停止了向后链的操作，这样，其中某一结点就无法找到它的前驱结点了。对于单链表的操作大家能够看我的这篇博客http://blog.csdn.net/zxnsirius/article/details/51183055我们将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成了一个环。这样的头尾相接的单链表称为单循环链表，简称循环链表。以下是循环链表的综合操作的样例程序执行结果/*‘)...

C++中循环控制语句

循环控制语句更改执行的正常序列。当执行离开一个范围时，所有在该范围中创建的自动对象都会被销毁。C++ 提供了下列的控制语句。点击链接查看每个语句的细节。控制语句描述break 语句终止 loop 或 switch 语句，程序流将继续执行紧接着 loop 或 switch 的下一条语句。continue 语句引起循环跳过主体的剩余部分，立即重新开始测试条件。goto 语句将控制转移到被标记的语句。但是不建议在程序中使用 goto 语句。注意：您可以按 Ctrl ...

C++PrimerPlus 练习题循环【代码】

第四题单利和复利// 单利投资和复利投资本金为100元int count = 1;// 本金int principal = 100;// A的第一年的收获float a_alone = principal * 0.1;// B第一年的收获利息float b_double = principal * 0.05;// b 收获的总和float b_Allhavest = b_double;while (b_Allhavest < a_alone * count){b_double += b_double * 0.05;b_Allhavest += b_double;cout << "b的利息-------" << b_double << endl;count++;}int year =...

C++ 循环队列实现缓冲类【代码】

好久没有写博客了，前段时间做项目需要一个缓冲机制用来缓存视频帧。下面是自己实现的视频缓冲类。在此类中用循环队列实现了视频帧数据的入队、出队。在类中使用互斥对象避免出入队出现错误。下面是代码。 /*****************头文件****************/using namespace std;#define MAXSIZE 50typedef struct {int iSize;//数据的大小char *cdata; }bufData; typedef struct {bufData mdata[MAXSIZE];int iRead;//队头int iWrite...

深入学习c++--智能指针(二) weak_ptr（打破shared_ptr循环引用）【代码】【图】

1. 几种智能指针1. auto_ptr: c++11中推荐不使用他(放弃)2. shared_ptr: 每添加一次引用就+1，减少一次引用，就-1；做到指针进行共享3. unique_ptr: 一个指针同时只能有一个使用者使用4. weaked_ptr: 与shared_ptr搭配使用1.1 weak_ptr参考：https://zh.cppreference.com/w/cpp/memory/weak_ptrstd::weak_ptr 是一种智能指针，它对被 std::shared_ptr 管理的对象存在非拥有性（“弱”）引用。在访问所引用的对象前必须先转换为 ...

map,vector 等容器内容的循环删除问题(C++)【代码】

map,vector 等容器内容的循环删除问题(C++) map,vector等容器的循环删除不能用普通的方法删除:for(auto p=list.begin();p!=list.end();p++)list.erase(p);类似的方式,会出错的,不信你调试试试 :)这里使用了一个` iterator` 的一个自增/自减 ,来巧妙的实现了, 删除当前的`iterator,` 但是有给当前的`iterator`赋值为其下一个的操作,不至于删除后,当前的 `iterator` 就失效了! 代码: 1 #include <iostream>2 #include <vector>3 #inc...

循环队列/顺序队列（C++）【代码】【图】

队列（queue）是一种限定存取位置的线性变。他允许在表的一端插入，在另一端删除。这个和计算机调度策略中的先来先服务FCFS(First Come/First Served)是一样的。队列中可以插入的一端为队尾（rear），允许删除的一端称为队头（front）。队列也分为两种，一种是用数组的存储表示，一种是基于链表的存储表示。基于数组的存储表示的队列被称为顺序队列。其数据成员包括，一维数组elements用来存储数据，指针front和rear用来指示队尾队...

循环双向链表的C++实现【代码】

循环双向链表的增删查改等基本操作#include<iostream> #include<assert.h> using namespace std; typedef int DataType; struct ListNode {DataType _data;ListNode* _prev;ListNode* _next;ListNode(const DataType& x):_data(x),_prev(NULL),_next(NULL){}ListNode():_data(0),_prev(NULL),_next(NULL){} }; class List { private:ListNode _head; public:List(){_head._prev=&_head;_head._next=&_head;}~List(){clear();}void ...

单链表，循环链表，双向链表（C++实现）【代码】【图】

首先是单链表（带附加表头），实现类代码如下： 1 template<class T>2struct LinkNode{//链表节点 3 T data;4 LinkNode *link;5 LinkNode(const T& args,LinkNode<T> *ptr=NULL){6 data=args;7 link=ptr;8 }9};10 11 template<class T>12class List{//带附加头节点的单链表 13protected:14 LinkNode<T> *first;//链表头指针 15public:16 List(){17 first=new LinkN...

首页 / C++ / C++双向循环链表

C++双向循环链表

内容导读

内容图文

内容总结

内容备注

内容手机端

【C++双向循环链表】教程文章相关的互联网学习教程文章

C++ for 循环【代码】

c++ 智能指针及循环引用问题

C++ 循环缓冲类【代码】【图】

[c/c++奇技淫巧]不用循环判断输出5到1【代码】【图】

循环链表简单操作 C++【代码】【图】

约瑟夫问题的C++简单实现（循环链表）

循环链表的创建、插入、删除、逆序、显示（C++实现）【图】

C++中循环控制语句

C++PrimerPlus 练习题循环【代码】

C++ 循环队列实现缓冲类【代码】

深入学习c++--智能指针(二) weak_ptr（打破shared_ptr循环引用）【代码】【图】

map,vector 等容器内容的循环删除问题(C++)【代码】

循环队列/顺序队列（C++）【代码】【图】

循环双向链表的C++实现【代码】

单链表，循环链表，双向链表（C++实现）【代码】【图】

循环链表 - 相关标签

C++ - 技术教程分类

C++ - 最新教程

C++ - 最热教程