Table of Contents
前言
第三天我們說明了什麼是抽象資料型別(Abstract Data Type, ADT),同時也介紹了8種相對常被使用的ADT,還沒有看過的朋友或是想要複習的朋友可以點擊【舌尖上的演算法】Day4 – 抽象資料型別及特性;但這些ADT畢竟只是概念,真正將ADT實作出來的物件就是所謂的資料結構(Data Structure)。
在接下來的20多天裡,我們將會針對一些比較淺顯易懂的演算法一一介紹,但是在正式開始品味這些演算法之前,我會先介紹資料結構本身,才會開始說明利用這種資料結構的演算法。今天,我會先提出兩種線性資料結構(Linear Data Structure)
的範例。
日後會再針對Binary Search Tree及HashTable做說明。
什麼是資料結構(Data Structure)?
- 上面提到ADT只是一個概念,並不是『真正』在演算法中使用的物件;既然ADT只是概念,勢必就會有將這些概念實作出來的物件,而這實作ADT的物件就是資料結構(Data Structures)。
- 資料結構用不同的方式來達到管理、儲存資料的目的。
- 一個好的資料結構可以大幅增加系統運行的效能。
- 不同類型的資料結構都有其適合的應用情境。
- 有些資料結構也可能是針對某單一應用情境下被設計實作出來的。
線性資料結構(Linear Data Structure)
線性資料結構,顧名思義,是直線性的資料結構,而這種資料結構最常被使用且最重要的就是Array
及Linked List
。
1. Array
Array
是一個1-D(one dimensional)的結構,每個Elements會有自己的indexArray
也是一個集合物件(Collection)- 基本上用來儲存相同資料型態的物件
- 儲存物件的時候具有連續性,如上圖,儲存物件的時候會依據index檢查該Element是否為空,當找到空的位置的時候,才將物件儲存在那個位置。
- 具快速存取性
Array
的三個操作模式:(1) Search:
從Array當中尋找指定的Element時,會從第0個index開始針對其Element做比較,一步一步往下查找,直到找到指定的Element才結束流程。
(2) Insertion:
當要把一個Element插入Array中指定的某一個位置時,對於這個指定位置後面的Elements來說,全部都要往後退一格。 但假設在插入這個新Element之前,Array本身的空間已經是滿的了,那就是變成要新增一個原Array長度加1的Array,然後再將Elements一個一個放進這個新Array裡面。
(3) Deletion:
從Array當中刪除指定的Element時,原本位在此Element後方的其他Elements都會往前移動一格。
2. Linked List
Linked List
的特性是每一個Node除了儲存Element之外,還包含了一個『指標』,這個指標代表的是下一個Node,也就是說,透過這個指標可以將每一個Node都串起來,形成一個List的結構。(Node = Element + Pointer)
- 在實作的時候,會有一個
head pointer
用來記錄第一個Node;有時候會另外有一個tail pointer
紀錄最後一個Node。 - 除了這種一般的
Singly Linked List
外,Linked List
還有其他種類的實作方式,其中一種是Doubly Linked List
,Double代表的是每一個Node都會記錄『前一個』和『後一個』的Node,在這邊我們不多做說明,因為在第25天的時候,我們會花比較多篇幅來介紹Doubly Linked List
,也會在第30天的時候介紹Cyclic Doubly Linked List
。 Linked List
的兩個操作模式:(1) Insertion:
因為
Linked List
是透過pointer將Node關聯起來,因此其實在改變『結構』的時候,只要做一件事:調整pointer連線的對象
。在做Insertion的時候,是將插入位置前一個Node的pointer指到New Node,再將New Node的pointer指到插入位置後一個的Node(如下圖)。(2) Deletion:
正如Insertion中提到的,我們針對要刪除的Node(B Node)的前一個Node(A Node)的Pointer做改變,只要將這個Pointer直接指定到『下一個Node(C Node)』,那這個要刪除的Node就斷開了連繫,進而被系統刪除(如下圖)。
Array
和Linked List
在程式實作中都很常被使用,很多簡單的演算法也都是透過這兩種資料結構來進行運用。
小結
- ADT畢竟只是概念,真正將ADT實作出來的物件就是所謂的資料結構(Data Structure)。
- 一個好的資料結構可以大幅增加系統運行的效能。
- 線性資料結構,顧名思義,是直線性的資料結構,而這種資料結構最常被使用且最重要的就是
Array
及Linked List
預告
接下來的數天,我們會將一些比較容易理解的演算法分類,然後再一一跟大家介紹,準備上主菜囉~
References
- Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin
- Data Structure - Wikipedia