# 認識資料結構
## 資料結構的定義

將資料以最有利的型態存放在記憶體內，以備電腦處理，並提供一些策略使電腦能最有效率地，從記憶體內存取這些資料，這些**資料的關係和存取策略**就稱為資料結構。

## 陣列(Array)
使用連續的記憶體空間，依照特定順序來儲存資料，是許多資料結構的發展基礎。

關於陣列的實作，在C語言有內建`Array`型別、Python有內建`List`型別。

優點：
1. 資料的搜尋方便，可隨機讀取資料
2. 設計時，資料結構簡單

缺點：
1. 事先需宣告固定記憶空間，彈性小
2. 刪除或加入資料需移動大量資料

## 鏈結串列(Linked-List)
`鏈結串列 (Linked-list)`是不使用連續的記憶體空間的情況下，將許多資料，依特定順序排列而成的線性串列。

1. 定義：由至少一組節點(node)所構成，節點包括一組`資料`與`指標`


實作方式是每個節點除了記錄資料之外，還使用額外的指標指向下一個節點，將節點以此方式串連起來形成一個連結串列。

2. 使用`鏈結串列(Linked-List)`的優點：
- 不需使用連續記憶體空間，不需事先指定串列大小。
- 能夠容易的修改指標，插入或移除節點。

3. 缺點如下：
- 使用額外的記憶體空間紀錄節點指標。
- 無法快速索引到某個節點，必須迭代搜索。

4. 分類

| | 單向 | 雙向 |
| -------- | -------- | -------- |
| 非環狀 | 單向鏈結串列 | 雙向鏈結串列 |
| 環狀 | 單向環狀鏈結串列 | 雙向環狀鏈結串列 |

### 單向鏈結串列
單向鏈結串列，每個節點只有一個指標，指向下一個節點。

適合存放稀疏多項式，節省記憶體空間。

### 雙向鏈結串列
雙向鏈結串列，每個節點有兩個指標，分別指向上一個跟下一個節點。

比起單向鏈結串列，指標可以往前面節點移動，不需重新掃描。

### 環狀鏈結串列
倘若該鏈結串列末端節點的指標指向第一個的節點，形成一個循環，稱為環狀鏈結串列

## 矩陣(Matrix)

一個m×n的矩陣是一個由m列（row）、n行（column）元素置換成的矩形陣列。
矩陣裡的元素可以是數字、符號或數學式。

以下是一個由6個數字元素構成的2列3行的矩陣：

\begin{bmatrix}1 & 9 & -13 \\20 & 5 & -6 \end{bmatrix}

矩陣常見運算與操作包括：
- 加減法
- 乘法
- 轉置(Transpose)

## 堆疊(Stack)


一群相同資料型態的組合，具備以下特性：
1. 所有動作均在頂端進行
2. 具備`後進先出(Last-In First-Out, LIFO)`的特性
3. 具備以下操作方式
- `create`: 建立空堆疊
- `push`：加入新元素到堆疊頂端
- `pop`：刪除堆疊的頂端元素
- `isEmpty`：判斷堆疊是否為空
- `full`：判斷堆疊是否已滿

例如桶裝的品客洋芋片，最先放進去的洋芋片，最後才會被拿到。

## 佇列(Queue)

一群相同資料型態的組合，具備以下特性：
1. 所有動作，都發生在兩端，分別是`尾端(rear)`, `前端(front)`
2. 具備`先進先出(First-In First-Out, FIFO)`的特性
3. 具備以下操作方式
- `create`: 建立空佇列
- `add`：加入新元素到佇列`尾端(rear)`，傳回新佇列
- `delete`：刪除佇列的`前端(front)`元素，傳回新佇列
- `front`：判斷佇列`前端(front)`的值
- `empty`：判斷堆疊是否已滿

例如買門票的隊伍，買完票的人先離開隊伍，後面來的人從隊伍後面加入。

## 樹狀結構（Tree）

### 基本定義
`樹(Tree)`由一個或一個以上的`節點(Node)`所構成，基本定義如下：
- `Node`：包含`資料(data)`與`指標(pointer)`
- `Root`： 樹的起始節點
- 節點之間可以互相連結，但不可以形成封閉無出口的迴圈

### 樹的特性
樹的特性如下：
- `Degree`： 每個節點的子樹個數
- `Level`：樹的層級
- `Height`： 樹的最大層級
- `Leaf`：Degree為零的節點，也就是沒有child/subtree

### 節點之間的關係特性
> 我們用這棵樹來舉例示意：

- `父母節點(Parent)`: 某個Node指向的Node，例如Node1是Node4的`Parent`
- `子節點(Child)`: 某個Node被某個Node指向，例如Node4是Node1的`Child`
- `祖先節點(Ancestor)`: 從某個Node出發，所有能夠以「尋找parent」的方式找到的node，皆稱為該Node的`Ancestor`，例如Node2, Root都是Node5的`Ancestor`
- `子孫節點(Descendant)`: 從某個Node出發，所有能夠以「尋找child」的方式找到的node，`Descendant`，例如Node1~Node7都是Root的`Descendant`
- `兄弟節點(Siblings)`: 擁有相同parent的node們，例如Node5和Node6

## 圖 Graph
`圖(Graph)`是由`頂點`跟`邊`所組成的集合，主要用於最短路徑搜尋、拓墣排序、或是計算交通網路。

通常用G=(V,E)來表示。
其中 V是頂點的集合，E是邊的集合，有兩種類型：
### 無向圖(Graph)
G~1~ = (V~1~, E~1~)
V~1~ = {A,B,C,D}
E~1~ = {(A,B),(A,C),(A,D),(B,D)}

### 有向圖(Digraph)

G~2~ = (V~2~, E~2~)
V~2~ = {A,B,C,D}
E~2~ = {<A,B>,<A,C>,<A,D>,<B,D>}

<!--

## 實作資料結構
我們可以使用C語言的`陣列(Array)`，或是Python的`串列(List)`來進行資料結構的實作。

### 實作Stack
- `create()`: 建立空堆疊
- `push(element)`：加入新元素到堆疊頂端
- `pop()`：刪除堆疊的頂端元素，並且輸出該元素
- `isEmpty()`：判斷堆疊是否為空
- `full()`：判斷堆疊是否已滿

### 實作Queue

### 實作Binary Tree

| Left Link | Data |Right Link |
| -------- | -------- | -------- |
| | | |

-->

###### tags: `資料結構與演算法`