Ch1 資料結構導論
一.演算法
1.「演算法」就是解決問題的策略與法則。在計算機科學的領域中，「演算法」就是解決某一個工作或問題，所需要的一些有限個數的指令或步驟
2.在任何演算法中，首先必須滿足以下5種條件：
（1）輸入（Input）：在演算法的處理過程中，通常所輸入資料可有可無，零或一個以上皆可
（2）有效性（Effectiveness）：每個步驟都可以正確執行，即使交給不同的人用手動來計算，也能達成相同效果
（3）明確性（Definiteness）：每一個步驟或指令必須要敘述的十分明確清楚，不可含糊不清而造成混淆
（4）有限性（Finiteness）：演算法一定會在有限的步驟後結束，不會產生無窮迴路
（5）輸出（Output）：至少或有一個輸出結果
二.演算法與程式設計
1.一個程式的產生過程，可區分為以下5個設計要領：
（1）需求與目的：首先要了解程式所要解決的問題，並搜集相關的輸入資訊與期望得到的輸出結果
（2）設計與規劃：根據撰寫此程式的目的、程式的使用者、滿足需求的軟硬體環境等，來著手設計這個程式演算法的敘述
（3）分析與討論：思考其他可能適合的演算法及資料結構，最後再選出最適當的標的，當然此刻還必須考慮到可讀性、穩定性及可維護性等因素
（4）撰寫與編輯：談到程式碼的撰寫，事先必須選擇所需的程式語言，再依據演算法來繪圖流程圖，最後進行程式碼的撰寫
（5）測試與偵錯：最後必須確認程式輸出是否符合需求，並進行包括所謂「語意錯誤」、「語法錯誤」與「邏輯錯誤」等相關測試與除錯工作
三.程式設計的風格
1.由上而下與模組化設計：其主要精神與模式就是將整個問題從上而下，由大到小，逐步分解成較小的單元，這些單元稱為模組，又可再細分成更小的單元，以利撰寫與維護程式碼
2.可讀性設計：適時使用「註解」提高程式的可讀性，且程式碼中的識別字名稱定義應具體且具意義
3.控制結構設計：包含了以下3種流程控制結構
（1）循序結構（Sequential structure）：程式敘述由上而下，接著一個程式敘述的執行指令
（2）選擇結構（Selection structure）：為一種條件控制敘述，包含一個條件判斷式，如果條件為真，則執行某些程式；一旦條件為假，則執行另一些程式
（3）重複結構（Repetition structure）：主要是迴圈控制的功能。迴圈會重複執行一個程式區塊的程式碼，直到符合特定的結束條件為止
4.物件導向程式設計：包括以下特性：
（1）封裝（Encapsulation）：封裝利用「類別」來實作抽象化資料型態（ADT）；而每個類別裡有其資料成員與函式成員，我們可將其資料成員定義為private；而將用來運算或操作資料的函式成員定義為public或protected來實現資訊隱藏，這就是「封裝」
（2）繼承（Inheritance）：繼承允許我們去定義一個新的類別來繼承既存的類別，進而使用或修改繼承而來的方法，並可在子類別中加入新的資料成員與函式成員。此外，透過類別的繼承行為，能讓程式開發人員重複利用已宣告類別的成員方法；並可經由多載（override），來重新定義及強化新類別所繼承的各項執行功能
（3）多形（Polymorphism）：多形就是一樣東西同時具有多種不同的型態，它展現了動態繫結的功能，也稱為「同名異式」。多形能在該軟體於發展和維護時，達到充分的延展性。多行最直接的定義，就是它具有繼承關係的不同類別物件，可以對相同名稱的成員函數呼叫，並產生不同的結果反應
四.Java的物件導向程式設計
1.建構元（constructor）：用來建立該類別的物件，並在建立的同時設定初始值
﹡通常Java宣告基本資料型態的變數（如整數）時，會自動分配記憶體空間，但是類別型態的變數在宣告時，則必須以new指令來配置記憶體空間，但這個配置動作並不會替所建立的物件給定初值，若想在建立物件的同時給定初值，就必須借助建構元
﹡建構元的使用除了必須與類別取同樣的名稱外，也不能有任何的傳回值。每個類別可以有一個以上的建構元，這些建構元可以有不同的參數個數或資料型態，亦即建構元可以多載定義
2.資料封裝（encapsulation）：將靜態屬性數值與動態行為方法，包覆於此物件所「參考」到的類別中。主要的目的是避免物件範圍以外的程式，有任何更動或破壞內部資料的可能
3.類別繼承：衍生類別可依據本身需求，對所繼承的各種方法重新定義（overriding）。另外衍生類別中也可根據實際的需要，宣告一個和基礎類別同樣名稱，但具有不同引數狀態的方法，這種作法稱為此方法的多載（overloading）
﹡當使用衍生類別建構元建立物件時，JAVA編譯器會先去呼叫基礎類別的建構元後，才會執行衍生類別的建構元
﹡.類別繼承的存取修飾子：
（1）public：所有類別皆可存取
（2）abstract：此類別不能被實體化（建立物件）
（3）final：此類別無法再被重新定義（繼承）
4.物件多形：利用類別繼承架構的基礎，先建立一個內容為「null」的基本類別物件，讓使用者可以將它轉變成為各種衍生類別物件，進而加以控制所有衍生類別的「同名異式」方法
五.遞迴演算法
1.遞迴（Recursion）的定義：假如一個函數或副程式，是由自身所定義或呼叫的，就稱為遞迴。它至少要定義2種條件，包括一個可以反覆執行的遞迴過程，與一個跳出執行過程的出口
﹡直接遞迴（Direction Recursion）：指遞迴函數中，允許直接呼叫該函數本身
﹡間接遞迴（Indirect Recursion）：指遞迴函數中，呼叫其他遞迴函數，再從其他遞迴函數呼叫回原來的遞迴函數
﹡尾歸遞迴（Tail Recursion）：程式的最後一個指令為遞迴呼叫，因為每次呼叫後，再回到前一次呼叫的第一行指令就是return，不需要再進行任何計算工作，如此稱為尾歸遞迴
2.費伯那序列（Fibonacci Polynomial）：一序列的第零項是0、第一項是1，其它每一個序列中項目的值是由其本身前面兩項的值相加所得
3.河內塔問題：
步驟1：將n-1個盤子，從木樁1移動到木樁2
步驟2：將第n個最大盤子，從木樁1移動到木樁3
步驟3：將n-1個盤子，從木樁2移動到木樁3
六.程式效能分析
1.關於程式所需記憶體的空間量度，稱為「空間複雜度」（Space Complexity）
2.關於程式所執行的時間，可以利用一種「概量」的觀念做為衡量執行的時間，也就是一種「漸近表示」（Asymptotic Notation），是用來估算一個演算法執行所花費的大概時間，稱為「時間複雜度」（Time Complexity）
3.Big-oh：我們定義一個T(n)來表示程式執行所要花費的時間，其中n代表資料輸入量，分析演算法在所有可能的輸入組合下，最多所需要的時間，也就是程式最高的時間複雜度，稱為「Big-oh」
﹡常見的Big-oh有下列幾種：
（1）O(1)或O(c)：稱為常數時間(constant time)，表示演算法的執行時間是一個常數倍
（2）O(n)：稱為線性時間(linear time)，執行的時間會隨資料集合的大小而線性成長
（3）O(log2 n)：稱為次線性時間(sub-linear time)，成長速度比線性時間還慢，而比常數時間還快
（4）O(n^2)：稱為平方時間(quadratic time)，演算法的執行時間會成二次方的成長
（5）O(n^3)：稱為立方時間(cubic time)，演算法的執行時間會成三次方的成長
（6）O(2^n)：稱為指數時間(exponential time)，演算法的執行時間會成二的n次方成長
（7）O(nlog2 n)：稱為線性乘對數時間，介於線性及二次方成長的中間之行為模式
4.Ω(omega)：也是一種時間複雜度的漸近表示法，如果說Big-oh是執行時間量度的最壞情況，那麼Ω就是最好的情況
5.Θ(Theta) ：是一種比Big-oh與Ω更精確的時間複雜度的漸近表示法
Ch2 線性串列
一.線性串列的定義
1.線性串列（Linear List）的定義如下：
（1）有序串列可以是空集合，或者可寫成（a1,a2,a3,…,an-1,an）
（2）存在唯一的第一個元素a1與存在唯一的最後一個元素an
（3）除了第一個元素a1外，每一個元素都有唯一的先行者（precessor），例如ai的先行者為ai-1
（4）除了最後一個元素an外，每一個元素都有唯一的後繼者（precessor），例如ai的後繼者為ai+1
2.線性串列的關係本身可以看成是一種有序對的集合，目的在表現串列中的任兩相鄰元素之間的關係
3.線性串列的應用如C/C++程式中的陣列或字串結構，在電腦中是屬於記憶體中的靜態資料結構（Static Data Structure），特性是使用連續記憶空間（Contiguous Allocation）來儲存，記憶體配置是在編譯時，就必須配置給相關的變數，容易造成記憶體的浪費。
又或者如鏈結串列（Linked Lists）結構，也是在C/C++中，多半是以指標變數型態來實作線性串列的資料結構，特點是串列節點的記憶體配置是在執行時才發生，所以不需事先宣告，能充分節省記憶體，或稱為「動態記憶體配置」（Dynamic Memory Allocation）
二.陣列
1.陣列在程式語言中，可看作一群相同名稱與資料型態的集合，並且在記憶體中佔有一塊連續的記憶體空間。要存取陣列中的資料時，則配合索引值（index）尋找出資料在陣列的位置
2.陣列通常必須包含下列5種屬性：
（1）起始位址：表示陣列名稱（或陣列第一個元素）所在記憶體中的起始位址
（2）維度（dimension）：代表此陣列為幾維陣列
（3）索引上下限：指元素在此陣列中，記憶體所儲存位置的上標與下標
（4）陣列元素個數：是索引上限與索引下限的差+1
（5）陣列型態：宣告此陣列的型態，決定陣列元素在記憶體中所佔有的空間大小
3.陣列依照語言的不同，其記憶體位置的配置也不相同，可區分為兩種方式：
（1）以列為主（Row-major）：一列一列來依序儲存，如Java、C/C++、PASCAL等
（2）以行為主（Column-major）：一行一行來依序儲存，如Fortran等
4.一維陣列（One-dimension Array）：假設A是一維陣列名稱，宣告A（1:u1），表示A內含有n個元素，其中1為上標，u1為下標。則陣列元素有A(1)、A(2)、A(3)…A(n)，α為此A陣列在記憶體中的起始位置，d為每一個陣列元素所佔用的空間，那麼陣列元素與記憶體位址有如下的關係：
元素：A(1)、A(2)、A(3)、…、A(n)
位址：α；α+1*d；α+2*d；…；α+(u1 - 1)*d
=>Loc(A(i))=α+(i - 1)*d
﹡Loc(A(i))表示A(i)所在的位址
5.二維陣列（Two-dimension Array）：假設A是二維陣列名稱，宣告A(1:m,1:n)，其中m代表列數，n代表行數，依據記憶體配置的不同，可分為：
（1）以列為主：存放順序為a11,a12,...a1n,a21,a22,...,..amn，假設α為陣列A在記憶體中的起始位置，d為每一個陣列元素所佔用的空間，那麼陣列元素aij與記憶體位址的關係則為：Loc(aij)=α+n*(i - 1)*d+(j - 1)*d
（2）以行為主：則存放順序為a11,a21,...am1,a12,a22,...,..amn，假設α為陣列A在記憶體中的起始位置，d為每一個陣列元素所佔用的空間，那麼陣列元素aij與記憶體位址的關係則為：Loc(aij)=α+(i - 1)*d+m*(j - 1)*d
6.三維陣列（Three-dimension Array）：假設陣列A宣告為A(1:u1,1:u2,1:u3)，表示A為一個含有u1*u2*u3元素的三維陣列，依據記憶體配置的不同，可分為：
（1）以列為主：在想像轉換公式時，是要計算A(i,j,k)看看它是在直線排列的第幾個位置。首先可以將陣列A視為u1個u2 * u3的二維陣列，再將每個二維陣列視為有u2個一維陣列，每一個一維陣列可包含u3的元素。另外每個元素有d個單位空間，且α為陣列起始位址，其關係為：Loc(A(i,j,k))=a+(i - 1)u2 u3 d+(j - 1)u3 d+(k - 1)d
（2）以行為主：將陣列A視為u3個u2*u1的二維陣列，再將每個二維陣列視為有u2個一維陣列，每一個陣列含有u1個元素。另外每個元素有d個單位空間，且α為陣列起始位址，其關係為：Loc(A(aijk))=α(k - 1)u2 u1 d+(j - 1)u1 d+(i - 1)d
7.n維陣列：假設陣列A宣告為A（1:u1,1:u2,1:u3,...,1:un），則可將陣列視為有u1個n - 1維陣列，每個n - 1維陣列中有u2個n - 2維陣列，...，有un - 1個一維陣列，在每個一維陣列中有un個元素。若α為陣列起始位址(a=Loc(A(1,1,1,...,1))，d為單位空間，則陣列A元素依據記憶體配置的不同，可分為：
（1）以列為主：Loc(A(i1,i2,i3,...,in))=
α+(i1 - 1)u2 u3 … un d
+(i2 - 1)u3 u4 ...un d
.
.
+(in-1 - 1)un d
+(in-1)un d
（2）以行為主：Loc(A(i1,i2,i3,...,in))=
α+(in - 1)un-1 un-2 … u1 d
+(in-1 - 1)un-2 un-3 ...u1 d
.
.
+(i2-1 - 1)u1 d
+(i1 - 1)d
三.矩陣
1.矩陣的加法：前提是相加的兩矩陣列數與行數都必須相等，而相加後矩陣的列數與行數也是相同，如Amxn+Bmxn=Cmxn
2.矩陣的乘法：前提是必須符合A為一個m*n的矩陣，B為一個n*p的矩陣，對A*B之後的結果為一個m*p的矩陣C
3.轉置矩陣：把原矩陣的行座標元素與列座標元素相互調換，假設At為A的轉置矩陣，則At[j,i]=A[i,j]
4.稀疏矩陣（Sparse Matic）：一個矩陣中大部份的元素為零則稱之。因為會浪費大量的空間，可利用三項式（3-tuple）的資料結構。我們把每一個非零項目以(i,j,item-value)來表示，其中i為此非零項目所在的列數，j為此非零項目所在的行數，item-value則為此非零項的值。就是假如一個稀疏矩陣有n個非零項目，那麼可以利用一個A(0:n,1:3)的二維陣列來表示，稱為壓縮矩陣。其中A(0,1)代表此稀疏矩陣的列數，A(0,2)代表此稀疏矩陣的行數，而A(0,3)則是此稀疏矩陣非零項目的總數
5.上三角形矩陣（Upper Triangular Matrix）：一種對角線以下元素皆為0的n*n矩陣，其中又可分為右上三角矩陣與左上三角矩陣：
（1）右上三角矩陣（Right Upper Triangular Matrix）：對nxn的矩陣A，假如i>j，則A(i,j)=0
（2）左上三角矩陣（Left Upper Triangular Matrix）：對nxn的矩陣A，假如i>n-j+1，則A(i,j)=0
6.下三角形矩陣（Lower Triangular Matrix）：一種對角線以上元素皆為0的n*n矩陣，其中又可分為右下三角矩陣與左下三角矩陣：
（1）右上三角矩陣（Right Lower Triangular Matrix）：對nxn的矩陣A，假如i<j，則A(i,j)=0
（2）左上三角矩陣（Left Lower Triangular Matrix）：對nxn的矩陣A，假如i<n-j+1，則A(i,j)=0
7.帶狀矩陣（Band Matrix）：在上三角形矩陣中，右上方的元素皆為零，在下三角形矩陣中，左下方的元素也為零，也就是除了第一列與第n列有兩個元素外，其餘每列都具有三個元素，使得中間主軸附近的值行程類似帶狀的矩陣。由於本身也是稀疏矩陣，在儲存上也只將非零項目儲存到一維陣列中
Ch3 鏈結串列
一.鏈結串列的定義
1.鏈結串列（Linked List）是由許多相同資料型態的項目，依特定順序排列而成的線性串列，但特性是在電腦記憶體中的位置是不連續、隨機的存在
2.鏈結串列的優點是資料的插入或刪除都相當方便，有新資料加入就向系統要一塊記憶體空間；資料刪除後，就把空間還給系統，不需要移動大量資料
3.鏈結串列的缺點是設計資料結構時較麻煩，另外在搜尋資料時，也無法像靜態資料一般可隨機讀取資料，必須循序找到該資料為止
二.單向鏈結串列
1.單向鏈結串列（Single Linked List）：節點由資料欄及指標欄組成，而指標欄將會指向下一個記憶體所在的位置
2.在單向鏈結串列中第一個節點是「串列指標首」，指向最後一個節點的NULL鏈結欄位，表示它是「串列指標尾」，不指向任何地方
3.由於串列中所有節點都知道節點本身的下一個節點在哪，但卻不能知道前一個節點的位置，因此「串列指標首」就顯得相當重要，只要串列首存在，就可以對整個串列進行走訪、加入及刪除節點等動作，除非必要，否則不可移動串列指標首
4.通常在其他程式語言中，如C/C++，是以指標型態來處理串列型態的結構。不過因在Java中沒有指標型態，所以可以宣告鏈結串列為類別型態
5.建立單向鏈結串列：先宣告節點的資料型態，讓每一個節點包含一筆資料，並包含指向下一筆資料的指標，使所有資料能被串在一起而形成一個串列結構
6.單向鏈結串列插入新節點會有3種不同的情形：
（1）新節點插入第一個節點之前，即成為此串列的首節點：只需要把新節點的指標指向串列原來的第一個節點，再把串列指標首移到新節點上即可
（2）新節點插入最後一個節點之後：只需把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可
（3）將新節點插入串列中間的位置：例如插入的節點是在X與Y之間，只要將X節點的指標指向新節點，新節點的指標指向Y節點即可
7.單向鏈結串列刪除節點會有3種不同的情形：
（1）刪除串列的第一個節點：只要把串列指標首指向第二個節點即可
（2）刪除串列內的中間節點：只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可
（3）刪除串列後的最後一個節點：只要把指向最後一個節點ptr的指標，直接指向NULL即可
8.單向鏈結串列的反轉：我們知道鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將陣列反轉，則必須使用三個指標變數來達成
9.單向鏈結串列的連結：只要將串列的首尾相連即可
三.環狀鏈結串列
1.若把串列的最後一個節點指標指向串列首，而不指向NULL，整個串列就成為一個單方向的環狀結構。如此就不必擔心串列首遺失的問題，因為每一個節點都可以都可以是串列首，也可以從任一個節點來追蹤其他節點。通常可做為記憶體工作區與輸出入緩衝區的處理及應用
2.環狀鏈結串列（Circular Linked List）的特點是在串列中的任一節點，都可以到達此串列內的各節點，建立的過程與單向鏈結串列相似，唯一的不同點是必須將最後一個節點指向第一個節點
3.環狀鏈結串列的優點是可以從任何一個節點追蹤所有節點，而且回收整個串列所需的時間是固定的，與長度無關
4.環狀鏈結串列的缺點是需要多一個鏈結空間，而且插入一個節點需要改變兩個鏈結
5.環狀鏈結串列插入新節點會有2種不同的情形：
（1）將新節點X插在第一個節點前，成為串列首：首先將新節點X的指標指向原串列首節點，並移動整個串列，將串列首指向新節點
（2）將新節點X插在串列中任意節點I之後：首先將新節點X的指標指向I節點的下一個節點，並將I節點的指標指向X節點
6.環狀鏈結串列刪除節點會有2種不同的情形：
（1）刪除環狀鏈結串列的第一個節點：首先將串列首移到下一個節點，將最後一個節點的指標移到新的串列首，新的串列首是原串列的第二個節點
（2）刪除環狀鏈結串列的中間節點：首先找到節點Y的前一個節點previous，將previous節點的指標指向節點Y的下一個節點
7.環狀鏈結串列的結合：因環狀串列沒有頭尾之分，所以無法直接把串列1的尾指向串列2的頭。但是因為沒有頭尾之分，所以不需走訪串列去尋找串列尾，直接改變兩個指標就可以把兩個環狀串列連結在一起
四.雙向鏈結串列
1.將兩個方向不同的鏈結串列結合起來，除了存放資料的欄位外，它有兩個指標欄位，其中一個指標指向後面的節點，另一個則指向前面節點，這稱為雙向鏈結串列（Double Linked List）
2.由於個節點都有兩個指標，所以可以雙向通行，能夠輕鬆找到前後節點，同時從串列中任一節點也可以找到其他節點，而不需經過反轉或比對節點等處理，執行速度較快。另外如果任一節點的鏈結斷裂，可經由反方向串列走訪，快速完整重建鏈結
3.雙向鏈結串列的最大優點是有兩個指標分別指向節點前後兩個節點，所以能夠輕鬆找到前後節點，同時從串列中任一節點也可以找到其他節點，而不需經過反轉或比對節點等處理，執行速度較快
4.雙向鏈結串列的缺點是因有兩個鏈結，所以在加入或刪除節點時都得花更多時間來移動指標，且較為浪費空間
5.雙向鏈結串列的定義：對每個節點而言，具有三個欄位，中間為資料欄位。左右各有兩個鏈結欄位，分別為LLINK及RLINK，其中RLINK指向下個節點，LLINK指向上一個節點
6.雙向鏈結串列插入新節點會有3種不同的情形：
（1）將新節點加入此串列的第一個節點前，步驟為：
<1>將新節點的右鏈結（RLINK）指向原串列的第一個節點
<2>將原串列第一個節點的左鏈結（LLINK）指向新節點
<3>將原串列的串列首指標head指向新節點，且新節點的左鏈結指向null
（2）將新節點加入此串列的最後一個節點之後，步驟為：
<1>將原串列的最後一個節點的右鏈結指向新節點
<2>將新節點的左鏈結指向原串列的最後一個節點，並將新節點的右鏈結指向null
（3）將新節點加入到ptr節點之後，步驟為：
<1>將ptr節點的右鏈結指向新節點
<2>將新節點的左鏈結指向ptr節點
<3>將ptr節點的下一個節點的左鏈結指向新節點
<4>將新節點的右鏈結指向ptr的下一個節點
7.雙向鏈結串列刪除節點會有3種不同的情形：
（1）刪除串列的第一個節點，步驟為：
<1>將串列首指標head指到原串列的第二個節點
<2>將新的串列首指標指向null
（2）刪除此串列的最後一個節點，步驟為：
<1>將原串列最後一個節點之前一個節點的右鍵指向null即可
（3）刪除串列中間的ptr節點，步驟為：
<1>將ptr節點的前一個節點右鏈結指向ptr節點的下一個節點
<2>將ptr節點的前一個節點左鏈結指向ptr節點的上一個節點
五.鏈結串列相關應用簡介
1.多項式表示法：表示法有兩種：
（1）使用一個n+2長度的一維陣列存放，陣列的第一個位置儲存最大指數n，其他位置依照指數n遞減，依序儲存相對應的係數。但這種方法對於某些多項式而言，會太過浪費空間
（2）只儲存多項式中非零的項目。若有m項非零項目則使用2m+1長的陣列來儲存每一個非零項的指數及係數
2.一般來說，使用陣列表示法常會出現以下困擾：
（1）多項式內容變動時，對陣列結構的影響相當大，演算法處理不易
（2）由於陣列是靜態資料結構，所以事先必須尋找一塊連續夠大的記憶體，因此容易形成空間的浪費
這時候若使用鏈結串列來表示多項式，就可以克服以上問題。多項式的鏈結串列表示法主要是儲存非零項目，並且每一項均符合以下資料結構：
COEF | EXP | LINK
﹡COEF：表示該變數的係數；EXP：表示該變數的指數；LINK表示指到下一節點的指標
3.稀疏矩陣表示法：環狀鏈結串列也可以用來表現稀疏矩陣。主要的技巧是可用節點來表示非零選項，由於是二維的矩陣，每個節點除了必須有3個資料欄位：row、col、value外，還必須有兩個鏈結欄位：right、down，其中right指標可用來連結同一列的節點，而down指標可用來連結同一行的節點，如下所示：
Down | Row(i) | Col(j) | Right
---------------------------------------
Value(aij)
﹡Value：表示此非零項的值；Row：以i表示非零項元素所在列數；Col：以j表示非零項元素所在行數；Down：為指向同一行中下一個非零元素的指標；Right：為指向同一列中下一個非零元素的指標
Ch4 堆疊與佇列
一.堆疊簡介
1.堆疊（stack）是一群相同資料型態的組合，並擁有後進先出的特性，所有的動作均在堆疊的頂端進行
2 .將每一個元素放入堆疊頂端，稱為推入（push）；從堆疊頂端中取出元素，稱為彈出（pop）
3.不論用陣列或鏈結串列都能製作一個堆疊，最重要是要有「後進先出」與從頂端讀取資料的兩個基本原則，並符合下列五種基本工作運算：
（1）CREATE：建立一個空堆疊
（2）PUSH：存放頂端資料，並傳回新堆疊
（3）POP：刪除頂端資料，並傳回新堆疊
（4）EMPTY：判斷堆疊是否為空堆疊，是則傳回true，不是則傳回false
（5）FULL：判斷堆疊是否已滿，是則傳回true，不是則傳回false
4.以陣列結構來製作堆疊的優點是製作與設計的演算法較為簡單。缺點是若堆疊本身是變動的話，因陣列大小並無法事先規劃宣告，這時往往必須使用最大可能性的陣列空間來考量，導致浪費記憶體空間
5.鏈結串列製作堆疊的優點是隨時可以動態改變串列長度。缺點是設計的演算法較為複雜
二.算術運算式的表示法
1.運算式種類若依據運算子在運算式中的位置，可區分為以下三種表示法：
（1）中序法（Infix）：運算子在兩個運算元的中間，如A+B
（2）前序法（Prefix）：運算子在運算元的前面，如+AB
（3）後序法（Postfix）：運算子在運算元的後面，如AB+
三.中序轉為前序與後序
1.括號轉換法：先用括號把中序式的運算子優先順序分出來，再進行運算子的移動，最後把括號拿掉就可完成中序轉後序或中序轉前序了
（1）中序轉前序：
<1>將運算式依運算子優先順序以括號括起來
<2>針對運算子，把括號內的運算子取代所有的左括號，以最近者為優先
<3>將所有右括號去掉，即得前序式結果
（2）中序轉後序：
<1>將運算式依運算子優先順序以括號括起來
<2>針對運算子，把括號內的運算子取代所有的右括號，以最近者為優先
<3>將所有左括號去掉，即得後序式結果
2.堆疊法：使用堆疊配合運算子優先順序來進行轉換
（1）中序轉前序：
<1>由右至左讀進中序運算式的每個字元(token)
<2>如果讀進的字元為運算元，則直接輸出到前序式中
<3>如果遇到'('，則彈出堆疊內的運算子，直到彈出到一個')'，兩者互相抵銷為止
<4> ")"的優先權在堆疊內比任何運算子都小，任何運算子都可壓過它，不過在堆疊外卻是優先權最高者
<5>當運算子準備進入堆疊內時，並須和堆疊頂端的運算子比較，如果外面的運算子優先權大於或等於頂端的運算子則推入，如果較小就彈出，直到遇到優先權較小者或堆疊為空時，就把外面這個運算子推入
<6>中序式讀完後，如果運算子堆疊不是空的，則將其內的運算子逐一彈出，輸出到前序式
（2）中序轉後序：
<1>由左至右讀進中序運算式的每個字元(token)
<2>如果讀進的字元為運算元，則直接輸出輸出到後序式中
<3>如果遇到')'，則彈出堆疊內的運算子，直到彈出到一個'('，兩者互相抵銷止
<4> "("的優先權在堆疊內比任何運算子都小，任何運算子都可壓過它，不過在堆疊外卻是優先權最高者
<5>當運算子準備進入堆疊內時，並須和堆疊頂端的運算子比較，如果外面的運算子優先權大於頂端的運算子則推入，如果較小或等於就彈出，直到遇到優先權較小者或堆疊為空時，就把外面這個運算子推入
<6>中序式讀完後，如果運算子堆疊不是空的，則將其內的運算子逐一彈出，輸出到後序式
四.前序與後序轉為中序
1.括號轉換法：
（1）前序轉中序：適當的以「運算子+運算元」方式括號。依次將每個運算子，以最近為原則取代後方的右括號，最後再去掉所有左括號
（2）後序轉中序：適當的以「運算元+運算子」方式括號，依次將每個運算子，以最近為原則取代前方的左括號，最後再去掉所有右括號
2.堆疊法：
（1）若要將前序式轉為中序式，由右至左讀進運算式的每個字元(token)；若是要將後序式轉換成中序式，則讀取方向改成由左至右
（2）辨別讀入字元，若為運算元則放入此堆疊中
（3）辨別讀入字元，若為運算子則從堆疊中取出兩個字元，結合成一個基本的中序運算式(<運算元><運算子><運算元>)後，再把結果放入堆疊
（4）在轉換過程中，前序和後序的結合方式是不同的，前序式的順序是是<運算元2><運算子><運算元1>而後序式是<運算元1><運算子><運算元2>
五.中序表示法求值
1.依照以下五個步驟：
（1）建立兩個堆疊，分別存放運算子及運算元
（2）讀取運算子時，必須先比較堆疊內的運算子優先權，若堆疊內運算子的優先權較高，則先計算堆疊內運算子的值
（3）計算時，取出一個運算子及兩個運算元進行運算，運算結果直接存回運算元堆疊中，當成一個獨立的運算元
（4）當運算式處理完畢後，一步一步清除運算子堆疊，直到堆疊空了為止
（5）取出運算元堆疊中的值就是計算結果
六.前序法的求值運算
1.通常使用中序表示法來求值，必須考慮到運算子的優先順序，所以要建立兩個堆疊，分存放運算子及運算元。但如果使用前序法的好處是不需考慮括號及優先權問題，所以可以直接使用一個堆疊來處理運算式即可，不需把運算元及運算子分開處理
七. 後序法的求值運算
1.後序運算式具有和前序運算式類似的好處，沒有優先權的問題，而且後序運算式可以直接在電腦上進行運算，而不需先全數放入堆疊後再讀回運算。另外在後序運算式中，它使用迴圈直接讀取運算式，如果遇到運算子就從堆疊中取出運算元進行運算
八.佇列
1.佇列是一種先進先出的資料結構，和堆疊一樣都是一種有序列的抽象資料型態
2.不論用陣列或鏈結串列都能製作一個佇列，最重要是要有「先進先出」基本原則，並符合下列五種基本工作運算：
（1）CREATE：建立一個空佇列
（2）ADD：將新資料加入佇列的尾端，傳回新佇列
（3）DELETE：刪除佇列前端的資料，傳回新佇列
（4）FRONT：傳回佇列前端的值
（5）EMPTY：判斷佇列是否為空集合，是則傳回true，不是則傳回false
3.以陣列結構製作佇列的好處是演算法相當簡單，不過與堆疊不同之處，是需要擁有兩種基本動作：加入與刪除，而且使用front與rear兩個註標來分別指向佇列的前端與尾端，缺點是陣列大小並無法事先規劃宣告
4.若以鏈結串列來實作佇列，在宣告佇列類別中，除了和佇列類別中相關的方法外，還必須有指向佇列前端及佇列尾端的指標，即front與rear
九.環狀佇列
1.環狀佇列是以一種Q(0:n-1)的一維陣列，同時Q(0)為Q(n-1)的下一個元素
2.指標front永遠以逆時鐘方向指向佇列中第一個元素的前一個位置，rear則指向佇列目前的最後位置。一開始front與rear均預設為-1，表示為空佇列，也就是說，若front==rear則為空佇列
十.優先佇列
1.優先佇列（priority queue）是一種先進先出的有序串列，其中每一個元素都賦予一個優先權，加入元素時可任意加入，但有最高優先權者則最先輸出
2.當各元素以輸入先後次序為優先權時，就是一般的佇列；若是以輸入先後次序做為最不優先權時，此優先佇列即為堆疊
十一.雙向佇列
1.雙向佇列（Deque）是一種前後兩端都可輸入或取出資料的有序串列
2.在雙向佇列中，我們仍使用2個指標，分別指向加入及取回端，只是加入及取回時，各指標所扮演的角色不再是固定的加入或取回，而且兩邊的指標都是往佇列中央移動
Ch5 樹狀結構
一.樹的基本觀念
1.「樹」是由一個或一個以上的節點（Node）組成，存在一個特殊的節點，稱為樹根（Root）。每個節點可代表一些資料和指標組合而成的記錄。其餘的節點可分為n≥0個互斥的集合，即是T1,T2,...,Tn。每一個子集合本身也是一種樹狀結構及此跟節點的子樹。此外，一棵合法的樹，節點間可以互相連結，但不能形成無出口的迴圈
2.樹可組成樹林，而樹林是由n個互斥樹的集合（n≥0），移去樹根即為樹林
3.樹的分支度為d≥0，且不能有零個節點。此外，樹不具次序性
4.專有名詞：
（1）分支度（Degree）：每個節點所有的子樹個數
（2）階層或階度（level）：樹的層級
（3）高度（Height）：樹的最大階度
（4）樹葉或稱終端節點（Terminal Nodes）：分支度為零的節點
（5）父節點（Parent）：每一個節點有連結上一層節點，該上一層的節點即為其父節點
（6）子節點（children）：每一個節點有連結下一層節點，該下一層的節點即為其子節點
（7）祖先節點（ancestor）：指從樹根到該節點路徑上所包含的節點
（8）子孫節點（decendent）：指在該節點往上追溯子樹中的任一節點
（9）兄弟節點（siblings）：有共同父節點的節點為兄弟節點
（10）非終端節點（Nonterminal Nodes）：樹葉以外的節點
（11）同代（Generation）：具有相同階層樹的節點
二.二元樹
1.二元樹（又稱knuth樹）是一種有序樹（Oreder Tree），並由節點所組成的有限集合，這個集合若不是空集合，就是由一個樹根與左子樹（Left Subtree）和右子樹（Right Subtree）所組成。
2.二元樹的分支度為0≤d≤2；階度為i的節點樹最多是2^(i-1)：可以有零個節點。此外，二元樹具次序性，需考慮到前後的次序關係
3.高度為 k 的二元樹上所有節點的數目最多為 2^k - 1個
﹡完美二元樹（Fully Binary Tree）：高度為 k 且總節點數為 2^k - 1的二元樹
4.高度為 k 的二元樹上所有節點的數目最少為 k 個
﹡當一 個二元樹完全沒有右節點或左節點時，則稱之為左歪斜樹或右歪斜樹
5.對於任何非空二元樹T，若n0為樹葉節點樹，且分支度為2的節點樹為n2，則有n0 = n2+1
二.特殊二元樹
1.完整二元樹（Complete Binary Tree）：若二元樹的深度為h，所含的節點數小於2^h - 1，但其節點的編號方式如同深度為h的完美二元樹一般，從左到右，由上到下的順序一一對應結合
2.正規二元樹（Formal Bianry Tree）：所有內部的節點都正好有兩個子節點
3.嚴格二元樹（Strictly Binary Tree）：每一個非終端節點均有非空的左右子樹
三.二元樹的儲存方式
1.一維陣列表示法：首先可以將此二元樹假想成一個完美二元樹，而且第k個階度具有2^(k-1)個節點，並且依序存放在此一維陣列中
（1）一維陣列中的索引值有以下關係：
<1>左子樹索引值是父節點索引值*2
<2>右子樹索引值是父節點索引值*2+1
（2）二元搜尋樹具有以下優點：
<1>可以是空集合，但若不是空集合，則節點上一定要有一個鍵值
<2>每一個樹根的值需大於左子樹的值
<3>每一個樹根的值需小於右子樹的值
<4>左右子樹也是二元搜尋樹
<5>樹的每個節點值都不相同
（3）通常以陣列表示法來儲存二元樹，若愈接近完美二元樹，則愈省空間，若是歪斜樹則最浪費空間。另外要增刪資料較麻煩，必須重新建立二元樹
2.串列表示法：由於二元樹最多只能有兩個子節點，就是分支度小於或等於2，而所謂串列表示法，就是利用鏈結串列來儲存二元樹。使用串列來表示二元樹的好處是，對於節點的增加與刪除較為容易，缺點是很難找到父節點，除非在每一節點多加一個父欄位
四.二元樹走訪
1.二元樹走訪（Binary Tree Traversal）就是「拜訪樹中所有的節點各一次」
2.中序走訪（BAC, Preorder）：左子樹->樹根->右子樹
3.前序走訪（ABC, Inorder）：樹根->左子樹->右子樹
4.後序走訪（BCA, Postorder）：左子樹->右子樹->樹根
5.若有中序與前序的走訪結果，或者中序與後序的走訪結果，則可由這些結果求得唯一的二元樹。若指具備前序與後序的走訪結果，則無法決定唯一的二元樹
五.二元樹節點的插入與刪除
1.插入節點的狀況與搜尋相似，重點是插入後仍要保持二元搜尋樹的特性。若插入的節點在二元樹中沒有插入的必要，而搜尋失敗的狀況，就是準備插入的位置
2.刪除節點可分為三種狀況：
（1）刪除的節點為樹葉：只要將其相連的父節點指向NULL即可
（2）刪除的節點只有一棵子樹：將其右指標欄放到其父節點的左指標欄
（3）刪除的節點有兩棵子樹，方法有兩種：
<1>找出中序立即前行者（inorder immediate predecessor），即是將欲刪除節點的左子樹最大者向上提。簡單來說，就是在該節點的左子樹，往右尋找，直到右指標為NULL，這個節點就是中序立即前行者
<2>找出中序立即後繼者（inorder immediate successor），即是將欲刪除節點的右子樹最小者向上提。簡單來說，就是在該節點的右子樹，往左尋找，直到左指標為NULL，這個節點就是中序立即後繼行者
六.二元運算樹
1.我們可以將中序運算式依優先權的順序，建成一棵二元運算樹（Binary Expression Test）。之後再依二元樹的特性進行前、中、後序的走訪，即可得到前中後序運算式。建立的方法可根據以下兩種原則：
（1）考慮算術式中運算子的結合性與優先權，再適當地加上括號，其中樹葉一定是運算元，內部節點一定是運算子
（2）再由最內層的括號逐步向外，利用運算子當樹根，左邊運算元當左子樹，右邊運算元當右子樹，其中優先權最低的運算子做為此二元運算樹的樹根
七.引線二元樹
1.引線二元樹（Threaded Binary Tree）就是將二元樹產生的空節點加以利用，再指到樹的其他節點，而這些鏈結就稱為「引線」（thread），而這棵樹就稱為引線二元樹
2.為了分辨左右子樹欄位是引線或正常的鏈結指標，我們必須於節點結構中，再加上兩個欄位LBIT與RBIT加以區別，而在繪圖中，引線則使用虛線表示，有別於一般的指標
3.將二元樹轉變為引線二元樹的步驟：
（1）先將二元樹經由中序走訪的方式依序排出，並將所有空鏈結改成引線
（2）若引線鏈結是指向該節點的左鏈結，則將該引線指到中序走訪順序下的前一個節點
（3）若引線鏈結是指向該節點的右鏈結，則將該引線指到中序走訪順序下的後一個節點
（4）指向一個空節點，並將此空節點的右鏈結指向自己，而空節點的左子樹就是此引線二元樹
4.引線二元樹的基本結構：LBIT | LCHILD | DATA | RCHILD | RBIT
﹡LBIT：左控制位元；LCHILD：左子樹鏈結；DATA：節點資料；RCHILD：右子樹鏈結；RBIT右控制位元
﹡若LCHILD為正常指標，則LBIT=1；若LCHILD為引線，則LBIT=0；若RCHILD為正常指標，則RBIT=1；若RCHILD為引線，則RBIT=0
5.引線二元樹的優點：
（1）在進行中序走訪時，不需要使用遞迴式與堆疊，直接利用各節點的指標即可
（2）由於充分使用空鏈結，所以避免了鏈結閒置浪費的情形。另外，中序走訪時的速度也較快
（3）任一個節點都很容易找出它的中序後繼者與中序前行者，在中序走訪時，可以不需使用堆疊或遞迴
6.引線二元樹的缺點：
（1）在加入或刪除節點時的速度較一般二元樹慢
（2）引線子樹間不能共享
八.一般樹化為二元樹
1.若要將一般樹狀結構轉化為二元樹，使用的方法稱為「CHILD-SIBLING」(leftmost-child-next-right-sibling)法則，其步驟為：
（1）將節點的所有兄弟節點，用平行線連接起來
（2）刪掉所有與子節點間的鏈結，指保留與最左子節點的鏈結
（3）順時針轉45°
九.樹林化為二元樹
1.步驟為：
（1）由左至右將每棵樹的樹根連接起來
（2）仍然利用樹化為二元樹的操作方法
十.樹與樹林的走訪
1.假設樹根為R，且此樹有n個節點，並可分成m個子樹，分別是T1, T2,...,Tm
2.樹的走訪方式：
（1）中序走訪：
<1>以中序走訪T1
<2>拜訪樹根R
<3>再以中序法追蹤T2, T3,...,Tm
（2）前序走訪：
<1>拜訪樹根R
<2>再以前序法依次拜訪T1, T2,...,Tm
（3）後序走訪：
<1>以後序法依次拜訪T1, T2,...,Tm
<2>拜訪樹根R
3.樹林的走訪方式：
（1）中序走訪：
<1>若樹林為空，則直接返回
<2>以中序走訪第一棵樹的子樹群
<3>中序走訪樹林中第一棵樹的樹根
<4>依中序法走訪樹林中其他的樹
（2）前序走訪：
<1>若樹林為空，則直接返回
<2>以前序走訪第一棵樹的子樹群
<3>前序走訪樹林中第一棵樹的樹根
<4>依前序法走訪樹林中其他的樹
（3）後序走訪：
<1>若樹林為空，則直接返回
<2>以後序走訪第一棵樹的子樹群
<3>後序走訪樹林中第一棵樹的樹根
<4>依後序法走訪樹林中其他的樹
十一.最佳化二元搜尋樹
1.延伸二元樹（Extension Binary Tree）：任何一個二元樹中，若具有n個節點，則有n-1個非空鏈結及n+1個空鏈結。若在每個空鏈結加上一個特定節點，則稱為外節點，其餘的節點稱為內節點，定義為「延伸二元樹」。另外定義外徑長=所有節點到樹根距離的總和，內徑長=所有內節點到樹根距離的總和
2.霍夫曼樹（Huffman Tree）：常用於處理資料壓縮的問題，可以根據資料出現的頻率來建構的二元樹。簡單來說，若有n個權值（q1, q2,...,qn），且構成一個有n節點的二元樹，每個節點外部節點權值為qi，則加權徑長度最小的就稱為「最佳化二元樹」或「霍夫曼樹」
3.求最佳化二元樹的步驟如下：
（1）產生兩個節點，對資料中出現過的每一元素各自產生一個樹葉節點，並賦予樹葉節點該元素的出現頻率
（2）令N為T1和T2的父親節點，T1和T2是T中出現頻率最低的兩個節點，令N節點的出現頻率等於T1和T2的出現頻率總和
（3）消去步驟的兩個節點，插入N，再重複步驟1
十二.平衡樹
1.因二元搜尋樹的缺點是無法永遠保持在最佳狀態。當加入之資料部份已排序的情況下，極有可能產生歪斜樹，因而使樹的高度增加，導致搜尋效率降低。所以二元搜尋樹較不利於資料的經常變動（加入或刪除）。為了能盡量降低搜尋所需要的時間，我們必須讓樹的高度越小越好
2.在平衡樹（Balanced Binary Tree或稱AVL樹）中，每次在插入和刪除資料後，必要的時候會對二元樹做一些高度的平衡調整動作
3.假設T是一個非空的二元樹，T1及Tr分別是它的左右子樹，若符合下列兩個條件，則稱T是高度平衡樹：
（1）T1及Tr也是高度平衡樹
（2）|h1 - hr| ≦ 1，h1及hr分別為T1與Tr的高度。也就是說，所有內部節點的左右子樹高度相差必定小於或等於1
十三.決策樹
1.決策樹（Decision Support System，DSS），是一種利用樹狀結構的方法，來討論一個問題的各種情況分佈的可能性。常用來設計遊戲的AI，故也稱為遊戲樹
十四.B樹
1.B樹是一種高度大於1的m階搜尋樹，它也是一種平衡樹概念的延伸，主要的特點包括：
（1）B樹上每一個節點都是m階節點
（2）每一個m階節點存放的鍵值最多為m-1個
（3）每一個m階節點分支度均小於等於m
（4）除非是空樹，否則樹根節點至少必須有兩個以上的子節點
（5）除了樹根及樹葉節點外，每一個節點最多不超過m個子節點，但至少包含┌m/2┐個子節點
（6）每個樹葉節點到樹根節點所經過的路徑長度皆一致，也就是說，所有的樹葉節點都必須在同一層（level）
（7）當要增加樹的高度時，處理的作法就是將該樹根節點一分為二
（8）B樹其鍵值分別為k1、k2、k3、k4…km-1，則k1<k2…<km-1
（9）B樹的節點表示法為P0,1，k1，P1,2，k2…Pm-2,m-1，km-1，Pm-1,m，其中 k1<k2<k3…<km-1
<1>P0,1指標所指向的子樹T1中的所有鍵值均小於k1<2>P1,2指標所指向的子樹T2中的所有鍵值均大於等於k1且小於k2
<3>Pm-1,m指標所指向的子樹Tm中所有鍵值均大於等於km-1
十五.二元空間分割樹
1.二元空間分割樹（Binary Space Partitionint Tree，BSP Tree）是一種二元樹，每個節點有兩個子節點，也是一種遊戲空間分割的方法，通常被使用在平面的繪圖應用
2.因物體與物體之間有位置上的相聯性，所以每一次當平面要重繪時，就必須考慮到平面上各個物體位置之間的關係，然後再加以重繪。BSP Tree採取的方法是，在一開始將資料檔讀進來的時候，就將整個資料檔中的數據先建成一個二元樹的資料結構
3.BSP最好還要經過轉換成平衡樹的過程，才可以減少搜尋所花得時間
十六.四元樹與八元樹
1.四元樹（Quadtree）就是樹的每個節點擁有四個子節點。它以遞迴的方式，軸心一致的將地形依四個象限分成四個子區域。對於2D平面與碰撞偵測來說相當有用
2.八元樹（Octree）定義若不為空樹的話，樹中任一節點的子節點樹只會有八個或零個，也就是子節點不會有8與0以外的數字。通常用於3D空間中的場景管理，多半適用在密閉或有限的空間中
Ch6 圖形結構
一.圖形的定義
1.圖形是由「頂點」和「邊」所組成的集合，通常用G=(V, E)來表示，其中V是所有頂點所成的集合，而E代表所有邊所成的集合
二.無向圖形
1.無向圖形（Graph）是一種具備同邊的兩個頂點沒有次序關係
2.定義：
（1）完整圖形：N個頂點，且正好有N(N-1)/2條邊，則稱之為完整圖形
（2）路徑（Path）：對於頂點Vi到頂點Vj的一條路徑，是指由所經過頂點所成的連續數列
（3）簡單路徑（Simple Path）：除了起點和終點可能相同外，其他經過的頂點都不同
（4）路徑長度（Path Length）：是指路徑上所包含邊的數目
（5）循環（Cycle）：起始頂點及終止頂點為同一個點的簡單路徑稱為循環
（6）依附（Incident）：若Vi與Vj相鄰，則稱(Vi, Vj)這個邊依附於頂點Vi與頂點Vj
（7）子圖（Subgraph）：當我們稱G’為G的子圖時，並定存在V(G’)⊆V(G)與E(G’)⊆E(G)
（8）相鄰（Adjacent）：若(Vi, Vj)是E(G)中的一邊，則稱Vi與Vj相鄰
（9）相連單元（Connected Component）：相連在一起的最大子圖
（10）分支度：一個頂點所擁有邊的總數
三.有向圖形
1.有向圖形（Digraph）是一種每一邊都可使用有序對<V1, V2>來表示，並且<V1, V2>與<V2, V1>是表示兩個不同方向的邊，而所謂<V1, V2>，是指V1為尾端指向為頭部的V2
2.定義：
（1）完整圖形：具有n個頂點，且正好有n(n-1)條邊，則稱之為有向圖形
（2）路徑（Path）：從頂點Vp到頂點Vq的路徑，是指一串由頂點所組成的連續有向序列
（3）強連接（Strongly Connected）：若每個相異的成對頂點Vi,Vj有直接路徑，同時，有另一條路徑從Vj到Vi，則稱此圖為強連接
（4）強連接單元（Strongly Connected Component）：構成強連接的最大子圖
（5）入分支度（In-degree）：以頂點V為箭頭的邊數目
（6）出分支度（Out-degree）：以頂點V為箭尾的邊數目
四.相鄰矩陣法
1.圖形A有n個頂點，以n*n的二維矩陣列表示。相鄰矩陣的定義：對於一個圖形G=(V,E)，假設有n個頂點，n≧１，則可以將n個頂點的圖形，利用一個n×n二維矩陣來表示，其中假如 A(i,j)=1，則表示圖形中有一條邊(Vi,Vj)存在。反之，A(i,j)=0，則沒有一條邊(Vi,Vj)存在
2.相關特性：
1.對無向圖形而言，相鄰矩陣一定是對稱的，而且對角線一定為0。有向圖形則不一定是如此
2.在無向圖形中，任一節點i的分支度為nΣj=1，就是第i列所有元素的和。在有向圖中，節點i的出分支度為nΣj=1，就是第i列所有元素的和，而入分支度為nΣi=1，就是第j行所有元素的和
3.用相鄰矩陣法表示圖形共需要n^2空間，由於無向圖形的相鄰矩陣一定是具有對稱關係，所以扣除對角線全部為零外，僅需儲存上三角形或下三角形的資料即可，因此僅需n(n-1)/2空間
3.優點是藉著矩陣的運算，可以求取許多特別的應用，且插入與刪除新邊時，會較為容易
4.因稀疏矩陣空間浪費的問題，若要計算所有頂點的分支度時，其時間複雜度為O(n^2)
五.相鄰串列法
1.相鄰串列法（adjacency list）就是將一個n列的相鄰矩陣，表示成n個鏈結串列，這種作法和相鄰矩陣相比較節省空間，如計算所有頂點的分支度時，其時間複雜度為O(n+e)，缺點是圖形新邊的加入或刪除會更動到相關的串列鏈結，較為麻煩費時
六.相鄰複合串列法
1.相鄰矩陣法與相鄰串列法都是從頂點的觀點出發，但若要處理的是「邊」，則必須使用相鄰多元串列。其結構為：M | V1 | V2 | LINK1 | LINK2
2.相關特性：
M：為記錄單元，是記錄該邊是否被找過的一個位元之欄位
V1及V2：為邊線起、終點。是所記錄的邊的起點與終點
LINK1：為起點指標。在尚有其它頂點與V1相連的情況下，此欄位會指向下一個與V1相連的邊節點，如果已經沒有任何頂點與V1相連時，則指向NULL
LINK2：為終點指標。在尚有其它頂點與V2相連的情況下，此欄位會指向下一個與V2相連的邊節點，如果已經沒有任何頂點與V2相連時，則指向NULL
七.索引表格法
1.索引表格法（Indexed Table）是一種用一維陣列來依序儲存與各頂點相鄰的所有頂點，並建立索引表格，來記錄各頂點在此一維陣列中第一個與該頂點相鄰的位置
八.圖形的走訪
1.圖形追蹤的定義：一個圖形G=(V,E)，存在某一頂點v∈V，我們希望從v開始，經由此節點相鄰的節點而去拜訪G中的其他節點
2.先深後廣法（Depth-First Search，DFS）：以堆疊與遞迴走訪。它從圖形的某一端點開始走訪，被拜訪過的頂點就做上已拜訪的記號，接著走訪此頂點的所有相鄰且未拜訪過得頂點中任一個頂點，並做上已拜訪的記號，再以該點為新的起點，繼續進行搜尋
3.先廣後深法（Breadth-First Search，BFS）：以佇列與遞迴走訪。同上方式走訪
九.擴張樹
1.擴張樹（Spanning Tree）又稱「花費樹」或「值樹」，當一個圖形連通時，則使用DFS或BFS必能拜訪圖形中所有的頂點，且G=(V,E)的所有邊可分成兩個集合：T和B（T為搜尋時所經過的所有邊，而B為其餘未被經過的邊）。若S=(V,T)為G中的擴張樹，則具有以下三項性質：
（1）E=T+B
（2）加入B中的任一邊到S中，則會產生循環
（3）V中的任何2頂點Vi、Vj在S中存在唯一的一條簡單路徑
2.最小花費擴張樹（Minimum Cost Spanning Tree）：若在樹的邊加上一個權重（weight）值，這種圖形就成為「加權圖形（Weighted Graph）」。如果這個權重值代表兩個頂點間的距離或成本，這類圖形就稱為網路（Network）
3.Kruskal演算法：將各邊線依權值大小由小到大排列，接著從權值最低的邊線開始架構最小成本擴張樹，如果加入的邊線會造成迴路則捨棄不用，直到加入了n-1個邊線為止
4.Prim演算法：又稱P氏法，對一個加權圖形G=(V,E)，設V={1,2,…,n}，假設U={1}，也就是說，U及V是兩個頂點的集合。然後從U-V差集所產生的集合中找出一個頂點x，該頂點x能與U集合中的某點形成最小成本的邊，且不會造成迴圈。然後將頂點x加入U集合中，反覆執行同樣的步驟，直到U集合等於V集合為止
十.
1.單點對全部頂點（Single Source All Destination）：通常使用Dijkstra演算法求得，其演算法定義如下：
（1）假設S={Vi|Vi∈V}，且Vi在已發現的最短路徑，其中V0∈S是起點
（2）假設w∉S，定義Dist(w)是從V0到w的最短路徑，這條路徑除了w外必屬於S。且有下列幾點特性：
<1>如果u是目前所找到最短路徑之下一個節點，則u必屬於V-S集合中最小花費成本的邊
<2>若u被選中，將u加入S集合中，則會產生目前的由V0到u最短路徑，對於w∉S，DIST(w)被改變成DIST(w)←Min{DIST(w),DIST(u)+COST(u,w)}
2.所有頂點對兩兩之間的最短距離（All Pairs Shortest Paths）：通常使用Floyd演算法求得，其演算法如下：
（1）A^k [i][j]=min{A^(k-1) [i][j],A^(k-1) [i][k]+A^(k-1) [k][j]}，k≧1﹡k表示經過的頂點，A^k [i][j]為從頂點i到j的經由k頂點的最短路徑
（2）A^0 [i][j]=COST[i][j]
（3）A^0為頂點i到j間的直通距離
（4）A^n [I,j]代表i到j的最短距離，即A^n便是我們所要求的最短路徑成本矩陣。
十一.AOV網路與拓樸排序
1.以頂點代表工作的網路，稱為頂點工作網路（Activity On Vertex Network，AOV）
2.在AOV網路中，具有部份次序關係，拓樸排序的功能就是將這些部份次序（Partial Order）的關係，轉換成線性次序（Linear Order）的關係。具有這種特性的線性次序就稱為拓樸序列（Topological Order）。排序的步驟如下：
（1）尋找圖形中任何一個沒有先行者的頂點
（2）輸出此頂點，並將此頂點的所有邊全部刪除
（3）重複以上兩個步驟處理所有頂點
十二.AOE網路
1.邊工作網路（Activity On Edge Network，AOE）網路是指事件的行動在邊上的有向圖形
2.其中的頂點做為各「進入邊事件」（incident in edge）的匯集點，當所有「進入邊事件」的行動全部完成後，才可以開始「外出邊事件」（incident out edge）的行動。在AOE網路會有一個源頭頂點和目的頂點。從源頭頂點開始計時執行各邊上事件的行動，到目的頂點完成為指所需的時間為所有事件完成的時間總花費
3.AOE完成所需的時間是由一條或數條的臨界路徑（critical path）所控制。所謂臨界路徑就是AOE有向圖形中從源頭頂點到目的頂點間最長的路徑長度
4.相關定義：
（1）最早時間（earlest time）：AOE網路中頂點的最早時間為該頂點最早可以開始其外出邊事件(incident out edge)的時間，它必須由最慢完成的進入邊事件所控制，我們用TE表示
（2）最晚時間（latest time）：AOE網路中頂點的最晚時間為該頂點最慢可以開始其外出邊事件，而不會影響整個AOE網路完成的時間。它是由外出邊事件中最早要求開始者所控制。以TL表示
（3）臨界頂點（critical vertex）：AOE網路中頂點的TE=TL，我們就稱它為臨界頂點。從源頭頂點到目的頂點的各個臨界頂點可以構成一條或數條的有向臨界路徑5.TE與TL計算原則：
（1）TE：由前往後（即由源頭到目的正方向），若第i項工作前面幾項工作有好幾個完成時段，取其中最大值（2）TL：由後往前（即由目的到源頭的反方向），若第i項工作後面幾項工作有好幾個完成時段，取其中最小值
Ch7 排序
一排序簡介
1.排序（Sorting）是指將一群資料，按特定規則調換位置，使資料具有某種次序關係（遞增或遞減）
1.在排序的過程中，資料的移動方式可分為「直接移動」與「邏輯移動」
2.直接移動：直接交換儲存資料的位置
3.邏輯移動：不會移動資料儲存位置，僅改變指向這些資料的輔助指標的值
二.氣泡排序法
1.氣泡排序法（Bubble Sort）又稱為交換排序法，其原理是由第一個元素開始，比較相鄰元素大小，若大小順序有誤，則對調後再進行下一個元素的比較，就如氣泡逐漸由水底逐漸冒升到水面上一樣
2.氣泡法分析：
（1）最壞清況及平均情況均需比較：(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2 次；時間複雜度為O(n^2)，最好情況只需完成一次掃瞄，發現沒有做交換的動作則表示已經排序完成，所以只做了n-1次比較，時間複雜度為O(n)
（2）由於氣泡排序為相鄰兩者相互比較對調，並不會更改其原本排列的順序，所以是穩定排序法
（3）只需一個額外的空間，所以空間複雜度為最佳
（4）此排序法適用於資料量小或有部份資料已經過排序
三.選擇排序法
1.選擇排序法（Selection Sort）可使用兩種方式排序，一為在所有的資料中，當由大至小排序，則將最大值放入第一位置；若由小至大排序時，則將最大值放入位置末端
2.選擇法分析：
（1）無論是最壞清況、最佳情況及平均情況都需要找到最大值(或最小值)，因此其比較次數為：(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2次；時間複雜度為O(n^2)
（2）由於選擇排序是以最大或最小值直接與最前方未排序的鍵值交換，資料排列順序很有可能被改變，故不是穩定排序法
（3）只需一個額外的空間，所以空間複雜度為最佳
（4）此排序法適用於資料量小或有部份資料已經過排序
四.插入排序法
1.插入排序法（Insert Sort）是將陣列中的元素，逐一與已排序好的資料作比較，如前兩個元素先排好，再將第三個元素插入適當的位置，所以這三個元素仍然是已排序好，接著再將第四個元素加入，重覆此步驟，直到排序完成為止
2.插入法分析：
1.最壞及平均清況需比較(n-1)+(n-2)+(n-3)+…+3+2+1=n(n-1)/2次；時間複雜度為O(n^2)，最好情況時間複雜度為O(n)
2.插入排序是穩定排序法
3.只需一個額外的空間，所以空間複雜度為最佳
4.此排序法適用於大部份資料已經過排序或已排序資料庫新增資料後進行排序
5.插入排序法會造成資料的大量搬移，所以建議在鏈結串列上使用
五.謝耳排序法
1.謝耳排序法（Shell Sort）的原則是將資料區分成特定間隔的幾個小區塊，以插入排序法排完區塊內的資料後再漸漸減少間隔的距離
2.謝耳法分析：
（1）任何情況的時間複雜度均為O(n^(3/2))
（2）謝耳排序法和插入排序法一樣，都是穩定排序
（3）只需一個額外空間，所以空間複雜度是最佳
（4）此排序法適用於資料大部份都已排序完成的情況
六.合併排序法
1.合併排序法（Merge Sort）是外部儲存裝置最常用的排序方法，工作原理是針對已排序好的二個或二個以上的檔案，經由合併的方式，將其組合成一個大的且已排序好的檔案。步驟如下：
（1）將N個長度為1的鍵值成對地合併成N/2個長度為2的鍵值組
（2）將N/2個長度為2的鍵值組成對地合併成N/4個長度為4的鍵值組
（3）將鍵值組不斷地合併，直到合併成一組長度為N的鍵值組為止
七.快速排序法
1.快速排序法（Quick Sort）又稱分割交換排序法，是目前公認最佳的排序法，也是使用切割征服(Divide and Conquer)的方式，會先在資料中找到一個隨機會自行設定一個虛擬中間值，並依此中間值將所有打算排序的資料分為兩部份
2.快速法分析：
（1）在最快及平均情況下，時間複雜度為O(nlog2n)。最壞情況就是每次挑中的中間值不是最大就是最小，其時間複雜度為O(n^2)（2）快速排序法不是穩定排序法
（3）在最差的情況下，空間複雜度為O(n)，而最佳情況為O(log2n)
（4）快速排序法是平均執行時間最快的排序
八.堆積排序法
1.堆積排序法（Heap Sort）可以算是選擇排序法的改進版，它可以減少在選擇排序法中的比較次數，進而減少排序時間。堆疊排序法是利用堆疊樹來完成排序
2.堆積法分析：
（1）在所有情況下，時間複雜度均為O(nlogn)
（2）堆積排序法不是穩定排序法
（3）只需要一額外的空間，空間複雜度為O(1)
九.基數排序法
1.基數排序法（Radix Sort）並不需要進行元素間的比較動作，而是屬於一種分配模式排序方式
2.基數排序法依比較的方向可分為最有效鍵優先（Most Significant Digit First，MSD）和最無效鍵優先（Least Significant Digit First，LSD）兩種。MSD法是從最左邊的位數開始比較；而LSD法是從最右邊的位數開始比較
3.基數法分析：
（1）在所有情況下，時間複雜度均為O(nlogpk），k是原始資料的最大值
（2）基數排序法是穩定排序法
（3）基數排序法會使用到很大的額外空間來存放串列資料，其空間複雜度為O(n*p)，n是原始資料的個數，p是資料字元數
（4）若n很大，p固定或很小，此排序法將會很有效率
十.直接合併排序法
1.直接合併排序法（Direct Merge Sort）是外部儲存裝置最常用的排序方法。它可以分為兩個步驟：
（1）將欲排序的檔案分為幾個可以載入記憶體空間大小的小檔案，再使用內部排序法將各檔案內的資料排序
（2）將第一步驟所建立的小檔案每二個合併成一個檔案。兩兩合併後，把所有檔案合併成一個檔案後即可完成排序
十一.k路合併法
1.使用k-way合併的原意是希望減少輸出入時間，但合併k個行程前要決定下一筆輸出的排序資料，必須作k-1次比較才可以得到答案。也就是說，雖然輸出入的時間減少，但進行k-way合併時，卻增加了更多的比較時間，因此必須選擇合適的k值，以求得平衡
十二.多相合併法
1.處理k-way合併時，通常會將要合併的行程平均分配到k個磁帶上，但為避免下一次合併過程中被重新分佈於磁帶時，不小心覆蓋掉資料，我們會採用2k個磁帶（k個當輸入，k個當輸出），但卻會因此造成磁帶的浪費
2.利用多項合併（Polyphase Merge），可以使用少於2k個磁帶，卻能正確無誤地執行k-way合併
Ch8 搜尋
一.常見的搜尋法
1.根據資料量的大小，可將搜尋分為：
（1）內部搜尋：資料量較小的檔案可以一次全部載入記憶體以進行搜尋
（2）外部搜尋：資料龐大的檔案便無法全部容納於記憶體中，這種檔案通常均先加以組織化，再存於磁碟中，搜尋時也必須循著檔案的組織性來達成
2.搜尋的技巧可分為：
（1）靜態搜尋：指的是搜尋過程中，搜尋的表格或檔案的內容不會受到更動
（2）動態搜尋：指的是搜尋過程中，搜尋的表格或檔案的內容可能會更動
二.循序搜尋法
1.循序搜尋法（Linear Search、Sequential Search）通常用於未經組織化的檔案而言，又稱為線性搜尋。找尋的過程從檔案第一筆開始，依序比較每個鍵值
2.線性搜尋法的優點是檔案或資料事前是不需經過任何處理與排序，也由於它未考慮到資料的特徵對於搜尋的影響，所以在應用上適合於各種情況，其缺點則是搜尋的速度較慢
三.二分搜尋法
1.二分搜尋法（Binary Search）是將資料分割成兩等份，再比較鍵值與中間值的大小，如果鍵值小於中間值，可確定要找的資料在前半段的元素，否則在後半部。如此分割數次直到找到或確定不存在為止
2.二分法必須事先經過排序，且資料量必須能直接在記憶體中執行，此法適合用於不需增刪的靜態資料，因為每次的搜尋都會比上一次少一半的範圍，最多只需要比較⌈log2n⌉或⌈log2(n+1)⌉，時間複雜度為O(log n)
四.內插搜尋法
1.內插搜尋法（Interpolation Search）又叫做插補搜尋法，是二分搜尋法的改版。它是依照資料位置的分佈，利用公式預測資料的所在位置，再以二分法的方式漸漸逼近
2.使用內插法是假設資料平均分佈在陣列中，而每一筆資料的差距是相當接近或有一定的距離比例。其內插法的公式為： Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))* ( high - low )
﹡key是要尋找的值，data[high]、data[low]是剩餘待尋找記錄中的最大值及最小值，資料比數為n
3.插補搜尋法的步驟如下：
（1）將記錄由小到大的順序給予1,2,3,…,n的編號
（2）令low=1，high=n
（3）當low<high時，重複執行步驟（4）及步驟（5）
（4）令Mid=low + (( key - data[low] ) / ( data[high] - data[low] ))*( high - low )
（5）若key<keyMid且high≠Mid-1則令high=Mid-1
（6）若key＝keyMid表示成功搜尋到鍵值的位置
（7）若key>keyMid且low≠Mid+1則令low=Mid+1
4.一般而言，使用內插搜尋法資料需先經過排序，優於循序排序法，而若資料的分佈愈平均，則搜尋速度愈快。此搜尋法的時間複雜度取決於資料分佈的情況而定，平均而言優於O(log n)
五.費氏搜尋法
1.費氏搜尋法（Fibonacci Search）又稱費伯那搜尋法，此法和二分法一樣都是以切割範圍來進行搜尋，不同的是費氏搜尋法不以對半切割而是以費氏級數的方式切割
2.費氏級數F(n)的定義如下：
（1）F0=0, F1=1
（2）Fi=Fi-1+Fi-2, i≧2
3.平均而言，費氏搜尋法的比較次數會少於二元搜尋法。其平均時間複雜度為為O(log2N)，不過費事搜尋演算法較為複雜，需額外產生費氏樹
六.雜湊搜尋法
1.雜湊法（Hashing）就是將本身的鍵值，經由特定的數學函數運算或使用其他的方法，轉換成相對應的資料儲存位址。而雜湊所使用的數學函數就稱為「雜湊函數」（Hashing Function）
2.有關雜湊函數的相關名詞：
（1）bucket（桶）：雜湊表中儲存資料的位置，每一個位置對應到唯一的一個位址（Bucket Address）。桶就好比一筆記錄
（2）slot（槽）：每一筆記錄中可能包含好幾個欄位，而slot指的就是「桶」中的欄位
（3）collision（碰撞）：若兩筆不同的資料，經過雜湊函數運算後，對應到相同的位址時，稱為碰撞
（4）溢位：如果資料經過雜湊函數運算後，所對應到的bucket已滿，則會使bucket發生溢位（5）雜湊表：儲存記錄的連續記憶體。雜湊表是一種類似資料表的索引表格，其中可分為n個bucket，每個bucket又可分為m個slot
（6）同義字（Synonym）：當兩個識別字I1及I2，經雜湊函數運算後所得的數值相同，即f(I1)=f(I2)，則稱I1與I2對於f這個雜湊函數是同義字
（7）載入密度（Loading Factor）：所謂載入密度是指識別字的使用數目除以雜湊表內槽的總數：α=n/(s*b)
﹡n為識別字的使用數目；s為每一個桶內的槽數；b為桶的數目
（8）完美雜湊（Perfect Hashing）：指沒有碰撞又沒有溢位的雜湊函數
3.設計雜湊函數時應遵循底下幾個規則：
（1）降低碰撞及溢位的產生
（2）雜湊函數不宜過於複雜，越容易計算越佳
（3）儘量把文字的鍵值轉換成數字的鍵值，以利雜湊函數的運算
（4）所設計的雜湊函數計算而得的值，儘量能均勻地分佈在每一桶中，不要太過於集中在某些桶內，這樣就可以降低碰撞，並減少溢位的處理
七.除法（Division）
1.除法是將資料除以某一個常數後，取餘數來當索引
八.中間平方法（Mid-Square）
1.中間平方法和除法相當類似，它是把資料乘以自己，之後再取中間的某段數字做索引
九.折疊法（Folding）
1.折疊法是將資料轉換成一串數字後，先將這串數字先拆成數個部份，最後再把它們加起來，就可以計算出這個鍵值的Bucket Address
2.在折疊法中有兩種作法：
（1）移動折疊法（Shift Folding）：直接將每一部份相加所得的值作為其Bucket Address
（2）邊界折疊法（Folding at the boundaries）：將每一部份之數字中的奇數位段或偶數位段反轉，再行相加來取得其Bucket Address，如此可降低碰撞的機會
十.數字分析法（Digital Analysis）
1.數字分析法適用於資料不會更改，且為數字型態的靜態表。在決定雜湊函數時先逐一檢查資料的相對位置及分佈情形，將重複性高的部份刪除
十一.線性探測法
1.線性探測法（Linear Probing）是當發生碰撞情形時，若該索引已有資料，則以線性的方式往後找尋空的儲存位置，一找到位置就把資料放進去
2.線性探測法通常把雜湊的位置視為環狀結構，如此一來若後面的位置已被填滿而前面還有位置時，可以將資料放到前面
十二.平方探測
1.在平方探測(Quadratic Probing)中，當溢位發生時，下一次搜尋的位址是(f(x)+i^2) mod B與(f(x)-i^2) mod B，即讓資料值加或減i的平方。可改善線性探測法中類似的鍵值會聚集在一起的缺點
十三.再雜湊
1.再雜湊（Rehashing）是一開始就先設置一系列的雜湊函數，如果使用第一種雜湊函數出現溢位時就改用第二種，如果第二種也出現溢位則改用第三種，一直到沒有發生溢位為止
十四.鏈結串列
1.鏈結串列（Chaining）將雜湊表的所有空間建立n個串列，最初的預設值只有n個串列首。如果發生溢位就把相同位址之鍵值鍵結在串列首的後面，形成一個鍵結串列，直到所有的可用空間全部用完為止
沒有留言:
張貼留言