數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課件第一頁，共九十九頁，2022年，8月28日線性表是一種最簡單的線性結(jié)構(gòu)。

什么是線性結(jié)構(gòu)？簡單地說，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集合。它有四個(gè)基本特征：

1．集合中必存在唯一的一個(gè)"第一元素"；

2．集合中必存在唯一的一個(gè)"最后元素"；

3．除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼"；

4．除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。第二頁，共九十九頁，2022年，8月28日2.1.1抽象數(shù)據(jù)類型線性表的定義

通?？梢韵铝小皀個(gè)數(shù)據(jù)元素的序列”表示線性表(Linear_List)

(a1,a2,...,ai,...,an)

序列中數(shù)據(jù)元素的個(gè)數(shù)n定義為線性表的表長；n=0時(shí)的線性表被稱為空表。稱i為ai在線性表中的位序。其抽象數(shù)據(jù)類型的定義如下：

ADTList{

數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|,∈D,i=2,...,n}第三頁，共九十九頁，2022年，8月28日基本操作：

{結(jié)構(gòu)初始化}

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表L。{銷毀結(jié)構(gòu)}

DestroyList(&L)

初始條件：線性表L已存在。

操作結(jié)果：銷毀線性表L。第四頁，共九十九頁，2022年，8月28日{(diào)引用型操作}ListEmpty(L)

初始條件：線性表L已存在。

操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE。ListLength(L)

初始條件：線性表L已存在。

操作結(jié)果：返回L中元素個(gè)數(shù)。PriorElem(L,cur_e,&pre_e)

初始條件：線性表L已存在。

操作結(jié)果：若cur_e是L中的數(shù)據(jù)元素，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無定義。第五頁，共九十九頁，2022年，8月28日NextElem(L,cur_e,&next_e)

初始條件：線性表L已存在。

操作結(jié)果：若cur_e是L中的數(shù)據(jù)元素，則用next_e返回它的后繼，

否則操作失敗，next_e無定義。GetElem(L,i,&e)

初始條件：線性表L已存在，1≤i≤LengthList(L)。

操作結(jié)果：用e返回L中第i個(gè)元素的值。第六頁，共九十九頁，2022年，8月28日LocateElem(L,e,compare())

初始條件：線性表L已存在，compare()是元素判定函數(shù)。

操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的元素的位序。

若這樣的元素不存在，則返回值為0。ListTraverse(L,visit())

初始條件：線性表L已存在，visit()為元素的訪問函數(shù)。

操作結(jié)果：依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit()。

一旦visit()失敗，則操作失敗。第七頁，共九十九頁，2022年，8月28日{(diào)加工型操作}ClearList(&L)

初始條件：線性表L已存在。

操作結(jié)果：將L重置為空表。PutElem(&L,i,&e)

初始條件：線性表L已存在，1≤i≤LengthList(L)。

操作結(jié)果：L中第i個(gè)元素賦值同e的值。第八頁，共九十九頁，2022年，8月28日ListInsert(&L,i,e)

初始條件：線性表L已存在，1≤i≤LengthList(L)+1。

操作結(jié)果：在L的第i個(gè)元素之前插入新的元素e，L的長度增1。ListDelete(&L,i,&e)

初始條件：線性表L已存在且非空，1≤i≤LengthList(L)。

操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的長度減1。}ADTList第九頁，共九十九頁，2022年，8月28日2.1.2線性表類型的應(yīng)用

如果已經(jīng)實(shí)現(xiàn)了上述定義的線性表類型，那么在應(yīng)用問題的求解中就可以利用類型中定義的各種操作。下面將舉三個(gè)例子說明之。第十頁，共九十九頁，2022年，8月28日例2-1

已知集合

A和

B，求兩個(gè)集合的并集，使

A＝A∪B，且

B不再單獨(dú)存在。

從集合的觀點(diǎn)看，此問題求解的方法很簡單，只要對(duì)集合

B中的所有元素一個(gè)一個(gè)地檢查，看看在集合

A中是否存在相同元素，若不存在，則將該元素插入到集合

A，否則舍棄之。

要在計(jì)算機(jī)中求解，首先要確定"如何表示集合"。集合可以有多種表示方法，對(duì)上述集合求并的問題可以用線性表表示集合。

現(xiàn)假設(shè)以線性表

LA和

LB分別表示集合

A和

B，即構(gòu)造兩個(gè)線性表

LA和

LB，它們的數(shù)據(jù)元素分別為集合

A和

B中的成員。

由此，上述集合求并的問題便可演繹為：要求對(duì)線性表作如下操作：擴(kuò)大線性表

LA，將存在于線性表

LB中而不存在于線性表

LA中的數(shù)據(jù)元素插入到線性表

LA中去。第十一頁，共九十九頁，2022年，8月28日具體操作步驟為：

1．從線性表

LB中取出一個(gè)數(shù)據(jù)元素；

2．依值在線性表

LA中進(jìn)行查詢；

3．若不存在，則將它插入到

LA中。

重復(fù)上述三步直至

LB為空表止。

那么，其中的每一步能否利用上述線性表類型中定義的基本操作來完成呢？第十二頁，共九十九頁，2022年，8月28日容易看出，上述的每一步恰好對(duì)應(yīng)線性表的一個(gè)基本操作：

1.ListDelete(LB,1,e);

2.LocateElem(LA,e,equal());

3.ListInsert(LA,n+1,e)

第十三頁，共九十九頁，2022年，8月28日由此得到求并集的算法如下所示：算法2.1

voidunion(List&LA,List&LB)

{//將所有在線性表LB中但不在LA中的數(shù)據(jù)元素插入到LA中,算法執(zhí)行之后，線性表LB不再存在。

La_len=ListLength(LA);//求得線性表LA的長度

while(!ListEmpty(LB))//依次處理LB中元素直至LB為空表止

{

ListDelete(LB,1,e);//從LB中刪除第1個(gè)數(shù)據(jù)元素并賦給e

if(!LocateElem(LA,e,equal())

ListInsert(LA,++La_len,e);

//當(dāng)LA中不存在和e值相同的數(shù)據(jù)元素時(shí)進(jìn)行插入

}//while

DestroyList(LB);//銷毀線性表LB

)//union第十四頁，共九十九頁，2022年，8月28日例2-2已知一個(gè)"非純集合"B，試構(gòu)造一個(gè)集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。換句話說，此問題即為從

B中挑選出所有"彼此相異"的元素構(gòu)成一個(gè)新的集合。如何區(qū)分元素的"相異"或"相同"，一個(gè)簡單方法即為將每個(gè)從

B中取出的元素和已經(jīng)加入到集合

A中的元素相比較。

如果還是以線性表

LB和

LA分別表示"集合"B和

A，那么和例2-1的問題相比，此問題求解的算法應(yīng)該如何寫呢？第十五頁，共九十九頁，2022年，8月28日容易看出，應(yīng)對(duì)線性表作和上例相同的操作，具體的三步也都相同，所不同之處僅僅在于兩點(diǎn)：一是例2-1的算法中

LA是已知的，而在此例算法中的

LA是待新建的；二是例2-1在求得并集之后，原來的兩個(gè)集合不再保留，而在此例中構(gòu)建新的集合

A的同時(shí)，原來的集合

B不變。第十六頁，共九十九頁，2022年，8月28日算法2.2

voidpurge(List&LA,ListLB)

{

//構(gòu)造線性表LA，使其只包含LB中所有值不相同的數(shù)據(jù)

//元素,算法不改變線性表LB

InitList(LA);

//創(chuàng)建一個(gè)空的線性表

LA

La_len=0;

Lb_len=ListLength(LB);

//求線性表

LB的長度

for(i=1;i<=Lb_len;i++)//依次處理

LB中每個(gè)元素

{

GetElem(LB,i,e);//取

LB中第

i個(gè)數(shù)據(jù)元素賦給

e

if(!LocateElem(LA,e,equal())

ListInsert(LA,++La_len,e);

//當(dāng)

LA中不存在和

e值相同的數(shù)據(jù)元素時(shí)進(jìn)行插入

}//for

)//purge

第十七頁，共九十九頁，2022年，8月28日例2-3

判別兩個(gè)集合是否相等。

兩個(gè)集合相等的充分必要條件是它們具有相同的元素。當(dāng)以線性表表示集合時(shí)，兩個(gè)線性表的長度應(yīng)該相等，且表中所有數(shù)據(jù)元素都能一一對(duì)應(yīng)，但相同的數(shù)據(jù)元素在各自的線性表中的"位序"不一定相同。

由此，"判別兩個(gè)線性表中的數(shù)據(jù)元素是否完全相同"的算法的基本思想為：首先判別兩者的表長是否相等；在表長相等的前提下，如果對(duì)于一個(gè)表中的所有元素，都能在另一個(gè)表中找到和它相等的元素的話，便可得到"兩個(gè)線性表表示的集合相等"的結(jié)論；反之，只要有一個(gè)元素在另一個(gè)表中不能找到相等元素時(shí)，便可得出"不等"的結(jié)論。第十八頁，共九十九頁，2022年，8月28日算法2.3

boolisEqual(ListLA,ListLB)

{

//若線性表LA和LB不僅長度相等，且所含數(shù)據(jù)元素也相同，

//則返回TRUE，否則返回FALSE。

La_len=Listlength(LA);

Lb_len=Listlength(LB);if(La_len!=Lb_len)return

FALSE;//兩表的長度不等

else

{

i=1;found=TRUE;

while(i<=La_len&&found)

{

GetElem(LA,i,e);

//取得

LA中一個(gè)元素

if(LocateElem(LB,e,equal())

i++;

//依次處理下一個(gè)

elsefound=FALSE;//LB中沒有和該元素相同的元素

}//while

returnfound;

}//else

)//isEqual

第十九頁，共九十九頁，2022年，8月28日2.2.1順序表

順序表是線性表的順序存儲(chǔ)表示的簡稱，它指的是，“用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素”，即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系(有序?qū)?lt;ai-1,ai>)”，并以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。如下圖所示。第二十頁，共九十九頁，2022年，8月28日不失一般性，假設(shè)每個(gè)數(shù)據(jù)元素占據(jù)的存儲(chǔ)量是一個(gè)常量C，則后繼元素的存儲(chǔ)地址和其前驅(qū)元素相隔一個(gè)常量，

即：LOC(ai)=LOC(ai-1)+C

↑一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量由此，所有數(shù)據(jù)元素的存儲(chǔ)位置均可由第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置得到

LOC(ai)=LOC(a1)+(i-1)×C

↑基地址

第二十一頁，共九十九頁，2022年，8月28日用C語言描述的順序表類型如下所示：

//存儲(chǔ)結(jié)構(gòu)

const

intMAXLISTSIZE=80;//預(yù)設(shè)的存儲(chǔ)空間最大容量

typedefstruct{

ElemType*elem;

//存儲(chǔ)空間基址

intlength;

//當(dāng)前長度

intlistsize;

//允許的最大存儲(chǔ)容量(以sizeof(ElemType)為單位)

}

SqList;

//俗稱

順序表

第二十二頁，共九十九頁，2022年，8月28日//基本操作接口(函數(shù)聲明)

voidInitList(SqList&L,intmaxsize);

//構(gòu)造一個(gè)最大存儲(chǔ)容量為maxsize的空的順序表L。voidDestroyList(SqList&L)

//

銷毀順序表

L。

boolListEmpty(SqListL)

//

若順序表

L為空表，則返回TRUE，否則返回

FALSE。

intListLength(SqListL)

//

返回順序表

L中元素個(gè)數(shù)。

intPriorElem(SqListL,ElemTypecur_e)

//

若

cur_e是順序表

L的元素，則返回其前驅(qū)的位序

//

(設(shè)第一個(gè)元素的前驅(qū)的位序?yàn)?)，否則返回-1。

第二十三頁，共九十九頁，2022年，8月28日intNextElem(SqListL,ElemTypecur_e)

//若cur_e是順序表L的元素，則返回其后繼的位序

//(設(shè)最后一個(gè)元素的后繼的位序?yàn)長的表長+1)，否則返回-1。boolGetElem(SqListL,intpos,ElemType&e)

//若1≤pos≤LengthList(L)，則用e帶回順序表L中第

//pos個(gè)元素的值且返回函數(shù)值為TRUE，否則返回函數(shù)值為FALSE。intLocateElem(SqListL,ElemTypee,bool(*compare)(ElemType,ElemType))

//返回順序表L中第1個(gè)與e

滿足關(guān)系compare()的數(shù)據(jù)元素的位序。

//若這樣的元素不存在，則返回值為0。compare()為數(shù)據(jù)元素的判定函數(shù)。voidListTraverse(SqListL,void(*visit)(ElemType))

//依次對(duì)順序表L的每個(gè)元素調(diào)用函數(shù)visit()。

//一旦visit()失敗，則操作失敗。voidClearList(SqList&L)//

將順序表

L重置為空表。

第二十四頁，共九十九頁，2022年，8月28日boolPutElem(SqListL,intpos,ElemType&e)

//

若1≤pos≤LengthList(L)，則對(duì)順序表

L中第

pos個(gè)元素

//賦值同

e的值且返回函數(shù)值為

TRUE，否則返回函數(shù)值為

FALSE。

boolListInsert(SqList&L,intpos,ElemTypee)

//

若存儲(chǔ)空間未滿且1≤pos≤LengthList(L)+1，則在順序表

L的

//第

pos個(gè)元素之前插入新的元素

e，L的長度增1，且返回函數(shù)值為TRUE，

//

否則不改變順序表且返回函數(shù)值為

FALSE。

boolListDelete(SqList&L,intpos,ElemType&e)

//

若1≤pos≤LengthList(L)，則刪除順序表

L的第

pos個(gè)元素

e，

//

L的長度增1，且返回函數(shù)值為TRUE，否則不改變順序表且返回函數(shù)值為FALSE。

第二十五頁，共九十九頁，2022年，8月28日以上定義的函數(shù)可在程序設(shè)計(jì)中引用，例如，上述算法2.2可改寫為下列可在主函數(shù)中調(diào)用的函數(shù)。

voidpurge(SqList&La,SqListLb)

{

//構(gòu)造順序表

La，使其只包含

Lb中所有值不相同的數(shù)據(jù)元素,

//算法不改變順序表

Lb

boolb;

intLb_len=Listlength(Lb);

//求線性表

Lb的長度

InitList(La,Lb_len);

//創(chuàng)建一個(gè)空的線性表

La

intLa_len=0;

for(i=1;i<=Lb_len;i++)

//依次處理

Lb中每個(gè)元素

{

b=GetElem(Lb,i,e);

//取Lb中第

i個(gè)數(shù)據(jù)元素賦給

e

if(!LocateElem(La,e,equal()))

{

++La_len;

b=ListInsert(La,La_len,e);//當(dāng)

La中不存在和

e值相同的

}

//數(shù)據(jù)元素時(shí)，進(jìn)行插入

}//for

第二十六頁，共九十九頁，2022年，8月28日2.2.2順序表中基本操作的實(shí)現(xiàn)

從順序表的存儲(chǔ)結(jié)構(gòu)定義容易看出，由于順序表的"長度"是個(gè)"顯值"，且由于第i個(gè)元素恰好存儲(chǔ)在數(shù)組的第

i個(gè)分量(數(shù)組下標(biāo)為

i-1)中，因此其"求長"、"判空"以及"存取第

i個(gè)數(shù)據(jù)元素"等操作都很容易實(shí)現(xiàn)。下面重點(diǎn)討論順序表類型定義中五個(gè)操作的實(shí)現(xiàn)。

一、初始化操作

二、元素定位操作

三、插入元素操作

四、刪除元素操作

五、銷毀結(jié)構(gòu)操作

第二十七頁，共九十九頁，2022年，8月28日一、初始化操作

對(duì)順序表而言，"初始化"的實(shí)質(zhì)是為它分配一個(gè)"足夠應(yīng)用"的元素存儲(chǔ)空間，由用戶根據(jù)它對(duì)線性表的使用要求定義一個(gè)最大存儲(chǔ)容量

maxsize，并約定當(dāng)用戶沒有提出特殊需求(maxsize=0)時(shí)，按予設(shè)的最大存儲(chǔ)量

MAXLISTSIZE進(jìn)行分配。第二十八頁，共九十九頁，2022年，8月28日算法2.4

voidInitList(SqList&L,intmaxsize)

{

//構(gòu)造一個(gè)空的線性表L

if(maxsize==0)

maxsize=MAXLISTSIZE;

L.elem=newElemType[maxsize];if(!L.elem)

exit(1);

//存儲(chǔ)分配失敗

L.length=0;

//順序表的初始長度為0

L.listsize=maxsize;

//該順序表可以存儲(chǔ)元素的最大容量

}//InitList

此算法的時(shí)間復(fù)雜度為O(1)。

第二十九頁，共九十九頁，2022年，8月28日二、元素定位操作

在順序表中"查詢"是否存在一個(gè)和給定值滿足判定條件的元素的最簡單的辦法是，依次取出結(jié)構(gòu)中的每個(gè)元素和給定值進(jìn)行比較。第三十頁，共九十九頁，2022年，8月28日算法2.5intLocateElem(SqListL,ElemTypee,

void(*compare)(ElemType,ElemType)){//在順序表L中查找第1個(gè)值與

e滿足判定條件compare()的元素，

//若找到，則返回其在

L中的位序，否則返回0。

i=1;

//i的初值為第1元素的位序

p=L.elem;

//p的初值為第1元素的存儲(chǔ)位置

while(i<=L.length&&!(*compare)(*p++,e))

++i;

//依次進(jìn)行判定

if(i<=L.length)returni;

//找到滿足判定條件的數(shù)據(jù)元素為第

i個(gè)元素

else

return0;

//該線性表中不存在滿足判定的數(shù)據(jù)元素

}//LocateElem

此算法的時(shí)間復(fù)雜度為：O(ListLength(L))

第三十一頁，共九十九頁，2022年，8月28日三、插入元素操作

首先分析，“插入元素”使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

假設(shè)在線性表的第i個(gè)元素之前插入一個(gè)元素e，使得線性表

(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)

即：(1)改變了表中元素之間的關(guān)系，使<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>(2)表長增1

由于順序表是以"存儲(chǔ)位置相鄰"表示"元素之間的前驅(qū)和后繼關(guān)系"，則必須"移動(dòng)元素"來體現(xiàn)"元素之間發(fā)生的變化"。第三十二頁，共九十九頁，2022年，8月28日算法2.6boolListInsert(SqList&L,intpos,ElemTypee){

//若存儲(chǔ)空間不滿且1≤pos≤Listlength(L)+1，則在順序表

L

的

//第

pos個(gè)元素之前插入新的元素

e且返回TRUE，否則返回FALSE

if(pos<1||pos>L.length+1)

returnFALSE;//插入位置不合法

if(L.length>=L.listsize)returnFALSE;

//當(dāng)前存儲(chǔ)空間已滿，無法插入

for(j=L.length-1;j>=pos-1;--j)

L.elem[j+1]=L.elem[j];//插入位置及之后的元素右移L.elem[pos-1]=e;

//插入

e

++L.length;

//表長增1

return

TRUE;

}//ListInsert

此算法的時(shí)間復(fù)雜度為：O(ListLength(L))

第三十三頁，共九十九頁，2022年，8月28日四、刪除元素操作

同樣首先分析，“刪除元素”使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

假設(shè)刪除線性表中第i個(gè)元素，使得線性表

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,ai+1,…,an)即：(1)改變了表中元素之間的關(guān)系，使<ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>(2)表長減1

對(duì)順序表而言，需要改變從第

i+1個(gè)元素起到第

n個(gè)元素的存儲(chǔ)位置，即進(jìn)行"從第

i+1到第

n個(gè)元素往前移動(dòng)一個(gè)位置"。第三十四頁，共九十九頁，2022年，8月28日算法2.7boolListDelete(SqList&L,intpos,ElemType&e){//若1≤pos≤Listlength(L)，則以e帶回從順序表L中刪除的//第pos個(gè)元素且返回TRUE，否則返回FALSE

if((pos<1)||(pos>L.length))

returnFALSE;//刪除位置不合法

for(j=pos;j<L.length;++j)

L.elem[j-1]=L.elem[j];//被刪除元素之后的元素左移--L.length;

//表長減1

returnTRUE;}//ListDelete

此算法的時(shí)間復(fù)雜度為：O(ListLength(L))

第三十五頁，共九十九頁，2022年，8月28日五、銷毀結(jié)構(gòu)操作算法2.8voidDestroyList(SqList&L){//釋放順序表L所占存儲(chǔ)空間

delete[]L.elem;

L.listsize=0;

L.length=0;

}//DestroyList_Sq

此算法的時(shí)間復(fù)雜度為：O(1)

第三十六頁，共九十九頁，2022年，8月28日六、插入和刪除操作的性能分析(p25)第三十七頁，共九十九頁，2022年，8月28日2.2.3順序表其它算法舉例

例2-4試編寫算法“比較”兩個(gè)順序表的大小。

算法的基本思想為：若ai=bj，則j增1，之后繼續(xù)比較后繼元素；否則即可得出比較結(jié)果。顯然，j的初值應(yīng)為0，循環(huán)的條件是j不超出其中任何一個(gè)表的范圍。若在循環(huán)內(nèi)不能得出比較結(jié)果，則循環(huán)結(jié)束時(shí)有三種可能出現(xiàn)的情況需要區(qū)分。

根據(jù)以上分析可得下列算法。第三十八頁，共九十九頁，2022年，8月28日算法2.9intcompare(SqListA,SqListB){//若A<B，則返回-1；若A=B，則返回0；若A>B，則返回1

j=0;

while(j<A.length&&j<B.length)

if(A.elem[j]<B.elem[j])return(-1);

elseif(A.elem[j]>B.elem[j])return(1);

elsej++;

if(A.length==B.length)return(0);

elseif(A.length<B.length)return(-1);

elsereturn(1);

}//compare

上述算法中只有一個(gè)while循環(huán)，它的執(zhí)行次數(shù)依賴于待比較的順序表的表長，因此，算法2.9的時(shí)間復(fù)雜度為O(Min(A.length,B.length))。第三十九頁，共九十九頁，2022年，8月28日例2-5試設(shè)計(jì)一個(gè)算法，用盡可能少的輔助空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行互換，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。

第四十頁，共九十九頁，2022年，8月28日算法2.10voidinvert(ElemType&R[],ints,intt){//本算法將數(shù)組R中下標(biāo)自s到t的元素逆置，即將//（Rs,Rs+1,…,Rt-1,Rt）改變?yōu)椋≧t,Rt-1,…,Rs+1,Rs）

for(k=s;k<=(s+t)/2;k++)

{

w=R[k];

R[k]=R[t-k+s];

R[t-k+s]=w;

}//for}//invert

第四十一頁，共九十九頁，2022年，8月28日算法2.11voidexchange(SqList&A,intm){//本算法實(shí)現(xiàn)順序表中前m個(gè)元素和后n個(gè)元素的互換

if(m>0&&m<A.length){

n=A.length-m;

invert(A.elem,0,m+n-1);

invert(A.elem,0,n-1);

invert(A.elem,n,m+n-1);

}

}//exchange第四十二頁，共九十九頁，2022年，8月28日例2-6編寫算法刪除順序表中"多余"的數(shù)據(jù)元素，即使操作之后的順序表中所有元素的值都不相同。

第四十三頁，共九十九頁，2022年，8月28日算法2.12voidpurge_Sq(SqList&L){

//刪除順序表L中的冗余元素，即使操作之后的順序表中只保留

//操作之前表中所有值都不相同的元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length;++i)//順序考察表中每個(gè)元素

{

j=0;

while(j<=k&&L.elem[j]!=L.elem[i])

++j;//在新表中查詢是否存在和L.elem[i]相同的元素

if(k==-1||j>k)//k=-1表明當(dāng)前考察的是第一個(gè)元素

L.elem[++k]=L.elem[i];

}//for

L.length=k+1;//修改表長

}//purge_Sq

此算法的時(shí)間復(fù)雜度為O(ListLength2(L))

第四十四頁，共九十九頁，2022年，8月28日分析：

算法中的基本操作為"比較"，控制結(jié)構(gòu)為兩重循環(huán)，外循環(huán)的執(zhí)行次數(shù)和順序表的表長相同，內(nèi)循環(huán)的執(zhí)行次數(shù)則不超過表長。此外，"比較"操作相對(duì)于"移動(dòng)"操作所需的時(shí)間也少。

從這個(gè)題的算法可以得到一些有益的啟示，某種情況下，"刪除"操作也可利用"插入"來實(shí)現(xiàn)。第四十五頁，共九十九頁，2022年，8月28日2.3.1單鏈表和指針

線性表的鏈?zhǔn)酱鎯?chǔ)表示的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的）。因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）。由這兩部分信息組成一個(gè)"結(jié)點(diǎn)"（如下圖所示），表示線性表中一個(gè)數(shù)據(jù)元素ai

其中存儲(chǔ)數(shù)據(jù)元素信息的域稱作數(shù)據(jù)域（設(shè)域名為data），存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域（設(shè)域名為next）。指針域中存儲(chǔ)的信息又稱做指針或鏈。數(shù)據(jù)域data指針域next第四十六頁，共九十九頁，2022年，8月28日由分別表示a1,a2,…,an的N個(gè)結(jié)點(diǎn)依次相鏈構(gòu)成的鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)表示，由于此類鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，故又稱單鏈表或線性鏈表，如下圖所示。和順序表類似，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中仍以第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的基地址，通常稱它為頭指針，線性表中所有數(shù)據(jù)元素都可以從頭指針出發(fā)找到。因?yàn)榫€性表的最后一個(gè)數(shù)據(jù)元素沒有后繼，因此最后一個(gè)結(jié)點(diǎn)中的"指針"是一個(gè)特殊的值"NULL"（在圖上用∧表示），通常稱它為"空指針"。第四十七頁，共九十九頁，2022年，8月28日為了便于處理一些特殊情況，在第一個(gè)結(jié)點(diǎn)之前附加一個(gè)"頭結(jié)點(diǎn)"，令該結(jié)點(diǎn)中指針域的指針指向第一個(gè)元素結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)，如下圖所示。

值得注意的是，若線性表為空，在不帶頭結(jié)點(diǎn)的情況下，頭指針為空(NULL)，但在帶頭結(jié)點(diǎn)的情況下，鏈表的頭指針不為空，而是其頭結(jié)點(diǎn)中指針域的指針為空，如下圖所示。

第四十八頁，共九十九頁，2022年，8月28日可以用C語言中的“結(jié)構(gòu)指針”來描述鏈表結(jié)構(gòu)typedefstructLNode{

ElemTypedata;

structLNode*next;

}*SLink;

若設(shè)LNode*p,*q;

SLinkH;

則p，q和H均為以上定義的指針型變量。若p的值非空，則表明p指向某個(gè)結(jié)點(diǎn)，p->data表示p所指結(jié)點(diǎn)中的數(shù)據(jù)域，p->next表示p所指結(jié)點(diǎn)中的指針域，若非空，則指向其"后繼"結(jié)點(diǎn)。第四十九頁，共九十九頁，2022年，8月28日指針型變量只能作同類型的指針賦值與比較操作。并且，指針型變量的"值"除了由同類型的指針變量賦值得到外，都必須用C語言中的動(dòng)態(tài)分配函數(shù)得到。例如，p=newLNode;表示在運(yùn)行時(shí)刻系統(tǒng)動(dòng)態(tài)生成了一個(gè)LNode類型的結(jié)點(diǎn)，并令指針p"指向"該結(jié)點(diǎn)。反之，當(dāng)指針p所指結(jié)點(diǎn)不再使用，可用deletep;釋放此結(jié)點(diǎn)空間。第五十頁，共九十九頁，2022年，8月28日2.3.2單鏈表中基本操作的實(shí)現(xiàn)

以下重點(diǎn)討論線性表的五個(gè)基本操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)。

一、初始化操作

根據(jù)上一節(jié)的約定，初始化建一個(gè)空的鏈表即為建立一個(gè)只有頭結(jié)點(diǎn)的鏈表。算法2.13voidInitList(SLink&L){

//創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表,L為指向頭結(jié)點(diǎn)的指針

L=newLNode;

if(!L)exit(1);//存儲(chǔ)空間分配失敗

L->next=NULL;}//nitList

算法的時(shí)間復(fù)雜度為O(1)。第五十一頁，共九十九頁，2022年，8月28日二、銷毀結(jié)構(gòu)操作算法2.14voidDestroyList(SLink&L){

//銷毀以L為頭指針的單鏈表，釋放鏈表中所有結(jié)點(diǎn)空間

while(L)

{

p=L;

L=L->next;

deletep;

}//while

L=NULL;}//DestroyList

算法的時(shí)間復(fù)雜度為O(Listlength(L))。第五十二頁，共九十九頁，2022年，8月28日三、存取元素操作

單鏈表是一種“順序存取”的結(jié)構(gòu)，即：為取第i元素，首先必須先找到第i-1個(gè)元素。因此不論i值為多少，都必須從頭結(jié)點(diǎn)開始起“點(diǎn)數(shù)“，直數(shù)到第i個(gè)為止。頭結(jié)點(diǎn)可看成是第0個(gè)結(jié)點(diǎn)。第五十三頁，共九十九頁，2022年，8月28日算法2.15boolGetElem(SLinkL,intpos,ElemType&e){//若1≤pos≤LengthList(L)，則用e帶回指針L指向頭結(jié)點(diǎn)的單鏈表//中第pos個(gè)元素的值且返回函數(shù)值為TRUE,否則返回函數(shù)值為FALSE

p=L->next;j=1;//變量初始化，p指向第一個(gè)結(jié)點(diǎn)

while(p&&j<pos)

{//順結(jié)點(diǎn)的指針向后查找，直至p指到第pos個(gè)結(jié)點(diǎn)或p為空止

p=p->next;++j;

}//while

if(!p||j>pos)returnFALSE;//鏈表中不存在第pos個(gè)結(jié)點(diǎn)

e=p->data;//取到第pos個(gè)元素

returnTRUE;

}//GetElem

算法的時(shí)間復(fù)雜度為O(ListLength(L))。第五十四頁，共九十九頁，2022年，8月28日四、插入元素操作

前面已經(jīng)分析過，在線性表中“插入”一個(gè)元素時(shí)，使元素之間的關(guān)系<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>。當(dāng)用指針指示后繼元素時(shí)，實(shí)現(xiàn)這種關(guān)系的改變就很容易了，只要修改相應(yīng)指針即可。因?yàn)樾碌脑夭迦朐诰€性表的第i個(gè)元素之前，使得ai不再是ai-1的后繼，而是新的元素e的后繼，因此需要修改元素e和元素ai-1所在結(jié)點(diǎn)的指針。

由此，算法的基本思想就是，首先找到第i-1個(gè)結(jié)點(diǎn)，然后修改相應(yīng)指針。第五十五頁，共九十九頁，2022年，8月28日算法2.16boolListInsert(SLink&L,intpos,ElemTypee){

//若1≤pos≤LengthList(L)+1，則在指針L指向頭結(jié)點(diǎn)的單鏈表

//的第pos個(gè)元素之前插入新的元素e，且返回函數(shù)值為TRUE,

//否則不進(jìn)行插入且返回函數(shù)值為FALSE

p=L;j=0;

while(p&&j<pos-1)

{//查找第pos-1個(gè)結(jié)點(diǎn)，并令指針p指向該結(jié)點(diǎn)

p=p->next;++j;

}//while

if(!p||j>pos-1)

returnFALSE;//參數(shù)不合法，pos小于1或者大于表長+1

s=newLNode;

if(!s)exit(1);//存儲(chǔ)空間分配失敗

s->data=e;//創(chuàng)建新元素的結(jié)點(diǎn)

s->next=p->next;p->next=s;//修改指針

returnTRUE;

}//ListInsert算法時(shí)間復(fù)雜度為O(ListLength(L))。第五十六頁，共九十九頁，2022年，8月28日五、刪除元素操作

和插入類似，由于刪除元素ai改變了元素之間的關(guān)系，使ai+1不再是ai的后繼，而是ai-1的后繼，因此需要修改元素ai-1所在結(jié)點(diǎn)的指針。因此在單鏈表中刪除元素操作的算法基本思想和插入相同，也是：首先找到第i-1個(gè)結(jié)點(diǎn)，然后修改相應(yīng)指針。第五十七頁，共九十九頁，2022年，8月28日算法2.17boolListDelete(SLink&L,intpos,ElemType&e){

//若1≤pos≤LengthList(L)，則刪除指針L指向頭結(jié)點(diǎn)的單鏈表

//中第pos個(gè)元素并以e帶回其值，返回函數(shù)值為TRUE，

//否則不進(jìn)行刪除操作且返回函數(shù)值為FALSE

p=L;j=0;

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

{//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)

p=p->next;++j;

}

if(!(p->next)||j>i-1)

returnFALSE;//刪除位置不合理

q=p->next;p->next=q->next;//修改指針

e=q->data;delete(q);//釋放結(jié)點(diǎn)空間

returnTRUE;}//ListDelete_L算法時(shí)間復(fù)雜度為O(ListLength(L))。第五十八頁，共九十九頁，2022年，8月28日2.3.3單鏈表其它算法舉例

例2-7

逆序創(chuàng)建鏈表假設(shè)線性表(a1，a2，…，an)的數(shù)據(jù)元素存儲(chǔ)在一維數(shù)組A[n]中，則從數(shù)組的最后一個(gè)分量起，依次生成結(jié)點(diǎn)，并逐個(gè)插入到一個(gè)初始為"空"的鏈表中。第五十九頁，共九十九頁，2022年，8月28日算法2.19voidCreateList_L(SLink&L,intn,ElemTypeA[]){

//已知數(shù)組A中存有線性表的n個(gè)數(shù)據(jù)元素，

//逆序建立帶頭結(jié)點(diǎn)的單鏈表。

L=newLNode;

if(!L)exit(1);//存儲(chǔ)空間分配失敗

L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的空的單鏈表

for(i=n;i>0;--i)

{p=newLNode;

if(!p)exit(1);//存儲(chǔ)空間分配失敗

p->data=A[i-1];//賦元素值

p->next=L->next;L->next=p;//插入在頭結(jié)點(diǎn)之后

}//for

}//CreateList_L容易看出，算法的時(shí)間復(fù)雜度為O(ListLength(L))。第六十頁，共九十九頁，2022年，8月28日例2-8以鏈表作存儲(chǔ)結(jié)構(gòu)解例2-5的問題，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。

解題分析：

因?yàn)閷?duì)鏈表來說，“插入”和“刪除”僅需修改指針即可完成，并且由于前m個(gè)元素之間和后n個(gè)元素之間的鏈接關(guān)系分別都不需要改變，則算法的實(shí)際操作為：

第六十一頁，共九十九頁，2022年，8月28日算法2.20

voidexchange_L(SLink&L，intm)

{

//本算法實(shí)現(xiàn)單鏈表中前m個(gè)結(jié)點(diǎn)和后n個(gè)結(jié)點(diǎn)的互換

if(m&&L->next)//鏈表不空且m!=0

{

p=L->next;k=1;

while(k<m&&p)//查找所在結(jié)點(diǎn)

{

p=p->next;++k;

}//while

if(p&&p->next)//n!=0時(shí)才需要修改指針

{

ha=L->next;//以指針ha記結(jié)點(diǎn)的位置

L->next=p->next;//將結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后

p->next=NULL;//設(shè)的后繼為空

q=L->next;//令q指向結(jié)點(diǎn)

while(q->next)q=q->next;//查找結(jié)點(diǎn)

q->next=ha;//將結(jié)點(diǎn)鏈接到結(jié)點(diǎn)之后

}//if(p)

}//if(m)

}//exchange_L

算法的時(shí)間復(fù)雜度為O(ListLength(L))。第六十二頁，共九十九頁，2022年，8月28日例2-9

編寫算法刪除單鏈表中"多余"的數(shù)據(jù)元素，即使操作之后的單鏈表中所有元素的值都不相同。

解題分析：

可以和順序表采用同樣算法，即設(shè)想新建一個(gè)鏈表，然后順序考察原鏈表中每一個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素，在"新表"中進(jìn)行查找，如果有相同的則舍棄之，否則就插入到新表中。

第六十三頁，共九十九頁，2022年，8月28日算法2.21

voidpurge_L(SLink&L)

{

//刪除單鏈表L中的冗余元素，即使操作之后的單鏈表中只保留

//操作之前表中所有值都不相同的元素

p=L->next;

L->next=NULL;;//設(shè)新表為空表

while(p)//順序考察原表中每個(gè)元素

{

succ=p->next;//記下結(jié)點(diǎn)*p的后繼

q=L->next;//q指向新表的第一個(gè)結(jié)點(diǎn)

while(q&&p->data!=q->data)q=q->next;

//在新表中查詢是否存在和p->data相同的元素

if(!q)//將結(jié)點(diǎn)*p插入到新的表中

{

p->next=L->next;

L->next=p;

}

elsedeletep;//釋放結(jié)點(diǎn)*p

p=succ;

}//for

}//purge_L

此算法的時(shí)間復(fù)雜度為O(ListLength2(L))。第六十四頁，共九十九頁，2022年，8月28日從以上對(duì)鏈表的各種操作的討論可知，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)勢在于：

(1)能有效利用存儲(chǔ)空間；因?yàn)樗莿?dòng)態(tài)存儲(chǔ)分配的結(jié)構(gòu)，不需要預(yù)先為線性表分配足夠大的空間，而是向系統(tǒng)"隨用隨取"，并且在刪除元素時(shí)可同時(shí)釋放空間。(2)用"指針"指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行"插入"、"刪除"等操作；而其劣勢則是不能隨機(jī)存取數(shù)據(jù)元素。同時(shí)，它還丟失了一些順序表有的長處，如線性表的"表長"和數(shù)據(jù)元素在線性表中的"位序"，在上述的單鏈表中都看不見了。又如，不便于在表尾插入元素，需遍歷整個(gè)表才能找到插入的位置。第六十五頁，共九十九頁，2022年，8月28日

為了更突出鏈表的優(yōu)勢，需改進(jìn)單鏈表結(jié)構(gòu)的定義。除了保留指向頭結(jié)點(diǎn)的指針外，還應(yīng)增設(shè)"尾指針"和"表長"兩個(gè)屬性，同時(shí)，我們從上面討論的鏈表基本操作的實(shí)現(xiàn)算法中可以看出，在對(duì)鏈表進(jìn)行操作時(shí)，經(jīng)常需要一個(gè)指針在鏈表中巡游，由此可以設(shè)想，如果將這個(gè)在操作中進(jìn)行巡游的"指針"以及它所指結(jié)點(diǎn)的數(shù)據(jù)元素在線性表中的"位序"納入鏈表結(jié)構(gòu)中，作為鏈表定義中的兩個(gè)成員，必然會(huì)對(duì)鏈表的操作帶來很多方便。

由此，在實(shí)際使用鏈表時(shí)需重新考慮鏈表結(jié)構(gòu)的定義并重新設(shè)計(jì)操作界面。詳細(xì)情況將留在2.5節(jié)進(jìn)行討論。第六十六頁，共九十九頁，2022年，8月28日2.3.4循環(huán)鏈表

循環(huán)鏈表(CircularLinkedList)是線性表的另一種形式的鏈?zhǔn)酱鎯?chǔ)表示。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)，并且將頭指針設(shè)成指向最后一個(gè)結(jié)點(diǎn)。空的循環(huán)鏈表由只含一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。第六十七頁，共九十九頁，2022年，8月28日

循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是"后繼是否為空"，而是"后繼是否為頭結(jié)點(diǎn)"。第六十八頁，共九十九頁，2022年，8月28日2.3.5雙向鏈表

顧名思義，雙向鏈表(DoubleLinkedList)的特點(diǎn)是其結(jié)點(diǎn)結(jié)構(gòu)中含有兩個(gè)指針域，其一指向數(shù)據(jù)元素的"直接后繼"，另一指向數(shù)據(jù)元素的"直接前驅(qū)"，用C語言描述如下：

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLink;

第六十九頁，共九十九頁，2022年，8月28日

與單鏈表類似，雙向鏈表也是由指向頭結(jié)點(diǎn)的頭指針唯一確定，若將頭尾結(jié)點(diǎn)鏈接起來則構(gòu)成雙向循環(huán)鏈表?？盏碾p向循環(huán)鏈表則由只含一個(gè)自成雙環(huán)的頭結(jié)點(diǎn)表示。

第七十頁，共九十九頁，2022年，8月28日2.3.5雙向鏈表

在雙向鏈表上進(jìn)行操作基本上和單向鏈表相同，例如，查找結(jié)點(diǎn)也是要從頭指針指示的頭結(jié)點(diǎn)開始，但插入和刪除時(shí)必須同時(shí)修改兩個(gè)方向上的指針，它們的算法分別如下所示。

第七十一頁，共九十九頁，2022年，8月28日算法2.22

voidListInsert_DuL(DuLink&L,DuLNode*p,DuLNode*s)

{

//在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中結(jié)點(diǎn)*p之后插入結(jié)點(diǎn)*s

s->next=p->next;p->next=s;

s->next->prior=s;s->prior=p;

}//ListInsert_DuL

第七十二頁，共九十九頁，2022年，8月28日算法2.23

voidListDelete_DuL(DuLink&L,DuNode*p,ElemType&e)

{

//刪除帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中結(jié)點(diǎn)*p的后繼，

//并以e返回它的數(shù)據(jù)元素

q=p->next;e=q->data;

p->next=q->next;

p->next->prior=p;

deleteq;

}//ListDelete_DuL第七十三頁，共九十九頁，2022年，8月28日2.4.1有序表的定義

若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，則稱該線性表為有序表(OrderedList)。

有序表的"有序"特性可以給某些操作帶來很大方便，在某些應(yīng)用問題中，如果用有序表而不是線性表將使算法的時(shí)間復(fù)雜度下降。第七十四頁，共九十九頁，2022年，8月28日例2-10

編寫算法刪除有序順序表中“多余”的數(shù)據(jù)元素，即使操作之后的有序順序表中所有元素的值都不相同。

算法2.24

voidpurge_OL(SqList&L)

{

//刪除有序順序表L中的冗余元素，即使操作之后的有序順序表中

//只保留操作之前表中所有值都不相同的元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length-1;++i)//順序考察表中每個(gè)元素

{

if(k==-1||L.elem[k]!=L.elem[i])

L.elem[++k]=L.elem[i];//在新表中不存在和L.elem[i]相同的元素

}//for

L.length=k+1;//修改表長

}//purge_OL

顯然，此算法的時(shí)間復(fù)雜度為O(ListLength(L))。第七十五頁，共九十九頁，2022年，8月28日2.4.1有序表的定義

例2-11

已知兩個(gè)鏈表（頭指針分別為La和Lb）中的數(shù)據(jù)元素均自小至大有序，編寫算法將這兩個(gè)鏈表歸并為一個(gè)鏈表。第七十六頁，共九十九頁，2022年，8月28日算法2.25

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)

{

//已知單鏈線性表La和Lb的元素按值非遞減排列。本算法

//歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按

//值非遞減排列。操作之后La和Lb消失

pa=La->next;pb=Lb->next;

Lc=rc=newLNode;//建空表，Lc為頭指針while(pa&&pb)

{

if(pa->data<=pb->data)

{//將*pa插入Lc表，指針pa后移

rc->next=pa;rc=pa;pa=pa->next;

}//if

else

{//將*pb插入Lc表，指針pb后移

rc->next=pb;rc=pb;pb=pb->next;

}//else

}//whilerc->next=pa?pa:pb;//插入剩余段

delete(La);delete(Lb);//釋放La和Lb的頭結(jié)點(diǎn)

}//MergeList_L

顯然，此算法的時(shí)間復(fù)雜度為O(ListLength(La)+ListLength(Lb))。第七十七頁，共九十九頁，2022年，8月28日2.4.2有序表的基本操作

有序表類型的基本操作和線性表類型中定義的基本操作基本相同，但由于LocateElem中函數(shù)參數(shù)compare的類型不同，（在有序表中，元素相互比較的結(jié)果將產(chǎn)生三種結(jié)果："小于"、"等于"和"大于"），則該函數(shù)的定義和實(shí)現(xiàn)的算法也就和線性表中的不同。

LocateElem(L,e,&q,int(*compare)(ElemType,ElemType))

初始條件：有序表L已存在，compare為有序判定函數(shù)。

操作結(jié)果：若有序表L中存在元素e，則q指示L中第一個(gè)值為e的元素的位置，并返回函數(shù)值TRUE；否則q指示第一個(gè)大于e的元素的前驅(qū)的位置，并返回函數(shù)值FALSE。

此外，在有序表中進(jìn)行"插入"操作時(shí)必須保持表的有序性。也就是說，在有序表中進(jìn)行插入時(shí)首先要查找插入位置，顯然，上述函數(shù)返回的位置即為插入位置，即應(yīng)插入在q指示的元素之后。第七十八頁，共九十九頁，2022年，8月28日2.5.1有序鏈表類型

//結(jié)構(gòu)定義

typedef

structLNode{//結(jié)點(diǎn)結(jié)構(gòu)

ElemTypedata;

structLNode*next;

}

*SLink;

typedef

struct

{//鏈表結(jié)構(gòu)

SLinkhead,//指向有序鏈表中的頭結(jié)點(diǎn)

tail,//指向有序鏈表中最后一個(gè)結(jié)點(diǎn)

curPtr;//指向操作的當(dāng)前結(jié)點(diǎn)，稱為“當(dāng)前指針”

intlength,//指示有序鏈表的長度

curPos;//指示當(dāng)前指針?biāo)附Y(jié)點(diǎn)的位序

}

OrderedLinkList;第七十九頁，共九十九頁，2022年，8月28日//基本操作接口(函數(shù)聲明)

boolMakeNode(SLink&p,ElemTypee);

//生成一個(gè)數(shù)據(jù)元素和e相同的新結(jié)點(diǎn)*p，并返回TRUE,若存儲(chǔ)分配失敗，

//則返回

FALSE。

boolInitList(OrderedLinkList&L);

//構(gòu)造一個(gè)空的有序鏈表L，若存儲(chǔ)分配失敗，令L.head為空并返回FALSE，

//否則返回TRUE。

voidDestroyList(OrderedLinkList&L);

//銷毀有序鏈表L，L不再存在。

boolListEmpty(OrderedLinkListL);

//若有序鏈表L為空表，則返回TRUE，否則返回FALSE。第八十頁，共九十九頁，2022年，8月28日

intListLength(OrderedLinkListL);

//返回有序鏈表L中元素個(gè)數(shù)。

SLinkPriorPos(OrderedLinkListL);

//移動(dòng)有序鏈表L中當(dāng)前指針到它當(dāng)前所指結(jié)點(diǎn)的直接前驅(qū)并返回。

SLinkNextPos(OrderedLinkListL);

//移動(dòng)有序鏈表L中當(dāng)前指針到它當(dāng)前所指結(jié)點(diǎn)的直接后繼并返回。

boolGetPos(OrderedLinkListL,intpos);

//若1≤pos≤LengthList(L)，則移動(dòng)當(dāng)前指針指向第pos個(gè)結(jié)點(diǎn)

//且返回函數(shù)值為TRUE，否則不移動(dòng)當(dāng)前指針且返回函數(shù)值為FALSE。第八十一頁，共九十九頁，2022年，8月28日

voidGetCurElem(OrderedLinkListL,ElemType&e);

//以e帶回當(dāng)前指針?biāo)附Y(jié)點(diǎn)中的數(shù)據(jù)元素。

boolLocateElem(OrderedLinkListL,ElemTypee,

int(*compare)(ElemType,ElemType));

//若有序鏈表L中存在和e相同的數(shù)據(jù)元素,則當(dāng)前指針指向第1個(gè)和e相同的結(jié)點(diǎn)，

//并返回TRUE，否則當(dāng)前指針指向第一個(gè)大于e的元素的前驅(qū)，并返回FALSE。

voidListTraverse(LinkListL,void(*visit)());

//依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。

voidClearList(LinkList&L);

//將有序鏈表L重置為空表，并釋放原鏈表的結(jié)點(diǎn)空間。第八十二頁，共九十九頁，2022年，8月28日

voidSetcurElem(LinkListL,ElemTypee);

//將有序鏈表L中當(dāng)前指針?biāo)附Y(jié)點(diǎn)中的數(shù)據(jù)元素修改為和e相同。

voidInsAfter(LinkList&L,SLinks);

//在有序鏈表L中當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后插入一個(gè)新的結(jié)點(diǎn)*s

//并移動(dòng)當(dāng)前指針指向新插入的結(jié)點(diǎn)。

boolDelAfter(LinkList&L,ElemType&e);

//若當(dāng)前指針?biāo)阜菃捂湵鞮中最后一個(gè)結(jié)點(diǎn)，則刪除當(dāng)前指針?biāo)附Y(jié)點(diǎn)之后的

//結(jié)點(diǎn),以e帶回它的數(shù)據(jù)元素并返回TRUE,否則不進(jìn)行刪除操作且返回FALSE。第八十三頁，共九十九頁，2022年，8月28日其中部分操作的偽碼算法如下：

boolMakeNode(SLink&p,ElemTypee)

{

//生成一個(gè)數(shù)據(jù)元素和e相同的新結(jié)點(diǎn)*p，并返回TRUE，

//若存儲(chǔ)分配失敗，則返回FALSE。

p=newLNode;

if(!p)returnFALSE;

p->data=e;p->next=NULL;

returnTRUE;

}

第八十四頁，共九十九頁，2022年，8月28日boolInitList(OrderedLinkList&L)