资料结构用C语言资讯工程学系ppt课件.ppt

資料結構 用C語言 資訊工程學系資訊工程學系 1 課程目標 資料結構是資訊科學學門中的核心課程 而本課程主要在介紹各種型態資料結構在C程式語言中的呈現 以及和演算法的關係 修習本課程的同學 除了學到常用的資料表現方式之外 如何在設計C程式時選取合適的資料結構 配合適當的演算法 和評估所採用的資料結構的優缺點等都是本課程的重點 2 課程大綱與進度 程式設計基本概念與C程式語言基本認識C程式語言組成資料型態 運算子 流程控制指令函數 指標 陣列與結構 輸入 輸出與檔案處理 演算法的規格 資料抽象化與程式的複雜度分析Array 陣列 與Structure 結構 Stack 堆疊 與Queue 佇列 LinkedList 串列 Tree 樹狀結構 Graph 圖狀結構 Sorting 排序 Hashing 雜湊結構 Heap 堆積結構 Searching 搜尋結構 3 參考書籍 EllisHorowitz SaratajSahni SusanAnderson freed FundamentalsofdatastructuresinC W H FreemanandCompany NewYork 1993BrianW Kernighan DennisM Ritchie TheCProgrammingLanguage 2ndEd Printice Hall NewJersey 1990 4 成績評量 平時成績 程式作業 30 期中考30 期末考40 5 第一章資料結構基本觀念 資訊工程學系 6 系統的生命週期SystemLifeCycle 需求 Requirement 一整套規格 Asetofspecifications 所需之輸入及輸出 InputsandOutputs 分析 Analysis 將問題分割成可以掌握的小問題有兩種分析方式由下而上 bottom up 由草圖一磚一瓦的蓋房子由上而下 top down 由程式最終要完成目標開始設計組織及流程圖 將程式分割成可管控的單元 7 系統的生命週期SystemLifeCycle 設計 Design 抽象化的資料型態 e g 選課系統 演算法的方法與步驟修正及程式設計 RefinementandCoding 完成抽象化資料的實際表示撰寫演算法的程式驗證 Verification 用理論證明該方法的正確性 CorrectnessProofs 費時可參考別人已驗證過的演算法測試 Testing e g if and switch 除錯 ErrorRemoval 8 演算法的一般規格AlgorithmSpecification 想要利用電腦解決特定問題的方法及步驟 輸入 Input 需要提供0個以上數量的外在資料輸出 Output 至少要有一個以上的資料產出確定性 Definiteness 每一項方法及步驟是清楚而且不是模稜兩可的有限性 Finiteness 這個演算法一定要在有限的步驟內完成有效性 Effectiveness 每一項方法及步驟是足夠簡單的可以完成 可以對應到程式 基本上用一支筆及一張紙就可以完整描述這個演算法 也就是每一步驟是可行的 9 幾個範例Samples 選擇排序法 SelectionSort 在未排序的數列中每次找出最小 最大 的 將最小 最大 的數值依序列出二元搜尋法 BinarySearch 在已排序好的數列中找到是否存在某一筆數值 10 SelectionSort 一個簡單的方法將一連串正整數做由大到小或者由小到大的排列從這些未排序的數列中一一找出最小 把它們依序置入一個排序的數列中這樣的敘述不是一個演算法的正確描述e g 沒有告訴這些數列一開始如何儲存 還有結果到底要放到哪裡我們嘗試用中英文和C語言夾雜著來描述這個演算法 11 氣泡排序法的演算法SelectionSortAlgorithm 假設資料都放在個整數陣列 名字為list 第i筆整數就放在list i 中 0 i nfor i 0 i n i Examinelist i tolist n 1 andsupposethatthesmallestintegerisatlist min Interchangelist i andlist min 完整程式Program1 3 12 Interchangelist i andlist min 交換數列中兩筆資料 swap 13 程式作業一 嘗試將課本program1 3的selectionsort macro版 改成呼叫swap 函數用MSVisualC 課本是用ANSIC 或用C 兩個版本的程式都要寫 盡可能在每行程式附上註解並盡可能說明這兩個版本的差異截止日期 2 27 程式嚴禁抄襲 發現抄襲者 與被抄襲者一律以零分計 將執行檔 原始檔及文件壓縮成以學號為檔名的zip檔 並上傳至下列FTP站台 14 二元搜尋法BinarySearch 假設有n個整數 n 1 它們已經排序過 而且放在一個整數型態的陣列中list 0 list 1 list n 1 要從上述陣列中搜尋到searchnum這個整數如果找到就傳回那個數值所在陣列中的索引位置如果找不到就傳回 1 15 二元搜尋法BinarySearch 讓left right兩個變數分別代表要搜尋數列範圍中最左邊及最右邊的索引位置一開始的位置當然是left 0 right n 1讓另一個變數middle left right 2假使我們比較list middle 和searchnum 可以發現下列三個現象searchnumlist middle searchnum應該落在middle和right區間 所以將left middle 1如果沒有找到 就要再將middle left right 2 繼續前一步驟 直到沒有數列可以檢查為止 16 程式 program1 6 中用到的比較函數 巨集寫法 defineCOMPARE x y x y 1 x y 0 1 conditionalexpressionexpr1 expr2 expr3函數呼叫寫法intcompare intx inty if x y return 1 elseif x y return0 elsereturn1 17 遞迴演算法RecursiveAlgorithms 直接遞迴 DirectRecursion 一函數直接呼叫自己二元搜尋法 binarysearch 排列 permutation 間接遞迴 IndirectRecursion A函數呼叫B函數 而B函數會再呼叫A函數BinarysearchandPermutationProgram1 7及program1 8在第四章及第五章會有更多的討論 18 程式作業2 Page14Exercise11TowerofHanoi漢諾塔或梵天塔截止日期兩個星期後 19 資料抽象化DataAbstraction C程式語言所提供的資料型態 datatype C本身已提供有char 字元 int 整數 float 浮點 double 雙精度浮點 另外還有short 短整數 long 長整數 及在基本型態還可以再加上關鍵字unsigned 非負 來做變化將相同資料型態群組化 array 陣列 將不一定相同的資料型態的資料集合起來 structure 結構 structstudent charlast name intstudent id chargrade C也提供了所謂指標資料型態 pointer inti p 20 資料抽象化DataAbstraction 資料型態 datatype 的定義一些物件的集合加上包含在物體上可以操作的一套操作方法抽象資料型態 abstractdatatype ADT 也是資料型態 而它被整理成物件的規格定義和在這些個物件上操作方法的所有規格定義在這些物件上所有的操作方法的定義規格是和物件的呈現及實際操作方法的製作是分開的C是沒有明顯的語法機制來製作ADT 但是可以用一樣的觀念來達成C Class ADA package 所以ADT可以是與實際製作無關的 21 資料抽象化DataAbstraction ADT資料型態所包含的功能產生者 建構者 Creator Constructor 產生想要的資料型態的實體轉換者 Transformer 通常是要將一個或多個其他的資料型態實體轉換成一個新的資料型態實體觀察者 記錄者 Observer Reporter 是提供資料型態實體的資訊 不會改變實體一個ADT的定義就是至少包含上述的一個功能 22 ADT實例 自然數 Nature Number 自然數 Nature Number 的結構 structure 就是物件 一個從0開始一直到電腦上的最大整數值 INT MAX 結束的一連串整數數列功能 x y可以是所有在Nature Number內的元素 TRUE FALSE是布林值 boolean 而 and 是一般整數的運算元Nat NoZero 0BooleanIs Zero x if x returnFALSEelsereturnTRUENat NoAdd x y if x y INT MAX returnx yBooleanEqual x y if x y returnTRUEelsereturnFALSENat NoSuccessor x if x INT MAX returnxelsereturnx 1Nat NoSubtract x y if x y return0elsereturnx y 23 效能分析 評量程式好壞的一些標準程式是否有達成所要完成的所有工作 執行結果正確與否 程式是否有任何操作說明的文件 程式是否有效的利用函數來產生邏輯單元 程式可讀性是否很高 客觀分析 ComplexityTheory 程式是否有效的利用了主要及次要的儲存裝置 SpaceComplexity程式執行出結果的時間是否能接受 TimeComplexity 24 演算法效能的表示式 空間複雜度 SpaceComplexity 一個程式要完成工作所需的電腦記憶體空間固定空間需求 fixedspacerequirement c可變空間需求 variablespacerequirement Sp I S P c Sp I 時間複雜度 TimeComplexity 一個程式要完成工作所需的電腦時間利用不管是在語法或語意上都有重要意義的程式執行的每一步 programstep 來作為衡量標準因為通常程式中的每一行與每次程式執行的實體變化無關漸近線的表示法當兩個同樣要去完成一個工作的程式的實體特質 e g inputsize algorithm 變化時 可以預測在執行時間上的成長 25 漸近線的表示法 f n 就是在算programstep時所獲致的函數值 e g f n c1n c2 O n f n O g n iffthereexistpositiveconstantscandn0suchthatf n n03n 2 O n 3n 2 2 n f n g n iffthereexistpositiveconstantscandn0suchthatf n cg n foralln n n03n 2 n 3n 2 3n n 1 n f n g n iffthereexistpositiveconstantsc1 c2andn0suchthatc1g n n0所以3n 2 n c1 3 c2 4以selectionsort為例 26 實際效能測量PracticalPerformanceMeasurement 實際的複雜度分析 PracticalComplexity 在每個不同程式的輸入大小 在不同區段的分析 e g Figure1 7 1 8and1 9 實際的執行效能測量UseCbuild infunctionsclock ortime tomeasureexecutiontimeFigure1 10 Program1 23andFigure1 11GeneratingTestDataWorstcasedatae g sequentialsearch Program1 24and1 25 Largenumberofrandomtestdata 27 IfandOnlyIf Iff isashorthandforthephrase ifandonlyif Thisphraseisusedinassertions IfIassertthat AifandonlyifB ImeanthatAistrueifBistrue andfurthermore AistrueonlywhenBistrue IfIsay CifD thenIknownothingaboutCwhenDisfalse oraboutDwhenCistrue Similarly wereItosay ConlyifD thenIamtellingyounothinga