数据布局专题四——双向轮回链表
添加时间: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、激劝本身能对峙把更多半据布局方面的常识写出来,让本身把握更深切,也趁便假充下小牛;
所有随风而逝的都属于昨天的,所有历经风雨留下来的才是面向未来的。—— 玛格丽特·米切尔 《飘》
文章目次:
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、激劝本身能对峙把更多半据布局方面的常识写出来,让本身把握更深切,也趁便假充下小牛;