第一章緒 論

1、第一章緒 論,1.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇,1.2 基本概念,1.3 算法和算法的量度,,1.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇,Niklaus Wirth： Algorithm + Data Structures = Programs,程序設(shè)計(jì):算法: 數(shù)據(jù)結(jié)構(gòu):,為計(jì)算機(jī)處理問(wèn)題編制 一組指令集,處理問(wèn)題的策略,問(wèn)題的數(shù)學(xué)模型,結(jié)構(gòu)靜力分析計(jì)算,例如: 數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題,─━ 線性代數(shù)方程

2、組,─━ 環(huán)流模式方程 (球面坐標(biāo)系),全球天氣預(yù)報(bào),非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題,例一: 求一組(n個(gè))整數(shù)中的最大值,算法: ?模型：？,基本操作是“比較兩個(gè)數(shù)的大小”,取決于整數(shù)值的范圍,例二：計(jì)算機(jī)對(duì)弈,算法：?模型：?,對(duì)弈的規(guī)則和策略,棋盤(pán)及棋盤(pán)的格局,例三：足協(xié)的數(shù)據(jù)庫(kù)管理,算法：?模型：?,需要管理的項(xiàng)目？如何管理？ 用戶界面？,各種表格,概括地說(shuō)：,數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型

3、(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。,,1.2 基本概念,一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu),二、數(shù)據(jù)類(lèi)型,三、抽象數(shù)據(jù)類(lèi)型,,一、數(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)中討論的基本單位,數(shù)據(jù)項(xiàng)：,是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位,數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合,例如：

4、,描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是,稱之為組合項(xiàng),,數(shù)據(jù)結(jié)構(gòu)：,帶結(jié)構(gòu)的數(shù)據(jù)元素的集合,假設(shè)用三個(gè) 4 位的十進(jìn)制數(shù)表示一個(gè)含 12 位數(shù)的十進(jìn)制數(shù)。,3214,6587,9345 ─ a1(3214),a2(6587),a3(9345),則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序”關(guān)系 ?a1,a2?、?a2,a3?,3214，6587，9345 a1 a2 a3,6587，3214，93

5、45 a2 a1 a3,≠,例如:,又例，在2行3列的二維數(shù)組{a1, a2, a3, a4, a5, a6}中六個(gè)元素之間存在兩個(gè)關(guān)系:,行的次序關(guān)系:列的次序關(guān)系:,row = {,,,},col = {,,},a1 a3 a5 a2 a4 a6,a1 a2 a3a4 a5 a6,,,,再例，在一維數(shù)組 {a1, a2, a3, a4, a5, a6} 的數(shù)據(jù)元素之間存在

6、如下的次序關(guān)系:,{| i=1, 2, 3, 4, 5},或者說(shuō)，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。,可見(jiàn)，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”,數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類(lèi):,線性結(jié)構(gòu),樹(shù)形結(jié)構(gòu),圖狀結(jié)構(gòu),集合結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的形式定義為:,數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組,Data_Structures = (D, S),其中:D 是數(shù)據(jù)元素的有限集， S 是 D上關(guān)系的有限集。,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),—— 邏輯結(jié)構(gòu)在存儲(chǔ)器

7、中的映象,“數(shù)據(jù)元素”的映象 ？,“關(guān)系”的映象 ？,數(shù)據(jù)元素的映象方法：,用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素,(321)10 = (501)8 = (101000001)2,A = (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)中

8、只含數(shù)據(jù)元素本身的信息,x y,,,,,,,鏈?zhǔn)接诚?以附加信息(指針)表示后繼關(guān)系,需要用一個(gè)和 x 在一起的附加信息指示 y 的存儲(chǔ)位置,y x,,,,,,,,,,在不同的編程環(huán)境中，,存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。,當(dāng)用高級(jí)程序設(shè)計(jì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類(lèi)型描述之。,例如:,以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用 C 語(yǔ)言中提供的整數(shù)數(shù)組類(lèi)型。,typedef int Long_in

9、t [3],定義長(zhǎng)整數(shù)為:,,二、數(shù)據(jù)類(lèi)型,在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明它們所 屬的數(shù)據(jù)類(lèi)型。,例如，C 語(yǔ)言中提供的基本數(shù)據(jù)類(lèi)型有:,整型 int,浮點(diǎn)型 float,字符型 char,邏輯型 bool （ C++語(yǔ)言）,雙精度型 double,,實(shí)型（ C++語(yǔ)言）,數(shù)據(jù)類(lèi)型 是一個(gè) 值的集合和定義在此集合上的 一組操作的總稱。,不同類(lèi)型的

10、變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。,,三、抽象數(shù)據(jù)類(lèi)型 (Abstract Data Type 簡(jiǎn)稱ADT),是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。,例如，抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義：,數(shù)據(jù)對(duì)象： D＝{e1,e2｜e1,e2∈RealSet } 數(shù)據(jù)關(guān)系： R1＝{ | e1是復(fù)數(shù)的實(shí)數(shù)部分 | e2 是復(fù)數(shù)的虛數(shù)部分 },

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

12、agPart )初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。,Add( z1,z2, &sum )初始條件：z1, z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1, z2 的 和值。,} ADT Complex,假設(shè):z1和z2是上述定義的復(fù)數(shù),則 Add(z1, z2, z3) 操作的結(jié)果,z3 = z1 + z2,即為用戶企求的結(jié)果,ADT 有兩個(gè)重要特征:,數(shù)據(jù)抽象,用A

13、DT描述程序處理的實(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ù)類(lèi)型的描述方法,抽象數(shù)據(jù)類(lèi)型可用（D，S，P）三元組表示。其中：D 是數(shù)據(jù)對(duì)象； S 是 D 上的關(guān)系集； P 是對(duì) D 的基本操作集。,ADT 抽象數(shù)據(jù)類(lèi)型名 { 數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定

14、義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作的定義〉} ADT 抽象數(shù)據(jù)類(lèi)型名,其中基本操作的定義格式為:,基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉 操作結(jié)果：〈操作結(jié)果描述〉,抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn),抽象數(shù)據(jù)類(lèi)型需要通過(guò)固有數(shù)據(jù)類(lèi)型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型)來(lái)實(shí)現(xiàn)。,例如，對(duì)以上定義的復(fù)數(shù)。,typedef struct { float realpart；

15、float imagpart；}complex；,// -----存儲(chǔ)結(jié)構(gòu)的定義,// -----基本操作的函數(shù)原型說(shuō)明,void Assign( complex &Z, float realval, float imagval )；// 構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) // realval 和 imagval 的值,float GetReal( cpmp

16、lex Z )； // 返回復(fù)數(shù) Z 的實(shí)部值,float Getimag( cpmplex Z )； // 返回復(fù)數(shù) Z 的虛部值,void add( complex z1, complex z2, complex &sum )； // 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和,// -----基本操作的實(shí)現(xiàn),void add(

17、complex z1, complex z2, complex &sum ) { // 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart;},{ 其它省略 },,1.3

18、算法和算法的衡量,一、算法,二、算法設(shè)計(jì)的原則,三、算法效率的衡量方法和準(zhǔn)則,四、算法的存儲(chǔ)空間需求,,算法是為了解決某類(lèi)問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：,1．有窮性 2．確定性 3．可行性4．有輸入 5．有輸出,一、算法,1．有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。,2．確定性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有

19、確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。,3．可行性 算法中的所有操作都必須足夠基本，都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。,4．有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過(guò)程中輸入，而有的算法表面上可以沒(méi)有輸入，實(shí)際上已被嵌入算法之中。,5．有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這

20、種確定關(guān)系即為算法的功能。,,二、算法設(shè)計(jì)的原則,設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：,1．正確性,2. 可讀性,3．健壯性,4．高效率與低存儲(chǔ)量需求,,1．正確性,首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說(shuō)明”方式給出的需求。,其次，對(duì)算法是否“正確”的理解可以有以下四個(gè)層次：,a．程序中不含語(yǔ)法錯(cuò)誤；,b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；,c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；,通常

21、以第 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ì)

22、的值，以便在更高的抽象層次上進(jìn)行處理。,,4．高效率與低存儲(chǔ)量需求,通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間，兩者都與問(wèn)題的規(guī)模有關(guān)。,,三、算法效率的 衡量方法和準(zhǔn)則,通常有兩種衡量算法效率的方法:,事后統(tǒng)計(jì)法,事前分析估算法,缺點(diǎn)：1．必須執(zhí)行程序 2．其它因素掩蓋算法本質(zhì),和算法執(zhí)行時(shí)間相關(guān)的因素：,1．算法選用的策略,2．問(wèn)題的規(guī)模,3．編寫(xiě)程序的語(yǔ)言,4．編譯程序產(chǎn)生的

23、機(jī)器代碼的質(zhì)量,5．計(jì)算機(jī)執(zhí)行指令的速度,一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用整數(shù)量n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。,假如，隨著問(wèn)題規(guī)模 n 的增長(zhǎng)，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f(n) 的增長(zhǎng)率相同，則可記作：,T (n) = O(f(n)),稱T (n) 為算法的(漸近)時(shí)間復(fù)雜度。,如何估算 算法的時(shí)間復(fù)雜度？,算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類(lèi)型的操作）,算法的

24、執(zhí)行時(shí)間 =原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間,算法的執(zhí)行時(shí)間 與 原操作執(zhí)行次數(shù)之和 成正比,從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是 基本操作 的原操作，以該基本操作 在算法中重復(fù)執(zhí)行的次數(shù) 作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。,例一兩個(gè)矩陣相乘,void mult(int a[], int b[], int& c[] ) { // 以二維數(shù)組存儲(chǔ)矩陣元素，c 為

25、 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,基本操作: 乘法操作,時(shí)間復(fù)雜度: O(n3),例二選擇排

26、序,void select_sort(int& a[], int n) { // 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 } // select_sort,基本操作: 比較(數(shù)據(jù)元素)操作,時(shí)間復(fù)雜度: O(n2),j = i; // 選擇第 i 個(gè)最小元素for ( k = i+1; k < n; ++k ) if (a[k] < a[j] ) j =

27、 k;,for ( i = 0; i< n-1; ++i ) { if ( j != i ) a[j] ←→ a[i]},例三起泡排序,void bubble_sort(int& a[], int n) { // 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for (i=n-1, change=TRUE; i>1 && change; --i)

28、} // bubble_sort,基本操作: 賦值操作,時(shí)間復(fù)雜度: O(n2),{ change = FALSE; // change 為元素進(jìn)行交換標(biāo)志 for (j=0; j a[j+1]) { a[j] ←→ a[j+1]; change = TRUE ;}} // 一趟起泡,,四、算法的存儲(chǔ)空間需求,算法的空間復(fù)雜度定義為:,表示隨著問(wèn)題規(guī)模 n 的增大，算法運(yùn)行

29、所需存儲(chǔ)量的增長(zhǎng)率與 g(n) 的增長(zhǎng)率相同。,S(n) = O(g(n)),算法的存儲(chǔ)量包括:,1．輸入數(shù)據(jù)所占空間,2．程序本身所占空間,3．輔助變量所占空間,若輸入數(shù)據(jù)所占空間只取決于問(wèn)題 本身，和算法無(wú)關(guān)，則只需要分析除 輸入和程序之外的輔助變量所占額外 空間。,若所需額外空間相對(duì)于輸入數(shù)據(jù)量 來(lái)說(shuō)是常數(shù)，則稱此算法為原地工作。,若所需存儲(chǔ)量依賴于特定的輸入，則通常按最壞情況考慮。,,1. 熟悉各名詞