《资料结构(用C语言)资讯工程学系.ppt》由会员分享，可在线阅读，更多相关《资料结构(用C语言)资讯工程学系.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、資料結構（用資料結構（用C語言）語言）資訊工程學系資訊工程學系王家輝王家輝資訊工程學系資訊工程學系http:/www.csie.mcu.edu.tw/wangchhttp:/www.csie.mcu.edu.tw/wangch課程目標課程目標n n資料結構是資訊科學學門中的核心課程，而本課程主要在介紹各種型態資料結構在C程式語言中的呈現，以及和演算法的關係。n n修習本課程的同學，除了學到常用的資料表現方式之外，如何在設計C程式時選取合適的資料結構、配合適當的演算法、和評估所採用的資料結構的優缺點等都是本課程的重點。課程大綱與進度課程大綱與進度n n程式設計基本概念與程式設計基本概念與C C程
2、式語言基本認識程式語言基本認識n nC C程式語言組成程式語言組成n n資料型態、運算子、流程控制指令資料型態、運算子、流程控制指令 n n函數、指標、陣列與結構函數、指標、陣列與結構)n n輸入輸入/輸出與檔案處理輸出與檔案處理)n n演算法的規格演算法的規格演算法的規格演算法的規格,資料抽象化與程式的複雜度分析資料抽象化與程式的複雜度分析資料抽象化與程式的複雜度分析資料抽象化與程式的複雜度分析n nArray(Array(陣列陣列)與與Structure(Structure(結構結構)n nStack(Stack(堆疊堆疊)與與Queue(Queue(佇列佇列)n nLinked List
3、(Linked List(串列串列)n nTree(Tree(樹狀結構樹狀結構)n nGraph(Graph(圖狀結構圖狀結構)n nSorting(Sorting(排序排序)n nHashing(Hashing(雜湊結構雜湊結構)n nHeap(Heap(堆積結構堆積結構)n nSearching(Searching(搜尋結構搜尋結構)參考書籍參考書籍n nEllis Horowitz,Sarataj Sahni,Susan Anderson-Ellis Horowitz,Sarataj Sahni,Susan Anderson-freed,freed,Fundamentals of dat
4、a structures in CFundamentals of data structures in C,W.H.Freeman and Company,New York,1993 W.H.Freeman and Company,New York,1993 n nBrian W.Kernighan,Dennis M.Ritchie,Brian W.Kernighan,Dennis M.Ritchie,The C The C Programming LanguageProgramming Language,2nd Ed.,Printice-Hall,2nd Ed.,Printice-Hall,
5、New Jersey,1990 New Jersey,1990 成績評量成績評量n n平時成績(程式作業)30%n n期中考30%n n期末考40%第一章第一章資料結構基本觀念資料結構基本觀念資訊工程學系系統的生命週期系統的生命週期System Life Cyclen n需求需求(Requirement)Requirement)n n一整套規格一整套規格(A set of specifications)A set of specifications)n n所需之輸入及輸出所需之輸入及輸出(Inputs and Outputs)Inputs and Outputs)n n分析分析(Analysi
6、s)Analysis)n n將問題分割成可以掌握的小問題將問題分割成可以掌握的小問題n n有兩種分析方式有兩種分析方式n n由下而上由下而上(bottom-up)bottom-up)n n由草圖一磚一瓦的蓋房子由草圖一磚一瓦的蓋房子n n由上而下由上而下(top-down)top-down)n n由程式最終要完成目標開始由程式最終要完成目標開始n n設計組織及流程圖設計組織及流程圖(將程式分割成可管控的單元將程式分割成可管控的單元)系統的生命週期系統的生命週期System Life Cyclen n設計設計(Design)Design)n n抽象化的資料型態抽象化的資料型態(e.g.(e.g.
7、選課系統選課系統)n n演算法的方法與步驟演算法的方法與步驟n n修正及程式設計修正及程式設計(Refinement and Coding)Refinement and Coding)n n完成抽象化資料的實際表示完成抽象化資料的實際表示n n撰寫演算法的程式撰寫演算法的程式n n驗證驗證(Verification)Verification)n n用理論證明該方法的正確性用理論證明該方法的正確性(Correctness Proofs)Correctness Proofs)n n費時費時n n可參考別人已驗證過的演算法可參考別人已驗證過的演算法n n測試測試(Testing)Testing)n
8、ne.e.g.if and switchg.if and switchn n除錯除錯(Error Removal)(Error Removal)演算法的一般規格演算法的一般規格Algorithm Specificationn n想要利用電腦解決特定問題的方法及步驟想要利用電腦解決特定問題的方法及步驟,n n輸入輸入(Input)Input)n n需要提供需要提供0 0個以上數量的外在資料個以上數量的外在資料n n輸出輸出(Output)Output)n n至少要有一個以上的資料產出至少要有一個以上的資料產出n n確定性確定性(Definiteness)Definiteness)n n每一項方法
9、及步驟是清楚而且不是模稜兩可的每一項方法及步驟是清楚而且不是模稜兩可的n n有限性有限性(Finiteness)Finiteness)n n這個演算法一定要在有限的步驟內完成這個演算法一定要在有限的步驟內完成n n有效性有效性(Effectiveness)Effectiveness)n n每一項方法及步驟是足夠簡單的可以完成每一項方法及步驟是足夠簡單的可以完成(可以對應到程式可以對應到程式),),基本上用一支筆及一張紙就可以完整描述這個演算法基本上用一支筆及一張紙就可以完整描述這個演算法,也就是也就是每一步驟是可行的每一步驟是可行的幾個範例幾個範例Samplesn n選擇排序法(Selecti
10、on Sort)n n在未排序的數列中每次找出最小在未排序的數列中每次找出最小(最大最大)的，將的，將最小最小(最大最大)的數值依序列出的數值依序列出n n二元搜尋法(Binary Search)n n在已排序好的數列中找到是否存在某一筆數值在已排序好的數列中找到是否存在某一筆數值Selection Sortn n一個簡單的方法將一連串正整數做由大到小或者由小到大的排列n n從這些未排序的數列中一一找出最小，把它們從這些未排序的數列中一一找出最小，把它們依序置入一個排序的數列中依序置入一個排序的數列中n n這樣的敘述不是一個演算法的正確描述這樣的敘述不是一個演算法的正確描述n ne.g.e.g
11、.沒有告訴這些數列一開始如何儲存，還有結果到底要沒有告訴這些數列一開始如何儲存，還有結果到底要放到哪裡放到哪裡n n我們嘗試用中英文和C語言夾雜著來描述這個演算法：氣泡排序法的演算法氣泡排序法的演算法Selection Sort Algorithmn n假設資料都放在個整數陣列,名字為list,第i筆整數就放在 listi 中,0=inforfor(i i=0;=0;i i=1),它們已經排序過,而且放在一個整數型態的陣列中n nlistlist0=0=listlist1=1=listlistn-1n-1n n要從上述陣列中搜尋到searchnum這個整數n n如果找到就傳回那個數值所在陣列中
12、的索引位如果找到就傳回那個數值所在陣列中的索引位置置n n如果找不到就傳回如果找不到就傳回-1-1二元搜尋法二元搜尋法Binary Searchn n讓讓left,rightleft,right兩個變數分別代表要搜尋數列範圍中最左邊兩個變數分別代表要搜尋數列範圍中最左邊及最右邊的索引位置及最右邊的索引位置n n一開始的位置當然是一開始的位置當然是 left left=0,=0,rightright=n n-1-1n n讓另一個變數讓另一個變數 middlemiddle=(=(leftleft+rightright)/2)/2n n假使我們比較假使我們比較 list list middlemid
13、dle 和和 searchnumsearchnum,可以發現下列三個可以發現下列三個現象現象n nsearchnumsearchnum list list middlemiddle n nsearchnumsearchnum應該落在應該落在middlemiddle和和rightright區間區間,所以將所以將leftleft=middle+1middle+1n n如果沒有找到，就要再將如果沒有找到，就要再將middlemiddle=(=(leftleft+rightright)/2,)/2,繼續前一步驟，繼續前一步驟，直到沒有數列可以檢查為止直到沒有數列可以檢查為止程式程式(program 1
14、.6)中用到的比較中用到的比較函數函數n n巨集寫法巨集寫法#define COMPARE(x,y)(x)(y)?1:(x)=(y)?define COMPARE(x,y)(x)(y)?1:(x)=(y)?0:1)0:1)n n conditional expression conditional expressionn nexpr1expr1?expr2expr2:expr3expr3n n函數呼叫寫法函數呼叫寫法int compare(int int compare(int x x,int,int y y)if(if(x x y y)return -1;)return -1;else if
15、(else if(x=yx=y)return 0;)return 0;else return 1;else return 1;遞迴演算法遞迴演算法Recursive Algorithmsn n直接遞迴（直接遞迴（Direct Recursion)Direct Recursion)n n一函數直接呼叫自己一函數直接呼叫自己n n二元搜尋法二元搜尋法(binary search)binary search)n n排列排列(permutation)permutation)n n 間接遞迴（間接遞迴（Indirect Recursion)Indirect Recursion)n nA A函數呼叫函數呼
16、叫 B B函數，而函數，而B B函數會再呼叫函數會再呼叫A A函數函數n nBinary search and PermutationBinary search and Permutationn nProgram 1.7Program 1.7及及program1.8program1.8n n在第四章及第五章會有更多的討論在第四章及第五章會有更多的討論程式作業程式作業2n nPage 14 Exercise 11n nTower of HanoiTower of Hanoin n漢諾塔或梵天塔漢諾塔或梵天塔n n截止日期截止日期n n兩個星期後兩個星期後資料抽象化資料抽象化Data Abstra
17、ctionn nC C程式語言所提供的資料型態程式語言所提供的資料型態(data type)data type)n nC C本身已提供有本身已提供有charchar(字元字元),),intint(整數整數),),floatfloat(浮點浮點),),doubledouble(雙精度浮點雙精度浮點)n n另外還有另外還有shortshort(短整數短整數),),longlong(長整數長整數)及在基本型態還可以再加上及在基本型態還可以再加上關鍵字關鍵字 unsignedunsigned(非負非負)來做變化來做變化n n將相同資料型態群組化將相同資料型態群組化,(,(array,array,陣列陣
18、列)n n將不一定相同的資料型態的資料集合起來將不一定相同的資料型態的資料集合起來(structure,structure,結構結構)structstruct student student charchar last_name;last_name;int int student_id;student_id;charchar grade;grade;n nC C也提供了所謂指標資料型態也提供了所謂指標資料型態(pointer)pointer)int iint i,*p;,*p;資料抽象化資料抽象化Data Abstractionn n資料型態資料型態(data type)data type)的
19、定義的定義n n一些物件的集合加上包含在物體上可以操作的一套操一些物件的集合加上包含在物體上可以操作的一套操作方法作方法n n抽象資料型態抽象資料型態(abstract data type,ADT)abstract data type,ADT)n n也是資料型態也是資料型態,而它被整理成物件的規格定義和在這些而它被整理成物件的規格定義和在這些個物件上操作方法的所有規格定義個物件上操作方法的所有規格定義n n在這些物件上所有的操作方法的定義規格是和物件的在這些物件上所有的操作方法的定義規格是和物件的呈現及實際操作方法的製作是分開的呈現及實際操作方法的製作是分開的n nC C是沒有明顯的語法機制來
20、製作是沒有明顯的語法機制來製作ADT,ADT,但是可以用一樣但是可以用一樣的觀念來達成的觀念來達成n nC+(Class),ADA(package)C+(Class),ADA(package)n n所以所以ADTADT可以是與實際製作無關的可以是與實際製作無關的資料抽象化資料抽象化Data Abstractionn nADTADT資料型態所包含的功能資料型態所包含的功能n n產生者產生者/建構者建構者(Creator/Constructor)Creator/Constructor)n n產生想要的資料型態的實體產生想要的資料型態的實體n n轉換者轉換者(Transformer)(Transfo
21、rmer)n n通常是要將一個或多個其他的資料型態實體轉換成一個新的資通常是要將一個或多個其他的資料型態實體轉換成一個新的資料型態實體料型態實體n n觀察者觀察者/記錄者記錄者(Observer/Reporter)Observer/Reporter)n n是提供資料型態實體的資訊是提供資料型態實體的資訊,不會改變實體不會改變實體n n一個一個ADTADT的定義就是至少包含上述的的定義就是至少包含上述的 一個功能一個功能ADT實例實例,自然數自然數(Nature_Number)n n自然數自然數(Nature_Number)Nature_Number)的結構的結構(structure)struc
22、ture)就是就是n n物件物件:一個從一個從0 0開始一直到電腦上的最大整數值開始一直到電腦上的最大整數值(INT_MAX)INT_MAX)結束的一連串結束的一連串整數數列整數數列n n功能功能:x x,y y可以是所有在可以是所有在Nature_NumberNature_Number內的元素內的元素,TRUE,FALSETRUE,FALSE是布林是布林值值(boolean)boolean)而而+,-,+,-,and=and=是一般整數的運算元是一般整數的運算元n nNat_NoNat_No Zero()Zero():=0:=0n nBooleanBoolean Is_Zero(Is_Zer
23、o(x x):=if(:=if(x x)return FALSE else)return FALSE else return TRUEreturn TRUEn nNat_NoNat_No Add(Add(x x,y y):=if(:=if(x x+y y)=INT_MAX)=INT_MAX)return return x x+y yn nBooleanBoolean Equal(x,y)Equal(x,y):=if(:=if(x=yx=y)return TRUE else)return TRUE else return FALSEreturn FALSEn nNat_NoNat_No Succ
24、essor(x)Successor(x):=if(:=if(x=x=INT_MAX)return INT_MAX)return x x else elsereturnreturn x x+1+1n nNat_NoNat_No Subtract(x,y)Subtract(x,y):=if(:=if(x x y y)return 0 else return)return 0 else return x-yx-y效能分析效能分析n n評量程式好壞的一些標準評量程式好壞的一些標準n n程式是否有達成所要完成的所有工作程式是否有達成所要完成的所有工作?n n執行結果正確與否執行結果正確與否?n n程式是
25、否有任何操作說明的文件程式是否有任何操作說明的文件?n n程式是否有效的利用函數來產生邏輯單元程式是否有效的利用函數來產生邏輯單元?n n程式可讀性是否很高程式可讀性是否很高?n n客觀分析客觀分析(Complexity TheoryComplexity Theory)n n程式是否有效的利用了主要及次要的儲存裝置程式是否有效的利用了主要及次要的儲存裝置程式是否有效的利用了主要及次要的儲存裝置程式是否有效的利用了主要及次要的儲存裝置?n nSpace ComplexitySpace Complexityn n程式執行出結果的時間是否能接受程式執行出結果的時間是否能接受程式執行出結果的時間是否能
26、接受程式執行出結果的時間是否能接受?n nTime ComplexityTime Complexity演算法效能的表示式演算法效能的表示式n n空間複雜度空間複雜度(Space Complexity)Space Complexity)n n一個程式要完成工作所需的電腦記憶體空間一個程式要完成工作所需的電腦記憶體空間n n固定空間需求固定空間需求(fixed space requirement),fixed space requirement),c cn n可變空間需求可變空間需求(variable space requirement),variable space requirement),S
27、 Sp p(I I)n nS S(P P)=)=c c+S Sp p(I I)n n時間複雜度時間複雜度(Time Complexity)Time Complexity)n n一個程式要完成工作所需的電腦時間一個程式要完成工作所需的電腦時間n n利用不管是在語法或語意上都有重要意義的程式執行的利用不管是在語法或語意上都有重要意義的程式執行的每一步每一步每一步每一步(program step)(program step)來作為衡量標準來作為衡量標準n n因為通常程式中的每一行與每次程式執行的實體變化無關因為通常程式中的每一行與每次程式執行的實體變化無關n n漸近線的表示法漸近線的表示法n n當兩
28、個同樣要去完成一個工作的程式的實體特質當兩個同樣要去完成一個工作的程式的實體特質(e.g.e.g.input size,algorithm)input size,algorithm)變化時變化時,可以預測在執行時間上的可以預測在執行時間上的成長成長漸近線的表示法漸近線的表示法n nf f(n n)就是在算就是在算program stepprogram step時所獲致的函數值時所獲致的函數值(e.g.(e.g.f f(n n)=)=c c1 1n n+c c2 2)n nO(O(n n)n nf f(n n)=)=OO(g g(n n)iff there exist positive cons
29、tants)iff there exist positive constants c c and and n n0 0 such that such that f f(n n)=)=n n0 0n n3 3n n+2=O(+2=O(n n),(3),(3n n+2)=4+2)=2n,n=2n n(n n)n nf f(n)=(n)=(g g(n n)iff there exist positive constants)iff there exist positive constants c c and and n n0 0 such that such that f f(n n)=)=cgcg
30、(n n)for all)for all n n,n n=n n0 0n n3 3n n+2=+2=(n n),(3),(3n n+2)=3+2)=3n,n=1n,n=1n n(n n)n nf f(n)=(n)=(g g(n n)iff there exist positive constants)iff there exist positive constants c c1 1,c,c2 2 and and n n0 0 such that such that c c1 1g g(n n)=)=f f(n n)=)=n n0 0n n所以所以3 3n n+2=+2=(n n),),c c1
31、 1=3,=3,c c2 2=4=4n n以以selection sortselection sort為例為例實際效能測量實際效能測量Practical Performance Measurementn n實際的複雜度分析實際的複雜度分析(Practical Complexity)Practical Complexity)n n在每個不同程式的輸入大小在每個不同程式的輸入大小,在不同區段的分析在不同區段的分析(e.g.Figure(e.g.Figure 1.7,1.8 and 1.9)1.7,1.8 and 1.9)n n 實際的執行效能測量實際的執行效能測量n nUse C build-in
32、 functions Use C build-in functions clockclock()()or time or time()to measure()to measure execution timeexecution timen nFigure 1.10,Program 1.23 and Figure 1.11Figure 1.10,Program 1.23 and Figure 1.11n nGenerating Test DataGenerating Test Datan nWorst case dataWorst case datan ne.g.sequential search(Program 1.24 and 1.25)e.g.sequential search(Program 1.24 and 1.25)n nLarge number of random test dataLarge number of random test data