# 資料結構

## 陣列

### 一維陣列

var arr = new int[3] { 1, 2, 3 };

[Example](https://dotnetfiddle.net/8RV5Pq)

### 二維陣列
二維陣列的定義是把第一維度的長度放在最後一個，並且把第二維度的長度放在前面

var arr = new int[4, 7]
{
    {1, 2, 3, 4, 5, 6, 7},
    {8, 9, 10, 11, 12, 13, 14},
    {15, 16, 17, 18, 19, 20, 21},
    {22, 23, 24, 25, 26, 27, 28}
};
for (int i = 0; i < arr.GetLength(0); i++)
{
    for (int j = 0; j < arr.GetLength(1); j++)
    {
        Console.Write(arr[i,j]);
    }
    Console.WriteLine();
}

[Example](https://dotnetfiddle.net/79I0Pc)

### 多維陣列
三維以上即為多維陣列。
三維陣列的定義是把第一維度的長度放在最後一個，並且把第二維度的長度放在第二個，第三維度放在第一個；
以此類推，因此維度跟定一時的順是反過來的

維度:              3 2 1
var arr = new int[3,3,3] 

維度:              4 3 2 1
var arr = new int[4,3,2,1] 

維度:              5 4 3 2 1
var arr = new int[3,2,3,1,2] 

var arr = new int[2, 3, 4, 7]
{
    {
        {
            {1, 2, 3, 4, 5, 6, 7},
            {8, 9, 10, 11, 12, 13, 14},
            {15, 16, 17, 18, 19, 20, 21},
            {22, 23, 24, 25, 26, 27, 28}
        },
        {
            {1, 2, 3, 4, 5, 6, 7},
            {8, 9, 10, 11, 12, 13, 14},
            {15, 16, 17, 18, 19, 20, 21},
            {22, 23, 24, 25, 26, 27, 28}
        },
        {
            {1, 2, 3, 4, 5, 6, 7},
            {8, 9, 10, 11, 12, 13, 14},
            {15, 16, 17, 18, 19, 20, 21},
            {22, 23, 24, 25, 26, 27, 28}
        }
    },
    {
        {
            {1, 2, 3, 4, 5, 6, 7},
            {8, 9, 10, 11, 12, 13, 14},
            {15, 16, 17, 18, 19, 20, 21},
            {22, 23, 24, 25, 26, 27, 28}
        },
        {
            {1, 2, 3, 4, 5, 6, 7},
            {8, 9, 10, 11, 12, 13, 14},
            {15, 16, 17, 18, 19, 20, 21},
            {22, 23, 24, 25, 26, 27, 28}
        },
        {
            {1, 2, 3, 4, 5, 6, 7},
            {8, 9, 10, 11, 12, 13, 14},
            {15, 16, 17, 18, 19, 20, 21},
            {22, 23, 24, 25, 26, 27, 28}
        }
    }
};
for (int i = 0; i < arr.GetLength(0); i++)
{
    Console.WriteLine("四維：");
    for (int j = 0; j < arr.GetLength(1); j++)
    {
        Console.WriteLine("    三維：");
        for (int k = 0; k < arr.GetLength(2); k++)
        {
            Console.WriteLine("        二維：");
            for (int l = 0; l < arr.GetLength(3); l++)
            {
                Console.Write("             一維："+arr[i, j, k, l]+", ");
            }
            Console.WriteLine();
        }
        Console.WriteLine();
    }
    Console.WriteLine();
}

[Example](https://dotnetfiddle.net/gHgUgN)

## 連結串列

### 單向連結串列
每一個節點都會包含**指標**跟**值**，必須透過讀取指標依照順序一路下去才能找到下一個**值**的所在位址，無法回頭往前推。

### 雙向連結串列
每一個節點都會包含 **2個指標** 跟 **1個值** ，可以透過 **往前** 或 **往後** 的來找到 **前一個** 或 **後一個** **值** 的所在位址。每次增加節點會需要調整4個指標，刪除會調整2個指標

### 環狀連結串列
每一個節點都會包含 **1個指標** 跟 **1個值** ，是單向連結串列的頭尾會相連。

## 堆疊
屬於後進先出的資料結構(LIFO，Last In First Out)，後進的資料會被提早取到；
一般可以用陣列去實作，但 C# 有內建 Stack

var numbers = new Stack<string>();
numbers.Push("1");
numbers.Push("2");
numbers.Push("3");
numbers.Push("4");
numbers.Push("5");

foreach( string number in numbers ) //依序印出
{
    Console.WriteLine(number);
}

Console.WriteLine("\n取出最頂端的資料 : " + numbers.Pop());
Console.WriteLine("\n取出最頂端的資料 : " + numbers.Pop());
Console.WriteLine("\n取出最頂端的資料 : " + numbers.Pop());
Console.WriteLine("\n取出最頂端的資料 : " + numbers.Pop());
Console.WriteLine("\n取出最頂端的資料 : " + numbers.Pop());

[Example](https://dotnetfiddle.net/m44M09)

## 佇列
先進先出(FIFO，First In First Out)，資料的概念必須以下幾個特點：
1. 有 2 個端點，分為 **前端** 及 **後端**；
2. 後端只可以 **新增** 資料
3. 前端只能 **刪除** 及 **修改** 資料
4. 資料的存取必須符合先進先出的概念


C#有內建 Queue 實現這個資料

var numbers = new Queue<string>();
numbers.Enqueue("1"); //將資料加入的後端
numbers.Enqueue("2");
numbers.Enqueue("3");
numbers.Enqueue("4");
numbers.Enqueue("5");

foreach( string number in numbers )
{
    Console.WriteLine(number);
}

//從的前端頭移除最早加入的元素
Console.WriteLine("\n取出前端的資料 : "+ numbers.Dequeue());  
Console.WriteLine("\n取出前端的資料 : "+ numbers.Dequeue());  
Console.WriteLine("\n取出前端的資料 : "+ numbers.Dequeue()); 
Console.WriteLine("\n取出前端的資料 : "+ numbers.Dequeue());  
Console.WriteLine("\n取出前端的資料 : "+ numbers.Dequeue());  

[Example](https://dotnetfiddle.net/5WvmZS)

## 樹 Tree
樹狀結構是一種階層式的架構，只有上對下或下對上的關係，不會有前後的關係，不可為空集合。
1. 由一個或多個節點組成的集合，會有一個根節點，放在最頂層，接著再沿著分支逐漸往下延伸；
2. 每個節點只會跟上下層的節點透過分支有連結
3. 不會有迴路存在


**一些名詞解釋：**
* 根節點：最頂端的節點，不會有父節點，只會有子節點；如圖上的 Alice
* 父節點：如果該節點下面有節點，即為父節點；如圖上的 Alice, Bob, Chris
* 子節點：如果該節點上面有節點，即為子節點；如圖上除了的 Alice 之外的節點全部都是子節點
* 兄弟節點：如果有共同的父節點，且為同一層，即為兄弟節點；如圖上的 Bob, Chris, David 為兄弟節點，Eva, Frank 也是兄弟節點
* 分支度：父節點的下一層有幾個子節點；如圖上的 Alice 的分支度是 3 因為有 3 個子節點， Bob 的分支度為2 因為有 2 個子節點
* 終端節點或樹葉：沒有任何子節點；如圖上的 Eva, Frank, Gina
* 非終端節點：沒有任何子節點；如圖上的 Eva, Frank, Gina 意外的均為非終端節點
* 階層：位於樹狀結構的第幾層；如圖上的 Alice 在第一層，Frank 在第三層
* 高度：總共有幾層節點；如圖上總共有3層

### 二元樹 Binary Tree
每一節點的子節點只會有0~2個，分別為 **左子樹 ** 及 **右子樹 **；有 **次序** 關係，**先左後右**；可以為空集合

**樹及二元樹之比較：**
|樹 tree|二元樹 binary tree|
|:----:|:----:|
|不可以為空|可以為空(空集合)|
|Node's degree $\geq$ 0即可|0 $\leq$ Node's degree $\leq$ 2|
|子樹之間無次序/方向之分|子樹有左右之分|


**完滿二元樹(Full B.T.，Full Binary Tree)**
代表一個樹在特定高度 **i** 下，所能出現的節點數量有符合以下公式的樹，即為完滿二元樹，此公式也代表一個樹的最大值：
公式：==$2^{i-1}$==
ex. 下圖的樹就是完滿二元樹，i為3
:::info
$2^{3}-1$ => $8-1$ => $7$
:::

推演過程：

**完整二元樹(Complete B.T.，Complete Binary Tree)**
需符合以下 2 個條件：
1. 節點數量除了最後一層之外，皆有完整填滿，公式：2^i-1^-1 < N < 2^i^-1
:::info
當 i = 3，則數量為 3~6
==> 2^3-1^-1 < n < 2^3-1
==> 2^2^-1 < n < 2^3^-1
==> 4-1 < n < 8-1
==> 3 < n < 7
:::
2. 需照順序排序，由上到下，由左到右，如果不照順序即不為完整二元樹

以上圖來說，圖節點數量在下圖紅框處內即為完整二元樹


### 歪斜樹 Skewed Binary Tree
節點只有左子樹或右子樹時，即為歪斜樹

### 嚴格二元樹 Strict Binary Tree
所有的非葉子節點的分支度都是2，即為嚴格二元樹

### 二元樹的程式表示

二元樹可以用陣列或連結串列來表示

|陣列|連結串列|
|:----:|:----:|
|訪問快|搜尋效率低|
|插入和刪除效率低|插入刪除效率高|

#### 陣列
1. 通常 Index 0 都會留空，從 Index 1 開始存放，Index 1 為根節點
2. 節點依照順序存放，從上到下，從左到右


公式：
i 為索引，計算後的值(四捨五入)代表該節點的索引
* 父節點： (i-1)/2
* 左子樹： 2 x i
* 右子樹： 2 x i - 1

ex. C 的索引是 3，故 C 的父節點是 (2-1)/2=1，因此 C 的父節點存在 Index 1 的位置
C 的索引是 3，故 C 的左子樹是 2x3=6，因此 C 的左子樹存在 Index 6 的位置
C 的索引是 3，故 C 的右子樹是 2x3+1=6，因此 C 的右子樹存在 Index 7 的位置


:::info
使用陣列儲存歪斜樹，如下圖，Index 2, 4, 5, 6 的記憶體全部都被浪費了
故陣列只適合儲存完滿二元樹或完整二元樹，且增加或搬移節點時，需要搬移多個節點

:::

#### 連結串列

1. 節點容易新增或刪除
2. 不容易找父節點

因為雙向連結串列剛好是1個值加上2個指標，因此剛好可以用來表示二元樹，用連結串列來表示二元樹比較節省空間，但在樹葉仍然會有一些指標的浪費
如下圖：

**完整二元樹：**
**右歪斜樹：**

通常程式碼結構會如下：

struct Node{
  Node* Lchild;
  Node* Rchild;
  int data;
};

### 二元樹排序走訪 Binary Tree Traversal

#### 中序走訪

###### tags: `資料結構`