双向链表代码

1、#ifndef H_doublyLinkedList002#define H_doublyLinkedList003#include<iostream>004#include<cassert>005usingnamespacestd;006 007template<classType>008structnodeType009010 Type info;011 nodeType<Type> *next;012 nodeType<Type> *back;013;/end of struct014 015template<classT

2、ype>016classdoublyLinkedList017018 friendostream& operator<< <Type>(ostream& osObject,constdoublyLinkedList<Type>& otherList);019public:020 /Constructor021 doublyLinkedList();022 doublyLinkedList(constdoublyLinkedList<Type>& otherList);023 024 /Use for init

3、ializing the list025 voidinitializeList();026 027 /Use for destroying the list028 voiddestroyList();029 030 /Use for judging the list is empty or not031 boolisEmpty();032 033 /Use for searching the item wether in the list,and return a bool variable034 boolsearchItem(constType& otherItem);035 036

4、 /Use for returning the first item037 Type front();038 039 /Use for returning the last item040 Type back();041 042 /Use for inserting the item to the list043 voidinsertNode(constType& insertItem);044 045 /Use for deleting the item from the list046 voiddeleteNode(constType& deleteItem);047 04

5、8 /Use for returning the length of the list049 intlength();050 051 /Use for copying one list to another list052 voidcopyList(constdoublyLinkedList<Type>& otherList);053 054 /Use for printing the list055 voidprintList();056private:057 nodeType<Type> *first;058 nodeType<Type> *la

6、st;059 intcount;060 061;/end of class062 063/*#constructor#*/064template<classType>065doublyLinkedList<Type>:doublyLinkedList()066067 first=NULL;068 last=NULL;069 count=0;070/end of constructor071 072template<classType>073doublyLinkedList<Type>:doublyLinkedList(constdoublyLin

7、kedList<Type>& otherList)074075 copyList(otherList);076/end of copy constructor077 078/*#copyList()#*/079template<classType>080voiddoublyLinkedList<Type>:copyList(constdoublyLinkedList<Type>& otherList)081082 nodeType<Type> *current;083 nodeType<Type> *new

8、Node;084 085 if(first!=NULL)086 destroyList();087 current=otherList.first;088 089 while(current->next!=NULL)090 091 newNode=newnodeType<Type>092 assert(newNode!=NULL);093 094 if(first=NULL)095 096 first=newNode;097 last=newNode;098 newNode->back=NULL;099 /end of if100 else101 102 last-&g

9、t;next=newNode;103 newNode->back=last;104 last=newNode;105 newNode->next=NULL;106 /end of else107 108 current=current->next;109 110 /end of while111 112 count=otherList.count;113 114/end of copyList115 116/*#override operator<<#*/117template<classType>118ostream& operator<

10、;<(ostream& osObject,constdoublyLinkedList<Type>& otherList)119120 nodeType<Type> *current;121 current=otherList.first;122 while(current!=NULL)123 124 osObject<<current->info<<" "125 current=current->next;126 /end of while127 returnosObject;128/end

11、of override operator129 130/*#printList()#*/131template<classType>132voiddoublyLinkedList<Type>:printList()133134 nodeType<Type> *current;135 current=first;136 while(current->next!=NULL)137 138 cout<<current->info<<" "139 current=current->next;140 /en

12、d of while141/end of printList142 143/*#initializeList()#*/144template<classType>145voiddoublyLinkedList<Type>:initializeList()146147 nodeType<Type> *newNode;148 Type num=0;149 150 cout<<"Input numbers(end with -999):"151 152 while(num!=-999)153 154 cin>>num;1

13、55 156 if(num!=-999)157 count+;158 159 newNode=newnodeType<Type>160 assert(newNode!=NULL);161 if(num!=-999)162 163 newNode->info=num;164 newNode->next=NULL;165 166 if(first=NULL)167 168 first=newNode;169 last=newNode;170 newNode->back=NULL;171 172 else173 174 last->next=newNode;175

14、 newNode->back=last;176 last=newNode;177 178 179 180 /end of while181 182/end of initializeList183 184/*#destroyList()#*/185template<classType>186voiddoublyLinkedList<Type>:destroyList()187188 nodeType<Type> *current;189 nodeType<Type> *trailCurrent;190 trailCurrent=first;

15、191 current=first->next;192 193 if(first=NULL)194 cout<<"Can not destroy an empty list!"<<endl;195 else196 197 while(current!=NULL)198 199 deletetrailCurrent;200 trailCurrent=current;201 current=current->next;202 count-;203 204 205 206/end of destroyList207 208/*#isEmpty(

16、)#*/209template<classType>210booldoublyLinkedList<Type>:isEmpty()211212 return(first=NULL);213/end of isEmpty214 215/*#length()#*/216template<classType>217intdoublyLinkedList<Type>:length()218219 returncount;220/end of length221 222/*#front()#*/223template<classType>224

17、Type doublyLinkedList<Type>:front()225226 return(first->info);227/end of front228 229/*#last()#*/230template<classType>231Type doublyLinkedList<Type>:back()232233 return(last->info);234/end of last235 236/*#searchItem()#*/237template<classType>238booldoublyLinkedList<

18、;Type>:searchItem(constType& otherItem)239240 nodeType<Type> *current;241 boolfound;242 243 found=false;244 current=first;245 246 if(first=NULL)247 cout<<"This is an empty list!"<<endl;248 if(first->info=otherItem|last->info=otherItem)249 found=true;250 else2

19、51 252 while(current->next!=NULL)253 254 if(current->info=otherItem)255 256 found=true;257 break;258 259 else260 current=current->next;261 262 /end of while263 /end of else264 returnfound;265/end of searchItem266 267/*#insertNode()#*/268template<classType>269voiddoublyLinkedList<Ty

20、pe>:insertNode(constType& insertItem)270271 nodeType<Type> *newNode;272 nodeType<Type> *current;273 nodeType<Type> *trailCurrent;274 275 newNode=newnodeType<Type>276 277 assert(newNode!=NULL);278 newNode->info=insertItem;279 newNode->back=NULL;280 newNode->nex

21、t=NULL;281 282 if(first=NULL)283 284 first=newNode;285 last=newNode;286 287 else288 289 trailCurrent=first;290 current=first->next;291 292 if(first->info>insertItem)293 294 first=newNode;295 newNode->next=trailCurrent;296 297 elseif(last->info<insertItem)298 299 cout<<"r

22、un here!"<<endl;300 last->next=newNode;301 newNode->back=last;302 last=newNode;303 cout<<last->info<<endl;304 305 else306 307 while(1)308 309 if(insertItem<current->info)310 311 trailCurrent->next=newNode;312 newNode->back=trailCurrent;313 newNode->next

23、=current;314 current->back=newNode;315 break;316 317 else318 319 trailCurrent=current;320 current=current->next;321 322 /end of while323 /end of else324 /end of else325 326 count+;327 328/end of insertNode329 330/*#deleteNode()#*/331template<classType>332voiddoublyLinkedList<Type>:

24、deleteNode(constType& deleteItem)333334 nodeType<Type> *current;335 nodeType<Type> *trailCurrent;336 boolfound=false;337 338 if(first=NULL)339 cout<<"This is an empty list!Can not delete any item."<<endl;340 341 else342 343 trailCurrent=first;344 current=first-&

25、gt;next;345 346 if(deleteItem=first->info)347 348 first=first->next;349 first->next->back=NULL;350 found=true;351 deletetrailCurrent;352 353 if(deleteItem=last->info)354 355 last->back->next=NULL;356 found=true;357 deletelast;358 359 360 while(current->info!=deleteItem|curren

26、t!=NULL)361 362 if(current->info=deleteItem)363 364 trailCurrent->next=current->next;365 current->next->back=trailCurrent;366 deletecurrent;367 break;368 369 else370 371 trailCurrent=current;372 current=current->next;373 374 /end of while375 /end of else376 377 if(!found)378 cout&l

27、t;<"There is no this item!"<<endl;379 380 count-;381 382/end of doublyLinkedList383#endif384-385#include"doublyLinkedList.h"386 387intmain()388389 inta;390 inttempItem;391 doublyLinkedList<int> myDoublyList;392 393 cout<<"My list is empty or not: "394 if(myDoublyList.isEmpty()395 cout<<"The list is empty"<<endl;396 else397 cout<<"The list is not empty"<<endl;398 399 myDoublyList.deleteNode(1);400 401 myDou