资料结构(用C语言)资讯工程学系.pptVIP

資料結構（用C語言） 資訊工程學系 王家輝 wangch@.tw 資訊工程學系 .tw/~wangch 課程目標 資料結構是資訊科學學門中的核心課程，而本課程主要在介紹各種型態資料結構在C程式語言中的呈現，以及和演算法的關係。 修習本課程的同學，除了學到常用的資料表現方式之外，如何在設計C程式時選取合適的資料結構、配合適當的演算法、和評估所採用的資料結構的優缺點等都是本課程的重點。 課程大綱與進度 程式設計基本概念與C程式語言基本認識 C程式語言組成 資料型態、運算子、流程控制指令 函數、指標、陣列與結構) 輸入/輸出與檔案處理) 演算法的規格,資料抽象化與程式的複雜度分析 Array(陣列)與Structure(結構) Stack(堆疊)與Queue(佇列) Linked List(串列) Tree(樹狀結構) Graph(圖狀結構) Sorting(排序) Hashing(雜湊結構) Heap(堆積結構) Searching(搜尋結構) 參考書籍 Ellis Horowitz, Sarataj Sahni, Susan Anderson-freed, Fundamentals of data structures in C, W.H. Freeman and Company, New York,1993 Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language, 2nd Ed., Printice-Hall, New Jersey, 1990 成績評量 平時成績(程式作業)30% 期中考30% 期末考40% 第一章資料結構基本觀念 資訊工程學系 系統的生命週期System Life Cycle 需求(Requirement) 一整套規格(A set of specifications) 所需之輸入及輸出(Inputs and Outputs) 分析(Analysis) 將問題分割成可以掌握的小問題 有兩種分析方式 由下而上(bottom-up) 由草圖一磚一瓦的蓋房子 由上而下(top-down) 由程式最終要完成目標開始 設計組織及流程圖(將程式分割成可管控的單元) 系統的生命週期System Life Cycle 設計(Design) 抽象化的資料型態(e.g.選課系統) 演算法的方法與步驟 修正及程式設計(Refinement and Coding) 完成抽象化資料的實際表示 撰寫演算法的程式 驗證(Verification) 用理論證明該方法的正確性(Correctness Proofs) 費時 可參考別人已驗證過的演算法 測試(Testing) e.g. ‘if’ and ‘switch’ 除錯(Error Removal) 演算法的一般規格Algorithm Specification 想要利用電腦解決特定問題的方法及步驟, 輸入(Input) 需要提供0個以上數量的外在資料 輸出(Output) 至少要有一個以上的資料產出 確定性(Definiteness) 每一項方法及步驟是清楚而且不是模稜兩可的 有限性(Finiteness) 這個演算法一定要在有限的步驟內完成 有效性(Effectiveness) 每一項方法及步驟是足夠簡單的可以完成(可以對應到程式), 基本上用一支筆及一張紙就可以完整描述這個演算法, 也就是每一步驟是可行的 幾個範例Samples 選擇排序法(Selection Sort) 在未排序的數列中每次找出最小(最大)的，將最小(最大)的數值依序列出 二元搜尋法(Binary Search) 在已排序好的數列中找到是否存在某一筆數值 Selection Sort 一個簡單的方法將一連串正整數做由大到小或者由小到大的排列 從這些未排序的數列中一一找出最小，把它們依序置入一個排序的數列中 這樣的敘述不是一個演算法的正確描述 e.g.沒有告訴這些數列一開始如何儲存，還有結果到底要放到哪裡 我們嘗試用中英文和C語言夾雜著來描述這個演算法： 氣泡排序法的演算法Selection Sort Algorithm 假設資料都放在個整數陣列, 名字為list, 第i筆整數就放在 list[i] 中, 0=in for (i=0; i n; i++) { Examine list[i] to list[n-1] and suppose that the smallest integer is at list[min]; Interchange list[i] and list[min]; } 完整程式 Program 1.3 Interchange list[i] and list[min];