認識資料結構

資料結構的定義

將資料以最有利的型態存放在記憶體內,以備電腦處理,並提供一些策略使電腦能最有效率地,從記憶體內存取這些資料,這些資料的關係和存取策略就稱為資料結構。

陣列(Array)

使用連續的記憶體空間,依照特定順序來儲存資料,是許多資料結構的發展基礎。

關於陣列的實作,在C語言有內建Array型別、Python有內建List型別。

優點:

  1. 資料的搜尋方便,可隨機讀取資料
  2. 設計時,資料結構簡單

缺點:

  1. 事先需宣告固定記憶空間,彈性小
  2. 刪除或加入資料需移動大量資料

鏈結串列(Linked-List)

鏈結串列 (Linked-list)是不使用連續的記憶體空間的情況下,將許多資料,依特定順序排列而成的線性串列。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  1. 定義:由至少一組節點(node)所構成,節點包括一組資料指標

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

實作方式是每個節點除了記錄資料之外,還使用額外的指標指向下一個節點,將節點以此方式串連起來形成一個連結串列。

  1. 使用鏈結串列(Linked-List)的優點:
  • 不需使用連續記憶體空間,不需事先指定串列大小。
  • 能夠容易的修改指標,插入或移除節點。
  1. 缺點如下:
  • 使用額外的記憶體空間紀錄節點指標。
  • 無法快速索引到某個節點,必須迭代搜索。
  1. 分類
單向 雙向
非環狀 單向鏈結串列 雙向鏈結串列
環狀 單向環狀鏈結串列 雙向環狀鏈結串列

單向鏈結串列

單向鏈結串列,每個節點只有一個指標,指向下一個節點。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

適合存放稀疏多項式,節省記憶體空間。

雙向鏈結串列

雙向鏈結串列,每個節點有兩個指標,分別指向上一個跟下一個節點。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

比起單向鏈結串列,指標可以往前面節點移動,不需重新掃描。

環狀鏈結串列

倘若該鏈結串列末端節點的指標指向第一個的節點,形成一個循環,稱為環狀鏈結串列

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

矩陣(Matrix)

一個m×n的矩陣是一個由m列(row)、n行(column)元素置換成的矩形陣列。
矩陣裡的元素可以是數字、符號或數學式。

以下是一個由6個數字元素構成的2列3行的矩陣:

[19132056]

矩陣常見運算與操作包括:

  • 加減法
  • 乘法
  • 轉置(Transpose)

堆疊(Stack)

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

一群相同資料型態的組合,具備以下特性:

  1. 所有動作均在頂端進行
  2. 具備後進先出(Last-In First-Out, LIFO)的特性
  3. 具備以下操作方式
  • create: 建立空堆疊
  • push:加入新元素到堆疊頂端
  • pop:刪除堆疊的頂端元素
  • isEmpty:判斷堆疊是否為空
  • full:判斷堆疊是否已滿

例如桶裝的品客洋芋片,最先放進去的洋芋片,最後才會被拿到。

佇列(Queue)

一群相同資料型態的組合,具備以下特性:

  1. 所有動作,都發生在兩端,分別是尾端(rear), 前端(front)
  2. 具備先進先出(First-In First-Out, FIFO)的特性
  3. 具備以下操作方式
  • create: 建立空佇列
  • add:加入新元素到佇列尾端(rear),傳回新佇列
  • delete:刪除佇列的前端(front)元素,傳回新佇列
  • front:判斷佇列前端(front)的值
  • empty:判斷堆疊是否已滿

例如買門票的隊伍,買完票的人先離開隊伍,後面來的人從隊伍後面加入。

樹狀結構(Tree)

基本定義


樹(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

圖(Graph)是由頂點所組成的集合,主要用於最短路徑搜尋、拓墣排序、或是計算交通網路。

通常用G=(V,E)來表示。
其中 V是頂點的集合,E是邊的集合,有兩種類型:

無向圖(Graph)


G1 = (V1, E1)
V1 = {A,B,C,D}
E1 = {(A,B),(A,C),(A,D),(B,D)}

有向圖(Digraph)


G2 = (V2, E2)
V2 = {A,B,C,D}
E2 = {<A,B>,<A,C>,<A,D>,<B,D>}

tags: 資料結構與演算法