资料结构简介-周清江副教授-淡江大学.pptVIP

Ch01 資料結構簡介 淡江大學 周清江 * 1.1 前言 * * 例如：請求出 1 到 2000 間能被 3 和 5 整除的整數之和 1.2 演算法 * * 虛擬碼及流程圖範例請參考：1-10 至1-19 1.3 演算法的效率評估 * * an2+bn+c an3+bn2+cn+d an log n n n log n n2 n3 2n 1.4 常見的資料結構 * 陣列：排列整齊的教室座位 鍊結串列：火車一節一節的車廂 堆疊：疊在一起的自助餐盤 佇列：演唱會入場口的長列人潮 樹狀結構：球賽的單敗淘汰賽程 圖形與網路：高速公路路網 排序：音樂CD 以筆劃或英文字母排列 了解每種資料結構的特性，以便在節省儲存空間、提高資料存取速度的前提下，透過程式之撰寫以便進一步開發出可以協助使用者儲存、處理資料的程式，便是學習資料結構最大的目的。 資料結構探討的主題 * 如何以最節省記憶體的方式來表示資料 不同的資料結構表示法和其相關演算法的探討 如何改進演算法的效率 建構資料存取方法、資料儲存結構 探討資料處理技巧，如： 排序、搜尋、合併、更新、分配等 利用結構化程式設計來提升軟體開發生產力 選擇資料結構之參考資訊 * 資料量多寡 資料是否常需異動 資料被擷取之頻率 儲存資料的記憶體容量 目前使用者可接受之擷取及異動時間 程式設計的容易程度 未來擴充後，使用者可接受之擷取及異動時間 勘誤 * 1-7， “一百本書” 應為 “四十本書” 1-8，範例，第 1 個 struct 改為 class ，第 2 個 struct 刪掉 1-11，流程圖判斷式， “IF SUM =20” 應為 “IF NUM = 20” 1-13，程式說明 4 ， “梯形” 應為 “菱形” 1-24，範例程式 第 1 列， “int n” 應為 “int m” 第 7 列，這 2 個 “n” 應為 “m” 1-26，範例程式 6 上方，出現的 2 個 “12” 應為 “16” (因為有 4 個 int 變數：i, grade, average, sum)