上堂課要點(diǎn)回顧數(shù)據(jù)結(jié)構(gòu)課程——涉及數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用D_S=(D,S)表示。數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算

算法效率指標(biāo)——時(shí)間效率和空間效率1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)2近3周

上課

內(nèi)容第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組和廣義表

線性結(jié)構(gòu)

若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼?？杀硎緸椋海╝1,a2,……,an）線性結(jié)構(gòu)的定義：（邏輯、存儲(chǔ)和運(yùn)算）3第二章線性表

學(xué)習(xí)指南【學(xué)習(xí)目標(biāo)】

1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。

2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。

3.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。

4.結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解。4【重點(diǎn)和難點(diǎn)】

鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針p和結(jié)點(diǎn)*p之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等?！局R(shí)點(diǎn)】

線性表、順序表、鏈表【學(xué)習(xí)指南】

本章建議完成的算法設(shè)計(jì)題為：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38第二章線性表

學(xué)習(xí)指南(續(xù))5線性結(jié)構(gòu)的特點(diǎn)：①只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；

②除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性結(jié)構(gòu)表達(dá)式：（a1,a2,……,an）線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最典型、最常用的是------線性表簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的見(jiàn)第2章6第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.3.1線性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表

2.4一元多項(xiàng)式的表示及相加7線性表：由一組數(shù)據(jù)組成，線性表或者是一個(gè)空表，或者可以寫(xiě)成（a1,a2,…ai,…an）,其中ai是取自某個(gè)集合S的元素。當(dāng)1<i<n時(shí)，數(shù)據(jù)元素ai-1稱為數(shù)據(jù)元素ai的直接前驅(qū)，而稱ai+1為ai的直接后繼。線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為該線性表的長(zhǎng)度。2.1

線性表的類型定義8（a1,a2,…ai-1，ai,ai＋1

，…,an）1.線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長(zhǎng)空表線性終點(diǎn)9形式化定義：Linearlist=(D,R)其中：D0為某個(gè)數(shù)據(jù)對(duì)象的集合N為線性表長(zhǎng)度10線性表的主要操作初始化求長(zhǎng)度取元素定位插入刪除11對(duì)線性表可進(jìn)行如下基本運(yùn)算：

InitList(&L)：構(gòu)造一個(gè)空的線性表L。ListLength(&L)：返回L數(shù)據(jù)元素的個(gè)數(shù)。GetElem(L,i,&e)：用e返回L中第i個(gè)數(shù)據(jù)元素的值。ListInsert(&L,i,e)：在L中第i個(gè)位置前插入新的數(shù)據(jù)元素e，L的長(zhǎng)度加1。ListDelete(&L,i,&e)：刪去L中第i個(gè)元素，用e返回其值，L的長(zhǎng)度減1。

PriorElem(L,cur_e,&pre_e)：用pre_e返回?cái)?shù)據(jù)元素cur_e的前驅(qū)，如果存在的話。

NextElem(L,cur_e,&next_e)：用next_e返回?cái)?shù)據(jù)元素cur_e的后繼，如果存在的話。

LocateElem(L,e,compare())：返回L中第一個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。0表示這種元素不存在。12例1分析26個(gè)英文字母組成的英文表

（A,B,C,D,……,Z）學(xué)號(hào)姓名性別年齡班級(jí)2001011810205于春梅女182001級(jí)電信016班2001011810260何仕鵬男182001級(jí)電信017班2001011810284王爽女182001級(jí)通信011班2001011810360王亞武男182001級(jí)通信012班：：：：：例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性13例3、學(xué)生健康情況登記表如下：姓名學(xué)號(hào)性別年齡健康情況王小林790631男18

健康陳紅790632女20

一般劉建平790633男21

健康張立立790634男17

神經(jīng)衰弱……..……..…….…….…….14例4、一副撲克的點(diǎn)數(shù)（2，3，4，…，J，Q，K，A）

15從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼a2；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨an-1；其余的內(nèi)部結(jié)點(diǎn)ai(2≦i≦n-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。

16

線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。抽象數(shù)據(jù)類型的定義為：P1917

算法2.1例2-1利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A=A∪B。

voidunion(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)}//for}18算法2.2p21例2-2巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問(wèn)題的算法如下：

19voidMergeList(listla，listlb，list&lc)

InitList(lc);I=j=1;k=0;La-len=ListLength(la);Lb-len=ListLength(lb);while((I<=la-len)&&(j<=lb-len)){

GetElem(la，I，ai);getelem(lb，j，bj);

if(ai<=bj){listinsert(lc，++k，ai);++I;}

else{listinsert(lc，++k，bj);++j;}}//while20

while(I<=la-len){

getelem((la，I++，ai);listinsert(lc，++k，ai);}//while處理la表

while(j<=lb-len){

getelem((lb，j++，bj);listinsert(lc，++k，bi);}//while處理lb表

}//MergeList21練：判斷下列敘述的正誤：1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。2.線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計(jì)算機(jī)。3.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。4.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的。一維向量是線性表，但二維或N維數(shù)組不是。“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。√×√√××222.2線性表的順序表示和實(shí)現(xiàn)2.2.1順序表的表示2.2.2順序表的實(shí)現(xiàn)2.2.3順序表的運(yùn)算效率分析本節(jié)小結(jié)作業(yè)232.2.1順序表的表示用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過(guò)數(shù)組V[n]來(lái)實(shí)現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。順序存儲(chǔ)定義：順序存儲(chǔ)方法：簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰24線性表順序存儲(chǔ)特點(diǎn)：1.

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

若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。計(jì)算方法是（參見(jiàn)存儲(chǔ)結(jié)構(gòu)示意圖）：設(shè)首元素a1的存放地址為L(zhǎng)OC(a1)（稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai)=LOC(a1)+L*（i-1）

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

注意：C語(yǔ)言中的數(shù)組的下標(biāo)從0開(kāi)始，即：V[n]的有效范圍是V[0]～V[n-1]25線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖a1a2……aiai+1……an

地址內(nèi)容元素在表中的位序1i2n空閑區(qū)i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L26一個(gè)一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素Ｍ[０]的第一個(gè)字節(jié)的地址是９８，則Ｍ[３]的第一個(gè)字節(jié)的地址是

113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址計(jì)算通式為：LOC(ai)=LOC(a1)+L*（i-1）27用數(shù)組V來(lái)存放26個(gè)英文字母組成的線性表（a，b，c，…，z），寫(xiě)出在順序結(jié)構(gòu)上生成和顯示該表的C語(yǔ)言程序。

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

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

}核心語(yǔ)句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例228voidmain(void)

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

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

/*字母線性表的顯示，即讀表操作*/{

inti;for(i=0;i<=n-1;i++)printf("%c",V[i]);printf("\n");}執(zhí)行結(jié)果：abcdefghijklmnopqrstuvwxyz292.2.2順序表的實(shí)現(xiàn)（或操作）回憶：數(shù)據(jù)結(jié)構(gòu)基本運(yùn)算操作有：修改、插入、刪除、查找、排序1)修改通過(guò)數(shù)組的下標(biāo)便可訪問(wèn)某個(gè)特定元素并修改之。核心語(yǔ)句:

V[i]=x;顯然，順序表修改操作的時(shí)間效率是T(n)=O(1)302)插入在線性表的第i個(gè)位置前插入一個(gè)元素實(shí)現(xiàn)步驟：將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素寫(xiě)到第i個(gè)位置；表長(zhǎng)加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//表長(zhǎng)加1核心語(yǔ)句：31由于C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。用結(jié)構(gòu)類型來(lái)定義順序表類型。

#defineListSize100

typedef

int

DataType;

typedef

struc{

DataType

data[ListSize];

intlength;}Sqlist;32線性表的插入運(yùn)算是指在表的第I(1≦i≦n+1)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表

(a1，…ai-1，ai，…，an)

變成長(zhǎng)度為n+1的線性表

(a1，…ai-1，x，ai，…，an)33算法2.3P23VoidInsertList(Sqlist*L，DataTypex，intI){

intj;if(I<1||I>l.length+1){printf(“Positionerror”);returnERROR};34

if(L.length>=ListSize){

printf(“overflow”);

exit(overflow);}

for(j=L.length-1;j>=I-1;j--)L.data[j+1]=L.data[j];L.data[I-1]=x;

L.length++;}35在線性表的第i個(gè)位置前插入一個(gè)元素的示意圖如下：121321242830427712132124252830427712345678123456789插入2536實(shí)現(xiàn)步驟：將第i至第n位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減1。注意：事先需要判斷，刪除位置i是否合法?應(yīng)當(dāng)有1≤i≤n或i=[1,n]3)刪除刪除線性表的第i個(gè)位置上的元素for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一個(gè)位置//表長(zhǎng)減1核心語(yǔ)句：37123456789121321242528304277123456781213212428304277刪除順序表中某個(gè)指定的元素的示意圖如下：38順序表插入和刪除的完整程序可自行用C語(yǔ)言編制。自行上機(jī)練習(xí)題：設(shè)有線性表LA＝（3,5,8,11）和

LB=（2,6,8,9,11,15,20）；①若LA和LB分別表示兩個(gè)集合A和B，求新集合

A＝AUB（‘并’操作，相同元素不保留）；注：此題來(lái)源于教材的例2.1和例2.2，見(jiàn)P20按規(guī)律插入插入到尾部預(yù)測(cè)輸出：LA=（3,5,8,11,2,6,9,15,20）②將LA與LB表歸并，要求仍有序（相同元素要保留）預(yù)測(cè)輸出：LC=（2,3,5,6,8,8,9,11,11,15,20）392.2.3順序表的運(yùn)算效率分析算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語(yǔ)句頻度）T(n)=O(移動(dòng)元素次數(shù))移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；若要考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)，該如何計(jì)算？討論1：若在長(zhǎng)度為n的線性表的第i位前插入一元素，則向后移動(dòng)元素的次數(shù)f(n)為: f(n)=n–i+1時(shí)間效率分析:40討論2：若在長(zhǎng)度為n的線性表上刪除第i位元素，向前移動(dòng)元素的次數(shù)f(n)為：

f(n)=思考：若刪除尾結(jié)點(diǎn)，則根本無(wú)需移動(dòng)（特別快）；若刪除首結(jié)點(diǎn)，則表中元素全部要前移（特別慢）；若要考慮在各種位置刪除（共n+1種可能）的平均移動(dòng)次數(shù)，該如何計(jì)算？n–i可以證明：插入、刪除操作平均需要移動(dòng)一半元素(n/2)插入、刪除算法的平均時(shí)間復(fù)雜度為：O(n)顯然，順序表的空間復(fù)雜度S(n)=O(1)（沒(méi)有占用輔助空間）41證明：假定在每個(gè)元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：將所有位置的執(zhí)行時(shí)間相加，然后取平均。若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移n次；若在a1后面插入，要后移n-1個(gè)元素，后移次數(shù)為n-1;……若在an-1后面插入，要后移1個(gè)元素；若在尾結(jié)點(diǎn)an之后插入，則后移0個(gè)元素；所有可能的元素移動(dòng)次數(shù)合計(jì)：0+1+…+n=n(n+1)/2

所以平均移動(dòng)次數(shù)為：n(n+1)/2÷（n+1）＝n/2≈O(n)

共有多少種插入形式?——連頭帶尾有n+1種同理可證：順序表刪除一元素的時(shí)間效率為:T（n)=(n-1)/2≈O(n)

42教材P25算法2.5也是對(duì)執(zhí)行效率的推導(dǎo)：假定在表中任意位置插入、刪除元素都是等概率的，插入概率p(i)=1/(n+1)，刪除概率q(i)=1/n，則：插入操作時(shí)間效率（平均移動(dòng)次數(shù)）

刪除操作時(shí)間效率（平均移動(dòng)次數(shù)）

43本節(jié)小結(jié)線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素；缺點(diǎn)：在插入，刪除某一元素時(shí)，需要移動(dòng)大量元素。為克服這一缺點(diǎn)，我們引入另一種存儲(chǔ)形式：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)見(jiàn)2.3節(jié)442.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析本節(jié)小結(jié)作業(yè)452.3.1鏈表的表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲(chǔ)器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過(guò)指針來(lái)實(shí)現(xiàn)注意：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：

數(shù)據(jù)域和指針域46例1畫(huà)出26個(gè)英文字母表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。該字母表在內(nèi)存的鏈?zhǔn)酱娣攀疽鈭D如下：

解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）aheadb/\z……各結(jié)點(diǎn)由兩個(gè)域組成：數(shù)據(jù)域：存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)；指針域：存儲(chǔ)直接后繼或者直接前驅(qū)的存儲(chǔ)位置。指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：47與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)：1、結(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……h(huán)ead循環(huán)鏈表示意圖：484、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

示意圖如下：頭指針頭結(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)志和表長(zhǎng)等信息;首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。492.3.1線性鏈表鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：50

其中：data域是數(shù)據(jù)域，用來(lái)存放結(jié)點(diǎn)的值。next是指針域（亦稱鏈域），用來(lái)存放結(jié)點(diǎn)的直接后繼的地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。

顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開(kāi)始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨磏ull（圖示中也可用^表示)。例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)datalink51單鏈表示意圖如下：

……110……130135……160頭指針head165170……200205…………………h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………16552headbatcateatmat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。例如：若頭指針名是head，則把鏈表稱為表head。用C語(yǔ)言描述的單鏈表如下：Typedefchardatatype;

Typedef

structnode{

datatypedata;

structnode*next;}listnode;53

typedef

listnode*linklist;

listnode*p;

linklisthead;注意區(qū)分指針變量和結(jié)點(diǎn)變量這兩個(gè)不同的概念。P為動(dòng)態(tài)變量，它是通過(guò)標(biāo)準(zhǔn)函數(shù)生成的，即

p=(listnode*)malloc(sizeof(listnode));函數(shù)malloc分配了一個(gè)類型為listnode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點(diǎn)變量不再需要了，又可通過(guò)標(biāo)準(zhǔn)函數(shù)

free(p)釋放所指的結(jié)點(diǎn)變量空間。54指針變量P和（其值為結(jié)點(diǎn)地址）和結(jié)點(diǎn)變量*P之間的關(guān)系。551.鏈?zhǔn)酱鎯?chǔ)特點(diǎn)：邏輯上相鄰，物理上不一定相鄰鏈表存放示意圖如下：a1heada2/\an……討論1

：每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和

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

指示。其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域(鏈域)562.與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語(yǔ)1）結(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)鏈表。4）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)以教材P27圖2.5和圖2.6內(nèi)容為例說(shuō)明。57何謂頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)？頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。

單鏈表可由一個(gè)頭指針唯一確定。頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息;首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。

頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a158一個(gè)線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲(chǔ)結(jié)構(gòu)用單鏈表表示如下，請(qǐng)問(wèn)其頭指針的值是多少？存儲(chǔ)地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針，因此關(guān)鍵是要尋找第一個(gè)結(jié)點(diǎn)的地址。7ZHAOH31∴頭指針的值是3159上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無(wú)頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)60答：討論1.在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？討論2.如何表示空表？頭結(jié)點(diǎn)即在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表、非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理，編程更方便。答：無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。^頭指針^頭指針頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)61討論3.頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可存放線性表長(zhǎng)度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長(zhǎng)度值。答：討論4.鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(shù)據(jù)類型，編程時(shí)該如何表示？因每個(gè)結(jié)點(diǎn)至少有兩個(gè)分量，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書(shū)寫(xiě)表達(dá)？

——補(bǔ)充C語(yǔ)言內(nèi)容

頭結(jié)點(diǎn)的數(shù)據(jù)域H623.補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型及其C語(yǔ)言表示法①類型定義和變量說(shuō)明可以合寫(xiě)為：struct

mytest

{

//mytest是自定義結(jié)構(gòu)類型名稱char

data;//定義數(shù)據(jù)域的變量名及其類型struct

mytest

*next;//定義指針域的變量名及其類型}test，*head