資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系課件

1、資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系1 資料結(jié)構(gòu)（用C語(yǔ)言） 資訊工程學(xué)系 資訊工程學(xué)系 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系2 課程目標(biāo) 資料結(jié)構(gòu)是資訊科學(xué)學(xué)門(mén)中的核心課程，而本 課程主要在介紹各種型態(tài)資料結(jié)構(gòu)在C程式語(yǔ)言 中的呈現(xiàn)，以及和演算法的關(guān)係。 修習(xí)本課程的同學(xué)，除了學(xué)到常用的資料表現(xiàn) 方式之外，如何在設(shè)計(jì)C程式時(shí)選取合適的資料 結(jié)構(gòu)、配合適當(dāng)?shù)难菟惴?、和評(píng)估所採(cǎi)用的資 料結(jié)構(gòu)的優(yōu)缺點(diǎn)等都是本課程的重點(diǎn)。 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系3 課程大綱與進(jìn)度 程式設(shè)計(jì)基本概念與C程式語(yǔ)言基本認(rèn)識(shí) C程式語(yǔ)言組成 資料型態(tài)、運(yùn)算子、流程控制指令 函數(shù)、指標(biāo)、陣列與結(jié)構(gòu)) 輸入/輸出與檔案處理) 演算法的規(guī)

2、格演算法的規(guī)格, ,資料抽象化與程式的複雜度分析資料抽象化與程式的複雜度分析 Array(陣列)與Structure(結(jié)構(gòu)) Stack(堆疊)與Queue(佇列) Linked List(串列) Tree(樹(shù)狀結(jié)構(gòu)) Graph(圖狀結(jié)構(gòu)) Sorting(排序) Hashing(雜湊結(jié)構(gòu)) Heap(堆積結(jié)構(gòu)) Searching(搜尋結(jié)構(gòu)) 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系4 參考書(shū)籍 Ellis Horowitz, Sarataj Sahni, Susan Anderson-freed, Fundamentals of data structures in C, W.H. Freeman

3、and Company, New York,1993 Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language, 2nd Ed., Printice- Hall, New Jersey, 1990 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系5 成績(jī)?cè)u(píng)量 平時(shí)成績(jī)(程式作業(yè))30% 期中考30% 期末考40% 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系6 第一章 資料結(jié)構(gòu)基本觀念 資訊工程學(xué)系 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系7 系統(tǒng)的生命週期 System Life Cycle 需求(Requirement) 一整套規(guī)格(A set of specif

4、ications) 所需之輸入及輸出(Inputs and Outputs) 分析(Analysis) 將問(wèn)題分割成可以掌握的小問(wèn)題 有兩種分析方式 由下而上(bottom-up) 由草圖一磚一瓦的蓋房子 由上而下(top-down) 由程式最終要完成目標(biāo)開(kāi)始 設(shè)計(jì)組織及流程圖(將程式分割成可管控的單元) 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系8 系統(tǒng)的生命週期 System Life Cycle 設(shè)計(jì)(Design) 抽象化的資料型態(tài)(e.g.選課系統(tǒng)) 演算法的方法與步驟 修正及程式設(shè)計(jì)(Refinement and Coding) 完成抽象化資料的實(shí)際表示 撰寫(xiě)演算法的程式 驗(yàn)證(Verifica

5、tion) 用理論證明該方法的正確性(Correctness Proofs) 費(fèi)時(shí) 可參考別人已驗(yàn)證過(guò)的演算法 測(cè)試(Testing) e.g. if and switch 除錯(cuò)(Error Removal) 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系9 演算法的一般規(guī)格 Algorithm Specification 想要利用電腦解決特定問(wèn)題的方法及步驟, 輸入(Input) 需要提供0個(gè)以上數(shù)量的外在資料 輸出(Output) 至少要有一個(gè)以上的資料產(chǎn)出 確定性(Definiteness) 每一項(xiàng)方法及步驟是清楚而且不是模稜兩可的 有限性(Finiteness) 這個(gè)演算法一定要在有限的步驟內(nèi)完成 有效

6、性(Effectiveness) 每一項(xiàng)方法及步驟是足夠簡(jiǎn)單的可以完成(可以對(duì)應(yīng)到程式), 基本上用一支筆及一張紙就可以完整描述這個(gè)演算法, 也就是 每一步驟是可行的 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系10 幾個(gè)範(fàn)例 Samples 選擇排序法(Selection Sort) 在未排序的數(shù)列中每次找出最小(最大)的，將最小(最大)的數(shù)值依序列 出 二元搜尋法(Binary Search) 在已排序好的數(shù)列中找到是否存在某一筆數(shù)值 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系11 Selection Sort 一個(gè)簡(jiǎn)單的方法將一連串正整數(shù)做由大到小或者 由小到大的排列 從這些未排序的數(shù)列中一一找出最小，把它們依序置

7、入一個(gè)排序的數(shù)列中 這樣的敘述不是一個(gè)演算法的正確描述 e.g.沒(méi)有告訴這些數(shù)列一開(kāi)始如何儲(chǔ)存，還有結(jié)果到底要放到 哪裡 我們嘗試用中英文和C語(yǔ)言?shī)A雜著來(lái)描述這個(gè)演算 法： 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系12 氣泡排序法的演算法 Selection Sort Algorithm 假設(shè)資料都放在個(gè)整數(shù)陣列, 名字為list, 第i筆整數(shù)就放在 listi 中, 0=in for (i=0; i=1), 它們已經(jīng)排序過(guò), 而且放在一個(gè)整數(shù)型 態(tài)的陣列中 list0=list1=listn-1 要從上述陣列中搜尋到searchnumsearchnum這個(gè)整數(shù) 如果找到就傳回那個(gè)數(shù)值所在陣列中的索引位置

8、 如果找不到就傳回 -1 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系16 二元搜尋法 Binary Search 讓left, right兩個(gè)變數(shù)分別代表要搜尋數(shù)列範(fàn)圍中最左 邊及最右邊的索引位置 一開(kāi)始的位置當(dāng)然是 left = 0, right=n-1 讓另一個(gè)變數(shù) middle=(left+right)/2 假使我們比較 list middle和 searchnumsearchnum, 可以發(fā)現(xiàn)下列三 個(gè)現(xiàn)象 searchnumsearchnum list middle searchnum應(yīng)該落在middle和right區(qū)間, 所以將left=middle+1 如果沒(méi)有找到，就要再將middle= (

9、left+right)/2, 繼續(xù)前一 步驟，直到?jīng)]有數(shù)列可以檢查為止 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系17 程式(program 1.6)中用到的比較函數(shù) 巨集寫(xiě)法 #define COMPARE(x,y) (x)(y) ? 1: (x) = (y) ? 0:1) conditional expression expr1?expr2:expr3 函數(shù)呼叫寫(xiě)法 int compare (int x, int y) if(x y) return -1; else if (x=y) return 0; else return 1; 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系18 遞迴演算法 Recursive Al

10、gorithms 直接遞迴（Direct Recursion) 一函數(shù)直接呼叫自己 二元搜尋法(binary search) 排列(permutation) 間接遞迴（Indirect Recursion) A函數(shù)呼叫 B函數(shù)，而B(niǎo)函數(shù)會(huì)再呼叫A函數(shù) Binary search and Permutation Program 1.7及program1.8 在第四章及第五章會(huì)有更多的討論 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系19 程式作業(yè)2 Page 14 Exercise 11 Tower of Hanoi 漢諾塔或梵天塔 截止日期 兩個(gè)星期後 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系20 資料抽象化 Data

11、Abstraction C程式語(yǔ)言所提供的資料型態(tài)(data type) C本身已提供有char(字元), int(整數(shù)), float(浮點(diǎn)), double(雙精度浮點(diǎn)) 另外還有short(短整數(shù)), long(長(zhǎng)整數(shù))及在基本型態(tài)還可以再加 上關(guān)鍵字 unsigned(非負(fù))來(lái)做變化 將相同資料型態(tài)群組化, (array, 陣列) 將不一定相同的資料型態(tài)的資料集合起來(lái)(structure, 結(jié)構(gòu)) struct student char last_name; int student_id; char grade; C也提供了所謂指標(biāo)資料型態(tài)(pointer) int i, *p; 資料

12、結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系21 資料抽象化 Data Abstraction 資料型態(tài)(data type)的定義 一些物件的集合加上包含在物體上可以操作的一套操作方法 抽象資料型態(tài)(abstract data type, ADT) 也是資料型態(tài), 而它被整理成物件的規(guī)格定義和在這些個(gè)物件上操作方 法的所有規(guī)格定義 在這些物件上所有的操作方法的定義規(guī)格是和物件的呈現(xiàn)及實(shí)際操作方 法的製作是分開(kāi)的 C是沒(méi)有明顯的語(yǔ)法機(jī)制來(lái)製作ADT, 但是可以用一樣的觀念來(lái)達(dá)成 C+(Class), ADA(package) 所以ADT可以是與實(shí)際製作無(wú)關(guān)的 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系22 資料抽象化 Data

13、 Abstraction ADT資料型態(tài)所包含的功能 產(chǎn)生者/建構(gòu)者(Creator/Constructor) 產(chǎn)生想要的資料型態(tài)的實(shí)體 轉(zhuǎn)換者(Transformer) 通常是要將一個(gè)或多個(gè)其他的資料型態(tài)實(shí)體轉(zhuǎn)換成一個(gè)新的資料型態(tài)實(shí)體 觀察者/記錄者(Observer/Reporter) 是提供資料型態(tài)實(shí)體的資訊, 不會(huì)改變實(shí)體 一個(gè)ADT的定義就是至少包含上述的 一個(gè)功能 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系23 ADT實(shí)例, 自然數(shù)(Nature_Number) 自然數(shù)(Nature_Number)的結(jié)構(gòu)(structure)就是 物件: 一個(gè)從0開(kāi)始一直到電腦上的最大整數(shù)值(INT_MAX)結(jié)

14、束的一連串 整數(shù)數(shù)列 功能: x,y可以是所有在Nature_Number內(nèi)的元素, TRUE, FALSE是布林值 (boolean)而+, -, , and =是一般整數(shù)的運(yùn)算元 Nat_No Zero( ):= 0 Boolean Is_Zero(x):= if (x) return FALSE else return TRUE Nat_No Add(x,y):= if (x+y)=INT_MAX) return x+y Boolean Equal(x,y):= if (x=y) return TRUE else return FALSE Nat_No Successor(x):= if

15、 (x=INT_MAX) return x else return x+1 Nat_No Subtract(x,y):= if (xy) return 0 else return x-y 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系24 效能分析 評(píng)量程式好壞的一些標(biāo)準(zhǔn) 程式是否有達(dá)成所要完成的所有工作? 執(zhí)行結(jié)果正確與否? 程式是否有任何操作說(shuō)明的文件? 程式是否有效的利用函數(shù)來(lái)產(chǎn)生邏輯單元? 程式可讀性是否很高? 客觀分析(Complexity Theory) 程式是否有效的利用了主要及次要的儲(chǔ)存裝置程式是否有效的利用了主要及次要的儲(chǔ)存裝置? ? Space ComplexitySpace Complex

16、ity 程式執(zhí)行出結(jié)果的時(shí)間是否能接受程式執(zhí)行出結(jié)果的時(shí)間是否能接受? ? Time ComplexityTime Complexity 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系25 演算法效能的表示式 空間複雜度(Space Complexity) 一個(gè)程式要完成工作所需的電腦記憶體空間 固定空間需求(fixed space requirement), c 可變空間需求(variable space requirement), Sp(I) S(P)=c+ Sp(I) 時(shí)間複雜度(Time Complexity) 一個(gè)程式要完成工作所需的電腦時(shí)間 利用不管是在語(yǔ)法或語(yǔ)意上都有重要意義的程式執(zhí)行的每一步每一

17、步 (program step)(program step)來(lái)作為衡量標(biāo)準(zhǔn) 因?yàn)橥ǔ３淌街械拿恳恍信c每次程式執(zhí)行的實(shí)體變化無(wú)關(guān) 漸近線的表示法 當(dāng)兩個(gè)同樣要去完成一個(gè)工作的程式的實(shí)體特質(zhì)(e.g. input size, algorithm)變化時(shí), 可以預(yù)測(cè)在執(zhí)行時(shí)間 上的成長(zhǎng) 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系26 漸近線的表示法 f(n)就是在算program step時(shí)所獲致的函數(shù)值(e.g. f(n)=c1n+c2) O(n) f(n)=O(g(n) iff there exist positive constants c and n0 such that f(n)=n0 3n+2=O(n

18、), (3n+2)=2 (n) f(n)= (g(n) iff there exist positive constants c and n0 such that f(n)=cg(n) for all n, n =n0 3n+2= (n), (3n+2)=3n,n=1 (n) f(n)= (g(n) iff there exist positive constants c1, c2 and n0 such that c1g(n)= f(n) =n0 所以3n+2= (n), c1=3, c2=4 以selection sort為例 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系27 實(shí)際效能測(cè)量 Practic

19、al Performance Measurement 實(shí)際的複雜度分析(Practical Complexity) 在每個(gè)不同程式的輸入大小, 在不同區(qū)段的分析(e.g. Figure 1.7 , 1.8 and 1.9) 實(shí)際的執(zhí)行效能測(cè)量 Use C build-in functions clock() or time() to measure execution time Figure 1.10, Program 1.23 and Figure 1.11 Generating Test Data Worst case data e.g. sequential search (Progra

20、m 1.24 and 1.25) Large number of random test data 資料結(jié)構(gòu)用C語(yǔ)言資訊工程學(xué)系28 If and Only IfIf and Only If IffIff is a shorthand for the phrase if and only ifif and only if. This phrase is used in assertions. If I assert that A A if and only ifif and only if B B I mean that A is true if B is true, and furthermore, A is true only when B is true. If I say C if D then I know nothing about C when D is false, or about D when C is true. Similarly, were I to say C only if D then I am telling you nothing about C when D is true, or about D when C is false. Got it? You can say the same thing in a variety of