第二章線性表-鏈表

第2章線性表

2.1線性表的定義和操作2.2線性表的順序存儲結(jié)構(gòu)及其操作算法

2.3線性表的鏈接存儲結(jié)構(gòu)

2.4

線性表操作在單鏈表上的實(shí)現(xiàn)

本次課教學(xué)內(nèi)容說明本課主題：線性表的鏈接存儲結(jié)構(gòu)表示與操作實(shí)現(xiàn)教學(xué)目的：掌握線性鏈表、單鏈表、表示及實(shí)現(xiàn)方法教學(xué)重點(diǎn)：線性鏈表之單鏈表的表示及實(shí)現(xiàn)方法教學(xué)難點(diǎn)：線性鏈表的概念2.3.1鏈接存儲的概念在鏈?zhǔn)酱鎯χ?每個存儲結(jié)點(diǎn)不僅包含有所存元素本身的信息(稱之為數(shù)據(jù)域),而且包含有元素之間邏輯關(guān)系的信息,即前驅(qū)結(jié)點(diǎn)包含有后繼結(jié)點(diǎn)的地址信息,這稱為指針域,這樣可以通過前驅(qū)結(jié)點(diǎn)的指針域方便地找到后繼結(jié)點(diǎn)的位置,提高數(shù)據(jù)查找速度。一般地,每個結(jié)點(diǎn)有一個或多個這樣的指針域。若一個結(jié)點(diǎn)中的某個指針域不指向任何結(jié)點(diǎn),則僅它的值為空,用常量NULL表示。datap1p2…pmdatapp1datap2

2.3.2線性表的鏈接存儲單鏈表?雙向鏈表?線性表L=(a1,a2,……,an)的單鏈表示意圖（不帶頭結(jié)點(diǎn)的）：2.3.2線性表的鏈接存儲線性表L=(a1,a2,……,an)的單鏈表存儲結(jié)構(gòu)（帶頭結(jié)點(diǎn)的）:2.3.2線性表的鏈接存儲線性表L=(a1,a2,……,an)的多鏈表的結(jié)構(gòu)形式

——一個雙向鏈表結(jié)構(gòu)示例圖線性表的雙向鏈表存儲結(jié)構(gòu)中，有什么特征呢？與單鏈表比較呢？2.3.3單鏈表上的簡單操作插入操作刪除操作

圖2-8從單鏈表中刪除結(jié)點(diǎn)的示意圖

2.3.4單鏈表中結(jié)點(diǎn)類型的定義struct

sNode

{

ElemTypedata;

struct

sNode*next;};datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)示例圖關(guān)于指針變量和結(jié)構(gòu)體類型變量的單元空間大小問題struct

snode{intdata;

struct

snode*next;};main(){struct

snodea;

printf("%o,%d",&a,sizeof(a));}2.3.4單鏈表中結(jié)點(diǎn)類型構(gòu)建單鏈表的簡單例子（p.34-35）如何建立一個具有n個結(jié)點(diǎn)的單鏈表呢？

后面再討論

2.3.5雙向鏈表中的結(jié)點(diǎn)類型和插入與刪除操作2.4線性表操作在單鏈表上的實(shí)現(xiàn)說明：每一個單鏈表（不帶頭結(jié)點(diǎn)）都有一個表頭指針，從而表頭指針代表了一個單鏈表或鏈表1初始化操作voidInitList(struct

sNode**HL){*HL=NULL;}其實(shí)初始化操作就是設(shè)置一個struct

sNode

類型的空值指針變量。如struct

sNode*p;

InitList(&p)就是使得p=NULL.可不可以將操作函數(shù)寫成voidInitList(struct

sNode*HL){HL=NULL;}?2清除線性表L中的所有元素，使之成為一個空表voidClearList(struct

sNode**HL){struct

sNode*cp,*np;cp=*HL;while(cp!=NULL){np=cp->next;free(cp);cp=np;}*HL=NULL;}3返回線性表L的長度，即單鏈表的長度int

SizeList(struct

sNode*HL){inti=0;while(HL!=NULL){i++;HL=HL->nxet;}returni;}類似的算法操作還有P.42的算法6：遍歷一個單鏈表5返回單鏈表中第pos個結(jié)點(diǎn)中的元素，若pos超出范圍，則停止程序運(yùn)行ElemType

GetElem(struct

sNode*HL,intpos){inti=0;/*統(tǒng)計(jì)已遍歷的結(jié)點(diǎn)數(shù)*/if(pos<1){printf("pos值非法，退出運(yùn)行!\n");exit(1);} while(HL!=NULL){i++; if(i==pos)break; HL=HL->next;} if(HL!=NULL)returnHL->data; else{printf("pos值非法，退出運(yùn)行!\n"); exit(1);}}類似的算法還有算法8：修改單鏈表中第pos個結(jié)點(diǎn)的值為x11向單鏈表中第pos個結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn)，若插入成功返回1，否則返回0int

InsertPosList(struct

sNode**HL,intpos,ElemTypex){inti=0;struct

sNode*newp;

struct

sNode*cp=*HL,*ap=NULL;if(pos<=0){printf("pos值不正確,返回0表示插入失敗!\n");return0;} /*查找第pos個結(jié)點(diǎn)*/ while(cp!=NULL){i++;if(pos==i)break;else{ap=cp;cp=cp->next;}}/*產(chǎn)生新結(jié)點(diǎn)，若分配失敗，則停止插入*/

newp=malloc(sizeof(struct

sNode));/*接下頁*/11向單鏈表中第pos個結(jié)點(diǎn)位置插入元素為x的結(jié)點(diǎn)，若插入成功返回1，否則返回0//接上頁if(newp==NULL){printf("內(nèi)存動態(tài)空間用完，無法插入!\n");return0;}

newp->data=x;/*把新結(jié)點(diǎn)插入到表頭*/

if(ap==NULL){newp->next=cp;/*或改為newp->next=*HL*/*HL=newp;}/*把新結(jié)點(diǎn)插入到ap和cp之間*/else{newp->next=cp;ap->next=newp;}/*插入成功返回1*/return1;}/*算法9和算法10為該算法的特例*/4566234566234566462345662846∧∧∧ffff∧圖2-14在單鏈表上進(jìn)行各種插入操作的圖形示例在單鏈表上進(jìn)行各種插入操作的圖形示例voidInsertOrderList(struct

sNode**HL,ElemTypex){struct

sNode*cp=*HL,*ap=NULL;

struct

sNode*newp;

newp=malloc(sizeof(struct

sNode));

if(newp==NULL){

printf("內(nèi)存動態(tài)空間用完，退出運(yùn)行!\n"); exit(1);}

newp->data=x;/*見下頁*/

12向有序單鏈表中插入元素x結(jié)點(diǎn)，使得插入后仍然有序if(cp==NULL||x<cp->data){

newp->next=cp; *HL=newp; return;} while(cp!=NULL) {if(x<cp->data)break;else{ap=cp;cp=cp->next;}} /*把x結(jié)點(diǎn)插入到ap和cp之間*/

newp->next=cp;

ap->next=newp;}//接上頁16從單鏈表中刪除值為x的第一個結(jié)點(diǎn)，若刪除成功則返回1否則返回0int

DeleteValueList(struct

sNode**HL,ElemTypex){ struct

sNode*cp=*HL;

struct

sNode*ap=NULL; while(cp!=NULL){ if(cp->data==x)break;

ap=cp;cp=cp->next; } if(cp==NULL)return0;

/*見下頁*/

/*對刪除的是表頭或非表頭分別進(jìn)行處理*/

if(ap==NULL)*HL=(*HL)->next;/*或改為*HL=cp->next*/elseap->next=cp->next;/*回收被刪除的結(jié)點(diǎn)*/free(cp);return1; }2.4線性表操作在單鏈表上的實(shí)現(xiàn)1556423973∧f從單鏈表中刪除值為x的第一個結(jié)點(diǎn)，若刪除成功則返回1否則返回060(1)對如下圖所示的單鏈表,若DeleteValueList(&f,15),那么要刪除的結(jié)點(diǎn)為第一個結(jié)點(diǎn)，其值為15，那么對應(yīng)的處理為(2)對如下圖所示的單鏈表,若DeleteValueList(&f,39),那么要刪除的結(jié)點(diǎn)為非第一個結(jié)點(diǎn)(第四個)，那么對應(yīng)的處理為if(ap==NULL)*HL=(*HL)->next;elseap->next=cp->next;2.4線性表操作在單鏈表上的實(shí)現(xiàn)1556423973∧f600其實(shí)對于算法16，可以采用帶附加頭結(jié)點(diǎn)的方法來使得操作更加方便。如下所示的單鏈表f,調(diào)用DeleteValueList(&f,15)和調(diào)用DeleteValueList(&f,42)時(shí)，當(dāng)找到要刪除的結(jié)點(diǎn)時(shí)，就不必要對所要刪除的結(jié)點(diǎn)進(jìn)行判斷是否為表頭結(jié)點(diǎn)，可以直接用下面語句處理就可以了：ap->next=cp->next;if(ap==NULL)*HL=(*HL)->next;elseap->next=cp->next;int

DeleteValueList(struct

sNode*HL,ElemTypex){ struct

sNode*cp=HL->next;

struct

sNode*ap=HL; while(cp!=NULL){ if(cp->data==x)break;

ap=cp;cp=cp->next; } if(cp==NULL)return0;

ap->next=cp->next;free(cp);/*回收被刪除的結(jié)點(diǎn)*/return1;}其實(shí)對于算法16，采用帶附加頭結(jié)點(diǎn)的單鏈表，程序改為如下：int

DeleteValueList(struct

sNode*HL,ElemTypex){ struct

sNode*cp=HL->next;

struct

sNode*ap=HL; while(cp!=NULL){ if(cp->data==x)break;

ap=cp;cp=cp->next; } if(cp==NULL)return0;

ap->next=cp->next;free(cp);/*回收被刪除的結(jié)點(diǎn)*/return1;}其實(shí)對于算法16，采用帶附加頭結(jié)點(diǎn)的單鏈表，程序還可以改為如下：思考題

建立單鏈表(1)在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表鏈表與順序表不同，它是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每個結(jié)點(diǎn)占用的存儲空間不是預(yù)先分配，而是運(yùn)行時(shí)系統(tǒng)根據(jù)需求而生成的，因此建立單鏈表從空表開始，每讀入一個數(shù)據(jù)元素則申請一個結(jié)點(diǎn)，然后插在鏈表的頭部，如圖下圖展現(xiàn)了線性表：（25,45,18,76,29）之鏈表的建立過程，因?yàn)槭窃阪湵淼念^部插入，讀入數(shù)據(jù)的順序和線性表中的邏輯順序是相反的?！?5∧4525187629761825∧45251825∧452525∧452525∧在頭部插入建立單鏈表(2)在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表頭插入建立單鏈表簡單，但讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾插入的方法。因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部，所以需加入一個指針

r用來始終指向鏈表中的尾結(jié)點(diǎn)，以便能夠?qū)⑿陆Y(jié)點(diǎn)插入到鏈表的尾部，如圖2.11展現(xiàn)了在鏈表的尾部插入結(jié)點(diǎn)建立鏈表的過程

。

在尾部插入建立單鏈表H=NULLr=NULL/*初始狀態(tài)*/29rH7629rH187629rH25∧4525187629rH4525187629rH單鏈表的存儲結(jié)構(gòu)typestruct

sNode

{ElemTypedata;

struct

sNode*next;}Lnode;在單鏈表中某結(jié)點(diǎn)p后面插入結(jié)點(diǎn)s，如圖1所示。……xsp圖1插入結(jié)點(diǎn)時(shí)指針的變化插入算法為：s=(Lnode*)malloc(sizeof(Lnode);s->data=x;s->next=p->next;p->next=s建立單鏈表根據(jù)單鏈表中某結(jié)點(diǎn)p后面插入結(jié)點(diǎn)s的算法，可以從無到有通過反復(fù)調(diào)用該算法而構(gòu)建一個單鏈表。兩種方式：前插法、后插法。前插法：先建立一個帶頭結(jié)點(diǎn)的空鏈表，然后依次反復(fù)生成新結(jié)點(diǎn)并插入到頭結(jié)點(diǎn)后，如圖2所示xsphead…圖2前插法建立單鏈表指針的變化前插法算法為：voidCreate_List_f(Lnode**head,intn){*head=(Lnode*)malloc(sizeof(Lnode);p=*head;*head->next=NULL;for(i=n;i>0;--i){s=(Lnode*)malloc(sizeof(Lnode);

scanf()//輸入結(jié)點(diǎn)數(shù)據(jù)xs->data=x;//生成新結(jié)點(diǎn)

s->next=p->next;p->next=s;//插入到表頭

}}headxs…x…p圖3后插法建立單鏈表指針的變化后插法算法為：voidCreate_List_f(Lnode**head,intn){*head=(Lnode*)malloc(sizeof(Lnode);p=