《數(shù)據(jù)結(jié)構(gòu)》課件第1章 緒論

1、數(shù) 據(jù) 結(jié) 構(gòu)課程介紹課程名稱：數(shù)據(jù)結(jié)構(gòu)教材：數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)，嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社，2007年4月教學(xué)方式：授課（54）+上機(jī)實(shí)踐（18）考核方式：期末閉卷70%，平時(shí)成績(jī)30%平時(shí)成績(jī)：考勤（10分，每次缺勤扣5分） 作業(yè)（10分） 實(shí)驗(yàn)（10分）以上三項(xiàng)任一項(xiàng)超過(guò)三次未到/交，取消考試資格！問(wèn)題：課堂、課后、電子郵件參考書(shū)籍：算法與數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述(第2版) ，張乃孝 編著，高等教育出版社 ，2006數(shù)據(jù)結(jié)構(gòu)與算法分析C語(yǔ)言描述(原書(shū)第2版)，(美)Mark Allen Weiss著，馮舜璽譯，機(jī)械工業(yè)出版社，2004算法導(dǎo)論(原書(shū)第2版)，Thomas H. Co

2、rmen等著，潘金貴等譯，機(jī)械工業(yè)出版社，2006課程結(jié)構(gòu)第一部分：(第1章)基本概念數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型、算法分析等第二部分：(第27章)各種基本類型的數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(shù)、二叉樹(shù)和圖第三部分：(第911章)討論查找和排序的各種實(shí)現(xiàn)方法及其綜合分析比較課程結(jié)束后：會(huì)分析數(shù)據(jù)結(jié)構(gòu)的特性，能夠在應(yīng)用中選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及算法。能夠編寫(xiě)結(jié)構(gòu)清楚、正確、易讀、符合軟件工程規(guī)范的應(yīng)用程序。第1章 緒論學(xué)習(xí)要點(diǎn): 熟悉各名詞、術(shù)語(yǔ)的含義掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法理解算法五個(gè)要素的

3、確切含義掌握計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法用計(jì)算機(jī)解決問(wèn)題的步驟？從具體問(wèn)題抽象出適當(dāng)?shù)臄?shù)學(xué)模型設(shè)計(jì)求解此模型的算法編出程序?qū)崿F(xiàn)如何編寫(xiě)出一個(gè)“好”的程序？必須：分析待處理對(duì)象的特征以及它們之間的關(guān)系 建立數(shù)學(xué)模型Niklaus Wirth：Data Structures + Algorithm = Programs處理問(wèn)題的策略問(wèn)題的數(shù)學(xué)模型1.1 什么是數(shù)據(jù)結(jié)構(gòu)非數(shù)值計(jì)算問(wèn)題例1 書(shū)目自動(dòng)檢索系統(tǒng)書(shū)目文件按書(shū)名按作者名按分類號(hào)索引表線性表例2 人機(jī)對(duì)奕問(wèn)題樹(shù).例3 多叉路口交通燈管理問(wèn)題CEDABABACADBABCBDDADBDCEAEBECED圖 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的

4、程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及其在計(jì)算機(jī)科學(xué)中所處的地位發(fā)展史：“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國(guó)外是從1968年才開(kāi)始設(shè)立的，1968年美國(guó)唐歐克努特教授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計(jì)算機(jī)程序設(shè)計(jì)技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。20世紀(jì)60年代末到70年代初：Niklaus Wirth公式20世紀(jì)70年代中期到80年代初：迅速發(fā)展地位：“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序

5、設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。1.2 基本概念和術(shù)語(yǔ)數(shù)據(jù)(Data)： 所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合。 是計(jì)算機(jī)操作的對(duì)象的總稱。 是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。數(shù)據(jù)元素(Data Element)： 是數(shù)據(jù)(集合)中的一個(gè)“個(gè)體”。 是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。 不可再分割 數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合。例如：描述一本書(shū)的書(shū)目信息為一個(gè)數(shù)據(jù)元素，可以數(shù)據(jù)對(duì)象(Data Object)： 性質(zhì)相同的數(shù)據(jù)元素的集合，數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)(Da

6、ta Structure)： 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。登錄號(hào)書(shū)名作者名分類號(hào)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)結(jié)構(gòu).例4 假設(shè)用三個(gè)4位的十進(jìn)制數(shù)表示一個(gè)含12位數(shù)的十進(jìn)制數(shù)。 不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”數(shù)據(jù)結(jié)構(gòu)的形式定義：二元組Data_Structure=(D,S)其中，D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。3214,6587,9345 a1(3214),a2(6587),a3(9345) 則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序”關(guān)系 a1,a2、a2,a33214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3 數(shù)據(jù)結(jié)構(gòu)

7、是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。邏輯結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖/網(wǎng)狀結(jié)構(gòu)例5 linear=(D,R) D=1,2,3,4,5,6,7,8,9,10 R=, ,例6 tree= (D,R) D=a, b, c, d, e, f, g, h, i, j, k, l R=, , ,物理結(jié)構(gòu)(又稱存儲(chǔ)結(jié)構(gòu))： 邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像。數(shù)據(jù)元素的映像：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。如：數(shù)據(jù)元素之間關(guān)系的映像：順序映像(順序存儲(chǔ)結(jié)構(gòu))：以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系。非順序映像(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))：借助指針元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。(321)10 = (501

8、)8 = (101000001)2 A = (101)8 = (001000001)2任何一個(gè)算法的設(shè)計(jì)取決于數(shù)據(jù)(邏輯)結(jié)構(gòu)，其實(shí)現(xiàn)取決于物理結(jié)構(gòu)。數(shù)據(jù)類型(Data Type)：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。原子類型：其值不可分解。如C語(yǔ)言中的整型等結(jié)構(gòu)類型：其值由若干成分按某種結(jié)構(gòu)組成，可以分解。如數(shù)組、記錄等不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。抽象數(shù)據(jù)類型(Abstract Data Type, ADT)：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲(chǔ)方式；定義它的人同樣不必要關(guān)心它如何存儲(chǔ)

9、。因此，抽象數(shù)據(jù)類型的定義只取決于它的一組邏輯特性，與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)！分類：原子類型、固定聚合類型、可變聚合類型形式定義：三元組ADT=(D, S, P) 其中， D是數(shù)據(jù)對(duì)象；S是D上的關(guān)系的集合；P是對(duì)D的基本操作的集合?；静僮鞯亩x格式為：基本操作名（參數(shù)表） 初始條件:初始條件描述 操作結(jié)果:操作結(jié)果描述兩種參數(shù)：賦值提供輸入值 引用提供輸入值、返回操作結(jié)果特點(diǎn)：數(shù)據(jù)抽象：強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝：將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。例7 抽象數(shù)據(jù)類型三元組的定義

10、：ADT Triplet 數(shù)據(jù)對(duì)象：D=e1,e2,e3|e1,e2,e3ElemSet(定義了關(guān)系運(yùn)算的某個(gè)集合) 數(shù)據(jù)關(guān)系：R1=, 基本操作： InitTriplet(&T, v1, v2, v3) 操作結(jié)果：構(gòu)造了三元組T, 元素e1,e2和e3分別被賦以參數(shù)v1,v2和v3的值。 DestroyTriplet(&T) 操作結(jié)果：三元組T被撤銷。 Get(T, i, &e) 初始條件：三元組T已經(jīng)存在，1i3。 操作結(jié)果：用e返回T的第i元的值。 Put(&T, i, e) 初始條件：三元組T已經(jīng)存在， 1i3。 操作結(jié)果：改變T的第i元的值為e。 IsAscending(T) 初始條

11、件：三元組已經(jīng)存在。 操作結(jié)果：如果T的3個(gè)元素按升序排列，則返回1，否則返回0。 .ADT Triplet數(shù)據(jù)類型名數(shù)據(jù)類型名1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可通過(guò)固有數(shù)據(jù)類型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來(lái)實(shí)現(xiàn)。本課程采用類C語(yǔ)言來(lái)描述，相關(guān)說(shuō)明見(jiàn)教材P10P11。例8 抽象數(shù)據(jù)類型Triplet的表示和實(shí)現(xiàn)。課后作業(yè)1. 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)別。2. 試仿照三元組的抽象數(shù)據(jù)類型寫(xiě)出抽象數(shù)據(jù)類型復(fù)數(shù)的定義。1.3 算法和算法分析1.3.1 算法定義： 對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)

12、操作。特性：有窮性：一個(gè)算法必須在執(zhí)行有限步驟之后結(jié)束確定性：算法的每一步必須是確切定義的,不能產(chǎn)生二義性可行性：算法是能行的輸入：一個(gè)算法有零個(gè)或多個(gè)輸入輸出：一個(gè)算法有至少一個(gè)輸出思考：算法與程序的區(qū)別！程序不一定滿足有窮性；程序中的指令必須是機(jī)器可以執(zhí)行的，算法中則不一定；算法代表了對(duì)問(wèn)題的解，而程序是算法在機(jī)器上的特定實(shí)現(xiàn)。算法的描述：自然語(yǔ)言流程圖程序設(shè)計(jì)語(yǔ)言，如C語(yǔ)言偽代碼介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)。例9 歐幾里德算法輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m和n的最大公約數(shù)。算法描述如下：自然語(yǔ)言： 輸入m和n； 求m除以

13、n的余數(shù)r； 若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第步； 將n的值放在m中，將r的值放在n中； 重新執(zhí)行第步。流程圖：N開(kāi)始輸入m和n r=m % nr=0m=n；n=r 輸出n結(jié)束Y程序設(shè)計(jì)語(yǔ)言：偽代碼： 1. r = m % n; 2. 循環(huán)直到r = 0; 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 輸出n;#includeint CommonFactor(int m, int n) int r = m % n; while (r!=0) m = n; n = r; r = m % n; return n;算法的評(píng)價(jià)衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性

14、(correctness):滿足具體問(wèn)題的需求可讀性(readability)：易讀、易理解健壯性(robustness):當(dāng)輸入數(shù)據(jù)非法時(shí)，算法能夠做出反應(yīng)或進(jìn)行處理效率與低存儲(chǔ)量:執(zhí)行時(shí)間短、存儲(chǔ)空間小算法效率的度量時(shí)間代價(jià)：用算法在計(jì)算機(jī)上運(yùn)行時(shí)消耗的時(shí)間來(lái)度量。有兩種方法：事后統(tǒng)計(jì)的方法：利用計(jì)算機(jī)內(nèi)部計(jì)時(shí)功能，進(jìn)行計(jì)時(shí)統(tǒng)計(jì)。缺陷必須先運(yùn)行程序；統(tǒng)計(jì)的時(shí)間依賴于計(jì)算機(jī)的軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣。事前分析估算的方法假設(shè)給定的是一臺(tái)通用計(jì)算機(jī)，滿足：執(zhí)行一條基本語(yǔ)句或一個(gè)基本運(yùn)算需花一個(gè)單位時(shí)間基本語(yǔ)句指：賦值語(yǔ)句、輸入語(yǔ)句、輸出語(yǔ)句基本運(yùn)算指：算術(shù)運(yùn)算、一次比較(字符比較、數(shù)值

15、比較)做法：從算法中選取一種對(duì)于所研究的問(wèn)題（或算法類型）來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。例10-1 兩個(gè)NN矩陣A和B相乘的算法。 for (i=0;in;i+) for (j=0;jn;j+) cij=0; for (k=0;kn;k+) cij=cij+aik*bkj; 基本操作時(shí)間復(fù)雜度T(n)：基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，記作T(n)=O(f(n)“O” 標(biāo)記的形式定義： 若f(n)是正整數(shù)n的一個(gè)函數(shù)，則xnO(f(n)表示存在一個(gè)正的常數(shù)M，使得當(dāng)nn0時(shí)都滿足|xn|M|f(n)|；(換句話就是說(shuō)，當(dāng)整型自變量n趨

16、向于無(wú)窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。)例10-2 NN矩陣相乘的算法的時(shí)間復(fù)雜度： 基本操作執(zhí)行的次數(shù)：nnn=n3 T(n)=O(n3)語(yǔ)句的頻度：是指該語(yǔ)句重復(fù)執(zhí)行的次數(shù)。與該語(yǔ)句包含的基本操作執(zhí)行的次數(shù)相同。漸近時(shí)間復(fù)雜度例11 分析語(yǔ)句+x; s=0;的頻度。解：將“+x”看成是基本操作，則語(yǔ)句頻度為，即時(shí)間復(fù)雜度為(1)；如果將“s=0”也看成是基本操作，則語(yǔ)句頻度為，其時(shí)間復(fù)雜度仍為(1)，即常量階。例12 分析語(yǔ)句for (i=1; i=n; +i) +x; s+=x;解：語(yǔ)句頻度為：2n，其時(shí)間復(fù)雜度為：T(n)=O(n)。即時(shí)間復(fù)雜度為線性階。例13 分析語(yǔ)句for

17、 (i=1; i=n; +i) for (j=1; j=n; +j) +x; s+=x;解：語(yǔ)句頻度為：2n2，其時(shí)間復(fù)雜度為：O(n2)。即時(shí)間復(fù)雜度為平方階?？偨Y(jié)：語(yǔ)句頻度和基本操作重復(fù)執(zhí)行的次數(shù)相等，且是關(guān)于n的一個(gè)精確的函數(shù)表達(dá)式；時(shí)間復(fù)雜度僅僅是取上述函數(shù)表達(dá)式的最高階，用O進(jìn)行標(biāo)記，且沒(méi)有任何系數(shù)！定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(n m)。(證明略)例14 for (i=2; i=n; +i) for (j=2; j= (y + 1)(y + 1) y+;以下六種計(jì)算算法時(shí)間復(fù)雜度的多項(xiàng)式是最常用的。其關(guān)系為：O(1)

18、O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時(shí)間的關(guān)系為：O(2n)O(n!)1 & change;-i) change=false; for(j=0;jaj+1) ajaj+1; change=TURE 分析：?jiǎn)栴}的輸入規(guī)模：n；基本操作：“交換序列中相鄰兩個(gè)整數(shù)”；實(shí)例：5 1 9 7 3 2 3 1 2 5 9 7“基本操作”數(shù)隨n變化的規(guī)律：a中序列自小至大有序時(shí)，“基本操作”數(shù)為0；a中序列自大至小有序時(shí)，“基本操作”數(shù)為 = =(1+2+3+.+(n-1)=n(n-1)/2算法的時(shí)間復(fù)雜度：最好情況下的時(shí)間復(fù)雜度：0最壞情況下的時(shí)間復(fù)雜度：W(n) =n(n-1)/2平均情況下的時(shí)間復(fù)雜度： AV(n) = 1/n