鏈表與鏈表的基本操作.ppt

1、7.2 鏈表與鏈表的基本操作,線性表是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列（a1,a2,an）。而線性表的物理結(jié)構(gòu)包括：順序表(數(shù)組)，鏈表 。,7.2.1 單鏈表基本算法,7.2.3 雙向鏈表(選讀),7.2.1 單鏈表基本算法,單鏈表（Singly Linked list）： 有若干結(jié)點(diǎn)（Node）組成。一個(gè)結(jié)點(diǎn)包含info和link兩個(gè)域，info域存放數(shù)據(jù)，類型由應(yīng)用決定；link存放指向該鏈表中下一個(gè)結(jié)點(diǎn)的地址。,結(jié)點(diǎn)定義如下： typedef int DataType; /數(shù)據(jù)為整型 struct Node DataType info; Node

2、*link; ;,在C/C+中允許一個(gè)類型（結(jié)構(gòu)體或類）的數(shù)據(jù)成員是自身的指針類型，但決不能是自身類型，這會(huì)導(dǎo)致一個(gè)無窮遞歸的定義。,7.2.1 單鏈表基本算法,通常使用表頭指針head指向單鏈表的第一個(gè)結(jié)點(diǎn)，head在使用中千萬不可丟失，否則鏈表整個(gè)丟失，內(nèi)存也發(fā)生泄漏。,infon-1 ,info2,info1,info0,head,圖7.3 單鏈表結(jié)構(gòu),單鏈表的插入與刪除： 只要改變鏈中結(jié)點(diǎn)指針的值，無需移動(dòng)表中的結(jié)點(diǎn)，就能實(shí)現(xiàn)插入和刪除操作。 若考慮在鏈表中包含數(shù)據(jù)info的結(jié)點(diǎn)之前插入一個(gè)新元素，則有三種情況： info位于第一個(gè)結(jié)點(diǎn)；位于中間某個(gè)結(jié)點(diǎn)；沒找到info。,7.2.1

3、單鏈表基本算法,infox,info0,info1,head,插在鏈?zhǔn)祝?首先新結(jié)點(diǎn)的link指針指向info0所在結(jié)點(diǎn)，然后，head指向新結(jié)點(diǎn)。即： newnode-link=head； head=newnode； /注意：鏈表操作次序非常重要,newnode,注意：訪問符“.”與“-”的區(qū)別。 p-link: p為結(jié)點(diǎn)指針； n.link: n為結(jié)點(diǎn); p-link等價(jià)于(*p).link。,7.2.1 單鏈表基本算法,infox,infoi-1,infoi,newnode,插在中間： 結(jié)點(diǎn)型指針q為指向infoi-1的工作指針，則： newnode-link=q-link； q-lin

4、k=newnode；,7.2.1 單鏈表基本算法,infox,newnode,p,infon-1 ,插在隊(duì)尾： 只要工作指針p找到隊(duì)尾，即可鏈在其后： p-link=newnode； newnode-link=NULL;,7.2.1 單鏈表基本算法,帶表頭結(jié)構(gòu)的鏈表： 通過給每一個(gè)鏈表加上一個(gè)表頭結(jié)點(diǎn)，可以提高結(jié)點(diǎn)插入操作的通用性。,空表如下：,head,下面將介紹帶表頭結(jié)構(gòu)的鏈表的各種基本算法。,tail,head,7.2.1 單鏈表基本算法,tail,p,info1,tail,p,tail,1.建立鏈表頭節(jié)點(diǎn) Node* CreatHead() Node *head,*tail; head

5、=new Node; /建立鏈表頭 tail=head; head-link=NULL; return head; 2.鏈表向后生長一個(gè)結(jié)點(diǎn) Node*GrowDN(Node*tail,DataType data) Node* p=new Node; /建立結(jié)點(diǎn) p-info=data; tail-link=p; tail=p; tail-link=NULL; return tail;,head,tail,info0,head,7.2.1 單鏈表基本算法,head,info0,P,P,info1,3.鏈表向前生長一結(jié)點(diǎn) void GrowUP(Node*head,DataType data)

6、Node* p=new node; p-info=data; p-link= head-link ; /新結(jié)點(diǎn)放在原鏈表前方 head-link=p; /頭結(jié)點(diǎn)放新結(jié)點(diǎn)之前 ,7.2.1 單鏈表基本算法,4. 鏈表遍歷查找(按關(guān)鍵字) Node*TravFind(Node*head, DataType key) Node *p=head-link; while(p!=NULL ,7.2.1 單鏈表基本算法,6. 刪除結(jié)點(diǎn)p后的結(jié)點(diǎn) void RemoveAfter(Node*p) Node*q; q=p-link; if(q!=NULL) p-link=q-link; delete q; q=

7、NULL; /如果該結(jié)點(diǎn)還要用，則不要釋放，將q返回 7. 刪除指定結(jié)點(diǎn)p void RemoveCur(Node*head, Node*p) Node*q=head; while(q-link!=NULL /刪除q后面的結(jié)點(diǎn)p ,7.2.1 單鏈表基本算法,8.清空單鏈表,保留表頭結(jié)點(diǎn) void MakeEmpty(Node* head) Node*p; while(head-link!=NULL)/未到尾節(jié)點(diǎn) p=head-link; head-link=p-link; /頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn)從鏈中脫落 delete p; p=NULL; /刪除脫離下來的結(jié)點(diǎn) ,7.2.2 單鏈表類設(shè)計(jì),不

8、同于【例7.5_h】的單鏈表類 定義結(jié)點(diǎn)類： typedef int DataType; class Node DataType info; /數(shù)據(jù)域 Node *link; /指針域 public: Node(); /生成空結(jié)點(diǎn)的構(gòu)造函數(shù) Node(const Datatype ,例7.5_h 結(jié)點(diǎn)類,Node:Node() link=NULL; Node:Node(const DataType ,定義鏈表類: class SLList Node *head,*tail; /鏈表頭指針和尾指針 public: SLList (); /構(gòu)造函數(shù)，生成頭結(jié)點(diǎn)(空鏈表) SLList(); /析構(gòu)

9、函數(shù) void MakeEmpty(); /清空鏈表，只余表頭結(jié)點(diǎn) Node* TravFind(DataType); /搜索數(shù)據(jù)域與data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 void PrintSLL(); /打印鏈表的數(shù)據(jù)域 void GrowUP(const DataType ,7.2.2 單鏈表類,例7.5_h 單鏈表類,鏈表類成員函數(shù)： SLList:SLList() head=tail=new Node(); SLList:SLList() MakeEmpty(); delete head; head=NULL; void SLList:MakeEmpty()/清空鏈表 Node *p

10、; while(head-link!=NULL) /把頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)從鏈中脫離 p=head-link; head-link=p-link; delete p; p=NULL; /刪除(釋放)脫離下來的結(jié)點(diǎn) tail=head; /表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈 ,例7.5_h 單鏈表類,鏈表類成員函數(shù)： Node* SLList:TravFind(DataType key) Node*p=head-link; while(p!=NULL ,例7.5_h 單鏈表類,鏈表類成員函數(shù)： void SLList:GrowUP(const DataType ,鏈表類成員函數(shù)： voi

11、d SLList:RemoveAfter(Node*p) Node*q; q=p-link; if(q!=NULL) p-link=q-link; delete q; q=NULL; ,例7.5_h 單鏈表類,void SLList:RemoveCur(Node*p) Node*q=head; while(q-link!=NULL /刪除q后面的結(jié)點(diǎn)p ,例7.5_h 主函數(shù),void int main() SLList L1; Node n, *tmp; for(int j=0;j10;j+) L1.GrowDN(j); /向后生成鏈表 cout初始鏈表:; L1.PrintSLL(); /

12、打印表 L1.GrowUP(20);/向前插入到頭結(jié)點(diǎn)后 cout插入結(jié)點(diǎn)后的鏈表:; L1.PrintSLL(); /打印 tmp=L1.TravFind(20); /查找插入的結(jié)點(diǎn) n=*tmp; cout找到結(jié)點(diǎn)的信息域:; n.PrintNode(); L1.RemoveCur(tmp);/刪除插入的結(jié)點(diǎn) cout刪除結(jié)點(diǎn)后的鏈表:; L1.PrintSLL();/打印 return 0; ,結(jié)果：,7.2.2 單鏈表類,討論復(fù)制構(gòu)造函數(shù)：P239說法有待改進(jìn)！如下： 本例中沒有給出Node類的復(fù)制構(gòu)造函數(shù)的根本原因在于： 對(duì)Node類復(fù)制的結(jié)果只是一個(gè)孤立結(jié)點(diǎn)： Node:Node(

13、Node （1）不涉及動(dòng)態(tài)內(nèi)存分配，不存在深復(fù)制和淺復(fù)制的問題（參見Node的構(gòu)造函數(shù)），無需自定義復(fù)制構(gòu)造函數(shù)和復(fù)制賦值運(yùn)算符。 （2）Node和SLList類的所有函數(shù)的參數(shù)和返回值僅使用指向Node的指針，因此無需自定義的復(fù)制構(gòu)造函數(shù)； （3）若程序中確實(shí)需要通過復(fù)制建立Node對(duì)象，完全可由系統(tǒng)默認(rèn)的復(fù)制構(gòu)造函數(shù)和復(fù)制賦值運(yùn)算符實(shí)現(xiàn)復(fù)制（按成員）。,7.2.2 單鏈表類,討論復(fù)制構(gòu)造函數(shù)： 單鏈表是通過動(dòng)態(tài)內(nèi)存分配建立的，因此鏈表的復(fù)制就涉及了深復(fù)制與淺復(fù)制問題，必須自定義復(fù)制構(gòu)造函數(shù)和復(fù)制賦值運(yùn)算符。 對(duì)象深復(fù)制過程： （1）復(fù)制對(duì)象主體，即數(shù)據(jù)成員（除了指向動(dòng)態(tài)內(nèi)存的指針）； 數(shù)據(jù)成員只有指向動(dòng)態(tài)內(nèi)存的指針head，tail, 此步不需要！ （2）為當(dāng)前對(duì)象分配獨(dú)立的自由存儲(chǔ)區(qū)空間； 分配一個(gè)完整的鏈表所占據(jù)的自由存儲(chǔ)區(qū)空間！ （3）將被復(fù)制對(duì)象的自由存儲(chǔ)區(qū)目標(biāo)內(nèi)容按位復(fù)制給當(dāng)