本文实例为大家分享了C++实现双向循环链表的具体代码，供大家参考，具体内容如下
一、概念
1.在双链表中的每个结点应有两个链接指针：
lLink -> 指向前驱结点 （前驱指针或者左链指针）
rLink->指向后继结点（后驱指针或者右链指针）
2.双链表常采用带附加头结点的循环链表方式：
first：头指针，不存放数据，或者存放特殊要求的数据。它的lLink指向双链表的尾结点（最后一个结点），
它的rLink指向双链表的首结点（第一个有效结点）。链表的首结点的左链指针lLink和尾结点的右链指针
rLink都指向附加头结点。
二、实现程序
1.DblList.h
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
|
#ifndef DblList_h#define DblList_h#include <iostream>using namespace std; template <class T>struct DblNode { // 链表结点定义 T data; DblNode<T> *lLink, *rLink; // 链表前驱（左链）和后继（右链）指针 DblNode(DblNode<T> *left = NULL, DblNode<T> *right = NULL):lLink(left), rLink(right){} // 构造函数 DblNode(T value, DblNode<T> *left = NULL, DblNode<T> *right = NULL):data(value), lLink(left), rLink(right){} // 构造函数}; template <class T>class DblList { // 双链表（双向循环链表）public: DblList(); // 构造函数：建立附加头结点 ~DblList(); // 析构函数：释放所有存储 void createDblList(); // 创建双向链表 int Length()const; // 计算双链表的长度 bool isEmpty(); // 判双链表空否 DblNode<T> *getHead()const; // 取附加头结点 void setHead(DblNode<T> *ptr); // 设置附加头结点地址 DblNode<T> *Search(const T x); // 在链表中沿后继方向寻找等于给定值x的结点 DblNode<T> *Locate(int i, int d); // 在链表中定位第i个结点，d=0按前驱方向，否则按后继方向 bool Insert(int i, const T x, int d); // 在第i个结点后插入x，d=0按前驱方向，否则按后继方向 bool Remove(int i, T &x, int d); // 删除第i个结点，x带回删除其值，d=0按前驱方向，否则按后继方向 void Output(); // 输出双链表中的数据private: DblNode<T> *first; // 附加头结点}; template <class T>DblList<T>::DblList() { // 构造函数：建立附加头结点 first = new DblNode<T>(); if(NULL == first) { cerr << "动态分配内存空间失败！" << endl; exit(1); } first->rLink = first->lLink = first; // 指向自身} template <class T>DblList<T>::~DblList() { // 析构函数：释放所有存储 DblNode<T> *current = first->rLink; while(current != first) { current->rLink->lLink = current->lLink; // 从lLink链中摘下 current->lLink->rLink = current->rLink; // 从rLink链中摘下 delete current; // 释放空间 current = first->rLink; } delete first; first = NULL;} template <class T>void DblList<T>::createDblList() { // 创建双向链表 int n, val; DblNode<T> *current = first; cout << "请输入要输入的个数n:"; cin >> n; cout << "请输入要输入的数：" << endl; for(int i = 0; i < n; i++) { cin >> val; DblNode<T> *newNode = new DblNode<T>(val); if(NULL == newNode) { cerr << "动态分配内存空间失败！" << endl; exit(1); } // 尾插入 while(current->rLink != first) current = current->rLink; // 往后继方向移动 newNode->rLink = current->rLink; current->rLink = newNode; newNode->rLink->lLink = newNode; newNode->lLink = current; current = current->rLink; // current往后移 }} template <class T>int DblList<T>::Length()const { // 计算双链表的长度 DblNode<T> *current = first->rLink; int count = 0; while(current != first) { current = current->rLink; count++; } return count;} template <class T>bool DblList<T>::isEmpty() { // 判双链表空否 return first->rLink == first;} template <class T>DblNode<T> *DblList<T>::getHead()const { // 取附加头结点 return first;} template <class T>void DblList<T>::setHead(DblNode<T> *ptr) { // 设置附加头结点地址 first = ptr;} template <class T>DblNode<T> *DblList<T>::Search(const T x) { // 在链表中沿后继方向寻找等于给定值x的结点 DblNode<T> *current = first->rLink; while(current != first && current->data != x) current = current->rLink; if(current != first) return current; // 搜索成功 else // 搜索失败 return NULL;} template <class T>DblNode<T> *DblList<T>::Locate(int i, int d) { // 定位 if((first->rLink == first) || (i = 0)) return first; DblNode<T> *current; if(d == 0) current = first->lLink; // 搜索前驱方向 else current = first->rLink; for(int j = 1; j < i; j++) { if(current == first) break; else if(d == 0) current = current->lLink; else current = current->rLink; } if(current != first) // 定位成功 return current; else return NULL;} template <class T>bool DblList<T>::Insert(int i, const T x, int d) { // 插入 DblNode<T> *current = Locate(i, d); // 查找第i个结点 if(current == NULL) // i不合理，插入失败 return false; DblNode<T> *newNode = new DblNode<T>(x); if(newNode == NULL) { cerr << "内存空间分配失败！" << endl; exit(1); } if(d == 0) { // 前驱方向插入 newNode->lLink = current->lLink; current->lLink = newNode; newNode->lLink->rLink = newNode; newNode->rLink = current; } else { // 后继方向插入 newNode->rLink = current->rLink; current->rLink = newNode; newNode->rLink->lLink = newNode; newNode->lLink = current; } return true;} template <class T>bool DblList<T>::Remove(int i, T &x, int d) { // 删除 DblNode<T> *current = Locate(i, d); // 查找第i个结点 if(current == NULL) // i不合理，插入失败 return false; current->rLink->lLink = current->lLink; // 从lLink链中摘下 current->lLink->rLink = current->rLink; // 从rLink链中摘下 x = current->data; delete current; // 释放空间 current = NULL; // 指向空 return true; // 删除成功} template <class T>void DblList<T>::Output() { // 输出双链表中的数据 DblNode<T> *current = first->rLink; while(current != first) { cout << current->data << " "; current = current->rLink; } cout << endl;} #endif /* DblList_h */ |
2.main.cpp
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include "DblList.h"using namespace std; int main(int argc, const char * argv[]) { int finished = 0, choice, i, x, d, len; // i存储第i个，d:存储方向 -》0表示前驱方向，否则为后继方向 DblList<int> L; DblNode<int> *head = NULL, *current; while(!finished) { cout << "\n*********菜单*********\n"; cout << "1:建立双链表\n"; cout << "2:双链表的长度\n"; cout << "3:双链表是否为空？\n"; cout << "4:取附加头结点\n"; cout << "5:设置附加头结点地址\n"; cout << "6:在链表中沿后继方向寻找等于给定值x的结点\n"; cout << "7:在链表中定位第i个结点，d=0按前驱方向，否则按后继方向\n"; cout << "8:在第i个结点后插入x，d=0按前驱方向，否则按后继方向\n"; cout << "9:删除第i个结点，x带回删除其值，d=0按前驱方向，否则按后继方向\n"; cout << "10:输出双链表中的数据:\n"; cout << "11:退出\n"; cout << "请输入选择[1-11]：\n"; cin >> choice; switch(choice) { case 1: L.createDblList(); // 建立双链表 break; case 2: len = L.Length(); // 双链表的长度 cout << "双链表的长度为：" << len << endl; break; case 3: if(L.isEmpty()) // 双链表是否为空 cout << "双链表为空" << endl; else cout << "双链表不空" << endl; break; case 4: head = L.getHead(); break; case 5: L.setHead(head); // 设置附加头结点地址 break; case 6: cout << "请输入要查找的值x:"; cin >> x; if(L.Search(x) != NULL) cout << "查找成功！" << endl; else cout << "查找失败！" << endl; break; case 7: cout << "请输入要定位第i个结点的i和方向d(d=0按前驱方向，否则按后继方向):"; cin >> i >> d; current = L.Locate(i, d); if(current == NULL) cout << "定位失败!" << endl; else cout << "定位成功！" << endl; break; case 8: cout << "在第i个结点后插入x，d=0按前驱方向，否则按后继方向。请输入i, x和d:"; cin >> i >> x >> d; if(L.Insert(i, x, d)) cout << "插入成功!" << endl; else cout << "插入失败！" << endl; break; case 9: cout << "删除第i个结点，x带回删除其值，d=0按前驱方向，否则按后继方向。请输入i和d:"; cin >> i >> d; if(L.Remove(i, x, d)) cout << "删除成功，删除的值为：" << x << endl; else cout << "删除失败！" << endl; break; case 10: cout << "双链表中的数据为：" << endl; L.Output(); break; case 11: finished = 1; break; default: cout << "输入错误, 请重新输入！" << endl; } // switch } // while return 0;} |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/chuanzhouxiao/article/details/85789918
