第2章2線性表的單鏈表存儲(chǔ)結(jié)構(gòu)課件

1typedefstructNode{DataTypedata;structNode*next;}SLNode,*LinkList;對(duì)于線性表的單鏈表存儲(chǔ)結(jié)構(gòu)描述:討論：?jiǎn)?：第一行的Node與最后一行的SLNode是不是一回事？答1：不是。前者Node是結(jié)構(gòu)名，后者SLNode是對(duì)整個(gè)struct類型的一種“縮寫(xiě)”，是一種“新定義名”，它只是對(duì)現(xiàn)有類型名的補(bǔ)充，而不是取代。請(qǐng)注意：typedef不可能創(chuàng)造任何新的數(shù)據(jù)類型，而僅僅是在原有的數(shù)據(jù)類型中命名一個(gè)新名字，其目的是使你的程序更易閱讀和移植。2typedefstructstudent{charname;intage;}student,*pointer;注意：student和student同名但不同意。同名是為了表述起來(lái)方便。例如，若結(jié)構(gòu)名為student，其新定義名縮寫(xiě)也最好寫(xiě)成student，因?yàn)槊枋龅膶?duì)象相同，方便閱讀和理解。問(wèn)2：結(jié)構(gòu)體中間的那個(gè)structNode是何意？答2：在“縮寫(xiě)”

SLNode還沒(méi)出現(xiàn)之前，只能用原始的structNode來(lái)進(jìn)行變量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)據(jù)類型是structNode。3例：?jiǎn)捂湵淼慕⒑洼敵隼河脝捂湵斫Y(jié)構(gòu)來(lái)存放26個(gè)英文字母組成的線性表（a，b，c，…，z）,請(qǐng)寫(xiě)出C語(yǔ)言程序。實(shí)現(xiàn)思路：先開(kāi)辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開(kāi)辟存儲(chǔ)空間并及時(shí)賦值，后繼結(jié)點(diǎn)的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”！4#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;將全局變量及函數(shù)提前說(shuō)明：node*p,*q,*head;//一般需要3個(gè)指針變量intn;//數(shù)據(jù)元素的個(gè)數(shù)intm=sizeof(node);/*結(jié)構(gòu)類型定義好之后，每個(gè)node類型的長(zhǎng)度就固定了，m求一次即可*/5新手特別容易忘記?。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è)慢慢鏈入6{p=head;while(p)//當(dāng)指針不空時(shí)循環(huán)（僅限于無(wú)頭結(jié)點(diǎn)的情況）

{printf("%c",p->data);p=p->next;//讓指針不斷“順藤摸瓜”

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

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

{

build();

display();

}

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

8二、單鏈表的操作實(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*/}9２、求單鏈表中數(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;

}10在鏈表中插入一個(gè)元素X的示意圖如下：Xqabp鏈表插入的核心語(yǔ)句：Step1：q->next=p->next;Step2：p->next=q；p->nexts->next思考：Step1和2能互換么？X結(jié)點(diǎn)的生成方式：m=sizeof(SLNode);q=(SLNode*)malloc(m);q->data=X;q->next=?bap插入X３、向單鏈表中插入一個(gè)元素11intListInsert(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)的12在鏈表中刪除某元素b的示意圖如下：cabp刪除動(dòng)作的核心語(yǔ)句（要借助輔助指針變量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)語(yǔ)句行不行？(p->next)->next××q４、從單鏈表中刪除一個(gè)元素13intListDelete(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;

} 14三、單鏈表的操作效率分析（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)（同順序表）。15四、應(yīng)用舉例例１、編程實(shí)現(xiàn)：建立一個(gè)單鏈表，首先依次輸入數(shù)據(jù)元素１,２,…,10，然后刪除數(shù)據(jù)元素５，最后依次顯示當(dāng)前表中的數(shù)據(jù)元素。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintDataType; #include"LinList.h"重點(diǎn)是鏈表16voidmain(void)

{SLNode*head;

inti,x;

ListInitiate(&head);

for(i=0;i<10;i++){

if(ListInsert(head,i,i+1)==0)

{printf("錯(cuò)誤!\n");return;}

}

if(ListDelete(head,4,&x)==0){

printf("錯(cuò)誤!\n");

return;

}

17for(i=0;i<ListLength(head);i++)

{

if(ListGet(head,i,&x)==0)

{ printf("錯(cuò)誤!\n");

return;}

elseprintf("%d",x);

}

Destroy(&head);

}

18五、循環(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)。問(wèn)：帶頭結(jié)點(diǎn)的循環(huán)單鏈表的插入、刪除算法如何寫(xiě)？head19例2：試用C語(yǔ)言編寫(xiě)一個(gè)算法，將一循環(huán)單鏈表就地逆置。操作前：（a1,a2,…ai-1，ai,ai+1

，…,an）操作后：（an,…ai+1

，ai,ai-1

，…,a2,a1

）20q=head;p=head->next;//有頭結(jié)點(diǎn)while(p!=head)//循環(huán)單鏈表{r=p->next;p->next=q;//前驅(qū)變后繼

q=p;p=r;}//準(zhǔn)備處理下一結(jié)點(diǎn)head->next=q;//以an為首q=head;p=head->next;//有頭結(jié)點(diǎn)while(p!=head)//循環(huán)單