###### tags: `DataStructure`
# 淺談資料結構
資料結構就是電腦儲存資料的架構，包含儲存的位址及模式
好的結構可以提升演算效率，即降低運算時間、減少記憶體佔用空間
本篇會簡單的介紹幾個常見的結構

---
資料結構大致分成三種型態
- 基本資料型態
- 最基本的資料單位，例如:整數、浮點、布林等
- 結構化資料型態
- 基本型態的集合體，例如:陣列、串列、字典
- 抽象資料型態
- 著重於資料的狀態、操作、封裝，是一種擁有特定模式的抽象概念，例如:堆疊、佇列

基本型態是資料的基礎單位，而結構化型態就是一組基本資料的集合
有些程式語言可以自定義struct，這也屬於結構化型態
這兩種型態比較基本，所以就不細說，接下來僅介紹抽象資料型態

## 抽象資料型態(Abstract Data Type, ADT)
抽象資料型態，是一種組織過的資料型態
提供 『物件 (objects)』 與 『作用於這些物件的 操作 (operations)』 規範，
<font color=red>而非實際表示法與具體實現的方式</font>，規範需說明每個操作要做什麼，而非如何做

操作規範基本上需包含以下四種：
- 函式名稱
- 參數型態
- 結果型態
- 函式功能的描述 (不必說明內部表示法或實作細節)

在物件導向程式中，ADT 可以用介面 (interface) 來表示
介面的中心思想是<font color=green>封裝隔離</font>，也就是外部類別只需呼叫介面提供的方法，不需知道內部如何實作
善用介面可使系統具高維護性、彈性，不論是擴充或重構，呼叫時內部僅會受到最小幅度的影響
有在串接第三方函式庫的人看到這裡就可以明白，其實 API 就是一種 ADT
> https://notfalse.net/5/adt

### 堆疊(Stack)
顧名思義他是一層層疊起來的結構，最先放入的會在最下方，而後放入的會在上方
因此要取得資料時，會先拿到最新的資料，這種原理叫做後進先出(Last In First Out)
而放入的動作稱為推入(Push)，拿取資料的動作稱為彈出(Pop)
嚴格來說，推疊使用上並不方便，因為只能單向操作，但從隨時能取得最新的資料這點來看
其實是相當便利，另外，在搜尋法中被稱為深度優先搜尋法，能隨時在搜尋選項中選擇最新資料
所以可利用堆疊的方式來管理內部的選項資訊

### 佇列(Queue)
它跟堆疊很像，差別僅在於它會優先取得最早的資料，這種原理叫做先進先出(First In First Out)
先進去的資料會先取得，這種依序的方式相當自然，也因此廣受應用，後來也出現了雙向佇列
另外，在搜尋法中被稱為廣度優先搜尋法，能優先在搜尋選項中選擇最早資料
所以可利用佇列的方式來管理內部的選項資訊

### 雜湊表(Hash Table)
在談雜湊表之前，先來談談與它相關的結構—列表與陣列
- 列表
列表內儲存的數據都搭配著一個指標，指標會對應到下一個數據存放的位址
所以不需要依序存在記憶體中，大多是分散於不同領域，然而分散儲存的方式
造成存取數據時，只能從頭跟著指標存取數據，此方式稱為順序存取(Sequential Access)
好處是追加與刪除數據時，只要把該數據位址的前後指標做修改即可
- 陣列
數據會依序存在記憶體的連續領域中，因為是連續領域，所以可用索引計算記憶體位址
直接存取每個數據，此方式稱為隨機存取(Random Access)
然而連續儲存的方式，造成追加、刪除數據時，需要高於列表的代價
追加數據要先確定陣列有空間可以新增數據，再者，為了挪出新數據需要的空間
需要將原數據依序向後移動(若追加在最後則不用移動)，再將新數據放入空間
刪除也同理，將預刪除資料移出後，把後方數據向前移動，這樣的操作相當耗時
- 優缺點
- 列表：存取慢、追加快、刪除快
- 陣列：存取快、追加慢、刪除慢
> 可以考慮哪種操作比較頻繁來決定用何種資料結構

再來談談雜湊表，它其實正是列表與陣列的合體，是一種Key-Value的形式
首先準備好一個陣列(ex:大小5)，存放數據時，先用雜湊函數計算此數據的Key值
假設算出的雜湊值為4928，將其除以陣列大小取餘數可得3，則該數據將存放在索引值3
若存放的索引值已經有數據，我們稱之為碰撞，此時新數據也存於相同索引值
而原數據增加一個指標，指向新數據的位址(如同列表的結構)
查找數據一樣先算出雜湊值，除以陣列大小取餘數，找到對應的的索引值即可
若索引值不是該數據，則依指標進行線性搜尋，找出Key值相同的資料

整體看下來，我們可以把雜湊表的結構想成行列樣式，行是陣列，列是列表
雜湊表利用雜湊函數，可以快速讀取陣列中的數據，當發生碰撞，可利用列表
但如果一開始陣列規模過小，將造成碰撞次數增加，容易產生線性搜尋
反之，陣列規模過大，會產生許多未儲存的空間，造成記憶體浪費
因此設定適當的陣列規模相當重要

補充:發生碰撞時，利用列表的方式稱為鏈結法，此外還有很多方式
最廣為使用的是開放定址法，求出第二候補的陣列位置，並儲存
若第二位置也有數據，則求出第三位置，這樣的方式可以解決陣列空間浪費的問題
而求出候補位置的方式也有很多種，例如使用多個雜湊函數或線性探測法。
雜湊函數有一項規則是無法從雜湊值回推出原始值，此條件適用於安全性相關用途
例如使用者密碼，並非使用雜湊表的必要條件。
雜湊表能彈性儲存、快速讀取數據，常用於程式語言的關聯陣列

### 堆積(Heap)
堆積是樹狀結構之一，屬於特殊的完全二元樹，用於實踐優先佇列
優先佇列是一種可以自由追加數據、讀取數據以極值(最小、最大)開始選取的資料結構
極值存於最上方，取數據只要從最上端拿取，然後最右下方的數據會往最上方補，再進行排序
追加數據則以最左下方開始追加，然後再進行排序。由於不易理解，請參考以下連結
> https://ithelp.ithome.com.tw/articles/10206479

### 二元搜尋樹(Binary Search Tree)
樹狀結構之一，所有節點都會大於其左邊的節點、小於其右邊的節點
因此最小值在最左方，最大值在最右方
追加數據從最上方開始，將其與所在節點比較，小於節點往左，大於節點往右
直到移動的位置沒有節點為止
> https://ithelp.ithome.com.tw/articles/10205875

> http://alrightchiu.github.io/SecondRound/mu-lu-yan-suan-fa-yu-zi-liao-jie-gou.html