第3节 线性表使用链式结构（双向循环）实现
时间：2010-08-29 来源：chinazhangjie
1 /* 主题: 线性表使用链式结构（双向循环）实现
2 * 作者: chinazhangjie(邮箱:[email protected])
3 * 开发语言: C++
4 * 开发环境: Microsoft Visual Studio 2008
5 * 日期: 2010.08.29
6 */
7
8 template <class T>
9 class linked_dclist {
10 class node;
11 public:
12 typedef T value_type;
13 typedef unsigned int ldc_size;
14 typedef node* node_pointer;
15 public:
16 // 构造函数
17 linked_dclist() {
18 __init_dclist();
19 }
20 // 拷贝构造函数
21 linked_dclist(const linked_dclist<T>& rhs) {
22 __init_dclist();
23 __copy_dclist(rhs);
24 }
25
26 // 析构函数
27 ~linked_dclist() {
28 // 销毁链表
29 __clear_dclist();
30 // 删除头结点
31 delete head;
32 head = NULL;
33 length = 0;
34 }
35
36 // 头插入
37 void push_front(value_type elem) {
38 node_pointer ins_node = new node(elem);
39 if (this->size() == 0) {
40 ins_node->next = head;
41 ins_node->prior = head;
42 head->next = ins_node;
43 head->prior = ins_node;
44 }else {
45 ins_node->next = head->next;
46 ins_node->prior = head;
47 head->next->prior = ins_node;
48 head->next = ins_node;
49 }
50 ++ length;
51 }
52 // 尾插入
53 void push_back(value_type elem) {
54 node_pointer ins_node = new node(elem);
55 if (ins_node == NULL) {
56 throw std::bad_alloc("push_back bad_alloc");
57 }
58 if (this->size() == 0) {
59 ins_node->next = head;
60 ins_node->prior = head;
61 head->next = ins_node;
62 head->prior = ins_node;
63 }
64 else {
65 ins_node->next = head;
66 ins_node->prior = head->prior;
67 head->prior->next = ins_node;
68 head->prior = ins_node;
69 }
70 ++ length;
71 }
72
73 // 在location的位置插入元素elem
74 void insert(ldc_size location,value_type elem) {
75 if (location > length) {
76 throw std::out_of_range("insert out_of_range");
77 }
78 else if (location == length) {
79 this->push_back(elem);
80 }
81 else {
82 if (location == 0)
83 this->push_front(elem);
84 else {
85 node_pointer ins_node = new node(elem);
86 if (ins_node == NULL)
87 throw std::bad_alloc("ins_node bad_alloc");
88 node_pointer tmp = head;
89 ldc_size i = 0;
90 while (i < location) {
91 tmp = tmp->next;
92 ++ i;
93 }
94 ins_node->next = tmp->next;
95 ins_node->prior = tmp;
96 tmp->next->prior = ins_node;
97 tmp->next = ins_node;
98 ++ length;
99 }
100 }
101 }
102
103 // 移除第location个元素，并返回其值
104 value_type remove(ldc_size location) {
105 if (location >= size())
106 throw std::out_of_range("remove out_of_range");
107 node_pointer tmp = head;
108 ldc_size i = 0;
109 while (i < location) {
110 tmp = tmp ->next;
111 ++ i;
112 }
113 node_pointer del_node = tmp->next;
114 tmp->next = del_node->next;
115 del_node->next->prior = tmp;
116 value_type re_value = del_node->data;
117 delete del_node;
118 -- length;
119 return re_value;
120 }
121
122 // 清空链表
123 void clear() {
124 __clear_dclist();
125 }
126
127 // 返回长度
128 ldc_size size() const { return length; }
129
130 // 排序——递增
131 void sort_increase() {
132 for (ldc_size i = 0; i < size() - 1; ++ i) {
133 ldc_size ii = i;
134 for (ldc_size j = i; j < size(); ++ j) {
135 if ((*this)[ii] > (*this)[j])
136 ii = j;
137 }
138 if (ii != i) {
139 value_type tmp = (*this)[ii];
140 (*this)[ii] = (*this)[i];
141 (*this)[i] = tmp;
142 }
143 }
144 }
145 // 排序——递减
146 void sort_decrease() {
147 for (ldc_size i = 0; i < size() - 1; ++ i) {
148 ldc_size ii = i;
149 for (ldc_size j = i; j < size(); ++ j) {
150 if ((*this)[ii] < (*this)[j])
151 ii = j;
152 }
153 if (ii != i) {
154 value_type tmp = (*this)[ii];
155 (*this)[ii] = (*this)[i];
156 (*this)[i] = tmp;
157 }
158 }
159 }
160 // 排序——函数指针
161 void sort(bool (*compare)(value_type,value_type)) {
162 for (ldc_size i = 0; i < size() - 1; ++ i) {
163 ldc_size ii = i;
164 for (ldc_size j = i; j < size(); ++ j) {
165 if ((*compare)((*this)[ii],(*this)[j]))
166 ii = j;
167 }
168 if (ii != i) {
169 value_type tmp = (*this)[ii];
170 (*this)[ii] = (*this)[i];
171 (*this)[i] = tmp;
172 }
173 }
174 }
175 // 排序——仿函数
176 template <class FunObj>
177 void sort(FunObj funojb) {
178 for (ldc_size i = 0; i < size() - 1; ++ i) {
179 ldc_size ii = i;
180 for (ldc_size j = i; j < size(); ++ j) {
181 if (Funobj((*this)[ii] ,(*this)[j]))
182 ii = j;
183 }
184 if (ii != i) {
185 value_type tmp = (*this)[ii];
186 (*this)[ii] = (*this)[i];
187 (*this)[i] = tmp;
188 }
189 }
190 }
191
192 // 合并链表
193 void merge(const linked_dclist<T>& rhs) {
194 this->sort_increase();
195 if (rhs.size() == 0)
196 return;
197 linked_dclist<T> other(rhs);
198 other.sort_increase();
199 if (this->size() == 0) {
200 (*this) = other;
201 return ;
202 }
203 ldc_size len1 = 0;
204 ldc_size len2 = 0;
205 linked_dclist<T> new_dclist;
206 while (len1 < this->size() && len2 < other.size()) {
207 if ((*this)[len1] <= other[len2]) {
208 new_dclist.push_back((*this)[len1]);
209 ++ len1;
210 }
211 else {
212 new_dclist.push_back(other[len2]);
213 ++ len2;
214 }
215 }
216 while (len1 < this->size()) {
217 new_dclist.push_back((*this)[len1]);
218 ++ len1;
219 }
220 while (len2 < this->size()) {
221 new_dclist.push_back((*this)[len2]);
222 ++ len2;
223 }
224 (*this) = new_dclist;
225 return ;
226 }
227
228 // 重载 "="
229 linked_dclist<T>& operator = (const linked_dclist<T>& rhs) {
230 if (this == &rhs)
231 return *this;
232 __clear_dclist();
233 __copy_dclist(rhs);
234 }
235 // 重载 "[]"
236 value_type& operator[] (ldc_size location) const {
237 if (location >= length) {
238 throw std::out_of_range("[] out_of_range");
239 }
240 ldc_size i = 0;
241 node_pointer tmp = head->next;
242 while (i < location) {
243 tmp = tmp->next;
244 ++ i;
245 }
246 return tmp->data;
247 }
248 // 重载 "<<"
249 friend ostream& operator << (ostream& out,linked_dclist<T>& rhs) {
250 node_pointer tmp = rhs.head->next;
251 while (tmp != rhs.head) {
252 out << tmp->data << ' ';
253 tmp = tmp->next;
254 }
255 cout << endl;
256 return out;
257 }
258
259 private:
260 // 构造头结点
261 void __init_dclist() {
262 head = new node(value_type());
263 if (head == NULL) {
264 throw std::bad_alloc("__init_dclist bad_alloc");
265 }
266 head->prior = head;
267 head->next = head;
268 length = 0;
269 }
270
271 // 请空链表
272 void __clear_dclist() {
273 if (this->size() == 0) {
274 return ;
275 }
276 node_pointer tmp = head->next;
277 while (tmp != head) {
278 node_pointer del_node = tmp;
279 tmp = tmp->next;
280 delete del_node;
281 }
282 head->next = head;
283 head->prior = head;
284 length = 0;
285 }
286
287 // 复制双向循环链表
288 void __copy_dclist(const linked_dclist<T> & rhs) {
289 if (rhs.size() == 0)
290 return ;
291 ldc_size i = 0;
292 while (i < rhs.size()) {
293 this->push_back(rhs[i]);
294 ++ i;
295 }
296 }
297
298 private:
299 node_pointer head;
300 ldc_size length;
301
302 private:
303 class node {
304 public:
305 node(value_type elem)
306 :data(elem),prior(NULL),next(NULL)
307 { }
308 public:
309 value_type data;
310 node* prior; // 前驱
311 node* next; // 后继
312 };
313 };
相关阅读 更多 +
