7.2鏈表與鏈表的基本操作課件

1、7.2 鏈表與鏈表的基本操作 線性表是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的邏輯結(jié)構(gòu)是n個數(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）組成。一個結(jié)點(diǎn)包含info和link兩個域，info域存放數(shù)據(jù)，類型由應(yīng)用決定；link存放指向該鏈表中下一個結(jié)點(diǎn)的地址。結(jié)點(diǎn)定義如下： typedef int DataType; /數(shù)據(jù)為整型struct Node DataType info; Node *link

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

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

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

5、 head-link=NULL; return head;2.鏈表向后生長一個結(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;headtailinfo0head7.2.1 單鏈表基本算法headinfo0 PPinfo13.鏈表向前生長一結(jié)點(diǎn)void GrowUP(Node*head,DataType data) Node* p=new node; p-info=data; p-link= he

6、ad-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&p-info!=key)p=p-link; /移動preturn p; /返回指針p，指向找到的結(jié)點(diǎn)，或者未找到，返回NULL5. 鏈表節(jié)點(diǎn)p后插入新節(jié)點(diǎn)：注意與向前向后生長算法的區(qū)別！void InsertAfter(Node*p, DataType x)Node *q=new Node;q-info=x;q

7、-link=p-link;p-link=q;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=NULL;/如果該結(jié)點(diǎn)還要用，則不要釋放，將q返回7. 刪除指定結(jié)點(diǎn)pvoid RemoveCur(Node*head, Node*p) Node*q=head; while(q-link!=NULL & q-link!=p) q=q-link; /遍歷查找 RemoveAfter(q);/刪除q后面的結(jié)點(diǎn)p7.2.1 單鏈表基本算法8.清

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)后第一個結(jié)點(diǎn)從鏈中脫落delete p; p=NULL;/刪除脫離下來的結(jié)點(diǎn)7.2.2 單鏈表類設(shè)計不同于【例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 &); /生

9、成一般結(jié)點(diǎn)的構(gòu)造函數(shù) void PrintNode(); /打印當(dāng)前結(jié)點(diǎn)的信息域 friend class SLList; /以SLList為Node友元類，SLList可直接訪問Node私有數(shù)據(jù)，比結(jié)構(gòu)安全;例7.5_h 結(jié)點(diǎn)類Node:Node()link=NULL;Node:Node(const DataType & data)info=data;link=NULL; void Node:PrintNode()coutinfolink!=NULL) /把頭結(jié)點(diǎn)后的第一個結(jié)點(diǎn)從鏈中脫離 p=head-link; head-link=p-link; delete p; p=NULL; /刪除

10、(釋放)脫離下來的結(jié)點(diǎn) tail=head; /表頭指針與表尾指針均指向表頭結(jié)點(diǎn)，表示空鏈例7.5_h 單鏈表類鏈表類成員函數(shù)：Node* SLList:TravFind(DataType key) Node*p=head-link; while(p!=NULL&p-info!=key)p=p-link; return p;/搜索成功返回該結(jié)點(diǎn)地址，不成功返回NULL void SLList:PrintSLL() /顯示鏈表 Node* p=head-link; while(p!=NULL) coutinfolink; coutlink=head-link;head-link=p; /新結(jié)點(diǎn)始

11、終在頭結(jié)點(diǎn)之后void SLList:GrowDN(const DataType& data)Node* p=new Node(data);tail-link=p;tail=p;tail-link=NULL;鏈表類成員函數(shù)：void 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-link!=p) q=q-link;/遍歷

12、查找if(q-link=tail) tail=q;/已經(jīng)找到末尾RemoveAfter(q);/刪除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(); /打印表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)coutlink;head=tail=new Node();while(p!=NULL)GrowDN(p-info);/向后生長一個結(jié)點(diǎn)p=p-link;7.2.2 單鏈表類討論復(fù)制構(gòu)造函數(shù)：/拷貝賦值運(yùn)算符SLList& SLList:operator=(SLList & ls)Node* p