第二章線性表A

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

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

2.1線性表的類型定義 3

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

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

其中，是第一個數(shù)據(jù)元素，又稱為起始結(jié)點，是最后一個數(shù)據(jù)元素，又稱為終端結(jié)點。5

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

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

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

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

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

2.1.2線性表的運算9

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

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

L是每個元素占用的存儲單元

11

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

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

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

intlenght；

}sequenlist；

14

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

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

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

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

voidinsert(A,n,x)vectorA;intn,x;{inti,j;scanf(“%d”,&i);/*確定插入位置*/if(i<1||i>n)print(“i值錯誤！\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個元素前插入數(shù)據(jù)元素x，若成功，返回TRUE，否則返回FALSE。*/intj;if(i<0||i>*num+1){printf(“Error!”); /*插入位置出錯*/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)++; /*長度加1*/returnTRUE;}

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

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

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

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

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

22

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

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

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

23

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

243．刪除運算

刪除運算是指將線性表中的第i個元素刪除，使線性表的長度由n變成n-1，由：

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

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

其中，1≤i≤n。線性表進(jìn)行刪除元素后，仍是一個線性表。刪除過程如圖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--；/*修改表長*/}}/*delete*/26

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

由此可見，對線性表刪除一個元素時，約需有一半的元素參加移動。

27

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

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

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

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--；/*修改表長度*/}else

j++；i++；}}/*purge*/29算法4順序表的查找(P26算法2.6)在一個有n個元素線性表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(“沒找到\n”);}30算法5:順序表的合并(P26算法2.7)

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

解:本題的解法思想是:依次掃描A和B的元素,比較當(dāng)前的元素的值,將較小值的元素賦給C,如此直到一個表掃描完畢,然后將未完的一個表余下所有元素賦給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未完時,將A余下的元素賦給C*/for(s=i+1;s<=m;s++){C[k]=A[s];k++;}if(i==m)/*當(dāng)B未完時,將B余下元素賦給C*/for(s=j+1;s<=n;s++){C[k]=B[s];k++;}}算法2.7C語言代碼為:321.基礎(chǔ)知識：題集2.1；

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

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

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

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

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

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

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

38

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

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

typedefintelemtype；

typedefstructnode/*結(jié)點類型定義*/

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

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

}linklist；

linklist*head，*p；/*head，p為單鏈表指針類型*/

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

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

建立一個單鏈表

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

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

6103675043

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

{charch；intx；

linklist*head，*r，*p；

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

head=p；

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

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é)點*/

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

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

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

}

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

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

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

{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))；/*申請新結(jié)點空間*/

scanf(“%d”，&x)；

p->data=x;

if(head==NULL)head=p；

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

r=p；/*尾指針移動，指向新的表尾*/

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

}

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

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

}/*creatlist*/

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

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

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

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

2．單鏈表上元素的插入和刪除運算4647

（a）

insert(linklist*p,elemtypex)

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

{linklist*s；

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

s->data=x；

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

p->next=s；

}/*insert*/

（1）插入算法48

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

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

{linklist*q，*p，*r；

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

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é)點*/

{q->next=r；

r->next=NULL；

}

}

}/*insert*/

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

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

在單鏈表中第i個結(jié)點（i>=0)之后插入一個元素為x的結(jié)點。voidinser(head,i)node*head;inti,x;{node*s,*p;intj;s=(node*)malloc(sizeof(node));/*建立一個待插入的結(jié)點s*/scanf(“%s”,&x);s->data=x;if(i==0)/*如果i=0，則將s所指結(jié)點插入到表頭后返回*/{s->next=head;head=s;}else{p=head;j=i;/*在單鏈表中查找第i個結(jié)點，由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é)點的后繼結(jié)點*/

{linklist*r；

r=p->next；

if(r!=NULL)

{p->next=r->next；

free(r)；

}}/*delete*/

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

{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*/

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

（1）按值檢索

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

linklist*locate（linklist*head，elemtypek）

{linklist*s；

s=head->next；/*從第一個結(jié)點起開始比較*/

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

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

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

}/*Locate*/

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

即利用被訪問結(jié)點的序號而檢索或查找結(jié)點的過程。

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*/

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

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

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ǔ)知識：題集2.1、2.4、2.5、2.6、2.7；

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

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

循環(huán)鏈表的基本運算與單鏈表基本一致，差別只在于最后一個結(jié)點的循環(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)鏈表中，從任一個已知結(jié)點出發(fā)可以找到其前趨結(jié)點，但時間耗費需O(n)，若希望能快速確定一個結(jié)點的直接前趨，可以再加上一個指針域存儲其直接前趨的信息，這樣就可以構(gòu)成雙向鏈表，它有兩個方向不同的鏈，如果將每個方向的鏈表構(gòu)成一個環(huán)，則可以構(gòu)成雙向循環(huán)鏈表。

雙向鏈表的C語言描述：

typedefstructdupnode

{elemtypedata；

structdupnode*next，*prior；

}dulinklist；

dulinklist*head;

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

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

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

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

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

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

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

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

{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個結(jié)點*/

{dulinklist*p;intj;

p=head;j=0;

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

{p=p->next;

j++;

}

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