結構_課程課件

1、第 一 章資料結構導論課程名稱：資料結構授課老師：_本章學習目標 讓讀者了解資料結構、演算法及程式之間的關係讓讀者了解如何評估演算法的執(zhí)行效率。本章內容 1-1 認識資料與資訊的關係1-2 何謂資料結構？1-3 何謂演算法?1-4 程式設計概念1-5 結構化程式設計1-6 演算法的效率評估 1-1 認識資料與資訊的關係1.資料(Data)：是指未經過處理的原始記錄。 例如：學生考試的原始成績。 2.資訊(Information) ：就是有經過資料處理的結果。 例如：全班同學成績之排名及分佈圖。 資料處理(Data Processing)則是將資料轉換成資訊的一連串 處理過程，而這一連串的處理過

2、程就是透過程式來處理。 例如：成績處理系統(tǒng)。如下圖所示：1.資料(Data)(1)是客觀存在的、具體的、事實的記錄。(2)簡單來說，日常生活中所記錄的事實資料(姓名、生日、電話及 地址)或學生在期中考的各科原始成績，這些都是未經過資料處 理的資料。 如表1-1所示。 2.資訊(Information) (1)經過資料處理之後的結果即為資訊。而資料與資訊的 特性比較。 如表1-2所示。(2)資料處理會將原始資料以加整理、計算及分析之後，變成有用 的資訊(含總成績、平均及排名次)。 如表1-3 所示。(3)有用的資訊是決策者在思考某一個問題時所需用到的資料，它是主觀 認定的。例如：班導師(決策者)

3、在學生考完期中考之後，想依學生考 試成績來獎勵。 1-2 何謂資料結構？ 資料結構(Data Structures)主要是探討如何將資料更有組織地存放到電腦記憶體中，以提昇程式之執(zhí)行效率的一門學問。 因此，有良好的資料結構（Data structure）及有效率的演算法（Algorithm）將可以大大的提昇程式的執(zhí)行效率。 在電腦科學(Computer Science)的領域中，我們如何透過電腦來取得即時的、有用的資訊，那就必須先要撰寫有效率及正確的程式去運作，而程式就是由資料結構和演算法所構成的。其公式如下：程式=資料結構(Data Structure)+演算法(Algorithms)其中：

4、資料結構：是指資料在記憶體中的儲存方式， 演算法:則是如何將資料作有效率的處理過程。因此，當我們在撰寫程式時，只有選擇適當的【資料結構】，才能夠設計出最有效率的【演算法】，進而轉換成為有效率的【程式】。 基本上，在資料結構課程中，包含有遞迴(Recursive)、陣列(Array)、堆疊(Stack)、佇列(Queue)、串列(List)、樹狀(Tree)、圖形(Graph)、排序(Sort)及搜尋(Search)等單元，雖然這幾種資料結構單元乍看之下，好像非常理論與抽象，但是在我們日常生活中，卻經?？梢钥吹?。【舉例】遞迴(Recursive)：老鼠走迷宮的問題就是屬於遞迴結構。陣列(Arra

5、y)：教室座位排列方式就是屬於陣列結構。堆疊(Stack)：碗盤的疊法、小朋友排積木、書本裝箱或座電梯等都 具有後進先出的特性就是屬於堆疊結構。佇列(Queue)：排隊買票看球賽，先到先買的方式就是所謂的 佇列結構【舉例】續(xù)串列(List)：高鐵火車的車箱串接方式就是屬於串列結構。樹狀(Tree)：如果球賽的賽程方式是採用淘汰制，就是一種樹狀 結構。圖形(Graph)：當看完球賽要回家的行駛路線圖，則可視為所謂的 圖形 結構。排序(Sort)：球賽成績的結果之排名方式就是屬於排序結構。搜尋(Search)：球賽比賽之前找尋某一隊的賽程就是屬於搜尋結 構?！緦嵗?撰寫一個程式來計算5位同學的資

6、料結構平均成績，並且比較沒有使用資料結構與演算法的差異。 第一種方法沒有使用資料結構與演算法，而是使用一般變數的宣告方式來個別存放成績資料。雖然也可以順利的計算出所需要的結果，但是，比較缺乏彈性，因為，當我們要計算的學生人數異動時，程式將會比較難以維護。例如：全班學生人數為50人時，則行號03的程式碼就會變數非常的長， 容易產生錯誤。 第二種方法是使用陣列資料結構來存放5位同學的成績資料，然後再使用for迴圈的演算法來計算5位同學的成績，最後再列印出結果。比較分析：第二種方法的程式比較有彈性，也就是說，當我們要計算的學生人數異動時，只要設定行號03的學生人數及行號04的陣列內容即可。 1-3

7、何謂演算法?演算法在韋氏辭典中定義為：在有限步驟內解決數學問題的程 序。我們可以把演算法(Algorithm)定義成：解決問題的方法。 【題目】製作蛋糕的方法，其步驟如下：1-3.1撰寫演算法應遵守五點原則1.輸入(Input)：不一定要有輸入?？赡軟]有，也可能是多個資料輸入。 【題目】 製作蛋糕時，必須要輸入：雞蛋、麵粉及鮮奶等食材?！菊n本例子】例如1：不需輸入 如果想要取得系統(tǒng)目前的時間，不須要輸入，只要寫一行now() 函數，就可以輸出系統(tǒng)時間。例如2：必需輸入 求某數為奇偶數時，則必須先要有一個輸入整數，才能進行 判斷。一、撰寫演算法應遵守五點原則： (續(xù)) 2.明確性(Definit

8、eness)：每一行指令都必須明確，不可模稜兩可。 【題目】製作蛋糕時，要加入多少的麵粉與雞蛋及要加熱多久， 必須明確，不可模稜兩可。 例如1：判斷某一數值是否為偶數。首先我們試著用下列文字來加以描述： (1)輸入一個正整數。(2)作餘除運算是否為0。(3)為0即為偶數。以上描述看來似乎正確，但是從演算法觀點來看，其中的第(2)點並不符合明確性，因它並未說明餘除運算是如何運算，容易造成混淆與不解。我們應該改寫為： (1)輸入一個正整數N。(2)如果N 除以2，其餘數為0。(3)則其N為偶數。不具明確性具明確性【課本例子】【課本例子】例如2：用功的學生才能領獎學金就不具有明確性，因為每一個人對用

9、功的定義可能不盡相同，而如果改為成績90以上的學生才能領獎學金就是具有明確性，因為90分是一個比較客觀的定義。一、撰寫演算法應遵守五點原則： (續(xù))3.有限性(Finiteness)：演算法不能有無窮迴路，必須能終止執(zhí)行， 亦即必須在有限的步驟內完成。 【題目】製作蛋糕必須在有限的步驟內完成【課本例子】由於演算法並非是真正可以執(zhí)行的程式。但是，真正的程式是可以有無窮迴路的動作。 例如：Windows 作業(yè)系統(tǒng)(系統(tǒng)程式)除非系統(tǒng)關機或當機，否則它會 永遠執(zhí)行一個等待迴圈，來等待使用者從鍵盤輸入或其他 的輸入設備。 一、撰寫演算法應遵守五點原則： (續(xù))4.正確性(Correctness) ：既

10、然演算法是解決問題的方法，因此， 正確性是最基本的要求。 【題目】製作出來的蛋糕必須要正確，亦即符合使用者的需求【課本例子】例如：以下判斷某數為奇偶數的演算法，雖然符合明確性，但是 不正確，因為N 除以2，其餘數為0，則N應該為偶數， 而非奇數。 輸入一個正整數N。如果N 除以2，其餘數為0。則其N為奇數。應該改為偶數 一、撰寫演算法應遵守五點原則：( 續(xù))5.輸出(Output)：至少一個輸出。 【題目】在製作蛋糕時，在輸入雞蛋、麵粉及鮮奶之後，一定會有輸出。2022/7/2528例如：在電腦中，處理資料的基本過程有三個步驟： 輸入 處理 輸出 (原始資料) (程式) (有用的資訊) 所以，

11、使用電腦來為我們處理資料時，有可能是系統(tǒng)自動接收到一個訊號，來當作輸入資料，但是系統(tǒng)至少會輸出一項讓使用者參考的有用資訊。 【課本例子】1-3.2 描述演算法有三種方法(一)文字敘述【定義】演算法可用文字來加以描述，但是會比較不精確，因此一般較 不常用?！绢}目】 請利用文字敘述來描述使用者登入帳號與密碼時，系統(tǒng)檢查的過程。【解答】步驟一：輸入使用者帳號與密碼步驟二：判斷帳號與密碼是否正確步驟三：如果正確時，則可以登入系統(tǒng) 否則，就無法登入！(二)流程圖（Flowchart）【定義】利用圖形方式來表達欲解決問題的步驟?！绢}目】請利用流程圖來描述使用者登入帳號與密碼時，系統(tǒng)檢查的過程?！窘獯稹空f明

12、：流程圖可以協(xié)助程式設計者設計程式，可增加程式的可讀性。(三)虛擬碼（Pseudo Code）【定義】兼具文字描述及流程圖的優(yōu)點，其方式是用文字摻雜程式語言， 來描述解題步驟與方法。【題目】 請利用虛擬碼敘述使用者登入帳號與密碼時，系統(tǒng)檢查的過程?！窘獯稹?(1)Input: UserName, Password (2)IF (UserName And Password) ALL True Output: You Can Pass! else Output: You Can not Pass!說明：在資料結構中，一般都是利用虛擬碼來表示演算法。 一、流程圖（Flowchart）【定義】利用圖形

13、方式來表達欲解決問題的步驟。【優(yōu)點】1.它可協(xié)助程式設計者設計更周詳的程式 2.可增加程式的可讀性 3.對於初學者而言可幫助奠定良好的程式設計基礎【作法】分析那些資料是要輸入，經過處理之後，要輸出 那些結果?！纠L製原則】1.流程圖必須使用標準符號，便於閱讀和分析。 2.流程圖中的文字力求簡潔、扼要，而且明確可行。 3.繪製方向應由上而下，由左至右。 4.流程線條避免太長或交叉，可多用連接符號。 延伸學習一、流程圖（Flowchart）【舉例】請繪出使用者登入帳號與密碼時，系統(tǒng)檢查的流程圖。提示：步驟1：輸入帳號與密碼 步驟2：檢查是否正確 步驟3.1：正確時，則顯示Pass。 步驟3.2：不正

14、確時，則顯示NoPass。 延伸學習二、虛擬碼（Pseudo Code）【比較流程圖與虛擬碼】【題目】比較1+2+3+10的流程圖與虛擬碼。延伸學習(1)設Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count = 60) printf(及格); else printf (不及格);End End Procedure4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止 當使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績?yōu)?0.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態(tài)改為float(浮點數

15、)【重要觀念】 系統(tǒng)發(fā)展的生命週期與程式設計之步驟比較 1-4.1 演算法與程式的差異？1.演算法是以人為主，亦即任何人都可以閱讀的程式碼， 因此，必須特別強調可讀性。 1-4.1 演算法與程式的差異？(續(xù))2.程式則是以電腦為主，它強調程式的執(zhí)行結果正確性、 可維護性及執(zhí)行效率。 1-4.2為什麼要撰寫程式?主要的目的：快速解決複雜的問題。 例如1：小華問：小明請幫我計算1加到10的總和。 小明說：1+2+3+10=55大家都會，太簡單了！1-4.2為什麼要撰寫程式?(續(xù))例如2：小華又問：小明請幫我計算1加到50000時。小明則說：太困難了，我無法馬上計算出結果。但是我可以利用 撰寫程式來

16、處理。說明：因此，我們可以非常清楚的知道，程式語言幫忙人類 解決複雜的問題。1-4.3 一個好程式需要滿足條件一、正確性(Correctness)二、效率性(Performance)三、可維護性(Maintainable)一、正確性(Correctness)既然演算法是解決問題的方法，所以正確性是一個好程式最基本的要求。例如：設計一個判斷奇偶數的程式 說明：上面的程式處理過程中，由於程式不正確，所以產生錯誤的結果。二、效率性(Performance)指程式真正執(zhí)行時所必須要花費的時間。一般評估執(zhí)行時間是依程式碼所被執(zhí)行的總次數來計算。亦即所謂的頻率次數)當頻率次數愈高時，代表所需的執(zhí)行時間愈長

17、。例如：計算下列程式中變數Count被執(zhí)行的次數為何？三、可維護性(Maintainable)一個好的程式，不只需要有效率地被正確地執(zhí)行之外，也必須要考慮程式的可讀性、及未來修改和擴充性，這屬於程式設計方法和風格的問題，例如：使用模組化來設計程式和加上完整程式註解的說明。 三、可維護性(Maintainable)(續(xù))(一) 縮排【使用時機】在使用巢狀結構時，必須特別需要。使用縮排技巧 未使用縮排技巧三、可維護性(Maintainable)(續(xù))(二) 註解【定義】它是一種非執(zhí)行的敘述亦即是給人看的，而電腦不會去執(zhí) 行它。此功能就是用來說明某一段程式碼的作用與目的。1.使用雙斜線/的使用時機：

18、可以寫在程式碼的後面或單獨一行註解。2.使用/*/的使用時機：註解的內容超過一行時。三、可維護性(Maintainable)(續(xù))(三) 變數及函數名稱的命名好的變數宣告命名說明：爾後維護時，看到變數名稱就可以得知變數的意義。不好的變數宣告命名說明：爾後維護時，無法馬上得知A與B變數所代表的意思。1-5 結構化程式設計【定義】利用由上而下的技巧，將程式分解成許多個獨立功能的 模組。如圖1-5所示。圖1-5 結構化程式設計的示意圖每一個獨立功能的模組都是由結構化程式設計的三個基本結構所組成。1-5.1 循序結構【定義】是指程式由上而下，依序逐一執(zhí)行?！绢}目】計算國文與英文兩科的平均成績。如下圖所

19、示：1-5.2 選擇結構【定義】指根據某種條件成立，來選擇不同的執(zhí)行路徑?！绢}目】計算兩科平均成績，並判斷平均成績是否及格。如下圖所示。 1-5.3 重複結構【定義】指讓某一段程式反覆執(zhí)行多次的敘述?！绢}目】利用迴圈來計算兩科總分及平均。如圖1-8所示。 i=2i+重複結構1-6 演算法的效率評估【定義】指用來計算某些演算法所撰寫的程式，在經過編譯之後， 實際執(zhí)行所需要的時間?！驹u估方法】 一、時間複雜度（Time Complexity） 二、空間複雜度（Space Complexity）一、時間複雜度（Time Complexity）【定義】 是指從主程式呼叫該副程式開始到完成之過程，所有花

20、費的 執(zhí)行時間?！居绊憟?zhí)行時間因素】(1) 硬體部份：機器的CPU執(zhí)行速度不考慮(2) 軟體部份：演算法的好壞是由執(zhí)行時間來決定，因此， 執(zhí)行時間 = 執(zhí)行次數每次執(zhí)行所需時間 但是，由於每次執(zhí)行所需時間會受CPU的影響(所以不考慮，則設為常數1)，所以： 執(zhí)行時間 = 執(zhí)行次數 1因此， 執(zhí)行時間=執(zhí)行次數二、空間複雜度（Space Complexity）【定義】是指從主程式呼叫該副程式開始到完成之過程，所有佔用的 記憶體空間。例如：參數、變數宣告，回傳值以及傳回 位址時，都會佔用記憶體空間。說明：保存A函數當時執(zhí)行時之狀態(tài) 包括：參數值區(qū)域變數值返回位址(Return Address)，時

21、間複雜度與空間複雜度之分析 基本上，時間複雜度的分析比空間複雜度來得重要，因為當資料量龐大時，時間複雜度會有較大的差異性，但是，空間複雜度則差異較小，再加上目前的記憶體相當便宜，因此，目前在資料結構所探討演算法之效率評估，都著重在時間複雜度方面的評估。1-6.1 時間複雜度(Time complexity)【定義】是指計算執(zhí)行程式所花費的時間。一般而言，我們可以將一個程式P的時間複雜度表示成T(P)的形式。而T(P)記錄了程式執(zhí)行次數n的成長速率。【定義】一般評估執(zhí)行時間是依程式碼所被執(zhí)行的總次數來計算。 也就是所謂的頻率次數)，當頻率次數愈高時，代表所 需的執(zhí)行時間愈長?！绢}目1】假設有一陣

22、列a，其陣列的大小為n，如果要將陣列a的元素相加，請問程式的執(zhí)行次數為何？一、演算法的執(zhí)行次數題目：陣列元素相加之演算法【解答】執(zhí)行的次數01020304050607int sum(int a , int n) int i, total=0; for (i=0; i n; i+) total += ai; return total;1n+1n1T(P)=2n+3i會再多執(zhí)行1次的比較加總【題目2】假設兩矩陣a, b相加，並且矩陣大小皆為n*n，請計算出下列程式的執(zhí)行次數？題目：兩矩陣a, b相加，利用雙重迴圈演算法【解答】執(zhí)行的次數01020304050607void Add(int a, i

23、nt b, int c, int n) int i, j; for(i=0; in; i+) for (j=0; jn; j+) ci,j =ai,j+bi,j;1n+1n*(n+1)n2T(P)=2n2+2n+2加總【題目3】假設兩矩陣a, b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執(zhí)行次數？題目：兩矩陣a, b相乘，利用多重迴圈演算法【解答】執(zhí)行的次數010203040506070809101112void Multi(int a, int b, int c, int n) int i, j, k, sum; for (i=0; i n; i+) for (j=0; j n;

24、j+) sum = 0; for (k=0; k n; k+) sum = sum+ai,k*bk,j; ci,j = sum; 1n+1n*(n+1)n2n2*(n+1)n3n2T(P)=2n3+4n2+2n+2加總【練習題】假設有一個巢狀迴圈之演算法，如下所示：請追蹤x=x+1的總執(zhí)行次數？【解答】利用等差數列：演算法For i=1 to n do For j=i to n do x=x+1 End End 演算法統(tǒng)計執(zhí)行的次數For i=1 to n do For j=i to n do x=x+1 End End i=1 i=2 i=3 i=nj=1 to n j=2 to n j=3

25、 to n j=n to n執(zhí)行：n次 (n-1)次 (n-2)次 1次二、演算法的時間複雜度O(n)【定義】O(n)可視為某演算法在電腦中所需執(zhí)行時間，亦即將 執(zhí)行次數轉換成電腦所需的執(zhí)行時間。【執(zhí)行次數轉換時間複雜度之作法】 取執(zhí)行次數中最高次方或最大指數部份的項目即可。 陣列元素相加為2n+3 = O(n)矩陣相加為2n2+2n+2 = O(n2)矩陣相乘為2n3+4n2+2n+2 = O(n3)三、時間複雜度的等級【定義】在資料結構中，評估某一演算法的執(zhí)行效率，必須視其 時間複雜度的等級?！緯r間複雜度的等級】說明：效率愈高，代表著執(zhí)行時間愈短。例如O(n)比O(n2)更有效率。O(n)

26、比O(n2)更有效率【舉例】假設有一個問題，分別利用七種不同演算法來解決， 請問下表中，那一種方法最佳，那一種方法最差？【解答】假設每一種演算法都必須輸入資料量(n=10)時， 則它們的時間複雜度大小順序為： O(log2 n) O(n) O(n log2 n) O(n2 ) O(n3 ) O(2n ) O(n! )評估演算法的三種方法：一、O(n)( Big-O of n)：最常被使用，用來表示理論上限二、(n) (Big-Omega of n)：用來表示理論下限三、(n)(Big-Theta of n)：表示理論上限與下限延伸學習一、O(n)( Big-O of n)：最常被使用，用來表示

27、理論上限【假設】f(n)：統(tǒng)計的執(zhí)行次數。g(n)：Big-O取執(zhí)行次數中最高次方或最大指數部份的項目。若且唯若f(n)=O(g(n)，則存在一正整數c及n0，對所有的n值而言，當nn0時，則f(n)c*g(n)均成立。延伸學習【題目】證明f(n)3n+2，可以用(n)來表示?！窘獯稹考僭Of(n)c*g(n)關係式成立3*n2c*n (因為f(n)=O(g(n)(c-3)*n2當c4時，則n2，所以n02 (因為nn0)所以只要c4，且n0 2時，則3*n24*nf(n) 3n2，就可以用(n)來表示。延伸學習【題目】證明f(n)10n2+5n+1 , 可用O(n2)表示?！窘獯稹考僭Of(n)

28、c*g(n)關係式成立10 n2+5n+1 c*n2 (因為f(n)=O(g(n)(c-10)n25n+1當c=11，則上式為n25n+1並且當n6時，則 n25n+1，所以n0=6(因為nn0)所以只要c11，n06則10 n2+5n+111n2f(n)= 10 n2+5n+1可以用O(n2)表示延伸學習二、(n) (Big-Omega of n)：用來表示理論下限若且唯若f(n)=(g(n)，則存在一正整數c及n0，對所有的n值而言，當nn0時，則f(n)c*g(n)均成立?！绢}目】證明f(n)3n+2，可以用(n)來表示?！窘獯稹?假設f(n)c*g(n)關係式成立3*n2c*n(3-c)*n-2當c2時，並且n1，上式即可成立找到c2， n01(因為nn0)時，則3n+2 2n2 f(n)= 3n+2可以用(n)表示延伸學習【題目】證明f