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

第二章線性表

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

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

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

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

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

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

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

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

}核心語(yǔ)句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例2順序表的操作用數(shù)組V來(lái)存放26個(gè)英文字母組成的線性表（a，b，c，…，z），寫(xiě)出在順序結(jié)構(gòu)上生成和顯示該表的C語(yǔ)言程序。voidmain(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é)果：abcdefghijklmnopqrstuvwxyz例2順序表的操作2.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í)間效率是O(1)2)插入在線性表的第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]在線性表的第i個(gè)位置前插入一個(gè)元素for(j=n;j>=i;j--)a[j+1]=a[j];

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

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

T(n)=O

(移動(dòng)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.時(shí)間效率分析:2.2.3順序表的運(yùn)算效率分析思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)才合理。討論1插入元素：若在長(zhǎng)度為n的線性表的第i(i>=1)位前插入一個(gè)元素，則向后移動(dòng)元素的次數(shù)f(n)為: f(n)=n–i+1推導(dǎo)：假定在每個(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

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

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

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

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

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

intlistsize;//當(dāng)前分配的表尺寸（字節(jié)單位）}SqList;注：三個(gè)分量可簡(jiǎn)寫(xiě)為：L.elemL.lengthL.listsize存儲(chǔ)結(jié)構(gòu)描述如下（見(jiàn)教材P22）：為什么不用數(shù)組sizeof(x)算符的意思是：計(jì)算變量x的長(zhǎng)度(字節(jié)數(shù))malloc(m)函數(shù)的意思是：新開(kāi)一片大小為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;

//暫無(wú)元素放入，空表

L.listsize=LIST_INIT_SIZE;

//表尺寸=初始分配量

ReturnOK;}//InitList_Sq動(dòng)態(tài)創(chuàng)建一個(gè)空順序表的算法realloc(*p,newsize)函數(shù)的意思是：新開(kāi)一片大小為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)//若表長(zhǎng)超過(guò)表尺寸則要增加尺寸

{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;}//增加表尺寸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個(gè)數(shù)據(jù)元素，則表長(zhǎng)+1returnOK;}//ListInsert_Sq動(dòng)態(tài)數(shù)組的核心是realloc(void*ptr,newsize)函數(shù)！for(intk=L.length-1;k>=i-1;k--)L.elem[k+1]=L.elem[k];動(dòng)態(tài)順序表的插入算法(續(xù)）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;//被刪除元素的值賦給eq=L.elem+L.length-1;//q是表尾的位置

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

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

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

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

一個(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稱：頭指針H的值是31（3）舉例例1：上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無(wú)頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)頭結(jié)點(diǎn)不計(jì)入鏈表長(zhǎng)度！

線性表具有兩種存儲(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：討論:

鏈表的數(shù)據(jù)元素有兩個(gè)域，不再是簡(jiǎn)單數(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’qp設(shè)p為指向鏈表的第i個(gè)元素的指針,則第i個(gè)元素的數(shù)據(jù)域?qū)憺?/p>

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

。練習(xí)：p->dataai的值p->nextai+1的地址附1：介紹C的三個(gè)有用的庫(kù)函數(shù)/算符（都在<stdlib.h>中）：sizeof(x)——計(jì)算變量x的長(zhǎng)度（字節(jié)數(shù)）；malloc(m)—開(kāi)辟m字節(jié)長(zhǎng)度的地址空間，并返回這段空間的首地址；free(p)——釋放指針p所指變量的存儲(chǔ)空間，即徹底刪除一個(gè)變量。sizeof(x)——計(jì)算x的長(zhǎng)度malloc(m)—開(kāi)m字節(jié)空間free(p)——?jiǎng)h除一個(gè)變量問(wèn)1：自定義結(jié)構(gòu)類型變量node的長(zhǎng)度m是多少？問(wèn)2：結(jié)構(gòu)變量node的首地址(指針p）是多少？問(wèn)3：怎樣刪除結(jié)構(gòu)變量node？*nextdatanode，長(zhǎng)度為m字節(jié)pm＝sizeof(node)

//單位是字節(jié)p＝(node*)malloc(m)free(p)//只能借助node的指針刪除！P->data=‘a(chǎn)’;p->next=q練習(xí)：①類型定義和變量說(shuō)明可以合寫(xiě)為：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表示法②對(duì)于指向結(jié)構(gòu)類型的指針變量，可說(shuō)明為：

node

*p,*q;

//或用

struct

LinkList

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

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

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

Lnode是何意？A3：在“縮寫(xiě)”

Lnode還沒(méi)出現(xiàn)之前，只能用原始的structLnode來(lái)進(jìn)行變量說(shuō)明。此處說(shuō)明了指針?lè)至康臄?shù)據(jù)類型是struct

Lnode。typedefstructstudent

{charname;intage;}student,*pointer;教材問(wèn)題討論：2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析2.3.2鏈表的實(shí)現(xiàn)（1）單鏈表的建立和輸出（2）單鏈表的修改（3）單鏈表的插入（4）單鏈表的刪除（1）單鏈表的建立和輸出例：用單鏈表結(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)的地址要提前送給前面的指針。先挖“坑”,后種“蘿卜”！#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è)變量的長(zhǎng)度就固定了，m求一次即可*/將全局變量及函數(shù)提前說(shuō)明：新手特別容易忘記??！{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è)慢慢鏈入如何建立帶頭結(jié)點(diǎn)的單鏈表（1）創(chuàng)建單鏈表{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()/*字母鏈表的輸出*/（2）單鏈表元素值顯示（2）單鏈表的修改(或讀取）思路：要修改第i個(gè)數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針p，然后才能執(zhí)行p->data=new_value。修改第i個(gè)數(shù)據(jù)元素的操作函數(shù)可寫(xiě)為：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è)元素，只能從頭指針開(kāi)始逐一查詢（順藤摸瓜），無(wú)法隨機(jī)存取。在鏈表中插入一個(gè)元素X的示意圖如下：Xsabp鏈表插入的核心語(yǔ)句：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next思考：Step1和Step2能互換么？X結(jié)點(diǎn)的生成方式：s=(node*)malloc(m);s->data=X;s->next=?bap插入X（3）單鏈表的插入（重點(diǎn)）在鏈表中刪除某元素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（4）單鏈表的刪除2.3.3鏈表的運(yùn)算效率分析（1）查找

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

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

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

O(1)。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因?yàn)橐獜念^查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度將是O(n)?？臻g效率分析鏈表中每個(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í)：2.4應(yīng)用舉例算法要求：已知：線性表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è)：合并后的C=（2,3,5,6,8,8,9,11，11）例1：兩個(gè)鏈表的歸并（教材P31例）重點(diǎn)是鏈表鏈表示意圖：3511/\8

La2611/\8

Lb92365

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

5

8

11^

Lb2

6

8

11^9

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

data;

structLnode

*next;}*linkList;typedefstruct{

//鏈表類型

linkhead,

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

int

len;

//鏈表中元素個(gè)數(shù)（長(zhǎng)度）}

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

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

VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈線性表La和Lb的元素按值非遞減排列。歸并為L(zhǎng)c后也按值非遞減排列。free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_Lpc->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)見(jiàn)P31算法2.12?是條件運(yùn)算符（為真則取第1項(xiàng)，見(jiàn)P10條件賦值）注：Lc用的是La的頭指針?biāo)伎迹ㄅe一反三）編程實(shí)踐題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：一元多項(xiàng)式的計(jì)算

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

em-1am-2

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

em-1

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

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

極端情況是表A和表B沒(méi)有一項(xiàng)指數(shù)相同，比

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

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

個(gè)新結(jié)點(diǎn)

合計(jì)時(shí)間復(fù)雜度為

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

(參見(jiàn)教材P39–43)

后續(xù)內(nèi)容3.用抽象數(shù)據(jù)類型如何定義一元多項(xiàng)式？（參見(jiàn)P40）ADTPolynomial{數(shù)據(jù)對(duì)象：D={ai|ai∈TermSet,i=1,2,…,m,m≥0TermSet中的每個(gè)元素包含一個(gè)表示系數(shù)的實(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}基本操作：線性鏈表若干公共基本操作的定義見(jiàn)教材P37（此處略）為本例定義的更多基本操作有：CreatPolyn(&P,m)操作結(jié)果：輸入m項(xiàng)的系數(shù)和指數(shù)，建立一元多項(xiàng)式P。//建表DestroyPolyn(&P)//銷毀也是P的一種變化初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：銷毀一元多項(xiàng)式P。//釋放表PrintPolyn(P)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：打印輸出一元多項(xiàng)式P。//輸出一元多項(xiàng)式表PolynLength(P)//項(xiàng)數(shù)=表長(zhǎng)初始條件：一元多項(xiàng)式P已存在。操作結(jié)果：返回一元多項(xiàng)式P中的項(xiàng)數(shù)。//求表長(zhǎng)，用函數(shù)值返回為本例定義的更多基本操作有：AddPolyn(&Pa,&Pb)

初始條件：一元多項(xiàng)式Pa和Pb已存在。

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

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

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

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

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

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

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

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

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

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

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

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

p=head->next;//有頭結(jié)點(diǎn)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é)點(diǎn)q=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為首替換法的核心語(yǔ)句：插入法的核心語(yǔ)句：ai-1aiqai+1prheada1heada2pq請(qǐng)上機(jī)驗(yàn)證并分析效率！1、試用C或類C語(yǔ)言編寫(xiě)一個(gè)高效算法，將一不帶頭結(jié)點(diǎn)單鏈表就地逆置。

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

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

2.5幾種特殊鏈表靜態(tài)鏈表雙向鏈表循環(huán)鏈表問(wèn)題：若某種高級(jí)語(yǔ)言沒(méi)有指針類型，能否實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)和運(yùn)算？如何實(shí)現(xiàn)？答：能！雖然鏈表通常用動(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)鏈表中的指針。指示域也常稱為“游標(biāo)”2.5.1靜態(tài)鏈表動(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ù)組。常用于無(wú)指針類型的高級(jí)語(yǔ)言中。2.5.1靜態(tài)鏈表

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

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

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

intcur;//指示域

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

為一個(gè)靜態(tài)鏈表；S[0].cur則表示第1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。說(shuō)明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)說(shuō)明3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。例如：在線性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之間插入新元素LIU，可以這樣實(shí)現(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é)點(diǎn)LIU677靜態(tài)鏈表各種操作編程靜態(tài)鏈表的各種操作建立、查找、插入、刪除、修改等操作例6：在雙向鏈表中如何實(shí)現(xiàn)插入和刪除運(yùn)算？單鏈表中查找只能從前往后，而不能從后往前查。為了查找方便，提高查找速度，可以在結(jié)點(diǎn)上增加一個(gè)指針域，用來(lái)存結(jié)點(diǎn)的直接前驅(qū)，這樣的鏈表，稱為雙向鏈表。其結(jié)點(diǎn)的結(jié)構(gòu)為：priordatanexttypedefstructDuLNode{ElemTypedata;//數(shù)據(jù)域

stru