大學(xué)計(jì)算機(jī)重要課程 第一章 緒論

1、數(shù) 據(jù) 結(jié) 構(gòu)計(jì)算機(jī)工程學(xué)院鄭如濱網(wǎng)絡(luò)教研室 40715959292920QQ:398620541課程介紹課程名稱：數(shù)據(jù)結(jié)構(gòu)教材：數(shù)據(jù)結(jié)構(gòu)(C語言版)，嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社，2007年4月教學(xué)方式：授課（54）+上機(jī)實(shí)踐（18）32datastructuredatastructure課程考核方式考核方式：期末閉卷60%，平時(shí)成績40%。平時(shí)成績組成：考勤: 缺勤1/3直接取消考試資格。請假需課前提前通知教師（電話或假條的方式）。無故未到一次，扣10%。作業(yè) ：未交一次，扣10%。未認(rèn)真完成作業(yè)，敷衍交作業(yè)，一次10%抄襲作業(yè)，一次20%絕對(duì)禁止上課前，寫本課程的作業(yè)。實(shí)驗(yàn)：平時(shí)

2、+最終的實(shí)驗(yàn)報(bào)告，以平時(shí)課堂上檢查為主。完成情況良好，可加分。平時(shí)表現(xiàn)：課堂回答問題、作業(yè)完成情況等、好的問題均可加分。加分項(xiàng)可部分與扣分項(xiàng)相抵問題：課堂、課后、電子郵件參考書籍編程類： 高質(zhì)量C+編程 專解疑難雜癥算法類：算法導(dǎo)論(建議：僅供查詢)程序員實(shí)用算法 代碼較詳細(xì)，對(duì)很多數(shù)據(jù)結(jié)構(gòu)有詳細(xì)的實(shí)現(xiàn)代碼 Andrew Binstock、John Rex、陳宗斌 機(jī)械工業(yè)出版社 (建議：僅供查詢)參考書籍(深入)：算法與數(shù)據(jù)結(jié)構(gòu)，傅清祥 王曉東 編著，電子工業(yè)出版社，2001數(shù)據(jù)結(jié)構(gòu)與算法分析C語言描述M，（美）Mike Allen Weiss著，機(jī)械工業(yè)出版社，2004算法導(dǎo)論(第二版)，

3、Thomas H. Cormen等著，高等教育出版社，2002注意事項(xiàng)：今天回去的作業(yè)，自己復(fù)習(xí)C+語言基礎(chǔ)，尤其是指針部分最為重要，還有結(jié)構(gòu)體、引用部分。c語言教科書：錯(cuò)誤調(diào)試常見問題：=與=，引用參數(shù)&(c+中的)的使用。上交的作業(yè)應(yīng)包含幾部分內(nèi)容： 班級(jí)，學(xué)號(hào)，姓名作業(yè)不清楚的地方及時(shí)提問，善用baidu等搜索引擎本課件內(nèi)快速查找信息請按：CTRL+F建議每個(gè)同學(xué)申請網(wǎng)絡(luò)存儲(chǔ)空間，如：金山快盤。用于存儲(chǔ)自己的常用代碼與文檔學(xué)習(xí)委員職責(zé)1.收作業(yè)，按學(xué)號(hào)排序。統(tǒng)計(jì)未繳同學(xué)名單。2.匯總同學(xué)的問題與意見，提交給老師。課程結(jié)構(gòu)第一部分：(第1章)基本概念數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類

4、型第二部分：(第27章)各種基本類型的數(shù)據(jù)結(jié)構(gòu)線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹、二叉樹和圖第三部分：(第911章)討論查找和排序的各種實(shí)現(xiàn)方法及其綜合分析比較學(xué)完該課程后應(yīng)該掌握的能力1.手寫代碼或者偽代碼的能力。2.利用偽代碼或者自然語言描述自己想法的能力3.熟練掌握基本數(shù)據(jù)結(jié)構(gòu)的特性，并能利用基本數(shù)據(jù)結(jié)構(gòu)思考問題、解決問題。4.了解基本算法第1章 緒論學(xué)習(xí)要點(diǎn): 熟悉各名詞、術(shù)語的含義掌握基本概念，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法理解算法五個(gè)要素的確切含義掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法用計(jì)算機(jī)解決問題的步驟？從具體問題抽象出適

5、當(dāng)?shù)臄?shù)學(xué)模型設(shè)計(jì)求解此模型的算法編出程序?qū)崿F(xiàn)如何編寫出一個(gè)“好”的程序？必須：分析待處理對(duì)象的特征以及它們之間的關(guān)系 建立數(shù)學(xué)模型Niklaus Wirth：Data Structures + Algorithm = Programs處理問題的策略問題的數(shù)學(xué)模型1.1 什么是數(shù)據(jù)結(jié)構(gòu)非數(shù)值計(jì)算問題例1 書目自動(dòng)檢索系統(tǒng)書目文件按書名按作者名按分類號(hào)索引表線性表例2 人機(jī)對(duì)奕問題樹.例3 多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計(jì)

6、算機(jī)科學(xué)中所處的地位“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國外是從1968年才開始設(shè)立的，1968年美國唐歐克努特教授開創(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年代初：程序設(shè)計(jì)的實(shí)質(zhì)是選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法(DS+Algorithm)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)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)

7、計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。1.2 基本概念和術(shù)語數(shù)據(jù)(Data)：P4 所有能被輸入到計(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)的集合。例如：描述一本書的書目信息為一個(gè)數(shù)據(jù)元素，可以數(shù)據(jù)對(duì)象(Data Object)： 性質(zhì)相同的數(shù)據(jù)元素的集合。如，整數(shù)數(shù)據(jù)結(jié)構(gòu)(Data Structure)：P5 相互之間存在一種

8、或多種特定關(guān)系的數(shù)據(jù)元素的集合。登錄號(hào)書名作者名分類號(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)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。

9、邏輯結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(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)): (使用計(jì)算機(jī)處理.) 邏輯結(jié)構(gòu)在存儲(chǔ)器中的映像。數(shù)據(jù)元素的映像：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。如：數(shù)據(jù)元素之間關(guān)系的映像：P6 圖順序映像(順序存儲(chǔ)結(jié)構(gòu))：以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系。非順序映像(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))：借助指針元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。(321)10 = (501)8 = (10

10、1000001)2 A = (101)8 = (001000001)2數(shù)據(jù)類型(Data Type)：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。如，整型變量.原子類型：其值不可分解。如C語言中的整型等結(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ǔ)。分類：原子類型、固定聚合類型、可變聚合類型 p8形式定義：三元組ADT

11、=(D, S, P) 其中， D是數(shù)據(jù)對(duì)象；S是D上的關(guān)系的集合；P是對(duì)D的基本操作的集合。P9基本操作的定義格式為：基本操作名（參數(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é)。1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。本書相關(guān)說明見教材P10P11，簡介。課后作業(yè)0. 用自己的一句話說明白

12、數(shù)據(jù)結(jié)構(gòu)是什么？并列舉三個(gè)例子說明ppt上面的三種數(shù)據(jù)結(jié)構(gòu)分別幫我們解決了什么問題（不少于100字）1.查詢資料，分別說出：typedef的用法，并舉出一例子struct結(jié)構(gòu)體的用法，并舉出一例子&引用類型參數(shù)(c+)的用法，并舉出一例子指向結(jié)構(gòu)體的指針的用法，并舉出一例子指向函數(shù)的指針的用法，并舉出一例子背面還有課后作業(yè)2. 試仿照三元組的抽象數(shù)據(jù)類型(p12)寫出抽象數(shù)據(jù)類型復(fù)數(shù)(內(nèi)有加法與減法操作)的定義。并嘗試編寫測試程序，可上機(jī)進(jìn)行運(yùn)行。(加分)1.3 算法和算法分析1.3.1 算法定義： 對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。特性：有窮

13、性：一個(gè)算法必須在執(zhí)行有限步驟之后結(jié)束確定性：算法的每一步必須是確切定義的,不能產(chǎn)生二義性可行性：算法是能行的輸入：一個(gè)算法有零個(gè)或多個(gè)輸入輸出：一個(gè)算法有至少一個(gè)輸出注意：算法與程序的區(qū)別！算法的描述：自然語言流程圖程序設(shè)計(jì)語言，如C語言偽代碼介于自然語言和程序設(shè)計(jì)語言之間的方法，它采用某一程序設(shè)計(jì)語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計(jì)。例7 歐幾里德算法輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m和n的最大公約數(shù)。算法描述如下：自然語言： 輸入m和n； 求m除以n的余數(shù)r； 若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行第步； 將n的值放在m中，將r的值放在n中； 重新執(zhí)行第步。流程圖：N開始輸入m

14、和n r=m % nr=0m=n；n=r 輸出n結(jié)束Y程序設(shè)計(jì)語言：偽代碼： 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)正確性(correctness):滿足具體問題的需求可讀性(readability)：易讀、易理解健壯性(robustness):當(dāng)輸入數(shù)據(jù)非法時(shí)，

15、算法能夠做出反應(yīng)或進(jìn)行處理效率與低存儲(chǔ)量:執(zhí)行時(shí)間短、存儲(chǔ)空間小算法效率的度量算法效率的度量時(shí)間代價(jià)：算法在計(jì)算機(jī)上運(yùn)行時(shí)消耗的時(shí)間來度量。有兩種方法：事后統(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í)行一條基本語句或一個(gè)基本運(yùn)算需花一個(gè)單位時(shí)間基本語句指：賦值語句、輸入語句、輸出語句基本運(yùn)算指：算術(shù)運(yùn)算、一次比較（字符比較、數(shù)值比較）做法：從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。例

16、8-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ù)雜度：基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，記作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)|；(換句話就是說，這當(dāng)整型自變量n趨向于無窮大時(shí)，兩者的比值是一個(gè)不等于0的常數(shù)。)例8-2 NN矩陣相乘的算法的時(shí)間復(fù)雜度： 基本操作執(zhí)行的次數(shù)：nnn=n3 T(n)=O(n3)

17、語句的頻度：是指該語句重復(fù)執(zhí)行的次數(shù)。與該語句包含的基本操作執(zhí)行的次數(shù)相同。例8 分析語句+x; s=0;的頻度。解：將“+x”看成是基本操作，則語句頻度為，即時(shí)間復(fù)雜度為(1)；如果將“s=0”也看成是基本操作，則語句頻度為，其時(shí)間復(fù)雜度仍為(1)，即常量階。例9 分析語句for (i=1; i=n; +i) +x; s+=x;解：語句頻度為：2n，其時(shí)間復(fù)雜度為：T(n)=O(n)。即時(shí)間復(fù)雜度為線性階。例10 分析語句for (i=1; i=n; +i) for (j=1; j=n; +j) +x; s+=x;解：語句頻度為：2n2，其時(shí)間復(fù)雜度為：O(n2)。即時(shí)間復(fù)雜度為平方階。定理

18、：若A(n)=amnm +am-1nm-1 +a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(n m)。(證明略)例11 for (i=2; i=n; +i) for (j=2; j= (y + 1)(y + 1) y+;以下六種計(jì)算算法時(shí)間復(fù)雜度的多項(xiàng)式是最常用的。其關(guān)系為：O(1)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 分析：問題的輸入規(guī)模：n；基本操作：“交換序列中相鄰兩個(gè)整數(shù)”；實(shí)例：5 1 9 7 3 2

19、 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)* 0+1+2+.+n(n-1)/2=O(n2)總結(jié)：確定算法問題規(guī)模；找出基本操作；分析基本操作是否只依賴于問題規(guī)模？是，就直接建立基本操作執(zhí)行次數(shù)的求和表達(dá)式，并求解、用漸進(jìn)符號(hào)表示；否則，分別對(duì)該算法的最好、最壞和平均情況的時(shí)間復(fù)雜度進(jìn)行分析。算法的存儲(chǔ)

20、空間代價(jià)一個(gè)算法的空間效率是指在算法的執(zhí)行過程中，所占據(jù)的輔助空間數(shù)量?？臻g復(fù)雜度：算法所需存儲(chǔ)空間的度量，記作S(n)=O(f(n) 其中，n為問題的規(guī)模。本章小結(jié)本章主要介紹了如下一些基本概念：數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象物理結(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型算法的概念、特性以及描述算法的分析課后作業(yè)1.設(shè)n為正整數(shù)，試確定下列各程序段中前置以記號(hào)的語句的頻度。(1)i=1; k=0; while (i=n-1) k+=10*i; i+;(2)i=1; k=0; while (i=n-1) i+; k+=10*i;(3)k=0; for (i=1; i=n; i+) for (j=i; j=n; j+) k+;(4)i=1; j=0; while (i+jj) j+; else i+;2.假設(shè)n為2的乘冪