資料結構小白入門
資料結構指一組相互之間存在一種或多種特定關系的資料元素的集合,
當我們需要在計算機中存盤這些資料時,還涉及到資料的,組織方式,在計算機中的存盤方式,以及定義在該資料上的一組操作;
- 一組資料相互之間有某種關系
- 組織方式
- 存盤方式
- 以及可對其進行的一組操作
理解:
我們學習的最終目的是要在計算機中存盤一組資料,但是不得不先考慮資料的組織方式,在計算機中的存盤方式,以及可以對這些資料進行的一組操作,當然了既然是一組資料必然表明了這寫資料之間是存在想換的關聯關系的;關系可能還會有多種;
例如:
一組資料:12345
組織方式:從小到大
存盤方式:可使用線性存盤結構
操作:要取出最大的一個
資料結構研究方向
問題:
- 機外處理
- 處理要求
建模:
- 邏輯結構
- 基本運算
實作:
- 存盤結構
- 演算法
基本術語
資料(Data):
? 所有能被計算機處理的符號的集合
資料元素(DataElement):
? 是資料集合中的一個 個體,即資料的基本單位
資料項(DataItem):
? 資料元素常常可分為若干個資料項,資料項是資料具有意義的最小單位
組織資料的三個層次:
資料(表)->資料元素(行)->資料項(欄位)
實際問題中的資料成為原始資料
邏輯結構(LogicalStructure)
? 資料元素之間的結構關系,如從小到大/一對一/一對多
物理結構(PhysicalStructure)
? 也會叫做存盤結構,指資料在計算機內的表示,邏輯結構在計算機中的具體實作
邏輯結構
常見的邏輯結構如下:
集合:
資料元素屬于同一個集合,表示為R{}; 資料之間不存在特定關系
組織結構松散,任意兩節點之間都沒有鄰接關系
線性:
除了起始節點d1和終端階段dn外,每個節點都有一個前驅和一個后繼,表示為R={d1,d2...dn},資料之間存在前后順序關系
各節點按邏輯關系排列,形成一條'鏈'
樹狀:
每個元素最多有一個前驅,可以有多個后繼,表示為(D,{R}),就像一個樹干長了多個樹枝
具備分支,層次特性,上層節點可以和下層多個節點相鄰接,但是下層節點只能和一個上層節點鄰接
圖狀:
任何兩個元素之間都可以相鄰接,表示為(D,{R})
注意:
邏輯結構
-
與元素本身的形式,內容,無關
-
元素的相對位置,無關
-
與包含的節點個數,無關
存盤結構
存盤結構由 存盤節點(每個存盤節點存放一個資料元素) 和 節點之間的邏輯關系共同組成
反過來說,一個完整的存盤結構必須可以存盤資料元素,以及元素之間的邏輯關系
存盤結構分類分為四種:(缺圖)
順序存盤
使用索引(相對起始位置)來表示資料的邏輯結構,資料被存盤在一組連續的存盤單元中
特點:
- 需預先分配長度,
- 插入和洗掉慢,需要移動其他元素
- 存取資料快捷,屬于隨機存盤結構(可通過索引直接訪問任意位置資料)
鏈式存盤
借助元素地址指標表示資料的邏輯結構,每個元素都會包含指向下一個元素的指標
這種結構需要在節點上附加一個指標項,指出后繼節點的位置,即每個節點存盤單元包含兩個部分:[資料項,指標項]
特點:
- 動態分配內容,不需要預先分配記憶體
- 插入洗掉快捷,不需要移動其他元素
- 非隨機存取結構(獲取資料必須遍歷前面的所有節點)
索引存盤(Map是否屬于索引結構 很疑惑?)
借助索引表來指示資料元素的存盤位置
索引表中包含了所有資料元素的地址,查詢索引表能夠快速的定位到需要的資料
特點:
- 索引是一份獨立于實際存放資料,的資料結構(就像書的目錄都在正文前面)
- 索引需要占用額外的存盤空間
- 當實際資料發生改變時需要重建索引
- 查詢資料快
- 插入修改,洗掉慢
散列存盤(哈希表)
通過散列函式計算得出元素的位置
特點:
- 在散列函式不變時,相同資料會得出相同的位置
- 存入順序和取出順序通常不一致
- 無法完成隨機存取(指定獲取某個元素)
順序和鏈式是最基本的也是最常用的存盤結構,需要重點掌握,包括各自的優缺點,使用場景等
鏈式存盤結構可實作樹結構(邏輯結構)
運算
運算指的是某種邏輯結構上可以進行的操作;
運算分為兩類:
-
加工型運算
會改變原邏輯結構的內容,順序,個數等的操作
-
參考型運行
與加工型運算相反
常見運算:
建立,查找,讀取,插入,洗掉
其中:
加工型:建立,插入,洗掉 參考型:讀取,查找
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93569.html
標籤：其他
下一篇：Lua實作的八皇后問題