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

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

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

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

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

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

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

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

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

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

ADTList{

數(shù)據(jù)對象：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)造一個空的線性表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中元素個數(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個元素的值。第六頁，共九十九頁，2022年，8月28日LocateElem(L,e,compare())

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

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

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

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

操作結(jié)果：依次對L的每個元素調(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個元素賦值同e的值。第八頁，共九十九頁，2022年，8月28日ListInsert(&L,i,e)

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

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

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

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

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

已知集合

A和

B，求兩個集合的并集，使

A＝A∪B，且

B不再單獨存在。

從集合的觀點看，此問題求解的方法很簡單，只要對集合

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

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

A，否則舍棄之。

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

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

LA和

LB分別表示集合

A和

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

LA和

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

A和

B中的成員。

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

LA，將存在于線性表

LB中而不存在于線性表

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

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

1．從線性表

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

2．依值在線性表

LA中進行查詢；

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

LA中。

重復上述三步直至

LB為空表止。

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

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個數(shù)據(jù)元素并賦給e

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

ListInsert(LA,++La_len,e);

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

}//while

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

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

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

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

A中的元素相比較。

如果還是以線性表

LB和

LA分別表示"集合"B和

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

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

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

A的同時，原來的集合

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

voidpurge(List&LA,ListLB)

{

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

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

InitList(LA);

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

LA

La_len=0;

Lb_len=ListLength(LB);

//求線性表

LB的長度

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

LB中每個元素

{

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

LB中第

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

e

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

ListInsert(LA,++La_len,e);

//當

LA中不存在和

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

}//for

)//purge

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

判別兩個集合是否相等。

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

由此，"判別兩個線性表中的數(shù)據(jù)元素是否完全相同"的算法的基本思想為：首先判別兩者的表長是否相等；在表長相等的前提下，如果對于一個表中的所有元素，都能在另一個表中找到和它相等的元素的話，便可得到"兩個線性表表示的集合相等"的結(jié)論；反之，只要有一個元素在另一個表中不能找到相等元素時，便可得出"不等"的結(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中一個元素

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

i++;

//依次處理下一個

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

}//while

returnfound;

}//else

)//isEqual

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

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

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

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

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

↑基地址

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

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

const

intMAXLISTSIZE=80;//預設的存儲空間最大容量

typedefstruct{

ElemType*elem;

//存儲空間基址

intlength;

//當前長度

intlistsize;

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

}

SqList;

//俗稱

順序表

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

voidInitList(SqList&L,intmaxsize);

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

//

銷毀順序表

L。

boolListEmpty(SqListL)

//

若順序表

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

FALSE。

intListLength(SqListL)

//

返回順序表

L中元素個數(shù)。

intPriorElem(SqListL,ElemTypecur_e)

//

若

cur_e是順序表

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

//

(設第一個元素的前驅(qū)的位序為0)，否則返回-1。

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

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

//(設最后一個元素的后繼的位序為L的表長+1)，否則返回-1。boolGetElem(SqListL,intpos,ElemType&e)

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

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

//返回順序表L中第1個與e

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

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

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

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

將順序表

L重置為空表。

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

//

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

L中第

pos個元素

//賦值同

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

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

FALSE。

boolListInsert(SqList&L,intpos,ElemTypee)

//

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

L的

//第

pos個元素之前插入新的元素

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

//

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

FALSE。

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

//

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

L的第

pos個元素

e，

//

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

第二十五頁，共九十九頁，2022年，8月28日以上定義的函數(shù)可在程序設計中引用，例如，上述算法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)建一個空的線性表

La

intLa_len=0;

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

//依次處理

Lb中每個元素

{

b=GetElem(Lb,i,e);

//取Lb中第

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

e

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

{

++La_len;

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

La中不存在和

e值相同的

}

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

}//for

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

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

i個分量(數(shù)組下標為

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

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

一、初始化操作

二、元素定位操作

三、插入元素操作

四、刪除元素操作

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

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

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

maxsize，并約定當用戶沒有提出特殊需求(maxsize=0)時，按予設的最大存儲量

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

voidInitList(SqList&L,intmaxsize)

{

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

if(maxsize==0)

maxsize=MAXLISTSIZE;

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

exit(1);

//存儲分配失敗

L.length=0;

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

L.listsize=maxsize;

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

}//InitList

此算法的時間復雜度為O(1)。

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

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

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

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

//若找到，則返回其在

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

i=1;

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

p=L.elem;

//p的初值為第1元素的存儲位置

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

++i;

//依次進行判定

if(i<=L.length)returni;

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

i個元素

else

return0;

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

}//LocateElem

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

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

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

假設在線性表的第i個元素之前插入一個元素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

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

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

L

的

//第

pos個元素之前插入新的元素

e且返回TRUE，否則返回FALSE

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

returnFALSE;//插入位置不合法

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

//當前存儲空間已滿，無法插入

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

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

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

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

假設刪除線性表中第i個元素，使得線性表

(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

對順序表而言，需要改變從第

i+1個元素起到第

n個元素的存儲位置，即進行"從第

i+1到第

n個元素往前移動一個位置"。第三十四頁，共九十九頁，2022年，8月28日算法2.7boolListDelete(SqList&L,intpos,ElemType&e){//若1≤pos≤Listlength(L)，則以e帶回從順序表L中刪除的//第pos個元素且返回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

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

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

delete[]L.elem;

L.listsize=0;

L.length=0;

}//DestroyList_Sq

此算法的時間復雜度為：O(1)

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

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

算法的基本思想為：若ai=bj，則j增1，之后繼續(xù)比較后繼元素；否則即可得出比較結(jié)果。顯然，j的初值應為0，循環(huán)的條件是j不超出其中任何一個表的范圍。若在循環(huán)內(nèi)不能得出比較結(jié)果，則循環(huán)結(jié)束時有三種可能出現(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

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

第四十頁，共九十九頁，2022年，8月28日算法2.10voidinvert(ElemType&R[],ints,intt){//本算法將數(shù)組R中下標自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){//本算法實現(xiàn)順序表中前m個元素和后n個元素的互換

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)//順序考察表中每個元素

{

j=0;

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

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

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

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

}//for

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

}//purge_Sq

此算法的時間復雜度為O(ListLength2(L))

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

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

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

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

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

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

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

ElemTypedata;

structLNode*next;

}*SLink;

若設LNode*p,*q;

SLinkH;

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

以下重點討論線性表的五個基本操作在鏈式存儲結(jié)構(gòu)中的實現(xiàn)。

一、初始化操作

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

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

L=newLNode;

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

L->next=NULL;}//nitList

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

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

while(L)

{

p=L;

L=L->next;

deletep;

}//while

L=NULL;}//DestroyList

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

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

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

while(p&&j<pos)

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

p=p->next;++j;

}//while

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

e=p->data;//取到第pos個元素

returnTRUE;

}//GetElem

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

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

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

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

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

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

p=L;j=0;

while(p&&j<pos-1)

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

p=p->next;++j;

}//while

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

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

s=newLNode;

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

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

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

returnTRUE;

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

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

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

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

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

p=L;j=0;

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

{//尋找第pos個結(jié)點，并令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é)點空間

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

例2-7

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

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

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

L=newLNode;

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

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

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

{p=newLNode;

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

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

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

}//for

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

解題分析：

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

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

voidexchange_L(SLink&L，intm)

{

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

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

{

p=L->next;k=1;

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

{

p=p->next;++k;

}//while

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

{

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

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

p->next=NULL;//設的后繼為空

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

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

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

}//if(p)

}//if(m)

}//exchange_L

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

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

解題分析：

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

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

voidpurge_L(SLink&L)

{

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

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

p=L->next;

L->next=NULL;;//設新表為空表

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

{

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

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

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

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

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

{

p->next=L->next;

L->next=p;

}

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

p=succ;

}//for

}//purge_L

此算法的時間復雜度為O(ListLength2(L))。第六十四頁，共九十九頁，2022年，8月28日從以上對鏈表的各種操作的討論可知，鏈式存儲結(jié)構(gòu)的優(yōu)勢在于：

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

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

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

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

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

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

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLink;

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

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

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

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

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

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

{

//在帶頭結(jié)點的雙向循環(huán)鏈表L中結(jié)點*p之后插入結(jié)點*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é)點的雙向循環(huán)鏈表L中結(jié)點*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)。

有序表的"有序"特性可以給某些操作帶來很大方便，在某些應用問題中，如果用有序表而不是線性表將使算法的時間復雜度下降。第七十四頁，共九十九頁，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)//順序考察表中每個元素

{

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

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

例2-11

已知兩個鏈表（頭指針分別為La和Lb）中的數(shù)據(jù)元素均自小至大有序，編寫算法將這兩個鏈表歸并為一個鏈表。第七十六頁，共九十九頁，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é)點

}//MergeList_L

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

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

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

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

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

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

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

typedef

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

ElemTypedata;

structLNode*next;

}

*SLink;

typedef

struct

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

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

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

curPtr;//指向操作的當前結(jié)點，稱為“當前指針”

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

curPos;//指示當前指針所指結(jié)點的位序

}

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

boolMakeNode(SLink&p,ElemTypee);

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

//則返回

FALSE。

boolInitList(OrderedLinkList&L);

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

//否則返回TRUE。

voidDestroyList(OrderedLinkList&L);

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

boolListEmpty(OrderedLinkListL);

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

intListLength(OrderedLinkListL);

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

SLinkPriorPos(OrderedLinkListL);

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

SLinkNextPos(OrderedLinkListL);

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

boolGetPos(OrderedLinkListL,intpos);

//若1≤pos≤LengthList(L)，則移動當前指針指向第pos個結(jié)點

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

voidGetCurElem(OrderedLinkListL,ElemType&e);

//以e帶回當前指針所指結(jié)點中的數(shù)據(jù)元素。

boolLocateElem(OrderedLinkListL,ElemTypee,

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

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

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

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

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

voidClearList(LinkList&L);

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

voidSetcurElem(LinkListL,ElemTypee);

//將有序鏈表L中當前指針所指結(jié)點中的數(shù)據(jù)元素修改為和e相同。

voidInsAfter(LinkList&L,SLinks);

//在有序鏈表L中當前指針所指結(jié)點之后插入一個新的結(jié)點*s

//并移動當前指針指向新插入的結(jié)點。

boolDelAfter(LinkList&L,ElemType&e);

//若當前指針所指非單鏈表L中最后一個結(jié)點，則刪除當前指針所指結(jié)點之后的

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

boolMakeNode(SLink&p,ElemTypee)

{

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

//若存儲分配失敗，則返回FALSE。

p=newLNode;

if(!p)returnFALSE;

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

returnTRUE;

}

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