《Fundamentals of Data Structure in C》
[Ch1]
====1.1系統生命週期====
需求
- 規格
- 輸入輸出說明
分析
- 由下而上： 沒有結構化
- 由上而下：以程式最後的目標為開端，並利用這個最後結果將程式分割成數個可管理的分段。
設計：延續分析，從程式所需資料物件和資料運算兩方面來設計系統。
- 資料物件：產生抽象的資料型態。
- 資料運算：需要演算法的規格並考量演算法的設計策略。
藉著盡可能延緩實作問題，不但可以產生一個可用數種語言編寫的系統，還可以有足夠的時間在選擇的語言中找到最有效率的實作方法。
改良和編碼：為每一個資料物件選擇表示法，並編寫各種運算之演算法。
選擇資料物件的表示法可以決定其相關的演算法的效率。
驗證
- 正確性驗證
- 測試
- 消除錯誤
基本的系統測試重點在於證明程式可以正確地執行，而程式的執行時間也是重要的因素。
====1.2演算法====
定義
- 是一組有限的指令，根據這些指令，可以完成一項特定的工作。
- 必須符合：輸入/ 輸出/ 明確的/ 有限的/ 有效率的
遞迴演算法：
函數可以呼叫自身（直接遞迴，direct recursion），或再度引用其呼叫函數（間接遞迴，indirect recursion）。
任何使用指派指令，if-else和while指令編寫的函數，都可以用遞迴的方式編寫。遞迴的函數比其對等的重複性函數容易瞭解。
====1.3資料抽象化====
資料型態：
- 物件和可以在這物件上作用的一組運算（operations）之集合。
- 陣列：具有相同的基本資料型態的元素之集合
- 結構：元素的集合，元素的資料型態不一定相同。
- 指標：對每種基本資料型態都有一個對應的指標資料型態。
抽象資料型態（abstract data type, ADT）：是一種資料型態，它的組織方式使得物件的規格與物件上的運算之規格和該物件的內部表示法與運算的實作法是獨立的。
資料型態的函數可分為數個類型：
- 產生/ 建構：產生新的實體（instance）
- 轉換
- 觀察/ 彙報
====1.4效率分析====
效率評估
- 效率分析（performance analysis）：複雜度理論（complexity theory）
- 效率估計（performance measurement）：機器相關的執行時間
空間複雜度
- 完全地執行程式所需的記憶體
- 固定的空間需求：指令/ 簡單變數/ 固定大小的結構變數/ 常數
- 可變的空間需求：在分析一個程式的空間複雜度時，通常僅考慮可變的空間需求。
時間複雜度
- 完全地執行程式所需要的計算機時間。
- 時間複雜度是以用來執行函數的程式所發生的步驟之數目來表示。
- 程式步驟是語法上或語意上有意義的程式段落。它的執行時間和實體的特性是無關的。
- 以重要特性來定義步驟計數函數的變數。
漸進式表示法（Asymptotic Notation？）
實際的複雜度（？）
====1.5效率估計====
效率評估
- 效率分析（performance analysis）：複雜度理論（complexity theory）
- 效率估計（performance measurement）：機器相關的執行時間
（？）
[Ch2]
====2.1陣列====
陣列（array）
- 陣列視同一種抽象資料型態
- 一般陣列為靜態配置（static/ local allocation），因為陣列的記憶體大小必須事先確定，無法更動。
- 相同型態資料之集合
- 直觀上，陣列是一組序對，一個索引（index）定義一個與其關連的值（value），數學上，稱為對應或映射。
- 標準運算：建立（create）/ 擷取（retrieve）/ 儲存（store）
====2.2結構和聯結====
結構（struct）
- 將不同型態的資料集合在一起
? strcpy/ strcmp
? 點號(.)當成結構成分運算符號
聯結（union）
- 欄位必須共用記憶體。
- 先設定標識欄位之值，再將值放入union中適當欄位。
- C 不會檢查欄位是否恰當。
結構的內部實作
- 一般而言，結構中的欄位值將根據位在結構定義中的先後順序，以位址漸增的方式儲存在記憶體。
- 結構中實際上會有空洞或壓縮以便將兩個相鄰的欄位適當地安排在記憶體中。
- struc/ union 型態的物件大小，是表示最大組成元素所需要的記憶體的數量，包括任何必要壓縮。
- 結構必需在相同形式的記憶體位址界限開始或結束。2/4/8/16倍數之位址。(?)
自我參考結構（self-referential structure）
- 結構中的部分組成元素是指向自身的指標。
- 通常需要動態記憶體管理常式（malloc/ free）
====2.3多項式抽象資料型態====
陣列可以用來製作其他的抽象資料型態，有序串列（ordered list）或線性串列（linear list）。
在串列上可以執行運算。
循序映射（sequential mapping）
- 以陣列表示一個有序串列，串列的元素關連到陣列的索引。
- 無法處理插入/ 刪除
====2.4稀疏矩陣抽象資料型態====
稀疏矩陣(sparse matrix)
轉置矩陣
矩陣相乘
====2.5多維陣列====
====2.6字串抽象資料型態====
C 的字串函數 fig2.8(2-41)
樣式比對
[Ch3]
====堆疊抽象資料型態====
====佇列抽象資料型態====
====迷宮問題====
====運算式計算====
====多元堆疊與佇列====
