浙江工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)第三章第1頁，共35頁。2MainIndexContentsLinkedListNodesEachNodeislikeapieceofachainToinsertanewlink,breakthechainatthedesiredlocationandsimplyreconnectatbothendsofthenewpiece.2第2頁，共35頁。3MainIndexContentsLinkedListNodesRemovalislikeInsertioninreverse.3第3頁，共35頁。4MainIndexContentsNodeCompositionAnindividualNodeiscomposedoftwoparts,aDatafieldcontainingthedatastoredbythenode,andaPointerfieldthatmarkstheaddressofthenextNodeinthelist.4第4頁，共35頁。5MainIndexContentsNode結(jié)點(diǎn)設(shè)計(jì)Template<typenameT>classnode{public:TnodeValue;//dataheldbythenodenode<T>*next;//nextnodeinthelistnode():next(NULL){}node(constT&item,node<T>*nextNode=NULL):nodeValue(item),next(nextNode){}};5第5頁，共35頁。AbstractModelofaListObjectdatanextdatanextdatanextdatanullfirst20xbfffaa28first0xbfffaa200xbfffaa280xbfffaa600xbfffaa8040xbfffaa6060xbfffaa808Nullfirst是指向node類型的指針：node<int>*first;first=newnode<int>(2,NULL);

0xbfffaa206第6頁，共35頁。7MainIndexContents1.如何生成鏈表node<int>*nodeptr1,*nodeptr2;nodeptr1=newnode<int>(1,null);nodeptr2=newnode<int>(2,null);思考：如何連接兩個(gè)結(jié)點(diǎn)？nodeptr1->next=nodeptr2;nodeptr3=newnode<int>(3,null);nodeptr2->next=nodeptr3;7第7頁，共35頁。8MainIndexContents將1,2,3,4,5順序插入鏈表（正向插入）node<int>*nodeptr1,*nodeptr2,*front;for(inti=1;i<6;i++){ nodeptr1=newnode<int>(i,NULL); nodeptr1->next=?}nodeptr1=newnode<int>(1,NULL);Front=nodeptr1;for(inti=2;i<6;i++){ nodeptr2=newnode<int>(i,NULL); nodeptr1->next=nodeptr2; nodeptr1=nodeptr1->next;}2.CreatingaLinkedList8第8頁，共35頁。9MainIndexContents2.CreatingaLinkedList將1,2,3,4,5順序插入鏈表（反向插入）node<int>*front=NULL,*newNode;inti;for(i=1;i<=5;i++){ front=newnode<int>(i,front);}9第9頁，共35頁。10MainIndexContents3.TraverseaLinkedList1.如何全部遍歷while(front!=Null){cout<<front->nodeValue;front=front->next;}2.如何訪問尾部元素while(front->next!=NULL){ front=front->next;}10第10頁，共35頁。11MainIndexContents4.InertanodeatfrontorbackofaLinkedList1.在表頭插入結(jié)點(diǎn)node<int>*p;p=newnode<int>(6,front);front=p;2.在表尾插入結(jié)點(diǎn)node<int>*q=front;while(q->next!=NULL){ q=q->next;}p=newnode<int>(6,NULL);q->next=p;11第11頁，共35頁。12MainIndexContents5.LinkedListwithbackpointernode<int>*front=Null,*newNode,*back;inti=0;while(i<5){ if(i==0){ front=newnode<int>(i,NULL); back=front; } else{ //back指針總是指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)

newNode=newnode<int>(i,NULL); back->next=newNode; back=back->next; } i++;}//創(chuàng)建鏈表的不同編程風(fēng)格，使用back指針12第12頁，共35頁。13MainIndexContentsTheinitiallistisempty:front=NULL,back=NULL.

5.1aLinkedListwithbackpointer13第13頁，共35頁。14MainIndexContents5.2aLinkedListwithbackpointer14第14頁，共35頁。15MainIndexContents5.3InsertinganodeatbackwithabackpointerNode<T>*front,*back,*newNode;newNode=newnode<T>(item);If(front!=Null) back->next=newNode;else front=newNode;back=newNode;15第15頁，共35頁。16MainIndexContents5.4.InsertinganodeatfrontwithabackpointerNode<T>*front,*back,*newNode;newNode=newnode<T>(item,front);If(front==Null) back=newNode;front=newNode;16第16頁，共35頁。17MainIndexContents6.DeletingFromtheFrontofaLinkedListfrontfront//front=NULLDeletingfrontofa1-nodelistDeletingfrontofamulti-nodelist//front=front->next17第17頁，共35頁。18MainIndexContents

6.1DeletinganodeatfrontNode<T>*front,*p;If(front!=Null){ p=front; front=front->next; deletep:}18第18頁，共35頁。19MainIndexContents

6.2DeletinganodeatfrontwithabackpointerNode<T>*front,*back,*p;If(front!=Null){ p=front; front=front->next; if(front==Null) back=Null; deletep:}19第19頁，共35頁。20MainIndexContents

6.3DeletinganodeatbackNode<T>*front,*p;node<int>*p=front;if(p==NULL)exit(1); //空鏈表if(p->next==NULL)deletep; //只有一個(gè)結(jié)點(diǎn)while(p->next->next!=NULL){ p=p->next;//遍歷到倒數(shù)第二個(gè)}q=p->next;p->next=NULL;deleteq;20第20頁，共35頁。21MainIndexContents7.InsertinganddeletinganodeInsert:newNode->next=curr;Prev->next=newNode;Delete:node<T>*curr,*prev;prev->next=curr->next;deletecurr;21第21頁，共35頁。22MainIndexContents8.DeletingaLinkedListnode<T>*p;while(front!=NULL){ p=front; front=front->next; deletep;}22第22頁，共35頁。23MainIndexContents單鏈表基本操作小結(jié)1.如何創(chuàng)建鏈表（正向、反向創(chuàng)建）node<int>*front=Null,*newNode,*back;

inti=0;while(i<5){ if(i==0){ front=newnode<int>(i,NULL); back=front; } else{ //back指針總是指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)

newNode=newnode<int>(i,NULL); back->next=newNode; back=back->next; } i++;}for(i=1;i<=5;i++){ front=newnode<int>(i,front);}23第23頁，共35頁。24MainIndexContents單鏈表基本操作2.如何在鏈表表頭/表尾插入新結(jié)點(diǎn)123front45p1p2表頭插入：p1->next=front;front=p1;表尾插入：back->next=p2;back=p2;注：若沒有back指針，可通過循環(huán)找到鏈表的尾結(jié)點(diǎn)。back24第24頁，共35頁。25MainIndexContents單鏈表基本操作3.如何在鏈表表頭/表尾刪除結(jié)點(diǎn)12345frontbackp表頭結(jié)點(diǎn)刪除：p=front;front=front->next;deletep;表尾結(jié)點(diǎn)刪除：(首先通過循環(huán)找到q結(jié)點(diǎn)，倒數(shù)第２個(gè)結(jié)點(diǎn))back=q->next;q->next=NULL;deleteback;q3.如何在鏈表表頭/表尾刪除結(jié)點(diǎn)25第25頁，共35頁。26MainIndexContents單鏈表基本操作Insert:newNode->next=curr;Prev->next=newNode;Delete:node<T>*curr,*prev;prev->next=curr->next;deletecurr;4.如何在鏈表中任意位置插入/刪除結(jié)點(diǎn)（需前驅(qū)指針/當(dāng)前指針共同推進(jìn),prev/curr）26第26頁，共35頁。27MainIndexContents單鏈表小結(jié)1.如何創(chuàng)建鏈表（正向、反向創(chuàng)建）2.如何在鏈表表頭插入新結(jié)點(diǎn)、刪除頭結(jié)點(diǎn)（鏈表維護(hù)有表尾結(jié)點(diǎn)/沒有表尾結(jié)點(diǎn)）3.如何在鏈表表尾插入新結(jié)點(diǎn)、刪除表尾結(jié)點(diǎn)

(鏈表維護(hù)有表尾結(jié)點(diǎn)/沒有表尾結(jié)點(diǎn))4.如何在鏈表中任意位置插入/刪除結(jié)點(diǎn)（需前驅(qū)指針/當(dāng)前指針共同推進(jìn),prev/curr）5.如何遍歷全部鏈表/如何查找某個(gè)結(jié)點(diǎn)6.如何連接鏈表7.如何拆分鏈表8.如何刪除鏈表27第27頁，共35頁。28MainIndexContents9.RemovingaTargetNode(實(shí)例)注意：前驅(qū)和當(dāng)前指針，交替推進(jìn)28第28頁，共35頁。29MainIndexContentsTemplate<TypenameT>VoideraseValue1(node<T>*front,constT&target){ node<T>*curr=front,*prev=Null; while(curr!=Null){ if(curr->nodeValue==target) { if(prev==Null) front=front->next; else prev->next=curr->next; deletecurr; } else{ prev=curr; curr=curr->next;} } }29第29頁，共35頁。30MainIndexContents思考：刪除鏈表中重復(fù)元素：Template<typenameT>VoidremoveDuplicate(node<T>*front){ TcurrValue; node<T>*curr,*p; curr=front; while(curr!=NULL) { currValue=curr->dataValue; p=curr; p=p->next;

eraseValue1(p,currValue); curr=curr->next; }}10.Removingduplicates30第30頁，共35頁。31MainIndexContentsErasingnodesindescendingorder#include<iostream>#include"d_node.h"#include"d_nodel.h"#include"d_random.h"usingnamespacestd;template<typenameT>node<T>*getMax(node<T>*front);template<typenameT>voideraseValue(node<T>*&front,constT&target);31第31頁，共35頁。32MainIndexContentsErasingnodesindescendingorderintmain(){ node<int>*front=NULL,*p; randomNumberrnd; intlistCount,i; cout<<"Enterthesizeofthelist:"; cin>>lis