數(shù)據(jù)結構(C語言版) 第1章 緒論

理論課教材：

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

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

數(shù)據(jù)結構是程序設計的基礎

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

=算法

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

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

其中:D是數(shù)據(jù)元素的有限集，

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

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

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

存儲內容

指針

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順序存儲數(shù)據(jù)的邏輯結構非線性結構集合圖狀結構有向圖無向圖樹形結構一般樹二叉樹線性結構一般線性表線性表推廣廣義表數(shù)組串受限線性表棧和隊列數(shù)據(jù)邏輯結構層次關系圖1.2基本概念和術語在用高級程序語言編寫的程序中，必須對程序中出現(xiàn)的每個變量、常量或表達式，明確說明它們所屬的數(shù)據(jù)類型。例C語言中，提供int,char,float,double等基本數(shù)據(jù)類型，數(shù)組、結構體、共用體、枚舉等構造數(shù)據(jù)類型，還有指針、空(void)類型等。用戶也可用typedef

自己定義數(shù)據(jù)類型typedefstruct

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

(AbstractDataType簡稱ADT)：是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作?！俺橄蟆钡囊饬x在于數(shù)據(jù)類型的數(shù)學抽象。一個抽象的數(shù)據(jù)類型的模塊通常應包含定義、表示和實現(xiàn)三部分。抽象數(shù)據(jù)類型定義格式ADT

抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉

數(shù)據(jù)關系：〈數(shù)據(jù)關系的定義〉

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

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

S是D上的關系集；

P是對D的基本操作集。

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

基本操作名（參數(shù)表）

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

操作結果：〈操作結果描述〉初始條件描述了操作執(zhí)行之前數(shù)據(jù)結構和參數(shù)應滿足的條件，若不滿足，則操作失敗，并返回相應出錯信息。操作結果說明了操作正常完成之后，數(shù)據(jù)結構的變化狀況和應返回的結果。若初始條件為空，則省略之?；静僮骼纾橄髷?shù)據(jù)類型復數(shù)的定義：

數(shù)據(jù)對象： //D

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

數(shù)據(jù)關系： //S

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

|e2

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

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

DestroyComplex(&Z)操作結果：復數(shù)Z被銷毀。

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

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

Add(z1,z2,&sum)初始條件：z1,z2是復數(shù)。操作結果：用sum返回兩個復數(shù)z1,z2的和值。}ADTComplex1.3抽象數(shù)據(jù)類型的表示和實現(xiàn)

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

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

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

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

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

if和switch(6)循環(huán)語句

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

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

scanf,printf(9)注釋

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

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

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

Assign(complex&Z,floatrealval,floatimagval)；

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

//數(shù)realval

和imagval

的值floatGetReal(cpmplexZ)；

//返回復數(shù)Z的實部值float

GetImag(complexZ)；

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

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

//用sum返回兩個復數(shù)z1,z2的和

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

{其它省略}typedefstruct{floatrealpart；

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

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

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

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

可讀性(readability)

健壯性(robustness)

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

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

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

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

當輸入的數(shù)據(jù)非法時，算法應當恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。4．高效率與低存儲量需求

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

1.事后統(tǒng)計——利用計算機內記時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分

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

所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

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

依據(jù)的算法選用何種策略

問題的規(guī)模

程序語言

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

機器執(zhí)行指令速度算法效率的度量

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

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

一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。算法效率的度量注意：T(n)是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)，而O(f(n))是指當問題規(guī)模趨向無窮大時，該算法時間復雜度的數(shù)量級。f(n)是n趨向無窮大時與T(n)為同階無窮大。算法=控制結構+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間

=

原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時間

算法的執(zhí)行時間

與

原操作執(zhí)行次數(shù)之和

成正比

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

的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則。如何估算算法的時間復雜度voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲矩陣元素，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中整數(shù)序列重新排列成自小至大有序的整數(shù)序列?；静僮?

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

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)