新世代計算機概論 第15章　資料結構

寫程式時ㄧ定要先宣告變數的資料結構，然後才用流程控制指令來描述資料處理的方法。 資料結構(data structure)：就是資料在記憶體內的排列方式及存取方法，而演算法(algorithm)就是處理資料的方法流程。

15-1 陣列(array) 一個完整的資料結構 (data structure) 必須包含資料、相關運算的定義及函數。 陣列(array)和變數一樣是用來存放資料，不同的是陣列雖然只有一個名稱，卻能夠用來循序存放具有相同形式的資料型態的多個資料，這些資料叫做元素(element)，陣列是透過索引(index)來區分各個元素。 當陣列最多能夠存放n個元素時，表示它的長度 (length) 為n，而且除了一維 (one-dimension) 陣列之外，大部分程式語言亦支援多維 (multi-dimension) 陣列。

一維陣列的記憶體配置—A(m) 如C語言 int A[5]; VB.NET Dim A(5) As integer

VB.NET Dim A(m-1,n-1) As integer 圖15.2 Row Column n 圖15.3 宣告成m×n的二維陣列 如C語言 int A[m-1][n-1]; VB.NET Dim A(m-1,n-1) As integer

多項式CnXn+Cn-1Xn-1……+C1X1+C0X0 如何表示? 其中，n為最高冪次，Cn,Cn-1,…C1,C0為係數 陣列的應用之一：多項式表達 多項式CnXn+Cn-1Xn-1……+C1X1+C0X0 如何表示? 其中，n為最高冪次，Cn,Cn-1,…C1,C0為係數 表示成Polynomial[]=(n,Cn,Cn-1…,C1,C0) 3X5+8X4-6X2+5為例=> 3X5+8X4+0X3-6X2+0X1+5X0 =>Polynomial[]=(5,3,8,0,-6,0,5) 但如何表示5X100-1?? 如以上述方式表示，將浪費很多記憶體 可在表示結構中，增加乙個非零項數個數及將非零項之係數與冪次一併表示，即可解決上述問題，如下 Polynomial[]=(4,3,5,8,4,-6,2,5,0)

陣列的應用 存放多項式 係數 冪次

二維陣列表示法 基本上，二維陣列要化成ㄧ維陣列來儲存，對應方式有兩種，以列為主(row-major)、或以行為主(column-major)。若陣列A(1：u1，1：u2) k0 行( j ) 1 2 3 …..… u2 自己位置 １ ２ ３：： (1)以列為主： A(i,j)=k0+(i-1)u2d+(j-1)d (2)以行為主： A(i,j)=k0+(j-1)u1d+(i-1)d 列 ( i ) u1 d

若陣列A(f1：u1，f2：u2)，共有m個列、n個行， 起始位址為k0，每個元素佔d個空間； 則m=u1-f1+1，n=u2-f2+1。因此， 以列為主：A(i,j)= k0+[(i-f1+1)-1]nd+[(j-f2+1)-1]d 以行為主：A(i,j)= k0+[(j-f2+1)-1]md+[(i-f1+1)-1]d 例題：A(-4：3,-3：2)，而啟始位置A(-4,-3)=100，d=1，若採以列為主排列，試問A(1,1)所在位置值為何? Sol: m=3-(-4)+1=8 n=2-(-3)+1=6 A(1,1)=100+5×6+4=134

例題：A(-4：3,-3：2)，而啟始位置A(-4,-3)=100，d=1，若採以列為主排列，試問A(1,1)所在位置值為何? -3 -2 -1 0 1 2 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 -4 -3 -2 -1 1 2 3

存放稀疏矩陣：ㄧ個m×n的陣列，大部分的元素都是0。採3-tuple結構(列i,行j,值value)，只儲存非零項目。 15

陣列的定址方式

下三角形(lower triangular)與上三角形(upper triangular)的循序儲存方式 a11 a11 a12 a13 a14 a21 a22 a22 a23 a24 a31 a32 a33 a33 a34 a41 a42 a43 a44 a44 ㄧ個n×n的上、下三角矩陣，其元素個數共有1+2+3+…. +n=n(n+1)/2，對應到一個一維陣列B(1:n(n+1)/2)中 (A)以列為主 (a)下三角之對應關係 矩陣A a11 a21 a22 a31 a32 a33.. aij…. ann 矩陣B B(1) B(2) B(3) B(4) B(5) B(6)..B(k)…B(n(n+1)/2) 所以 aij=i(i-1)/2+j=k B(K) a33=3(3-1)/2+3=6 元素零 元素零 B(6)

所以 aij=n(i-1)-i(i-1)/2+j=k B(K) (B)以行為主 a23=4(2-1)-2(2-1)/2+3=6 矩陣A a11 a12 a13 a14 a22 a23.. aij…. ann 矩陣B B(1) B(2) B(3) B(4) B(5) B(6)..B(k)…B(n(n+1)/2) 所以 aij=n(i-1)-i(i-1)/2+j=k B(K) (B)以行為主 a23=4(2-1)-2(2-1)/2+3=6 (a)下三角之對應關係 矩陣A a11 a21 a31 a41 a22 a32.. aij…. ann 所以 aij=n(j-1)-j(j-1)/2+i=k B(K) (b)上三角之對應關係 a32=4(2-1)-2(2-1)/2+3=6 矩陣A a11 a12 a22 a13 a23 a33.. aij…. ann 所以 aij=j(j-1)/2+i=k B(K) a33=3(3-1)/2+3=6 B(6) B(6) B(6)

15-2　堆疊(stack) — S(1:n) 是一個有順序的資料列(ordered list)，所有的加入與刪除動作都發生在串列的同ㄧ端，這一端稱為頂端(top)，另ㄧ端為底端(bottom)。具有後進先出(LIFO ,last-in-first-out)特性。 在stack中加入ㄧ個元素稱為壓入(push)，刪除一個元素稱為彈出(pop)；堆疊S=(d0,d1,…dn-1,dn)，其中dn為頂端(S(n))，d0為底端(S(1))。 push pop

PUSH與POP演算法 Procedure PUSH(item,STACK,n,top) if top≧n then call STACK-FULL top top+1 STACK(top) item end Procedure POP(item,STACK,top) if top≦0 then call STACK-EMPTY item STACK(top) top top-1 /*考慮overflow,先加後擺item*/ /*考慮underflow,先拿item後減1*/

資料反轉(data reversing)：abcde edcba 回溯(backtracking)：副程式或遞迴式呼叫 堆疊經常應用於下列幾個方面： 資料反轉(data reversing)：abcde edcba 回溯(backtracking)：副程式或遞迴式呼叫 資料剖析(data parsing) 運算式表示法轉換 中序表示法 (infix)：如a+b 前序表示法 (prefix)：如+ab 後序表示法 (postfix)：如ab+ ㄧ般習慣用的中序式有運算符號優先權與結合性問題 ，而且有括號先處理的問題，在編譯處理時非常麻煩 。解決的方法是將中序式轉換為後序式表示。

使用堆疊將運算式A * (B + C) - D由中序表示法轉換成後序表示法： A*(B+C)-D {[A*(B+C) ] –D} {[A(BC)+]* D}- A B C + * D -

系統堆疊(system stack)是程式在執行期間用來處理函數呼 叫的結構，只要程式ㄧ呼叫函數，就會在系統堆疊內產 生一個包含指標、返回位址與區域變數的記錄。 系統堆疊頂端的記錄就是目前正在執行的函數，執行完畢 就會從系統頂端刪除其記錄，返回呼叫該函數的程式。

15-3　佇列(queue) – S(1:n) Queue是一個有順序的資料列(ordered list)，資料(item)的加入與刪除發生在不同端：由後端(rear)加入，前端(front)刪除，因此具有先進先出(FIFO)的特性。Queue常視為環狀結構(0:n-1, circular queue)。常應用於工作排程。 front n-1 n-2 1 . 2 . 8 3 7 4 6 5 rear

ADDQ與DELETEQ演算法 ref.15-14範例 Procedure ADDQ(item,Queue,n,front,rear) rear (rear+1) mod n /*取餘數*/ if front = rear then call QUEUE-FULL Queue(rear) item end Procedure DELETEQ(item,Queue,n,front,rear) if rear = front then call QUEUE-EMPTY front (front+1) mod n item Queue(front)

rear front front=0,rear=4 front front rear rear front=2,rear=4 front=2,rear=1

front 根據ADDQ演算法，當 front = rear時將發生overflow，由於先將rear指標加1，故事實上還有一個Q(rear)的位置。而在Queue中的第一個元素不在Q(front)，而是其順時針之下一個位置Q(front + 1)。若使用了這個位置，則在ADDQ與DELETEQ中判斷front = rear時，無法去區別是overflow或underflow。 rear 此時若欲再新增J8，是否可以?會出現何種情形? Procedure ADDQ(item,Queue,n,front,rear) rear (rear +1) mod n /*取餘數*/ if front = rear then call QUEUE-FULL Queue(rear) item end 若要使用這個空間，亦即充分用到n個位置，則在ADDQ與DELETEQ演算法應該如何改寫?

環型佇列完整ADDQ與DELETEQ演算法 Procedure ADDQ(item,Queue,n,front,rear,TAG) if front = rear and TAG = 1 then call QUEUE-FULL rear (rear+1) mod n /*取餘數*/ Queue(rear) item if front = rear then TAG 1 end Procedure DELETEQ(item,Queue,n,front,rear,TAG) if rear = front and TAG = 0 then call QUEUE-EMPTY front (front+1) mod n item Queue(front) if front = rear then TAG 0

串列(List) … 線性串列(如陣列方式) 串列是許多項目的有序組合，可分為線性串列與鏈結串列(linked list)兩種。 … 線性串列(如陣列方式) 連續記憶體位置(sequential allocation) 使用指標形成鏈結串列，來連結串列中的上下節點，每個節點(node)有兩個欄位，分別存放節點的資料(data)與指標(pointer)，也就是不必再以連續空間來儲存串列。同時，每個節點可以有1個或2個鏈結欄。 資料 鏈結 左鏈結 資料 右鏈結 Data Link Link Data

15-4　鏈結串列 15

首先，定義節點的結構與初始化，假設節點的資料欄位為整數型別 /*這個巨集用來判斷是否還有記憶體空間，若ptr為NULL，表示記憶體已滿，傳回True*/ #define IS_FULL(ptr)(!(ptr)) /*list_node是串列的節點，list_pointer是指向節點的指標*/ typedef struct list_node *list_pointer; typedef struct list_node { int data; /*節點的資料欄位*/ list_pointer link; /*節點的指標欄位*/ }; list_pointer ptr=NULL； /*初始狀態為空串列，故串列 的名稱ptr指向NULL*/

/*linked list插入新節點的insert函數*/ void insert(list_pointer *ptr,list_pointer node,int item) { list_pointer temp; /*配置大小為list_node的記憶體給temp*/ temp=(list_pointer)malloc(sizeof(list_node)); if (IS_FULL(temp)) { /*判斷temp是否full,是表記憶體不足*/ print(“Memory is full”); return; } temp -> data=item /*設定新節點的資料欄位為第三個參數的值*/ if (*ptr) { /*若ptr不是指向空串列*/ temp -> link = node -> link; /*將新節點的指標指向插入 處之節點的指標所指向的節點*/ node -> link = temp; } /*將插入處節點的指標改為指向新節點*/ else { temp -> link = NULL; /*若ptr為空串列,將新節點指標指向NULL*/ *ptr = temp; } /*串列名稱ptr改為指向新節點*/ }

/*linked list刪除節點的delete函數*/ void delete(list_pointer *ptr,list_pointer trail,list_pointer node) { if (trail) /*若trail非NULL,表示要刪除的不是第一個節點*/ trail->link = node->link; /*將trail的指標指向要被刪除之 節點的指標所指向的節點*/ else *ptr = (*ptr)->link; /*因為是刪除第一個節點，所以 串列名稱必須指向下一個節點*/ free(node); }

15

使用linked list存放多項式 資料結構可定義如下 typedef struct poly_node *poly_ptr; int coef; /*非零項的係數*/ int exp; /*非零項的冪次*/ poly_ptr link; /*非零項的指標*/ }poly_node; 多項式3X5+8X4-6X2+5使用linked list表達成 f 3 5 · 8 4 · -6 2 · 5 NULL

15-5 樹(tree) 樹是由一個或多個節點(node)所組成的有限集合 樹根(root) -- 祖先(ancestor) 子孫(descendant) 父親(parent) 孩子(child) 兄弟(sibling) 終端節點(terminal node) 內部節點(internal node) 階級(degree):該節點有幾顆子樹 層次(level) 高度(height)或深度(depth) 由於樹中每個節點的degree，常造成記憶體空間的浪費，因此將樹化為二元樹以便利儲存。

15-5-1 二元樹(binary tree) 二元樹是每個節點最多有兩個孩子的樹 對高度為h的二元樹來說，全部存滿的話，總共有20 + 21 + … + 2h-1 = 2h - 1個節點。 二元樹在第i個level的最大節點數目為2i-1 二元樹與數的差異: 1.樹沒有order關係,二元樹有. 2.樹中每一個節點的degree ,n≧0;而二元樹0≦n≦2. 3.數不可以為空集合,至少有一個樹根，二元樹可以為空集合。 left child right child 圖15.15(b)

skewed binary tree：二元樹中所有的節點都沒有left child或right child。 ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ full binary tree：ㄧ個含有其最大的節點數目的二元樹；若depth=k，含有2k-1個節點。 Complete binary tree：ㄧ個depth為k的二元樹，若含有少於2k-1個節點，而且節點的編號排列次序如同在depth為k的full binary tree。 left- skewed right- skewed

15 15

使用linked list來存放二元樹 15

如何將一般的算術式化為二元樹 考慮運算符號的優先權與結合性，適當的括弧起來 由內層括弧開始，運算符號是樹根，左邊的運算元是left child，右邊的運算元是right child，由下往上連結成二元樹狀。 將A/B**C*D+E化為二元樹 (((A/(B**C)*D)+E) + * E / D A ** B C

常見的樹狀結構運算 – 追蹤(traversal) 中序(inorder)追蹤 – 左中右 void inorder(tree_pointer ptr) { if (ptr){ inorder(ptr->lchild); printf(“%d”, ptr->data); inorder(ptr->rchild); } 圖13.15(b) 的中序追蹤的結果為DBGEHACFI。

前序(preorder)追蹤 – 中左右 void preorder(tree_pointer ptr) { if (ptr){ printf(“%d”, ptr->data); preorder(ptr->lchild); preorder(ptr->rchild); } 圖13.15(b) 的前序追蹤的結果為ABDEGHCFI。

後序(postorder)追蹤 – 左右中 void postorder(tree_pointer ptr) { if (ptr){ postorder(ptr->lchild); postorder(ptr->rchild); printf(“%d”, ptr->data); } 圖13.15(b) 的後序追蹤的結果為DGHEBIFCA。

二元樹追蹤練習 某二元樹其前序追蹤順序為ABCDEFGH，中序追蹤順序為CDBAFEHG，請繪出此二元樹結構?

二元樹追蹤練習 某二元樹其前序追蹤順序為ABCDEFGH，中序追蹤順序為CDBAFEHG，請繪出此二元樹結構? 前序:中左右 中序:左中右 前序:中左右 中序:左中右 A A A A CDB FEHG B FEHG B E B E CD C F HG C F G D D H

15-5-2 二元搜尋樹 它必須滿足下列條件： 每個節點包含唯一的鍵 (key)。 左右子樹亦為二元搜尋樹。 15-5-2　二元搜尋樹 它必須滿足下列條件： 每個節點包含唯一的鍵 (key)。 左右子樹亦為二元搜尋樹。 左子樹的鍵必須小於其樹根的鍵，右子樹的鍵必須大於其樹根的鍵。

15

(1)若欲刪除的節點為該二元搜尋樹的樹葉節點，則直接刪除該節點即可。 刪除二元搜尋樹的節點 (1)若欲刪除的節點為該二元搜尋樹的樹葉節點，則直接刪除該節點即可。 (2)若該節點為二元搜尋樹的內部節點，除了直接刪除該節點外，還要以該節點的左子樹中最大的節點、或右子樹中最小的節點填入其位置。 圖13.21

15-6　搜尋(search) 15-6-1　循序搜尋(sequential search)

15-6-2 二元搜尋(binary search)

高度平衡二元樹(AVL Tree) 高度平衡(height balanced)二元樹為Adelson-Velskii與Landis在1962年所提出，子樹的高度是平衡的(亦即左右子樹的高度差最多僅能≦1)。由於平衡的特性，所有動態的存取、節點的插入或刪除均可在O(log n)時間內完成。

高度平衡二元樹(AVL Tree) 試將5、4、3、2、1依序插入空的AVL tree，再以後續追蹤(postorder traversal)拜訪的順序為? 插入或刪除任何AVL tree上的node時，須依binary tree 節點次序且保持|hL-hR|≦1原則，否則須調整節點位置。 插入5 5 插入2 4 插入4 5 3 5 4 2 插入3 5 插入1 4 4 3 5 3 2 因高度差>1,須調整 1 因高度差>1,須調整 4 4 3 5 2 5 1 3 後序:左右中 順序為13254

15-7 排序(sort) 將ㄧ群資料按照某一個排列規則，重新安排此群資料的次序(遞增或遞增)。 傳統上，排序分為兩種，ㄧ種是內部排序法：把資料完全存放在主記憶體內作排序；另一種是外部排序法：資料太多無法完全存放於主記憶體內，必須用到外部的儲存設備，如磁帶、磁諜等來執行排序。

15-7 排序(sort) 15-7-1插入排序(insertion sort) 在一個已排序好的i筆資料陣列中，插入新的資料r，使得i+1個資料重新排序妥當。重複以上動作，直到所有資料被插入適當位置為止。

15-7-2氣泡排序(bubble sort) 將兩個相鄰資料做比較，並依大小順序作位置對調，如此將所有資料循環依次將使得至少一個資料位於正確位置。重複執行上述動作，n個資料最多需要循環n-1次。

15-7-3 快速排序(quick sort) 在所有排序法中，快速排序法是最有效的一種。 step1：取第一個資料項的鍵值k當做控制鍵。 step2：由左向右找到第一個鍵值大於k的資料項i ，且由右向左找到第1個鍵值小於k的資料項j。 step3：若i<j則將第i個資料項與第j個資料項位置對調並回到step2，否則將控制鍵資料與第j項對調，此時檔案項目將ㄧ分為二，如此兩群資料可獨立執行。

15-7-3　快速排序

外部排序法 大量資料的排序常用的方法是合併排序法(Merge Sort) 第一階段為利用內部排序法如堆積排序法(heap sort)或快速排序法(quick sort)將片段資料排好，這種排好的片斷稱為RUN。 第二階段是將第一階段所產生的各個RUN做合併排序，直到變成一個RUN為止。 做合併排序時可以利用選擇樹(selection tree)的觀念，來減少在決定下一個最小鍵值記錄所需的比較次數。選擇樹本身為一個二元樹，其中每一節點卽為其兩個兒子節點的較小者，因此在選擇樹中樹根節點必為全樹中具有最小鍵值者。

合併排序法(Merge Sort) 為將原來n筆資料項，以兩兩合併方式變成n/2個已排序好的檔案，再將此n/2個檔以兩兩合併方式變成n/4個已排序好的檔案，以此方式重複兩兩合併，最後變成一個檔案時排序卽告完成。 12 8 14 6 5 9 23 4 PASS1: 8 12 6 14 5 9 4 23 PASS2: 6 8 12 14 4 5 9 23 PASS3: 4 5 6 8 9 12 14 23

錐形排序法(Heap Sort) Step1:將欲排序之資料項陣列建成一個完全二元樹(complete binary tree)。 Step2：將完全二元樹轉換成錐形樹(heap tree)：為一個完全二元樹，其每一個父節點值均大於或等於其子節點的值，且樹根(root)為整個tree中最大。 Step3：將數根植取出放入陣列最末位置，並將樹中最後一個節點值放置數根中，重複執行step2與step3，直到僅剩下一個節點。 Step4：將處理完畢的陣列依序輸出其列值，即可得ㄧ由小而大的資料順序。

例：3、11、6、4、9、5、7、8、10、2、1 3 11 11 6 10 7 4 9 5 7 8 9 5 6 8 10 2 1 3 4 2 1 1 10 10 7 9 7 8 9 5 6 8 2 5 6 3 4 2 3 4 1 Complete binary tree Heap tree 輸出11,並將1調整至樹根 重調回Heap tree

9 8 8 7 4 7 4 2 5 6 3 2 5 6 3 1 1 7 6 5 4 4 6 4 5 4 1 3 1 3 2 5 1 3 2 1 3 2 2 3 2 1 2 1 1 輸出10 輸出9 輸出8 輸出7 輸出6 輸出5 輸出4 輸出3 輸出2 輸出1

常見排序法的主要演算法則 排序法 平均時間 最差情況 Selection O(n2) Insertion Bubble Shell O(nlogn) O(ns), 1<s<2 Merge Heap Radix O(nlogpn) O(nlogpn) ~ O(n)