第1章 概論

• 2020 年 10 月 3 日
• 筆記
• 數據結構-考研or面試

第1章 概論

一、數據結構的基本概念與術語

1.1 數據結構的基本概念

1. 數據結構：按一定的邏輯結構組成的一批數據，使用某種存儲結構將這批數據存儲於電腦中，並在這些數據上定義了一個運算集合

1.2 數據的邏輯結構

1. 邏輯結構的種類：

   1. 集合
   2. 線性結構
   3. 樹形結構
   4. 圖狀結構

2. 數據的邏輯結構：數據和數據之間存在的邏輯關係

3. 開始結點：結點沒有前驅結點

4. 終端結點：結點沒有後繼結點

5. 內部結點：既不是開始結點也不是終端結點

6. 註：有時候，邏輯結構簡稱為數據結構

1.3 數據的存儲結構

1. 存儲結構的種類：

   1. 順序存儲
   2. 鏈式存儲
   3. 索引存儲
   4. 散列存儲

2. 數據的存儲結構：數據在電腦中的存儲方式

3. 順序存儲：邏輯上相鄰的結點物理位置也相鄰

4. 鏈式存儲：邏輯上相鄰的結點物理位置不一定相鄰（可相鄰可不相鄰）

5. 索引存儲：根據結點的索引號確定該結點的存儲地址

6. 散列存儲：結點在電腦中的存儲地址由h（函數）決定

   1. 存儲密度 = 數據本身所佔存儲空間的大小 / 整個數據結構所佔存儲空間的大小
   2. 註：順序存儲密度 = 1；鏈式存儲密度 < 1

1.4 數據的運算集合

1. 數據的運算：定義在數據的邏輯結構上，具體實現依賴於數據的存儲結構
2. 數據的運算集合
   1. 插入
   2. 刪除
   3. 檢索
   4. 輸出
   5. 排序

二、數據類型和抽象數據類型（大綱未規定）

2.1 數據類型

1. 數據類型：反映了數據的取值範圍以及對這類數據可以施加的運算
2. 數據類型的兩個方面：數據屬性 + 在數據上可以施加的運算集合
3. 註：數據結構是數據存在的形式

2.2 抽象數據類型

1. 抽象數據類型：數據類型的進一步抽象，基本數據類型的延伸和發展

2.3 抽象數據類型的描述和實現

1. 抽象數據類型的描述：抽象數據類型的名稱 + 數據的集合 + 數據之間的關係和操作的集合
2. 抽象數據類型的實現：依賴於程式設計語言實現

三、演算法和演算法分析

3.1 演算法的基本概念和基本特徵

1. 演算法：求解問題的方法和步驟（一系列有限的運算規則 or 若干條指令組成的有窮序列）
2. 演算法的特徵：
   1. 有窮性：演算法執行必須在有限步結束
   2. 確定性：演算法的每一個步驟都必須是確定的、獨一無二的
   3. 輸入：演算法有0個或多個輸入
   4. 輸出：演算法一定有輸出結果
   5. 可行性：演算法中的運算必須是可以實現的
3. 程式：用電腦語言表達的求解一個問題的一系列指令的序列
4. 演算法和程式的區別：演算法具有有窮性；程式不需要具有有窮性

3.2 演算法的時間複雜度和空間複雜度

1. 演算法的時間複雜度：演算法執行過程中他的基本操作的執行次數
2. 註：評價演算法的時間複雜度時，不考慮兩演算法執行次數之間的細小區別，而只關心演算法的本質區別
3. 常見演算法的複雜度：1、\(log_2n\)、n、\(nlog_2n\)、\(n^2\)、\(n^3\)、\(2^n\)
4. 演算法的最好情況：演算法計量值的最小值
5. 演算法的最壞情況：演算法計量值的最大值
6. 演算法的平均情況：演算法在所有可能情況下的計算量的加權平均值
7. 演算法的空間複雜度：除了存儲數據本身以外的附加存儲空間

、