資料結構 Data Structure chapter 1 德明科技大學資訊科技系

課程資訊 Lecturer: 江政杰 課程網頁 Office: 四合院 301 URL: nas.takming.edu.tw/pluto Mail: pluto@mail.takming.edu.tw 課程網頁 URL: nas.takming.edu.tw/pluto/ds/ds.html 教材、補充資訊 作業 相關連結 德明科技大學資訊科技系

課程資訊 Text Book : 成績評量 資料結構 – 使用C語言 李春雄著 上奇出版社 期中、期末各佔30%、平時成績佔40% 德明科技大學資訊科技系

課程內容 資料結構與演算法 遞迴 Recursion 陣列 Array 堆疊 Stack 佇列 Queue 鏈結串列 Linked List 樹狀結構 Tree Structure 圖形 Graph Structure 排序 Sorting 搜尋 Search 德明科技大學資訊科技系

修課基礎 程式撰寫 具備邏輯概念 還無法順利掌握程式撰寫?? 對於變數、函數、陣列等基本程式語言的使用與掌握 對於一個問題，可以在找出解決方法之後，撰寫出程式碼 具備邏輯概念 學習程式除了語法的熟悉外，最重要的是邏輯概念的訓練，才有能力學習其他語言 還無法順利掌握程式撰寫?? 以資料結構這門課程為程式設計的進階訓練 程式設計能力的再次訓練 德明科技大學資訊科技系

上課方式 投影片展示，請自行搭配課本閱讀 實例練習 作業練習 期中、期末考試 在課程中會搭配一些程式範例，讓同學實際操作程式之撰寫，以掌握程式撰寫的能力 作業練習 每一段時間，會有一完整的題目要求撰寫程式，計入平時成績內 期中、期末考試 德明科技大學資訊科技系

學習程式 入門 進階 深入 學習VB、Dev C++等軟體的使用 熟悉VB、C的語法撰寫 學習資料結構與演算法 最好的練習就是實際克服困難的題目 這學期的範圍 德明科技大學資訊科技系

程式的組成 資料：在程式中以變數的型態出現，每個變數都在記憶體有一席之地，包含 程序：即if、loop等程式語法與流程 變數型態：決定所佔記憶體的長度 變數值：實際的變數資料值 變數位址：系統處理 程序：即if、loop等程式語法與流程 I/O：輸入與輸出，如scanf與printf 輸入  處理  輸出 德明科技大學資訊科技系

練習 請撰寫一個程式，可以顯示九九乘法表 以兩層迴圈方式處理 先能夠顯示正確結果，才思考如何排的漂亮 先示範… 德明科技大學資訊科技系

資料與資訊 p1-2 資料 是客觀存在的、具體的、事實的記錄 資訊 經過資料處理之後的結果即為資訊 資料 資訊 德明科技大學資訊科技系

資料結構的概念 當我們解決問題時，還沒開始實際寫程式，必須先規劃程式如何撰寫 有效率的程式 = 資料結構 + 演算法 I/O：輸入輸出的格式與資料內容 程序：處理的方法(演算法) 資料：決定此問題會用到那些類型的資料 有效率的程式 = 資料結構 + 演算法 所謂的資料結構，就是針對一個問題，決定如何設計資料部份，尤其是適合此問題的特殊資料類型 資料在記憶體中的儲存方式 德明科技大學資訊科技系

資料結構的概念 在任何問題中，資料元素都不是孤立存在，彼此之間存在某些邏輯關係，這種關係可稱為結構(structure)，種類有 集合：元素間沒有次序性 線性結構：陣列、串列、佇列、堆疊 樹狀結構 圖形結構 德明科技大學資訊科技系

範例說明 p1-5 寫一個程式計算五個同學的平均成績 德明科技大學資訊科技系

演算法的五原則 演算法(Algorithm): 解決問題的方法 輸入(Input) 輸出(Output) 明確性(Definiteness) 不一定要有輸入。可能沒有，也可能是多個資料輸入。 例如(1)：取得系統目前的時間，不須要輸入，只要寫一行now()函數， 就可以輸出系統時間 例如(2)：求某數為奇偶數時，則必須先要有一個整數輸入，才能運算 輸出(Output) 至少要有一個輸出 明確性(Definiteness) 每一行指令都必須明確，不可模稜兩可 「用功的學生才能領獎學金」就不具有明確性，因為每一個人對用功的定義可能不盡相同。而如果改為「成績90以上的學生才能領獎學金」就是具有明確性，因為90分是一個比較客觀的定義。 德明科技大學資訊科技系

演算法的五原則 有限性(Finiteness) 正確性(Correctness) 演算法不能有無窮迴路，必須能終止執行 由於演算法並非是真正可以執行的程式，而是設計者所推演出解決問題的步驟，因此，必須在有限的步驟內要完成解決問題的程序 真正的程式是可以有無窮迴路的動作 正確性(Correctness) 既然演算法是解決問題的方法，因此正確性是最基本的要求 德明科技大學資訊科技系

演算法的範例 演算法: 一組可用來解決特定問題的有限指令或步驟 依循這些指令或步驟，可以完成工作 案例: 做蛋糕 德明科技大學資訊科技系

演算法的範例 好吃的蛋糕怎麼來? 輸　入 明確性 有限性 輸　出 正確性 德明科技大學資訊科技系

描述演算法的三種方法 文字 採用口語化的文字敘述來加以描述，容易冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較不常用 p1-10 文字 採用口語化的文字敘述來加以描述，容易冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較不常用 例如：請利用「文字敘述」使用者登入帳號與密碼時，系統檢查的過程。 步驟一：輸入使用者帳號與密碼 步驟二：判斷帳號與密碼是否正確 步驟三：如果正確時，則可以登入系統 否則，就無法登入！ 德明科技大學資訊科技系

描述演算法的三種方法 流程圖 利用圖形方式來表達欲解決問題的步驟 德明科技大學資訊科技系

描述演算法的三種方法 虛擬碼 使用文字摻雜程式語言，來描述解題步驟與方法 兼具文字描述及流程圖的優點 //登錄帳號密碼的檢查 (1)Input: UserName, Password (2)IF (UserName And Password) ALL True Output: You Can Pass! else Output: You Can not Pass! //計算1+2+3+…+10 (1)設Count=1,Total=0; (2)Total=Total+Count; (3)Count=Count+1; (4)若Count > 10 則至步驟(5)，否則回步驟(2) (5)印出Total 不是可以執行的指令 只是說明程式處理的流程 德明科技大學資訊科技系

程式設計概念 p1-14 德明科技大學資訊科技系

程式設計概念 德明科技大學資訊科技系

程式設計概念 系統發展的生命週期與程式設計之步驟比較 德明科技大學資訊科技系

程式設計範例 題目 計算國文與英文的平均成績，並依照平均成績來求顯示「及格」與「不及格」 1.分析及定義問題。 兩個等級分別如下： (1)及格：60(含)以上。 (2)不及格：60以下。 2.畫出整合問題的流程圖或撰寫問題的演算法 德明科技大學資訊科技系

4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止 3.撰寫及建立程式模組 4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止 當使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績為60.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態改為float(浮點數) 德明科技大學資訊科技系

結構化程式設計 利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組 強調任何程式邏輯均可由三種結構組成 p1-18 利用「由上而下」的技巧，將程式分解成多個具有獨立功能的模組 強調任何程式邏輯均可由三種結構組成 循序(Sequence)：簡單命令式的指令 如X=Y+Z 選擇(Condition)：做決策使用 if-then-else select case / switch 重複(Repetition)：重複執行 do-while do-until for 循序 選擇 德明科技大學資訊科技系 重複

演算法、資料結構、程式 演算法 資料結構 程式 整個問題的解決方法，以邏輯方式描述 以文字、或虛擬碼方式，撰寫整個程式的流程 可對應到程式的撰寫，但是與程式語言的選擇無關 資料結構 要解決問題時所需要的資料，以及資料彼此之間的關連與結構 著重在資料的表現、資料之間的結構關係 程式 實際可以執行 真實的解決問題，以符合程式語言的規範完成 不同程式語言有不同的撰寫方法，但是彼此的基本概念卻很相似 德明科技大學資訊科技系

演算法、資料結構、程式 在討論問題的解決方案時，大多以演算法搭配資料結構為溝通的工具 程式撰寫是基本的技能，更進階的是 有效率的演算法 直接以程式語言討論太過於瑣碎 程式撰寫是基本的技能，更進階的是 針對特定問題採用適當的資料結構 設計有效率的演算法解決所面對的問題 有效率的演算法 用較少的記憶體空間完成處理同一個問題 用較少的執行時間完成處理同一個問題 德明科技大學資訊科技系

演算法的時間效率 程式的執行速度受到哪些因素影響 演算法的設計並不考慮程式語言與硬體架構，因此以指令數量為評估效率的主要依據 p1-22 程式的執行速度受到哪些因素影響 程式需要執行的指令數量 CPU的速度 電腦架構例如記憶體大小等 其他例如編譯程式的效率等 演算法的設計並不考慮程式語言與硬體架構，因此以指令數量為評估效率的主要依據 Q: 怎麼計算一個演算法的指令數量 基本上是無法精確計算需要之指令數量，why? 那該怎麼評估一個演算法所需的指令數量 德明科技大學資訊科技系

程式中指令數目的計算 循序結構(一般指令) 決策分支結構(if) 重複結構(loop) 例如: x=x+1 每個指令執行一次 決策分支結構(if) 例如: if (x>1) then ... 只有條件為正時才會執行 重複結構(loop) 例如: for i=1 to 100 迴圈內的指令重複100次 真正計算指令數量有困難，但是從以上三個結構來看，顯然迴圈內的執行數量是重點 Q: 計算下列程式中變數Count被執行的次數為何 德明科技大學資訊科技系

迴圈敘述的頻率計數 1. 先根據「迴圈計數器」的範圍算出迴圈重複的次數 2. 再乘上迴圈內的行數。 下列的程式片段，計算10組整數除法的商數及餘數 1. For i = 0 To 9 2. Q = m[i] / n[i] 3. R = m[i] Mod n[i] ; 4. Console.WriteLine(“{0} / {1} = {2} … {3}”, m[i], n[i], Q, R) 5. Next 迴圈重複的次數為10次，迴圈內有3個敘述，因此第2行到第4行（迴圈的主體）的頻率計數為30 ( = 10  3 )。 第1行for迴圈的頭會執行11次，前10次造成迴圈主體的重複執行，第11次發現條件不符而離開迴圈。 因此整個迴圈（迴圈的頭加上迴圈的主體）的頻率計數為41 ( = 11 + 30 )。 德明科技大學資訊科技系

【舉例1】 假設有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加，請問程式的執行次數為何？ 【解析】行號04會執行n+1次，而前n次會執行迴圈主體，但是在第n+1次時沒有符合迴圈的條件，故離開迴圈。 德明科技大學資訊科技系

【舉例2】 假設兩矩陣a, b相加，並且矩陣大小皆為n*n，請計算出下列程式的執行次數？ 【解析】行號04外層迴圈(for)的計數器i從0~n-1，共會執行n+1次，而行號05內層迴圈(for)的計數器j從0~n-1，也會執行n+1次。因此，當外層迴圈執行1次時，則內層迴圈要執行一回合，也就是j從0~n-1(共有n次) 德明科技大學資訊科技系

【舉例3】 假設兩矩陣a, b相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執行次數 德明科技大學資訊科技系

雙層迴圈、內圈不固定次數 2 For j = i+1 To n 3 result += 1 4 Next 5 Next 1          For i = 1 To n 2 For j = i+1 To n 3 result += 1 4 Next 5 Next 由於內圈迴圈計數器 j 的範圍，是隨著外圈迴圈計數器 i 的範圍改變的，因此我們針對迴圈計數器 i 的變化來分析： 德明科技大學資訊科技系

總次數 ＝ (n-1) + (n-2) + … + 1 = n * ( n-1 ) / 2 i 的值 j 的範圍 第3行執行次數 1 2 …… n n-1 2 3 …… n n-2 3 4 …… n n-3 …   n …… n n n+1 …… n 總次數 ＝ (n-1) + (n-2) + … + 1 = n * ( n-1 ) / 2 數學式： 總次數 ＝ = = = n2 – = 德明科技大學資訊科技系

範例：計算 n 階乘 ( n! ) 的函式 1 Function factor( ByVal n As Integer) As Integer 2 Dim i, result As Integer 3               result = 1 4               i = 1 5               Do while i < = n 6                 result = result * i ; 7                  i += 1 ; 8                Loop 9                Return result 10 End Function 德明科技大學資訊科技系

我們計算每一行敘述被執行的次數： 多1次為最後一次比較條件不成立 行號 n>0 時 n <= 0 時 1 2 3 n+1 5 n 6 8 總次數 3n+4 4 多1次為最後一次比較條件不成立   如果 n>0，頻率計數為 3n+4次，如果 n <= 0 ，頻率計數為 4次 如果更複雜的程式，似乎很難真的計算出指令的數量 仔細觀察，3n+4的值重點在n是多少，當n很大時，4其實不重要 一般計算時，主要依據 n 的狀況，也就是迴圈的層次 德明科技大學資訊科技系

Big-O Big-O符號的數學定義為：若且唯若 f(n) = O(g(n)) 則存在大於 0 的常數 c 和 n0，使得對所有的 n 值，當n ≧ n0 時，f(n) ≦ c * g(n) 均成立。 用數學式表示為： f(n) = O(g(n))   c, n0>0   n≧ n0 , f (n) ≦ c * g(n) 用口語解釋為：f(n) 取Big-O符號為O( g(n))，當 n 夠大的時候，g(n)相當 於是f(n)的上限  用圖示可表達為：   c*g(n) f(n) n n0 德明科技大學資訊科技系

◎ 9 n2 + 6nlgn + 9 = O( n2 ) ，因為n2 的次數最大，取最高次項而不計係數時，自然取到n2 ◎ 5n2 + 6n + 9 ＝ O( n2 ) → f( n ) = 5n2 + 6n + 9, g( n ) = n2 → f 函數取Big-O符號為 g函數 →5n2 + 6n + 9 取 Big-O 符號為 O( n2 ) ◎ 3n lgn + 9n + 10 = O( nlgn ) ，因為 n lgn 的次數比n 大，取最高次項而不計係數時，自然取到 n lgn (lg n = log2n) ◎ 9 n2 + 6nlgn + 9 = O( n2 ) ，因為n2 的次數最大，取最高次項而不計係數時，自然取到n2 ◎ 19n3 + 9 n2 + 6n+ 9 = O( n3 ) ，因為n3 的次數最大，取最高次項而不計係數時，自然取到 n3 德明科技大學資訊科技系

德明科技大學資訊科技系

將各種複雜度隨n值變化的結果繪成圖表，以便了解複雜度對程式效能的影響有多大：( X軸代表n值的成長，Y軸代表g(n)值的成長 ) 25 210 215 220 225 230 n3 n2 nlgn n lgn 1 2 4 8 16 32 64 128 德明科技大學資訊科技系