數(shù)據(jù)結(jié)構(gòu)2-線性表課件

第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4應(yīng)用舉例2022/11/171第2章線性表2.1線性表的邏輯結(jié)構(gòu)2022/112.1線性表的邏輯結(jié)構(gòu)2022/11/172（a1,a2,…ai-1，ai,ai＋1

，…,an）線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長。n≥0空表線性終點(diǎn)2.1線性表的邏輯結(jié)構(gòu)2022/11/102（a1,2（A,B,C,D,……,Z）2022/11/173例2分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析：數(shù)據(jù)元素都是同類型（記錄），元素間關(guān)系是線性的。分析：

數(shù)據(jù)元素都是同類型（字母），元素間關(guān)系是線性的。注意：同一線性表中的元素必定具有相同特性！例1分析26個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。（A,B,C,D,……,Z）3“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。2022/11/174×是指各元素具有相同的數(shù)據(jù)類型試判斷下列敘述的正誤：“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)4a1a3a4ana2線性表的特性1.有限性：線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1,ai)，即ai-1是ai的前驅(qū)，ai是ai-1的后繼；a1無前驅(qū)，an無后繼，其它每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。

a1a3a4ana2線性表的特性1.有限性：線性表中數(shù)據(jù)元5線性表的抽象數(shù)據(jù)類型定義ADTList{數(shù)據(jù)對(duì)象：

D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D

}基本操作：InitList（&L）前置條件：表不存在輸入：無

功能：表的初始化輸出：無

后置條件：建一個(gè)空表線性表的抽象數(shù)據(jù)類型定義ADTList{6DestroyList（&L）前置條件：表已存在

輸入：無

功能：銷毀表

輸出：無

后置條件：釋放表所占用的存儲(chǔ)空間ListLength（L）

前置條件：表已存在

輸入：無

功能：求表的長度

輸出：表中數(shù)據(jù)元素的個(gè)數(shù)

后置條件：表不變線性表的抽象數(shù)據(jù)類型定義DestroyList（&L）線性表的抽象數(shù)據(jù)類型定義7GetElem（L,i,&e）

前置條件：表已存在

輸入：元素的序號(hào)i

功能：在表中取序號(hào)為i的數(shù)據(jù)元素

輸出：若i合法，用e返回序號(hào)為i的元素值，否則拋出異常

后置條件：表不變LocateElem（L,e,compare()）

前置條件：表已存在

輸入：數(shù)據(jù)元素e

功能：在線性表中查找值等于e的元素

輸出：若查找成功，返回e在表中的序號(hào)，否則返回0

后置條件：表不變線性表的抽象數(shù)據(jù)類型定義GetElem（L,i,&e）線性表的抽象數(shù)據(jù)類型定義8線性表的抽象數(shù)據(jù)類型定義ListInsert（&L,i,e）

前置條件：表已存在

輸入：插入位置i；待插元素e 功能：在表的第i個(gè)位置處插入一個(gè)新元素e

輸出：若插入不成功，拋出異常

后置條件：若插入成功，表中增加一個(gè)新元素，長度增加1ListDelete（&L,i,&e）

前置條件：表已存在

輸入：刪除位置i

功能：刪除表中的第i個(gè)元素

輸出：若刪除成功，用e返回被刪元素，否則拋出異常

后置條件：若刪除成功，表中減少一個(gè)元素，長度減1線性表的抽象數(shù)據(jù)類型定義ListInsert（&L,i,9線性表的抽象數(shù)據(jù)類型定義ListEmpty(L)

前置條件：表已存在

輸入：無

功能：判斷表是否為空

輸出：若是空表，返回1，否則返回0

后置條件：表不變}ADT進(jìn)一步說明:（1）線性表的基本操作根據(jù)實(shí)際應(yīng)用而定；（2）復(fù)雜的操作可以通過基本操作的組合來實(shí)現(xiàn)；（3）對(duì)不同的應(yīng)用，操作的接口可能不同。線性表的抽象數(shù)據(jù)類型定義ListEmpty(L)進(jìn)一步說明10例2-1求兩個(gè)集合的并,即A=A∪B分析：設(shè)A、B分別由兩個(gè)線性表LA和LB表示，要求將LB中存在而LA中不存在的DE插入到表LA中。算法思想：①依次從LB中取出一個(gè)DE；②判在LA中是否存在；③若不存在，則插入到LA中。例2-1求兩個(gè)集合的并,即A=A∪B算法思想：①依次從11算法描述voidunion(List&La,list&Lb)//將所有在Lb中存在而La中不存在的數(shù)據(jù)元素插入到La中去n=ListLength(La)；//確定線性表La的長度m=ListLength(Lb)；FOR(i=1;i<=m;i++)

{

GetElem(Lb,i,e)；//取Lb中第i個(gè)數(shù)據(jù)元素k=LocateElem(La,e)；//在La中進(jìn)行搜索

if(!k){

ListInsert(La,n+1,e)；//在LA表尾插入n=n+1//表長加1

}}算法描述12例2-2線性表LA和LB，兩表中數(shù)據(jù)元素按值非遞減有序排列。要求將LA和LB歸并到新線性表LC，且LC中數(shù)據(jù)元素仍然按值非遞減排列。例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)

則：LC=(2,3,5,6,8,8,9,11,11,15,20)例2-2線性表LA和LB，兩表中數(shù)據(jù)元素按值非遞減有13例2-2算法思想：①初始化：置LC為空表，設(shè)置變量i,j，初值為1，分別指向LA和LB的第一個(gè)DE，k表示LC的長度，初值為0。②當(dāng)i<=LENGTH(LA)ANDj<=LENGTH(LB)時(shí)，判斷：

若i所指的元素<=j所指的元素，則將i所指的元素插入在LC的k+1前，并且i,k的值分別加1；否則，將j所指的元素插入在LC的k+1前，并且j,k的值分別加1。③重復(fù)②直到某個(gè)表的元素插入完畢。④將未插入完的表的余下的元素，依次插入在LC后。例2-2算法思想：14算法描述voidMergeList(ListLa,listLb,List&Lc){//LA和LB中元素依值非遞減有序排列//歸并得到的LC中的元素仍依值非遞減有序排列

InitList（Lc）；i=1；j=1；k=0；//初始化La_len=ListLength(La);Lb_len=ListLength(Lb);

WHILE(i<=

La_len)&&(j<=

La_len))//當(dāng)前元素的標(biāo)號(hào)未超出La

{

//和Lb的長度

GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i}else{ListInsert(Lc,++k,bj);++j}}while(i<=La_len){

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}

while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//endMergList算法描述while(j<=Lb_len152.2線性表的順序表示和實(shí)現(xiàn)2022/11/17162.2.1順序表的表示2.2.2順序表的實(shí)現(xiàn)2.2.3順序表的運(yùn)算效率分析2.2線性表的順序表示和實(shí)現(xiàn)2022/11/10順序表的表示用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素。2022/11/1717把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。順序存儲(chǔ)定義：順序存儲(chǔ)方法：特點(diǎn)：邏輯上相鄰的元素，物理上也相鄰可以利用數(shù)組V[n]來實(shí)現(xiàn)注意：在C語言中數(shù)組的下標(biāo)是從0開始，即：

V[n]的有效范圍是從V[0]～V[n-1]2.2.1順序表的表示用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)171.

邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.

若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組V[n]的下標(biāo)）。2022/11/1718設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai+1)=LOC(ai)+L

LOC(ai)=LOC(a1)+L*（i-1）對(duì)上述公式的解釋如圖所示線性表順序存儲(chǔ)特點(diǎn)：1.邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2022/1182022/11/1719

地址內(nèi)容元素在表中的位序1i2n空閑區(qū)i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)LLOC(ai)=LOC(a1)+L*（i-1）線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖下標(biāo)起點(diǎn)是12022/11/1019地址19設(shè)有一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素Ｍ[０]的第一個(gè)字節(jié)的地址是98，則Ｍ[３]的第一個(gè)字節(jié)的地址是多少？2022/11/1720答案：113但此題要注意下標(biāo)起點(diǎn)是從0開始：LOC(M[3])=98+5×(4-1)=113解：已知地址計(jì)算通式為：LOC(ai)=LOC(a1)+L*（i-1）例1設(shè)有一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)202022/11/1721

charV[26];voidbuild(intn)/*字母線性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)

V[i]=V[i-1]+1;

}核心語句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例2用數(shù)組V來存放26個(gè)英文字母組成的線性表（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。省略了include語句2022/11/1021

核心語句：例2用數(shù)組V來存放2212022/11/1722voidmain(void)

/*主函數(shù)，字母線性表的生成和輸出*/{n=26;

/*n是表長，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V的實(shí)際下標(biāo)*/build(n);display(n);}voiddisplay(intn)

/*字母線性表的顯示，即讀表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",v[i]);printf("\n");}執(zhí)行結(jié)果：abcdefghijklmnopqrstuvwxyz2022/11/1022voidmain(void)222.2.2順序表的實(shí)現(xiàn)（或操作）2022/11/1723數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：

修改、插入、刪除、查找、排序1)修改通過數(shù)組的下標(biāo)便可訪問某個(gè)特定元素并修改之。核心語句:

V[i]=x;2.2.2順序表的實(shí)現(xiàn)（或操作）2022/11/102232022/11/1724在線性表的第i個(gè)位置前插入一個(gè)元素實(shí)現(xiàn)步驟：將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素寫到第i個(gè)位置；表長加1。注意：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?

應(yīng)當(dāng)符合條件：1≤i≤n+1或i=[1,n+1]for(j=n;j>=i;j--)a[j+1]=a[j];

a[i]=x;n++;//元素后移一個(gè)位置//插入x//表長加1核心語句：2)插入2022/11/1024在線性表的第i個(gè)位置前插入一個(gè)元素實(shí)242022/11/1725在線性表的第i個(gè)位置前插入一個(gè)元素的示意圖如下：插入252022/11/1025在線性表的第i個(gè)位置前插入一個(gè)元素的25實(shí)現(xiàn)步驟：將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；表長減1。注意：事先需要判斷，刪除位置i是否合法?應(yīng)當(dāng)符合條件：1≤i≤n或i=[1,n]2022/11/1726刪除線性表的第i個(gè)位置上的元素for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一個(gè)位置//表長減1核心語句：3)刪除實(shí)現(xiàn)步驟：2022/11/1026刪除線性表的第i個(gè)位置上的262022/11/1727刪除順序表中某個(gè)指定的元素的示意圖如下：順序表插入和刪除的完整程序請同學(xué)們自編。2022/11/1027刪除順序表中某個(gè)指定的元素的示意圖如272.2.3順序表的運(yùn)算效率分析算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度）T(n)=O(移動(dòng)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.2022/11/1728思考：若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)才合理。討論1：若在長度為n的線性表的第i位前插入一個(gè)元素，則向后移動(dòng)元素的次數(shù)f(n)為: f(n)=n–i+1時(shí)間效率分析:2.2.3順序表的運(yùn)算效率分析算法時(shí)間主要耗費(fèi)在移動(dòng)元素282022/11/1729推導(dǎo)：假定在每個(gè)元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來計(jì)算平均執(zhí)行時(shí)間：將所有位置的執(zhí)行時(shí)間相加，然后取平均。若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移次數(shù)為n；若在a1后面插入，要后移n-1個(gè)元素，后移次數(shù)為n-1;……若在an-1后面插入，要后移次數(shù)為1；若在尾結(jié)點(diǎn)an之后插入，則后移次數(shù)為0；

故插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少種插入形式?——連頭帶尾有n+1種!所有可能的元素移動(dòng)次數(shù)合計(jì)：0+1+…+n=n(n+1)/22022/11/1029推導(dǎo)：假定在每個(gè)元素位置上插入x的可29線性表的抽象數(shù)據(jù)類型定義（見教材P19）初始化、撤銷、清空、判空；求表長、表頭、表尾、前趨、后繼；讀元素、查找（含定位）、遍歷；插入、刪除2022/11/1730ADTList

{數(shù)據(jù)對(duì)象：D={ai

|ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai–1,ai>|ai–1,ai∈D,i=2,…,n}基本操作：}

ADTList線性表的抽象數(shù)據(jù)類型定義（見教材P19）2022/11/1030線性表的基本操作如何表示？（見教材P19）2022/11/1731InitList(&L);//建空表，初始化DestoryList(&L);//撤銷表，釋放內(nèi)存intLengthList(L);//求表中元素個(gè)數(shù)，即表長POSITIONLocateElem(L,ElemTypee，compare())//查找ePriorElem(L,cur_e,&pre_e);//求當(dāng)前元素e的前驅(qū)NextElem(L,cur_e,&next_e);//求當(dāng)前元素e的后繼ListInsertBefore(&L,i,e);//把e插入到第i個(gè)元素之前ListDelete(&L,i,&e);//刪除第i個(gè)元素并“看”此元素ListTraverse(L,Visit());//“看”表中全部元素（遍歷）初始化、撤銷、清空、判空；求表長、表頭、表尾、前趨、后繼；讀元素、查找（含定位）、遍歷；插入、刪除線性表的基本操作如何表示？（見教材P19）2022/11/312022/11/1732順序表操作的典型例子教材例2-1：求兩個(gè)線性表的“并”，即：LAULB=?算法至少有兩種：①LA和LB都是無序表，則從LB中取元素逐一與LA中所有元素比較，相同則不插入LA中；②若LA和LB已經(jīng)是有序表，則“歸并”的時(shí)間效率可以大大提高。2022/11/1032順序表操作的典型例子教材例2-1：求32歸并的算法2022/11/17331。從LB中取每一元素GetElem（LB,i,e）2。依值在LA中查找LocateElem（LA,e,equal()）3。若不存在，則插入ListInsert（LA,n+1，e）歸并的算法2022/11/10331。從LB中取每一元素2。332022/11/1734voidunion(List&La，ListLb){La-len=ListLength(La);Lb-len=ListLength(Lb);for(i=1;i<=Lb-len;i++){GetElem(Lb，i，e);if(!LocateElem(La，e，equal))ListInsert(La，++La-len，e)}}2022/11/1034voidunion(List&L342022/11/1735順序表各種操作算法的“通式”該如何書寫？———采用抽象數(shù)據(jù)類型來表示順序表的存儲(chǔ)結(jié)構(gòu)是一維數(shù)組，如果插入的元素個(gè)數(shù)超過數(shù)組定義的長度怎么辦？———采用動(dòng)態(tài)分配的一維數(shù)組2022/11/1035順序表各種操作算法的“通式”該如何35動(dòng)態(tài)數(shù)組簡介先為順序表空間設(shè)定一個(gè)初始分配量，一旦因插入元素而空間不足時(shí)，可為順序表增加一個(gè)固定長度的空間增量。2022/11/1736#defineLIST_INIT_SIZE100//存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//存儲(chǔ)空間的分配增量Typedefstruct{ElemType*elem;//表基址(用指針*elem表示）

intlength;//表長度（表中有多少個(gè)元素）

intlistsize;//當(dāng)前分配的表尺寸（字節(jié)單位）}SqList;SqListL;注：三個(gè)分量可簡寫為：L.elemL.lengthL.listsize存儲(chǔ)結(jié)構(gòu)描述如下（見教材P22）：動(dòng)態(tài)數(shù)組簡介先為順序表空間設(shè)定一個(gè)初始分配量，一旦因插入元素362022/11/1737sizeof(x)算符的意思是：計(jì)算變量x的長度(字節(jié)數(shù))malloc(m)函數(shù)的意思是：新開一片大小為m字節(jié)的連續(xù)空間，并把該區(qū)首址作為函數(shù)值。StatusInitList_Sq(

SqList

&L)

//創(chuàng)建一個(gè)空線性表{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if(!L.elem)exit(OVERFLOW);

//分配失敗，結(jié)束程序

L.length=0;

//暫無元素放入，空表

L.listsize=LIST_INIT_SIZE;

//表尺寸=初始分配量

ReturnOK;}//InitList_Sq動(dòng)態(tài)創(chuàng)建一個(gè)空順序表的算法：2022/11/1037sizeof(x)算符的意思是：計(jì)算372022/11/1738realloc(*p,newsize)函數(shù)的意思是：新開一片大小為newsize的連續(xù)空間，并把以*p為首址的原空間數(shù)據(jù)都拷貝進(jìn)去。動(dòng)態(tài)順序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序線性表中第i個(gè)位置之前插入新的元素eif(i<1ori>L.length+1)returnERROR;//檢驗(yàn)i值的合法性if(L.length

≥

L.listsize)//若表長超過表尺寸則要增加尺寸

{newbase=(ElemType*)realloc(L.elem,(L.listsize

+

LISTINCREMENT)*sizeof(ElemType));if(newbase=NULL)exit(OVERFLOW);//分配失敗則退出并報(bào)錯(cuò)

L.elem=newbase;//重置新基址

L.listsize=

L.listsize

+LISTINCREMENT;}//增加表尺寸2022/11/1038realloc(*p,newsi382022/11/1739q=&L.elem[i-1];//q為插入位置。

for(p=L.elem[L.length-1];p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素統(tǒng)統(tǒng)后移,p為元素位置*q=e;//插入e++L.length;//增加1個(gè)數(shù)據(jù)元素，則表長+1returnOK;}//ListInsert_Sq動(dòng)態(tài)數(shù)組的核心是realloc(void*ptr,newsize)函數(shù)！2022/11/1039q=&L.elem[i-1]392022/11/1740動(dòng)態(tài)順序表的刪除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在順序表L中刪除第i個(gè)元素，用e返回其值if(i<1ori>L.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被刪除元素的位置

e=*p;//被刪除元素的值賦給e

q=L.elem+L.length-1;//q是表尾的位置

for(++p;p<=q;p++)*(p-1)=*p;//待刪元素后面的統(tǒng)統(tǒng)前移--L.length;//表長-1returnOK;}//ListDelete_Sq2022/11/1040動(dòng)態(tài)順序表的刪除算法if(i<40在順序表L中查找第一個(gè)值與e滿足compare（）的元素的位序i=1；p=L.elem2022/11/1741While（i<=L.length&&!(*compare)(*p++,e)）i++;if(i<=L.length)returnielsereturn0;在順序表L中查找第一個(gè)值與e滿足compare（）的元素的位41VoidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)

//歸并La和Lb得到新的線性表Lc2022/11/1742pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(Elemtype))；初始化if（!Lc.elem）exit(overflow);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){if(*pa<*pb)*pc++=pa++;else*pc++=pb++;}核心語句P26算法２.７VoidMergeList_Sq(SqListLa,S422022/11/1743While（pa<=pa_last）*pc++=*pa++;While(pb<=pb_last)*pc++=*pb++;}插入La/Lb剩余元素2022/11/1043While（pa<=pa_last）432022/11/1744鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.2節(jié)小結(jié)線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，方便快捷；缺點(diǎn)：在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。解決問題的思路：改用另一種線性存儲(chǔ)方式：2022/11/1044鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.2節(jié)小結(jié)線性表順序存442.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2022/11/17452.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2022/11/10452.452.3.1鏈表的表示2022/11/1746鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過指針來實(shí)現(xiàn)！讓每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置2.3.1鏈表的表示2022/11/1046鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)46例：請畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2022/11/1747該字母表在內(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)的鏈域的值指針域(鏈域)例：請畫出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2022/11/472022/11/17481）結(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ù)語：2022/11/10481）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)484）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別2022/11/1749頭指針頭結(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)。示意圖如下：4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別2022/11/1049頭492022/11/1750答：討論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ì)入鏈表長度！2022/11/1050答：討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什50（3）舉例例1：2022/11/1751一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31稱：頭指針H的值是31（3）舉例2022/11/1051一個(gè)線性表的邏輯結(jié)構(gòu)為：（512022/11/1752上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)頭結(jié)點(diǎn)不計(jì)入鏈表長度！2022/11/1052上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形52例2：2022/11/1753

線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，如下圖所示。其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,

首址=

末址=

。例2：2022/11/1053線性表具有兩種存儲(chǔ)方式532022/11/1754討論:

鏈表的數(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’qp2022/11/1054討論:鏈表的數(shù)據(jù)元素有兩個(gè)域，不再542022/11/1755設(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è)變量。2022/11/1055設(shè)p為指向鏈表的第i個(gè)元素的指針,則55sizeof(x)——計(jì)算x的長度malloc(m)—開m字節(jié)空間free(p)——?jiǎng)h除一個(gè)變量2022/11/1756問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=qsizeof(x)——計(jì)算x的長度2022/11/1056問56附2：補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法2022/11/1757②對(duì)于指向結(jié)構(gòu)類型的指針變量，可說明為：

node*p,*q;

//或用

struct

lx

*p,*q;//注：上面已經(jīng)定義了node為用戶自定義的lx類型。①類型定義和變量說明可以合寫為：typedefstruct

lx

//lx是自定義結(jié)構(gòu)類型名稱{chardata;//定義數(shù)據(jù)域的變量名及其類型

struct

lx*next;//定義指針域的變量名及其類型}node，*pointer;//node是lx結(jié)構(gòu)類型的類型替代,

*pointer是指針型的lx結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型*/附2：補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法2022/11/1057572022/11/1758單鏈表的抽象數(shù)據(jù)類型描述如下（參見教材P28）：TypedefstructLnode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域}Lnode,*LinkList;//*LinkList為Lnode類型的指針至此應(yīng)可看懂教材P22關(guān)于順序表動(dòng)態(tài)分配的存儲(chǔ)結(jié)構(gòu)。其特點(diǎn)是：用結(jié)構(gòu)類型和指針來表示順序結(jié)構(gòu)，更靈活。如何具體編程來建立和訪問鏈表？——鏈表的實(shí)現(xiàn)2022/11/1058單鏈表的抽象數(shù)據(jù)類型描述如下（參見教582.3.2鏈表的實(shí)現(xiàn)（1）單鏈表的建立和輸出（2）單鏈表的修改（3）單鏈表的插入（4）單鏈表的刪除2022/11/17592.3.2鏈表的實(shí)現(xiàn)（1）單鏈表的建立和輸出2022/59（1）單鏈表的建立和輸出例：用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線性表（a，b，c，…，z）,請寫出C語言程序。2022/11/1760實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個(gè)結(jié)點(diǎn)開辟存儲(chǔ)空間并及時(shí)賦值，后繼結(jié)點(diǎn)的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”！（1）單鏈表的建立和輸出例：用單鏈表結(jié)構(gòu)來存放26個(gè)英文字602022/11/1761#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode

*next;}node;node*p,*q,*head;//一般需要3個(gè)指針變量intn;//數(shù)據(jù)元素的個(gè)數(shù)intm=sizeof(node);/*結(jié)構(gòu)類型定義好之后，每個(gè)node類型的長度就固定了，m求一次即可*/將全局變量及函數(shù)提前說明：2022/11/1061#include<stdio.h>將612022/11/1762新手特別容易忘記！！{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è)慢慢鏈入2022/11/1062新手特別容易忘記??！{inti;622022/11/1763{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()/*字母鏈表的輸出*/2022/11/1063{p=head;討論：要統(tǒng)計(jì)鏈表中數(shù)63（2）單鏈表的修改(或讀?。┧悸罚阂薷牡趇個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p，然后才能執(zhí)行p->data=new_value。2022/11/1764修改第i個(gè)數(shù)據(jù)元素的操作函數(shù)可寫為：Status

GetElem_L(LinkListL,inti,ElemType&e){p=L->next;j=1;//帶頭結(jié)點(diǎn)的鏈表while(p&&j<i){p=p->next;++j;}if(!p

||j>i)returnERROR;p->data=e;//若是讀取則為：e=p->data;returnOK;}//

GetElem_L缺點(diǎn)：想尋找單鏈表中第i個(gè)元素，只能從頭指針開始逐一查詢（順藤摸瓜），無法隨機(jī)存取。（2）單鏈表的修改(或讀取）思路：要修改第i個(gè)數(shù)據(jù)元素，必64（3）單鏈表的插入2022/11/1765在鏈表中插入一個(gè)元素X的示意圖如下：Xsabp鏈表插入的核心語句：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next思考：Step1和2能互換么？X結(jié)點(diǎn)的生成方式：s=(node*)malloc(m);s->data=X;s->next=?bap插入X（3）單鏈表的插入2022/11/1065在鏈表中插入一個(gè)65StatusListInsert_L(LinkList&L,inti,ElemTypee){2022/11/1766p=L;j=0;While(p&&j<i-1){p=p->next,++j}//尋找第i-1個(gè)節(jié)點(diǎn)If(!p||j>i-1)returnRrror//i小于1或者大于表長s=(LinkList)malloc(sizeof(LNode));//生成新節(jié)點(diǎn)s->data=e;//插入L中s->next=p->next;p->next=s;returnOK;}核心算法StatusListInsert_L(LinkList&66（4）單鏈表的刪除2022/11/1767在鏈表中刪除某元素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（4）單鏈表的刪除2022/11/1067在鏈表中刪除某元67StatusListDelete_L(LinkList&L,inti,ElemTypee){2022/11/1768p=L;j=0;while(p->next&&j<i-1){p=p->next,++j}if(!p->next||j>i-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//尋找第i個(gè)節(jié)點(diǎn),并令p指向其前驅(qū)刪除并釋放節(jié)點(diǎn)StatusListDelete_L(LinkList&682.3.3鏈表的運(yùn)算效率分析（1）查找

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

因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為

O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是O(n)。2.3.3鏈表的運(yùn)算效率分析（1）查找2022/1692022/11/1770從表尾到表頭逆向建立單鏈表的算法VoidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶頭節(jié)點(diǎn)的單鏈線性表for(i=n;i>0;--i){}L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//建立帶頭節(jié)點(diǎn)的單鏈表p=(LinkList)malloc(sizeof(LNode));

//生成新節(jié)點(diǎn)scanf(&p->data);

//輸入元素值p->next=L->next;L->next=p;

//插入到表頭用兩種方式建立26個(gè)字母的單鏈表并顯示思考：如何正向建立鏈表2022/11/1070從表尾到表頭逆向建立單鏈表的算法Vo702022/11/1771空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一個(gè)指針空間，相當(dāng)于總共增加了n個(gè)整型變量，空間復(fù)雜度為

O(n)。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，需找到它的，其時(shí)間復(fù)雜度為。

前驅(qū)結(jié)點(diǎn)的地址/指針O(n)練習(xí)：2022/11/1071空間效率分析鏈表中每個(gè)結(jié)點(diǎn)都要增加一712022/11/1772順序表操作的典型例子教材例2-1：求兩個(gè)線性表的“并”，即：LAULB=?算法至少有兩種：①LA和LB都是無序表，則從LB中取元素逐一與LA中所有元素比較，相同則不插入LA中；②若LA和LB已經(jīng)是有序表，則“歸并”的時(shí)間效率可以大大提高。2022/11/1072順序表操作的典型例子教材例2-1：求722022/11/1773voidunion(List&La，ListLb)

{

La-len=ListLength(La);Lb-len=ListLength(Lb);

for(I=1;I<=Lb-len;I++){GetElem(Lb，I，e);if(!LocateElem(La，e，equal))ListInsert(La，++La-len，e)}

}算法時(shí)間復(fù)雜度：O（ListLength（LA）*ListLength（LB））2022/11/1073voidunion(List&L73voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)

//歸并La和Lb得到新的線性表Lc2022/11/1774pa=La.elem;pa=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(Elemtype))；If（!Lc.elem）exit(overflow);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa<=pa_last&&pb<=pb_last){If(*pa<*pb)*pc++=pa++;Else*pc++=pb++;}While（pa<=pa_last）*pc++=*pa++;While(pb<=pb_last)*pc++=*pb++;voidMergeList_Sq(SqListLa,SqL742022/11/1775算法時(shí)間復(fù)雜度：O(ListLength(LA)+ListLength(LB))2022/11/1075算法時(shí)間復(fù)雜度：O(ListLeng75應(yīng)用舉例2022/11/1776算法要求：已知：線性表A和B，分別由單鏈表La和Lb

存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列（即已經(jīng)有序）；要求：將A和B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表

Lc

存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測：合并后的C=（2,3,5,6,8,8,9,11，11）例1：兩個(gè)鏈表的歸并（教材P31例）重點(diǎn)是鏈表應(yīng)用舉例2022/11/1076算法要求：例1：兩個(gè)鏈表的歸76鏈表示意圖：2022/11/17773511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)鏈表示意圖：2022/11/10773511/\877算法設(shè)計(jì)：2022/11/1778算法主要包括搜索、比較、插入三個(gè)操作：搜索：需要設(shè)立三個(gè)指針來指向La、Lb和Lc鏈表；比較：比較La和Lb表中結(jié)點(diǎn)數(shù)據(jù)的大?。徊迦耄簩a和Lb表中數(shù)據(jù)較小的結(jié)點(diǎn)插入新鏈表Lc

。請注意鏈表的特點(diǎn)，僅改變指針便可實(shí)現(xiàn)數(shù)據(jù)的移動(dòng),即“數(shù)據(jù)不動(dòng)，指針動(dòng)”算法設(shè)計(jì)：2022/11/1078算法主要包括搜索、比較、插782022/11/1779La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當(dāng)前結(jié)點(diǎn)。歸并過程示意如下：Lc=LaPbPaPaPb2022/11/1079La35811^Lb26792022/11/1780算法實(shí)現(xiàn)：

VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈線性表La和Lb的元素按值非遞減排列。歸并為Lc后也按值非遞減排列。free(Lb);

//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L

pc->next=pa?pa:pb;

//插入非空表的剩余段while(pa&&pb)//將pa、pb結(jié)點(diǎn)按大小依次插入Lc中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next}}

pa=La->next;pb=Lb->next;Lc=pc=La；

//有頭結(jié)點(diǎn)見P31算法2.12?是條件運(yùn)算符（為真則取第1項(xiàng)，見P10條件賦值）注：Lc用的是La的頭指針時(shí)間復(fù)雜度：與算法2.7相同空間復(fù)雜度2022/11/1080算法實(shí)現(xiàn)：VoidMerg802022/11/1781思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，怎么修改？2、重復(fù)的數(shù)據(jù)元素不需要插入，怎么修改？編程訓(xùn)練建議：簡單：先建立一個(gè)整型數(shù)的單鏈表，然后統(tǒng)計(jì)單鏈表中數(shù)據(jù)元素為0的個(gè)數(shù)。稍難：先建立一個(gè)字母單鏈表并輸出到屏幕上，再試著插入一個(gè)字母（例如將I插入到L之后）。2022/11/1081思考：1、不用Lc，直接把L81思考：若某種高級(jí)語言沒有指針類型，能否實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)和運(yùn)算？如何實(shí)現(xiàn)？2022/11/1782答：能！雖然鏈表通常用動(dòng)態(tài)級(jí)聯(lián)方式存儲(chǔ)，但也可以用一片連續(xù)空間（一維數(shù)組）實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)，這種方式稱為靜態(tài)鏈表。具體實(shí)現(xiàn)方法：定義一個(gè)結(jié)構(gòu)型數(shù)組（每個(gè)元素都含有數(shù)據(jù)域和指示域），就可以完全描述鏈表，指示域就相當(dāng)于動(dòng)態(tài)鏈表中的指針。思考：若某種高級(jí)語言沒有指針類型，能否實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)和運(yùn)算？822022/11/1783動(dòng)態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)數(shù)組中每個(gè)元素都至少有兩個(gè)分量，屬于結(jié)構(gòu)型數(shù)組。常用于無指針類型的高級(jí)語言中。2022/11/1083動(dòng)態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針數(shù)據(jù)832022/11/1784

靜態(tài)單鏈表的類型定義如下：

#defineMAXSIZE1000//預(yù)分配最大的元素個(gè)數(shù)（連續(xù)空間

typedefstruct{ElemTypedata;//數(shù)據(jù)域

int

cur;//指示域

}component,SLinkList[MAXSIZE];//這是一維結(jié)構(gòu)型數(shù)組前例1：軟考題：L={23，17，47，05，31}若此分量定義為指針型，屬于動(dòng)態(tài)鏈表；若此分量定義為整型（放下標(biāo)），則屬于靜態(tài)鏈表。Z47Y31V23X17U051001191041081161122022/11/1084靜態(tài)單鏈表的類型定義如下：前例84回顧例1：2022/11/1785一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，回顧2022/11/1085一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHA852022/11/1786前例2：一線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態(tài)鏈表如何表示？——教材P32例題data0123456…1000cur說明1：假設(shè)S為SLinkList型變量，則S為一個(gè)靜態(tài)鏈表；S[0].cur則表示第1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。說明2：如果數(shù)組的第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則：S[i].data表示第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)；S[i].cur

表示第k+1個(gè)結(jié)點(diǎn)(即k的直接后繼)的位置。i頭結(jié)點(diǎn)2022/11/1086前例2：一線性表S=(ZH862022/11/1787說明3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。例如：在線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之間插入新元素LIU，可以這樣實(shí)現(xiàn)：Step1:將QIAN的指示器原內(nèi)容備份到臨時(shí)變量temp：temp=S[3].cur；Step2:將QIAN的指示器換為新元素LIU的位置：S[3].cur=7；Step3:將LIU的指示器變?yōu)楹罄^SUN的位置：S[7].cur=temp；data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi頭結(jié)點(diǎn)LIU6772022/11/1087說明3：靜態(tài)鏈表的插入與刪除操作與普87循環(huán)鏈表(circularlinkedlist)循環(huán)鏈表是表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使鏈表構(gòu)成環(huán)狀特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next=NULL循環(huán)鏈表p或p->next=H2022/11/1788hh空表循環(huán)鏈表(circularlinkedlist)202288雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點(diǎn)結(jié)點(diǎn)定義2022/11/1789typedefstructnode{Elemtypeelement;structnode*prior,*next;}DulNode,*DulinkList;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;雙向鏈表（doublelinkedlist）2022/1892022/11/1790bcaP指針域的變化：

后繼方向：ai-1的后繼由ai(指針p)變?yōu)閍i+1(指針p->next);;

前驅(qū)方向：ai+1的前驅(qū)由ai(指針p)變?yōu)閍i-1(指針p->prior

);

刪除算法評(píng)價(jià)：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;p->prior->next=p->nextp->next->prior=

p->prior;2022/11/1090bcaP指針域的變化：刪除算法評(píng)價(jià)：902022/11/1791StatusListDelete_Dul(DuLinkList&L,inti,ElemType){//刪除帶頭節(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置元素e//i的合法值為1<i<表長+1If(!p=GetElemP_Dul(L,i))returnERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}//ListDelete_Dul核心語句2022/11/1091StatusListDelete_912022/11/1792①ai-1的后繼從ai(指針是p)變?yōu)閤（指針是s):②ai的前驅(qū)從ai-1(指針是p->prior)變?yōu)閤(指針是s);

算法評(píng)價(jià)：T(n)=O(1)xSbaP插入注意：要修改雙向指針！指針域的變化：s->next=p;

p->prior->next=s;

s->prior=

p->prior

;

p->prior

=s;2022/11/1092①ai-1的后繼從ai(指針922022/11/1793StatusListInset_Dul(DuLinkList&L,inti,ElemType){//在帶頭節(jié)點(diǎn)的雙鏈循環(huán)線性表L中第i個(gè)位置之前插入元素e//i的合法值為1<i<表長+1If(!p=GetElemP_Dul(L,i))