资料结构导论PPT课件

1 資料結構DataStructure chapter1 2 課程資訊 Lecturer 江政杰Office 四合院301URL nas takming edu tw plutoMail pluto mail takming edu tw課程網頁URL nas takming edu tw pluto ds ds html教材 補充資訊作業相關連結 3 課程資訊 TextBook 資料結構 使用C語言李春雄著上奇出版社成績評量期中 期末各佔30 平時成績佔40 4 課程內容 資料結構與演算法遞迴Recursion陣列Array堆疊Stack佇列Queue鏈結串列LinkedList樹狀結構TreeStructure圖形GraphStructure排序Sorting搜尋Search 5 修課基礎 程式撰寫對於變數 函數 陣列等基本程式語言的使用與掌握對於一個問題 可以在找出解決方法之後 撰寫出程式碼具備邏輯概念學習程式除了語法的熟悉外 最重要的是邏輯概念的訓練 才有能力學習其他語言還無法順利掌握程式撰寫 以資料結構這門課程為程式設計的進階訓練程式設計能力的再次訓練 6 上課方式 投影片展示 請自行搭配課本閱讀實例練習在課程中會搭配一些程式範例 讓同學實際操作程式之撰寫 以掌握程式撰寫的能力作業練習每一段時間 會有一完整的題目要求撰寫程式 計入平時成績內期中 期末考試 7 學習程式 入門學習VB DevC 等軟體的使用熟悉VB C的語法撰寫進階學習資料結構與演算法深入最好的練習就是實際克服困難的題目 8 程式的組成 資料 在程式中以變數的型態出現 每個變數都在記憶體有一席之地 包含變數型態 決定所佔記憶體的長度變數值 實際的變數資料值變數位址 系統處理程序 即if loop等程式語法與流程I O 輸入與輸出 如scanf與printf 輸入 處理 輸出 9 練習 請撰寫一個程式 可以顯示九九乘法表以兩層迴圈方式處理先能夠顯示正確結果 才思考如何排的漂亮先示範 10 資料與資訊 資料是客觀存在的 具體的 事實的記錄資訊經過資料處理之後的結果即為資訊 p1 2 11 資料結構的概念 當我們解決問題時 還沒開始實際寫程式 必須先規劃程式如何撰寫I O 輸入輸出的格式與資料內容程序 處理的方法 演算法 資料 決定此問題會用到那些類型的資料有效率的程式 資料結構 演算法所謂的資料結構 就是針對一個問題 決定如何設計資料部份 尤其是適合此問題的特殊資料類型資料在記憶體中的儲存方式 12 資料結構的概念 在任何問題中 資料元素都不是孤立存在 彼此之間存在某些邏輯關係 這種關係可稱為結構 structure 種類有集合 元素間沒有次序性線性結構 陣列 串列 佇列 堆疊樹狀結構圖形結構 13 範例說明 寫一個程式計算五個同學的平均成績 p1 5 14 演算法的五原則 演算法 Algorithm 解決問題的方法輸入 Input 不一定要有輸入 可能沒有 也可能是多個資料輸入 p1 7 例如 1 取得系統目前的時間 不須要輸入 只要寫一行now 函數 就可以輸出系統時間例如 2 求某數為奇偶數時 則必須先要有一個整數輸入 才能運算 輸出 Output 至少要有一個輸出明確性 Definiteness 每一行指令都必須明確 不可模稜兩可 用功的學生才能領獎學金 就不具有明確性 因為每一個人對用功的定義可能不盡相同 而如果改為 成績90以上的學生才能領獎學金 就是具有明確性 因為90分是一個比較客觀的定義 15 演算法的五原則 有限性 Finiteness 演算法不能有無窮迴路 必須能終止執行由於演算法並非是真正可以執行的程式 而是設計者所推演出解決問題的步驟 因此 必須在有限的步驟內要完成解決問題的程序真正的程式是可以有無窮迴路的動作正確性 Correctness 既然演算法是解決問題的方法 因此正確性是最基本的要求 16 演算法的範例 演算法 一組可用來解決特定問題的有限指令或步驟依循這些指令或步驟 可以完成工作案例 做蛋糕 17 演算法的範例 好吃的蛋糕怎麼來 輸入 輸出 明確性 正確性 有限性 18 描述演算法的三種方法 文字採用口語化的文字敘述來加以描述 容易冗長且較不精確 在撰寫 閱讀 會意時可能會有誤差 因此一般較不常用 p1 10 例如 請利用 文字敘述 使用者登入帳號與密碼時 系統檢查的過程 步驟一 輸入使用者帳號與密碼步驟二 判斷帳號與密碼是否正確步驟三 如果正確時 則可以登入系統否則 就無法登入 19 描述演算法的三種方法 流程圖利用圖形方式來表達欲解決問題的步驟 20 描述演算法的三種方法 虛擬碼使用文字摻雜程式語言 來描述解題步驟與方法兼具文字描述及流程圖的優點 登錄帳號密碼的檢查 1 Input UserName Password 2 IF UserNameAndPassword ALLTrueOutput YouCanPass elseOutput YouCannotPass 計算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 程式設計範例 題目計算國文與英文的平均成績 並依照平均成績來求顯示 及格 與 不及格 1 分析及定義問題 兩個等級分別如下 1 及格 60 含 以上 2 不及格 60以下 2 畫出整合問題的流程圖或撰寫問題的演算法 25 3 撰寫及建立程式模組 4 對每一個程式模組進行測試及除錯 直到沒有錯誤為止當使用者輸入國文為60分 英文為61分時 是否可以計算出平均成績為60 5 如果沒有則必須要進行除錯 亦即要將Average的資料型態改為float 浮點數 26 結構化程式設計 利用 由上而下 的技巧 將程式分解成多個具有獨立功能的模組強調任何程式邏輯均可由三種結構組成循序 Sequence 簡單命令式的指令如X Y Z選擇 Condition 做決策使用if then elseselectcase switch重複 Repetition 重複執行do whiledo untilfor p1 18 循序 選擇 重複 27 演算法 資料結構 程式 演算法整個問題的解決方法 以邏輯方式描述以文字 或虛擬碼方式 撰寫整個程式的流程可對應到程式的撰寫 但是與程式語言的選擇無關資料結構要解決問題時所需要的資料 以及資料彼此之間的關連與結構著重在資料的表現 資料之間的結構關係程式實際可以執行真實的解決問題 以符合程式語言的規範完成不同程式語言有不同的撰寫方法 但是彼此的基本概念卻很相似 28 演算法 資料結構 程式 在討論問題的解決方案時 大多以演算法搭配資料結構為溝通的工具直接以程式語言討論太過於瑣碎程式撰寫是基本的技能 更進階的是針對特定問題採用適當的資料結構設計有效率的演算法解決所面對的問題有效率的演算法用較少的記憶體空間完成處理同一個問題用較少的執行時間完成處理同一個問題 29 演算法的時間效率 程式的執行速度受到哪些因素影響程式需要執行的指令數量CPU的速度電腦架構例如記憶體大小等其他例如編譯程式的效率等演算法的設計並不考慮程式語言與硬體架構 因此以指令數量為評估效率的主要依據Q 怎麼計算一個演算法的指令數量基本上是無法精確計算需要之指令數量 why 那該怎麼評估一個演算法所需的指令數量 p1 22 30 程式中指令數目的計算 循序結構 一般指令 例如 x x 1每個指令執行一次決策分支結構 if 例如 if x 1 then 只有條件為正時才會執行重複結構 loop 例如 fori 1to100迴圈內的指令重複100次真正計算指令數量有困難 但是從以上三個結構來看 顯然迴圈內的執行數量是重點 Q 計算下列程式中變數Count被執行的次數為何 31 迴圈敘述的頻率計數 1 先根據 迴圈計數器 的範圍算出迴圈重複的次數2 再乘上迴圈內的行數 下列的程式片段 計算10組整數除法的商數及餘數1 Fori 0To92 Q m i n i 3 R m i Modn 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 32 舉例1 假設有一陣列a 其陣列的大小為n 如果要將陣列a的元素相加 請問程式的執行次數為何 解析 行號04會執行n 1次 而前n次會執行迴圈主體 但是在第n 1次時沒有符合迴圈的條件 故離開迴圈 33 舉例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次 34 舉例3 假設兩矩陣a b相乘 並且矩陣大小皆為n n 相加請計算出下列程式的執行次數 35 雙層迴圈 內圈不固定次數1Fori 1Ton2Forj i 1Ton3result 14Next5Next由於內圈迴圈計數器j的範圍 是隨著外圈迴圈計數器i的範圍改變的 因此我們針對迴圈計數器i的變化來分析 36 數學式 總次數 n2 37 範例 計算n階乘 n 的函式1Functionfactor ByValnAsInteger AsInteger2Dimi resultAsInteger3result 14i 15Dowhilei n6result result i 7i 1 8Loop9Returnresult10EndFunction 38 我們計算每一行敘述被執行的次數 如果n 0 頻率計數為3n 4次 如果n 0 頻率計數為4次 多1次為最後一次比較條件不成立 如果更複雜的程式 似乎很難真的計算出指令的數量 仔細觀察 3n 4的值重點在n是多少 當n很大時 4其實不重要一般計算時 主要依據n的狀況 也就是迴圈的層次 39 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 的上限 n n0 f 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 3nlgn 9n 10 O nlgn 因