第二章數(shù)據(jù)結構教案

第二章數(shù)據(jù)結構教案1第1頁，課件共147頁，創(chuàng)作于2023年2月第二章線性表

線性表是一種最簡單的線性結構。什么是線性結構？簡單地說，線性結構是一個數(shù)據(jù)元素的有序（次序）集合。它有四個基本特征：1．集合中必存在唯一的一個"第一元素"；2．集合中必存在唯一的一個"最后元素"；3．除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼"；4．除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅"。第2頁，課件共147頁，創(chuàng)作于2023年2月

2.1.1抽象數(shù)據(jù)類型線性表的定義

通常可以下列"n個數(shù)據(jù)元素的序列"表示線性表(Linear_List)(a1,a2,...,ai,...,an)序列中數(shù)據(jù)元素的個數(shù)n定義為線性表的表長；n=0時的線性表被稱為空表。稱i為ai在線性表中的位序。

第3頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義

其抽象數(shù)據(jù)類型的定義如下：ADTList{數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}第4頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義

基本操作：{結構初始化}InitList(&L)操作結果：構造一個空的線性表L。{銷毀結構}DestroyList(&L)初始條件：線性表L已存在。操作結果：銷毀線性表L。第5頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義{引用型操作}ListEmpty(L)初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE。ListLength(L)初始條件：線性表L已存在。操作結果：返回L中元素個數(shù)。第6頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義

PriorElem(L,cur_e,&pre_e)初始條件：線性表L已存在。操作結果：若cur_e是L中的數(shù)據(jù)元素，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義。NextElem(L,cur_e,&next_e)初始條件：線性表L已存在。操作結果：若cur_e是L中的數(shù)據(jù)元素，則用ext_e返回它的后繼，否則操作失敗，next_e無定義。

第7頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義

GetElem(L,i,&e)初始條件：線性表L已存在，1≤i≤LengthList(L)。操作結果：用e返回L中第i個元素的值。LocateElem(L,e,compare())初始條件：線性表L已存在，compare()是元素判定函數(shù)。操作結果：返回L中第1個與e滿足關系compare()的元素的位序。若這樣的元素不存在，則返回值為0。第8頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義

ListTraverse(L,visit())初始條件：線性表L已存在，visit()為元素的訪問函數(shù)。操作結果：依次對L的每個元素調用函數(shù)visit()。一旦visit()失敗，則操作失敗。第9頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義{加工型操作}ClearList(&L)初始條件：線性表L已存在。操作結果：將L重置為空表。PutElem(&L,i,e)初始條件：線性表L已存在，1≤i≤LengthList(L)。操作結果：L中第i個元素賦值同e的值。第10頁，課件共147頁，創(chuàng)作于2023年2月2.1.1抽象數(shù)據(jù)類型線性表的定義

ListInsert(&L,i,e)初始條件：線性表L已存在，1≤i≤LengthList(L)+1。操作結果：在L的第i個元素之前插入新的元素e，L的長度增1。ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，1≤i≤LengthList(L)。操作結果：刪除L的第i個元素，并用e返回其值，L的長度減1。}ADTList第11頁，課件共147頁，創(chuàng)作于2023年2月

2.1.2線性表類型的應用

如果已經實現(xiàn)了上述定義的線性表類型，那么在應用問題的求解中就可以利用類型中定義的各種操作。下面將舉幾個例子說明之。例2-1已知集合A和B，求兩個集合的并集，使A＝A∪B，且B不再單獨存在。第12頁，課件共147頁，創(chuàng)作于2023年2月

2.1.2線性表類型的應用

從集合的觀點看，此問題求解的方法很簡單，只要對集合B中的所有元素一個一個地檢查，看看在集合A中是否存在相同元素，若不存在，則將該元素插入到集合A，否則舍棄之。要在計算機中求解，首先要確定"如何表示集合"。集合可以有多種表示方法，對上述集合求并的問題可以用線性表表示集合。第13頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用

現(xiàn)假設以線性表LA和LB分別表示集合A和B，即構造兩個線性表LA和LB，它們的數(shù)據(jù)元素分別為集合A和B中的成員。由此，上述集合求并的問題便可演繹為：要求對線性表作如下操作：擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。第14頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用具體操作步驟為：1．從線性表LB中取出一個數(shù)據(jù)元素；2．依值在線性表LA中進行查詢；3．若不存在，則將它插入到LA中。重復上述三步直至LB為空表止。那么，其中的每一步能否利用上述線性表類型中定義的基本操作來完成呢？第15頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用容易看出，上述的每一步恰好對應線性表的一個基本操作：1.ListDelete(LB,1,e);2.LocateElem(LA,e,equal());3.ListInsert(LA,n+1,e)第16頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用算法2.1voidunion(List&LA,List&LB){//將所有在線性表LB中但不在LA中的數(shù)據(jù)元//素插入到LA中,//算法執(zhí)行之后，線性表LB不再存在。La_len=ListLength(LA);//求得線性表LA//的長度while(!ListEmpty(LB)){//依次處理LB中//元素直至LB為空表止。第17頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用

ListDelete(LB,1,e);//從LB中刪除第1個數(shù)//據(jù)元素并賦給eif(!LocateElem(LA,e,equal())ListInsert(LA,++La_len,e);//當LA中不存在和e值相同的數(shù)據(jù)元素時進行//插入}//whileDestroyList(LB);//銷毀線性表LB}//union第18頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用

例2-2已知一個“非純集合”B，試構造一個集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。算法2.2

voidpurge(List&LA,ListLB)

{

//構造線性表LA，使其只包含LB中所有值不相//同的數(shù)據(jù)元素,算法不改變線性表LB

第19頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用

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

第20頁，課件共147頁，創(chuàng)作于2023年2月2.1.2線性表類型的應用

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

ListInsert(LA,++La_len,e);

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

}//for

}//purge

第21頁，課件共147頁，創(chuàng)作于2023年2月

2.1.2線性表類型的應用

例2-3判別兩個集合是否相等。

算法2.3

boolisEqual(ListLA,ListLB)

{

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

La_len=Listlength(LA);

Lb_len=Listlength(LB);

第22頁，課件共147頁，創(chuàng)作于2023年2月

2.1.2線性表類型的應用

if(La_len!=Lb_len)returnFALSE;//兩表的長度不等

else

{

i=1;found=TRUE;

while(i<=La_len&&found)

{

GetElem(LA,i,e);

//取得LA中一個元素

第23頁，課件共147頁，創(chuàng)作于2023年2月

2.1.2線性表類型的應用

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

i++;//依次處理下一個

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

}//while

returnfound;

}//else

}//isEqual第24頁，課件共147頁，創(chuàng)作于2023年2月

2.2線性表的順序存儲表示和實現(xiàn)

2.2.1順序表

順序表是線性表的順序存儲表示的簡稱，它指的是，“用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素”，即以“存儲位置相鄰”表示“位序相繼的兩個數(shù)據(jù)元素之間的前驅和后繼的關系(有序對<ai-1，ai>)"，并以表中第一個元素的存儲位置作為線性表的起始地址，稱作線性表的基地址。如下圖所示。

第25頁，課件共147頁，創(chuàng)作于2023年2月

2.2.1順序表

不失一般性，假設每個數(shù)據(jù)元素占據(jù)的存儲量是一個常量C，則后繼元素的存儲地址和其前驅元素相隔一個常量，

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

↑一個數(shù)據(jù)元素所占存儲量

第26頁，課件共147頁，創(chuàng)作于2023年2月

2.2.1順序表

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

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

↑基地址用C語言描述的順序表類型如下所示：

第27頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

//存儲結構

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

typedefstruct{

ElemType*elem;//存儲空間基址

intlength;//當前長度

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

}SqList;//俗稱順序表

第28頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

//基本操作接口(函數(shù)聲明)

voidInitList(SqList&L,intmaxsize);

//構造一個最大存儲容量為maxsize的空的//順序表L。

voidDestroyList(SqList&L)

//銷毀順序表L。第29頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

boolListEmpty(SqListL)

//若順序表L為空表，則返回TRUE，否則//返回FALSE。

intListLength(SqListL)

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

第30頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

intPriorElem(SqListL,ElemTypecur_e)

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

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

intNextElem(SqListL,ElemTypecur_e)

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

//(設最后一個元素的后繼的位序為L的表長+1)，否則//返回-1。第31頁，課件共147頁，創(chuàng)作于2023年2月2.2.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滿足關系compare()的數(shù)//據(jù)元素的位序。若這樣的元素不存在，則返回值為0。

//compare()為數(shù)據(jù)元素的判定函數(shù)。第32頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

voidListTraverse(SqListL,void(*visit)(ElemType))

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

voidClearList(SqList&L)

//將順序表L重置為空表。第33頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

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。第34頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

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

//若1≤pos≤LengthList(L)，則刪除順序表L//的第pos個元素e，L的長度增1，且返回函//數(shù)值為TRUE，否則不改變順序表且返回函//數(shù)值為FALSE。

第35頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

以上定義的函數(shù)可在程序設計中引用，例如，述算法2.2可改寫為下列可在主函數(shù)中調用的函數(shù)。

voidpurge(SqList&La,SqListLb)

{//構造順序表La，使其只包含Lb中所有值//不相同的數(shù)據(jù)元素,算法不改變順序表Lb

boolb;

intLb_len=Listlength(Lb);

//求線性表Lb的長度

第36頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

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()))

第37頁，課件共147頁，創(chuàng)作于2023年2月2.2.1順序表

{

++La_len;

b=ListInsert(La,La_len,e);}//當La中不存在和e值相同的數(shù)據(jù)元//素時，進行插入。

}//for

}//purge第38頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

從順序表的存儲結構定義容易看出，由于順序表的"長度"是個"顯值"，且由于第i個元素恰好存儲在數(shù)組的第i個分量(數(shù)組下標為i-1)中，因此其"求長"、"判空"以及"存取第i個數(shù)據(jù)元素"等操作都很容易實現(xiàn)。下面重點討論順序表類型定義中五個操作的實現(xiàn)。

一、初始化操作

二、元素定位操作

三、插入元素操作

四、刪除元素操作

五、銷毀結構操作

第39頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

一、初始化操作

對順序表而言，"初始化"的實質是為它分配一個"足夠應用"的元素存儲空間，由用戶根據(jù)它對線性表的使用要求定義一個最大存儲容量maxsize，并約定當用戶沒有提出特殊需求(maxsize=0)時，按予設的最大存儲量MAXLISTSIZE進行分配。第40頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

算法2.4

voidInitList(SqList&L,intmaxsize)

{

//構造一個空的線性表L

if(maxsize==0)

maxsize=MAXLISTSIZE;

L.elem=newElemType[maxsize];第41頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

if(!L.elem)exit(1);//存儲分配失敗

L.length=0;//順序表的初始長度為0

L.listsize=maxsize;//該順序表可以存儲//元素的最大容量

}//InitList

此算法的時間復雜度為O(1)。第42頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

二、元素定位操作

在順序表中"查詢"是否存在一個和給定值滿足判定條件的元素的最簡單的辦法是，依次取出結構中的每個元素和給定值進行比較。算法2.5

intLocateElem(SqListL,ElemTypee,

void（*compare)(ElemType,lemType))

第43頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

{//在順序表L中查找第1個值與e滿足判定條件//compare()的元素，若找到，則返回其在L中//的位序，否則返回0。

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

p=L.elem;//p的初值為第1元素的存儲位置

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

++i;//依次進行判定

第44頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

if(i<=L.length)returni;

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

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

}//LocateElem

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

第45頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

三、插入元素操作

首先分析，"插入元素"使線性表的邏輯結構發(fā)生什么變化？

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

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

即：

(1)改變了表中元素之間的關系，使<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>第46頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

(2)表長增1

由于順序表是以"存儲位置相鄰"表示"元素之間的前驅和后繼關系"，則必須"移動元素"來體現(xiàn)"元素之間發(fā)生的變化"。算法2.6

boolListInsert(SqList&L,intpos,ElemTypee)

{

//若存儲空間不滿,且1≤pos≤Listlength(L)+1，//則在順序表L的第pos個元素之前插入新的元//素e且返回TRUE，否則返回FALSE

第47頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

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];

//插入位置及之后的元素右移

第48頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

L.elem[pos-1]=e;//插入e

++L.length;//表長增1

returnTRUE;

}//ListInsert此算法的時間復雜度為：O(ListLength(L))第49頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

四、刪除元素操作

同樣首先分析，“刪除元素”使線性表的邏輯結構發(fā)生什么變化？假設刪除線性表中第i個元素，使得線性表(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,ai+1,…,an)

即：

(1)改變了表中元素之間的關系，使<ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>

第50頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

(2)表長減1

對順序表而言，需要改變從第i+1個元素起到第n個元素的存儲位置，即進行“從第i+1到第n個元素往前移動一個位置”。

算法2.7

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

{//若1≤pos≤Listlength(L)，則以e帶回從順序//表L中刪除的第pos個元素且返回TRUE，

第51頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

//否則返回FALSE

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

returnFALSE;//刪除位置不合法

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

L.elem[j-1]=L.elem[j];//被刪除元素之后//的元素左移第52頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

--L.length;//表長減1

returnTRUE;

}//ListDelete

此算法的時間復雜度為：O(ListLength(L))第53頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

五、銷毀結構操作

算法2.8

voidDestroyList(SqList&L)

{

//釋放順序表L所占存儲空間

delete[]L.elem;

L.listsize=0;

L.length=0;

}//DestroyList_Sq此算法的時間復雜度為：O(1)第54頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

六、插入和刪除操作的性能分析

試問，在順序表中任何一個合法位置上進行"一次"插入或刪除操作時，需要移動的元素個數(shù)的平均值是多少？

令Ein(n)表示在長度為n的順序表中進行一次插入操作時所需進行"移動"元素個數(shù)的期望值（即平均移動個數(shù)），則第55頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

其中，pi是在第i個元素之前插入一個元素的概率，n-i+1是在第i個元素之前插入一個元素時所需移動的元素個數(shù)。由于可能插入的位置i=1,2,3,…,n+1共n+1個，假設在每個位置上進行插入的機會均等，則第56頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

由此，在上述等概率假設的情況下，

第57頁，課件共147頁，創(chuàng)作于2023年2月2.2.2順序表中基本操作的實現(xiàn)

類似地，刪除操作在上述等概率假設的情況下是：

第58頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例例2-4試編寫算法“比較”兩個順序表的大小。

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

第59頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例算法2.9

intcompare(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);第60頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例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))。第61頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例例2-5試設計一個算法，用盡可能少的輔助空間將順序表中前m個元素和后n個元素進行互換，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。算法2.10

voidinvert(ElemType&R[],ints,intt)

{//本算法將數(shù)組R中下標自s到t的元素逆置，//即將（Rs,Rs+1,…,Rt-1,Rt）改變?yōu)?/（Rt,Rt-1,…,Rs+1,Rs）第62頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例for(k=s;k<=(s+t)/2;k++)

{

w=R[k];

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

R[t-k+s]=w;

}//for

}//invert

第63頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例算法2.11

voidexchange(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第64頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例例2-6編寫算法刪除順序表中“多余”的數(shù)據(jù)元素，即使操作之后的順序表中所有元素的值都不相同。算法2.12

voidpurge_Sq(SqList&L)

{

//刪除順序表L中的冗余元素，即使操作之//后的順序表中只保留操作之前表中所有值//都不相同的元素

第65頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例

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

第66頁，課件共147頁，創(chuàng)作于2023年2月2.2.3順序表其它算法舉例此算法的時間復雜度為O(ListLength2(L))

分析：

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

從這個題的算法可以得到一些有益的啟示，某種情況下，"刪除"操作也可利用"插入"來實現(xiàn)。第67頁，課件共147頁，創(chuàng)作于2023年2月2.3線性表的鏈式存儲表示和實現(xiàn)

2.3.1單鏈表和指針

線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。因此，為了表示每個數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。由這兩部分信息組成一個"結點"（如下圖所示），表示線性表中一個數(shù)據(jù)元素ai。數(shù)據(jù)域data指針域next第68頁，課件共147頁，創(chuàng)作于2023年2月2.3.1單鏈表和指針其中存儲數(shù)據(jù)元素信息的域稱作數(shù)據(jù)域（設域名為data），存儲直接后繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。

由分別表示,,…,的N個結點依次相鏈構成的鏈表，稱為線性表的鏈式存儲表示，由于此類鏈表的每個結點中只包含一個指針域，故又稱單鏈表或線性鏈表，如下圖所示。

第69頁，課件共147頁，創(chuàng)作于2023年2月2.3.1單鏈表和指針和順序表類似，在鏈式存儲結構中仍以第一個數(shù)據(jù)元素的存儲地址作為線性表的基地址，通常稱它為頭指針，線性表中所有數(shù)據(jù)元素都可以從頭指針出發(fā)找到。因為線性表的最后一個數(shù)據(jù)元素沒有后繼，因此最后一個結點中的"指針"是一個特殊的值"NULL"（在圖上用∧表示），通常稱它為"空指針"。第70頁，課件共147頁，創(chuàng)作于2023年2月2.3.1單鏈表和指針

為了便于處理一些特殊情況，在第一個結點之前附加一個"頭結點"，令該結點中指針域的指針指向第一個元素結點，并令頭指針指向頭結點，如下圖所示。第71頁，課件共147頁，創(chuàng)作于2023年2月2.3.1單鏈表和指針

值得注意的是，若線性表為空，在不帶頭結點的情況下，頭指針為空(NULL)，但在帶頭結點的情況下，鏈表的頭指針不為空，而是其頭結點中指針域的指針為空，如下圖所示。第72頁，課件共147頁，創(chuàng)作于2023年2月2.3.1單鏈表和指針可以用C語言中的"結構指針"來描述鏈表結構。

typedefstructLNode

{

ElemTypedata;

structLNode*next;

}*SLink;

第73頁，課件共147頁，創(chuàng)作于2023年2月2.3.1單鏈表和指針若設LNode*p,*q;

SLinkH;

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

一、初始化操作

根據(jù)上一節(jié)的約定，初始化建一個空的鏈表即為建立一個只有頭結點的鏈表。第76頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)算法2.13

voidInitList(SLink&L)

{

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

L=newLNode;

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

L->next=NULL;

}//nitList算法的時間復雜度為O(1)。第77頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)二、銷毀結構操作算法2.14

voidDestroyList(SLink&L)

{

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

while(L)

{

p=L;

L=L->next;

deletep;

}//while

L=NULL;

}//DestroyList算法的時間復雜度為O(Listlength(L))。第78頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)三、存取元素操作

單鏈表是一種"順序存取"的結構，即：為取第i元素，首先必須先找到第i-1個元素。因此不論i值為多少，都必須從頭結點開始起"點數(shù)"，直數(shù)到第i個為止。頭結點可看成是第0個結點。

第79頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)算法2.15

boolGetElem(SLinkL,intpos,ElemType&e)

{

//若1≤pos≤LengthList(L)，則用e帶回指針//L指向頭結點的單鏈表中第pos個元素的值且//返回函數(shù)值為TRUE,否則返回函數(shù)值為FALSE

p=L->next;j=1;

//變量初始化，p指向第一個結點

while(p&&j<pos)第80頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)

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

p=p->next;++j;

}//while

if(!p||j>pos)returnFALSE;

//鏈表中不存在第pos個結點

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

returnTRUE;

}//GetElem

算法的時間復雜度為O(ListLength(L))。第81頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)

四、插入元素操作

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

由此，算法的基本思想就是，首先找到第i-1個結點，然后修改相應指針。第82頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)算法2.16

boolListInsert(SLink&L,intpos,ElemTypee)

{

//若1≤pos≤LengthList(L)+1，則在指針L指//向頭結點的單鏈表的第pos個元素之前插入//新的元素e，且返回函數(shù)值為TRUE,否則不//進行插入且返回函數(shù)值為FALSE

p=L;j=0;

第83頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)while(p&&j<pos-1)

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

p=p->next;++j;

}//while

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

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

s=newLNode;

第84頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)if(!s)exit(1);//存儲空間分配失敗

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

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

//修改指針

returnTRUE;

}//ListInsert算法時間復雜度為O(ListLength(L))。第85頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)五、刪除元素操作

和插入類似，由于刪除元素ai改變了元素之間的關系，使ai+1不再是ai的后繼，而是ai-1的后繼，因此需要修改ai-1元素所在結點的指針。因此在單鏈表中刪除元素操作的算法基本思想和插入相同，也是：首先找到第i-1個結點，然后修改相應指針。第86頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)算法2.17

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

{//若1≤pos≤LengthList(L)，則刪除指針L指//向頭結點的單鏈表中第pos個元素并以e帶//回其值，返回函數(shù)值為TRUE，否則不進行//刪除操作且返回函數(shù)值為FALSE

p=L;j=0;

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

第87頁，課件共147頁，創(chuàng)作于2023年2月2.3.2單鏈表中基本操作的實現(xiàn)while(p->next&&j<i-1)

{//尋找第pos個結點，并令p指向其前驅

p=p->next;++j;

}

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

returnFALSE;//刪除位置不合理

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

e=q->data;delete(q);//釋放結點空間

returnTRUE;

}//ListDelete_L算法時間復雜度為O(ListLength(L))。第88頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例例2-7逆序創(chuàng)建鏈表

假設線性表(a1，a2，…，an)的數(shù)據(jù)元素存儲在一維數(shù)組A[n]中，則從數(shù)組的最后一個分量起，依次生成結點，并逐個插入到一個初始為"空"的鏈表中。

第89頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例算法2.19voidCreateList_L(SLink&L,intn,ElemTypeA[])

{

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

//逆序建立帶頭結點的單鏈表。

L=newLNode;

if(!L)exit(1);//存儲空間分配失敗0第90頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例L->next=NULL;//先建立一個帶頭結//點的空的單鏈表

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

{p=newLNode;

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

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

p->next=L->next;L->next=p;

//插入在頭結點之后

}//for

}//CreateList_L容易看出，算法的時間復雜度為O(ListLength(L))第91頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例例2-8以鏈表作存儲結構解例2-5的問題，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。

解題分析：

因為對鏈表來說，"插入"和"刪除"僅需修改指針即可完成，并且由于前m個元素之間和后n個元素之間的鏈接關系分別都不需要改變，則算法的實際操作為：第92頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例(1)從鏈表中刪除(a1,a2,…,am)；

(2)將(b1,b2,…,bn)鏈接到頭結點之后；

(3)將(a1,a2,…,am)鏈接到bn之后。第93頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例

算法2.20

voidexchange_L(SLink&L，intm)

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

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

{

p=L->next;k=1;

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

{

p=p->next;++k;

}//while第94頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例if(p&&p->next)//n!=0時才需要修改指針

{

ha=L->next;

//以指針ha記a1結點的位置

L->next=p->next;

//將b1結點鏈接在頭結點之后

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

q=L->next;//令q指向b1結點第95頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例while(q->next)q=q->next;

//查找bn結點

q->next=ha;

//將a1結點鏈接到bn結點之后

}//if(p)

}//if(m)

}//exchange_L算法的時間復雜度為O(ListLength(L))。第96頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例例2-9編寫算法刪除單鏈表中"多余"的數(shù)據(jù)元素，即使操作之后的單鏈表中所有元素的值都不相同。

解題分析：

可以和順序表采用同樣算法，即設想新建一個鏈表，然后順序考察原鏈表中每一個結點的數(shù)據(jù)元素，在"新表"中進行查找，如果有相同的則舍棄之，否則就插入到新表中。第97頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例算法2.21

voidpurge_L(SLink&L)

{//刪除單鏈表L中的冗余元素，即使操作之后//的單鏈表中只保留操作之前表中所有值都不//相同的元素

p=L->next;

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

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

第98頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例{succ=p->next;//記下結點*p的后繼

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

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

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

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

{

p->next=L->next;

L->next=p;

}

第99頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例elsedeletep;//釋放結點*p

p=succ;

}//while(p)}//purge_L

此算法的時間復雜度為O(ListLength2(L))。第100頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例總結：從以上對鏈表的各種操作的討論可知，鏈式存儲結構的優(yōu)勢在于：

(1)能有效利用存儲空間；(2)用"指針"指示數(shù)據(jù)元素之間的后繼關系，便于進行"插入"、"刪除"等操作；第101頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例而其劣勢則是不能隨機存取數(shù)據(jù)元素。同時，它還丟失了一些順序表有的長處，如線性表的"表長"和數(shù)據(jù)元素在線性表中的"位序"，在上述的單鏈表中都看不見了。又如，不便于在表尾插入元素，需遍歷整個表才能找到插入的位置。第102頁，課件共147頁，創(chuàng)作于2023年2月2.3.3單鏈表其它算法舉例為了更突出鏈表的優(yōu)勢，需改進單鏈表結構的定義。除了保留指向頭結點的指針外，還應增設"尾指針"和"表長"兩個屬性，同時，我們從上面討論的鏈表基本操作的實現(xiàn)算法中可以看出，在對鏈表進行操作時，經常需要一個指針在鏈表中巡游，由此可以設想，如果將這個在操作中進行巡游的"指針"以及它所指結點的數(shù)據(jù)元素在線性表中的"位序"納入鏈表結構中，作為鏈表定義中的兩個成員，必然會對鏈表的操作帶來很多方便。第103頁，課件共147頁，創(chuàng)作于2023年2月2.3.4循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)是線性表的另一種形式的鏈式存儲表示。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表成為一個由鏈指針相鏈接的環(huán)，并且將頭指針設成指向最后一個結點。空的循環(huán)鏈表由只含一個自成循環(huán)的頭結點表示。第104頁，課件共147頁，創(chuàng)作于2023年2月2.3.4循環(huán)鏈表第105頁，課件共147頁，創(chuàng)作于2023年2月2.3.4循環(huán)鏈表循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于，判別鏈表中最后一個結點的條件不再是"后繼是否為空"，而是"后繼是否為頭結點"。第106頁，課件共147頁，創(chuàng)作于2023年2月2.3.5雙向鏈表顧名思義，雙向鏈表(DoubleLinkedList)的特點是其結點結構中含有兩個指針域，其一指向數(shù)據(jù)元素的"直接后繼"，另一指向數(shù)據(jù)元素的"直接前驅"，用C語言描述如下：typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLink第107頁，課件共147頁，創(chuàng)作于2023年2月2.3.5雙向鏈表與單鏈表類似，雙向鏈表也是由指向頭結點的頭指針唯一確定，若將頭尾結點鏈接起來則構成雙向循環(huán)鏈表。空的雙向循環(huán)鏈表則由只含一個自成雙環(huán)的頭結點表示。第108頁，課件共147頁，創(chuàng)作于2023年2月2.3.5雙向鏈表在雙向鏈表上進行操作基本上和單向鏈表相同，例如，查找結點也是要從頭指針指示的頭結點開始，但插入和刪除時必須同時修改兩個方向上的指針，它們的算法分別如下所示。

算法2.22voidListInsert_DuL(DuLink&L,DuLNode*p,DuLNode*s)

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

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

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

}//ListInsert_DuL

第109頁，課件共147頁，創(chuàng)作于2023年2月2.3.5雙向鏈表算法2.23voidListDelete_DuL(DuLink&L,DuNode*p,ElemType&e)

{

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

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

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

p->next=q->next;

p->next->prior=p;

deleteq;

}//ListDelete_DuL第110頁，課件共147頁，創(chuàng)作于2023年2月2.4有序表的類型定義2.4.1有序表的定義

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

有序表的"有序"特性可以給某些操作帶來很大方便，在某些應用問題中，如果用有序表而不是線性表將使算法的時間復雜度下降。

第111頁，課件共147頁，創(chuàng)作于2023年2月2.4.1有序表的定義例2-10編寫算法刪除有序順序表中“多余”的數(shù)據(jù)元素，即使操作之后的有序順序表中所有元素的值都不相同。

算法2.24

voidpurge_OL(SqList&L)

{

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

//只保留操作之前表中所有值都不相同的元素第112頁，課件共147頁，創(chuàng)作于2023年2月2.4.1有序表的定義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))。第113頁，課件共147頁，創(chuàng)作于2023年2月2.4.1有序表的定義例2-11已知兩個鏈表（頭指針分別為La和Lb）中的數(shù)據(jù)元素均自小至大有序，編寫算法將這兩個鏈表歸并為一個鏈表。

算法2.25voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)

{

//已知單鏈線性表La和Lb的元素按值非遞減排列。本算//法歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按

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

第114頁，課件共147頁，創(chuàng)作于2023年2月2.4.1有序表的定義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

第115頁，課件共147頁，創(chuàng)作于2023年2月2.4.1有序表的定義

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

delete(La);delete(Lb);//釋放La和Lb的頭結點}//MergeList_L

顯然，此算法的時間復雜度為

O(ListLength(La)+ListLength(Lb))。第116頁，課件共147頁，創(chuàng)作于2023年2月2.4.2有序表的基本操作2.4.2有序表的基