My road to c++
C++博客
首页
新随笔
联系
聚合
管理
随笔-13 评论-0 文章-2 trackbacks-0
双向链表的实现(Alpha1.0 )
1
/**/
/*
*
2
Double List base on dynamic array
3
Version: 1.0
4
Member function as follow:
5
size()
6
push_back(T) // inset an elm
7
erase(T) // delete an elm
8
empty() // if it is an empty list
9
print()
10
find(T&) // find an elm
11
12
Use C++ template
13
*
*/
14
#include
<
iostream
>
15
using
namespace
std;
16
template
<
typename T
>
17
struct
Node
18
{
19
T data;
20
Node
<
T
>*
prev;
21
Node
<
T
>*
next;
22
Node()
{ prev
=
NULL; next
=
NULL; }
23
}
;
24
25
template
<
typename T
>
26
class
DList
27
{
28
private
:
29
Node
<
T
>*
head;
30
int
size;
31
public
:
32
DList();
33
~
DList()
{ delete head; size
=
0
; }
34
int
Size()
{
return
size; }
35
bool
empty()
{
return
size
==
0
; }
36
void
push_back(
const
T
&
);
37
T front()
const
{
return
head
->
data;}
38
void
find(
const
T
&
);
39
void
erase(
const
T
&
);
40
void
print()
const
;
41
}
;
42
43
template
<
typename T
>
DList
<
T
>
::DList()
44
{
45
head
=
new
Node
<
T
>
;
46
head
->
prev
=
NULL;
47
head
->
next
=
NULL;
48
size
=
0
;
49
}
50
51
template
<
typename T
>
void
DList
<
T
>
::push_back(
const
T
&
one)
52
{
53
Node
<
T
>*
p
=
head;
54
if
( size
==
0
) p
->
data
=
one;
55
else
56
{
57
while
( p
->
next
!=
NULL )
58
p
=
p
->
next;
59
Node
<
T
>*
new_node
=
new
Node
<
T
>
;
60
new_node
->
data
=
one;
61
new_node
->
next
=
NULL;
62
new_node
->
prev
=
p;
63
p
->
next
=
new_node;
64
}
65
size
++
;
66
}
67
68
template
<
typename T
>
void
DList
<
T
>
::find(
const
T
&
one)
69
{
70
Node
<
T
>*
p
=
head;
71
while
( p
->
next
!=
NULL )
72
{
73
if
( p
->
data
==
one )
{cout
<<
"
It's in the position of
"
<<
size
-
1
<<
endl;
break
;}
74
else
p
=
p
->
next;
75
}
76
if
( p
->
data
==
one
&&
p
->
next
==
NULL ) cout
<<
"
It's the last element
"
<<
endl;
77
else
cout
<<
"
No such an element!
"
<<
endl;
78
}
79
80
template
<
typename T
>
void
DList
<
T
>
::erase(
const
T
&
one)
81
{
82
Node
<
T
>*
p
=
head;
83
while
( p
->
next
!=
NULL )
84
{
85
if
(p
->
data
==
one)
86
{
87
p
->
next
->
prev
=
p
->
prev;
88
p
=
p
->
prev;
89
p
->
next
=
p
->
next
->
next;
90
size
--
;
91
break
;
92
}
93
else
p
=
p
->
next;
94
}
95
96
if
( p
->
data
==
one
&&
p
->
next
==
NULL )
97
{
98
p
->
prev
->
next
=
NULL;
99
size
--
;
100
}
101
else
102
cout
<<
"
No such an element!
"
<<
endl;
103
}
104
105
template
<
typename T
>
void
DList
<
T
>
::print()
const
106
{
107
Node
<
T
>*
p
=
head;
108
while
( p
->
next
!=
NULL )
109
{
110
cout
<<
p
->
data
<<
"
"
;
111
p
=
p
->
next;
112
}
113
cout
<<
p
->
data
<<
endl;
114
}
115
116
//
Test Function
117
#include
<
iostream
>
118
int
main()
119
{
120
DList
<
int
>
list;
121
int
n;
122
cout
<<
"
Please input the number which you want to create!
"
<<
endl;
123
cin
>>
n;
124
cout
<<
"
Input the number you want to add in the array.\n
"
;
125
cout
<<
"
----------------------------------------------------------------\n\n
"
;
126
while
(n
--
)
//
cin.hasnext()
127
{
128
int
a;
129
cin
>>
a;
130
list.push_back(a);
131
}
132
cout
<<
"
You input the array as follow
"
<<
endl;
133
list.print();
134
cout
<<
"
Do you want to delete an element ?
"
<<
endl;
135
cout
<<
"
Yes/No?
"
<<
endl;
136
string
s;
137
cin
>>
s;
138
if
( s
==
"
yes
"
||
s
==
"
YES
"
)
139
{
140
cout
<<
"
which number?
"
<<
endl;
141
int
tem;
142
cin
>>
tem;
143
list.erase(tem);
144
cout
<<
"
Now the array as follow
"
<<
endl;
145
list.print();
146
}
147
cout
<<
"
Do you want to find an element?
"
<<
endl;
148
cout
<<
"
Yes/No?
"
<<
endl;
149
string
s2;
150
cin
>>
s2;
151
if
( s2
==
"
yes
"
||
s2
==
"
YES
"
)
152
{
153
cout
<<
"
which number?
"
<<
endl;
154
int
tem;
155
cin
>>
tem;
156
list.find(tem);
157
}
158
159
cout
<<
"
Now the size of the array is
"
<<
list.Size()
<<
endl;
160
cout
<<
"
The first number is :
"
<<
list.front()
<<
endl;
161
cout
<<
endl;
162
cout
<<
"
----------------------------------------------------------------\n\n
"
;
163
system(
"
pause
"
);
164
return
0
;
165
166
}
167
168
posted on 2009-02-22 21:58
亦夏
阅读(178)
评论(0)
编辑
收藏
引用
所属分类:
DataStruct
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
栈的实现(顺序结构)Alpha 2.0
二查查找树的实现(链式) Alpha1.0
队列的实现(链式结构) Alpha 1.0
队列的实现(数组结构) Alpha 1.0
栈的实现(链式结构)Alpha 1.0
栈的实现(顺序结构)Alpha 1.0
循环链表的实现(Alpha)
双向链表的实现(Alpha1.0 )
单向链表的实现(Alpha 1.0)
线性表的顺序表示和实现(静态数组方式)(Alpha1.0)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2024年9月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
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
1
2
3
4
5
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
(13)
ACM (2)
DataStruct(10)
TopCoder(1)
随笔档案
(13)
2009年5月 (1)
2009年4月 (3)
2009年3月 (5)
2009年2月 (4)
文章分类
(2)
ACM(1)
Alogrithm
C part of c++
C++0X
Datestruct
Game of c++
General(1)
Object-orient of c++
Others
Puzzle
STL
Template c++
Visual c++
文章档案
(2)
2009年2月 (1)
2009年1月 (1)
搜索
最新随笔
1. Search and DP
2. 栈的实现(顺序结构)Alpha 2.0
3. HowEasy
4. HDOJ_1010.Tempter of the Bone(DFS)
5. 二查查找树的实现(链式) Alpha1.0
6. 队列的实现(链式结构) Alpha 1.0
7. 队列的实现(数组结构) Alpha 1.0
8. 栈的实现(链式结构)Alpha 1.0
9. 栈的实现(顺序结构)Alpha 1.0
10. 循环链表的实现(Alpha)
最新评论
阅读排行榜
1. HDOJ_1010.Tempter of the Bone(DFS)(903)
2. 队列的实现(链式结构) Alpha 1.0(446)
3. HowEasy(428)
4. Search and DP(380)
5. 线性表的顺序表示和实现(静态数组方式)(Alpha1.0)(329)
评论排行榜
1. 线性表的顺序表示和实现(静态数组方式)(Alpha1.0)(0)
2. 单向链表的实现(Alpha 1.0)(0)
3. 双向链表的实现(Alpha1.0 )(0)
4. 循环链表的实现(Alpha)(0)
5. 栈的实现(顺序结构)Alpha 1.0(0)