本文是通过C++ 的知识实现数据结构中的双向链表，这里不多说 了，代码注释很清楚，
实现代码：
|
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
239
240
241
242
|
//double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virtual void Insert(const Type &)=0; virtual void Remove(const Type &)=0; }; template<typename T> class DLinkListNode:public DBListADT<typename T>//此处必须为实现的类型，当然以派生类的模板类型也可以，但是不能是Type { public: void Append(const T &);//这边也需要是当前类的类型,不能为Type void Insert(const T &); void Remove(const T &); };*/template<typename T>class DLinkList; template<typename Type> class DNode { friend class DLinkList<Type>;//指定前需声明 public: DNode(){next=NULL;prior=NULL;} ~DNode(){} private: DNode *next; DNode *prior; Type data; }; template<typename T> class DLinkList { public: DLinkList() { // head=new DNode<T>[sizeof(DNode<T>)]; head=new DNode<T>; } ~DLinkList() { if(head->next==NULL) delete head; else { DNode<T> *p=head->next; DNode<T>*s=NULL; while(p) { s=p->next ; delete p; p=s; } } } void DeleteElement(size_t position) { DNode<T> *p=head->next; size_t index=1; for(;index<position;index++) p=p->next ; if(p==NULL) return ; p->prior ->next =p->next ; p->next ->prior =p->prior ; delete p; } void InsertElement(T data,size_t position); void CreateDLinkList(T a[],int n); void PrintDLinkList(); private: DNode<T> *head; }; template<typename T> void DLinkList<T>:: InsertElement (T data,size_t position) { DNode<T> *p=head->next; size_t index=1; for(;index<position;index++) p=p->next; if(p==NULL) return; //DNode<T> *s=new DNode<T>[sizeof(DNode<T>)]; DNode<T> *s=new DNode<T>; s->data=data; s->next=p; s->prior=p->prior; p->prior->next=s; p->prior=s; } template<typename T> void DLinkList<T>::CreateDLinkList(T a[],int n) { DNode<T>*p=head; DNode<T>*s=NULL; int i=0; for(;i<n;i++) { // s=new DNode<T>[sizeof(DNode)]; s=new DNode<T>; s->data=a[i]; p->next=s; s->prior=p; p=s; } s->next=NULL; } template<typename T>void DLinkList<T>::PrintDLinkList () { DNode<T> *p=head->next; while(p) { cout<<p->data<<endl; p=p->next; } } int main() { int a[10]={1,2,3,4,5,6,7,8,9,10}; DLinkList<int>Dlist; Dlist.CreateDLinkList(a,10); Dlist.DeleteElement (3); Dlist.InsertElement(3,3); Dlist.PrintDLinkList(); return 0; } //double LinkList implement with C++ Class //************************************************************ /*#include<iostream> using namespace std; class Node { friend class List; public: //Node(int a):next(NULL),prior(NULL),data(a){} Node(){} private: Node *next; Node *prior; int data; }; class List { public: List() { cout<<"create head DBLinkList"<<endl; head=new Node[sizeof(Node)]; }; ~List() { if(head->next==NULL) { delete head; } else { Node *p=head->next; Node *s; delete head; while(p) { s=p->next ; delete p; p=s; } } cout<<"destructor called to clear DBLinkList"<<endl; } void CreateDoubleLink(int a[],int n); void DeleteElemData(int position); void InsertElement(int data,int position); void PrintDList(); private: Node *head; }; void List::CreateDoubleLink (int a[],int n) { head->next =NULL; Node *s,*p=head; int i=0; for(;i<n;i++) { s=new Node[sizeof(Node)]; s->data =a[i]; p->next =s; s->prior =p; p=s; } s->next =NULL; } void List::PrintDList() { Node *p=head->next ; while(p) { cout<<p->data <<endl; p=p->next ; } } void List::DeleteElemData(int position) {//可以通过重载delete运算符来达到这个效果，则直接用delete就OK了 Node *p=head->next ; //while(p!=NULL&&p->data !=data) // p=p->next ; int i=1; for(;i<position;i++) p=p->next ; if(p==NULL) return ; p->prior ->next =p->next ; p->next ->prior =p->prior ; delete p; } void List::InsertElement (int data,int position) {//可以重载new运算符来达到这个效果，则直接用new就OK了 Node *p=head->next ; int i=1; for(;i<position;i++) p=p->next ; Node *s=new Node[sizeof(Node)]; s->data =data; s->prior =p->prior ; s->next =p; p->prior ->next =s; p->prior =s; } int main() { List Dlist; int a[10]={1,2,3,4,5,6,7,8,9,10}; Dlist.CreateDoubleLink (a,10); Dlist.DeleteElemData(3); Dlist.InsertElement (3,3); Dlist.PrintDList (); return 0; }*/ //************************************************************************************* |
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/typename/article/details/6111728
