Day 01 七天學會基本演算法（一）踏入演算法學習前應該了解的資料結構

前言

了解演算法之前，我們應該先從基本的資料結構開始理解，之後在程式的設計上才能更加熟練應該要使用何種資料結構，本篇內容會介紹最基本的資料結構，包含陣列、鏈結串列、堆疊、佇列、樹、圖。

何謂資料結構？

資料結構是資料在電腦中儲存、組織的方式，當我們在寫程式時，要先規劃好我們會使用到的資料該用什麼方式去表示，而學習良好的資料結構可以幫助我們讓程式跑起來更有效率。

資料結構就是當資料進到電腦時，我們運用什麼樣的邏輯去處理這些資料，並決定資料在電腦中的順序及記憶體中的位置。就好比說我們在選擇裝水的容器時，會選擇以「杯子」去裝，選擇裝書的時候則會選擇「箱子」去裝，而如何為資料選擇一個良好的方式去儲存，就是我們應該學習的。

資料結構的型態

資料結構分為三種型態：

ㄧ、基本資料型態(Primitive Data Type)

基本資料型態也稱為純量資料型態，此種資料型態不能以其他型態來定義，如：boolean, int , char，你沒有辦法用整數int去定義一個char的字元資料。

二、結構化資料型態(Structured Data Type)

又稱為虛擬資料型態，比基本資料型態更高一層，如：字串(string) 陣列(array)

三、抽象資料型態(Abstract Data Type, ADT)

ADT是一種值的集合，只定義出數學和操作的概念，並不實際寫出實作的方法，例如Stack就是一種ADT，每個人寫的Stack或許寫法不同，但實現的功能基本上是相同的。

超人氣資料結構

（一）陣列(Array)

陣列是最為人知的資料結構了，尤其剛開始接觸程式的人都會碰到陣列這塊，陣列的結構為一排緊密相鄰的可數記憶體，提供一個能直接存取任意資料內容的計算方法。主要特點有以下：

• 通常用來儲存有序串列的相同資料於連續記憶空間
• 記憶體的配置是在編譯的時候完成
• 須事先宣告固定的記憶體空間，因此容易造成記憶體浪費
• 讀取與修改串列的資料時間是固定的
• 刪除或加入新元素需要移動大量資料

陣列可以用一排房屋來比喻，就像是一條路上的房屋們，每個房子代表一個儲存空間，房子的住址就是索引，只要知道住址，就能很輕易地找到房子，相對的，因為房子是剛開始就配置好，想要增加或移動當然也很困難。

（二）鏈結串列（Linked List）

鏈結串列算是稍微進階一點的資料結構，由相同資料型態按造特定的順序排列而成的線性串列。特點有下：

• 記憶體位置不連續，以隨機的方式儲存
• 因為不用事先定義好一塊連續的記憶體空間，所以插入或刪除資料都很方便
• 分為單向鏈結串列與雙向鏈結串列
• 每個節點知道下一個節點位置，但無法知道上一個節點位置，所以當想查詢特定節點時，必須從頭節點開始走訪

以下是在java中常見的Linked List的形式：

// 創建一條以String組成的Link
LinkedList<String> link = new LinkedList<String>();
// 新增資料
link.add("大雄"); 
link.add("小夫");
link.add("多拉A夢");

// 使用Iterator 協助我們造訪每個node
Iterator it = link.iterator();
// 如果link後面還有節點就print出名字
while(it.hasNext()){
    System.out.print(it.next() + " ");
}
// print出 大雄 小夫 多拉A夢

（三）堆疊（Stack）

堆疊是一群相同資料的組合，將所有動作都放置在頂部進行操作，概念就像餐廳內的盤子一樣，一個一個疊起來，而要取用時就取最上面那一個，堆疊具有以下特性：

• 只能從頂端存取資料
• 後進先出的原則
• 屬於抽象資料型態
• 只需一個指標：top

四種常見的操作：

• push：存放資料至頂端，回傳新的堆疊
• pop ：刪除頂端資料，並回傳新的堆疊
• isEmpty：判斷堆疊是否為空
• full：判斷堆疊是否為滿

// 創建Stack
Stack<String> st = new Stack<String>();
// 新增資料
st.push("大雄");
st.push("小夫");

System.out.print(st.pop()); // 將st最上面pop出來，因此print: 小夫
System.out.print(st.pop()); // print: 大雄

（四）佇列（Queue）

佇列就好比到餐廳的排隊，先到的人先點餐，常被使用在CPU的工作排程、先廣後深搜索法（BFS)，其特性如下：

• FIFO,先進先出特性
• 需兩個指標，一個在前端(front)一個在尾端(rear)

四種常見的操作：

• add ： 將新的資料加入佇列中
• delete：刪除佇列前端的資料
• front：傳回佇列前端的值
• empty：判斷佇列是否為空

// LinkedList類實現了Queue接口，因此我們可以把LinkedList當成Queue來用。
Queue<String> queue = new LinkedList<String>();
// 添加元素
queue.offer("a"); // [a]
queue.offer("b"); // [a,b]
queue.offer("c"); // [a,b,c]
for(String q : queue){
    System.out.println(q);
}
// print出
a
b
c

// 查看頭元素，使用peek方法返回頭元素
String accessedNumber = queue.peek();
System.out.println(accessedNumber); // print出 a

樹狀結構

樹狀結構是一種非線性結構，廣泛應用於日常生活中，例如：組織架構，籃球賽程、公司組織等，因為畫出來的外型很像樹，所以我們叫它樹狀結構。

樹（Tree）

由一個或以上的節點（Node）組成，最頂部的節點稱為樹根（Root），這些節點是什麼呢？其實就想像成是資料，樹的節點可以互相連結但不能有迴圈，以下是關於樹結構的專有名詞（請搭配下面的樹狀圖）：

• 分支度（Degree）：每個節點有多少個子節點。
  • F的分支度為2，A的分支度為0。
• 階層（Level）：樹的層級，通常樹根所在的那一層為第一層。
  • F為Level 1，C則為Level 3。
• 高度（Height）：樹的最大階層數。
  • 此樹之高度為4
• 父節點（Parent）：每個節點有連結的上一層父節點，每個Node只有一個以內的父節點。
  • B之父節點為F
  • C之父節點為D
• 子節點（Children）：每個節點有連結的下一層節點，每個Node的子節點不一定相同。
  • D有C、E兩個children
• 祖先和子孫：祖先為樹根到該點前所有的節點，子孫為該節點往下的子樹中的任一節點。
  • H的祖先有 I、G、F
  • 除了F外的所有點皆是F的子孫
• 兄弟節點：具有同一個父親的子節點
  • C和E、A和D

二元樹（Binary Tree)

二元樹是由分支度小於或等於2的節點組成，也就是說每個節點最多只能有兩個子節點，它具有以下特點：

• 樹不可以為空集合，但二元樹可以

• 樹的分支度為d>=0，但二元樹則為0 <= d <= 2

• 樹並沒有順序關係，但二元樹有，如下圖兩棵二元樹是不同的。

圖形結構

圖是由點、邊組成，通常用G=(V,E)表示，V是節點（Vertice），E是邊(Edge)，圖可以分成有向圖與無向圖，無向圖以(V1,V2)表示，有向圖以<V1,V2>表示。

無向圖

下面這張圖就是典型的無向圖，兩個頂點具備同一條邊，並沒有誰指向誰的問題。

我們可以用下列方式來表示：

V = {A,B,C,D,E}
E = {(A,B),(A,E),(B,C),(B,D),(C,D),(C,E),(D,E)}

有向圖

有向圖則是每個邊是有次序的方式來表示< A,B >指的即為A指向B，與< B, A >，B指向A是不相同的，以下列圖表示：

V = {A,B,D,E}
E = {<A,B>,<B,D>,<D,A>,<A,E>}

下集預告

熟話說好的基礎是成功的基石，當我們能熟練運用好的資料結構時，再加上演算法，程式效能將能大幅提升，明天我將敘述關於演算法的基礎-複雜度的概念與費波那契數列的相關問題。