資料結構基礎知識

概述

資料結構是為實作對計算機資料有效使用的各種資料組織形式，服務于各類計算機操作，不同的資料結構具有各自對應的適用場景，旨在降低各種演算法計算的時間與空間復雜度，達到最佳的任務執行效率，

分類

線性資料結構（物理結構）

陣列(Array)、鏈表(Linked List)、堆疊(Stack)、佇列(Queue)

非線性資料結構（邏輯結構）

樹(Tree)、堆(Heap)、散串列(Hashing)、圖(Graph)

陣列

陣列是將相同型別的元素存盤于連續記憶體空間的資料結構，其長度不可變，

如下圖所示，構建此陣列需要在初始化時給定長度，并對陣列每個索引元素賦值，代碼如下：

// 初始化一個長度為 5 的陣列 array
int[] array = new int[5];
// 元素賦值
array[0] = 2;
array[1] = 3;
array[2] = 1;
array[3] = 0;
array[4] = 2;

或者可以使用直接賦值的初始化方式，代碼如下：

int[] array = {2, 3, 1, 0, 2};

可變陣列

可變陣列是經常使用的資料結構，其基于陣列和擴容機制實作，相比普通陣列更加靈活，常用操作有：訪問元素、添加元素、洗掉元素，

// 初始化可變陣列
List<Integer> array = new ArrayList<>();

// 向尾部添加元素
array.add(2);
array.add(3);
array.add(1);
array.add(0);
array.add(2);

鏈表

鏈表以節點為單位，每個元素都是一個獨立物件，在記憶體空間的存盤是非連續的，鏈表的節點物件具有兩個成員變數：「值 val」，「后繼節點參考 next」，

class ListNode {
    int val;       // 節點值
    ListNode next; // 后繼節點參考
    ListNode(int x) { val = x; }
}

如下圖所示，建立此鏈表需要實體化每個節點，并構建各節點的參考指向，

// 實體化節點
ListNode n1 = new ListNode(4); // 節點 head
ListNode n2 = new ListNode(5);
ListNode n3 = new ListNode(1);

// 構建參考指向
n1.next = n2;
n2.next = n3;

堆疊

堆疊是一種具有 「先入后出」 特點的抽象資料結構，可使用陣列或鏈表實作，

Stack<Integer> stack = new Stack<>();

如下圖所示，通過常用操作 「入堆疊 push()」,「出堆疊 pop()」，展示了堆疊的先入后出特性，

stack.push(1); // 元素 1 入堆疊
stack.push(2); // 元素 2 入堆疊
stack.pop(); // 出堆疊 -> 元素 2
stack.pop(); // 出堆疊 -> 元素 1

注意：通常情況下，不推薦使用 Java 的 Vector 以及其子類 Stack ，而一般將 LinkedList 作為堆疊來使用，

LinkedList<Integer> stack = new LinkedList<>();

stack.addLast(1);   // 元素 1 入堆疊
stack.addLast(2);   // 元素 2 入堆疊
stack.removeLast(); // 出堆疊 -> 元素 2
stack.removeLast(); // 出堆疊 -> 元素 1

佇列

佇列是一種具有 「先入先出」 特點的抽象資料結構，可使用鏈表實作，

Queue<Integer> queue = new LinkedList<>();

如下圖所示，通過常用操作 「入隊 push()」,「出隊 pop()」，展示了佇列的先入先出特性，

queue.offer(1); // 元素 1 入隊
queue.offer(2); // 元素 2 入隊
queue.poll();   // 出隊 -> 元素 1
queue.poll();   // 出隊 -> 元素 2

樹

樹是一種非線性資料結構，根據子節點數量可分為 「二叉樹」 和 「多叉樹」，最頂層的節點稱為 「根節點 root」，以二叉樹為例，每個節點包含三個成員變數：「值 val」、「左子節點 left」、「右子節點 right」 ，

class TreeNode {
    int val;        // 節點值
    TreeNode left;  // 左子節點
    TreeNode right; // 右子節點
    TreeNode(int x) { val = x; }
}

如下圖所示，建立此二叉樹需要實體化每個節點，并構建各節點的參考指向，

// 初始化節點
TreeNode n1 = new TreeNode(3); // 根節點 root
TreeNode n2 = new TreeNode(4);
TreeNode n3 = new TreeNode(5);
TreeNode n4 = new TreeNode(1);
TreeNode n5 = new TreeNode(2);

// 構建參考指向
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;

圖

圖是一種非線性資料結構，由 「節點（頂點）vertex」 和 「邊 edge」 組成，每條邊連接一對頂點，根據邊的方向有無，圖可分為 「有向圖」 和 「無向圖」 ，

如下圖所示，此無向圖的 頂點 和 邊 集合分別為：

• 頂點集合： vertices = {1, 2, 3, 4, 5}
• 邊集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

表示圖的方法通常有兩種：

1、鄰接矩陣： 使用陣列 verticesvertices 存盤頂點，鄰接矩陣 edgesedges 存盤邊；edges[i][j] 代表節點 i + 1和節點 j + 1之間是否有邊，

int[] vertices = {1, 2, 3, 4, 5};
int[][] edges = {{0, 1, 1, 1, 1},
                 {1, 0, 0, 1, 0},
                 {1, 0, 0, 0, 1},
                 {1, 1, 0, 0, 1},
                 {1, 0, 1, 1, 0}};

2、鄰接表： 使用陣列vertices存盤頂點，鄰接表edges存盤邊， edges為一個二維容器，第一維 i 代表頂點索引，第二維 edges[i] 存盤此頂點對應的邊集和；例如 edges[0] = [1, 2, 3, 4]代表 vertices[0]的邊集合為 [1, 2, 3, 4]，

int[] vertices = {1, 2, 3, 4, 5};
List<List<Integer>> edges = new ArrayList<>();

List<Integer> edge_1 = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
List<Integer> edge_2 = new ArrayList<>(Arrays.asList(0, 3));
List<Integer> edge_3 = new ArrayList<>(Arrays.asList(0, 4));
List<Integer> edge_4 = new ArrayList<>(Arrays.asList(0, 1, 4));
List<Integer> edge_5 = new ArrayList<>(Arrays.asList(0, 2, 3));
edges.add(edge_1);
edges.add(edge_2);
edges.add(edge_3);
edges.add(edge_4);
edges.add(edge_5);

鄰接矩陣 VS 鄰接表 ：

鄰接矩陣的大小只與節點數量有關，即N^2，其中N為節點數量，因此，當邊數量明顯少于節點數量時，使用鄰接矩陣存盤圖會造成較大的記憶體浪費，因此，鄰接表 適合存盤稀疏圖（頂點較多、邊較少）；鄰接矩陣適合存盤稠密圖（頂點較少、邊較多），

散串列

散串列是一種非線性資料結構，通過利用 Hash 函式將指定的 「鍵 key」 映射至對應的 「值 value」 ，以實作高效的元素查找，

設想一個簡單場景：小力、小特、小扣的學號分別為 10001, 10002, 10003 ，現需求從「姓名」查找「學號」，

則可通過建立姓名為 key ，學號為 value 的散串列實作此需求，代碼如下：

// 初始化散串列
Map<String, Integer> dic = new HashMap<>();

// 添加 key -> value 鍵值對
dic.put("小力", 10001);
dic.put("小特", 10002);
dic.put("小扣", 10003);

// 從姓名查找學號
dic.get("小力"); // -> 10001
dic.get("小特"); // -> 10002
dic.get("小扣"); // -> 10003

自行設計 Hash 函式：

假設需求：從「學號」查找「姓名」，

將三人的姓名存盤至以下陣列中，則各姓名在陣列中的索引分別為 0, 1, 2，

String[] names = { "小力", "小特", "小扣" };

此時，我們構造一個簡單的Hash函式（%為取余符號），公式和封裝函式如下所示：

hash(key) = (key - 1) % 10000

int hash(int id) {
    int index = (id - 1) % 10000;
    return index;
}

則我們構建了以學號為 key 、姓名對應的陣列索引為 value 的散串列，利用此 Hash 函式，則可在 O(1) 時間復雜度下通過學號查找到對應姓名，即：

names[hash(10001)] // 小力
names[hash(10002)] // 小特
names[hash(10003)] // 小扣

以上設計只適用于此示例，實際的 Hash 函式需保證低碰撞率、
高魯棒性(健壯性)等，以適用于各類資料和場景，

堆

堆是一種基于 「完全二叉樹」 的資料結構，可使用陣列實作，以堆為原理的排序演算法稱為 「堆排序」 ，基于堆實作的資料結構為 「優先佇列」 ，堆分為 「大頂堆」 和 「小頂堆」 ，大（小）頂堆：任意節點的值不大于（小于）其父節點的值，

完全二叉樹定義： 設二叉樹深度為 k ，若二叉樹除第 k 層外的其它各層（第 1 至 k?1 層）的節點達到最大個數，且處于第 k 層的節點都連續集中在最左邊，則稱此二叉樹為完全二叉樹，

如下圖所示，為包含 1, 4, 2, 6, 8 元素的小頂堆，將堆（完全二叉樹）中的結點按層編號，即可映射到右邊的陣列存盤形式，

通過使用「優先佇列」的「壓入 push()」和「彈出pop()」操作，即可完成堆排序，實作代碼如下：

// 初始化小頂堆
Queue<Integer> heap = new PriorityQueue<>();

// 元素入堆
heap.add(1);
heap.add(4);
heap.add(2);
heap.add(6);
heap.add(8);

// 元素出堆（從小到大）
heap.poll(); // -> 1
heap.poll(); // -> 2
heap.poll(); // -> 4
heap.poll(); // -> 6
heap.poll(); // -> 8

標籤：其他

上一篇：1003 我要通過！（20分）

下一篇：NTP授時服務器是如何讓計算機時間同步的？