大學計算機重要課程 第一章 緒論

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

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

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

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

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

6、算機科學中所處的地位“數(shù)據(jù)結構”作為一門獨立的課程在國外是從1968年才開始設立的，1968年美國唐歐克努特教授開創(chuàng)了數(shù)據(jù)結構的最初體系，他所著的計算機程序設計技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結構和存儲結構及其操作的著作。20世紀60年代末到70年代初：程序設計的實質是選擇一種好的結構，加上設計一種好的算法(DS+Algorithm)20世紀70年代中期到80年代初：迅速發(fā)展地位：“數(shù)據(jù)結構”在計算機科學中是一門綜合性的專業(yè)基礎課。數(shù)據(jù)結構是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。數(shù)據(jù)結構這一門課的內容不僅是一般程序設計（特別是非數(shù)值性程序設計）的基礎，而且是設

7、計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要基礎。1.2 基本概念和術語數(shù)據(jù)(Data)：P4 所有能被輸入到計算機中，且能被計算機處理的符號的集合。 是計算機操作的對象的總稱。 是計算機處理的信息的某種特定的符號表示形式。數(shù)據(jù)元素(Data Element)： 是數(shù)據(jù)（集合）中的一個“個體”。 是數(shù)據(jù)結構中討論的基本單位。數(shù)據(jù)項：是數(shù)據(jù)結構中討論的最小單位。 不可再分割 數(shù)據(jù)元素可以是數(shù)據(jù)項的集合。例如：描述一本書的書目信息為一個數(shù)據(jù)元素，可以數(shù)據(jù)對象(Data Object)： 性質相同的數(shù)據(jù)元素的集合。如，整數(shù)數(shù)據(jù)結構(Data Structure)：P5 相互之間存在一種

8、或多種特定關系的數(shù)據(jù)元素的集合。登錄號書名作者名分類號數(shù)據(jù)元素數(shù)據(jù)項結構.例4 假設用三個4位的十進制數(shù)表示一個含12位數(shù)的十進制數(shù)。 不同的“關系”構成不同的“結構”數(shù)據(jù)結構的形式定義：二元組Data_Structure=(D,S)其中，D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。3214,6587,9345 a1(3214),a2(6587),a3(9345) 則在數(shù)據(jù)元素 a1、a2 和 a3 之間存在著“次序”關系 a1,a2、a2,a33214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3 數(shù)據(jù)結構是相互之間存在著某種邏輯關系的數(shù)據(jù)元素的集合。

9、邏輯結構集合結構線性結構樹形結構圖/網狀結構例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=, , ,物理結構(又稱存儲結構): (使用計算機處理.) 邏輯結構在存儲器中的映像。數(shù)據(jù)元素的映像：用二進制位(bit)的位串表示數(shù)據(jù)元素。如：數(shù)據(jù)元素之間關系的映像：P6 圖順序映像(順序存儲結構)：以相對的存儲位置表示后繼關系。非順序映像(鏈式存儲結構)：借助指針元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。(321)10 = (501)8 = (10

10、1000001)2 A = (101)8 = (001000001)2數(shù)據(jù)類型(Data Type)：一個值的集合和定義在這個值集上的一組操作的總稱。如，整型變量.原子類型：其值不可分解。如C語言中的整型等結構類型：其值由若干成分按某種結構組成，可以分解。如數(shù)組等不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。抽象數(shù)據(jù)類型(Abstract Data Type, ADT)：一個數(shù)學模型以及定義在該模型上的一組操作。關鍵：使用它的人可以只關心它的邏輯特征，不需要了解它的存儲方式；定義它的人同樣不必要關心它如何存儲。分類：原子類型、固定聚合類型、可變聚合類型 p8形式定義：三元組ADT

11、=(D, S, P) 其中， D是數(shù)據(jù)對象；S是D上的關系的集合；P是對D的基本操作的集合。P9基本操作的定義格式為：基本操作名（參數(shù)表） 初始條件:初始條件描述 操作結果:操作結果描述兩種參數(shù)：賦值提供輸入值 引用提供輸入值、返回操作結果特點：數(shù)據(jù)抽象：強調的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝：將實體的外部特性和其內部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏其內部實現(xiàn)細節(jié)。1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級編程語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)。本書相關說明見教材P10P11，簡介。課后作業(yè)0. 用自己的一句話說明白

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

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

14、和n r=m % nr=0m=n；n=r 輸出n結束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;算法的評價衡量算法優(yōu)劣的標準正確性(correctness):滿足具體問題的需求可讀性(readability)：易讀、易理解健壯性(robustness):當輸入數(shù)據(jù)非法時，

15、算法能夠做出反應或進行處理效率與低存儲量:執(zhí)行時間短、存儲空間小算法效率的度量算法效率的度量時間代價：算法在計算機上運行時消耗的時間來度量。有兩種方法：事后統(tǒng)計的方法：利用計算機內部計時功能，進行計時統(tǒng)計。缺陷必須先運行程序；統(tǒng)計的時間依賴于計算機的軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣。事前分析估算的方法假設給定的是一臺通用計算機，滿足：執(zhí)行一條基本語句或一個基本運算需花一個單位時間基本語句指：賦值語句、輸入語句、輸出語句基本運算指：算術運算、一次比較（字符比較、數(shù)值比較）做法：從算法中選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作重復執(zhí)行的次數(shù)作為算法的時間量度。例

16、8-1 兩個NN矩陣A和B相乘的算法。 for (i=0;in;i+) for (j=0;jn;j+) cij=0; for (k=0;kn;k+) cij=cij+aik*bkj; 基本操作時間復雜度：基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，記作T(n)=O(f(n)“O” 標記的形式定義： 若f(n)是正整數(shù)n的一個函數(shù)，則xnO(f(n)表示存在一個正的常數(shù)M，使得當nn0時都滿足|xn|M|f(n)|；(換句話就是說，這當整型自變量n趨向于無窮大時，兩者的比值是一個不等于0的常數(shù)。)例8-2 NN矩陣相乘的算法的時間復雜度： 基本操作執(zhí)行的次數(shù)：nnn=n3 T(n)=O(n3)

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

18、：若A(n)=amnm +am-1nm-1 +a1n+a0是一個m次多項式，則A(n)=O(n m)。(證明略)例11 for (i=2; i=n; +i) for (j=2; j= (y + 1)(y + 1) y+;以下六種計算算法時間復雜度的多項式是最常用的。其關系為：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時間的關系為：O(2n)O(n!)1 & change;-i) change=false; for(j=0;jaj+1) ajaj+1; change=TURE 分析：問題的輸入規(guī)模：n；基本操作：“交換序列中相鄰兩個整數(shù)”；實例：5 1 9 7 3 2

19、 3 1 2 5 9 7“基本操作”數(shù)隨n變化的規(guī)律：a中序列自小至大有序時，“基本操作”數(shù)為0；a中序列自大至小有序時，“基本操作”數(shù)為 = =(1+2+3+.+(n-1)=n(n-1)/2算法的時間復雜度：最好情況下的時間復雜度：0最壞情況下的時間復雜度：W(n) =n(n-1)/2平均情況下的時間復雜度： AV(n) = (1/n)* 0+1+2+.+n(n-1)/2=O(n2)總結：確定算法問題規(guī)模；找出基本操作；分析基本操作是否只依賴于問題規(guī)模？是，就直接建立基本操作執(zhí)行次數(shù)的求和表達式，并求解、用漸進符號表示；否則，分別對該算法的最好、最壞和平均情況的時間復雜度進行分析。算法的存儲

20、空間代價一個算法的空間效率是指在算法的執(zhí)行過程中，所占據(jù)的輔助空間數(shù)量。空間復雜度：算法所需存儲空間的度量，記作S(n)=O(f(n) 其中，n為問題的規(guī)模。本章小結本章主要介紹了如下一些基本概念：數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)對象物理結構數(shù)據(jù)類型抽象數(shù)據(jù)類型算法的概念、特性以及描述算法的分析課后作業(yè)1.設n為正整數(shù)，試確定下列各程序段中前置以記號的語句的頻度。(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.假設n為2的乘冪