第二章線性表A

1第2章線性表2.1線性表的基本概念2.2線性表的順序存儲(chǔ)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.4一元多項(xiàng)式的表示及相加2

從本章開(kāi)始到第四章討論的線性表、棧、隊(duì)列和串的邏輯結(jié)構(gòu)都屬于線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，元素之間存在一個(gè)對(duì)一個(gè)的相互關(guān)系，其邏輯特征為：在數(shù)據(jù)元素的非空有限集中：（1）存在唯一的一個(gè)被稱(chēng)為“起始”的數(shù)據(jù)元素。（2）存在唯一的一個(gè)被稱(chēng)為“終端”的元素。

2.1線性表的類(lèi)型定義 3

（3）除起始元素外，其它每個(gè)元素有且僅有一個(gè)直接前趨。（4）除終端元素之外，其它每個(gè)元素有且僅有一個(gè)直接后繼。本章的基本內(nèi)容：線性表的邏輯結(jié)構(gòu)定義和各種存儲(chǔ)結(jié)構(gòu)、描述方法及其建立在這兩種存儲(chǔ)結(jié)構(gòu)上的運(yùn)算實(shí)現(xiàn)。42.1.1線性表的邏輯結(jié)構(gòu)

在實(shí)際應(yīng)用中，線性表是最常用而且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。線性表定義：線性表是由n個(gè)數(shù)據(jù)元素組成的有限序列，其中，n即數(shù)據(jù)元素的個(gè)數(shù)，定義為線性表的長(zhǎng)度，當(dāng)n為零時(shí)稱(chēng)為空表，一般將n>0時(shí)的線性表記為：

其中，是第一個(gè)數(shù)據(jù)元素，又稱(chēng)為起始結(jié)點(diǎn)，是最后一個(gè)數(shù)據(jù)元素，又稱(chēng)為終端結(jié)點(diǎn)。5

當(dāng)i=1，2，…，n-1時(shí)，有且僅有一個(gè)直接后繼；當(dāng)i=2，3，…n時(shí)，有且僅有一個(gè)直接前趨。注意這里（1≤i≤n）僅僅是一個(gè)抽象的符號(hào)，其具體含義，在不同的情況下各不相同，它可以是一個(gè)數(shù)，一條記錄或一個(gè)符號(hào)，甚至是更復(fù)雜的信息。例如，英文字母表(A，B，……Z)是一個(gè)線性表，職工工資表等。線性表的結(jié)點(diǎn)之間的邏輯關(guān)系符合線性結(jié)構(gòu)的邏輯特征，是一種線性結(jié)構(gòu)。

6線性表的特點(diǎn)：同一線性表中的元素必定具有相同特性；相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系；線性表中元素個(gè)數(shù)n(n>=0)為線性表的長(zhǎng)度,當(dāng)n=0時(shí)稱(chēng)為空表；在非空線性表中，每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置；線性表的長(zhǎng)度可以根據(jù)需要增長(zhǎng)或縮短。7抽象數(shù)據(jù)類(lèi)型線性表的定義格式ADTlist{

數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：基本操作：以下是一些常用操作，以函數(shù)方式出現(xiàn)

……}ADTlistElemSet是某個(gè)確定的、將由用戶自行定義的、含某個(gè)關(guān)系運(yùn)算的數(shù)據(jù)對(duì)象8

常見(jiàn)的線性表的基本運(yùn)算：（1）置空表ClearList(L)：將線性表L置成空表。（2）求長(zhǎng)度ListLenght(L)：求給定線性表L中數(shù)據(jù)元素的個(gè)數(shù)。（3）取元素GetElem(L,i,&e)：用e返回線性表L中的第i個(gè)數(shù)據(jù)元素。（4）插入ListInsert(&L,i,e)：在線性表L中第i個(gè)位置之前插入新的元素e,L的長(zhǎng)度加1。

2.1.2線性表的運(yùn)算9

（5）刪除ListDelete(&L,i,&e)：刪除L中第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。（6）判定ListEmpty(L)：若L為空表，則返回true,否則返回false。利用基本運(yùn)算可以實(shí)現(xiàn)線性表的其它復(fù)雜運(yùn)算。需要指出的是，這里給出的只是定義在邏輯結(jié)構(gòu)上的抽象運(yùn)算，即只關(guān)心這些運(yùn)算是“做什么”的，至于“怎樣實(shí)現(xiàn)”則依賴(lài)于所選定的存儲(chǔ)結(jié)構(gòu)。102.2線性表的順序表示和實(shí)現(xiàn)

順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，即按順序存儲(chǔ)方式構(gòu)成的線性表的存儲(chǔ)結(jié)構(gòu)。其存儲(chǔ)方式是：線性表的第一個(gè)元素存放在個(gè)一片連續(xù)的存儲(chǔ)空間開(kāi)始位置處，第二個(gè)元素緊跟著存放在第一元素之后…，以此類(lèi)推。利用順序表來(lái)存儲(chǔ)線性表，可借助數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的物理位置相鄰特性來(lái)表示線性表中數(shù)據(jù)元素之間的線性邏輯關(guān)系。線性表中第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置計(jì)算公式為：

L是每個(gè)元素占用的存儲(chǔ)單元

11

這樣，一旦起始地址LOC（a1）（圖2.2中設(shè)為b）和一個(gè)數(shù)據(jù)元素占用的存儲(chǔ)單元的大?。↙值）確定下來(lái)，就可求出任一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，顯然，這種表便于進(jìn)行隨機(jī)訪問(wèn)，因此，順序表是一種隨機(jī)存取的結(jié)構(gòu)。1213

在具體實(shí)現(xiàn)時(shí)，可利用高級(jí)程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組即向量來(lái)為線性表的順序存儲(chǔ)開(kāi)辟存儲(chǔ)空間，存儲(chǔ)空間大小應(yīng)大于等于線性表長(zhǎng)度，用一個(gè)整型變量來(lái)表示線性表的長(zhǎng)度，從而可將順序表描述為：

#defineList_INIT100typedefintelemtype；/*elemtype表示元素類(lèi)型，此處設(shè)為int*/typedefstruct{elemtypevec[List_INIT]；

intlenght；

}sequenlist；

14

在上面描述中，順序表是一個(gè)結(jié)構(gòu)體類(lèi)型。其中，vec成員（又稱(chēng)為數(shù)據(jù)域）指線性表數(shù)據(jù)元素所占用的存儲(chǔ)空間，而lenght成員（又稱(chēng)為長(zhǎng)度域）則用于存儲(chǔ)線性表長(zhǎng)度，它表示線性表最后一個(gè)元素在向量中的位置，elemtype則為線性表中數(shù)據(jù)元素類(lèi)型。15

本節(jié)討論在定義線性表順序存儲(chǔ)結(jié)構(gòu)之后，如何在這種結(jié)構(gòu)上實(shí)現(xiàn)有關(guān)數(shù)據(jù)運(yùn)算。下面重點(diǎn)討論線性表的順序表的建立、數(shù)據(jù)元素的插入和刪除運(yùn)算。

2.2.2順序表上的基本運(yùn)算163.順序表的常用算法算法1順序表的建立(P23算法2.3)輸入n個(gè)整數(shù)，產(chǎn)生一個(gè)存儲(chǔ)這些整數(shù)的順序表A的函數(shù)如下：voidcreate(A,n)vectorA;intn;{inti;for(i=1;i<=n;i++)cin>>A[i];/*scanf(“%d”,A[i]);*/}typedefintvector[m]定義了一個(gè)新的類(lèi)型，順序表中n小于或等于mmain(){vectorB;intj,n;cin>>n;create(B,n);for(j=1;j<=n;j++)cout<<B[j];/*Printf(“%d”,B[j]);*/}172．插入運(yùn)算線性表的插入運(yùn)算是指在表的第i個(gè)元素之前插入一個(gè)新的數(shù)據(jù)元素，插入的結(jié)果使得線性表的長(zhǎng)度由n變?yōu)閚+1，線性表的數(shù)據(jù)元素間的邏輯關(guān)系發(fā)生了變化，使得物理存儲(chǔ)順序也發(fā)生相應(yīng)的變化。插入過(guò)程如圖2.3所示。18121321242830427712345678插入25121321242528304277123456789插入后(a)(b)19算法2順序表的插入（如圖2.3）121321242830427712345678插入25

在一個(gè)有n個(gè)元素的順序表A中的第i個(gè)元素之前插入一個(gè)元素x的函數(shù)如下：

voidinsert(A,n,x)vectorA;intn,x;{inti,j;scanf(“%d”,&i);/*確定插入位置*/if(i<1||i>n)print(“i值錯(cuò)誤！\n”);else{for(j=n;j>=i;j--)A[j+1]=A[j];A[i]=x;n++;}}20intInsert(ElemtypeList[],int*num,inti,Elemtypex){/*在順序表List[]中，*num為表尾元素下標(biāo)位置，在第i個(gè)元素前插入數(shù)據(jù)元素x，若成功，返回TRUE，否則返回FALSE。*/intj;if(i<0||i>*num+1){printf(“Error!”); /*插入位置出錯(cuò)*/returnFALSE;}if(*num>=MAXNUM-1){printf(“overflow!”);returnFALSE;} /*表已滿*/for(j=*num;j>=i;j--)List[j+1]=List[j]; /*數(shù)據(jù)元素后移*/List[i]=x; /*插入x*/(*num)++; /*長(zhǎng)度加1*/returnTRUE;}

P24【算法2.4順序表的插入】21

在本算法中是從最后一個(gè)元素開(kāi)始后移，直到第i個(gè)元素為止。該算法時(shí)間主要花費(fèi)在for循環(huán)語(yǔ)句上，執(zhí)行的次數(shù)為n-i+1。當(dāng)i=1時(shí)，全部元素均參加移動(dòng)，共需要移動(dòng)n次；當(dāng)i=n+1時(shí)，不需移動(dòng)元素。算法在最壞情況下，時(shí)間復(fù)雜度為O(n)，最好情況下時(shí)間復(fù)雜度為O(1)。顯然，元素移動(dòng)的次數(shù)直接影響了算法執(zhí)行時(shí)間，平均移動(dòng)次數(shù)。

假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，且為等概率，則平均移動(dòng)次數(shù)的期望值為：

其中，當(dāng)1≤i≤n+1時(shí)，p1=p2=……=pn+1=

可見(jiàn)，在順序存儲(chǔ)的線性表中插入一個(gè)元素，約平均移動(dòng)線性表中一半的元素，顯然，當(dāng)n較大時(shí)，算法效率較低，算法的平均時(shí)間復(fù)雜度為O(n)。

22

在本算法中是從最后一個(gè)元素開(kāi)始后移，直到第i個(gè)元素為止。該算法時(shí)間主要花費(fèi)在for循環(huán)語(yǔ)句上，執(zhí)行的次數(shù)為n-i+1。當(dāng)i=1時(shí)，全部元素均參加移動(dòng)，共需要移動(dòng)n次；當(dāng)i=n+1時(shí)，不需移動(dòng)元素。算法在最壞情況下，時(shí)間復(fù)雜度為O(n)，最好情況下時(shí)間復(fù)雜度為O(1)。顯然，元素移動(dòng)的次數(shù)直接影響了算法執(zhí)行時(shí)間，平均移動(dòng)次數(shù)。

假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，且為等概率，則平均移動(dòng)次數(shù)的期望值為：

其中，當(dāng)1≤i≤n+1時(shí)，p1=p2=……=pn+1=

23

可見(jiàn)，在順序存儲(chǔ)的線性表中插入一個(gè)元素，約平均移動(dòng)線性表中一半的元素，顯然，當(dāng)n較大時(shí)，算法效率較低，算法的平均時(shí)間復(fù)雜度為O(n)。

243．刪除運(yùn)算

刪除運(yùn)算是指將線性表中的第i個(gè)元素刪除，使線性表的長(zhǎng)度由n變成n-1，由：

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

變成為：(a1，a2，…，ai-1，ai+1，…，an)

其中，1≤i≤n。線性表進(jìn)行刪除元素后，仍是一個(gè)線性表。刪除過(guò)程如圖2.4所示。25算法3順序表的刪除（如圖2.4）具體算法如下：

voiddelete(L，i)sequenlist*L；

inti；

{intj；

if((i<1)||(i>(*L).len+1))printf(“deletefail！\n”)；/*刪除位置不正確*/else{*y=(*L).vec[i-1]；/*y為一外部變量，用于接收被刪除的元素*/for(j=i；j<=(*L).len；j++)(*L).vec[j-1]=(*L).vec[j]；/*元素前移*/(*L).Len--；/*修改表長(zhǎng)*/}}/*delete*/26

與插入算法相似，要?jiǎng)h除一個(gè)元素需向前移動(dòng)元素，刪除第i個(gè)元素時(shí)，將第i+1，i+2，…，n個(gè)元素依次前移，其移動(dòng)次數(shù)為n-i，假設(shè)刪除線性表中的任一位置上元素的概率相等（等于1/n），則刪除運(yùn)算所需的移動(dòng)元素的平均移動(dòng)次數(shù)如下所示。

由此可見(jiàn)，對(duì)線性表刪除一個(gè)元素時(shí)，約需有一半的元素參加移動(dòng)。

27

顯然，該算法的時(shí)間復(fù)雜度為Ｏ(n)。通過(guò)以上討論可以發(fā)現(xiàn)，當(dāng)表長(zhǎng)較大時(shí)，對(duì)順序存儲(chǔ)結(jié)構(gòu)進(jìn)行插入和刪除運(yùn)算，由于要移動(dòng)元素，運(yùn)算效率低，但這種存儲(chǔ)結(jié)構(gòu)對(duì)于隨機(jī)存取元素卻十分方便。28

例如，一個(gè)線性表中可能含有重復(fù)的元素（值相同），現(xiàn)要求刪除重復(fù)元素中的多余元素，只保留其中位序最小的一個(gè)。如線性表（5，2，2，3，5，2），經(jīng)過(guò)清除重復(fù)元素后變?yōu)?5，2，3)。

假定線性表以順序存儲(chǔ)方式存儲(chǔ)，則其算法可描述如下：

voidpurge(sequenlist*L)

{inti=0，j，k；

while(i<=(*L).Len-1){j=i+1；

while(j<=(*L).Len-1)

if((*L).vec[i]==(*L).vec[j])

{for(k=j；k<=(*L).Len-1；k++)(*L).vec[k–1]=(*L).vec[k]；/*元素前移*/

(*L).Len--；/*修改表長(zhǎng)度*/}else

j++；i++；}}/*purge*/29算法4順序表的查找(P26算法2.6)在一個(gè)有n個(gè)元素線性表A中查找值為x的元素的函數(shù)如下：

voidfind(A[],n,x)intn.x;{intj;i=1;while(i<=n&&A[i]!=x)i++;if(i<=n)printf(“找到了！\n”);elseprintf(“沒(méi)找到\n”);}30算法5:順序表的合并(P26算法2.7)

有兩個(gè)順序表A(有m個(gè)元素)和B(有n個(gè)元素),其元素均以從小到大的升序排列,編寫(xiě)一個(gè)函數(shù)將它們合并成一個(gè)順序表C,要求C的元素也是從小到大的升序排列.

解:本題的解法思想是:依次掃描A和B的元素,比較當(dāng)前的元素的值,將較小值的元素賦給C,如此直到一個(gè)表掃描完畢,然后將未完的一個(gè)表余下所有元素賦給C即可.31Voidlink(intA[],intB[];intm,n;intC[]){inti=1,j=1,k=1,s;while(i<=m&&j<=n)/*掃描A和B,將當(dāng)前的較小元素賦給C*/ifA[i]<B[j]){C[k]=A[I];i++;k++;}else{C[k]=B[j];j++;k++;}if(j==n)/*當(dāng)A未完時(shí),將A余下的元素賦給C*/for(s=i+1;s<=m;s++){C[k]=A[s];k++;}if(i==m)/*當(dāng)B未完時(shí),將B余下元素賦給C*/for(s=j+1;s<=n;s++){C[k]=B[s];k++;}}算法2.7C語(yǔ)言代碼為:321.基礎(chǔ)知識(shí)：題集2.1；

2.算法實(shí)現(xiàn)：寫(xiě)出教材算法2.4、2.5（線性表中元素的插入和刪除算法）的C/C++語(yǔ)言程序，并上機(jī)調(diào)試；

3.算法設(shè)計(jì)題：題集2.10、2.11。作業(yè)33

線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：（1）邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也是相鄰的,因此可以隨機(jī)存取表中任意元素(可用地址公式).

（2）無(wú)需為表示數(shù)據(jù)元素之間的關(guān)系而增加額外存儲(chǔ)空間；（3）可以方便地隨機(jī)存取表中任一元素。（4）必須預(yù)先為線性表分配空間，表容量難以擴(kuò)充，必須按線性表最大可能的長(zhǎng)度分配空間，有可能造成存儲(chǔ)空間浪費(fèi)。2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)34

（5）插入和刪除運(yùn)算時(shí)必須移動(dòng)大量元素，效率較低；為避免大量元素的移動(dòng)，本節(jié)討論線性表的另一種存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，是最常用的存儲(chǔ)方法之一，它不僅可以表示線性表，而且可以表示各種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。這種結(jié)構(gòu)按不同的分類(lèi)方法可分為單鏈表、循環(huán)鏈表和雙向鏈表等。35

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)是:邏輯關(guān)系上相鄰的兩個(gè)元素,在物理位置上不一定相鄰,不能隨機(jī)存取鏈中數(shù)據(jù).2.3.1線性鏈表a.一個(gè)結(jié)點(diǎn)——數(shù)據(jù)元素ai的存儲(chǔ)映象。ai存入的數(shù)據(jù)指向其后繼如：鏈表中存入數(shù)據(jù)6,9,3,76937^Head(頭指針)3637

這樣，利用每個(gè)結(jié)點(diǎn)的指針域就可以將n個(gè)結(jié)點(diǎn)按其邏輯次序連成一個(gè)鏈表，這種鏈表中每個(gè)結(jié)點(diǎn)只含一個(gè)指針域，故稱(chēng)為線性鏈表或單鏈表。例如，線性表（red，orange，white，yellow，green，blue），其單鏈表的存儲(chǔ)方式如圖2.5所示。由于單鏈表中第一個(gè)結(jié)點(diǎn)無(wú)直接前趨，可另設(shè)一個(gè)頭指針head存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址。同樣，最后一個(gè)結(jié)點(diǎn)無(wú)直接后繼，其指針域?yàn)榭罩导礊镹ULL，有時(shí)用^表示。整個(gè)單鏈表可由頭指針唯一地確定。單鏈表是一種非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

38

也可以將圖2.5中的單鏈表直觀地畫(huà)成如圖2.6所示，其中箭頭用來(lái)表示鏈域中的指針。39b.結(jié)構(gòu)指針定義

單鏈表可以用C語(yǔ)言中的指針數(shù)據(jù)類(lèi)型實(shí)現(xiàn)，描述如下：

typedefintelemtype；

typedefstructnode/*結(jié)點(diǎn)類(lèi)型定義*/

{elemtypedata；/*數(shù)據(jù)域*/

structnode*next；/*定義指針域*/

}linklist；

linklist*head，*p；/*head，p為單鏈表指針類(lèi)型*/

另外，利用C語(yǔ)言中的指針數(shù)據(jù)類(lèi)型要注意指針變量和結(jié)點(diǎn)變量，其關(guān)系如圖2.7所示。40單鏈表上的基本運(yùn)算

為了便于實(shí)現(xiàn)各種運(yùn)算，常在單鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)附加的結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)，其它的結(jié)點(diǎn)稱(chēng)為表結(jié)點(diǎn)。本章若無(wú)特殊說(shuō)明，均采用帶頭結(jié)點(diǎn)的單鏈表，如圖2.8的(a)，(b)所示。411.

建立一個(gè)單鏈表

（1）算法2.8C語(yǔ)言程序輸入一系列整數(shù)，以0標(biāo)志結(jié)束，將這些整數(shù)作為data域建立一個(gè)單鏈表的函數(shù)：

voidcrea(){node*head,*p,*s;intx,cycle=1;/*cycle是循環(huán)變量*/head=(node*)malloc(sizeof(node));/*建立頭結(jié)點(diǎn)，由dead所指向*/p=head;while(cycle){scanf(“%d”,&x);if(x!=0){s=(node*)malloc(sizef(node));/*建立下一個(gè)結(jié)點(diǎn)，由s所指向*/42s->data=x;p->next=s;p=s;}/*把s結(jié)點(diǎn)鏈接到前面建立的單鏈表中*/elsecycle=0;}head=head->next;/*刪除頭結(jié)點(diǎn)*/p->next=NULL;}如果輸入的整數(shù)序列是：

6103675043

linklist*creatlist()/*函數(shù)返回一個(gè)指向單鏈表表頭的指針*/

{charch；intx；

linklist*head，*r，*p；

p=（linklist*）malloc（sizeof（linklist））；

head=p；

p->next=NULL；/*生成頭結(jié)點(diǎn)*/

r=p；/*建立單鏈表表尾指針*/

ch=getchar()；/*ch為建立與否標(biāo)志*/

while(ch!=‘?’)/*‘?’為輸入結(jié)束標(biāo)志符*/

{scanf(“%d”,&x)；/*讀入新數(shù)據(jù)元素*/

p=（linklist*）malloc(sizeof(linklist))；

p->data=x;

p->next=NULL；/*生成新結(jié)點(diǎn)*/

r->next=p；/*連接新結(jié)點(diǎn)*/

r=r->next；/*修改尾指針*/

ch=getchar()；/*讀入建立與否的標(biāo)志*/

}

return(head)；/*返回表頭指針head*/

}/*creatlist*/（2）建立帶頭結(jié)點(diǎn)的單鏈表44（3）建立不帶頭結(jié)點(diǎn)的單鏈表

linklist*creatlist()/*函數(shù)返回一個(gè)指向鏈表表頭的指針*/

{charch；intx；linklist*head，*p，*r

head=NULL；r=NULL；/*設(shè)立尾指針r，其初值為空*/

ch=getchar()；/*讀入建立與否標(biāo)志*/

while(ch!=‘?’)/*‘?’為輸入結(jié)束標(biāo)志符*/

{p=(linklist*)malloc(sizeof(linklist))；/*申請(qǐng)新結(jié)點(diǎn)空間*/

scanf(“%d”，&x)；

p->data=x;

if(head==NULL)head=p；

elser->next=p；/*非空表，則新結(jié)點(diǎn)*p插入到*r之后*/

r=p；/*尾指針移動(dòng)，指向新的表尾*/

ch=getchar()；/*讀入建立與否的標(biāo)志*/

}

if(r!=NULL)r->next=NULL；

returnhead；/*返回表頭指針head*/

}/*creatlist*/

在算法中引入頭結(jié)點(diǎn)可以不必區(qū)分空表與非空表，可以統(tǒng)一空鏈表與非空鏈表的處理。上述兩個(gè)算法的時(shí)間復(fù)雜度都為O(n)。45

插入結(jié)點(diǎn)的指針變化圖2.9所示。指針的修改操作為：①s->next=p->next；②p->next=s；上述指針進(jìn)行相互賦值的語(yǔ)句順序不能顛倒，若次序變化為：①p->next=s；②s->next=p->next；則會(huì)導(dǎo)致錯(cuò)誤。同樣，要?jiǎng)h除單鏈表結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)也很簡(jiǎn)單，只要用一個(gè)指針指向被刪除結(jié)點(diǎn)，修改*p的指針域，最后釋放結(jié)點(diǎn)*p即可，如圖2.10所示。刪除一個(gè)結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)的指針操作為：

p->next=p->next->next；

不難發(fā)現(xiàn)，在單鏈表存儲(chǔ)結(jié)構(gòu)中進(jìn)行元素的插入和刪除時(shí)，只需要修改有關(guān)的指針內(nèi)容，而不需要移動(dòng)元素。

2．單鏈表上元素的插入和刪除運(yùn)算4647

（a）

insert(linklist*p,elemtypex)

/*將值為x的新結(jié)點(diǎn)插入*p之后*/

{linklist*s；

s=（linklist*）malloc(sizeof(linklist))；/*生成x的新結(jié)點(diǎn)*s*/

s->data=x；

s->next=p->next；/*新結(jié)點(diǎn)鏈入單鏈表*/

p->next=s；

}/*insert*/

（1）插入算法48

（b）voidinsert(linklist*head,elemtypek,elemtypex)

/*在單鏈表中值為k的結(jié)點(diǎn)之前插入一個(gè)值為x的新結(jié)點(diǎn)*/

{linklist*q，*p，*r；

r=(linklist*)malloc(sizeof(linklist))；/*生成新結(jié)點(diǎn)*/

r->data=x；

if(head->next==NULL){head->next=r；

r->next=NULL；

}

else

{q=head->next；

p=head->next->next；

while(p!=NULL)

{if(p->data!=k)*/

{q=p；

p=p->next；

}

elsebreak；49if(p!=NULL)

{q->next=r；

r->next=p；

}

else/*在鏈表表尾處插入新結(jié)點(diǎn)*/

{q->next=r；

r->next=NULL；

}

}

}/*insert*/

該算法的時(shí)間主要耗費(fèi)在查找值為k的結(jié)點(diǎn)位置上，算法時(shí)間復(fù)雜度為O(n)。50

算法2.9單鏈表的插入（C語(yǔ)言函數(shù)）

在單鏈表中第i個(gè)結(jié)點(diǎn)（i>=0)之后插入一個(gè)元素為x的結(jié)點(diǎn)。voidinser(head,i)node*head;inti,x;{node*s,*p;intj;s=(node*)malloc(sizeof(node));/*建立一個(gè)待插入的結(jié)點(diǎn)s*/scanf(“%s”,&x);s->data=x;if(i==0)/*如果i=0，則將s所指結(jié)點(diǎn)插入到表頭后返回*/{s->next=head;head=s;}else{p=head;j=i;/*在單鏈表中查找第i個(gè)結(jié)點(diǎn)，由p指向*/while(p!=NULL&&j<i){j++;p=p->next;}if(p!=NULL)/*若找查成功,則把s插入到其后*/{s->next=p->next;p->next=s;}elseprintf(“未找到！\n”);}}51（a）

delete(linklist*p)/*刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/

{linklist*r；

r=p->next；

if(r!=NULL)

{p->next=r->next；

free(r)；

}}/*delete*/

（b）linklist*delete(linklist*head，inti)/*刪除單鏈表head的第i個(gè)結(jié)點(diǎn)*/

{intj=0；

linklist*p，*s，*q；

p=head；j=0；

while((p->next!=NULL)&&(j<i-1)}

{p=p->next；

j++；

}（2）刪除算法52if(p->next!=NULL)

{q=p->next；

p->next=p->next->next；

free(q)；

}

else

returnNULL；

s=head；

returns；

}/*delete*/

該算法時(shí)間復(fù)雜度為O(n)。53一般情況下，可以按某個(gè)元素的序號(hào)或按某給定值兩種方法檢索。

（1）按值檢索

按值檢索，即是檢索單鏈表中是否存在值為給定值k的結(jié)點(diǎn)，整個(gè)過(guò)程可以通過(guò)結(jié)點(diǎn)的值和給定值的比較而實(shí)現(xiàn)。

linklist*locate（linklist*head，elemtypek）

{linklist*s；

s=head->next；/*從第一個(gè)結(jié)點(diǎn)起開(kāi)始比較*/

while(s!=NULL)/*掃描整個(gè)鏈表*/

if(s->data!=k)s=s->next；

elsebreak；returns；/*返回結(jié)點(diǎn)的位置或NULL*/

}/*Locate*/

算法時(shí)間復(fù)雜度為O(n)。3.單鏈表上元素的檢索54

即利用被訪問(wèn)結(jié)點(diǎn)的序號(hào)而檢索或查找結(jié)點(diǎn)的過(guò)程。

linklist*get(linklist*head，inti)

{intj；

linklist*p；

p=head；j=0；

while((p->next!=NULL)&&(i>j))

{p=p->next；

j++；

}

if(i==j)returnp；

else

returnNULL；

}/*get*/

該算法中最壞情況下的時(shí)間復(fù)雜度為O(n)。（2）按序號(hào)檢索55

例，將兩個(gè)遞增的單鏈表合并為一個(gè)遞增單鏈表，且要求不重新開(kāi)辟空間，其算法可描述如下：

void*union(linklist*heada，linklist*headb)/*合并單鏈表heada與headb*/

{linklist*p，*q，*r，*u；

p=heada->next；

q=headb->next；

r=heada；

while(p!=NULL)&&(q!=NULL)

{if(p->data>q->data；

{u=q->next；

r->next=q；

r=q；

q->next=p；

q=u；

}

56else

if(p->data<=q->data)

{r=p；

p=p->next；

}}if(q!=NULL)r->next=q；

}/*union*/57

1.基礎(chǔ)知識(shí)：題集2.1、2.4、2.5、2.6、2.7；

2.算法實(shí)現(xiàn)：寫(xiě)出教材算法2.10單鏈表的刪除C/C++語(yǔ)言程序，并上機(jī)調(diào)試通過(guò);2.算法設(shè)計(jì)題:2.15、2.16。作業(yè)58

如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)（或第一個(gè)表結(jié)點(diǎn)）的地址值，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，如圖2.12所示，這樣的鏈表稱(chēng)為循環(huán)鏈表。顯然，它是一種首尾相接的鏈表，從循環(huán)鏈表中任一個(gè)結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有其它結(jié)點(diǎn)。對(duì)單鏈表的鏈接方式稍作一些改變，就可構(gòu)成一個(gè)新的存儲(chǔ)結(jié)構(gòu)——單循環(huán)鏈表。同樣，也有多重鏈的循環(huán)鏈表。在循環(huán)鏈表中，為了使空表和非空表的處理一致，同樣可設(shè)置一個(gè)頭結(jié)點(diǎn)。2.3.2循環(huán)鏈表59

循環(huán)鏈表的基本運(yùn)算與單鏈表基本一致，差別只在于最后一個(gè)結(jié)點(diǎn)的循環(huán)處理上。只要將單鏈表算法中出現(xiàn)NULL處改為頭指針即可。例如，將單循環(huán)鏈表倒置或逆置。

linklist*invert(head)

linklist*head；

{linklist*p，*q，*s;

q=head；

p=head->next；

while(p!=head)

{s=q；

q=p；

p=p->next；

q->next=s；

}

p->next=q；

returnhead；

}/*invert*/60

在單循環(huán)鏈表中，從任一個(gè)已知結(jié)點(diǎn)出發(fā)可以找到其前趨結(jié)點(diǎn)，但時(shí)間耗費(fèi)需O(n)，若希望能快速確定一個(gè)結(jié)點(diǎn)的直接前趨，可以再加上一個(gè)指針域存儲(chǔ)其直接前趨的信息，這樣就可以構(gòu)成雙向鏈表，它有兩個(gè)方向不同的鏈，如果將每個(gè)方向的鏈表構(gòu)成一個(gè)環(huán)，則可以構(gòu)成雙向循環(huán)鏈表。

雙向鏈表的C語(yǔ)言描述：

typedefstructdupnode

{elemtypedata；

structdupnode*next，*prior；

}dulinklist；

dulinklist*head;

雙向循環(huán)鏈表也可由頭指針head唯一確定，同樣可增加頭結(jié)點(diǎn)，使得雙鏈表的某些運(yùn)算簡(jiǎn)便一些，如圖2.14所示。2.3.3雙向鏈表6162

由于雙向鏈表在其結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)既有指向其直接前趨的指針域，又有指向其直接后繼的指針域，因此比起單鏈表來(lái)，要在一個(gè)雙向鏈表中檢索某一個(gè)已知結(jié)點(diǎn)的直接前趨和后繼結(jié)點(diǎn)要方便得多。結(jié)點(diǎn)*p可通過(guò)多種方式訪問(wèn)，設(shè)指針p指向雙向鏈表中某個(gè)結(jié)點(diǎn)，則有：p->next->prior=p=p->prior->next

雙向鏈表中結(jié)點(diǎn)的插入情況如圖2.16所示。63

在*p結(jié)點(diǎn)之前插入結(jié)點(diǎn)*s的正確步驟應(yīng)為：

①p->prior->next=s；②s->prior=p->prior；③s->next=p；④p->prior=s；

由于雙向鏈表中每個(gè)結(jié)點(diǎn)涉及兩個(gè)指針的運(yùn)算，對(duì)于某些運(yùn)算要注意運(yùn)算順序。在上面的步驟中指針p->prior的修改必須在*p結(jié)點(diǎn)的前趨結(jié)點(diǎn)*(p->prior)的后繼指針修改之后方可改動(dòng)，否則會(huì)不能正確地插入結(jié)點(diǎn)。

在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)*p的指針變化如圖2.15所示。指針修改的運(yùn)算步驟為：①p->prior->next=p->next；②p->next->prior=p->prior；64voidindulist(dulinklist*head,inti,elemtypex)

/*在雙向循環(huán)鏈表head中的第i個(gè)結(jié)點(diǎn)之前插入值為x的新結(jié)點(diǎn)*/

{dulinklist*p，*s;intj;

p=head;j=0;

while((p->next!=head)&&(j<i-1))

{p=p->next;

j++;}

if((i>0)&&(j==i-1))

{s=malloc(sizeof(dulinklist));s->data=x;

s->next=p->next;

s->prior=p；

p->next=s；

s->next->prior=s;}

elseprintf(“error！\n”)

/*indulist*/1．插入算法（算法2.18）65voiddeledulist(dulinklist*head,inti)/*刪除雙向鏈表head中的第i個(gè)結(jié)點(diǎn)*/

{dulinklist*p;intj;

p=head;j=0;

while((p->next!=head)&&(j<i))

{p=p->next;

j++;

}

if((i>0)&&(j==i))