1、德明科技大學資訊科技系1資料結構Data Structurechapter 1德明科技大學資訊科技系2課程資訊 Lecturer:江政杰 Office:四合院 301 URL:nas.takming.edu.tw/pluto Mail:plutomail.takming.edu.tw 課程網頁 URL:nas.takming.edu.tw/pluto/ds/ds.html 教材、補充資訊 作業 相關連結德明科技大學資訊科技系3課程資訊 Text Book:資料結構 使用C語言李春雄著 上奇出版社 成績評量 期中、期末各佔30%、平時成績佔40%德明科技大學資訊科技系4課程內容 資料結構與演算法
2、 遞迴 Recursion 陣列 Array 堆疊 Stack 佇列 Queue 鏈結串列 Linked List 樹狀結構 Tree Structure 圖形 Graph Structure 排序 Sorting 搜尋 Search德明科技大學資訊科技系5修課基礎 程式撰寫 對於變數、函數、陣列等基本程式語言的使用與掌握 對於一個問題，可以在找出解決方法之後，撰寫出程式碼 具備邏輯概念 學習程式除了語法的熟悉外，最重要的是邏輯概念的訓練，才有能力學習其他語言 還無法順利掌握程式撰寫?以資料結構這門課程為程式設計的進階訓練 程式設計能力的再次訓練德明科技大學資訊科技系6上課方式 投影片展示，請
3、自行搭配課本閱讀 實例練習 在課程中會搭配一些程式範例，讓同學實際操作程式之撰寫，以掌握程式撰寫的能力 作業練習 每一段時間，會有一完整的題目要求撰寫程式，計入平時成績內 期中、期末考試德明科技大學資訊科技系7學習程式 入門 學習VB、Dev C+等軟體的使用 熟悉VB、C的語法撰寫 進階 學習資料結構與演算法 深入 最好的練習就是實際克服困難的題目這學期的範圍德明科技大學資訊科技系8程式的組成 資料：在程式中以變數的型態出現，每個變數都在記憶體有一席之地，包含 變數型態：決定所佔記憶體的長度 變數值：實際的變數資料值 變數位址：系統處理 程序：即if、loop等程式語法與流程 I/O：輸入與
4、輸出，如scanf與printf輸入輸入 處理處理 輸出輸出德明科技大學資訊科技系9練習 請撰寫一個程式，可以顯示九九乘法表 以兩層迴圈方式處理 先能夠顯示正確結果，才思考如何排的漂亮 先示範德明科技大學資訊科技系10資料與資訊 資料 是客觀存在的、具體的、事實的記錄 資訊 經過資料處理之後的結果即為資訊資資料料資資訊訊p1-2德明科技大學資訊科技系11資料結構的概念 當我們解決問題時，還沒開始實際寫程式，必須先規劃程式如何撰寫 I/O：輸入輸出的格式與資料內容 程序：處理的方法(演算法)資料：決定此問題會用到那些類型的資料 有效率的程式有效率的程式=資料結構資料結構+演算法演算法 所謂的資料
5、結構，就是針對一個問題，所謂的資料結構，就是針對一個問題，決定如何設計資料部份，尤其是適合此決定如何設計資料部份，尤其是適合此問題的特殊資料類型問題的特殊資料類型 資料在記憶體中的儲存方式德明科技大學資訊科技系12資料結構的概念 在任何問題中，資料元素都不是孤立存在，彼此之間存在某些邏輯關係，這種關係可稱為結構(structure)，種類有 集合：元素間沒有次序性 線性結構：陣列、串列、佇列、堆疊 樹狀結構 圖形結構德明科技大學資訊科技系13範例說明 寫一個程式計算五個同學的平均成績p1-5德明科技大學資訊科技系14演算法的五原則演算法(Algorithm):解決問題的方法1.輸入輸入(Inp
6、ut)不一定要有輸入。可能沒有，也可能是多個資料輸入。p1-7例如(1)：取得系統目前的時間，不須要輸入，只要寫一行now()函數，就可以輸出系統時間例如(2)：求某數為奇偶數時，則必須先要有一個整數輸入，才能運算2.輸出輸出(Output)至少要有一個輸出3.明確性明確性(Definiteness)每一行指令都必須明確，不可模稜兩可 用功的學生才能領獎學金就不具有明確性，因為每一個人對用功的定義可能不盡相同。而如果改為成績90以上的學生才能領獎學金就是具有明確性，因為90分是一個比較客觀的定義。德明科技大學資訊科技系15演算法的五原則4.有限性有限性(Finiteness)演算法不能有無窮迴
7、路，必須能終止執行由於演算法並非是真正可以執行的程式，而是設計者所推演出解決問題的步驟，因此，必須在有限的步驟內要完成解決問題的程序真正的程式是可以有無窮迴路的動作5.正確性正確性(Correctness)既然演算法是解決問題的方法，因此正確性是最基本的要求德明科技大學資訊科技系16演算法的範例 演算法:一組可用來解決特定問題的有限指令或步驟 依循這些指令或步驟，可以完成工作 案例:做蛋糕德明科技大學資訊科技系17演算法的範例 好吃的蛋糕怎麼來?德明科技大學資訊科技系18描述演算法的三種方法 文字 採用口語化的文字敘述來加以描述，容易冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較
8、不常用p1-10例如：請利用文字敘述使用者登入帳號與密碼時，系統檢查的過程。步驟一：輸入使用者帳號與密碼步驟二：判斷帳號與密碼是否正確步驟三：如果正確時，則可以登入系統 否則，就無法登入！德明科技大學資訊科技系19描述演算法的三種方法 流程圖 利用圖形方式來表達欲解決問題的步驟德明科技大學資訊科技系20描述演算法的三種方法 虛擬碼 使用文字摻雜程式語言，來描述解題步驟與方法 兼具文字描述及流程圖的優點/登錄帳號密碼的檢查登錄帳號密碼的檢查(1)Input:UserName,Password(2)IF(UserName And Password)ALL True Output:You Can P
9、ass!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不是可以執行的指令不是可以執行的指令只是說明程式處理的流程只是說明程式處理的流程德明科技大學資訊科技系21程式設計概念p1-14德明科技大學資訊科技系22程式設計概念德明科技大學資訊科技系23程式設計概念 系統發展的生命週期與程式設計之步驟比較 德明科技大學資訊科技系24程式設計範例 題目 計算國文與英文的平均成
10、績，並依照平均成績來求顯示及格與不及格1.分析及定義問題。兩個等級分別如下：(1)及格：60(含)以上。(2)不及格：60以下。2.畫出整合問題的流程圖或撰寫問題的演算法德明科技大學資訊科技系253.撰寫及建立程式模組4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止當使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績為60.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態改為float(浮點數)德明科技大學資訊科技系26結構化程式設計 利用由上而下的技巧，將程式分解成多個具有獨立功能的模組 強調任何程式邏輯均可由三種結構組成 循序(Sequence)：簡單命令式的
11、指令 如X=Y+Z 選擇(Condition)：做決策使用 if-then-else select case/switch 重複(Repetition)：重複執行 do-while do-until for p1-18循序循序選擇選擇重複重複德明科技大學資訊科技系27演算法、資料結構、程式 演算法 整個問題的解決方法，以邏輯方式描述 以文字、或虛擬碼方式，撰寫整個程式的流程 可對應到程式的撰寫，但是與程式語言的選擇無關 資料結構 要解決問題時所需要的資料，以及資料彼此之間的關連與結構 著重在資料的表現、資料之間的結構關係 程式 實際可以執行 真實的解決問題，以符合程式語言的規範完成 不同程式語
12、言有不同的撰寫方法，但是彼此的基本概念卻很相似德明科技大學資訊科技系28演算法、資料結構、程式 在討論問題的解決方案時，大多以演算法搭配資料結構為溝通的工具 直接以程式語言討論太過於瑣碎 程式撰寫是基本的技能，更進階的是 針對特定問題採用適當的資料結構 設計有效率的演算法解決所面對的問題 有效率的演算法 用較少的記憶體空間記憶體空間完成處理同一個問題 用較少的執行時間執行時間完成處理同一個問題德明科技大學資訊科技系29演算法的時間效率 程式的執行速度受到哪些因素影響 程式需要執行的指令數量 CPU的速度 電腦架構例如記憶體大小等 其他例如編譯程式的效率等 演算法的設計並不考慮程式語言與硬體架構
13、，因此以指令數量指令數量為評估效率的主要依據 Q:怎麼計算一個演算法的指令數量 基本上是無法精確計算需要之指令數量，why?那該怎麼評估一個演算法所需的指令數量p1-22德明科技大學資訊科技系30程式中指令數目的計算循序結構(一般指令)例如:x=x+1 每個指令執行一次決策分支結構(if)例如:if(x1)then.只有條件為正時才會執行重複結構(loop)例如:for i=1 to 100 迴圈內的指令重複100次真正計算指令數量有困難，但是從以上三個結構來看，顯然迴圈顯然迴圈內的執行數量是重點內的執行數量是重點Q:計算下列程式中變數Count被執行的次數為何德明科技大學資訊科技系31迴圈敘
14、述的頻率計數1.先根據迴圈計數器的範圍算出迴圈重複的次數2.再乘上迴圈內的行數。下列的程式片段，計算10組整數除法的商數及餘數1.For i=0 To 9 2.Q=mi/ni 3.R=mi Mod ni;4.Console.WriteLine(“0/1=2 3”,mi,ni,Q,R)5.Next迴圈重複的次數為10次，迴圈內有3個敘述，因此第2行到第4行（迴圈的主體）的頻率計數為30(=10 3)。第1行for迴圈的頭會執行11次，前10次造成迴圈主體的重複執行，第11次發現條件不符而離開迴圈。因此整個迴圈（迴圈的頭加上迴圈的主體）的頻率計數為41(=11+30)。德明科技大學資訊科技系32【
15、舉例1】假設有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加，請問程式的執行次數為何？【解析】行號04會執行n+1次，而前n次會執行迴圈主體，但是在第n+1次時沒有符合迴圈的條件，故離開迴圈。德明科技大學資訊科技系33【舉例2】假設兩矩陣a,b相加，並且矩陣大小皆為n*n，請計算出下列程式的執行次數？【解析】行號04外層迴圈(for)的計數器i從0n-1，共會執行n+1次，而行號05內層迴圈(for)的計數器j從0n-1，也會執行n+1次。因此，當外層迴圈執行1次時，則內層迴圈要執行一回合，也就是j從0n-1(共有n次)德明科技大學資訊科技系34【舉例3】假設兩矩陣a,b相乘，並且矩陣大
16、小皆為n*n，相加請計算出下列程式的執行次數德明科技大學資訊科技系35雙層迴圈、內圈不固定次數雙層迴圈、內圈不固定次數 1 For i=1 To n 2For j=i+1 To n 3 result+=1 4 Next 5 Next 由於內圈迴圈計數器 j 的範圍，是隨著外圈迴圈計數器 i 的範圍改變的，因此我們針對迴圈計數器 i 的變化來分析：德明科技大學資訊科技系36數學式：總次數 i 的值j 的範圍第3行執行次數12 nn-123 nn-234 nn-3 n-1n n1nn+1 n0 總次數 (n-1)+(n-2)+1=n*(n-1)/2 ninij111=niin1)1)1(=niin
17、1)(=n2 2)1(nn=2)1(nn德明科技大學資訊科技系37範例範例：計算計算 n n 階乘階乘 (n!)(n!)的函式的函式 1 Function factor(ByVal n As Integer)As Integer2 Dim i,result As Integer3 result=1 4 i=1 5 Do while i 0 時n 0，頻率計數為 3n+4次，如果 n 0 n n0,f(n)c*g(n)用口語解釋為：f(n)取Big-O符號為O(g(n)，當 n 夠大的時候，g(n)相當 於是f(n)的上限上限 nn0f(n)c*g(n)用圖示可表達為：德明科技大學資訊科技系40
18、 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德明科技大學資訊科技系41德明科技大學資訊科技系422nn3n2nlgnnlgn1248163264128將各種複雜度隨n值變化的結果繪成圖表，以便了解複雜度對程式效能的影響有多大：(X軸代表n值的成長，Y軸代表g(n)值的成長)25210215220225230
