將資料以最有利的型態存放在記憶體內,以備電腦處理,並提供一些策略使電腦能最有效率地,從記憶體內存取這些資料,這些資料的關係和存取策略就稱為資料結構。
使用連續的記憶體空間,依照特定順序來儲存資料,是許多資料結構的發展基礎。
關於陣列的實作,在C語言有內建Array
型別、Python有內建List
型別。
優點:
缺點:
鏈結串列 (Linked-list)
是不使用連續的記憶體空間的情況下,將許多資料,依特定順序排列而成的線性串列。
資料
與指標
實作方式是每個節點除了記錄資料之外,還使用額外的指標指向下一個節點,將節點以此方式串連起來形成一個連結串列。
鏈結串列(Linked-List)
的優點:單向 | 雙向 | |
---|---|---|
非環狀 | 單向鏈結串列 | 雙向鏈結串列 |
環狀 | 單向環狀鏈結串列 | 雙向環狀鏈結串列 |
單向鏈結串列,每個節點只有一個指標,指向下一個節點。
適合存放稀疏多項式,節省記憶體空間。
雙向鏈結串列,每個節點有兩個指標,分別指向上一個跟下一個節點。
比起單向鏈結串列,指標可以往前面節點移動,不需重新掃描。
倘若該鏈結串列末端節點的指標指向第一個的節點,形成一個循環,稱為環狀鏈結串列
一個m×n的矩陣是一個由m列(row)、n行(column)元素置換成的矩形陣列。
矩陣裡的元素可以是數字、符號或數學式。
以下是一個由6個數字元素構成的2列3行的矩陣:
矩陣常見運算與操作包括:
一群相同資料型態的組合,具備以下特性:
後進先出(Last-In First-Out, LIFO)
的特性create
: 建立空堆疊push
:加入新元素到堆疊頂端pop
:刪除堆疊的頂端元素isEmpty
:判斷堆疊是否為空full
:判斷堆疊是否已滿例如桶裝的品客洋芋片,最先放進去的洋芋片,最後才會被拿到。
一群相同資料型態的組合,具備以下特性:
尾端(rear)
, 前端(front)
先進先出(First-In First-Out, FIFO)
的特性create
: 建立空佇列add
:加入新元素到佇列尾端(rear)
,傳回新佇列delete
:刪除佇列的前端(front)
元素,傳回新佇列front
:判斷佇列前端(front)
的值empty
:判斷堆疊是否已滿例如買門票的隊伍,買完票的人先離開隊伍,後面來的人從隊伍後面加入。
樹(Tree)
由一個或一個以上的節點(Node)
所構成,基本定義如下:
Node
:包含資料(data)
與指標(pointer)
Root
: 樹的起始節點樹的特性如下:
Degree
: 每個節點的子樹個數Level
:樹的層級Height
: 樹的最大層級Leaf
:Degree為零的節點,也就是沒有child/subtree我們用這棵樹來舉例示意:
父母節點(Parent)
: 某個Node指向的Node,例如Node1是Node4的Parent
子節點(Child)
: 某個Node被某個Node指向,例如Node4是Node1的Child
祖先節點(Ancestor)
: 從某個Node出發,所有能夠以「尋找parent」的方式找到的node,皆稱為該Node的Ancestor
,例如Node2, Root都是Node5的Ancestor
子孫節點(Descendant)
: 從某個Node出發,所有能夠以「尋找child」的方式找到的node,Descendant
,例如Node1~Node7都是Root的Descendant
兄弟節點(Siblings)
: 擁有相同parent的node們,例如Node5和Node6圖(Graph)
是由頂點
跟邊
所組成的集合,主要用於最短路徑搜尋、拓墣排序、或是計算交通網路。
通常用G=(V,E)來表示。
其中 V是頂點的集合,E是邊的集合,有兩種類型:
G1 = (V1, E1)
V1 = {A,B,C,D}
E1 = {(A,B),(A,C),(A,D),(B,D)}
G2 = (V2, E2)
V2 = {A,B,C,D}
E2 = {<A,B>,<A,C>,<A,D>,<B,D>}
資料結構與演算法