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


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>}

下集預告

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

#演算法





演算法是找軟體相關工作時一定會被問到的問題,也是幫助自己寫程式更增進效能與技巧的思考方式,希望透過這個系列文撰寫基本演算法的介紹,內容包含:堆疊、排序、搜尋、分治、動態規劃等內容。

留言討論