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

,*,按一下以編輯母片標題樣式,按一下以編輯母片,第二層,第三層,第四層,第五層,資料結構（用C語言）,資訊工程學系,王家輝,wangchmcu.edu.tw,資訊工程學系,www.csie.mcu.edu.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=,i,n,for,(,i,=0;,i,=1),它們已經排序過,而且放在一個整數型態的陣列中,list,0=,list,1=,list,n-1,要從上述陣列中搜尋到,searchnum,這個整數,如果找到就傳回那個數值所在陣列中的索引位置,如果找不到就傳回-1,二元搜尋法Binary Search,讓,left,right,兩個變數分別代表要搜尋數列範圍中最左邊及最右邊的索引位置,一開始的位置當然是,left,=0,right,=,n,-1,讓另一個變數,middle,=(,left,+,right,)/2,假使我們比較,list,middle,和,searchnum,可以發現下列三個現象,searchnum,list,middle,searchnum,應該落在,middle,和,right,區間,所以將,left,=,middle+1,如果沒有找到，就要再將,middle,=(,left,+,right,)/2,繼續前一步驟，直到沒有數列可以檢查為止,程式(program 1.6)中用到的比較函數,巨集寫法,#,define COMPARE(x,y)(x)(y)?1:(x)=(y)?0:1),conditional expression,expr1,?,expr2,:,expr3,函數呼叫寫法,int compare(int,x,int,y,),if(,x,y,)return -1;,else if(,x=y,)return 0;,else return 1;,遞迴演算法Recursive Algorithms,直接遞迴（,Direct Recursion),一函數直接呼叫自己,二元搜尋法(,binary search),排列(,permutation),間接遞迴（,Indirect Recursion),A,函數呼叫,B,函數，而,B,函數會再呼叫,A,函數,Binary search and Permutation,Program 1.7,及,program1.8,在第四章及第五章會有更多的討論,程式作業2,Page 14 Exercise 11,Tower of Hanoi,漢諾塔或梵天塔,截止日期,兩個星期後,資料抽象化Data Abstraction,C,程式語言所提供的資料型態(,data type),C,本身已提供有,char,(,字元),int,(,整數),float,(,浮點),double,(,雙精度浮點),另外還有,short,(,短整數),long,(,長整數)及在基本型態還可以再加上關鍵字,unsigned,(,非負)來做變化,將相同資料型態群組化,(,array,陣列),將不一定相同的資料型態的資料集合起來(,structure,結構),struct,student,char,last_name;,int,student_id;,char,grade;,C,也提供了所謂指標資料型態(,pointer),int i,*p;,資料抽象化Data Abstraction,資料型態(,data type),的定義,一些物件的集合加上包含在物體上可以操作的一套操作方法,抽象資料型態(,abstract data type,ADT),也是資料型態,而它被整理成物件的規格定義和在這些個物件上操作方法的所有規格定義,在這些物件上所有的操作方法的定義規格是和物件的呈現及實際操作方法的製作是分開的,C,是沒有明顯的語法機制來製作,ADT,但是可以用一樣的觀念來達成,C+(Class),ADA(package),所以,ADT,可以是與實際製作無關的,資料抽象化Data Abstraction,ADT,資料型態所包含的功能,產生者/建構者(,Creator/Constructor),產生想要的資料型態的實體,轉換者,(Transformer),通常是要將一個或多個其他的資料型態實體轉換成一個新的資料型態實體,觀察者/記錄者(,Observer/Reporter),是提供資料型態實體的資訊,不會改變實體,一個,ADT,的定義就是至少包含上述的 一個功能,ADT實例,自然數(Nature_Number),自然數(,Nature_Number),的結構(,structure),就是,物件:一個從0開始一直到電腦上的最大整數值(,INT_MAX),結束的一連串整數數列,功能:,x,y,可以是所有在,Nature_Number,內的元素,TRUE,FALSE,是布林值(,boolean),而+,-,and=,是一般整數的運算元,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(,x=,INT_MAX)return,x,else,return,x,+1,Nat_No,Subtract(x,y):=if(,x,y,)return 0 else return,x-y,效能分析,評量程式好壞的一些標準,程式是否有達成所要完成的所有工作?,執行結果正確與否?,程式是否有任何操作說明的文件?,程式是否有效的利用函數來產生邏輯單元?,程式可讀性是否很高?,客觀分析(,Complexity Theory,),程式是否有效的利用了主要及次要的儲存裝置?,Space Complexity,程式執行出結果的時間是否能接受?,Time Complexity,演算法效能的表示式,空間複雜度(,Space Complexity),一個程式要完成工作所需的電腦記憶體空間,固定空間需求(,fixed space requirement),c,可變空間需求(,variable space requirement),S,p,(,I,),S,(,P,)=,c,+,S,p,(,I,),時間複雜度(,Time Complexity),一個程式要完成工作所需的電腦時間,利用不管是在語法或語意上都有重要意義的程式執行的,每一步,(program step),來作為衡量標準,因為通常程式中的每一行與每次程式執行的實體變化無關,漸近線的表示法,當兩個同樣要去完成一個工作的程式的實體特質(,e.g.input size,algorithm),變化時,可以預測在執行時間上的成長,漸近線的表示法,f,(,n,),就是在算,program step,時所獲致的函數值,(e.g.,f,(,n,)=,c,1,n,+,c,2,),O(,n,),f,(,n,)=,O,(,g,(,n,)iff there exist positive constants,c,and,n,0,such that,f,(,n,)=,n,0,3,n,+2=O(,n,),(3,n,+2)=2,(,n,),f,(n)=,(,g,(,n,)iff there exist positive constants,c,and,n,0,such that,f,(,n,)=,cg,(,n,)for all,n,n,=,n,0,3,n,+2=,(,n,),(3,n,+2)=3,n,n=1,(,n,),f,(n)=,(,g,(,n,)iff there exist positive constants,c,1,c,2,and,n,0,such that,c,1,g,(,n,)=,f,(,n,)=,n,0,所以,3,n,+2=,(,n,),c,1,=3,c,2,=4,以,selection sort,為例,實際效能測量Practical Performance Measurement,實際的複雜度分析(,Practical Complexity),在每個不同程式的輸入大小,在不同區段的分析,(e.g.Figure 1.7,1.8 and 1.9),實際的執行效能測量,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(Program 1.24 and 1.25),Large number of random test data,If and Only If,Iff,is a shorthand for the phrase,if and only if,.This phrase is used in assertions.If I assert that,A,if and only if,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 ways.Saying,A,iff,B,is the same thing as saying A implies B,and B implies A,or,one of my favorites,that A is a necessary and,sufficient condition,for B,or,equivalently,B is a necessary and,sufficient condition,for A.,The following are,equivalent,conditions:,A implies B,B if A,A only if B,A is,sufficient,for B,B is necessary for A,B or(not A),So if I say that A is necessary,and,sufficient,for B,then we get:A,if and only if,B,and(B or(not A)and(A or(not B)which is equivalent to(A and B)or(not A)and(not B)-in other words,A and B are either both true or both false.A and B are equivalent.,