數(shù)據(jù)結(jié)構(gòu)課件-第1章

第一章緒論臧麗1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分析本章重點(diǎn)難點(diǎn)

重點(diǎn):①數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及基本操作的概念及相互關(guān)系；②抽象數(shù)據(jù)類型(ADT)的概念和實(shí)現(xiàn)方法，算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。難點(diǎn):①抽象數(shù)據(jù)類型(ADT)的概念和實(shí)現(xiàn)方法；②算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。1.1

什么是數(shù)據(jù)結(jié)構(gòu)

為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特性以及各處理對(duì)象之間存在的關(guān)系,這就是”數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科形成和發(fā)展的背景.NiklausWirth：沃思

Algorithm

+DataStructures=Programs算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)

處理問題的策略給出問題的數(shù)學(xué)模型編制出用計(jì)算機(jī)處理問題的指令用計(jì)算機(jī)解決具體問題時(shí)經(jīng)過的步驟：從具體問題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型

設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法

編程序，進(jìn)行測試，調(diào)整直至得到最終解答。非數(shù)值計(jì)算的程序設(shè)計(jì)問題例一:圖書館的書目檢索系統(tǒng)自動(dòng)化問題算法:?模型：？查找圖書某一方面的信息按照某一方面信息建立的表格按圖書的某些特征項(xiàng)建索引(如編號(hào)、書名、作者、出版日期等)根據(jù)查詢要求，按某一索引項(xiàng)進(jìn)行排序操作對(duì)象：是一本書的基本信息，如：編號(hào)、書名、作者、出版日期對(duì)象間關(guān)系：按某一索引項(xiàng)的線性排序關(guān)系如：按編號(hào)進(jìn)行排序本例表示了一種數(shù)據(jù)結(jié)構(gòu)---線性數(shù)據(jù)結(jié)構(gòu)問題1：圖書檢索自動(dòng)化(線性結(jié)構(gòu))

圖書目錄文件示例數(shù)據(jù)：書目信息

結(jié)構(gòu)：順序關(guān)系——線性結(jié)構(gòu)例二：計(jì)算機(jī)和人對(duì)弈問題算法：?模型：?對(duì)弈的規(guī)則和策略棋盤及棋盤的格局（樹結(jié)構(gòu)）井字棋對(duì)奕“樹”數(shù)據(jù)：棋盤格局

結(jié)構(gòu)：層次關(guān)系——樹結(jié)構(gòu)例三：多叉路口交通燈的管理設(shè)置交通燈要滿足以下幾個(gè)要求：沒有不通的道路行駛的車輛不發(fā)生相互碰撞保證路口達(dá)到最大車流量對(duì)這個(gè)實(shí)際問題進(jìn)行抽象，找出對(duì)象及其間的關(guān)系,從而建立數(shù)據(jù)結(jié)構(gòu)模型：操作對(duì)象：通路關(guān)系：行駛沖突關(guān)系---不能同時(shí)通行（圖結(jié)構(gòu)）五叉路口交通管理示意圖數(shù)據(jù)：交通線路

結(jié)構(gòu)：網(wǎng)狀關(guān)系——圖結(jié)構(gòu)問題轉(zhuǎn)換、抽象在上述圖中，可以同時(shí)通車的道路對(duì)應(yīng)的頂點(diǎn)染以相同顏色，有線段相連的頂點(diǎn)染以不同的顏色，且使所用顏色數(shù)量盡量少。至此這個(gè)實(shí)際問題便轉(zhuǎn)換成圖論中經(jīng)典問題：圖的染色問題---頂點(diǎn)的顏色與交通燈的顏色相對(duì)應(yīng)。檢查數(shù)學(xué)模型與原問題的對(duì)應(yīng)性圖中已列出所有可能的通路（路路通）。具有沖突關(guān)系的頂點(diǎn)（通路）顏色不同（不發(fā)生碰撞）。顏色少，則每一種顏色（交通燈色）具有更多的車輛通行（流量最大）。本例例示了另一種數(shù)據(jù)結(jié)構(gòu)---圖狀數(shù)據(jù)結(jié)構(gòu)概括地說：

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三者之間的一門核心課程，在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。

程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。1.2

基本概念和術(shù)語一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位，相當(dāng)于“記錄”。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位相當(dāng)于記錄的“域”或字段數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是稱之為數(shù)據(jù)項(xiàng)

數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例：整數(shù)數(shù)據(jù)對(duì)象是集合N=學(xué)號(hào)姓名班號(hào)性別出生日期入學(xué)成績001劉影01女19840417623002李恒01男19831211679003陳誠02男19840910638數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。例，在2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}中六個(gè)元素之間存在兩個(gè)關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：線性結(jié)構(gòu)數(shù)據(jù)元素之間是一對(duì)一的關(guān)系樹形結(jié)構(gòu)數(shù)據(jù)元素之間是一對(duì)多的關(guān)系圖狀結(jié)構(gòu)數(shù)據(jù)元素之間是多對(duì)多的關(guān)系集合結(jié)構(gòu)數(shù)據(jù)元素同屬于一個(gè)集合數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，即

D={di

|i=1,2,……,n,n≥0}

S是D上關(guān)系的有限集，

即

S={rj

|j=1,2,……,k,k≥1}，其中，rj是定義在D上的一個(gè)二元關(guān)系,

rj

={<dj,dk>|j,k=1,2,……,n,j≠k}對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下三方面的問題：①數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系，是具體關(guān)系的抽象。與數(shù)據(jù)的存儲(chǔ)無關(guān)。②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：

數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)存中的表示(映像)；③數(shù)據(jù)的運(yùn)算

即對(duì)數(shù)據(jù)施加的操作。定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的抽象的操作。邏輯結(jié)構(gòu)示例例4：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（1）

S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達(dá)式可用圖形表示為：bcaefd本結(jié)構(gòu)是線性的邏輯結(jié)構(gòu)示例例5：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（2）

S=(D,R)D={di|1≤i≤5}R={(di,dj),i<j}解：上述數(shù)據(jù)結(jié)構(gòu)可用圖形表示為：本結(jié)構(gòu)是非線性的

d1d5d2d4d3數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2(A)16=(101)8=(001000001)2關(guān)系的映象方法：（表示

x,y

的方法）順序映象以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系例如:令y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C而C是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息xy鏈?zhǔn)接诚笠愿郊有畔?指針)表示后繼關(guān)系需要用一個(gè)和x在一起的附加信息指示y的存儲(chǔ)位置yx在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通常可用高級(jí)編程語言中提供的數(shù)據(jù)類型描述之。二、數(shù)據(jù)類型

在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所

屬的數(shù)據(jù)類型。例如，C

語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型雙精度型double實(shí)型（C++語言）數(shù)據(jù)類型

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

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。三、抽象數(shù)據(jù)類型

(AbstractDataType

簡稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離抽象數(shù)據(jù)類型按值的不同分為3類：1、原子類型：變量的值是不可分解的；2、固定聚合類型：變量的值由確定數(shù)目的成分按某種結(jié)構(gòu)組成；3、可變聚合類型：變量的值由不確定數(shù)目的成分按某種結(jié)構(gòu)組成。抽象數(shù)據(jù)類型可用以下三元組表示（D，S，P）

D：是數(shù)據(jù)對(duì)象

S：是D上的關(guān)系集

P：是對(duì)D的基本操作集抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的格式定義為：

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

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

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

操作結(jié)果：〈操作結(jié)果描述〉

賦值參數(shù)只為操作提供輸入值。引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。ADT有兩個(gè)重要特征:數(shù)據(jù)抽象

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

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義：

數(shù)據(jù)對(duì)象：

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

數(shù)據(jù)關(guān)系：

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

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{其中用兩個(gè)實(shí)數(shù)來表示復(fù)數(shù)，將復(fù)數(shù)定義為兩個(gè)實(shí)數(shù)的有序?qū)?，并約定實(shí)部是前驅(qū)，虛部是后繼。

基本操作：

InitComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

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

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

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

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex多形數(shù)據(jù)類型：是指其值的成分不確定的數(shù)據(jù)類型。1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實(shí)現(xiàn)的操作來組合新的操作。例如，對(duì)以上定義的復(fù)數(shù)typedef

struct{

float

realpart；

float

imagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

Int(complex&Z,

float

realval,float

imagval)；//

構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval

和imagval

的值float

GetReal(complexZ)；

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

Getimag(complexZ)；

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

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

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和

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

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

{其它省略}1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)---

類C語言預(yù)定義常量和類型函數(shù)結(jié)果狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2函數(shù)的返回類型status，其值是函數(shù)結(jié)果狀態(tài)代碼typedef

int

stauts;數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（typedef）描述。數(shù)據(jù)元素的類型約定為ElemType,由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。基本操作的算法都用以下形式的函數(shù)描述函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{//算法說明語句序列} //函數(shù)名賦值語句簡單賦值變量名=表達(dá)式串聯(lián)賦值變量名1=變量名2=···=變量名k=表達(dá)式;成組賦值（變量名1，變量名2，···，變量名k）=（表達(dá)式1，表達(dá)式2，···，表達(dá)式k）;交換賦值條件賦值選擇語句條件語句1if(表達(dá)式)語句；條件語句2if(表達(dá)式)語句；else語句；開關(guān)語句1switch(表達(dá)式){case值1：語句序列1；break;···case值n：語句序列n;break;default:語句序列n+1;}選擇語句（續(xù)）開關(guān)語句2switch{case條件1：語句序列1；break;···case條件n：語句序列n;break;default:語句序列n+1;}循環(huán)語句for語句for(賦初值表達(dá)式序列;

條件;修改表達(dá)式序列)語句；while語句while(條件)語句；do-while語句do{

語句序列；

}while(條件)；結(jié)束語句函數(shù)結(jié)束語句return表達(dá)式; return;Case結(jié)束語句break；異常結(jié)束語句exit(異常代碼）;輸入輸出語句輸入語句scanf([格式串],變量1,···,

變量名n);輸出語句printf([格式串],表達(dá)式1,···,

表達(dá)式n);注釋單行注釋//文字序列邏輯運(yùn)算約定與運(yùn)算A&&B,當(dāng)A的值為0時(shí),不再對(duì)B求值或運(yùn)算A||B,當(dāng)A的值非0時(shí),不再對(duì)B求值基本函數(shù)求最大值max(表達(dá)式1,···,表達(dá)式n)求最小值min(表達(dá)式1,···,表達(dá)式n)求絕對(duì)值abs(表達(dá)式)求不足整數(shù)值floor(表達(dá)式)求進(jìn)位整數(shù)值ceil(表達(dá)式)判定文件結(jié)束eof(文件變量)或eof判定行結(jié)束eoln(文件變量)或eoln引用調(diào)用和值調(diào)用---按值傳遞voidsneezy(intx);intmain(){

inttimes=20;

sneezy(times); ...}voidsneezy(intx){ ...}創(chuàng)建times變量，賦值為20202個(gè)變量2個(gè)名稱times創(chuàng)建x變量，將實(shí)參值20復(fù)制給x20xvoidgrumpy(int&x);intmain(){

inttimes=20;

grumpy(times); ...}voidgrumpy(int&x){ ...}引用調(diào)用和值調(diào)用---按引用傳遞創(chuàng)建times變量，賦值為20201個(gè)變量2個(gè)名稱使x成為times的別名times,x動(dòng)態(tài)內(nèi)存分配void*malloc(long

NumBytes)分配NumBytes個(gè)字節(jié)，并返回指向該內(nèi)存的指針。如果分配失敗，則返回一個(gè)空指針NULL。注意：1、申請(qǐng)內(nèi)存空間后，必須檢查是否分配成功

T=(ElemType*)malloc(3*sizeof(ElemType));if(!T)exit(OVERFLOW);//分配存儲(chǔ)空間失敗…2、記得釋放，并將指向這塊內(nèi)存的指針指向NULL，防止程序后面不小心使用它

free(T);T=NULL;1.4算法和算法分析一、算法二、算法設(shè)計(jì)的要求三、算法效率的度量四、算法的存儲(chǔ)空間需求

算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法必須滿足以下五個(gè)重要特性：1．有窮性

2．確定性3．可行性4．輸入5．輸出一、算法1．有窮性對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。

2．確定性

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

5．輸出它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能，一個(gè)算法有一個(gè)或多個(gè)的輸出。二、算法設(shè)計(jì)的要求設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存儲(chǔ)量需求1．正確性

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

其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：a．程序中不含語法錯(cuò)誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；

c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第

c層意義的正確性作為衡量一個(gè)算法是否合格的標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；2.可讀性

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

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

通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間，兩者都與問題的規(guī)模有關(guān)。三、算法效率的度量通常有兩種衡量算法效率的方法:

事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1．必須執(zhí)行程序

2．其它因素掩蓋算法本質(zhì)和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度計(jì)算機(jī)硬件與軟件有關(guān)一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。算法=控制結(jié)構(gòu)+原操作（順序、分支和循環(huán)）（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間

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

算法的執(zhí)行時(shí)間

與

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

成正比

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

的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。一般被視作基本操作的是最深層循環(huán)內(nèi)的語句例一兩個(gè)矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積

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

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

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

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

乘法操作時(shí)間復(fù)雜度:

O(n3)

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。如何估算算法的時(shí)間復(fù)雜度？例一(a){++x;s=0}(b)For(i=1;i<=n;++i){++x;s+=x;}(c)for(j=1;j<=n;++j)

for(k=1;k<=n;++k){++x;s+=x;}含基本操作”x增1”的語句的頻度分別為1、n和n2

，則這3個(gè)程序段的時(shí)間復(fù)雜度分別為O（1）、O（n）和O（n2）時(shí)間復(fù)雜度曲線常見的時(shí)間復(fù)雜度：

O(1),O(log2n),O(n),O(nlog2n),O(n2),O(n3),O(2n)O(1)<O(log2n)＜O(n)＜O(nlog2n)＜(n2)＜O(n3)＜＜O(2n)例二for(j=2;j<=i-1;++j){++x;a[i][j]=x;}for(i=2;i<=n;++i){

語句頻度為：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴時(shí)間復(fù)雜度:O(n2)

即此算法的時(shí)間復(fù)雜度為平方階.例三起泡排序void

bubble_sort(int&a[],intn){

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

(i=n-1,change=TRUE;i>1&&change;