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

资产评估资产评估课程讲义课程讲义資料結構（用資料結構（用C語言）語言）資訊工程學系王家輝wangchmcu.edu.tw資訊工程學系http:/www.csie.mcu.edu.tw/wangch资产评估资产评估课程讲义课程讲义課程目標課程目標l資料結構是資訊科學學門中的核心課程，而本課程主要在介紹各種型態資料結構在C程式語言中的呈現，以及和演算法的關係。l修習本課程的同學，除了學到常用的資料表現方式之外，如何在設計C程式時選取合適的資料結構、配合適當的演算法、和評估所採用的資料結構的優缺點等都是本課程的重點。资产评估资产评估课程讲义课程讲义課程大綱與進度課程大綱與進度l程式設計基本概念與C程式語言基本認識lC程式語言組成資料型態、運算子、流程控制指令 函數、指標、陣列與結構)輸入/輸出與檔案處理)l演算法的規格演算法的規格,資料抽象化與程式的複雜度分析資料抽象化與程式的複雜度分析lArray(陣列)與Structure(結構)lStack(堆疊)與Queue(佇列)lLinked List(串列)lTree(樹狀結構)lGraph(圖狀結構)lSorting(排序)lHashing(雜湊結構)lHeap(堆積結構)lSearching(搜尋結構)资产评估资产评估课程讲义课程讲义參考書籍參考書籍lEllis Horowitz,Sarataj Sahni,Susan Anderson-freed,Fundamentals of data structures in C,W.H.Freeman and Company,New York,1993 lBrian W.Kernighan,Dennis M.Ritchie,The C Programming Language,2nd Ed.,Printice-Hall,New Jersey,1990 资产评估资产评估课程讲义课程讲义成績評量成績評量l平時成績(程式作業)30%l期中考30%l期末考40%资产评估资产评估课程讲义课程讲义第一章第一章資料結構基本觀念資料結構基本觀念資訊工程學系资产评估资产评估课程讲义课程讲义系統的生命週期系統的生命週期System Life Cyclel需求(Requirement)一整套規格(A set of specifications)所需之輸入及輸出(Inputs and Outputs)l分析(Analysis)將問題分割成可以掌握的小問題有兩種分析方式l由下而上(bottom-up)由草圖一磚一瓦的蓋房子l由上而下(top-down)由程式最終要完成目標開始設計組織及流程圖(將程式分割成可管控的單元)资产评估资产评估课程讲义课程讲义系統的生命週期系統的生命週期System Life Cyclel設計(Design)抽象化的資料型態(e.g.選課系統)演算法的方法與步驟l修正及程式設計(Refinement and Coding)完成抽象化資料的實際表示撰寫演算法的程式l驗證(Verification)用理論證明該方法的正確性(Correctness Proofs)l費時l可參考別人已驗證過的演算法測試(Testing)le.g.if and switch除錯(Error Removal)资产评估资产评估课程讲义课程讲义演算法的一般規格演算法的一般規格Algorithm Specificationl想要利用電腦解決特定問題的方法及步驟,輸入(Input)l需要提供0個以上數量的外在資料輸出(Output)l至少要有一個以上的資料產出確定性(Definiteness)l每一項方法及步驟是清楚而且不是模稜兩可的有限性(Finiteness)l這個演算法一定要在有限的步驟內完成有效性(Effectiveness)l每一項方法及步驟是足夠簡單的可以完成(可以對應到程式),基本上用一支筆及一張紙就可以完整描述這個演算法,也就是每一步驟是可行的资产评估资产评估课程讲义课程讲义幾個範例幾個範例Samplesl選擇排序法(Selection Sort)在未排序的數列中每次找出最小(最大)的，將最小(最大)的數值依序列出l二元搜尋法(Binary Search)在已排序好的數列中找到是否存在某一筆數值资产评估资产评估课程讲义课程讲义Selection Sortl一個簡單的方法將一連串正整數做由大到小或者由小到大的排列從這些未排序的數列中一一找出最小，把它們依序置入一個排序的數列中l這樣的敘述不是一個演算法的正確描述e.g.沒有告訴這些數列一開始如何儲存，還有結果到底要放到哪裡l我們嘗試用中英文和C語言夾雜著來描述這個演算法：资产评估资产评估课程讲义课程讲义氣泡排序法的演算法氣泡排序法的演算法Selection Sort Algorithml假設資料都放在個整數陣列,名字為list,第i筆整數就放在 listi 中,0=infor(i=0;i=1),它們已經排序過,而且放在一個整數型態的陣列中list0=list1=listn-1l要從上述陣列中搜尋到searchnum這個整數如果找到就傳回那個數值所在陣列中的索引位置如果找不到就傳回-1资产评估资产评估课程讲义课程讲义二元搜尋法二元搜尋法Binary Searchl讓left,right兩個變數分別代表要搜尋數列範圍中最左邊及最右邊的索引位置一開始的位置當然是 left=0,right=n-1讓另一個變數 middle=(left+right)/2假使我們比較 list middle和 searchnum,可以發現下列三個現象lsearchnum list middlesearchnum應該落在middle和right區間,所以將left=middle+1如果沒有找到，就要再將middle=(left+right)/2,繼續前一步驟，直到沒有數列可以檢查為止资产评估资产评估课程讲义课程讲义程式程式(program 1.6)中用到的比較函數中用到的比較函數l巨集寫法#define COMPARE(x,y)(x)(y)?1:(x)=(y)?0:1)conditional expressionlexpr1?expr2:expr3l函數呼叫寫法int compare(int x,int y)if(x y)return -1;else if(x=y)return 0;else return 1;资产评估资产评估课程讲义课程讲义遞迴演算法遞迴演算法Recursive Algorithmsl直接遞迴（Direct Recursion)一函數直接呼叫自己l二元搜尋法(binary search)l排列(permutation)l 間接遞迴（Indirect Recursion)A函數呼叫 B函數，而B函數會再呼叫A函數lBinary search and PermutationProgram 1.7及program1.8l在第四章及第五章會有更多的討論资产评估资产评估课程讲义课程讲义程式作業程式作業2lPage 14 Exercise 11Tower of Hanoil漢諾塔或梵天塔截止日期l兩個星期後资产评估资产评估课程讲义课程讲义資料抽象化資料抽象化Data AbstractionlC程式語言所提供的資料型態(data type)C本身已提供有char(字元),int(整數),float(浮點),double(雙精度浮點)l另外還有short(短整數),long(長整數)及在基本型態還可以再加上關鍵字 unsigned(非負)來做變化l將相同資料型態群組化,(array,陣列)l將不一定相同的資料型態的資料集合起來(structure,結構)struct student char last_name;int student_id;char grade;C也提供了所謂指標資料型態(pointer)int i,*p;资产评估资产评估课程讲义课程讲义資料抽象化資料抽象化Data Abstractionl資料型態(data type)的定義一些物件的集合加上包含在物體上可以操作的一套操作方法l抽象資料型態(abstract data type,ADT)也是資料型態,而它被整理成物件的規格定義和在這些個物件上操作方法的所有規格定義在這些物件上所有的操作方法的定義規格是和物件的呈現及實際操作方法的製作是分開的C是沒有明顯的語法機制來製作ADT,但是可以用一樣的觀念來達成lC+(Class),ADA(package)所以ADT可以是與實際製作無關的资产评估资产评估课程讲义课程讲义資料抽象化資料抽象化Data AbstractionlADT資料型態所包含的功能產生者/建構者(Creator/Constructor)l產生想要的資料型態的實體轉換者(Transformer)l通常是要將一個或多個其他的資料型態實體轉換成一個新的資料型態實體觀察者/記錄者(Observer/Reporter)l是提供資料型態實體的資訊,不會改變實體l一個ADT的定義就是至少包含上述的 一個功能资产评估资产评估课程讲义课程讲义ADT實例實例,自然數自然數(Nature_Number)l自然數(Nature_Number)的結構(structure)就是物件:一個從0開始一直到電腦上的最大整數值(INT_MAX)結束的一連串整數數列功能:x,y可以是所有在Nature_Number內的元素,TRUE,FALSE是布林值(boolean)而+,-,and=是一般整數的運算元lNat_No Zero():=0lBoolean Is_Zero(x):=if(x)return FALSE else return TRUElNat_No Add(x,y):=if(x+y)=INT_MAX)return x+ylBoolean Equal(x,y):=if(x=y)return TRUE else return FALSElNat_No Successor(x):=if(x=INT_MAX)return x elsereturn x+1lNat_No Subtract(x,y):=if(xy)return 0 else return x-y资产评估资产评估课程讲义课程讲义效能分析效能分析l評量程式好壞的一些標準程式是否有達成所要完成的所有工作?執行結果正確與否?程式是否有任何操作說明的文件?程式是否有效的利用函數來產生邏輯單元?程式可讀性是否很高?l客觀分析(Complexity Theory)程式是否有效的利用了主要及次要的儲存裝置程式是否有效的利用了主要及次要的儲存裝置?lSpace Complexity程式執行出結果的時間是否能接受程式執行出結果的時間是否能接受?lTime Complexity资产评估资产评估课程讲义课程讲义演算法效能的表示式演算法效能的表示式l空間複雜度(Space Complexity)一個程式要完成工作所需的電腦記憶體空間l固定空間需求(fixed space requirement),cl可變空間需求(variable space requirement),Sp(I)lS(P)=c+Sp(I)l時間複雜度(Time Complexity)一個程式要完成工作所需的電腦時間l利用不管是在語法或語意上都有重要意義的程式執行的每一步每一步(program step)來作為衡量標準因為通常程式中的每一行與每次程式執行的實體變化無關l漸近線的表示法當兩個同樣要去完成一個工作的程式的實體特質(e.g.input size,algorithm)變化時,可以預測在執行時間上的成長资产评估资产评估课程讲义课程讲义漸近線的表示法漸近線的表示法lf(n)就是在算program step時所獲致的函數值(e.g.f(n)=c1n+c2)O(n)lf(n)=O(g(n)iff there exist positive constants c and n0 such that f(n)=n0l3n+2=O(n),(3n+2)=2(n)lf(n)=(g(n)iff there exist positive constants c and n0 such that f(n)=cg(n)for all n,n=n0l3n+2=(n),(3n+2)=3n,n=1(n)lf(n)=(g(n)iff there exist positive constants c1,c2 and n0 such that c1g(n)=f(n)=n0l所以3n+2=(n),c1=3,c2=4l以selection sort為例资产评估资产评估课程讲义课程讲义實際效能測量實際效能測量Practical Performance Measurementl實際的複雜度分析(Practical Complexity)在每個不同程式的輸入大小,在不同區段的分析(e.g.Figure 1.7,1.8 and 1.9)l 實際的執行效能測量Use C build-in functions clock()or time()to measure execution timelFigure 1.10,Program 1.23 and Figure 1.11Generating Test DatalWorst case datae.g.sequential search(Program 1.24 and 1.25)lLarge number of random test data