除了連續儲存的儲存方式之外，本章將探討電腦主記憶體其他存放資料的方式，所以主題會是資料結構，而其目的是讓使用者能以抽象化工具的形式來存取資料而非強迫使用者了解資料在記憶體中的排列方式。

基本資料結構

首先先介紹一些在後續個章節中會作為範例的基本資料結構，集合資料並抽象化為串列結構或其他結構，這些方法都是解題方案中常用的工具。

陣列與聚合資料

陣列 (array) 是矩形資料塊且每個資料都具有相同的型別，最簡單的形式是一維陣列，亦即所有資料排列成一排且每項都以索引值來標示其位置，二維陣列包含數列與數行其位置是兩個索引值標示，第一個索引標示位置相對應的列數而二個索引標示相對應的行數。

聚合類型 (aggregate type) 是可能具有不同類型和大小的資料塊，在資料塊中的資料通常稱為欄位 (field)，例如表示某員工的資料塊，欄位可能包含員工姓名(字串)、年齡(整數)和技術等級(浮點數)，聚合資料的欄位通常以欄位名稱存取而非數值形式。

串列、堆疊和佇列

串列 (list)

另一種基本資料結構稱為串列 (list)，是一群有序的資料串，串列的起點位置稱為串列的頭部 (head) 而另一端稱為尾部 (tail)。

堆疊 (stack)

堆疊 (stack) 是一種只能在頭部進行新增與刪除的串列，比如一疊書中要新增或移除新的書都只能從這疊書的最上面進行操作，一般將堆疊的頭部稱為頂部 (top) 而尾部稱為底部 (bottom) 或 基底 (base)，在頂部新增一個資料的動作稱為推入 (pushing) 而在頂部移除一個資料的動作稱為彈出 (popping)，要注意的是無論是加入或移除都只能對第一項數據進行操作，因此堆疊被認為是後進先出 (last-in first-out, LIFO)

這種 LIFO 的特性很適合處理儲存或取出順序顛倒的資料，因此堆疊通常用來作為回朔操作的資料結構，回朔 (backtracking) 是指以進入的相反次序退出的程序。

佇列 (queue)

佇列 (queue) 是一種只能在頭部移除資料並只能在尾部新增資料的串列，比如排隊的隊伍，最先處理的是隊伍中的第一位而新來排隊的需要排在隊伍的最後方，這種結構稱為先進先出 (first-in first-out, FIFO)，佇列通常被用來當緩衝區背後的資料結構，緩衝區是當資料要從一個位置傳送到另一個位置時所放置的暫時區域，當資料頂部放置於緩衝區後他們會被放置在佇列的尾端，然後當資料要轉移到最後目的地時會以佇列儲存的順序轉移到最後目的地，因此資料會以相同順序轉移到目的地。

樹

數 (tree) 是一群有階層組織的資料項像一般公司的階層圖一樣，樹中的每個位置稱為節點 (node)，在頂部的節點稱為根節點 (root node)，而最底層的節點稱為終端節點 (terminal node) 或葉節點 (leaf node)，通常會將從根節點到葉節點的最長路徑稱為深度 (depth)。

有時會把樹的某個節點看做可生出下一層的節點，所以會將緊鄰的下層節點當作子輩 (children) 並且將緊鄰的上層結點當作父輩 (parent)，此外還會將具有相同父輩的其他節點稱為兄弟 (sibling)，樹中每個父節點最多只能有兩個子節點的樹稱為二元樹 (binary tree)。

如果某個節點旗下的所有節點也具有數的結構的話，我們稱這個小的樹叫做子樹 (subtree)，因此每個子節點都是該子樹的根，每個這樣的子樹都是父節點底下的一個分支 (branch)。

資料相關概念

本章會探討與資料結構相關的三個課題: 抽象化, 靜態與動態結構的差異與指標的概念。

抽象化

電腦中的主記憶體並非如陣列, 串列, 堆疊, 佇列和樹的結構，他的組織方式是連續的記憶體儲存單元，因此必須要靠模擬的方式來產生所有其他的結構，所以剛剛提到的資料結構都是抽象化的工具，以便使用者可以以更便利的形式存取資訊而不用在意資料實際儲存的方式。

所以的使用者並不一定是人，若當狀況是某個人使用電腦記錄一些數據的話，使用者就會是人，在這個狀況下使用者應用的軟體就必須以抽象化形式來表達其資料以便使用者使用，若當這個情況是網際網路的伺服器時，使用者就會是用戶端，這種情況下伺服器就必須以抽象化形式來表達其資料以便使用者使用，所以使用者並不一定是人，而是看使用的狀況與場景。

靜態與動態結構

建構抽象化資料結構有一個重要的差異就是要模擬的結構是靜態的還是動態的，也就是說這個資料結構的大小會不會隨時間有所變動，一般來說靜態結構會比動態結構還要好處理，若結構是靜態的就只需要提供一種方式來存取各項資料，或提供另一種方式來更改指定資料的儲存值，但如果是動態的話就必須要處理新增與刪除資料的問題，以尋找所需要的記憶體空間以跨大資料結構。

垃圾回收 (garbage collection): 將未使用的儲存空間回收以作為未來使用的過程稱為垃圾回收 (garbage collection)，垃圾回收有些細微的問題，比如說在使用鏈結結構的情況下，每次指標內容更改時就必須要決定是否要回收原先指標指向的儲存空間，這樣的問題非常複雜，而不精確的垃圾回收會導致資料的流失或儲存空間減少，所以如果垃圾回收沒有將未使用的空間回收的話就會讓可用空間減少，這種情況稱為記憶體洩漏 (memory leak)。

指標

電腦主記憶體的儲存單元是以數值型態的位置來標示，因為是數值型態所以這些位置本身可以進行編碼並儲存於記憶體儲存單元中，而指標(pointer) 就是用來儲存這種編碼位置的儲存區，在資料結構中指標是用來記錄資料儲存的位置，所以指標總是指向某一筆資料或是空的記憶體，簡單來說指標是指向門牌號碼，而這個門牌裡面可能有住人(有資料)或沒有住人(空的)，在前面介紹 CPU 的時候有提到程式計數器是用來儲存下一個要執行的指令的位置，這個就是指標，實際上程式計數器也叫做指令指標 (instruction pointer)，很多近代的程式語言的基本型態都包含了指標，也就是說這些程式語言允許宣告、配置和操作指標。

資料結構實作

在前面幾章中介紹了資料結構應如何儲存在電腦的主記憶體中，這些資料結構在高階程式語言中是基本的結構，接著要來了解如果使用了這些結構是如何將他們轉換為機械語言以及處理儲存於主記憶體的資料。

陣列儲存

在一個靜態結構的陣列中，陣列的大小不會因為任何原因發生變化，所以在主記憶體中會保留一個固定大小的連續儲存空間，接著資料會從記憶體空間的第一個位置開始儲存資料，將第一列的所有資料儲存在記憶體中，按照相同的方式在儲存下一列，這種儲存方式稱為以列為優先法 (row major order)，另一種是以行為優先法 (column major oeder) 這就是一行接著一行的儲存資料。

如果每列為 5 個元素的話，我們希望要找到第三列的四行的資料，我們需要先經過第一列與第二列，這樣才能到達目標第三列，接著要跳過第一道第三行才能到目標第四行，所以我們需要跳過 5(一列五個) * 2(跳過兩列) + 3(跳過三行) = 13 個元素，根據上面的算法可以有一個公式用於計算，如果我們以 c 代表陣列行數，則第 i 列與 j 行資料的位置將是

x + (c * (i - 1)) + (j + 1)

上面的 x 第一列第一行資料所在的儲存單元位置，也就是說需要聽過 i - 1 列以到達目標列數，而每個列包含 c 個資料，所以要再跳過 j + 1 個資料向才能達到目標行數，上面的例子中 c = 5, i = 3, j = 4，若起始位置設為 x 則要到第三列第四行的話需要聽過 x + (5 * 2) + 3 = x + 13，這就跟我們剛算的結果一樣，而 (c * (i - 1)) + (j - 1) 有時候被稱為地址多項式 (address polynomial)。

串列儲存

如果要在記憶體中儲存名字，方法之一是將整個名字的串列儲存在一個連續的記憶體中就跟陣列一樣，將整個串列儲存在一個很大的記憶體區塊中，每個資料項都相繼的儲存於連續的記憶體儲存單元中，這樣的排列方式稱為連續串列 (contiguous list)，連續串列在靜態串列中非常好用，不過如果要儲存動態串列的話就會有問題，當對串列進行新增會刪除的話會導致資料花費很多時間在重新排列，最壞的情況下可能會導致整個串列都要移動到新加入內容的後面，這樣就會在背地做很多額外的工作導致效能降低。

如果允許串列的每個資料都儲存在記憶體的不同位置而不是一定要連續的儲存在一起的話就可以解決這個問題，以前面要儲存名字的例子來說，我們可以將名稱設定不能超過 8 個字元，接著將這 8 個字元放進 9 個連續的記憶體儲存單位中，而空出來的那個位元則作為指標，他會指向下一個名稱的記憶體位置，這樣串列就可以散佈在整個記憶體中而不用一定要連續存放，這種串聯方式稱為鏈結串列 (linked list)。

為了要保有鏈結串列的起始位置，這時就需要另一個指標用來儲存第一筆資料向的位置，將這個指標稱為頭部指標 (head pointer)，而為了要標記串列的尾端則需要使用一個空指標 (null point)，他是放在串列的最後一項只是一個特殊位元的字串。

剛剛提到的需要新增或刪除項目，在鏈結串列中只需要改變一個指標值就可以刪除或新增一個項目，已刪除為例，如果要刪除某項的話只需要將指標移動到要被刪除項目的下一項即可，這樣當走遍整個串列時，因為沒有指標指向被刪除的資料項所以就會跳過他。

如果是新增的從擇需要選擇一塊沒被使用的記憶體儲存單元，將大小定義成跟其他連結一樣大，然後將要插入位置的前一筆資料的指標指向新增的資料，而新增資料的指標就指向原先指向的資料位置即可

堆疊與佇列儲存

堆疊

為了儲存堆疊和佇列可以使用類似連續串列的方式，在堆疊中需要保留一塊足夠大的記憶體空間以應付最大的堆疊情況，在記憶體的區塊的某一端指定為堆疊的基底，這個是第一個資料被放入的地方，之後的每一項資料都會被存在前一下的下個位置，因此堆疊會往記憶體區塊的另一個方向除件增加。

當有資料被 pushing 或 popping 堆疊時，頂部位置會跟著在記憶體區塊的儲存單元中來回移動，因為當有新資料被 pushing 近來頂部位置就必須要移動到最新資料的記憶體位置上，相對的如果 popping 了資料那麼頂部就需要移動到下一筆資料的記憶體位置上，為了知道頂部所在的位置，頂部位置的地址會儲存在另一個記憶體中，稱為堆疊指標 (stack pointer) 亦即堆疊指標是指向堆疊頂部的指標。

上圖為堆疊的完整結構，他的運作會是：要推入一個新的資料需要將堆疊指標指向堆疊頂部的下一個位置然後將新資料存入堆疊頂部的位置，而如果要彈出一個資料則需要先讀出堆疊指標所指向的位置資料值然後將堆疊指標指向堆疊頂部的前一個位置。

佇列

佇列的傳統實作方法跟堆疊很像，一樣要保留一塊夠大的記憶體空間以應付最大的佇列，但是在佇列操作中需要在兩端進行操作因此需要預留兩個記憶體單元作為頭尾的指標，其中一個稱為頭部指標 (head pointer) 而指向尾部的指標稱為尾部指標 (tail pointer)，當佇列為空時頭尾兩個指標會指向同個位置，每次要儲存一個新資料資料會被存入尾部指標的位置，然後尾部指標會指向下一個未使用的位置，因此尾部指標總是會指向佇列尾部第一個空位，而從佇列中移除資料的話要先讀出頭部指標所指出的位置的資料，然後從頭部指標值指向佇列的下一個資料。

佇列的儲存方式會有一個問題，那就是隨著資料的增加與刪除會讓整個佇列在記憶體中不斷移動，因此需要某個方法將佇列侷限在某段記憶體中，這個方法其實很簡單就是當著列的尾部達到記憶體區塊的末端時，把之後新增的資料存在記憶體另一端空白的區域(因為佇列尾部指標會隨著資料刪除而往前移動)，這樣就可以讓頭部指標重新指回記憶體區塊的初始位置，這種方式稱為環形佇列 (circular queue)。

二元樹儲存

二元樹的每個節點最多只有兩個子輩，他的結構與鏈結串列差不多但不一樣的是二元樹的資料結構會有三個元素：資料, 指向該節點的第一個子輩節點, 指向該節點的第二個子輩節點，通常會將第一個指標當作左子輩指標 (left child point) 而另一個稱為右子輩指標 (right child point)，不過這只是方便我們記憶，實際上電腦的記憶體是沒有左右之分的。

要儲存樹狀結構首先需要有一塊足夠大的記憶體區塊，接著以二元樹來說每個節點需要指向自己的左子輩指標和右子輩指標，如果沒有子輩節點的話要把它指定為空值(表示這個節點是終端節點)，還需要預留一個記憶體位置用於儲存跟節點的位置，稱為根指標 (root pointer)。

另一種儲存二元樹的方式是將他儲存在連續的記憶體儲存空間中，將根節點儲存於第一個位置，接著將根節點的左子輩與右子輩儲存在第二與第三個記憶體中，接著每個節點的子輩的左右子輩分別存於 2n 和 2n+1 個儲存位置，而記憶體中沒有儲存的位置會以特殊位元字串表示該位置沒有資料。

以上面的圖為例，A 是根節點所以會儲存在記憶體的第一個位置，接著 B 和 C 是根節點的左右子輩所以分別放在第二與第三個位置，接著由於 D 是 B 節點的左子輩指標所以他存放的位置是 2 * 2 = 4，相對的 E 是右子輩指標所以會存放在 2 * 2 + 1 = 5，所以如果 E 節點也有左右子輩的話那麼他們存放的位置將會是 2 * 5 = 10 和 2 * 5 + 1 = 11。

相較於第一種儲存方式，這種連續儲存的方式可以提供很有效率的找到任何節點的父節點和兄弟節點，每個子輩的父節點會是該位置除 2 的值(餘數不算)，比如上面提到的 E 的左子輩位置為 10 那麼他的父節點位置就在 10 / 2 = 5 的位置，不過如果二元樹中不是每個節點都有子輩的話那麼這種儲存方式就會變得很沒效率，因為會有很多空的直儲存在記憶體中從而佔據很多記憶體空間。

Reference

• computer science - AN OVERVIEW