-
数据布局专题四——双向轮回链表
添加时间:2013-5-14 点击量:所有随风而逝的都属于昨天的，所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》文章目次：
01. 博文简介：
02. 概念：
03. 示例图：
04. 优毛病：
05. 代码解析：
06. 运行景象：
07. 题记：
一：概念
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的随便率性一个结点开端，都可以很便利地接见它的前驱结点和后继结点，一般我们都机关双向轮回表，STL中实现了双链表轮回表。
二：示例图
三：链表的优毛病
链表大一个毛病，就是查找一个元素，必须全部链表遍历，也可以看出这种数据布局便于插入或者删除一个接点。
四：代码解析
1、获取节点信息
1 /
2 按照地位获取相对应的节点信息
3 size_t 是一个无符号的类型，断定调用该函数时入参必然是正数，
4 如许的请求也提示我们在写函数时，应当避免把如许函数露出给客户
5 不知道为什么linux很多api函数都有size_t类型的入参（经由过程调试，传入负数会导致严重的bug），
6 有知道的伴侣，请辅佐分享下
7 /
8 DLNode<T> GetElemP（size_t i） const{
9 int j = 0;
10 DLNode<T> p = head;
11
12 do{
13 p = p->next;
14 j++;
15 }while（p != head && j < i）;
16
17 return p;
18 }
19
20 /
21 按照元素获取对应的节点信息
22 /
23 DLNode<T> GetElemE（const T &e） const{
24 DLNode<T> p = head->next;
25
26 while（p != head && e != p->data）{
27 p = p->next;
28 }
29
30 return p;
31 }2、插入节点
插入过程如下图：
代码解析如下：
1 /
2 在指定的地位插入节点
3 /
4 void Insert（size_t i，const T &e）{
5 //获取指定的地位节点
6 DLNode<T> p = GetElemP（i）;
7 //插入新节点
8 Insert（p，e）;
9 }
10 /
11 在指定的指针节点插入新的节点
12 /
13 void Insert（DLNode<T> p，const T &e）{
14 //创建一个新的节点
15 DLNode<T> q = new DLNode<T>（e）;
16 //设置新节点的向后的指针域（指向图中2节点）
17 q->next = p->next;
18 //设置新节点的向前的指针域（指向图中1节点）
19 q->prev = p;
20
21 //设置插入节点的后继节点的向前指针域（图中3节点的上一个节点指针域指向新节点2）
22 p->next->prev = q;
23 //设置插入节点的向后的指针域（指向新节点2）
24 p->next = q;
25 }
26 /
27 从头结点的地位插入新的节点
28 /
29 void AddHead（const T &e）{
30 Insert（head，e）;
31 }
32 /
33 从第一个节点的地位插入新的节点
34 /
35 void Insert（const T &e）{
36 Insert（1，e）;
37 }3、删除节点
删除节点如下图，可以从图中看到，删除节点仅仅改变前驱和后继节点相干的指针域，这个就是为什么数据删除高手还可以找回来原因；
代码解析如下：
1 /
2 按照元素内容删除对应的节点
3 /
4 void Delete（const T &e）{
5 //按照元素内容获取对应的节点
6 DLNode<T> p = GetElemE（e）;
7 //更多关于auto_ptr常识，请浏览memory里auto_ptr源码
8 std::auto_ptr<DLNode<T> > new_ptr（p）;
9 //设置删除节点后继节点向前的指针域为删除节点向前指针域
10 p->next->prev = p->prev;
11 //设置删除节点前驱节点向后的指针域为删除节点向后指针域
12 p->prev->next = p->next;
13 }4、遍历节点，在stl源码中有很是强大遍历神器（iterator），把泛型的常识应用到极致，感激的伴侣可以读读源码
1 /
2 遍历双向链表
3 /
4 void Traverse（）{
5 //指向第一个节点信息
6 DLNode<T> p = head->next;
7
8 //若是节点向后指针域便是头结点，默示链表已经遍历完成
9 while（p != head）{
10 std::cout<<p is value = <<p->data;
11 std::cout<<<<std::endl;
12 p = p->next;
13 }
14 }5、清空链表
1 /
2 清空全部链表节点
3 /
4 void Clear（）{
5 //获取第一个节点信息
6 DLNode<T> p = head->next;
7
8 //若是节点向后指针域便是头结点，默示链表已经被清空
9 while（p != head && p != 0）{
10 //更多关于auto_ptr常识，请浏览memory里auto_ptr源码
11 std::auto_ptr<DLNode<T> > new_ptr（p）;
12 std::cout<<p;
13 std::cout<<std::endl;
14 //履行后继节点
15 p = p->next;
16 }
17 //恢复出厂原状，向前和向后的指针域都指向本身，构成双向链表
18 head->next = head->prev = head;
19 }6、是否为空和策画链表长度
/
断定链表是否为空
/
bool Empty（）{
return head->next = head;
}
/
策画链表的长度
/
int Length（）{
int i = 0;
DLNode<T> p = head->next;
//若是节点向后指针域便是头结点，链表遍历完成，
while（p != head）{
//履行后继节点
p = p->next;
//累计链表节点长度
i++;
}
return i;
}7、测试代码
1 void test（）{
2 std::cout<<----------- begin------------<<std::endl;
3 for（int i = 1; i <= 5; ++i）{
4 Insert（i）;
5 }
6 AddHead（6）;
7 AddHead（7）;
8 Traverse（）;
9 std::cout<<----------- end------------<<std::endl;
10
11 std::cout<<frist list length=<<Length（）<<std::endl;
12
13 std::cout<<----------- begin----------<<std::endl;
14 Delete（2）;
15 std::cout<<----------- end----------<<std::endl;
16
17 std::cout<<second list length=<<Length（）<<std::endl;
18
19 std::cout<<-----------traversal of the elemetns begin----------<<std::endl;
20
21 Traverse（）;
22 Clear（）;
23 Delete（1）;
24 Clear（）;
25 std::cout<<third list length=<<Length（）<<std::endl;
26 }8、运行成果
9、完全代码
1 /
2 DLinkList.h
3
4 Created on: 2012-10-13
5 Author: hs
6 /
7
8 ＃ifndef DLINKLIST_H_
9 ＃define DLINKLIST_H_
10 ＃include core/node/DLNode.h
11
12 template<class T>
13 class DLinkList {
14 private:
15 DLNode<T> head;//头结点
16 /
17 按照地位获取相对应的节点信息
18 size_t 是一个无符号的类型，断定调用该函数时入参必然是正数，
19 如许的请求也提示我们在写函数时，应当避免把如许函数露出给客户
20 不知道为什么linux很多api函数都有size_t类型的入参（经由过程调试，传入负数会导致严重的bug），
21 有知道的伴侣，请辅佐分享下
22 /
23 DLNode<T> GetElemP（size_t i） const{
24 int j = 0;
25 DLNode<T> p = head;
26
27 do{
28 p = p->next;
29 j++;
30 }while（p != head && j < i）;
31
32 return p;
33 }
34
35 /
36 按照元素获取对应的节点信息
37 /
38 DLNode<T> GetElemE（const T &e） const{
39 DLNode<T> p = head->next;
40
41 while（p != head && e != p->data）{
42 p = p->next;
43 }
44
45 return p;
46 }
47 /
48 在指定的地位插入节点
49 /
50 void Insert（size_t i，const T &e）{
51 //获取指定的地位节点
52 DLNode<T> p = GetElemP（i）;
53 //插入新节点
54 Insert（p，e）;
55 }
56 /
57 在指定的指针节点插入新的节点
58 /
59 void Insert（DLNode<T> p，const T &e）{
60 //创建一个新的节点
61 DLNode<T> q = new DLNode<T>（e）;
62 //设置新节点的向后的指针域（指向图中2节点）
63 q->next = p->next;
64 //设置新节点的向前的指针域（指向图中1节点）
65 q->prev = p;
66
67 //设置插入节点的后继节点的向前指针域（图中3节点的上一个节点指针域指向新节点2）
68 p->next->prev = q;
69 //设置插入节点的向后的指针域（指向新节点2）
70 p->next = q;
71 }
72
73 public:
74 /
75 机关函数，初始化头结点（向前和向后都指向本身，构成双向链表）
76 /
77 DLinkList（）:head（new DLNode<T>（0））{
78 head->next = head;
79 head->prev = head;
80 }
81
82 /
83 析构函数，开释所有新创建的节点
84 /
85 ~DLinkList（）{
86 Clear（）;
87 }
88 /
89 清空全部链表节点
90 /
91 void Clear（）{
92 //获取第一个节点信息
93 DLNode<T> p = head->next;
94
95 //若是节点向后指针域便是头结点，默示链表已经被清空
96 while（p != head && p != 0）{
97 //更多关于auto_ptr常识，请浏览memory里auto_ptr源码
98 std::auto_ptr<DLNode<T> > new_ptr（p）;
99 std::cout<<p;
100 std::cout<<std::endl;
101 //履行后继节点
102 p = p->next;
103 }
104 //恢复出厂原状，向前和向后的指针域都指向本身，构成双向链表
105 head->next = head->prev = head;
106 }
107 /
108 断定链表是否为空
109 /
110 bool Empty（）{
111 return head->next = head;
112 }
113
114 /
115 策画链表的长度
116 /
117 int Length（）{
118
119 int i = 0;
120 DLNode<T> p = head->next;
121
122 //若是节点向后指针域便是头结点，链表遍历完成，
123 while（p != head）{
124 //履行后继节点
125 p = p->next;
126 //累计链表节点长度
127 i++;
128 }
129
130 return i;
131 }
132 /
133 从头结点插入新的元素
134 /
135 void AddHead（const T &e）{
136 Insert（head，e）;
137 }
138 /
139 从第一个地位插入新的节点
140 /
141 void Insert（const T &e）{
142 Insert（1，e）;
143 }
144
145 /
146 按照元素内容删除对应的节点
147 /
148 void Delete（const T &e）{
149 //按照元素内容获取对应的节点
150 DLNode<T> p = GetElemE（e）;
151 //更多关于auto_ptr常识，请浏览memory里auto_ptr源码
152 std::auto_ptr<DLNode<T> > new_ptr（p）;
153 //设置删除节点后继节点向前的指针域为删除节点向前指针域
154 p->next->prev = p->prev;
155 //设置删除节点前驱节点向后的指针域为删除节点向后指针域
156 p->prev->next = p->next;
157 }
158
159 /
160 遍历双向链表
161 /
162 void Traverse（）{
163 //指向第一个节点信息
164 DLNode<T> p = head->next;
165
166 //若是节点向后指针域便是头结点，默示链表已经遍历完成
167 while（p != head）{
168 std::cout<<p is value = <<p->data;
169 std::cout<<<<std::endl;
170 p = p->next;
171 }
172 }
173
174 void test（）{
175 std::cout<<----------- begin------------<<std::endl;
176 for（int i = 1; i <= 5; ++i）{
177 Insert（i）;
178 }
179 AddHead（6）;
180 AddHead（7）;
181 Traverse（）;
182 std::cout<<----------- end------------<<std::endl;
183
184 std::cout<<frist list length=<<Length（）<<std::endl;
185
186 std::cout<<----------- begin----------<<std::endl;
187 Delete（7）;
188 std::cout<<----------- end----------<<std::endl;
189
190 std::cout<<second list length=<<Length（）<<std::endl;
191
192 std::cout<<-----------traversal of the elemetns begin----------<<std::endl;
193
194 Traverse（）;
195 Clear（）;
196 Delete（1）;
197 Clear（）;
198 std::cout<<third list length=<<Length（）<<std::endl;
199 }
200 };
201
202 ＃endif / DLINKLIST_H_ /
View Code五：景象
1、运行景象：Ubuntu 10.04 LTS+VMware8.0.4+gcc4.4.3；
2、开辟对象：Eclipse+make
六：题记
1、上方的代码不免有bug，若是你发明代码写的有题目，请你辅佐指出，让我们一路进步，让代码变的更摩登和更结实；
2、我本身妙手动写上方代码，离不开郝斌、高一凡、侯捷、严蔚敏等教员的册本和视频领导，在这里感激他们；
3、激劝本身能对峙把更多半据布局方面的常识写出来，让本身把握更深切，也趁便假充下小牛；
