[DAY20] C#基礎與實作(資料結構)

15th鐵人賽 c#

2023-10-03 23:41:16

1702 瀏覽

分享至

C# 程式基礎

資料結構：

具有資訊(意義)的資料，如被排序、被規劃/整理，這些被賦予意義的資料

陣列 (Array)：

陣列是一個有序的資料結構。具有固定大小的相同類型元素的集合。
宣告陣列：type[] arrayName;，例如 int[] numbers;
初始化陣列：arrayName = new type[length];，例如 numbers = new int[5];
存取元素：使用索引，例如 int firstNumber = numbers[0];
程式實作：
```
int[] numbers = new int[] { 1, 2, 3, 4, 5 };
```
可參考 [DAY3] C#基礎與實作(Array)

列表 (List)：

列表是可動態調整大小的元素集合，通常使用 List 類別實作。
宣告列表：List listName = new List();
添加元素：listName.Add(item);
存取元素：使用索引，例如 type firstItem = listName[0];

程式實作：

List<string> names = new List<string>();
names.Add("Alice");
names.Add("Bob");

可參考 [DAY8] C#基礎與實作(List)

字典 (Dictionary)：

字典是鍵-值對的集合，通常使用 Dictionary<TKey, TValue> 類別實作。
宣告字典：Dictionary<keyType, valueType> dictionaryName = new Dictionary<keyType, valueType>();
添加鍵-值對：dictionaryName[key] = value;
存取值：使用鍵，例如 valueType value = dictionaryName[key];

程式實作：

Dictionary<string, int> ages = new Dictionary<string, int>();
ages["Alice"] = 25;
ages["Bob"] = 30;
ages["Charlie"] = 22;

可參考 [DAY9] C#基礎與實作(Dictionary)

佇列 (Queue)：

佇列是先進先出 (FIFO) 的資料結構，通常使用 Queue 類別實作。
宣告佇列：Queue queueName = new Queue();
添加元素到佇列尾部：queueName.Enqueue(item);
移除佇列前端元素：type item = queueName.Dequeue();

程式實作:

Queue<int> queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);

堆疊 (Stack)：

堆疊是後進先出 (LIFO) 的資料結構，通常使用 Stack 類別實作。
宣告堆疊：Stack stackName = new Stack();
添加元素到堆疊頂部：stackName.Push(item);
移除堆疊頂部元素：type item = stackName.Pop();

程式實作:

Stack<string> items = new Stack<string>();
items.Push("Item 1");
items.Push("Item 2");

鏈結串列 (Linked List)：

鏈結串列是一個線性資料結構，其中的元素以節點 (Node) 形式相互連結。
每個節點都包含一個值(資料)和一個指向下一個節點的鏈結。
C# 中的 LinkedList 類別實作了連結串列。

程式實作:

LinkedList<int> linkedList = new LinkedList<int>();

linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);

LinkedListNode<int> node = linkedList.Find(2);
linkedList.AddAfter(node, 4);

// 現在 linkedList 包含 1 -> 2 -> 4 -> 3

程式實作(class 建立):

class Node
{
    public int Value { get; set; }
    public Node Next { get; set; }
}

class LinkedList
{
    public Node Head { get; set; }
    // 添加、刪除、搜尋等操作的方法
}

樹 (Tree)：

樹是一種層次結構的資料結構，由節點組成，其中一個節點稱為根節點。
每個節點可以有零個或多個子節點。
常見的樹類型包括二元樹 (Binary Tree)、二元搜尋樹 (Binary Search Tree) 等。
二元樹 (Binary Tree)
- 二元樹是一種階層結構，每個節點最多有兩個子節點。
- 常被用於搜索和排序演算法。

程式實作(class 建立):

class TreeNode
{
    public int Value { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }
}

二元搜尋樹 (Binary Search Tree, BST)
- 二元搜尋樹是一種常見的二元樹資料結構，其中每個節點都具有以下特性：
  - 左子樹中的所有節點的值小於該節點的值。
  - 右子樹中的所有節點的值大於該節點的值。
- BST 可以用於有效地搜索、插入和刪除元素。
- BST 具有平均和最壞情況下的 O(log n) 複雜度。

程式實作(建立和操作二元搜尋樹):

class TreeNode
{
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }
}

TreeNode root = new TreeNode(10);
root.Left = new TreeNode(5);
root.Right = new TreeNode(15);
root.Left.Left = new TreeNode(3);

堆 (Heap)：

堆是一種二元樹，通常用於實現優先佇列 (Priority Queue)。
堆分為最小堆 (Min Heap) 和最大堆 (Max Heap)。
最小堆中，根節點的值最小；最大堆中，根節點的值最大。
C# 中可使用 System.Collections.Generic 中的 Heap 來實現堆。

程式實作(建立最小堆):

using System;
using System.Collections.Generic;

Heap<int> minHeap = new Heap<int>(HeapType.Min);
minHeap.Insert(10);
minHeap.Insert(15);
minHeap.Insert(5);

int min = minHeap.ExtractTop(); // 取出最小值，這裡是 5

圖 (Graph)

圖是一種由節點 (Node) 和邊 (Edge) 構成的資料結構，用於模擬實體物件之間的關聯。
圖可以是有向的 (Directed) 或無向的 (Undirected)，根據邊的方向。
圖的表示方式有多種，包括鄰接矩陣和鄰接串列。

程式實作(建立無向圖):

class Graph
{
    private int V; // 節點數
    private List<int>[] adj; // 鄰接串列

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new List<int>();
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
        adj[w].Add(v); // 無向圖需加入雙向邊
    }
}

Graph graph = new Graph(4);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 2);
graph.AddEdge(2, 3);