资料结构导论课件.ppt

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課程內容 資料結構與演算法 遞迴 Recursion 陣列 Array 堆疊 Stack 佇列 Queue

2、 鏈結串列 Linked List 樹狀結構 Tree Structure 圖形 Graph Structure 排序 Sorting 搜尋 Search.5修課基礎 程式撰寫 對於變數、函數、陣列等基本程式語言的使用與掌握 對於一個問題，可以在找出解決方法之後，撰寫出程式碼 具備邏輯概念 學習程式除了語法的熟悉外，最重要的是邏輯概念的訓練，才有能力學習其他語言 還無法順利掌握程式撰寫?以資料結構這門課程為程式設計的進階訓練 程式設計能力的再次訓練.6上課方式 投影片展示，請自行搭配課本閱讀 實例練習 在課程中會搭配一些程式範例，讓同學實際操作程式之撰寫，以掌握程式撰寫的能力 作業練習 每一段

3、時間，會有一完整的題目要求撰寫程式，計入平時成績內 期中、期末考試.7學習程式 入門 學習VB、Dev C+等軟體的使用 熟悉VB、C的語法撰寫 進階 學習資料結構與演算法 深入 最好的練習就是實際克服困難的題目這學期的範圍.8程式的組成 資料：在程式中以變數的型態出現，每個變數都在記憶體有一席之地，包含 變數型態：決定所佔記憶體的長度 變數值：實際的變數資料值 變數位址：系統處理 程序：即if、loop等程式語法與流程 I/O：輸入與輸出，如scanf與printf輸入輸入 處理處理 輸出輸出.9練習 請撰寫一個程式，可以顯示九九乘法表 以兩層迴圈方式處理 先能夠顯示正確結果，才思考如何排的

4、漂亮 先示範.10資料與資訊 資料 是客觀存在的、具體的、事實的記錄 資訊 經過資料處理之後的結果即為資訊資資料料資資訊訊p1-2.11資料結構的概念 當我們解決問題時，還沒開始實際寫程式，必須先規劃程式如何撰寫 I/O：輸入輸出的格式與資料內容 程序：處理的方法(演算法)資料：決定此問題會用到那些類型的資料 有效率的程式有效率的程式=資料結構資料結構+演算法演算法 所謂的資料結構，就是針對一個問題，所謂的資料結構，就是針對一個問題，決定如何設計資料部份，尤其是適合此決定如何設計資料部份，尤其是適合此問題的特殊資料類型問題的特殊資料類型 資料在記憶體中的儲存方式.12資料結構的概念 在任何問題

5、中，資料元素都不是孤立存在，彼此之間存在某些邏輯關係，這種關係可稱為結構(structure)，種類有 集合：元素間沒有次序性 線性結構：陣列、串列、佇列、堆疊 樹狀結構 圖形結構.13範例說明 寫一個程式計算五個同學的平均成績p1-5.14演算法的五原則演算法(Algorithm):解決問題的方法輸入輸入(Input)1.不一定要有輸入。可能沒有，也可能是多個資料輸入。p1-7例如(1)：取得系統目前的時間，不須要輸入，只要寫一行now()函數，就可以輸出系統時間例如(2)：求某數為奇偶數時，則必須先要有一個整數輸入，才能運算輸出輸出(Output)至少要有一個輸出明確性明確性(Defini

6、teness)每一行指令都必須明確，不可模稜兩可 用功的學生才能領獎學金就不具有明確性，因為每一個人對用功的定義可能不盡相同。而如果改為成績90以上的學生才能領獎學金就是具有明確性，因為90分是一個比較客觀的定義。.15演算法的五原則 有限性有限性(Finiteness)演算法不能有無窮迴路，必須能終止執行由於演算法並非是真正可以執行的程式，而是設計者所推演出解決問題的步驟，因此，必須在有限的步驟內要完成解決問題的程序真正的程式是可以有無窮迴路的動作 正確性正確性(Correctness)既然演算法是解決問題的方法，因此正確性是最基本的要求.16演算法的範例 演算法:一組可用來解決特定問題的有

7、限指令或步驟 依循這些指令或步驟，可以完成工作 案例:做蛋糕.17演算法的範例 好吃的蛋糕怎麼來?.18描述演算法的三種方法 文字 採用口語化的文字敘述來加以描述，容易冗長且較不精確，在撰寫、閱讀、會意時可能會有誤差，因此一般較不常用p1-10例如：請利用文字敘述使用者登入帳號與密碼時，系統檢查的過程。步驟一：輸入使用者帳號與密碼步驟二：判斷帳號與密碼是否正確步驟三：如果正確時，則可以登入系統 否則，就無法登入！.19描述演算法的三種方法 流程圖 利用圖形方式來表達欲解決問題的步驟.20描述演算法的三種方法 虛擬碼 使用文字摻雜程式語言，來描述解題步驟與方法 兼具文字描述及流程圖的優點/登錄帳

8、號密碼的檢查登錄帳號密碼的檢查(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不是可以執行的指令不是可以執行的指令只是說明程式處理的流程只是說明程式處理的流程.21程式設計概念p1-14.22程式設計概念

9、.23程式設計概念 系統發展的生命週期與程式設計之步驟比較.24程式設計範例 題目 計算國文與英文的平均成績，並依照平均成績來求顯示及格與不及格1.分析及定義問題。兩個等級分別如下：(1)及格：60(含)以上。(2)不及格：60以下。2.畫出整合問題的流程圖或撰寫問題的演算法.253.撰寫及建立程式模組4.對每一個程式模組進行測試及除錯，直到沒有錯誤為止當使用者輸入國文為60分，英文為61分時，是否可以計算出平均成績為60.5，如果沒有則必須要進行除錯，亦即要將Average的資料型態改為float(浮點數).26結構化程式設計 利用由上而下的技巧，將程式分解成多個具有獨立功能的模組 強調任何

10、程式邏輯均可由三種結構組成 循序(Sequence)：簡單命令式的指令 如X=Y+Z 選擇(Condition)：做決策使用 if-then-else select case/switch 重複(Repetition)：重複執行 do-while do-until for p1-18循序循序選擇選擇重複重複.27演算法、資料結構、程式 演算法 整個問題的解決方法，以邏輯方式描述 以文字、或虛擬碼方式，撰寫整個程式的流程 可對應到程式的撰寫，但是與程式語言的選擇無關 資料結構 要解決問題時所需要的資料，以及資料彼此之間的關連與結構 著重在資料的表現、資料之間的結構關係 程式 實際可以執行 真實的

11、解決問題，以符合程式語言的規範完成 不同程式語言有不同的撰寫方法，但是彼此的基本概念卻很相似.28演算法、資料結構、程式 在討論問題的解決方案時，大多以演算法搭配資料結構為溝通的工具 直接以程式語言討論太過於瑣碎 程式撰寫是基本的技能，更進階的是 針對特定問題採用適當的資料結構 設計有效率的演算法解決所面對的問題 有效率的演算法 用較少的記憶體空間記憶體空間完成處理同一個問題 用較少的執行時間執行時間完成處理同一個問題.29演算法的時間效率 程式的執行速度受到哪些因素影響 程式需要執行的指令數量 CPU的速度 電腦架構例如記憶體大小等 其他例如編譯程式的效率等 演算法的設計並不考慮程式語言與硬

12、體架構，因此以指令數量指令數量為評估效率的主要依據 Q:怎麼計算一個演算法的指令數量 基本上是無法精確計算需要之指令數量，why?那該怎麼評估一個演算法所需的指令數量p1-22.30程式中指令數目的計算循序結構(一般指令)例如:x=x+1 每個指令執行一次決策分支結構(if)例如:if(x1)then.只有條件為正時才會執行重複結構(loop)例如:for i=1 to 100 迴圈內的指令重複100次真正計算指令數量有困難，但是從以上三個結構來看，顯然迴圈顯然迴圈內的執行數量是重點內的執行數量是重點Q:計算下列程式中變數Count被執行的次數為何.31迴圈敘述的頻率計數1.先根據迴圈計數器的

13、範圍算出迴圈重複的次數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【舉例1】假設有一陣列a，其陣列的大小為n，如果要將陣列

14、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相乘，並且矩陣大小皆為n*n，相加請計算出下列程式的執行次數.35雙層迴圈、內圈不固定次數雙層迴圈、內圈不固定

15、次數 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(=niin1)(=n2 2)1(nn=2)1(nn.37範例範例：計算計算 n n 階乘階乘 (n!)(n!)的函式的函式 1 Function

16、 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 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