數據結構與算法第一章
- 2022 年 7 月 24 日
- 筆記
數據結構與算法 （第一次課）
數據元素是數據的基本單位
數據項是是數據的最小不餓分割單位
數據>數據元素>數據項
數據對象是數據元素相同的集合
數據對象是性質相同的數據元素的集合
數據元素是數據的個體
數據對象是數據的子集
- 數據>數據對象>數據元素>數據項
數據結構：數據的運算和實現，邏輯結構和物理結構（存儲結構）
存儲結構是邏輯結構的映像和元素本身的映像
邏輯結構是數據結構的抽象，存儲結構是數據結構的實現
邏輯機構的種類
- 線性結構
線性結構有且只有一個開始和終端節點，並且每個節點都最多有一個直接前趨或者直接後繼
例如： 線性表、隊列、棧、串
- 非線性結構
例如：圖、樹
邏輯結構劃分第二種方式
- 集合結構：數據元素之間除了同屬於一個集合外沒有任何其他關係
- 線性結構：數據元素之間存在一對一的關係
- 樹形結構：數據元素之間存在一對多的關係
- 圖狀（網狀）結構：數據元素之間存在多對多的關係
存儲結構的種類
- 順序存儲結構
- 鏈式存儲結構
- 索引存儲結構
- 散列存儲結構
順序結構
用一串連續的存儲單元依次存儲數據
鏈式結構
任意的存儲單元數據元素之間的邏輯關係用指針來表示
索引結構
存儲數據的同時還建立索引表
索引的一般形式是：關鍵字+地址
索引有：稠密索引和稀疏索引
散列存儲結構
根據關鍵字計算出該結點的存儲地址
數據類型和抽象數據類型
基本數據類型
構造數據類型
指針、空等數據類型
typedef定義數據類型
數據類型是一種性質相同元素的結合以及值集合上的一組操作
抽象數據類型（ADT：abstract data type）：抓住本質屬性，捨棄不必要屬性的相同元素的結合以及值集合上的一組操作，包括：數據對象，數據對象上的關係集，數據對象的基本操作；
