計概：抽象資料型態與副程式

抽象資料型態

Abstract data type, ADT，就是一種容器。

堆疊 Stack

為LIFO(Last In First Out)，後進先出，即當我們要放資料時，放在最上面（也就是最後一個），要拿資料的時候也是拿最上面。

• 插入 Push
• 刪除 Pop

---

佇列 Queue

為FIFO(First In First Out)，先進先出，即當我們要放資料時，排在最後面 rear，拿資料時拿第一個 front；類似於排隊。

---

串列

項目是同性質的、線性的、可變長度的；可由陣列實現。

• 也可視為鍵結結構，基於節點 node的概念，一個接著下一個。

---

樹 Tree

二元樹

每個node有兩個後繼節點，稱作子結點 children，可一直延續下去。起始節點稱作樹根 root。
一個node 可能有0至2個節點，左邊的稱作 left child，右邊的稱作 right child；如有一個節點沒有子結點，則稱作樹葉 leaf。

二元搜尋樹 BST

如果 left child < node < right child，則此數為BST。

---

圖形 Graph

G=(V,E)，V 為圖形中的點集合，E 為編集合。
如果邊有方向，稱作有向圖，反之，則為無向圖。
若兩個邊之間存在一條邊，則稱作相鄰頂點。
兩點之間的路徑由一連串的相鄰頂點組成。

圖形演算法

• 深度優先搜索 BFS
• 廣度優先搜索 DFS
• 最短路徑搜索

---

副程式

swap(num1,num2)
temp ← num1
num1 ← num2
num2 ← temp

tags: 計算機概論