chap001數據結構11、用道德的示范來造就一個人，顯然比用法律來約束他更有價值。——希臘12、法律是無私的，對誰都一視同仁。在每件事上，她都不徇私情。——托馬斯13、公正的法律限制不了好的自由，因為好人不會去做法律不允許的事情。——弗勞德14、法律是為了保護無辜而制定的。——愛略特15、像房子一樣，法律和法律都是相互依存的。——伯克chap001數據結構chap001數據結構11、用道德的示范來造就一個人，顯然比用法律來約束他更有價值。——希臘12、法律是無私的，對誰都一視同仁。在每件事上，她都不徇私情。——托馬斯13、公正的法律限制不了好的自由，因為好人不會去做法律不允許的事情。——弗勞德14、法律是為了保護無辜而制定的。——愛略特15、像房子一樣，法律和法律都是相互依存的。——伯克數據結構計算機科學的核心課程：授課教師：宣士斌（教授）聯系方式： 移動電話E-mail:xuanshibingxun QQ:404868138第一章緒論1.1數據結構討論的范疇1.2基本概念1.3算法和算法的量度1.1

數據結構討論的范疇NiklausWirth：

Algorithm

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

處理問題的策略問題的數學模型結構靜力分析計算例如:數值計算的程序設計問題─━線性代數方程組─━環流模式方程(球面坐標系)全球天氣預報非數值計算的程序設計問題例一:求一組(n個)整數中的最大值算法:?模型：？基本操作是“比較兩個數的大小”取決于整數值的范圍例二：計算機對弈算法：?模型：?對弈的規則和策略棋盤及棋盤的格局例三：足協的數據庫管理算法：?模型：?需要管理的項目？如何管理？用戶界面？各種表格例三：旅行商問題算法：?模型：?找出代價最小的回路圖概括地說：

數據結構是一門討論“描述現實世界實體的數學模型(非數值計算)及其上的操作在計算機中如何表示和實現”的學科。1.2基本概念一、數據與數據結構二、數據類型三、抽象數據類型一、數據與數據結構所有能被輸入到計算機中，且能被計算機處理的符號的集合。數據:是計算機操作的對象的總稱。是計算機處理的信息的某種特定的符號表示形式。是數據（集合）中的一個“個體”數據元素:是數據結構中討論的基本單位

數據項：是數據結構中討論的最小單位數據元素可以是數據項的集合例如：描述一個運動員的數據元素可以是稱之為組合項數據結構：帶結構的數據元素的集合假設用三個4位的十進制數表示一個含

12位數的十進制數。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)則在數據元素a1、a2和a3之間存在著“次序”關系

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

a1a3a5

a2a4a6a1a2a3a4a5a6

數據結構：帶結構的數據元素的集合再例，在一維數組{a1,a2,a3,a4,a5,a6}的數據元素之間存在如下的次序關系:{<ai,ai+1>|i=1,2,3,4,5}

或者說，數據結構是相互之間存在著某種邏輯關系的數據元素的集合。數據結構：帶結構的數據元素的集合可見，不同的“關系”構成不同的“結構”數據的邏輯結構可歸結為以下四類:線性結構樹形結構圖狀結構集合結構數據結構的形式定義為:數據結構是一個二元組Data_Structures=(D,S)其中:D是數據元素的有限集，

S是D上關系的有限集。數據的存儲結構

——邏輯結構在存儲器中的映象“數據元素”的映象？“關系”的映象？數據元素的映象方法：用二進制位(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]定義長整數為:二、數據類型

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

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

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

不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。三、抽象數據類型

(AbstractDataType簡稱ADT)是指一個數學模型以及定義在此數學模型上的一組操作。例如，抽象數據類型復數的定義：

數據對象：

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

數據關系：

R1＝{<e1,e2>|e1是復數的實數部分

|e2是復數的虛數部分}ADTComplex{基本操作：

AssignComplex(&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假設:z1和z2是上述定義的復數則Add(z1,z2,z3)操作的結果z3=z1+z2即為用戶企求的結果ADT有兩個重要特征:數據抽象

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

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

S是D上的關系集；P是對D的基本操作集。ADT

抽象數據類型名{數據對象：〈數據對象的定義〉

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

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

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

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

賦值參數只為操作提供輸入值。引用參數以&打頭，除可提供輸入值外，還將返回操作結果。初始條件描述了操作執行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。抽象數據類型的表示和實現抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。例如，對以上定義的復數。typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲結構的定義//-----基本操作的函數原型說明void

Assign(complex&Z,

floatrealval,floatimagval)；//構造復數Z,其實部和虛部分別被賦以參數//realval和imagval的值float

GetReal(cpmplexZ)；//返回復數Z的實部值float

Getimag(cpmplexZ)；//返回復數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.3算法和算法的衡量一、算法二、算法設計的原則三、算法效率的衡量方法和準則四、算法的存儲空間需求

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

2．確定性3．可行性4．有輸入5．有輸出一、算法1．有窮性對于任意一組合法輸入值，在執行有窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間內完成。

2．確定性

對于每種情況下所應執行的操作，在算法中都有確切的規定，使算法的執行者或閱讀者都能明確其含義及如何執行。并且在任何條件下，算法都只有一條執行路徑。3．可行性算法中的所有操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之。4．有輸入作為算法加工對象的量值，通常體現為算法中的一組變量。有些輸入量需要在算法執行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。

5．有輸出它是一組與“輸入”有確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。二、算法設計的原則設計算法時，通常應考慮達到以下目標：1．正確性2.可讀性3．健壯性4．高效率與低存儲量需求1．正確性

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

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

d．程序對于一切合法的輸入數據都能得出滿足要求的結果；2.可讀性

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

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

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

事后統計法事前分析估算法缺點：1．必須執行程序2．其它因素掩蓋算法本質和算法執行時間相關的因素：1．算法選用的策略2．問題的規模3．編寫程序的語言4．編譯程序產生的機器代碼的質量5．計算機執行指令的速度一個特定算法的“運行工作量”的大小，只依賴于問題的規模（通常用整數量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)例二選擇排序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;}}//一趟起泡常用來評判算法效率的

標準函數為：logn,n,nlogn,n2,n3,2n,n!結論(1)只要算法的執行時間不隨問題規模n的增加而增長,算法的頻度是某個常數,即使這個常數再大,算法的時間復雜度是O(1)。(2)為了簡化運算,可以用頻度最大的語句衡量時間復雜度.當有若干循環語句時,算法的時間復雜度由嵌套層數最多的語句的頻度決定。結論(3)最好時間復雜性,最壞時間復雜性,平均時間復雜性對有些算法,問題規模相同,輸入集不同,其效率也不同。Tmin:最好情況不能代表算法的性能；Tmax:最壞情況可以知道算法至少能達到的性能；Tavg:較好地反映了算法的性能。四、算法的存儲空間需求算法的空間復雜度定義為:

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