數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課件1

1、數(shù)據(jù)結(jié)構(gòu)（類C語(yǔ)言描述） 主講人：包曉安浙江理工大學(xué) 電科專業(yè)Email:bao_xiaoan第一章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念1.3算法及其量度1.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇Niklaus WirthAlgorithm+Data Structures=Programs程序設(shè)計(jì)：為計(jì)算機(jī)處理問(wèn)題編制一組指令集算法：處理問(wèn)題的策略數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型例如：數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題結(jié)構(gòu)靜力分析計(jì)算線性代數(shù)方程組預(yù)報(bào)人口增長(zhǎng)情況的數(shù)學(xué)模型微分方程非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例一：電話號(hào)碼查詢系統(tǒng) 設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排： (a1，b

2、1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒(méi)有這個(gè)人，則該算法也能夠報(bào)告沒(méi)有這個(gè)人的標(biāo)志。 算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)應(yīng)的電話號(hào)碼，或者說(shuō)依賴于名字和其電話號(hào)碼的結(jié)構(gòu)。 數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。 上述的問(wèn)題是一種數(shù)據(jù)結(jié)構(gòu)問(wèn)題?？蓪⒚趾蛯?duì)應(yīng)的電話號(hào)碼設(shè)計(jì)成：二維數(shù)組、表結(jié)構(gòu)、向量。 假定名字和其電話號(hào)碼邏輯上已安排成N元向量的形式，它的每個(gè)元素是一個(gè)數(shù)對(duì)(ai，bi)， 1in 數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義

3、的各種運(yùn)算的算法。例二：圖書館的書目檢索系統(tǒng)自動(dòng)化問(wèn)題例三：計(jì)算機(jī)和人對(duì)弈問(wèn)題例四：多叉路口交通燈的管理問(wèn)題概括地說(shuō)：數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型（非數(shù)值計(jì)算）及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)1.2 基本概念一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：所有能被輸入到計(jì)算機(jī)中，且被計(jì)算機(jī)處理的符號(hào)的集合計(jì)算機(jī)操作的對(duì)象的總稱是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式數(shù)據(jù)項(xiàng)：數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合例如：運(yùn)動(dòng)員（數(shù)據(jù)元素）姓名俱樂(lè)部名稱出生日期參加日期職務(wù)業(yè)績(jī)年月日數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 根據(jù)數(shù)

4、據(jù)元素間關(guān)系的不同特性，通常有下列四類基本的結(jié)構(gòu)：集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”，別無(wú)其他關(guān)系。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。（第25章）樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。（第6章）圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。 （第7章） （a）集合結(jié)構(gòu) （b）線性結(jié)構(gòu) （c）樹型結(jié)構(gòu) （d）圖形結(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)系的有限集。 例 復(fù)數(shù)的數(shù)

5、據(jù)結(jié)構(gòu)定義如下： Complex=(C，R) 其中：C是含兩個(gè)實(shí)數(shù)的集合C1，C2，分別表示復(fù)數(shù)的實(shí)部和虛部。R=P，P是定義在集合上的一種關(guān)系C1，C2。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有兩種不同的表示方法： 順序表示和非順序表示由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu):用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針，用此指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。關(guān)系的映像方法:(表示x,y的方法）順序映像 以存儲(chǔ)位置的相鄰表示后繼關(guān)系y的存儲(chǔ)位置和x的存儲(chǔ)位置之間差一個(gè)常量C而C是

6、一個(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ì)語(yǔ)言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語(yǔ)言中提供的數(shù)據(jù)類型描述之。例如：以三個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中提供的整數(shù)數(shù)組類型，定義長(zhǎng)整數(shù)為：typedef int long_int3二、數(shù)據(jù)類型在用高級(jí)程序語(yǔ)言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說(shuō)明他們所屬的數(shù)據(jù)類型。數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。例、在C語(yǔ)言中數(shù)據(jù)類型：基本類

7、型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義整型 定義在其上的操作為加減乘除和取模等算術(shù)運(yùn)算三、抽象數(shù)據(jù)類型（Abstract Data Type簡(jiǎn)稱ADT）是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作ADT有兩個(gè)重要特征：數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)特征，其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）例如：抽象數(shù)據(jù)類型復(fù)數(shù)的定義ADT Complex數(shù)據(jù)對(duì)象:D=e1,e2|e1,e2 RealSet數(shù)據(jù)關(guān)系:R1=|e1是復(fù)數(shù)的實(shí)數(shù)部分, |e2是復(fù)數(shù)的虛數(shù)部分基本操作：InitComplex(&Z,v

8、1,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的虛部值A(chǔ)dd(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sun返回兩個(gè)復(fù)數(shù)z1,z2的和值。ADT ComplexADT有兩個(gè)重要特征：數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)特征，其所能完成的功能以及它和外部用戶的接口（即外界

9、使用它的方法）數(shù)據(jù)封裝將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)抽象數(shù)據(jù)類型的描述方法抽象數(shù)據(jù)類型可用（D,S,P）三元組表示其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過(guò)固有數(shù)據(jù)類型（高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型）來(lái)實(shí)現(xiàn)1.3 算法和算法的衡量一、算法算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列。一個(gè)算法必須滿足以下五個(gè)重要特性：1.有窮性 2.確定性 3.可行性4.有輸入 5.有輸出1.有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；2.確定

10、性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(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é)果，這種確定關(guān)系即為算法的功能。二、算法設(shè)計(jì)的原則設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1.正確性2.可讀性3.健壯性4.高效率與低存

11、儲(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é)果；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í)行，而

12、應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(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.編寫程序的語(yǔ)言4.編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5.計(jì)算機(jī)執(zhí)行指令的速度假如，隨著問(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ù)雜

13、度：指算法中包含簡(jiǎn)單操作次數(shù),一般不必精確計(jì)算出算法的時(shí)間,只要大致計(jì)算出相應(yīng)數(shù)量級(jí),如(1)、(n)、(nlog2n)、(n2)、(n3)、(2n)等。for (i=1，i=n; +i) /兩個(gè)N*N矩陣相乘 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; 由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為: nnn=n3時(shí)間復(fù)雜度為T(n)=O(n3)如何估算算法的時(shí)間復(fù)雜度？頻度：是指該語(yǔ)句重復(fù)執(zhí)行的次數(shù)算法的運(yùn)行時(shí)間：一個(gè)算法中所有語(yǔ)句的頻度之和。例1、 +x ; s=0;將x自增看成是基本操作，則

14、語(yǔ)句頻度為，即時(shí)間復(fù)雜度為(1)如果將s=0也看成是基本操作，則語(yǔ)句頻度為，其時(shí)間復(fù)雜度仍為(1)，即常量階。例2、for (i=1; i=n; +i) +x; s+=x; 語(yǔ)句頻度為：2n其時(shí)間復(fù)雜度為： T(n)= O(n) 即時(shí)間復(fù)雜度為線性階。例3、i=1; 語(yǔ)句1：頻度=1 while (i=n) i=i*10; 語(yǔ)句2：頻度= lg（n） 其時(shí)間復(fù)雜度為： T(n)= 1+ logn= O(lg（n）) 例、for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 語(yǔ)句頻度為：2n2其時(shí)間復(fù)雜度為：O(n2) 即時(shí)間復(fù)雜度為平方階。例、for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x;ai，j=x;語(yǔ)句頻度為： 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ù)雜度為平方階.以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)指數(shù)時(shí)間的關(guān)系為： O(2n)O(n!)O(nn) 當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)