第1章緒論(2)

1、11.1 數(shù)據(jù)結(jié)構(gòu)的定位數(shù)據(jù)結(jié)構(gòu)的定位1.2 基本概念基本概念1.3 算法和算法的分析算法和算法的分析21.2 基本概念基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型3二、數(shù)據(jù)類型二、數(shù)據(jù)類型 在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明明確說(shuō)明它們所 屬的數(shù)據(jù)類型數(shù)據(jù)類型。 數(shù)據(jù)類型數(shù)據(jù)類型 是一個(gè)值的集合值的集合和定義在此集合上的一組操作的總稱一組操作的總稱。4例如，例如，C 語(yǔ)言中提供的基本數(shù)據(jù)類型有語(yǔ)言中提供的基本數(shù)據(jù)類型有: :整型整型 short intshort int，intint，lon

2、g intlong int實(shí)型：實(shí)型： floatfloat，doubledouble字符型：字符型：charchar 不同類型的變量，其所能取的值的范圍值的范圍不同，所能進(jìn)行的操作進(jìn)行的操作不同。5問(wèn)題問(wèn)題1 1：是否所有的計(jì)算機(jī)語(yǔ)言都需要聲明數(shù)據(jù)類型？：是否所有的計(jì)算機(jī)語(yǔ)言都需要聲明數(shù)據(jù)類型？答：答： 不是，匯編語(yǔ)言不需要聲明數(shù)據(jù)類型。不是，匯編語(yǔ)言不需要聲明數(shù)據(jù)類型。問(wèn)題問(wèn)題2 2：在高級(jí)語(yǔ)言中，是否需要對(duì)每個(gè)變量都聲明數(shù)：在高級(jí)語(yǔ)言中，是否需要對(duì)每個(gè)變量都聲明數(shù)據(jù)類型？據(jù)類型？答：不是，有些高級(jí)語(yǔ)言可以對(duì)某些類型的變量不需要聲明答：不是，有些高級(jí)語(yǔ)言可以對(duì)某些類型的變量不需要聲明。問(wèn)題

3、問(wèn)題3 3：為什么在：為什么在javajava，C C，C C等高級(jí)語(yǔ)言中要強(qiáng)制等高級(jí)語(yǔ)言中要強(qiáng)制聲明變量類型？聲明變量類型？答：答：1 1。避免造成一些不易發(fā)現(xiàn)的邏輯錯(cuò)誤，。避免造成一些不易發(fā)現(xiàn)的邏輯錯(cuò)誤，2 2。通過(guò)數(shù)據(jù)類型實(shí)現(xiàn)信息隱藏，。通過(guò)數(shù)據(jù)類型實(shí)現(xiàn)信息隱藏，3 3。動(dòng)態(tài)分配和回收內(nèi)存。動(dòng)態(tài)分配和回收內(nèi)存。問(wèn)題問(wèn)題4: 4: 不同高級(jí)語(yǔ)言的數(shù)據(jù)類型定義是否相同？不同高級(jí)語(yǔ)言的數(shù)據(jù)類型定義是否相同？答：不同。這就是為什么不同語(yǔ)言編寫的程序不能夠互操作的原答：不同。這就是為什么不同語(yǔ)言編寫的程序不能夠互操作的原因之一。因之一。6三、抽象數(shù)據(jù)類型三、抽象數(shù)據(jù)類型 (Abstract Dat

4、a Type 簡(jiǎn)稱簡(jiǎn)稱ADT) 是指一個(gè)是指一個(gè)數(shù)學(xué)模型數(shù)學(xué)模型以及定義在以及定義在此數(shù)學(xué)模型上的一組操作。此數(shù)學(xué)模型上的一組操作。 與具體實(shí)現(xiàn)的語(yǔ)言無(wú)關(guān)。與具體實(shí)現(xiàn)的語(yǔ)言無(wú)關(guān)。7例如例如: :“整數(shù)整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。是一個(gè)抽象數(shù)據(jù)類型。其其數(shù)學(xué)特性和具體的計(jì)算機(jī)或語(yǔ)言無(wú)關(guān)。數(shù)學(xué)特性和具體的計(jì)算機(jī)或語(yǔ)言無(wú)關(guān)。 C C語(yǔ)言的整型語(yǔ)言的整型“intint”只實(shí)現(xiàn)了一個(gè)只實(shí)現(xiàn)了一個(gè)從從3276832768到到3276732767之間的整數(shù)的集合。之間的整數(shù)的集合。8抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D，S，P）三元組表示其中，D 是數(shù)據(jù)對(duì)象集， S 是 D 上的關(guān)

5、系集， P 是對(duì) D 的基本操作集。 9ADT 抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名基本操作名（參數(shù)表） 初始條件：初始條件：初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述 10類類C C語(yǔ)言語(yǔ)言 精選了精選了C C語(yǔ)言的一個(gè)核心子集，同時(shí)作了語(yǔ)言的一個(gè)核心子集，同時(shí)作了若干擴(kuò)充修改，增強(qiáng)了語(yǔ)言的描述功能。以若干擴(kuò)充修改，增強(qiáng)了語(yǔ)言的描述功能。以下作簡(jiǎn)要說(shuō)明。下作簡(jiǎn)要說(shuō)明。（1 1）預(yù)定義常量和類型：）預(yù)定義常量和類型：# #define

6、 TRUE 1define TRUE 1#define FALSE 0#define FALSE 0#define OK 1#define OK 1#define ERROR 0#define ERROR 0#define INFEASIBLE 1#define INFEASIBLE 1#define OVERFLOW -2#define OVERFLOW -2typedef int typedef int Status; Status; 11（2 2）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型）數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義（定義（typedeftypedef）描述，數(shù)據(jù)元素的類型約）描述，數(shù)據(jù)

7、元素的類型約定為定為ElemTypeElemType，由用戶在使用該類型時(shí)自行，由用戶在使用該類型時(shí)自行定義。定義。（3 3）基本操作的算法都用以下形式的函數(shù)）基本操作的算法都用以下形式的函數(shù)描述：描述：函數(shù)類型函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）函數(shù)名（函數(shù)參數(shù)表） /算法說(shuō)明算法說(shuō)明語(yǔ)句序列語(yǔ)句序列/函數(shù)名函數(shù)名 12算法中使用的輔助變量可以不做變量說(shuō)明。算法中使用的輔助變量可以不做變量說(shuō)明。一般而言，一般而言，a,b,c,d,ea,b,c,d,e等用作數(shù)據(jù)元素名，等用作數(shù)據(jù)元素名，i,j,k,l,m,ni,j,k,l,m,n等用作整型變量名等用作整型變量名,p,q,r,p,q,r等用作等用作指

8、針變量名。函數(shù)定義為指針變量名。函數(shù)定義為Status Status 類型。為了類型。為了便于算法描述，函數(shù)的參數(shù)除了值傳遞方式便于算法描述，函數(shù)的參數(shù)除了值傳遞方式外，增添了外，增添了c+c+語(yǔ)言的引用調(diào)用的參數(shù)傳遞方語(yǔ)言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以式。在形參表中，以& &打頭的參數(shù)即為引用參打頭的參數(shù)即為引用參數(shù)。數(shù)。13函數(shù)調(diào)用時(shí)的參數(shù)傳遞函數(shù)調(diào)用時(shí)的參數(shù)傳遞值傳遞值傳遞把實(shí)參的值傳給被調(diào)用函數(shù)的副本中。被把實(shí)參的值傳給被調(diào)用函數(shù)的副本中。被調(diào)用函數(shù)修改的是副本的值，實(shí)參不變。調(diào)用函數(shù)修改的是副本的值，實(shí)參不變。引用傳遞引用傳遞 & :& :

9、被傳遞的不是實(shí)參的值，而是實(shí)參的地址。被傳遞的不是實(shí)參的值，而是實(shí)參的地址。被調(diào)用函數(shù)通過(guò)地址存取被引用的實(shí)參，函數(shù)執(zhí)被調(diào)用函數(shù)通過(guò)地址存取被引用的實(shí)參，函數(shù)執(zhí)行后實(shí)參的值將發(fā)生改變。行后實(shí)參的值將發(fā)生改變。 int int a=1;b=2; a=1;b=2; swap(a,b); swap(a,b); void swap(int &i,int void swap(int &i,int &j) &j) int int t=j; t=j; j=i; j=i; i=t; i=t; Assign( &Z, v1, v2 )14（4 4）賦值語(yǔ)句）賦值語(yǔ)句簡(jiǎn)單賦

10、值簡(jiǎn)單賦值 變量名變量名= =表達(dá)式表達(dá)式串聯(lián)賦值串聯(lián)賦值 變量名變量名1=1=變量名變量名2=2= =表達(dá)式表達(dá)式成組賦值成組賦值 （變量名（變量名1 1，變量名，變量名2.2.）= =（表達(dá)式（表達(dá)式1 1，表達(dá)，表達(dá)式式2 2）結(jié)構(gòu)名結(jié)構(gòu)名= =結(jié)構(gòu)名結(jié)構(gòu)名結(jié)構(gòu)名結(jié)構(gòu)名=值值1 1，值，值2 2.數(shù)組名數(shù)組名=表達(dá)式表達(dá)式數(shù)組名數(shù)組名 起始下標(biāo)，終止下標(biāo)起始下標(biāo)，終止下標(biāo)=數(shù)組名數(shù)組名 起始下標(biāo)，終起始下標(biāo)，終止下標(biāo)止下標(biāo) 交換賦值交換賦值 變量名變量名 - - 變量名變量名條件賦值條件賦值 變量名變量名= =條件表達(dá)式？表達(dá)式條件表達(dá)式？表達(dá)式T T：表達(dá)式：表達(dá)式F F15（5 5）

11、選擇語(yǔ)句）選擇語(yǔ)句條件語(yǔ)句條件語(yǔ)句1 if 1 if 語(yǔ)句語(yǔ)句條件語(yǔ)句條件語(yǔ)句2 if else 2 if else 語(yǔ)句語(yǔ)句開關(guān)語(yǔ)句開關(guān)語(yǔ)句1 switch(1 switch(表達(dá)式表達(dá)式)case )case 值值1 :1 :開關(guān)語(yǔ)句開關(guān)語(yǔ)句2 2 switcheswitchecase case 條件條件1 1： （6 6）循環(huán)語(yǔ)句）循環(huán)語(yǔ)句for for 語(yǔ)句語(yǔ)句while while 語(yǔ)句語(yǔ)句do while do while 語(yǔ)句語(yǔ)句 16（7 7）結(jié)束語(yǔ)句）結(jié)束語(yǔ)句函數(shù)結(jié)束語(yǔ)句函數(shù)結(jié)束語(yǔ)句 return return case case 結(jié)束語(yǔ)句結(jié)束語(yǔ)句 breakbreak異常結(jié)

12、束語(yǔ)句異常結(jié)束語(yǔ)句 exit(exit(異常代碼異常代碼) )（8 8）輸入輸出語(yǔ)句）輸入輸出語(yǔ)句輸入語(yǔ)句輸入語(yǔ)句 scanfscanf(a,b,c)(a,b,c)輸出語(yǔ)句輸出語(yǔ)句 printfprintf(a,b,c)(a,b,c)（9 9）注釋）注釋 / 17（1010）基本函數(shù)）基本函數(shù)求最大值求最大值 max()max()求最小值求最小值 min()min()求絕對(duì)值求絕對(duì)值 abs()abs()向下取整向下取整 floor()floor()向上取整向上取整 ceil()ceil()判定文件結(jié)束判定文件結(jié)束 eofeof()()判定行結(jié)束判定行結(jié)束eolneoln()()（1111）邏

13、輯運(yùn)算約定）邏輯運(yùn)算約定18例如，例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)復(fù)數(shù)” 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： De1,e2e1,e2RealSet 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | e1是復(fù)數(shù)的實(shí)數(shù)部分, | e2 是復(fù)數(shù)的虛數(shù)部分 ADT Complex 19基本操作：基本操作： AssignComplex( &Z, v1, v2 ) 初始條件：初始條件：&Z為非空。 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部 分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( &Z) 初始條件：初始條件：復(fù)數(shù)Z存在。 操作結(jié)果：復(fù)數(shù)Z被銷毀。 GetReal( Z, &realP

14、art ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。20 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 的 和值。 ADT Complex211.3 1.3 算法和算法的分析算法和算法的分析一、算法一、算法二、算法設(shè)計(jì)的原則二、算法設(shè)計(jì)的原則三、算法效率的度量方法和準(zhǔn)則三、算法效率的度量方法和準(zhǔn)則四、算法的存儲(chǔ)空間需求四、算法的存儲(chǔ)空間需求22 算法算法是為了解決某類

15、問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列操作序列。一個(gè)算法必須滿足以下五五個(gè)重要特性特性：1 1有窮性有窮性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出一、算法一、算法231 1有窮性有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間有限時(shí)間內(nèi)完成； 2 2確定性確定性 對(duì)于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且并且在任何條件下，算法都只有一在任何條件下，算法都只有一條執(zhí)行路徑；條執(zhí)行路徑；243 3可行性可行性 算法中的所有操作都必須足夠

16、基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4 4有輸入有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中；25 5 5有輸出有輸出 它是一組與“輸入”與確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。26二、算法設(shè)計(jì)的原則二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求271 1正確性正確性 首先，首先，算法應(yīng)當(dāng)滿足滿足以特定的“規(guī)格規(guī)格說(shuō)明說(shuō)明”方式給出的需求需

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

18、藏較多錯(cuò)誤而難以調(diào)試；303健壯性健壯性 當(dāng)輸入的數(shù)據(jù)非法非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出處理出錯(cuò)的方法錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。314高效率與低存儲(chǔ)量需求高效率與低存儲(chǔ)量需求 通常，效率指的是通常，效率指的是算法執(zhí)行時(shí)算法執(zhí)行時(shí)間間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中中所需的最大存儲(chǔ)空間所需的最大存儲(chǔ)空間。兩者都。兩者都與問(wèn)題的規(guī)模有關(guān)。在有些情況與問(wèn)題的規(guī)模有關(guān)。在有些情況下，兩者相互矛盾下，兩者相互矛盾3

19、2三三、算法效率的、算法效率的 度量方法和準(zhǔn)則度量方法和準(zhǔn)則通常有兩種兩種衡量算法效率的方法: 事后統(tǒng)計(jì)法事后統(tǒng)計(jì)法事前分析估算法事前分析估算法缺點(diǎn)：缺點(diǎn)：1。必須執(zhí)行程序 2。其它因素掩蓋算法本質(zhì)33算法執(zhí)行時(shí)間時(shí)間相關(guān)的因素因素：1 1算法算法選用的策略的策略2 2問(wèn)題的規(guī)模問(wèn)題的規(guī)模3 3編寫程序的語(yǔ)言語(yǔ)言4 4編譯編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量的質(zhì)量5 5計(jì)算機(jī)計(jì)算機(jī)執(zhí)行指令的速度的速度34算法（程序）算法（程序）= = 控制結(jié)構(gòu)控制結(jié)構(gòu) + + 原操作原操作 （固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 =原操作原操作(i)(i)的的執(zhí)行次數(shù)執(zhí)行次數(shù)原操作原操作(i)(i)的執(zhí)行

20、時(shí)間的執(zhí)行時(shí)間 算法的執(zhí)行時(shí)間算法的執(zhí)行時(shí)間 與與 原操作執(zhí)行次數(shù)之和原操作執(zhí)行次數(shù)之和 成正比成正比 算法的執(zhí)行時(shí)間分析：算法的執(zhí)行時(shí)間分析：35例例一一兩兩個(gè)個(gè)矩矩陣陣相相乘乘void mult(int a, int b, int& c ) / 以二維數(shù)組存儲(chǔ)矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult原操作執(zhí)行次數(shù)之和：原操作執(zhí)行次數(shù)之和： 2 2n3 3n2 2n1 n+1n(n+1)n2 n2

21、 (n+1)n3 36n算法中所有語(yǔ)句的次數(shù)（頻度）之和是算法中所有語(yǔ)句的次數(shù)（頻度）之和是矩陣階矩陣階數(shù)數(shù)n n的函數(shù)的函數(shù) f(n) =f(n) = 2n2n3 3 + 3n + 3n2 2 + 2n +1 + 2n +1n一般地，稱一般地，稱n n是問(wèn)題的規(guī)模。執(zhí)行次數(shù)是問(wèn)題的規(guī)模。執(zhí)行次數(shù)f(n)f(n)是是關(guān)于關(guān)于n n的多項(xiàng)式函數(shù)的多項(xiàng)式函數(shù),f(n),f(n)與執(zhí)行時(shí)間成正比。與執(zhí)行時(shí)間成正比。n當(dāng)當(dāng)n n趨于無(wú)窮大時(shí)，把執(zhí)行次數(shù)函數(shù)趨于無(wú)窮大時(shí)，把執(zhí)行次數(shù)函數(shù)f(n)f(n)的數(shù)的數(shù)量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度量級(jí)（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度 T(n) = O(f(n) -T(n) = O(f(n) -大大O O表示表示漸進(jìn)漸進(jìn)T(n) = O(nT(n) = O(n3 3) ) 隨著問(wèn)題規(guī)模隨著問(wèn)題規(guī)模 n n 的增長(zhǎng)，算法執(zhí)行時(shí)間的的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率增長(zhǎng)率和和 f(n) f(n) 的的增長(zhǎng)率增長(zhǎng)率相同，相同，37 void select_sort(int& a , int n) / 將將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 / select_sortfor ( i = 0; i n; +i ) if ( j != i ) aj ai例例二二選選擇擇排排序序時(shí)間復(fù)雜度: