资料结构DataStructu.ppt
資料結構Data Structures,樹德科技大學九十五學年度第一學期 資訊管理系四技必修課程,http:/,課程資訊,課程代號:IMU088010109511 科目中文名稱:資料結構科目英文名稱:Data Structures開課班級:日間部四技二年級任課老師:余振國 博士(L0809,Tel:6158000Ext3008)學 分 數:3.0 學分 先修科目:Java程式設計、基礎數學 上課時間：Class A 15101700 Mon.13101400 Wed.Class B 11101200,13101500 Mon.上課地點：L0825 教室、電腦教室(四),教學目標:本課程要使學生瞭解電腦內資料的儲存方式，並對於資料如何被有效的應用、處理和維護，並提供評估方法。經由課程的介紹，使學生在設計程式時能夠有效地運用電腦資源。本課程以Java程式語言作為各式資料結構的範例解說以及實作練習。主要教材:資料結構理論使用Java/柯溫釗著，博碩文化)參考書籍：Data Structures and Algorithms in Java/2nd Ed.,M.T.Goodrich and R.Tamassia,John Wiley&Sons,Inc.,2001.Java程式語言/Ken Arnold 等著/吳宏信譯/碁峯Java在資料結構及演算法的應用/Robert Lafore 原著,胡銘珍編譯/全華科技圖書代理 教學評量:平時成績(含出席、作業及平時測驗)40%，期中考30%，期末考30%,課程規劃,資料結構作業(一),作業題：請以Java撰寫一程式，能在彈出視窗上分別建立不同框格，要求在框格內輸入你的名字、學號、班級，並在一空白框格內顯示：班級，學號，姓名，歡迎你來參加Java測試。範例:java/Welcome.java本作業請於九月二十四日前寄至 Note:e-mail之主旨請按四資管2A(B)學號姓名DS作業一填寫，附加檔案以Homework1_學號.java命名。請慎重，寄一次就好,資料結構的介紹,Chapter 1,資料結構簡介,e.g.功課表。成績單。火車時刻表。,何謂資料？就決策觀點而言，資料(Data)是一種不具評估價值的片段項目，適於人或電腦間溝通、解釋或處理的事實、觀念或指令。,資訊(Information)：資料經過有系統的整理，可以產生預期的結果。資料型態(Data Type)：定義程式變數的種類。結構化的資料型態(Structured Data Type)：許多相同資料型態的資料元素，依某種順序排列而成的資料型態。資料集(Data Object)：性質相類似的資料元素所組合而成的集合。,資料結構簡介,研究計算機如何儲存資料，如何結合這些資料，以及如何操作這些資料等問題。,資料結構探討的問題,資料結構簡介,演算法必須合乎下列條件：輸入。.輸出。.At least one result步驟明確。有限步驟。經濟有效。New Definition:以有限步驟求出正確的答案或預期的結果來解決問題，這些過程就是演算法,何謂演算法(Algorithm)？是指使用指令操縱計算機解決問題的方法。,資料結構簡介,需求。分析。設計。撰寫程式。驗證。,程式設計的產生步驟：,資料結構簡介,資料結構簡介,需求。分析。設計。撰寫程式。驗證。,程式設計的產生,資料結構簡介,需求。分析。分析方法由上而下結構化程式設計。由下而上。設計。撰寫程式。驗證。,程式設計的產生,資料結構簡介,需求。分析。設計。撰寫程式。驗證。,程式設計的產生,循序結構。重複結構。選擇結構。,結構化程式設計,資料結構簡介,優點程式撰寫是由上而下，程式易於連貫，邏輯清楚明確，容易了解。由上而下的程式維護容易，可以降低成本。缺點結構化程式設計指令較多，所須記憶體空間較大。結構化程式設計所佔的記憶體空間較大，因此，程式執行的時間較長。,結構化程式設計,資料結構簡介,資料結構簡介,好的程式符合以下條件：程式執行能得到正確的結果程式執行的時間短程式資源分配的效率高程式佔用記憶體空間少,資料結構簡介,需求。分析。設計。撰寫程式。驗證。,程式設計的產生,好的演算法必備特性：能正確地處理問題的需求 能完整地考慮問題的各種狀況 能有效地執行且所需時間 愈短愈好執行所需記憶體空間 愈少愈好,處理演算法的方法,資料結構簡介,Backtracking：Branch-and-Bound：Divide-and-Conquer：Dynamic Programming：Enumeration：Greedy Method：,處理演算法的方法,資料結構簡介,書上少 u,Backtracking：先定義問題空間，然後從此問題空間尋找解決的答案。如n皇后問題Branch-and-Bound：Divide-and-Conquer：Dynamic Programming：Enumeration：Greedy Method：,處理演算法的方法,資料結構簡介,Backtracking：Branch-and-Bound：用於樹狀追蹤(tree traversal)。建立(如二元樹的)樹狀結構，再依據其特性尋找問題的答案。Divide-and-Conquer：Dynamic Programming：Enumeration：Greedy Method：,處理演算法的方法,資料結構簡介,Backtracking：Branch-and-Bound：Divide-and-Conquer：將一個問題分割成許多小問題，逐一解決這些小問題後，再將答案合併就可得原來問題的答案。如：快速排序法。Dynamic Programming：Enumeration：Greedy Method：,處理演算法的方法,資料結構簡介,Backtracking：Branch-and-Bound：Divide-and-Conquer：Dynamic Programming：將一個問題分成幾個問題，然後將前一問題的最佳選擇答案留下來，作為決定目前問題的最佳選擇答案Enumeration：Greedy Method：,處理演算法的方法,資料結構簡介,Backtracking：Branch-and-Bound：Divide-and-Conquer：Dynamic Programming：Enumeration：在一群可能答案中尋找出正確的答案Greedy Method：,處理演算法的方法,資料結構簡介,Backtracking：Branch-and-Bound：Divide-and-Conquer：Dynamic Programming：Enumeration：Greedy Method：用於以某種規則做最佳選擇,處理演算法的方法,資料結構簡介,流程圖,資料結構簡介,以流程圖表示輸入一數(如18)，輸出其因數。,ex=1+x+x2/2!+x3/3!.+xn/n!，若ex0.0005，試寫一演算法解ex。若x=1，求e的值為若干？,Solution,
