数据结构课件

第一章緒論一、數據結構討論的範疇二、基本概念三、演算法和演算法的量度一、數據結構討論的範疇(數據結構在軟體開發中的地位)系統分析系統設計系統實現系統維護系統設計NiklausWirth

Algorithm

+DataStructures=Programs程式設計:演算法:數據結構:為電腦處理問題編制一組指令集

處理問題的策略問題的數學模型

結構靜力分析計算例如:數值計算的程式設計問題─━線性代數方程組─━環流模式方程

(球面坐標系)全球天氣預報非數值計算的程式設計問題例一:求一組(n個)整數中的最大值演算法:?模型：？基本操作是“比較兩個數的大小”取決於整數值的範圍例二：旅館客房的管理演算法：?模型：?先來先服務佇列例三：鋪設城市的煤氣管道演算法：?模型：?如何規劃使得總投資花費最少？圖概括地說，

數據結構是一門討論“描述現實世界實體的數學模型(非數值計算)及其上的操作在電腦中如何表示和實現”的學科。二、基本概念1、數據與數據結構2、數據類型3、抽象數據類型1、數據與數據結構

所有能被輸入到電腦中，且能被電腦處理的符號(數值、字元等)的集合。數據:是電腦操作的對象的總稱。

是電腦處理的資訊的某種特定的符號表示形式。

是數據（集合）中的一個“個體”,在電腦中通常作為一個整體進行考慮和處理。是數據結構中討論的基本單位。數據元素:如:整數“5”,字元“N”等。

----是不可分割的“原子”

其中每個款項稱為一個“資料項目”它是數據結構中討論的最小單位數據元素也可以由若干款項構成。例如：描述一個學生的數據元素稱之為組合項年月日姓名學號班號性別出生日期入學成績原子項數據結構：帶結構的數據元素的集合有一個特性相同的數據元素的集合，如果在數據元素之間存在一種或多種特定的關係，則稱為一個數據結構。指的是數據元素之間存在的關係例如，當用三個

4位的十進位數表示一個含

12位數的十進位數時，3214,6587,9345

─

a1(3214),a2(6587),a3(9345)則在數據元素a1、a2和a3

之間存在著“次序”關係

a1,a2

、

a2,a3

3214，6587，93456587，3214，9345例如:a1a2a3a2a1a3又例，在2行3列的二維數組中六個元素{a1,a2,a3,a4,a5,a6}之間存在兩個關係:行的次序關係:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a2a3a4a5a6列的次序關係:

若在

6個數據元素{a1,a2,a3,a4,a5,a6}之間存在如下的次序關係:{<ai,ai+1>|i=1,2,3,4,5}

數據結構是相互之間存在著某種邏輯關係的數據元素的集合。可見，不同的“關係”構成不同的“結構”則構成一維數組的定義。從關係或結構分，數據結構可歸結為以下四類:線性結構樹形結構圖狀結構集合結構數據結構包括“邏輯結構”

和“物理結構”兩個方面(層次):邏輯結構

是對數據元素之間的邏輯關係的描述，它可以應一個數據元素的集合和定義在此集合上的若干關係來表示;物理結構是邏輯結構在電腦中的表示和實現，故又稱“存儲結構”。數據結構的形式定義描述為:數據結構是一個二元組Data_Structures=(D,S)其中:D是數據元素的有限集，

S是D上關係的有限集。例如:定義“課題組”為一個數據結構Group=(P,R)P={T,G1,…,Gn,S11,…Snm}R={R1,R2}R1={<T,G1>,…,<T,Gn>}R2={<Gi,Sij>|i=1,…,n,j=1,…,m}數據的存儲結構

——

邏輯結構在記憶體中的映像“數據元素”的映像？“關係”的映像？數據元素的映像方法：用二進位位(bit)的位串表示數據元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關係的映像方法：（表示

x,y

的方法）順序映像以相對的存儲位置表示後繼關係例如:令y的存儲位置和x的存儲位置之間差一個常量C而C是一個隱含值，整個存儲結構中只含數據元素本身的資訊xy鏈式映像以附加資訊(指針)表示後繼關係需要用一個和x在一起的附加資訊指示y的存儲位置yx在不同的編程環境中，存儲結構可有不同的描述方法，當用高級程式設計語言進行編程時，通常可用高級編程語言中提供的數據類型描述之。例如:

以三個帶有次序關係的整數表示一個長整數時，可利用C語言中提供的整數數組類型，

typedefintLong_int[3];定義長整數為:typedefstruct{

inty;//年號Year

intm;//月號Month

intd;//日號Day}DateType;//日期類型定義“日期”為:定義“學生”為:typedefstruct{

charid[8];//學號

charname[16];//姓名

charsex;//性別‘M/F’:男/女

DateTypebdate;//出生日期}Student;//學生類型2、數據類型

在用高級程式語言編寫的程式中，必須對程式中出現的每個變數、常量或運算式，明確說明它們所

屬的數據類型。例如，C

語言中提供的基本數據類型有:整型int浮點型float字元型char邏輯型bool（C++語言）雙精度型double實型（C++語言）

數據類型是一個值的集合和定義在此集合上的一組操作的總稱。

不同類型的變數，其所能取的值的範圍不同，所能進行的操作不同。例如：整型值的範圍是：-32768~32767操作是：+，-，*，/，%各種高級程式設計語言中都擁有“整數”類型，儘管它們在不同處理器上實現的方法不同，但對程式員而言是“相同的”，因為它們的數學特性相同。從“數學抽象”的角度看，可稱它為一個“抽象數據類型”。3、抽象數據類型

(AbstractDataType

簡稱ADT)

是指一個數學模型以及定義在此數學模型上的一組操作例如:“整數”是一個抽象數據類型。

其數學特性和具體的電腦或語言無關。“抽象”的意義在於強調數據類型的數學特性。抽象數據類型還包括用戶在設計軟體系統時自己定義的數據類型。在構造軟體系統的各個相對獨立的模組時，定義一組數據和施與這些數據之上的一組操作，並在模組內部給出它們的表示和實現細節，在模組外部使用的只是抽象的數據和抽象的操作。例如，定義抽象數據類型“複數”

數據對象：

D＝{e1,e2｜e1,e2∈RealSet}

數據關係：

R＝{<e1,e2>|e1是複數的實數部分,

e2

是複數的虛數部分}ADTComplex{基本操作：

InitComplex(&Z,v1,v2)操作結果：構造複數Z,其實部和虛部分別被賦以參數v1和v2的值。

DestroyComplex(&Z)操作結果：複數Z被銷毀。

GetReal(Z,&RealPart)初始條件：複數已存在。操作結果：用RealPart返回複數Z的實部值。

GetImag(Z,&ImagPart)初始條件：複數已存在。操作結果：用ImagPart返回複數Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是複數。操作結果：用sum返回兩個複數z1,z2的和值。}ADTComplex

#include<iostream.h>#include"complex.h"

voidmain()

{

}…

…

complexz1,z2,z3,z4,z; floatRealPart,ImagPart;

InitComplex(z1,8.0,6.0);

InitComplex(z2,4.0,3.0);

Add(z1,z2,z3);

Multiply(z1,z2,z4); if(Division(z4,z3,z)){

GetReal(z,RealPart);

GetImag(z,ImagPart);}//ifADT有兩個重要特徵:數據抽象

用ADT描述程式處理的實體時，強調的是其本質的特徵、其所能完成的功能以及它和外部用戶的介面（即外界使用它的方法）數據封裝

將實體的外部特性和其內部實現細節分離，並且對外部用戶隱藏其內部實現細節抽象數據類型的描述方法抽象數據類型可用（D，S，P）三元組表示其中，D是數據對象，

S是D上的關係集，

P是對D的基本操作集。ADT

抽象數據類型名{

數據對象：〈數據對象的定義〉

數據關係：〈數據關係的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數據類型名其中基本操作的定義格式為:基本操作名（參數表）

初始條件：〈初始條件描述〉

操作結果：〈操作結果描述〉

賦值參數只為操作提供輸入值；引用參數以&打頭，除可提供輸入值外，還將返回操作結果。初始條件描述了操作執行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，並返回相應出錯資訊。操作結果說明了操作正常完成之後，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。抽象數據類型的表示和實現

抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。類C語言詳見10-11頁。例如，對以上定義的複數typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲結構的定義//-----基本操作的函數原型說明voidInitComplex(complex&Z,

floatrealval,floatimagval)；//

構造複數Z,其實部和虛部分別被賦以參數//realval

和imagval

的值float

GetReal(complexZ)；

//返回複數Z的實部值float

GetImag(complexZ)；

//返回複數Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個複數z1,z2的和//-----基本操作的實現voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個複數z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其他省略}三、演算法和演算法的衡量1、演算法2、演算法設計的原則3、演算法效率的衡量方法和準則4、演算法的存儲空間需求

演算法是為了解決某類問題而規定的一個有限長的操作序列。一個演算法必須滿足以下五個重要特性：①有窮性

②確定性③可行性④有輸入⑤有輸出1、演算法①

有窮性對於任意一組合法輸入值，在執行有窮步驟之後一定能結束，即：演算法中的每個步驟都能在有限時間內完成；

②

確定性

對於每種情況下所應執行的操作，在演算法中都有確切的規定，使演算法的執行者或閱讀者都能明確其含義及如何執行。並且在任何條件下，演算法都只有一條執行路徑；③

可行性演算法中的所有操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之；④

有輸入作為演算法加工對象的量值，通常體現為演算法中的一組變數。有些輸入量需要在演算法執行過程中輸入，而有的演算法表面上可以沒有輸入，實際上已被嵌入演算法之中；

⑤

有輸出它是一組與“輸入”有確定關係的量值，是演算法進行資訊加工後得到的結果，這種確定關係即為演算法的功能。2、演算法設計的原則設計演算法時，通常應考慮達到以下目標：①正確性②可讀性③健壯性④高效率與低存儲量需求①

正確性

首先，演算法應當滿足以特定的“規格說明”方式給出的需求。

其次，對演算法是否“正確”的理解可以有以下四個層次：a．程式中不含語法錯誤；b．程式對於幾組輸入數據能夠得出滿足要求的結果；c．程式對於精心選擇的、典型、苛刻且帶有刁難性的幾組輸入數據能夠得出滿足要求的結果；通常以第

c層意義的正確性作為衡量一個演算法是否合格的標準。

d．程式對於一切合法的輸入數據都能得出滿足要求的結果；②可讀性

演算法主要是為了人的閱讀與交流，其次才是為電腦執行。因此演算法應該易於人的理解；另一方面，晦澀難讀的程式易於隱藏較多錯誤而難以調試；③健壯性

當輸入的數據非法時，演算法應當恰當地作出反應或進行相應處理，而不是產生莫名奇妙的輸出結果。並且，處理出錯的方法不應是中斷程式的執行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。④高效率與低存儲量需求

通常，效率指的是演算法執行時間；存儲量指的是演算法執行過程中所需的最大存儲空間。兩者都與問題的規模有關。3、演算法效率的衡量方法和準則通常有兩種衡量演算法效率的方法:

事後統計法事前分析估算法缺點：1。必須執行程式

2。其他因素掩蓋演算法本質和演算法執行時間相關的因素：①演算法選用的策略②問題的規模③編寫程式的語言④編譯程式產生的機器代碼的品質⑤電腦執行指令的速度

一個特定演算法的“運行工作量”的大小，只依賴於問題的規模（通常用整數量n表示），或者說，它是問題規模的函數。

假如，隨著問題規模n的增長，演算法執行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為演算法的(漸近)時間複雜度如何估算演算法的時間複雜度？演算法=控制結構+原操作（固有數據類型的操作）演算法的執行時間

=原操作(i)的執行次數×原操作(i)的執行時間

演算法的執行時間

與

原操作執行次數之和

成正比

從演算法中選取一種對於所研究的問題來說是基本操作

的原操作，以該基本操作在演算法中重複執行的次數作為演算法運行時間的衡量準則。例一兩個矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數組存儲矩陣元素，c為a和b的乘積

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

for(j=1;j<=n;++j){c[i][j]=0;

for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];

}//for}//mult基本操作:

乘法操作時間複雜度:

O(n3)1.下麵程式段中帶下劃線的語句的執行次數的數量級是：

【合肥工業大學1999三、1（2分）】i=1;while(i<n)i=i*2;

2.下麵程式段中帶下劃線的語句的執行次數的數量級是()。【合肥工業大學2000三、1（2分）】i=1;while(i<n){for(j=0;j<n;j++)x=x+1;i=i*2；}3.下麵程式段中帶有下劃線的語句的執行次數的數量級是()【合肥工業大學2001三、1（2分）】

i=n*n; while(i!=1)i=i/2;

4．設n是偶數，試計算運行下列程式段後m的值並給出該程式段的時間複雜度。【南京郵電大學2000一、1】m=0;for(i=0;i<n;i++)for(j=2*i;j<=n;j++)m=m+1;5.分析下麵程式段的時間複雜度。

intfact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}例二選擇排序voidselect_sort(int&a[],intn){

//將a中整數序列重新排列成自小至大有序的整數序列。

}//select_sort基本操作:

比較(數據元素)操作時間複雜度:

O(n2)j=i;//

選擇第i個最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}例三起泡排序voidbubble_sort(int&a[],intn){

//將a中整數序列重新排列成自小至大有序的整數序列。for

(i=n-1,change=TRUE;i≥1&&change;--i)}//bubble_sort基本操作:

賦值操作時間複雜度:

O(n2){

change=FALSE;

//change為元素進行交換標誌

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟起泡按數量階遞增排列，常見的時間複雜度有：O(1)≤O(log2n)≤

O(n)≤

O(nlog2n)≤

O(n2)≤

O(n3)≤…≤

O(nk)≤

O(2n)4、演算法的存儲空間需求演算法的空間複雜度定義為:

表示隨著問題規模n的增大，演算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))演算法的存儲量包括:①輸入數據所占空間;②程式本身所占空間；③輔助變數所占空間。

若輸入數據所占空間只取決與問題本身，和演算法無關，則只需要分析除輸入和程式之外的輔助變數所占額外空間。

若所需額外空間相對於輸入數據量來說是常數，則稱此演算法為原地工作。

若所需存儲量依賴於特定的輸入，則通常按最壞情況考慮。1.

熟悉各名詞、術語的含義，掌握基本概念。2.

理解演算法五個要素的確切含義。本章學習要點3.

掌握計算語句頻度和估算演算法時間複雜度的方法。思考題:

1.41.61.71.191.20補充：寫一函數，用不多於3n/2的平均比較次數在一個向量A中找出最大和最小值的元素。本章作業:1.31.8線性表是一種最簡單的線性結構第二章線性表

線性結構的基本特徵:1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最後元素”3．除最後元素在外，均有唯一的後繼；4．除第一元素之外，均有唯一的前驅。線性結構

是一個數據元素的有序（次序）集2.1

線性表的類型定義2.3線性表類型的實現

鏈式映像2.4一元多項式的表示2.2線性表類型的實現

順序映像2.1線性表的類型定義抽象數據類型線性表的定義如下：ADTList{

數據對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}{稱n

為線性表的表長;

稱n=0

時的線性表為空表。}數據關係：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設線性表為(a1，a2,...，ai，...，an),

稱i為ai線上性表中的位序。}

基本操作：

結構初始化操作結構銷毀操作

引用型操作

加工型操作

}ADTList

InitList(&L)操作結果：構造一個空的線性表L。初始化操作

結構銷毀操作DestroyList(&L)初始條件：操作結果：線性表L已存在。銷毀線性表L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作:

ListEmpty(L)初始條件：操作結果：線性表L已存在。若L為空表，則返回TRUE，否則FALSE。（線性表判空）ListLength(L)初始條件：操作結果：線性表L已存在。返回L中元素個數。（求線性表的長度）

PriorElem(L,cur_e,&pre_e)初始條件：操作結果：線性表L已存在。若cur_e是L的元素，則用pre_e返回它的前驅，否則操作失敗，pre_e無定義。（求數據元素的前驅）NextElem(L,cur_e,&next_e)初始條件：操作結果：線性表L已存在。若cur_e是L的元素，則用next_e返回它的後繼，否則操作失敗，next_e無定義。（求數據元素的後繼）GetElem(L,i,&e)

初始條件：

操作結果：線性表L已存在，用

e返回L中第i

個元素的值。（求線性表中某個數據元素）且1≤i≤LengthList(L)LocateElem(L,e,compare())初始條件：操作結果：線性表L已存在，e

為給定值，

compare()是元素判定函數。返回L中第1個與e滿足關係

compare()的元素的位序。若這樣的元素不存在，則返回值為0。（定位函數）

ListTraverse(L,visit())初始條件：操作結果：線性表L已存在。Visit()為某個訪問函數。依次對L中每個元素調用函數標visit()。一旦visit()失敗，則操作失敗。（遍曆線性表）加工型操作

ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)

ClearList(&L)初始條件：操作結果：線性表L已存在。將L重置為空表。（線性表置空）PutElem(&L,i,&e)初始條件：操作結果：線性表L已存在，L中第i個元素賦值e。（改變數據元素的值）且1≤i≤LengthList(L)

ListInsert(&L,i,e)初始條件：操作結果：線性表L已存在，在L的第i個元素之前插入新的元素e，L的長度增1。（插入數據元素）且1≤i≤LengthList(L)+1ListDelete(&L,i,&e)初始條件：操作結果：線性表L已存在且非空，刪除L

的第

i

個元素，並用e返回其值，L的長度減1。（刪除數據元素）1≤i≤LengthList(L)利用上述定義的線性表類型可以實現其他更複雜的操作例

2-2例

2-3例

2-1

假設:有兩個集合A和B分別用兩個線性表LA和LB表示，即：線性表中的數據元素即為集合中的成員。

現要求一個新的集合A＝A∪B。例2-1

要求對線性表作如下操作：擴大線性表LA，將存在於線性表LB中而不存在於線性表

LA中的數據元素插入到線性表LA

中去。上述問題可演繹為：1．從線性表LB中依次察看每個數據元素;2．依值線上性表LA中進行查訪;3．若不存在，則插入之。GetElem(LB,i)→e

LocateElem(LA,e,equal())

ListInsert(LA,n+1,e)(n表示線性表LA當前長度)操作步驟：

GetElem(Lb,i,e);//取Lb中第i個數據元素賦給e

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的數據元素，則插入之La_len=ListLength(La);//求線性表的長度

Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}//for}//unionvoidunion(List&La,ListLb){

已知一個非純集合B，試構造一個純集合A，使A中只包含B中所有值各不相同的數據元素。仍選用線性表表示集合例

2-2集合B集合A從集合B

取出物件放入集合A要求集合A中同樣物件不能有兩件以上因此，演算法的策略應該和例2-1基本相同,差別僅在於集合A的初始狀態是“空集”voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}//union

GetElem(Lb,i,e);//取Lb中第i個數據元素賦給e

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的數據元素，則插入之for(i=1;i<=Lb_len;i++){}//forInitList(La);//構造(空的)線性表LA若線性表中的數據元素相互之間可以比較，並且數據元素在表中依值非遞減或非遞增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，則稱該為有序表(OrderedList)。試改變結構，以有序表表示集合。例如：（2，3，3，5，6，6，6，8，12）對集合B而言，

值相同的數據元素必定相鄰對集合A而言，

數據元素依值從小至大的順序插入因此，數據結構改變了，解決問題的策略也相應要改變。voidpurge(List&La,ListLb)

{InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長度

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

}//for}//purge

GetElem(Lb,i,e);//取Lb中第i個數據元素賦給eif

(ListEmpty(La)||!equal(en,e))

{

ListInsert(La,++La_len,e);

en=e;}

//La中不存在和e相同的數據元素，則插入之則

歸併兩個“其數據元素按值非遞減有序排列”的有序表LA和LB，求得有序表LC也具有同樣特性。設

La=(a1,…,ai,…,an),Lb=(b1,…,bj,…,bm)

Lc=(c1,…,ck,…,cm+n)且已由(a1,…,ai-1)和(b1,…,bj-1)歸併得

(c1,…,ck-1)例

2-3k=1,2,…,m+n1．初始化LC為空表；基本操作：2．分別從LA和LB中取得當前元素ai

和bj；3．若ai≤bj，則將ai

插入到LC中，否則將

bj

插入到LC中；4．重複2和3兩步，直至LA或LB中元素被取完為止；5．將LA表或LB表中剩餘元素複製插入到

LC表中。

//La和Lb均非空，i=j=1,k=0GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){//將ai插入到Lc中

ListInsert(Lc,++k,ai);++i;}else{//將bj插入到Lc中

ListInsert(Lc,++k,bj);++j;}voidMergeList(ListLa,ListLb,List&Lc){

//本演算法將非遞減的有序表La和Lb歸併為Lc}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空InitList(Lc);//構造空的線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while(i<=La_len){//當La不空時

GetElem(La,i++,ai);ListInsert(Lc,++k,ai);

}

//插入La表中剩餘元素

while(j<=Lb_len){//當Lb不空時

GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);

}

//插入Lb表中剩餘元素2.2線性表類型的實現----順序映像最簡單的一種順序映像方法是：

令y的存儲位置和x的存儲位置相鄰。順序映像——

以x的存儲位置和y的存儲位置之間某種關係表示邏輯關係<x,y>

用一組地址連續的存儲單元

依次存放線性表中的數據元素

a1a2

…ai-1ai

…an線性表的起始地址，稱作線性表的基地址以“存儲位置相鄰”表示有序對<ai-1，ai>

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

一個數據元素所占存儲量↑所有數據元素的存儲位置均取決於第一個數據元素的存儲位置

LOC(ai)=

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

↑基地址順序映像的C語言描述typedefstruct{

}SqList;//俗稱順序表ElemType*elem;//存儲空間基址int

length;//當前長度int

listsize;//當前分配的存儲容量

//(以sizeof(ElemType)為單位)線性表的基本操作在順序表中的實現InitList(&L)//結構初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素Status

InitList_Sq(SqList&L,intmaxsize)

{//構造一個最大容量為maxsize的順序表

}//InitList_Sq演算法時間複雜度：O(1)L.elem=newElemType[maxsize];

//

為順序表分配大小為maxsize的數組空間if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;例如：順序表的查找23754138546217L.elemL.length=7L.listsizee=38pppppi12341850p可見，基本操作是，將順序表中的元素逐個和給定值e相比較。

intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在順序表中查詢第一個滿足判定條件的數據元素，

//若存在，則返回它的位序，否則返回0}//LocateElem_Sq

O(ListLength(L))if(i<=L.length)returni;elsereturn0;演算法的時間複雜度為：i=1;//i的初值為第1元素的位序p=L.elem;

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

(i<=L.length&&!(*compare)(*p++,e))++i;(*compare)(*p++,e)//找到滿足條件的元素//沒有找到滿足條件的元素線性表操作

ListInsert(&L,i,e)的實現：首先分析:插入元素時，線性表的邏輯結構發生什麼變化？

(a1,…,ai-1,ai,…,an)改變為a1a2

…ai-1ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加(a1,…,ai-1,e,ai,…,an)

StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在順序表L的第i個元素之前插入新的元素e,

//i的合法範圍為1≤i≤L.length+1}//ListInsert_Sq

演算法時間複雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之後的元素右移*q=e;//插入e++L.length;//表長增1returnOK;……元素右移考慮移動元素的平均情況:

假設在第

i個元素之前插入的概率為，

則在長度為n的線性表中插入一個元素所需移動元素次數的期望值為：

若假定線上性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：if(L.length>=L.listsize)returnOVERFLOW;//當前存儲空間已滿

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

returnERROR;

//

插入位置不合法2118307542568721183075例如：ListInsert_Sq(L,5,66)

L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p線性表操作

ListDelete(&L,i,&e)的實現：首先分析：刪除元素時，線性表的邏輯結構發生什麼變化？

(a1,…,ai-1,ai,ai+1,…,an)改變為ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

(a1,…,ai-1,ai+1,…,an)StatusListDelete_Sq(SqList&L,inti,ElemType&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被刪除元素之後的元素左移--L.length;//表長減1returnOK;演算法時間複雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法元素左移考慮移動元素的平均情況:

假設刪除第

i個元素的概率為

,則在長度為n的線性表中刪除一個元素所需移動元素次數的期望值為：若假定線上性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)

p2.3線性表類型的實現----鏈式映像一、單鏈表二、結點和單鏈表的C語言描述三、線性表的操作在單鏈表中的實現四、一個帶頭結點的單鏈表類型五、其他形式的鏈表六、有序表類型

用一組地址任意的存儲單元存放線性表中的數據元素。一、單鏈表以元素(數據元素的映像)

+指針(指示後繼元素存儲位置)=結點

(表示數據元素或數據元素的映像)以“結點的序列”表示線性表

稱作鏈表

以線性表中第一個數據元素的存儲地址作為線性表的地址，稱作線性表的頭指針頭結點

a1a2…...an^頭指針頭指針

有時為了操作方便，在第一個結點之前虛加一個“頭結點”，以指向頭結點的指針為鏈表的頭指針空指針線性表為空表時，頭結點的指針域為空

typedefstructLNode{ElemTypedata;//數據域

structLNode*next;//指針域

}LNode,*LinkList;

二、結點和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針三、單鏈表操作的實現GetElem(L,i,&e)//取第i個數據元素ListInsert(&L,i,e)//插入數據元素ListDelete(&L,i,&e)//刪除數據元素ClearList(&L)//重置線性表為空表CreateList(&L,n)

//生成含n個數據元素的鏈表L

線性表的操作

GetElem(L,i,&e)在單鏈表中的實現:211830754256∧pppj123

因此，查找第i個數據元素的基本操作為：移動指針，比較j和i

單鏈表是一種順序存取的結構，為找第i個數據元素，必須先找到第i-1個數據元素。

令指針p

始終指向線性表中第j

個數據元素

StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結點的鏈表的頭指針，以e返回第i個元素}//GetElem_L演算法時間複雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個結點，j為計數器while(p&&j<i){p=p->next;++j;}//

順指針向後查找，直到p指向第i個元素

//

或p為空if(!p||j>i)

returnERROR;//第i個元素不存在e=p->data;//取得第i個元素returnOK;ai-1

線性表的操作

ListInsert(&L,i,e)

在單鏈表中的實現：

有序對<ai-1,ai>

改變為<ai-1,e>和<e,ai>eaiai-1

因此，在單鏈表中第i個結點之前進行插入的基本操作為:

找到線性表中第i-1個結點，然後修改其指向後繼的指針。

可見，在鏈表中插入結點只需要修改指針。但同時，若要在第i個結點之前插入元素，修改的是第i-1個結點的指針。StatusListInsert_L(LinkList&L,inti,ElemTypee){

//L為帶頭結點的單鏈表的頭指針，本演算法

//在鏈表中第i個結點之前插入新的元素e

}//LinstInsert_L演算法的時間複雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

尋找第i-1個結點if(!p||j>i-1)

returnERROR;//

i大於表長或者小於1s=newLNode;

//生成新結點if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp線性表的操作ListDelete(&L,i,&e)在鏈表中的實現:有序對<ai-1,ai>和<ai,ai+1>

改變為<ai-1,ai+1>ai-1aiai+1ai-1

在單鏈表中刪除第

i個結點的基本操作為:找到線性表中第i-1個結點，修改其指向後繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;deleteq;pqStatusListDelete_L(LinkList&L,inti,ElemType&e){

//刪除以L為頭指針(帶頭結點)的單鏈表中第i個結點

}//ListDelete_L演算法的時間複雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個結點，並令p指向其前趨q=p->next;p->next=q->next;

//刪除並釋放結點e=q->data;deleteq;returnOK;if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理操作ClearList(&L)在鏈表中的實現:voidClearList(&L){//將單鏈表重新置為一個空表

while(L->next){

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

}}//ClearListdeletep;演算法時間複雜度：O(ListLength(L))如何從線性表得到單鏈表？鏈表是一個動態的結構，它不需要預分配空間，因此生成鏈表的過程是一個結點“逐個插入”的過程。例如：逆位序輸入n個數據元素的值，建立帶頭結點的單鏈表。（頭插法）操作步驟：一、建立一個“空表”；二、輸入數據元素an，建立結點並插入；三、輸入數據元素an-1，建立結點並插入；ananan-1四、依次類推，直至輸入a1為止。voidCreateList_L(LinkList&L,intn){//逆序輸入n個數據元素，建立帶頭結點的單鏈表}//CreateList_L演算法的時間複雜度為:O(Listlength(L))L=newLNode;L->next=NULL;

//先建立一個帶頭結點的單鏈表for(i=n;i>0;--i){p=newLNode;

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}回顧2.1節中三個例子的演算法，看一下當線性表分別以順序存儲結構和鏈式存儲結構實現時，它們的時間複雜度為多少？voidunion(List&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);

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

GetElem(Lb,i,e);if(!LocateElem(La,e,equal())

ListInsert(La,++La_len,e);

}//for}//union控制結構：基本操作：for迴圈GetElem,LocateElem

和ListInsert當以順序映像實現抽象數據類型線性表時為:

O(ListLength(La)×ListLength(Lb))

當以鏈式映像實現抽象數據類型線性表時為:

O(ListLength(La)×ListLength(Lb))例2-1演算法時間複雜度

voidpurge(List&La,ListLb){

InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);

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

GetElem(Lb,i,e);

if(ListEmpty(La)||

!equal(en,e))

{

ListInsert(La,++La_len,e);en=e;}

}//for}//purge控制結構：基本操作：for迴圈GetElem

和

ListInsert當以順序映像實現抽象數據類型線性表時為:

O(ListLength(Lb))當以鏈式映像實現抽象數據類型線性表時為:

O(Lb_len×(Lb_len+La_len))例2-2演算法時間複雜度voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){

GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj){

ListInsert(Lc,++k,ai);++i;}

else{

ListInsert(Lc,++k,bj);++j;}

}……控制結構：基本操作：三個並列的while迴圈GetElem,ListInsert當以順序映像實現抽象數據類型線性表時為:

O(ListLength(La)+ListLength(Lb))當以鏈式映像實現抽象數據類型線性表時為:

O(ListLength2(La)+ListLength2(Lb))例2-3演算法時間複雜度用上述定義的單鏈表實現線性表的操作時，存在的問題：

改進鏈表的設置：1．單鏈表的表長是一個隱含的值；

1．增加“表長”、“表尾指針”、“當前位置的指針”和“當前序號”四個數據域；2．在單鏈表的最後一個元素之後插入元素時，需遍曆整個鏈表；3．在鏈表中，元素的“位序”概念淡化，結點的“位置”概念加強。2．將基本操作中的“位序i”改變為“指針p”。四、一個帶頭結點的線性鏈表類型typedefstructLNode{//結點類型

ElemTypedata;

structLNode*next;}*Link,*Position;StatusMakeNode(Link&p,ElemTypee);

//分配由p指向的值為e的結點，並返回OK；

//若分配失敗，則返回ERRORvoidFreeNode(Link&p);

//

釋放p所指結點typedefstruct

{//鏈表類型

Linkhead,tail;

//分別指向頭結點和

//

最後一個結點的指針

intlen;

//指示鏈表長度

Linkcurrent;

//指向當前被訪問的結點

//的指針，初始位置指向頭結點

intcurpos;//指示當前指針位置,初值為0}LinkList;鏈表的基本操作:{結構初始化和銷毀結構}StatusInitList(LinkList&L);

//構造一個空的線性鏈表L，其頭指針、

//

尾指針和當前指針均指向頭結點，

//

當前位置和表長為零。StatusDestroyList(LinkList&L);

//銷毀線性鏈表L，L不再存在。O(1)O(n){引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//

求表長StatusPrior(LinkListL);

//改變當前指針指向其前驅StatusNext(LinkListL);

//改變當前指針指向其後繼ElemTypeGetCurElem(LinkListL);

//返回當前指針所指數據元素O(1)O(1)O(n)O(1)O(1)

StatusLocatePos(LinkListL,inti);

//改變當前指針指向第i個結點StatusLocateElem(LinkListL,ElemTypee,

Status(*compare)(ElemType,ElemType));

//若存在與e滿足函數compare()判定關係的元

//素，則移動當前指針指向第1個滿足條件的

//元素的前驅，並返回OK;否則返回ERRORStatusListTraverse(LinkListL,Status(*visit)());

//

依次對L的每個元素調用函數visit()O(n)O(n)O(n)