数据结构【二】:循环链表和双向链表(C++)

循环链表


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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
LinkNode *next=NULL;
T data;
};
template<class T>
class List
{
public:
List();//构造函数
List(const T& x);//构造函数
List( List<T>& L);//复制构造函数
~List(){makeEmpty();};
void makeEmpty();//置空表
int getLength()const;//获取表长
LinkNode<T> *getHead()const{return head;};//获取头节点地址
LinkNode<T> *Search(T x);// 查询含有数据x节点的地址 失败返回NULL
LinkNode<T> *Locate(int i);// 查询第i个 数据的地址 失败返回NULL
bool getData(int i,T&x);//用x获取第i个数据
bool setData(int i,T &x);//用x替换第i个位替上的数据
bool Insert(int i,T &x);//在第i个元素后插入数据x
bool Remove(int i,T &x);//删除第i个数据并用x返回
bool isEmpyty()const; //判断表空
bool isFull()const ;//判断表满
void inputQianCha();//清空链表,输入结束标志,根据标志判断来输入数据
void inputHouCha();//清空链表,输入结束标志,根据标志判断来输入数据
void output();//输出
List<T>&operator=(List<T> &L);
protected:
LinkNode<T> *head;
};
template <class T>
List<T>::List()
{
head=new LinkNode<T>;
head->next=head; //增加
}
template <class T>
List<T>::List(const T& x)
{
head=new LinkNode<T>(x);
head->next=head; //增加
}
template <class T>
List<T>::List(List<T>& L)
{
LinkNode<T> *p1,*p2,*newNode,*Lhead;
p1=L.getHead()->next;
Lhead=L.getHead(); //增加
p2=head=new LinkNode<T>; //p2=head=new LinkNode<T>;必须要有 new LinkNode<T>,因为此时head还没有构造出来。
while(p1!=Lhead)
{
newNode=new LinkNode<T>;
newNode->data=p1->data;
p2->next=newNode;
p2=newNode;
p1=p1->next;
}
p2->next=head; //增加
}
template <class T>
void List<T>::makeEmpty()
{
LinkNode<T> *p=head->next;
while(head->next!=head) //改变
{
head->next=p->next;
delete p;
p=head->next;
}
}
template <class T>
int List<T>::getLength()const
{
LinkNode<T> *p=head->next;
int num=0;
while(p!=head) //改变
{
num++;
p=p->next;
}
return num;
}
template <class T>
LinkNode<T>* List<T>::Search(T x)
{
LinkNode<T> *p=head->next;
while(p!=head) //修改
{
if(p->data==x)
return p;
p=p->next;
}
return NULL; //修改为NULL,因为循环链表最后元素的下一个指向为head.

}
template <class T>
LinkNode<T>* List<T>::Locate(int i)
{
if(i<=0) return NULL;
int num=1;
LinkNode<T> *p=head->next;
while(i!=num&&p!=head) //修改
{
num++;
p=p->next;
}
if(p==head)
return NULL; //添加为NULL,因为循环链表最后元素的下一个指向为head. 没找到必须返回NULL
else
return p;
}
template <class T>
bool List<T>::getData(int i,T&x)
{
LinkNode<T> *p=Locate(i);
if(p==NULL)
return false;
else
{
x=p->data;
return true;
}
}
template <class T>
bool List<T>::setData(int i,T &x)
{
LinkNode<T> *p=Locate(i);
if(p==NULL)
return false;
else
{
p->data=x;
return true;
}
}
template <class T>
bool List<T>::Insert(int i,T &x)
{
LinkNode<T> *p1=Locate(i),*p2;
if(p1==NULL)
return false;
else
{
p2=new LinkNode<T>(x);
if(p2==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
p2->next=p1->next;
p1->next=p2;
return true;
}
}
template <class T>
bool List<T>::Remove(int i,T &x)
{
LinkNode<T> *p1=Locate(i-1),*p2;
if(p1==NULL||p1->next==head) //修改
return false;
else
{
p2=p1->next;
p1->next=p2->next;
x=p2->data;
delete p2;
return true;
}
}
template <class T>
bool List<T>::isEmpyty()const
{
if(head->next==head)
return true;
else
return
false;
}
template <class T>
bool List<T>::isFull()const
{
return false;
}
template <class T>
void List<T>::inputQianCha()
{
makeEmpty();
T endTag,val;
LinkNode<T> *newNode;
cout<<"请输入结束标志";
cin>>endTag;
while(1)
{
cin>>val;
if(val==endTag)
break;
newNode=new LinkNode<T>;
newNode->data=val;
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
newNode->next=head->next;
head->next=newNode;
}
}
template <class T>
void List<T>::inputHouCha()
{
makeEmpty();
T endTag,val;
LinkNode<T> *newNode,*p=head;
cout<<"请输入结束标志";
cin>>endTag;
while(1)
{
cin>>val;
if(val==endTag)
break;
newNode=new LinkNode<T>;
newNode->data=val;
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
p->next=newNode;
p=p->next;
}
p->next=head; //增加
}
template <class T>
void List<T>::output()
{
LinkNode<T> *p=head->next;
while(p!=head)
{
cout<<p->data<<",";
p=p->next;
}
cout<<endl;
}
template <class T>
List<T>& List<T>::operator=(List<T> &L)
{
makeEmpty(); //先清空原有的数据
LinkNode<T> *p1,*p2,*newNode,*Lhead;
p1=L.getHead()->next;
Lhead=L.getHead();
p2=head;
while(p1!=Lhead)
{
newNode=new LinkNode<T>;
newNode->data=p1->data;
p2->next=newNode;
p2=newNode;
p1=p1->next;
}
p2->next=head;
return *this;
}
int main()
{
List<int> test1,test2;
int a,len,i;
test1.inputHouCha();
test2.inputQianCha();
test1.output();
test2.output();
test2=test1;
test2.output();
}
/*
和单链表区别:
主要是构造的时候进行尾部连接头部:
1、构造函数中 添加head->next=head;
2、复制构造函数和重载=号函数中增加Lhead=L.getHead();用while(p1!=Lhead)来判别循环表结束 最后增加p2->next=head; 为末尾添加head连接;
3、 前插法构造不需要变化,后插法需要在最后增加p2->next=head; 为末尾添加head连接;
其他函数有需要遍历的,判断结束条件改变为!+head即可:
4、置空函数makeEmpty()获取表长函数getLength()查询数据函数Search(T x)获取第i个元素的地址函数Locate(int i)删除元素函数Remove(int i,T &x)判空函数isEmpyty()
输出函数output()只需要变化判断结束条件head->next!=head
5、返回指针类若遍历后找不到,则返回NULL,因为循环链表最后元素的下一个指向为head而不是NULL 不能用最后的指向代替 。若不修改,会影响调用的判断
6、 其他函数不需要改变
*/

和单链表区别:
主要是构造的时候进行尾部连接头部:
1、构造函数中 添加head->next=head;
2、复制构造函数和重载=号函数中增加Lhead=L.getHead();用while(p1!=Lhead)来判别循环表结束 最后增加p2->next=head; 为末尾添加head连接;
3、 前插法构造不需要变化,后插法需要在最后增加p2->next=head; 为末尾添加head连接
其他函数有需要遍历的,判断结束条件改变为!=head即可:
4、置空函数makeEmpty()获取表长函数getLength()查询数据函数Search(T x)获取第i个元素的地址函数Locate(int i)删除元素函数Remove(int i,T &x)判空函数isEmpyty()
输出函数output()只需要变化判断结束条件head->next!=head
5、 返回指针类若遍历后找不到,则返回NULL,因为循环链表最后元素的下一个指向为head而不是NULL 不能用最后的指向代替 。若不修改,会影响调用的判断

双向链表(带附加头结点的循环链表形式 )


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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
LinkNode *left=NULL,*next=NULL;
T data;
} ;
template<class T>
class List
{
public:
List();//构造函数
List(const T& x);//构造函数
List( List<T>& L);//复制构造函数
~List(){makeEmpty();};
void makeEmpty();//置空表
int getLength()const;//获取表长
LinkNode<T> *getHead()const{return head;};//获取头节点地址
LinkNode<T> *Search(T x);// 向后查询含有数据x节点的地址 失败返回NULL
LinkNode<T> *Locate(int i,int d);// 查询向右(向左)第i个 数据的地址,d!=0向右查找 d==0向左查找失败返回NULL
bool getData(int i,T&x,int d);//用x获取向右(向左)第i个数据, d!=0向右查找 d==0向左查找
bool setData(int i,T &x,int d);//用x替换向右(向左)第i个数据, d!=0向右查找 d==0向左查找
bool Insert(int i,T &x,int d);//在向右(向左)第i个元素后插入数据x d!=0向右查找 d==0向左查找
bool Remove(int i,T &x,int d);//删除第向右(向左)i个数据并用x返回 d!=0向右查找 d==0向左查找
bool isEmpyty()const; //判断表空
bool isFull()const ;//判断表满
void inputQianCha();//输入结束标志,根据标志判断来输入数据
void inputHouCha();//输入结束标志,根据标志判断来输入数据
void output();//输出
List<T>&operator=(List<T> &L);
protected:
LinkNode<T> *head;
};
template <class T>
List<T>::List()
{
head=new LinkNode<T>;
head->next=head;
head->left=head;

}
template <class T>
List<T>::List(const T& x)
{
head=new LinkNode<T>(x);
head->right=head;
head->left=head;
}
template <class T>
List<T>::List(List<T>& L)
{
LinkNode<T> *p1,*newNode,*Lhead;
p1=L.getHead()->next;
Lhead=L.getHead();
head=new LinkNode<T>; //必须要有 new LinkNode<T>,因为此时head还没有构造出来。
head->left=head->next=head; //加上这步构造一个头节点
while(p1!=Lhead)
{
newNode=new LinkNode<T>;
newNode->data=p1->data;
newNode->next=head; //后插法四步 ,由于是双向链表,可以直接通过head操作。
newNode->left=head->left;
head->left->next=newNode;
head->left=newNode;
p1=p1->next; //别忘了p1需要往后移动
}
}
template <class T>
void List<T>::makeEmpty()
{
LinkNode<T> *p=head->next;
while(head->next!=head)
{
head->next=p->next;
delete p;
p=head->next;
}
head->left=head; //增添左指向为head
}
template <class T>
void List<T>::inputQianCha()
{
makeEmpty();
T endTag,val;
LinkNode<T> *newNode;
cout<<"请输入结束标志";
cin>>endTag;
while(1)
{
cin>>val;
if(val==endTag)
break;
newNode=new LinkNode<T>;
newNode->data=val;
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
newNode->next=head->next;
head->next=newNode;
newNode->next->left=newNode;
newNode->left=head;
}
}
template <class T>
void List<T>::inputHouCha()
{
makeEmpty();
T endTag,val;
LinkNode<T> *newNode,*p=head;
cout<<"请输入结束标志";
cin>>endTag;
while(1)
{
cin>>val;
if(val==endTag)
break;
newNode=new LinkNode<T>;
newNode->data=val;
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
newNode->next=head;
newNode->left=head->left;
head->left->next=newNode;
head->left=newNode;
}
}
template <class T>
void List<T>::output()
{
LinkNode<T> *p=head->next;
while(p!=head)
{
cout<<p->data<<",";
p=p->next;
}
cout<<endl;
}
template <class T>
int List<T>::getLength()const
{
LinkNode<T> *p=head->next;
int num=0;
while(p!=head)
{
num++;
p=p->next;
}
return num;
}
template <class T>
LinkNode<T>* List<T>::Search(T x)
{
LinkNode<T> *p=head->next;
while(p!=head)
{
if(p->data==x)
return p;
p=p->next;
}
return NULL; //修改为NULL,因为循环链表最后元素的下一个指向为head.
}
template <class T>
LinkNode<T>* List<T>::Locate(int i,int d)
{
if(i<=0) return NULL;
int num=1;
LinkNode<T> *p;
if(d!=0) //增加判断语句是左查询还是右查询
p=head->next;
else
p=head->left;
while(i!=num&&p!=head) //修改
{
num++;
if(d!=0) //增加判断语句是左查询还是右查询
p=p->next;
else
p=p->left;
}
if(p==head)
return NULL; //添加为NULL,因为循环链表最后元素的下一个指向为head. 没找到必须返回NULL
else
return p;
}
template <class T>
bool List<T>::getData(int i,T&x,int d)
{
LinkNode<T> *p=Locate(i,d);
if(p==NULL)
return false;
else
{
x=p->data;
return true;
}
}
template <class T>
bool List<T>::setData(int i,T &x,int d)
{
LinkNode<T> *p=Locate(i,d);
if(p==NULL)
return false;
else
{
p->data=x;
return true;
}
}
template <class T>
bool List<T>::Insert(int i,T &x,int d)
{
LinkNode<T> *p1,*newNode;
if(i!=0)
p1=Locate(i,d);
else //增加一种空表插入判断
p1=head;
if(p1==NULL)
return false;
else
{
newNode=new LinkNode<T>;
newNode->data=x;
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
newNode->next=p1->next;
p1->next=newNode;
newNode->next->left=newNode;
newNode->left=p1;
return true;
}
}
template <class T>
bool List<T>::Remove(int i,T &x,int d)
{
LinkNode<T> *p1=Locate(i,d); //由于是双向链表,所以不用再找第i-1个了
if(p1==NULL) //修改
return false;
else
{
p1->left->next=p1->next;
p1->next->left=p1->left;
delete p1;
return true;
}
}
template <class T>
bool List<T>::isEmpyty()const
{
if(head->next==head)
return true;
else
return
false;
}
template <class T>
bool List<T>::isFull()const
{
return false;
}
template <class T>
List<T>& List<T>::operator=(List<T> &L)
{
makeEmpty(); //清空链表 ,只剩下头节点
LinkNode<T> *p1,*newNode,*Lhead;
p1=L.getHead()->next;
Lhead=L.getHead();
while(p1!=Lhead)
{
newNode=new LinkNode<T>;
newNode->data=p1->data;
newNode->next=head; //后插法四步 ,由于是双向链表,可以直接通过head操作。
newNode->left=head->left;
head->left->next=newNode;
head->left=newNode;

p1=p1->next; //别忘了p1需要往后移动
}
return *this;
}
int main()
{
List<int> test1;
int a,len;
int x;
test1.inputHouCha();
test1.output();
test1.makeEmpty();
List<int> test2(test1);
test2.output();
}
/*双向循环链表和单链表的区别:
1、结点中有前驱和后驱两个连接指针
2、构造函数中需要对前指针后指针赋头节点值 head->right=head->left=head;
3、前插法创建和后插法:均需要四步。注意分析。
4、 置空函数需要添加左指向为head
5、按顺序查找并返回地址进行判断添加。之后其他函数如获取数据等直接调用即可
6、插入函数Insert需要多一种第0个元素后插入的条件,即空表插入的条件。
7、删除函数Remove由于是双向链表,所以不用再找第i-1个了 判断也不需要考虑第i-1个是最后一个了。
8、复制构造函数和重载=号,需要清空链表,构造使用后插法则4步即可
*/

双向循环链表和单链表的区别:
1、结点中有前驱和后驱两个连接指针
2、构造函数中需要对前指针后指针赋头节点值 head->right=head->left=head;
3、前插法创建和后插法:均需要四步。注意分析。
4、 置空函数需要添加左指向为head
5、按顺序查找并返回地址进行判断添加。之后其他函数如获取数据等直接调用即可
6、插入函数Insert需要多一种第0个元素后插入的条件,即空表插入的条件。
7、删除函数Remove由于是双向链表,所以不用再找第i-1个了 判断也不需要考虑第i-1个是最后一个了。
8、复制构造函数和重载=号,需要清空链表,构造使用后插法则4步即可

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~