理論課教材：

數據結構（C語言版）嚴蔚敏吳偉民編著數據結構1.0學習數據結構的主要意義和要求

1.1數據結構討論的范疇1.2基本概念1.3抽象數據類型的表示和實現1.4算法和算法的度量第一章緒論學習數據結構的主要意義和要求數據結構和算法是計算機學科的兩大支柱

數據結構是程序設計的基礎

程序=算法+數據結構要求：意義：（1）掌握各類基本數據結構類型和相應的存儲結構（2）提高閱讀和編寫算法的能力（3）能針對給定問題，選擇相適應的數據結構，并能設計和分析算法1.1數據結構討論的范疇程序

=算法

+數據結構程序設計：為計算機處理問題編制一組指令集算法：處理問題的策略數據結構：問題的數學模型非數值計算的程序設計問題例1書目自動檢索系統例2人機對奕問題例3多叉路口交通燈管理問題例1書目自動檢索系統書目文件按書名按作者名按分類號索引表線性表例2人機對奕問題樹……..……..…...…...…...…...例3多叉路口交通燈管理問題圖CEDABABACADBABCBDDADBDCEAEBECED數據結構定義

數據結構是一門討論“描述現實世界實體”的數學模型(非數值計算)及其上的操作在計算機中如何表示和實現”的學科。數據（data)—所有能被輸入到計算機中，且能被計算機處理的符號的集合，是計算機操作的對象的總稱。數據元素（dataelement）—是數據（集合）中的一個“個體”，是數據的基本單位，也稱節點（node）或記錄（record）數據項（dataitem）—有獨立含義的數據最小單位，也稱域(field)。數據對象（dataobject)—是性質相同的數據元素的集合，是數據的一個子集。1.2基本概念和術語根據數據元素間關系的基本特性，有四種基本結構（集合）——數據元素間除“同屬于一個集合”外，無其它關系線性結構——一個對一個，如線性表、棧、隊列樹形結構——一個對多個，如樹圖狀結構——多個對多個，如圖1.2基本概念和術語數據結構(datastructure)—是相互之間存在一種或多種特定關系的數據元素的集合1.2基本概念和術語數據結構的形式定義為:數據結構是一個二元組Data_Structures=(D,S)

其中:D是數據元素的有限集，

S是D上關系的有限集。數據元素的映象方法：例用二進制位(bit)的位串表示數據元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2關系的映象方法：（表示x,y的方法）順序映象以相對的存儲位置表示后繼關系鏈式映象

以附加信息(指針)表示后繼關系數據的邏輯結構—只抽象反映數據元素的邏輯關系數據的存儲（物理）結構—數據的邏輯結構在計算機存儲器中的映象換句話說

按某種邏輯關系組織起來的一批數據，按一定的映象方式把它存放在計算機的存儲器中，并在這些數據上定義了一個運算的集合，就叫做數據結構數據的邏輯結構與存儲結構密切相關存儲結構分為：順序存儲結構——借助元素在存儲器中的相對位置來表示數據元素間的邏輯關系鏈式存儲結構——借助指示元素存儲地址的指針表示數據元素間的邏輯關系線性表樹圖順序存儲結構鏈式存儲結構復合存儲結構邏輯結構物理結構存儲地址

存儲內容

指針

1345

元素1

1400

1346

元素4∧…….……..…….

1400

元素2

1536…….……..…….

1536

元素3

1346

鏈式存儲h1536元素21400元素11346元素3∧元素41345h元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內容Loc(元素i)=Lo+（i-1)*m順序存儲數據的邏輯結構非線性結構集合圖狀結構有向圖無向圖樹形結構一般樹二叉樹線性結構一般線性表線性表推廣廣義表數組串受限線性表棧和隊列數據邏輯結構層次關系圖1.2基本概念和術語在用高級程序語言編寫的程序中，必須對程序中出現的每個變量、常量或表達式，明確說明它們所屬的數據類型。例C語言中，提供int,char,float,double等基本數據類型，數組、結構體、共用體、枚舉等構造數據類型，還有指針、空(void)類型等。用戶也可用typedef

自己定義數據類型typedefstruct

{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;數據類型：是一個值的集合和定義在此集合上的一組操作的總稱。1.2基本概念和術語不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。抽象數據類型

(AbstractDataType簡稱ADT)：是指一個數學模型以及定義在此數學模型上的一組操作。“抽象”的意義在于數據類型的數學抽象。一個抽象的數據類型的模塊通常應包含定義、表示和實現三部分。抽象數據類型定義格式ADT

抽象數據類型名{

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

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

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

抽象數據類型名抽象數據類型可用（D，S，P）三元組表示。其中：D是數據對象；

S是D上的關系集；

P是對D的基本操作集。

賦值參數只為操作提供輸入值。引用參數以&打頭，除可提供輸入值外，還可返回操作結果。其中基本操作的定義格式為:

基本操作名（參數表）

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

操作結果：〈操作結果描述〉初始條件描述了操作執行之前數據結構和參數應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果說明了操作正常完成之后，數據結構的變化狀況和應返回的結果。若初始條件為空，則省略之。基本操作例如，抽象數據類型復數的定義：

數據對象： //D

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

數據關系： //S

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

|e2

是復數的虛數部分}ADTComplex{基本操作： //P

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的和值。}ADTComplex1.3抽象數據類型的表示和實現

抽象數據類型需要通過固有數據類型(高級編程語言中已實現的數據類型)來實現。ADT有兩個重要特征:數據抽象

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

將實體的外部特性和其內部實現細節分離，并且對外部用戶隱藏其內部實現細節。本書采用的C語言核心子集(1)預定義常量類型://函數結果狀態代碼#defineTRUE1#defineFLASE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數的類型，其值是//函數的結果狀態代碼typedefintStatus(2)數據元素類型約定為ElemType(3)基本操作的算法都用以下形式的函數描述

函數類型函數名（函數參數表）{ //算法說明 語句序列

}函數名(4)賦值語句(5)選擇語句

if和switch(6)循環語句

for,while,do-while(7)結束語句

return,break,exit(8)輸入輸出語句

scanf,printf(9)注釋

單行注釋//(10)基本函數

max,min,abs,eof…(11)邏輯運算

&&,||,!//-----基本操作的函數原型說明void

Assign(complex&Z,floatrealval,floatimagval)；

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

//數realval

和imagval

的值floatGetReal(cpmplexZ)；

//返回復數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;}

{其它省略}typedefstruct{floatrealpart；

floatimagpart；}complex；//-----存儲結構的定義例如，對以上定義的復數。1.4算法和算法的度量算法（algorithm）—解決某一特定問題的具體步驟的描述，是指令的有限序列一個算法必須滿足以下五個重要特性：1．有窮性

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

算法中每一條指令必須有確切的含義，讀者理解時不會產生二義性。并且在任何條件下，算法都只有一條執行路徑，即對于相同的輸入只能得出相同的輸出。3．可行性

算法中的所有操作都可以通過已經實現的基本操作運算有限次來實現。4．有輸入一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合。有些輸入量需要在算法執行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。5．有輸出一個算法有零個或多個輸出，這些輸出是同輸入有著某些特定關系的量。算法特性算法的評價—衡量算法優劣的標準正確性(correctness)

可讀性(readability)

健壯性(robustness)

效率與低存儲量算法設計的要求1．正確性

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

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

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

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

通常，效率指的是算法執行時間；存儲量指的是算法執行過程中所需的最大存儲空間，兩者都與問題的規模有關。算法設計的要求算法效率——用依據該算法編制的程序在計算機上執行所消耗的時間來度量

1.事后統計——利用計算機內記時功能，不同算法的程序可以用一組或多組相同的統計數據區分

缺點：必須先運行依據算法編制的程序

所得時間統計量依賴于硬件、軟件等環境因素，掩蓋算法本身的優劣

算法效率的度量2.事前分析估計——一個高級語言程序在計算機上運行所消耗的時間取決于：

依據的算法選用何種策略

問題的規模

程序語言

編譯程序產生機器代碼質量

機器執行指令速度算法效率的度量

同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，———所以使用絕對時間單位衡量算法效率不合適

假如，隨著問題規模n的增長，算法執行時間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時間復雜度。

一個特定算法的“運行工作量”的大小，只依賴于問題的規模（通常用整數量n表示），或者說，它是問題規模的函數。算法效率的度量注意：T(n)是某個算法的時間耗費，它是該算法所求解問題規模n的函數，而O(f(n))是指當問題規模趨向無窮大時，該算法時間復雜度的數量級。f(n)是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中整數序列重新排列成自小至大有序的整數序列。基本操作:

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

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){}//select_sortif(j!=i)