Data Structure资料结构ppt课件.pptVIP

Data Structure資料結構 副教授 翁志祁 義0321(星期三: 02-04) 課程簡介 本課程在使同學瞭解各種資料結構，如Stacks, Queues, Linked Lists, Trees, Hash, Graph等。 並使同學熟悉對這些資料結構的搜尋、讀寫 、插入、刪除的演算法(algorithm)。更重要的是使學生在利用這些資料結構及演算法解決問題時，同時能夠評估記憶體使用空間和執行時間的複雜度(Complexity)。最終目標是要讓同學能根據問題，選擇適當的資料結構及演算法，正確地、且有效率地去解決問題。 參考書籍與教學網站 Data Structures and Program Design in C,Kruse, Tondo, Leung, 全華圖書,2597-1300x338 資料結構使用C語言，吳勁樺著. 金禾資訊(02)2789-0561 本課程教材可至下列網址下載: .tw/~cweng/ 因為教材內容正在陸續的更新中，所以只需下載最近要用到的章節。 成績比重和輔導時間 期中考試 30% 期末考試 40% 平時成績 30%(含出席、作業、測驗) 星期一12:00~13:00 星期二14:00~16:00 星期三12:00~13:00 星期四15:00~17:00 第一章 資料結構導論本章重點 認識資料與資訊 演算法(Algorithm) 程式(program)與程式設計(programming) 演算法的效能分析 1. 認識資料與資訊 資料(Data)，指的就是一種未經處理的原始文字(Word)、數字(Number)、符號(Symbol)或圖形(Graph)等，它所表達出來的只是一種沒有評估價值的基本原素或項目。例如姓名或我們常看到的課表、通訊錄等等都可泛稱是一種「資料」。 資料處理 「資料處理」就是用人力或機器設備，對資料進行有系統的整理如記錄、排序、合併、整合、計算、統計等，以使原始的「資料」符合需求，而成為有用的「資訊」(Information) 資料結構 資料結構是在資料處理過程中，一種分析、組織資料的方法(algorithm)與邏輯(logic)。它考慮到了資料間的特性與相互關係(relationship)。 程式設計師必須選擇一種資料結構來進行資料的新增、修改、刪除、儲存等動作，如果在選擇資料結構時作了錯誤的決定，那程式執行起來的速度將可能變得非常沒有效率 。 資料和資訊的角色是否一成不變 不一定。同一份文件可能在某種況下為資料，而在另一種狀況下則為資訊。 例如美伊戰爭的戰役死傷人數報告，對你我這些平民百姓而言，當然只是一份不痛不癢的「資料」(Data)；不過對於英美聯軍指揮官而言，這份報份可就是彌足珍貴的「資訊」(Information)。 2.演算法(Algorithm) 資料結構加上演算法等於可執行程式。 「演算法」在韋氏辭典定義為：「在有限步驟內解決數學問題的程序。」 在計算機領域可以把演算法定義成：「為了解決某一個工作或問題，所需要有限數目的機械性或重覆性指令與計算步驟。」 演算法五個條件 輸入(Input)：0個或多個輸入資料，這些輸入必需有清楚的描述或定義。 輸出(Output)：至少會有一個輸出結果，不可以沒有輸出結果。 明確性(Definiteness)：每一個指令或步驟必需是簡潔明確而不含糊的。 有限性(Finiteness)：在有限的步驟後一定會結束，不會產生無窮迴路。 有效性(Effectiveness)：步驟清楚且可行，能讓使用者用紙筆計算而求出答案。 演算法常用的表現方法 一般文字：中文、英文、數字等。 虛擬語言：接近高階程式語言的寫法，經常使用的有SPARKS、PASCA-LIKE等語言。 表格或圖形：如陣列、樹狀圖、矩陣圖等。 流程圖：資料流程圖)及控制流程圖可以算是一種通用的表示法，也有固定的圖型符號。 程序語言：目前資料結構的演算法經常是以可讀性高的高階語言來表示，例如C語言、C++語言、Java語言、Visual Basic語言等，在本書中將以C語言來表達演算法 演算法、程式、與流程圖的異同 演算法和程序是有所區別，因為程式不一定要滿足有限性的要求，如作業系統或機器上的運作程式；除非當機，否則永遠在等待迴路(waiting loop)或記錄機器運作狀況，這也違反了演算法五大原則之一的「有限性」。 只要是演算法都能夠利用程式流程圖表現，但因為程式流程圖可包含無窮迴路，所以無法利用演算法來表達。 3. 程式(program)與程式設計(programming) 程式產生的五個階段: 需求認識：了解程式所要解決的問題是什麼，有那些輸入及輸出等。 設計規劃：根據需求，選擇適合的資料結構，並以任何的表示