chap_01_font_embedded1

1、方燦Southwestern University839147計算機科學(xué)是一門研究用計算機進行信息表示和處理計算機科學(xué)是一門研究用計算機進行信息表示和處理的科學(xué)。這里面涉及到兩個問題：信息的的科學(xué)。這里面涉及到兩個問題：信息的表示表示，信息，信息的的處理處理。信息的表示和組織又直接關(guān)系到處理信息的程序的效信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著應(yīng)用問題的不斷復(fù)雜，導(dǎo)致信息量劇增與信率。隨著應(yīng)用問題的不斷復(fù)雜，導(dǎo)致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問題中大，結(jié)構(gòu)又相當(dāng)復(fù)雜

2、。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。結(jié)構(gòu)這門課所要研究的問題。數(shù)據(jù)結(jié)構(gòu)討論的范疇(數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的地位)系統(tǒng)分析系統(tǒng)實現(xiàn)系統(tǒng)維護系統(tǒng)設(shè)計Algorithm + Data Structures = Programs程序設(shè)計程序設(shè)計: :算法算法: 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu): 為計算機處理問題編制 一組指令集 處理問題的策略處理問題的策略問題的數(shù)學(xué)模型問題的數(shù)學(xué)模型By: Niklaus Wirth觀察：計算機會花費90%的運算時間在10%的代碼執(zhí)行上 找到并提高這10%部分的效率，可以有效

3、提高整個系統(tǒng)效率（瓶頸效應(yīng)）高配置的硬件，加上低效率的程序，執(zhí)行效果遠不如一般的硬件加上高效率的程序（NASA的運算能力，人腦VS計算機，密碼破解）例：例：旅客登機的管理算法：?模型：?先進后出，后進先出棧例例2 2：鋪設(shè)城市的煤氣管道算法：?模型：?如何規(guī)劃使得總投資花費最少？最小生成樹算法圖-樹-最小生成樹概括地說: 數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學(xué)模型及其上的操作在計算機中如何表示和實現(xiàn)”的學(xué)科。基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)數(shù)據(jù): :所有能被輸入被輸入到計算機中，且能被計算機處理的符號處理的符號( (數(shù)值、字符等

4、數(shù)值、字符等) )的集合是計算機操作的對象計算機操作的對象的總稱是計算機處理的信息的信息的某種特定的符號表示形式，表示形式，是客觀世界的字符化描述或字符化描述或者符號表示者符號表示 是數(shù)據(jù)（集合）中的一個“個體個體”,在計算機中通常作為一個整體進行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本基本單位。數(shù)據(jù)元素數(shù)據(jù)元素: :如:整數(shù)“5”,字符“N”等。 -是不可分割的“原子” 其中每個款項稱為一個“數(shù)據(jù)項數(shù)據(jù)項”它是數(shù)據(jù)結(jié)構(gòu)中討論的最小最小單位數(shù)據(jù)元素也可以由若干款項構(gòu)成。數(shù)據(jù)元素也可以由若干款項構(gòu)成。例如： 描述一個學(xué)生的數(shù)據(jù)元素稱之為組合項稱之為組合項年 月 日姓 名 學(xué) 號 班 號性別 出生日期

5、入學(xué)成績原子項原子項數(shù)據(jù)對象數(shù)據(jù)對象(Data Object)(Data Object)：是性質(zhì)相：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合子集。如字符集合C=A,C=A,B,B,C C, , 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)結(jié)構(gòu)的數(shù)據(jù)元素的集合有一個特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個數(shù)據(jù)結(jié)構(gòu)。指的是數(shù)據(jù)元素之間存在的關(guān)系當(dāng)用三個三個 4 4 位的十進制數(shù)位的十進制數(shù)表示一個含 12 12 位數(shù)的十進制數(shù)時，位數(shù)的十進制數(shù)時，3214,6587,9345 a1a1(3214),a2a2(6587),a3a3

6、(9345)則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序次序”關(guān)系關(guān)系 a1, a2a1, a2 、 a2, a3a2, a3 例如例如: :又例，在 2 行 3 列的二維數(shù)組中六個元素a1, a2, a3, a4, a5, a6之間存在兩個關(guān)系:行的次序關(guān)系行的次序關(guān)系:row = ,col = , a1 a2 a3 a4 a5 a6列的次序關(guān)系列的次序關(guān)系: :若在 6 個數(shù)據(jù)元素a1, a2, a3, a4, a5, a6 之間存在如下的次序關(guān)系次序關(guān)系:| i=1, 2, 3, 4, 5數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合據(jù)

7、元素的集合?？梢姡煌摹瓣P(guān)系關(guān)系”構(gòu)成不同的“結(jié)構(gòu)結(jié)構(gòu)”則構(gòu)成一維數(shù)組一維數(shù)組的定義。從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下四類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)包括“邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)” 和“物理結(jié)物理結(jié)構(gòu)構(gòu)”兩個方面(層次):邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以應(yīng)一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示;物理結(jié)構(gòu)物理結(jié)構(gòu) 是邏輯結(jié)構(gòu)在計算機中的表示和實現(xiàn)，故又稱“存儲結(jié)構(gòu)存儲結(jié)構(gòu)” 。數(shù)據(jù)結(jié)構(gòu)的形式定義描述數(shù)據(jù)結(jié)構(gòu)的形式定義描述為:數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structures = (D, S)其中:D 是數(shù)據(jù)元素的有限集數(shù)據(jù)元素的有限集

8、， S 是 D上關(guān)系的有限集關(guān)系的有限集。例例2 2：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)設(shè)數(shù)據(jù)邏輯結(jié)構(gòu) B=B=（K K，R R） K=kK=k1 1, k, k2 2, , k, , k9 9 R= k R= ，k ，k ，k ，k ，k ，k ，k ，k ，k ，k 畫出這邏輯結(jié)構(gòu)的圖示，并確定那些畫出這邏輯結(jié)構(gòu)的圖示，并確定那些是起點，那些是終點是起點，那些是終點數(shù)據(jù)結(jié)構(gòu)的存儲方式數(shù)據(jù)結(jié)構(gòu)的存儲方式 數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的存儲包括數(shù)據(jù)數(shù)據(jù)元素的存儲元素的存儲和和元素之間的關(guān)系的表示元素之間的關(guān)系的表示。 元素之間的關(guān)系在計算機中有兩種不同的元素之間的關(guān)系在計算機中有兩種不同

9、的表示方法：順序表示和非順序表示。由此表示方法：順序表示和非順序表示。由此得出兩種不同的存儲結(jié)構(gòu)：得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)和和鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)。 順序存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)結(jié)構(gòu)( (關(guān)系關(guān)系) )。 數(shù)據(jù)元素存放的數(shù)據(jù)元素存放的地址是連續(xù)的地址是連續(xù)的 鏈?zhǔn)酱鎯Y(jié)構(gòu)：鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針加一個存放另一個元素地址的指針(pointer )(pointer )，用該指針來表示數(shù)據(jù)元素，用該指

10、針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)之間的邏輯結(jié)構(gòu)( (關(guān)系關(guān)系) )。 數(shù)據(jù)元素存放的數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求地址是否連續(xù)沒有要求 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方面，一個面，一個算法的設(shè)計取決于算法的設(shè)計取決于所選定的所選定的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)，而而算法的實現(xiàn)依賴于算法的實現(xiàn)依賴于所采用的所采用的存儲結(jié)構(gòu)存儲結(jié)構(gòu)。例：一維數(shù)組（順序），結(jié)構(gòu)體（鏈?zhǔn)剑├阂痪S數(shù)組（順序），結(jié)構(gòu)體（鏈?zhǔn)剑?shù)據(jù)結(jié)構(gòu)的三個組成部分：數(shù)據(jù)結(jié)構(gòu)的三個組成部分：邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)： 數(shù)據(jù)元素之間邏輯關(guān)系的描述數(shù)據(jù)元素之間邏輯關(guān)系的描述 D_S= D_S=（D D，S

11、S）存儲結(jié)構(gòu)存儲結(jié)構(gòu)： 數(shù)據(jù)元素在計算機中的存儲及其數(shù)據(jù)元素在計算機中的存儲及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲結(jié)構(gòu)或物理結(jié)構(gòu)。結(jié)構(gòu)。數(shù)據(jù)操作數(shù)據(jù)操作： 對數(shù)據(jù)要進行的運算。對數(shù)據(jù)要進行的運算。線性表線性表樹樹圖圖順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)復(fù)合存儲結(jié)構(gòu)復(fù)合存儲結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)物理結(jié)構(gòu)邏輯結(jié)構(gòu)與所采用的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表棧和隊列數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系數(shù)據(jù)類型數(shù)據(jù)類型(Dat

12、a Type)(Data Type)：指的是：指的是一個值的集合一個值的集合和和定義在定義在該值集上的一組操作該值集上的一組操作的總稱。的總稱。數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。數(shù)據(jù)類型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個概念。 在在C C語言中數(shù)據(jù)類型有：基本類型和構(gòu)造類型。語言中數(shù)據(jù)類型有：基本類型和構(gòu)造類型。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。述數(shù)據(jù)對象各元素之間的相互關(guān)系。數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型 在用高級程序語言編寫的程序中，必須

13、對程序中出現(xiàn)的每個變量、常量或表達式，明確說明明確說明它們所屬的數(shù)據(jù)類型數(shù)據(jù)類型 例如，C語言提供的整型，浮點型，雙精度型，字符型等等 數(shù)據(jù)類型不同，操作也不同,字符，數(shù)值？各種高級程序設(shè)計語言中都擁有“整數(shù)”類型，盡管它們在不同處理器上實現(xiàn)的方法不同，但對程序員而言是“相同的”，因為它們的數(shù)學(xué)特性相同。從“數(shù)學(xué)抽象”的角度看，可稱它為一個“抽象數(shù)據(jù)類型” 。例如例如: :“整數(shù)”是一個抽象數(shù)據(jù)類型。其數(shù)學(xué)特性和具體的計算機或語言無關(guān)?！俺橄蟆钡囊饬x在于強調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。抽象數(shù)據(jù)類型還包括用戶在設(shè)計軟件系統(tǒng)時自己定義的數(shù)據(jù)類型。在構(gòu)造軟件系統(tǒng)的各個相對獨立的模塊時，定義一組數(shù)據(jù)一組數(shù)據(jù)和

14、施與這些數(shù)據(jù)之上的一組操一組操作作，并在模塊內(nèi)部內(nèi)部給出它們的表示和實現(xiàn)細表示和實現(xiàn)細節(jié)節(jié)，在模塊外部外部使用的只是抽象的數(shù)據(jù)和抽抽象的數(shù)據(jù)和抽象的操作象的操作。抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D D，S S，P P）三元組表示其中，D 是數(shù)據(jù)對象， S 是 D 上的關(guān)系集， P 是對 D 的基本操作集。 ADTADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)對象：數(shù)據(jù)對象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義 ADT ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名基本操作名（參數(shù)表） 初始條件：初始條件：初

15、始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述 賦值參數(shù)賦值參數(shù) 只為操作提供輸入值；引用參數(shù)引用參數(shù) 以& &打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。操作結(jié)果操作結(jié)果 說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。例如，例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)復(fù)數(shù)” 數(shù)據(jù)對象：數(shù)據(jù)對象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分 ADT Complex ADT Comp

16、lex 基本操作：基本操作： AssignComplex( &Z, v1, v2 )AssignComplex( &Z, v1, v2 )操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實部和虛部 分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( &Z)DestroyComplex( &Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realPart )GetReal( Z, &realPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實部值。 GetImag( Z, &ImagPart )GetImag(

17、 Z, &ImagPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。 Add( z1,z2, &sum )Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個復(fù)數(shù)z1, z2 的 和值。 ADT Complex ADT ComplexADT ADT 有兩個重要特征:數(shù)據(jù)抽象數(shù)據(jù)抽象 用ADTADT描述程序處理的實體時，強調(diào)的是其本質(zhì)的特征本質(zhì)的特征、其所能完成的功能其所能完成的功能以及它和外部用戶的接口外部用戶的接口（即外界使用它的方外界使用它的方法法）數(shù)據(jù)封裝數(shù)據(jù)封裝 將實體的外部特性和其內(nèi)部實現(xiàn)

18、外部特性和其內(nèi)部實現(xiàn)細節(jié)分離細節(jié)分離，并且對外部用戶隱藏其內(nèi)部實對外部用戶隱藏其內(nèi)部實現(xiàn)細節(jié)現(xiàn)細節(jié)抽象數(shù)據(jù)類型的表示和實現(xiàn)抽象數(shù)據(jù)類型的表示和實現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。typedef struct typedef struct floatfloat realpart； floatfloat imagpart； complex；例如，上面所提到的復(fù)數(shù)數(shù)據(jù)類型例如，上面所提到的復(fù)數(shù)數(shù)據(jù)類型/ -/ -存儲結(jié)構(gòu)的定義存儲結(jié)構(gòu)的定義/ -/ -基本操作的實現(xiàn)基本操作的實現(xiàn)void add( complex z1, complex z2,

19、complex &sum ) / 以 sum 返回兩個復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 算法和算法的衡量算法和算法的衡量一、算法一、算法二、算法設(shè)計的原則二、算法設(shè)計的原則三、算法效率的衡量方法和準(zhǔn)則三、算法效率的衡量方法和準(zhǔn)則四、算法的存儲空間需求四、算法的存儲空間需求算法算法是為了解決某類問題而規(guī)定的一個有限長的操作序列操作序列，是求解方法、步驟的一個精精確描述確描述。一個算法必須滿足以下五五個重要特特性性：1 1有窮性有窮

20、性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出算法算法1 1有窮性有窮性 對于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間有限時間內(nèi)完成； 2 2確定性確定性 對于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且并且在任在任何條件下，算法都只有一條執(zhí)行路徑；何條件下，算法都只有一條執(zhí)行路徑；3 3可行性可行性 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；4 4有輸入有輸入 作為算法加工對象的量值，通常體現(xiàn)為算法中的

21、一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中； 5 5有輸出有輸出 它是一組與“輸入”存在確定關(guān)系的量值，是算法進行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。1 1有窮性有窮性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出例：解決“燈不亮了”的算法二、算法設(shè)計的原則二、算法設(shè)計的原則設(shè)計算法時，通常應(yīng)考慮達到以下目標(biāo)：1 1正確性正確性2. 2. 可讀性可讀性3 3健壯性健壯性5 5高效率與低存儲量需求高效率與低存儲量需求4 4通用性通用性1 1正確性正確性首先，首先，算法應(yīng)當(dāng)滿足滿足以特定的“規(guī)格規(guī)

22、格說明說明”方式給出的需求需求。其次，其次，對算法是否“正確正確”的的理解可以有以下四個層次四個層次：a a程序中不含語法錯誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； c c程序?qū)τ诰倪x擇的、典型、苛刻且程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；要求的結(jié)果；通常以第 c c 層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。 d d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；2. 2. 可讀性可讀性算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計算機執(zhí)行。因此算法應(yīng)該易于易于人的理解理解；另一方面，晦

23、澀難讀的程序易于隱藏較多錯誤而難以調(diào)試；3 3魯棒性魯棒性/ /健壯性健壯性當(dāng)輸入的數(shù)據(jù)非法非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M行相應(yīng)處理進行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯處理出錯的方法的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個表示錯誤或錯誤性質(zhì)的值表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進行處理。4 4通用性通用性算法應(yīng)能解決一類問題，而非針對某些特定輸入。5 5高效率與低存儲量需求高效率與低存儲量需求通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。三、算法效率的衡量方法和準(zhǔn)則三、算法效率的衡量方法和準(zhǔn)則通常

24、有兩種兩種衡量算法效率的方法: 事后統(tǒng)計法事后統(tǒng)計法事前分析估算法事前分析估算法缺點：缺點：1。必須執(zhí)行程序 2。其它因素掩蓋算法本質(zhì)和算法執(zhí)行時間時間相關(guān)的因素因素：1 1算法算法選用的策略的策略2 2問題的規(guī)模問題的規(guī)模3 3編寫程序的語言語言4 4編譯編譯程序產(chǎn)生的機器代碼的質(zhì)量的質(zhì)量5 5計算機計算機執(zhí)行指令的速度的速度一個給定算法的算法的“運行工作量運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)是問題規(guī)模的函數(shù)。算法的執(zhí)行時間算法的執(zhí)行時間 =基本操作的執(zhí)行次數(shù)基本操作的執(zhí)行次數(shù)基本操作的執(zhí)行時間基本操作的執(zhí)行時間 算法的執(zhí)行時間算法的執(zhí)行時

25、間 與與 基本操作執(zhí)行次數(shù)之和基本操作執(zhí)行次數(shù)之和 成正比成正比 多種基本操作？求和處理假如，隨著問題規(guī)模 n 的增長，算算法執(zhí)行時間的增長率和法執(zhí)行時間的增長率和 f(n) f(n) 的增長的增長率相同率相同，則可記作：T (n) = O(f(n)T (n) = O(f(n)稱稱T (n) T (n) 為算法的為算法的(漸近)時間復(fù)雜時間復(fù)雜度度定義: 給定兩個非負函數(shù)f(n) 和 g(n), 如果存在一個正整數(shù)n0 以及一個常數(shù)k0 使得f(n)kg(n) 對于任意nn0 的正整數(shù)都成立，那么我們說f(n)=O(g(n), 關(guān)于“Big Oh”使用正確的“Big Oh”表示 如果f(n)

26、是一個d次多項式，那么f(n) 是 O(nd) 基本原則： 舍棄低階項 舍棄常數(shù)系數(shù) 使用最低的可能數(shù)量級 正確：“100n 是O(n)” ，錯誤：“100n 是O(n2)” 使用最簡標(biāo)注 正確：“3n + 5 是 O(n)” ，錯誤：“3n + 5 是 O(3n)”void mult(int a, int b, int& c ) / 以二維數(shù)組存儲矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k1 & change; -i) change=false;for (j=0;

27、 jaj+1) aj aj+1 ; change=TURE ; 最好情況：最好情況：0 0次次 最壞情況：最壞情況：1+2+3+1+2+3+ +n-1=n(n-1)/2+n-1=n(n-1)/2 平均時間復(fù)雜度為：平均時間復(fù)雜度為： O(nO(n2 2) ) 四、算法的存儲空間需求四、算法的存儲空間需求算法的空間復(fù)雜度定義為空間復(fù)雜度定義為: :表示隨著問題規(guī)模表示隨著問題規(guī)模 n n 的增大，的增大，算法運行所需存儲量的增長率算法運行所需存儲量的增長率與與 g(n) g(n) 的增長率相同。的增長率相同。S(n) = O(g(n)S(n) = O(g(n)算法的存儲量算法的存儲量包括:1輸入數(shù)據(jù)輸入數(shù)據(jù)所占空間2程序本身程序本身所