數(shù)據(jù)結(jié)構(gòu)第二章線性表

第二章線性表

第1章緒論第2章線性表第3章棧和隊列第4章串第5章數(shù)組和廣義表第6章樹和二叉樹第7章圖第9章查找第10章排序目錄數(shù)據(jù)結(jié)構(gòu)課程的起點什么是線性結(jié)構(gòu)？線性結(jié)構(gòu)的定義若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼?！杀硎緸椋海╝1,a2,……,an）簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是特點①只有一個首結(jié)點和尾結(jié)點；特點②除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。一對一(1:1)線性結(jié)構(gòu)的邏輯類型線性結(jié)構(gòu)包括：線性表、堆棧、隊列、字符串、數(shù)組等，其中最典型、最常用的是------線性表第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實現(xiàn)（重點）2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)（重點）2.4應(yīng)用舉例（a1,a2,…ai-1，ai,ai＋1

，…,an）線性表的定義：用數(shù)據(jù)元素的有限序列表示n=0時稱為數(shù)據(jù)元素線性起點ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長。n≥0空表線性終點2.1線性表的邏輯結(jié)構(gòu)

（A,B,C,D,……,Z）分析：數(shù)據(jù)元素都是同類型（字母），元素間關(guān)系是線性的。例1分析26個英文字母組成的英文表是什么結(jié)構(gòu)。例2分析學(xué)生情況登記表是什么結(jié)構(gòu)。學(xué)號姓名性別年齡班級012003010622陳建武男192003級電信0301班012003010704趙玉鳳女182003級電信0302班012003010813王澤男192003級電信0303班012003010906薛荃男192003級電信0304班012003011018王春男192003級電信0305班：：：

：：分析：數(shù)據(jù)元素都是同類型（記錄），元素之間關(guān)系是線性的。注意：同一線性表中的元素必定具有相同特性（數(shù)據(jù)類型）！1、“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)都相等?！潦侵父髟鼐哂邢嗤臄?shù)據(jù)類型試判斷下列敘述的正誤2、線性結(jié)構(gòu)就是線性表×線性表的物理結(jié)構(gòu)類型

線性表的物理結(jié)構(gòu)類型

順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)在確定線性表物理結(jié)構(gòu)的基礎(chǔ)上，可以進(jìn)行相關(guān)的操作和編程，用函數(shù)實現(xiàn)。物理結(jié)構(gòu)與邏輯結(jié)構(gòu)區(qū)別邏輯結(jié)構(gòu)是抽象的，獨立于計算機(jī)的，無法進(jìn)行具體的計算；物理結(jié)構(gòu)是具體的，包括順序結(jié)構(gòu)與鏈?zhǔn)浇Y(jié)構(gòu)，決定了數(shù)據(jù)對象如何實現(xiàn)具體的運(yùn)算。

例如數(shù)組與單鏈表就是兩種不同的物理結(jié)構(gòu)，在插入與刪除操作時具體實現(xiàn)不一樣2.2線性表的順序表示和實現(xiàn)2.2.1順序表的表示2.2.2順序表的實現(xiàn)2.2.3順序表的運(yùn)算效率分析2.2.1順序表的表示用一組地址連續(xù)的存儲單元依次存儲線性表的元素。把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。線性表的順序表示又稱為順序存儲結(jié)構(gòu)或順序映像。順序存儲方法：特點：邏輯上相鄰的元素，物理上也相鄰可以利用數(shù)組V[n]來實現(xiàn)注意：在C語言中數(shù)組的下標(biāo)是從0開始，即：

V[n]的有效范圍是從V[0]～V[n-1]順序存儲定義：1.邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組a[n]的下標(biāo)）。線性表順序存儲特點設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+L*（i-1）對上述公式的解釋如圖所示線性表順序存儲特點a1a2……aiai+1……an

地址內(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）線性表的順序存儲結(jié)構(gòu)示意圖設(shè)有一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個數(shù)組元素用相鄰的4個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素Ｍ[０]的第一個字節(jié)的地址是９８，則Ｍ[３]的第一個字節(jié)的地址是多少？110但此題要注意下標(biāo)起點略有不同：LOC(M[3])=98+4×(4-1)=110解：已知地址計算通式為：LOC(ai)=LOC(a1)+L*（i-1）例1

charV[30];voidbuild()/*字母線性表的生成，即建表操作*/{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個英文字母組成的線性表（a，b，c，…，z），寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。voidmain(void)

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

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

/*字母線性表的顯示，即讀表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",v[i]);printf("\n");}執(zhí)行結(jié)果：abcdefghijklmnopqrstuvwxyz例2順序表的操作2.2.2順序表的實現(xiàn)（或操作）數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：修改、插入、刪除、查找、排序1)修改

通過數(shù)組的下標(biāo)便可訪問某個特定元素并修改之。核心語句:V[i]=x;顯然，順序表修改操作的時間效率是O(1)2)插入在線性表的第i個位置前插入一個元素實現(xiàn)步驟：將第n至第i

位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。注意：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?

應(yīng)當(dāng)有1≤i≤n+1或i=[1,n+1]在線性表的第i個位置前插入一個元素for(j=n;j>=i;j--)a[j+1]=a[j];

a[i]=x;n++;//元素后移一個位置//插入x//表長加1核心語句2)插入在線性表的第i個位置前插入一個元素的示意圖如下：121321242830427712132124252830427712345678123456789插入25實現(xiàn)步驟：將第i+1

至第n位的元素向前移動一個位置；表長減1。注意：事先需要判斷，刪除位置i是否合法?應(yīng)當(dāng)有1≤i≤n或i=[1,n]刪除線性表的第i個位置上的元素for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一個位置//表長減1核心語句：3)刪除123456789121321242528304277123456781213212428304277刪除順序表中某個指定的元素的示意圖如下：2.2.3順序表的運(yùn)算效率分析算法時間主要耗費(fèi)在移動元素的操作上，因此計算時間復(fù)雜度的基本操作（最深層語句頻度）

T(n)=O

(移動元素次數(shù))而移動元素的個數(shù)取決于插入或刪除元素的位置.時間效率分析:2.2.3順序表的運(yùn)算效率分析思考：若插入在尾結(jié)點之后，則根本無需移動（特別快）；若插入在首結(jié)點之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)才合理。討論1插入元素：若在長度為n的線性表的第i(i>=1)位前插入一個元素，則向后移動元素的次數(shù)f(n)為: f(n)=n–i+1推導(dǎo)：假定在每個元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來計算平均執(zhí)行時間：將所有位置的執(zhí)行時間相加，然后取平均。若在首結(jié)點前插入，需要移動的元素最多，后移n次；若在a1后面插入，要后移n-1個元素，后移次數(shù)為n-1;……若在an-1后面插入，要后移1個元素；若在尾結(jié)點an之后插入，則后移0個元素；所有可能的元素移動次數(shù)合計：0+1+‥+n=n(n+1)/2

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

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

2.2.3順序表的運(yùn)算效率分析想一想：順序表插入、刪除算法的平均空間復(fù)雜度為多少？插入效率：刪除效率：教材P25算法2.5也是對執(zhí)行效率的推導(dǎo)：因為沒有占用輔助空間！含義：對于順序表，插入、刪除操作平均需要移動一半元素(n/2)O(1)即插入、刪除算法的平均時間復(fù)雜度為O(n)2.2.3順序表的運(yùn)算效率分析課堂討論：1、順序表的“宏觀”算法該如何書寫？———采用抽象數(shù)據(jù)類型來表示2、順序表的存儲結(jié)構(gòu)是一維數(shù)組，如果插入的元素個數(shù)超過數(shù)組定義的長度怎么辦？———采用動態(tài)分配的一維數(shù)組1、抽象數(shù)據(jù)類型定義初始化、撤銷、清空、判空；求表長、表頭、表尾、前趨、后繼；讀元素、查找（含定位）、遍歷；插入、刪除線性表的定義（見教材P19）ADTList

{數(shù)據(jù)對象：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線性表的基本操作如何表示？（見教材P19）InitList(&L);//建空表，初始化DestoryList(&L);//撤銷表，釋放內(nèi)存intLengthList(L);//求表中元素個數(shù)，即表長POSITIONLocateElem(L,ElemTypee，compare());PriorElem(L,cur_e,&pre_e);//求當(dāng)前元素e的前驅(qū)NextElem(L,cur_e,&next_e);//求當(dāng)前元素e的后繼ListInsertBefore(&L,i,e);//把e插入到第i個元素之前ListDelete(&L,i,&e);//刪除第i個元素并“看”此元素ListTraverse(L,Visit());//“看”表中全部元素（遍歷）初始化、撤銷、清空、判空；求表長、表頭、表尾、前趨、后繼；讀元素、查找（含定位）、遍歷；插入、刪除順序表操作的典型例子教材例2-1：求兩個線性表的“并”，即：LAULB=?算法至少有兩種：①LA和LB都是無序表，則從LB中取元素逐一與LA中所有元素比較，相同則不插入LA；②若LA和LB已經(jīng)是有序表，則“歸并”的時間效率可以大大提高。2、動態(tài)數(shù)組先為順序表空間設(shè)定一個初始分配量，一旦因插入元素而空間不足時，可為順序表增加一個固定長度的空間增量。#defineLIST_INIT_SIZE100//存儲空間的初始分配量#defineLISTINCREMENT10//存儲空間的分配增量typedefstruct{ElemType*elem;//表基址(用指針*elem表示）

intlength;//表長度（表中有多少個元素）

intlistsize;//當(dāng)前分配的表尺寸（字節(jié)單位）}SqList;注：三個分量可簡寫為：L.elemL.lengthL.listsize存儲結(jié)構(gòu)描述如下（見教材P22）：為什么不用數(shù)組sizeof(x)算符的意思是：計算變量x的長度(字節(jié)數(shù))malloc(m)函數(shù)的意思是：新開一片大小為m字節(jié)的連續(xù)空間，并把該區(qū)首址作為函數(shù)值。StatusInitList_Sq(SqList&L)

//創(chuàng)建一個空線性表{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動態(tài)創(chuàng)建一個空順序表的算法realloc(*p,newsize)函數(shù)的意思是：新開一片大小為newsize的連續(xù)空間，并把以*p為首址的原空間數(shù)據(jù)都拷貝進(jìn)去。動態(tài)順序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序線性表中第i個位置之前插入新的元素eif(i<1ori>L.length+1)returnERROR;//檢驗i值的合法性if(L.length≥L.listsize)//若表長超過表尺寸則要增加尺寸

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

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

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

L.listsize=L.listsize+LISTINCREMENT;}//增加表尺寸q=&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個數(shù)據(jù)元素，則表長+1returnOK;}//ListInsert_Sq動態(tài)數(shù)組的核心是realloc(void*ptr,newsize)函數(shù)！for(intk=L.length-1;k>=i-1;k--)L.elem[k+1]=L.elem[k];動態(tài)順序表的插入算法(續(xù)）StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在順序表L中刪除第i個元素，用e返回其值if(i<1ori>L.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被刪除元素的位置

e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//q是表尾的位置

for(++p;p<=q;p++)*(p-1)=*p;//待刪元素后面的統(tǒng)統(tǒng)前移--L.length;//表長-1returnOK;}//ListDelete_Sq動態(tài)順序表的刪除算法鏈?zhǔn)酱鎯Y(jié)構(gòu)2.2本節(jié)小結(jié)線性表順序存儲結(jié)構(gòu)特點：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰；優(yōu)點：可以隨機(jī)存取表中任一元素，方便快捷；缺點：在插入或刪除某一元素時，需要移動大量元素。解決問題的思路：改用另一種線性存儲方式：第2章線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.4應(yīng)用舉例2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.3.1鏈表的表示2.3.2鏈表的實現(xiàn)2.3.3鏈表的運(yùn)算效率分析鏈?zhǔn)酱鎯Y(jié)構(gòu)特點：其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實現(xiàn)？通過指針來實現(xiàn)！2.3.1鏈表的表示讓每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和指針域指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼或者直接前驅(qū)的存儲位置設(shè)計思想：犧牲空間效率換取時間效率2.3.1鏈表的表示例：請畫出26個英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。解：該字母表的邏輯結(jié)構(gòu)為：（a,b,…,y,z）該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：鏈表存放示意圖如下：a1heada2/\an……指針域(鏈域)鏈表存放示意圖如下：討論1

：每個存儲結(jié)點都包含兩部分：數(shù)據(jù)域和

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

指示。其直接前驅(qū)結(jié)點的鏈域的值指針域(鏈域)1）結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：

n個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚?，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。(2)與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表（但未必是雙向鏈表）；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……循環(huán)鏈表示意圖：head(2)與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語4）頭指針、頭結(jié)點和首元結(jié)點的區(qū)別頭指針頭結(jié)點首元結(jié)點a1heada2…infoan^頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點、或為首元結(jié)點）的指針；通常頭指針也是一個類似于結(jié)點的結(jié)構(gòu)體頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計入表長度。首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點。示意圖如下：討論1.在鏈表中設(shè)置頭結(jié)點有什么好處？頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域可以為空，也可存放表長度等附加信息，其作用是為了對鏈表進(jìn)行操作時，編程更方便。答：答：討論2.如何表示空表？無頭結(jié)點時，當(dāng)頭指針的值為空時表示空表；^頭指針無頭結(jié)點^頭指針頭結(jié)點有頭結(jié)點有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空時表示空表。頭結(jié)點不計入鏈表長度！

一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？存儲地址數(shù)據(jù)域指針域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。7ZHAOH31稱：頭指針H的值是31（3）舉例例1：上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點②有頭結(jié)點頭結(jié)點不計入鏈表長度！

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

Y=

Z=

,

首址=

末址=

。例2：討論:

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

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

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

。練習(xí)：p->dataai的值p->nextai+1的地址附1：介紹C的三個有用的庫函數(shù)/算符（都在<stdlib.h>中）：sizeof(x)——計算變量x的長度（字節(jié)數(shù)）；malloc(m)—開辟m字節(jié)長度的地址空間，并返回這段空間的首地址；free(p)——釋放指針p所指變量的存儲空間，即徹底刪除一個變量。sizeof(x)——計算x的長度malloc(m)—開m字節(jié)空間free(p)——刪除一個變量問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=q練習(xí)：①類型定義和變量說明可以合寫為：typedefstruct

LinkList

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

struct

LinkList*next;//定義指針域的變量名及其類型}node，*pointer;//node是LinkList結(jié)構(gòu)類型的類型替代,*pointer是指針型的LinkList結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型*/附2：補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法②對于指向結(jié)構(gòu)類型的指針變量，可說明為：

node

*p,*q;

//或用

struct

LinkList

*p,*q;pointerp,q;//注：上面已經(jīng)定義了node為用戶自定義的LinkList類型。附2：補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法單鏈表的抽象數(shù)據(jù)類型描述如下（參見教材P28）：typedefstructLnode

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

structLnode*next;//指針域}Lnode,*LinkList;//*LinkList為Lnode類型的指針至此應(yīng)可看懂教材P22關(guān)于順序表動態(tài)分配的存儲結(jié)構(gòu)。其特點是：用結(jié)構(gòu)類型和指針來表示順序結(jié)構(gòu)，更靈活。如何具體編程來建立和訪問鏈表？——鏈表的實現(xiàn)typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;教材P28對于線性表的單鏈表存儲結(jié)構(gòu)描述:教材問題討論：Q1：第一行的Lnode與最后一行的Lnode是不是一回事？A1：不是。前者Lnode是結(jié)構(gòu)名，后者Lnode是對整個struct類型的一種“縮寫”，是一種“新定義名”，它只是對現(xiàn)有類型名的補(bǔ)充，而不是取代。請注意：typedef不可能創(chuàng)造任何新的數(shù)據(jù)類型，而僅僅是在原有的數(shù)據(jù)類型中命名一個新名字，其目的是使你的程序更易閱讀和移植。typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;Q2：那為何兩處要同名(Lnode和Lnode）？太不嚴(yán)謹(jǐn)了吧？A2：同名是為了表述起來方便。例如，若結(jié)構(gòu)名為student，其新定義名縮寫也最好寫成student，因為描述的對象相同，方便閱讀和理解。Q3：結(jié)構(gòu)體中間的那個struct

Lnode是何意？A3：在“縮寫”

Lnode還沒出現(xiàn)之前，只能用原始的structLnode來進(jìn)行變量說明。此處說明了指針分量的數(shù)據(jù)類型是struct

Lnode。typedefstructstudent

{charname;intage;}student,*pointer;教材問題討論：2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.3.1鏈表的表示2.3.2鏈表的實現(xiàn)2.3.3鏈表的運(yùn)算效率分析2.3.2鏈表的實現(xiàn)（1）單鏈表的建立和輸出（2）單鏈表的修改（3）單鏈表的插入（4）單鏈表的刪除（1）單鏈表的建立和輸出例：用單鏈表結(jié)構(gòu)來存放26個英文字母組成的線性表（a，b，c，…，z）,請寫出C語言程序。算法實現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結(jié)點開辟存儲空間并及時賦值，后繼結(jié)點的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”！#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}node;node*p,*q,*head;//一般需要3個指針變量intn;//數(shù)據(jù)元素的個數(shù)intm=sizeof(node);/*結(jié)構(gòu)類型定義好之后，每個變量的長度就固定了，m求一次即可*/將全局變量及函數(shù)提前說明：新手特別容易忘記！！{inti;head=(node*)malloc(m);//m=sizeof(node)前面已求出p=head;for(i=1;i<26;i++)//因尾結(jié)點要特殊處理，故i≠26{p->data=i+‘a(chǎn)’-1;//第一個結(jié)點值為字符ap->next=(node*)malloc(m);//為后繼結(jié)點“挖坑”！p=p->next；}//讓指針變量P指向后一個結(jié)點p->data=i+‘a(chǎn)’-1;//最后一個元素要單獨處理p->next=NULL;}//單鏈表尾結(jié)點的指針域要置空！voidbuild()//字母鏈表的生成。要一個個慢慢鏈入如何建立帶頭結(jié)點的單鏈表（1）創(chuàng)建單鏈表{p=head;while(p)//當(dāng)指針不空時循環(huán)，僅限于無頭結(jié)點的情況

{printf("%c",p->data);

p=p->next;

//讓指針不斷“順藤摸瓜”

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

sum++;sum=0;voiddisplay()/*字母鏈表的輸出*/（2）單鏈表元素值顯示（2）單鏈表的修改(或讀取）思路：要修改第i個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點的指針p，然后才能執(zhí)行p->data=new_value。修改第i個數(shù)據(jù)元素的操作函數(shù)可寫為：Status

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

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

GetElem_L缺點：想尋找單鏈表中第i個元素，只能從頭指針開始逐一查詢（順藤摸瓜），無法隨機(jī)存取。在鏈表中插入一個元素X的示意圖如下：Xsabp鏈表插入的核心語句：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next思考：Step1和Step2能互換么？X結(jié)點的生成方式：s=(node*)malloc(m);s->data=X;s->next=?bap插入X（3）單鏈表的插入（重點）在鏈表中刪除某元素b的示意圖如下：cabp刪除動作的核心語句（要借助輔助指針變量q）：q=p->next;//首先保存b的指針，靠它才能找到c；p->next=q->next;//將a、c兩結(jié)點相連，淘汰b結(jié)點；free(q)；//徹底釋放b結(jié)點空間p->next思考：省略free(q)語句行不行？(p->next)->next××q（4）單鏈表的刪除2.3.3鏈表的運(yùn)算效率分析（1）查找

因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為

O(n)。時間效率分析（2）插入和刪除

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

O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度將是O(n)?？臻g效率分析鏈表中每個結(jié)點都要增加一個指針空間，相當(dāng)于總共增加了n個整型變量，空間復(fù)雜度為

O(n)。在n個結(jié)點的單鏈表中要刪除已知結(jié)點*P，需找到它的，其時間復(fù)雜度為前驅(qū)結(jié)點的地址/指針O(n)練習(xí)：2.4應(yīng)用舉例算法要求：已知：線性表A和B，分別由單鏈表La和Lb存儲，其中數(shù)據(jù)元素按值非遞減有序排列（即已經(jīng)有序）；要求：將A和B歸并為一個新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表Lc存儲。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測：合并后的C=（2,3,5,6,8,8,9,11，11）例1：兩個鏈表的歸并（教材P31例）重點是鏈表鏈表示意圖：3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點算法設(shè)計算法主要包括搜索、比較、插入三個操作：搜索：需要設(shè)立三個指針來指向La、Lb和Lc鏈表；比較：比較La和Lb表中結(jié)點數(shù)據(jù)的大??；插入：將La和Lb表中數(shù)據(jù)較小的結(jié)點插入新鏈表Lc。請注意鏈表的特點，僅改變指針便可實現(xiàn)數(shù)據(jù)的移動,即“數(shù)據(jù)不動，指針動”La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，Pc指向新鏈表當(dāng)前結(jié)點。歸并過程示意如下：Lc=LaPbPaPaPb算法設(shè)計typedefstructLnode{//結(jié)點類型Elemtype

data;

structLnode

*next;}*linkList;typedefstruct{

//鏈表類型

linkhead,

tail;//分別指向鏈表頭尾結(jié)點

int

len;

//鏈表中元素個數(shù)（長度）}

link;一個帶頭結(jié)點的線性鏈表類型定義如下：

（用類C語言，見P37）：結(jié)點的結(jié)構(gòu)表結(jié)構(gòu)算法實現(xiàn)：

VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈線性表La和Lb的元素按值非遞減排列。歸并為Lc后也按值非遞減排列。free(Lb);//釋放Lb的頭結(jié)點}//MergeList_Lpc->next=pa?pa:pb;//插入非空表的剩余段while(pa&&pb)//將pa、pb結(jié)點按大小依次插入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é)點見P31算法2.12?是條件運(yùn)算符（為真則取第1項，見P10條件賦值）注：Lc用的是La的頭指針?biāo)伎迹ㄅe一反三）編程實踐題1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，怎么修改？2、重復(fù)的數(shù)據(jù)元素不需要插入，怎么修改？{elseif(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;pb=pb->next;}例2：一元多項式的計算

(參見教材P39–43)討論：一元多項式的數(shù)學(xué)通式？用抽象數(shù)據(jù)類型如何描述它的定義？用C語言如何描述它的定義？如何編程實現(xiàn)兩個一元多項式相加？但當(dāng)多項式的次數(shù)很高且零系數(shù)項很多時，更適于用鏈表存儲。1.一元多項式的數(shù)學(xué)通式？機(jī)內(nèi)存儲方式？一般用順序存儲——a0a1a2…am-2am-1鏈?zhǔn)酱鎯m-1

em-1am-2

em-2…a0e0^或0.0-1…am-1

em-1

^a0e0通常設(shè)計兩個數(shù)據(jù)域（系數(shù)項和指數(shù)項）和一個指針域頭結(jié)點只存系數(shù)項（但零系數(shù)項也不能遺漏）coefexponlinkP2000(x)=1+3x1000+5x20002.如何編程實現(xiàn)兩個一元多項式相加？3142810a^814－310106b^例：運(yùn)算規(guī)則：兩多項式中指數(shù)相同的項對應(yīng)系數(shù)相加，若和不為0,則構(gòu)成多項式c(=a+b)中的一項；a和b中所有指數(shù)不相同的項均應(yīng)拷貝到c中。鏈表a：鏈表b：實現(xiàn)思路：依次比較Pa和Pb所指結(jié)點中的指數(shù)項，依Pa->expon=、<或>Pb->expon等情況，再決定是將兩系數(shù)域的數(shù)值相加（并判其和是否為0），還是將較高指數(shù)項的結(jié)點插入到新表c中。3142810^aPa814-310106^bPb1114-3102810^cPc106+運(yùn)算效率分析：(1) 系數(shù)相加 0加法次數(shù)min(m,n)

其中m和n分別表示表A和表B的結(jié)點數(shù)。(2) 指數(shù)比較

極端情況是表A和表B沒有一項指數(shù)相同，比

較次數(shù)最多為m+n-1(3) 新結(jié)點的創(chuàng)建

極端情況是產(chǎn)生m+n

個新結(jié)點

合計時間復(fù)雜度為

O(m+n)續(xù)例2：一元多項式的計算

(參見教材P39–43)

后續(xù)內(nèi)容3.用抽象數(shù)據(jù)類型如何定義一元多項式？（參見P40）ADTPolynomial{數(shù)據(jù)對象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0TermSet中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,

且ai-1中的指數(shù)值<ai中的指數(shù)值,i=1,2,…,n}基本操作：線性鏈表若干公共基本操作的定義見教材P37（此處略）為本例定義的更多基本操作有：CreatPolyn(&P,m)操作結(jié)果：輸入m項的系數(shù)和指數(shù)，建立一元多項式P。//建表DestroyPolyn(&P)//銷毀也是P的一種變化初始條件：一元多項式P已存在。操作結(jié)果：銷毀一元多項式P。//釋放表PrintPolyn(P)初始條件：一元多項式P已存在。操作結(jié)果：打印輸出一元多項式P。//輸出一元多項式表PolynLength(P)//項數(shù)=表長初始條件：一元多項式P已存在。操作結(jié)果：返回一元多項式P中的項數(shù)。//求表長，用函數(shù)值返回為本例定義的更多基本操作有：AddPolyn(&Pa,&Pb)

初始條件：一元多項式Pa和Pb已存在。

操作結(jié)果：完成多項式相加運(yùn)算，即：Pa＝Pa＋Pb，

并銷毀一元多項式Pb。//兩表相加SubtractPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相減運(yùn)算，即：Pa＝Pa－Pb，并銷毀一元多項式Pb。//兩表相減}ADTPolynomialMultiplyPolyn(&Pa,&Pb)初始條件：一元多項式Pa和Pb已存在。操作結(jié)果：完成多項式相乘運(yùn)算，即：Pa＝Pa×Pb，并銷毀一元多項式Pb。//兩表相乘為本例定義的更多基本操作有：4.用C語言如何具體描述它的定義？用標(biāo)準(zhǔn)C語言：

typedefstructpoly_node{intcoef;intexpon;poly_pointerlink;};typedefstructpoly_node*poly_pointer;poly_pointera,b,c;coefexponlink5.具體編程（用C語言）利用建表操作CreatPolyn(&P,m)分別建立鏈表a和鏈表b；詳細(xì)內(nèi)容參見教材P42下部描述。2.利用加操作AddPolyn(&Pa,&Pb)對鏈表a和鏈表b進(jìn)行相加；詳細(xì)內(nèi)容參見教材P43描述。編程時請注意，在前面定義中已規(guī)定：初始條件：一元多項式Pa和Pb已存在。

操作結(jié)果：完成多項式相加運(yùn)算，即：Pa＝Pa＋Pb，

并銷毀一元多項式Pb。從教材程序中可“猜”出，例中的鏈表是按指數(shù)項升序排列的。ha=GetHead(Pa);hb=GetHead(Pb);//取二表頭指針(指向頭結(jié)點）qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);//指向二表首元/下一結(jié)點while(qa&&qb){//若二表均未到末尾，

a=GetCurElem(qa);//則比較兩結(jié)點的數(shù)據(jù)域（注意a,b含有

b=GetCurElem(qb);//兩個數(shù)據(jù)分量）switch(*cmp(a,b)){//

cmp(a,b)是用戶自定義函數(shù)，見P42倒9行case-1://依a的指數(shù)值>=<b的指數(shù)值，分別返回-1,0,+1ha=qa;qa=NextPos(Pa,ha);break;

//a的指數(shù)值小則鏈接，說明是升序case0://若a的指數(shù)值等于b，則系數(shù)相加，但和為0時不要sum=a.coef+b.coef;If(sum!=0.0){SetCurElem(qa,sum);ha=qa;}教材第43頁的算法2.23——多項式加法

else{DelFirst(ha,qa);FreeNode(qa);}//若系數(shù)為0，則兩結(jié)點都刪DelFirst(hb,qb);FreeNode(qb);//a<=b時都會刪除b結(jié)點。qa=NextPos(Pa,ha);qb=NextPos(Pb,hb);break;case1://若a的指數(shù)值>b，應(yīng)先鏈接（前插）b（保持升序）DelFirst(hb,qb);InsFirst(ha,qb);//此二動作不要調(diào)換qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;//a表結(jié)點大，后移}//switch}//while//直到查完a表If(!ListEmpty(Pb))Append(Pa,qb);//若b表還不空，則剩表全部//鏈接到a表中；b表空時無需動作，因為此時a表已求和完畢。FreeNode(hb);//無論什么結(jié)局，最終b表都是要廢掉的。}}//AddPolyn教材第43頁的算法2.23——多項式加法分析：要想讓an指向an-1,……a2指向a1，一般有兩種算法：①替換法：掃描a1……an,

將每個ai的指針域指向ai-1。實際上是鏈棧的概念^a1heada2思路：后繼變前驅(qū)思路：頭部變尾部②插入法：掃描a1……an,

將每個ai插入到鏈表首部即可。例3：試用C或類C語言編寫一個高效算法，將一循環(huán)單鏈表就地逆置。

p=head->next;//有頭結(jié)點if(p!=head){q=p->next;p->next=head;p=q};//處理a1while(p!=head)//循環(huán)單鏈表{q=p->next//保存原后繼

p->next=head->next;head->next=p;p=q;}//準(zhǔn)備處理下一結(jié)點q=head;p=head->next;//有頭結(jié)點while(p!=head)//循環(huán)單鏈表{r=p->next;p->next=q;//前驅(qū)變后繼

q=p;p=r;}//準(zhǔn)備處理下一結(jié)點head->next=q;//以an為首替換法的核心語句：插入法的核心語句：ai-1aiqai+1prheada1heada2pq請上機(jī)驗證并分析效率！1、試用C或類C語言編寫一個高效算法，將一不帶頭結(jié)點單鏈表就地逆置。

舉一反三2、試用C或類C語言編寫一個高效算法，將一帶頭結(jié)點單鏈表就地逆置。

3、試用C或類C語言編寫一個高效算法，將一不帶頭結(jié)點循環(huán)單鏈表就地逆置。

2.5幾種特殊鏈表靜態(tài)鏈表雙向鏈表循環(huán)鏈表問題：若某種高級語言沒有指針類型，能否實現(xiàn)鏈?zhǔn)酱鎯瓦\(yùn)算？如何實現(xiàn)？答：能！雖然鏈表通常用動態(tài)級聯(lián)方式存儲，但也可以用一片連續(xù)空間（一維數(shù)組）實現(xiàn)鏈?zhǔn)酱鎯?，這種方式稱為靜態(tài)鏈表。具體實現(xiàn)方法：定義一個結(jié)構(gòu)型數(shù)組（每個元素都含有數(shù)據(jù)域和指示域），就可以完全描述鏈表，指示域就相當(dāng)于動態(tài)鏈表中的指針。指示域也常稱為“游標(biāo)”2.5.1靜態(tài)鏈表動態(tài)鏈表樣式：靜態(tài)鏈表樣式：指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)指示數(shù)據(jù)數(shù)組中每個元素都至少有兩個分量，屬于結(jié)構(gòu)型數(shù)組。常用于無指針類型的高級語言中。2.5.1靜態(tài)鏈表

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

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

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

intcur;//指示域

}component,SLinkList[MAXSIZE];//這是一維結(jié)構(gòu)型數(shù)組前例1：軟考題：L={23，17，47，05，31}若此分量定義為指針型，屬于動態(tài)鏈表（題目中是指針）；若此分量定義為整型（通常存放下標(biāo)），則屬于靜態(tài)鏈表。Z47Y31V23X17U05100119104108116112前例2：一線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態(tài)鏈表如何表示？——教材P32例題data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…1000cur說明1：假設(shè)S為SLinkList型變量，則S[MAXSIZE]

為一個靜態(tài)鏈表；S[0].cur則表示第1個結(jié)點在數(shù)組中的位置。說明2：如果數(shù)組的第i個分量表示鏈表的第k個結(jié)點，則：S[i].data表示第k個結(jié)點的數(shù)據(jù)；S[i].cur

表示第k+1個結(jié)點(即k的直接后繼)的位置。i頭結(jié)點說明3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。例如：在線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之間插入新元素LIU，可以這樣實現(xiàn)：S[7].cur=S[3].cur；Step2:將QIAN的游標(biāo)換為新元素LIU的下標(biāo)：S[3].cur=7Step1:將QIAN的游標(biāo)值存入LIU的游標(biāo)中：data……2SUN4ZHOU0WU6QIAN5LI3ZHAO101234561000curi頭結(jié)點LIU677靜態(tài)鏈表各種操作編程靜態(tài)鏈表的各種操作建立、查找、插入、刪除、修改等操作例6：在雙向鏈表中如何實現(xiàn)插入和刪除運(yùn)算？單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點上增加一個指針域，用來存結(jié)點的直接前驅(qū)，這樣的鏈表，稱為雙向鏈表。其結(jié)點的結(jié)構(gòu)為：priordatanexttypedefstructDuLNode{ElemTypedata;//數(shù)據(jù)域

stru