第2章線性表2(單鏈表)課件

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、單鏈表的存儲(chǔ)結(jié)構(gòu)二、單鏈表的操作實(shí)現(xiàn)三、鏈表的運(yùn)算效率分析1１、單鏈?zhǔn)郊氨硎痉椒?1)單鏈表:構(gòu)成鏈表的結(jié)點(diǎn)只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針。其結(jié)構(gòu)特點(diǎn)：邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針域數(shù)據(jù)域nextdata或樣式：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼的存儲(chǔ)位置設(shè)計(jì)思想：犧牲空間效率換取時(shí)間效率一、單鏈表的存儲(chǔ)結(jié)構(gòu)2定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下:

typedefstructNode

{

DataTypedata;

structNode*next;

}SLNode;

其中,data域用來存放數(shù)據(jù)元素,next域用來存放指向下一個(gè)結(jié)點(diǎn)的指針。

3例：請(qǐng)畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）鏈表存放示意圖如下：a1heada2/\an……討論1：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和

。討論2：在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由

指示。其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域(鏈域)41）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：

結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……循環(huán)鏈表示意圖：head(2)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：54）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2…infoan^頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計(jì)入表長度。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。示意圖如下：6答：討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2.如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；^頭指針無頭結(jié)點(diǎn)^頭指針頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。頭結(jié)點(diǎn)不計(jì)入鏈表長度！7一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針H的值是31２、帶頭結(jié)點(diǎn)單鏈表和不帶頭結(jié)點(diǎn)單鏈表的比較例：8上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)頭結(jié)點(diǎn)不計(jì)入鏈表長度！9

對(duì)比帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程和不帶帶頭結(jié)點(diǎn)的單鏈表的插入、刪除過程，可以得知：若設(shè)計(jì)的單鏈表帶頭結(jié)點(diǎn)，則無論是在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入還是在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入都不會(huì)改變頭指針的數(shù)值。若設(shè)計(jì)的單鏈表不帶頭結(jié)點(diǎn)，則在第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)前插入與在其他數(shù)據(jù)元素結(jié)點(diǎn)前插入其算法的處理方法不同。在單鏈表中刪除一個(gè)結(jié)點(diǎn)時(shí)類似。因此，單鏈表一般構(gòu)造成帶頭結(jié)點(diǎn)的單鏈表。10討論:

鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：以26個(gè)字母的鏈表為例，每個(gè)結(jié)點(diǎn)都有兩個(gè)分量：字符型指針型設(shè)每個(gè)結(jié)點(diǎn)用變量node表示，其指針用p表示，兩個(gè)分量分別用data和*next表示，這兩個(gè)分量如何賦值？p*nextdatanode方式1：直接表示為

node.data＝'a'；node.next=q方式2：p指向結(jié)點(diǎn)首地址，然后p->data='a';p->next=q;方式3：p指向結(jié)點(diǎn)首地址，然后(*p).data='a'；(*p).next＝q‘a(chǎn)’‘b’qp11設(shè)p為指向鏈表的第i個(gè)元素的指針,則第i個(gè)元素的數(shù)據(jù)域?qū)憺?/p>

，指針域?qū)憺?/p>

。練習(xí)：p->dataai的值p->nextai+1的地址附1：介紹C的三個(gè)有用的庫函數(shù)/算符（都在<stdlib.h>中）：sizeof(x)——計(jì)算變量x的長度（字節(jié)數(shù)）；malloc(m)—開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；free(p)——釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。12sizeof(x)——計(jì)算x的長度malloc(m)—開m字節(jié)空間free(p)——?jiǎng)h除一個(gè)變量問1：自定義結(jié)構(gòu)類型變量node的長度m是多少？問2：結(jié)構(gòu)變量node的首地址(指針p）是多少？問3：怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長度為m字節(jié)pm＝sizeof(node)//單位是字節(jié)p＝(node*)malloc(m)free(p)//只能借助node的指針刪除！p->data=‘a(chǎn)’;p->next=q13②對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為：SLNode*p,*q;

//或用struct

SLNode

*p,*q;//注：上面已經(jīng)定義了SLNode為用戶自定義的Node類型。①類型定義和變量說明可以合寫為：typedefstructNode//Node是自定義結(jié)構(gòu)類型名稱{DataTypedata;//定義數(shù)據(jù)域的變量名及其類型structNode*next;//定義指針域的變量名及其類型}SLNode，*p;//SLNode是Node結(jié)構(gòu)類型的類型替代,

*p是指針型的Node結(jié)構(gòu)類型的替代附2：補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法1415例：單鏈表的建立和輸出例：用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線性表（a，b，c，…，z）,請(qǐng)寫出C語言程序。實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開辟存儲(chǔ)空間并及時(shí)賦值，后繼結(jié)點(diǎn)的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”！16#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;將全局變量及函數(shù)提前說明：node*p,*q,*head;//一般需要3個(gè)指針變量intn;//數(shù)據(jù)元素的個(gè)數(shù)intm=sizeof(node);/*結(jié)構(gòu)類型定義好之后，每個(gè)node類型的長度就固定了，m求一次即可*/17新手特別容易忘記?。inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=1;i<26;i++)//因尾結(jié)點(diǎn)要特殊處理，故i≠26{p->data=i+‘a(chǎn)’-1;//第一個(gè)結(jié)點(diǎn)值為字符ap->next=(node*)malloc(m);//為后繼結(jié)點(diǎn)“挖坑”！p=p->next；}

//讓指針變量P指向后一個(gè)結(jié)點(diǎn)p->data=i+‘a(chǎn)’-1;//最后一個(gè)元素要單獨(dú)處理p->next=NULL;}//單鏈表尾結(jié)點(diǎn)的指針域要置空！voidbuild()//字母鏈表的生成。要一個(gè)個(gè)慢慢鏈入18{p=head;while(p)//當(dāng)指針不空時(shí)循環(huán)（僅限于無頭結(jié)點(diǎn)的情況）{printf("%c",p->data);p=p->next;//讓指針不斷“順藤摸瓜”

}}討論：要統(tǒng)計(jì)鏈表中數(shù)據(jù)元素的個(gè)數(shù)，該如何改寫？

sum++;sum=0;voiddisplay()/*字母鏈表的輸出*/19voidmain()

{

build();

display();

}

問：上述建立的單鏈表帶頭結(jié)點(diǎn)嗎？

20二、單鏈表的操作實(shí)現(xiàn)定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體如下:

typedefstructNode

{

DataTypedata;

structNode*next;

}SLNode;１、初始化voidListInitiate(SLNode**head)／*初始化*/{ /*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/ if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1); (*head)->next=NULL; /*置鏈尾標(biāo)記NULL*/}21２、求單鏈表中數(shù)據(jù)元素的個(gè)數(shù)

intListLength(SLNode*head)

{

SLNode*p=head;/*p指向頭結(jié)點(diǎn)*/

intsize=0;/*size初始為0*/

while(p->next!=NULL)/*循環(huán)計(jì)數(shù)*/

{

p=p->next;

size++;

}

returnsize;

}22在鏈表中插入一個(gè)元素X的示意圖如下：Xqabp鏈表插入的核心語句：Step1：q->next=p->next;Step2：p->next=q；p->nextp->next思考：Step1和2能互換么？X結(jié)點(diǎn)的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q->data=X;q->next=?bap插入X３、向單鏈表中插入一個(gè)元素23intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q; intj; p=head; j=-1;while(p->next!=NULL&&j<i-1){(1) p=p->next;j++; } if(j!=i-1){ printf("插入位置參數(shù)錯(cuò)！"); return0;}(2)

if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1); q->data=x;(3)

q->next=p->next; p->next=q;(4) return1;} 注：此單鏈表是帶頭結(jié)點(diǎn)的24在鏈表中刪除某元素b的示意圖如下：cabp刪除動(dòng)作的核心語句（要借助輔助指針變量q）：q

=p->next;

//首先保存b的指針，靠它才能找到c；p->next=q->next;

//將a、c兩結(jié)點(diǎn)相連，淘汰b結(jié)點(diǎn)；free(q)；

//徹底釋放b結(jié)點(diǎn)空間p->next思考：省略free(q)語句行不行？(p->next)->next××q４、從單鏈表中刪除一個(gè)元素25intListDelete(SLNode*head,inti,DataType*x){ SLNode*p,*s; intj;(1)p=head; j=-1; while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){ p=p->next; j++; } if(j!=i-1) {printf(“插入位置參數(shù)錯(cuò)！”);return0; }(2)

s=p->next;*x=s->data;(3)p->next=p->next->next; free(s);

return1;} 26三、單鏈表的操作效率分析（1）查找

因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為O(n)。時(shí)間效率分析（2）插入和刪除

因線性鏈表不需要移動(dòng)元素，只要修改指針，僅就插入或刪除而言，時(shí)間復(fù)雜度為O(1)。但是，如果要在單鏈表中進(jìn)行在某結(jié)點(diǎn)前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所以一般情況下，單鏈表插入和刪除操作的時(shí)間復(fù)雜度是O(n)（同順序表）。27五、循環(huán)單鏈表xheada0an……循環(huán)鏈表示意圖：循環(huán)單鏈表是單鏈表的另一種形式，其結(jié)構(gòu)特點(diǎn)是鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域不再是結(jié)束標(biāo)記，而是指向整個(gè)鏈表的第一個(gè)結(jié)點(diǎn)，從而使鏈表形成一個(gè)環(huán)。問：帶頭結(jié)點(diǎn)的循環(huán)單鏈表的插入、刪除算法如何寫？head28例2：試用C語言編寫一個(gè)算法，將一循環(huán)單鏈表就地逆置。操作前：（a1,a2,…ai-1，ai,ai+1，…,an）操作后：（an,…a