数据结构——Doubly_Linked_List的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED
template <class Node_entry>
struct Node
{
// data members
Node_entry entry;
Node<Node_entry> *next;
Node<Node_entry> *back;
// constructors
Node();
Node(Node_entry item, Node<Node_entry> *link_back = nullptr,
Node<Node_entry> *link_next = nullptr);
// The parameter add_on is set an default value null.
};
#endif // NODE_H_INCLUDED

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "Node.h"
template <class Node_entry>
Node<Node_entry>::Node()
/*Pre:None.
Post:Initialize the next links to Null.
*/
{
back = nullptr;
next = nullptr;
}
template <class Node_entry>
Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *link_back,
Node<Node_entry> *link_next)
/*Pre:None.
Post:Add a first node to Node structure.
*/
{
entry = item;
back = link_back;
next = link_next;
}

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
/**********************************
Doubly_Ordered_List
**********************************/
#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H
#include "Node.h"
namespace
{
enum Error_code{success, range_error, underflow, overflow, fail, not_present};
}
template <class List_entry>
class Doubly_Linked_List
{
public:
Doubly_Linked_List();
int size()const;
bool full()const;
bool empty()const;
void clear();
void traverse(void(*visit)(List_entry &));
Error_code retrieve(int position, List_entry &x)const;
Error_code replace(int position, const List_entry &x);
Error_code remove(int position, List_entry &x);
Error_code insert(int position, const List_entry &x);
~Doubly_Linked_List();
Doubly_Linked_List(const Doubly_Linked_List<List_entry> &copy);
void operator = (const Doubly_Linked_List<List_entry> &copy);
protected:
Node<List_entry> *head;
int count;
mutable int current_position;
// 在const函数中需要修改用mutable
mutable Node<List_entry> *current;
void set_position(int position)const;
private:
};
/*
Implementation of the Class
*/
template <class List_entry>
Doubly_Linked_List<List_entry>::Doubly_Linked_List()
// 构造函数
{
count = 0;
head = current = nullptr;
current_position = -1;
}
template <class List_entry>
Doubly_Linked_List<List_entry>::~Doubly_Linked_List()
// 析构函数
{
clear();
}
template <class List_entry>
Doubly_Linked_List<List_entry>::Doubly_Linked_List(const Doubly_Linked_List<List_entry> &copy)
// 拷贝构造函数
{
count = copy.count;
current_position = copy.current_position;
Node<List_entry> *new_node, *old_node = copy.head;
if(old_node==nullptr)head = current = nullptr;
else
{
new_node = head = new Node<List_entry>(old_node->entry);
while(old_node->next != nullptr)
{
old_node = old_node->next;
new_node->next = new Node<List_entry>(old_node->entry);
new_node->next->back = new_node;
new_node = new_node->next;
}
set_position(current_position);
}
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::operator = (const Doubly_Linked_List<List_entry> &copy)
// 操作符=重载
{
if(this==&copy)return;
// 判断是否进行了自己赋值给自己的操作
//Doubly_Linked_List new_copy(copy);
// 调用拷贝构造函数
clear();
Node<List_entry> *p = copy.head;
int pos = 0;
insert(pos, p->entry);
// 插入第一个元素并设置head指针
head = current;
if(p->next)p->next->back = p;
p = p->next;
pos++;
while(p)
{
insert(pos, p->entry);
if(p->next)p->next->back = p;
// p->next不为空时其back指针指向p所指的结点
p = p->next;
pos++;
}
count = copy.count;
current_position = copy.current_position;

// 不能直接用current = copy.current, 因为copy将被析构

set_position(current_position);
}
template <class List_entry>
int Doubly_Linked_List<List_entry>::size()const
{
return count;
}
template <class List_entry>
bool Doubly_Linked_List<List_entry>::full()const
{
return false;
}
template <class List_entry>
bool Doubly_Linked_List<List_entry>::empty()const
{
return (count<=0);
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::clear()
{
Node<List_entry> *p = head;
for(; p!=nullptr; p = head)
{
head = head->next;
delete p;
}
count = 0;
head = current = nullptr;
current_position = -1;
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::set_position(int position)const
{
// 向后搜索
if(current_position <= position)
for(; current_position != position; current_position++)
current = current->next;
// 向前搜索
else
for(; current_position != position; current_position--)
current = current->back;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::replace(int position, const List_entry &x)
{
if(position<0 || position>=count)return range_error;
set_position(position);
current->entry = x;
return success;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::retrieve(int position, List_entry &x)const
{
if(position<0 || position>=count)return range_error;
set_position(position);
x = current->entry;
return success;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::remove(int position, List_entry &x)
{
Node<List_entry> *previous, *following;
//if(count==0)return fail;
if(position<0 || position>=count)return range_error;
if(position==0)
{
following = head;
current = head = head->next;
// 重设current和head指针
current_position = 0;
if(head)head->back = nullptr;
// 若还有结点将其back置为nullptr
}
else
// 包括了pos在count-1的情况
{
set_position(position-1);
previous = current;
following = current->next;
previous->next = following->next;
if(following->next)following->next->back = previous;
}
x = following->entry;
delete following;
count--;
return success;
}
template <class List_entry>
Error_code Doubly_Linked_List<List_entry>::insert(int position, const List_entry &x)
{
Node<List_entry> *new_node, *following, *preceding;
if(position<0 || position>count)return range_error;
// 在pos==0处进行插入
if(position==0)
{
if(count==0)following = nullptr;
else
{
set_position(0);
following = current;
}
preceding = nullptr;
}
else
{
set_position(position-1);
preceding = current;
following = current->next;
}
new_node = new Node<List_entry>(x, preceding, following);
// 申请新结点
if(new_node==nullptr)return overflow;
// 申请失败
if(preceding!=nullptr)preceding->next = new_node;

if(!preceding)head = new_node;
// 若在pos==0的位置插入重设head指针

if(following!=nullptr)following->back = new_node;
current = new_node;
current_position = position;
count++;
return success;
}
template <class List_entry>
void Doubly_Linked_List<List_entry>::traverse(void (*visit)(List_entry &))
{
Node<List_entry> *to_visit = head;
for(; to_visit; to_visit = to_visit->next)
// 遍历列表中所有元素并执行visit函数
(*visit)(to_visit->entry);
}
#endif // DOUBLY_LINKED_LIST_H