Tree的完整整理：
Tree
定義：
1. 不允許Null Tree
2. 必存在Node Root
3. 其餘Nodes形成Subtree
Binary Tree
定義：
1. 允許Null Tree
2. 0<=degree<=2
3. Subtree有順序之分
Binary Tree Three Rules
1. i-level Tree：Nodes Max = 2^(i-1)
2. k-height Tree：Node Max = 2^k-1
3. N(Node numbers) = n0(leafs numbers) + n1(degree 1 numbers) + n2(degree 2 numbers) ; n0 = n2 + 1
Special Binary Tree
1. Skewed Binary Tree (left or right)
2. Full Binary Tree (every level is full)
3. Complete Binary Tree (every nodes degree=2)
Binary Search Tree
定義：
1. Binary Tree的一種
2. L.child < Root < R.child
3. L.child and R.child are Binary Search Tree
Extend Binary Tree
1. Binary Tree的一種
2. 在原有子葉n個節點上，加入n+1個空連結形成Complete Binary Tree，額外的節點稱為外部和失敗節點
3. E：外部節點；I：內部節點。用Level算內外部路徑，E.I.成正比，即Complete Binary Tree的E.I.有Min；加權後，則不一定。
M.W.E.P.L. Problem
使用Huffman Algorithm（霍夫曼演算法）解決之。
Tip：挑選兩個Min Number為Child建立子樹。
AVL Tree
1. 為BST的一種，左右子樹高度差不能超過1
2. Balance Factor Value is (-1,0,1)
3. L.child and R.child are AVL Tree
Node計算
要形成樹高h的AVL Tree：最少需要F(h+2)-1個Nodes
B-Tree
1. Balance m-way Search Tree
2. Root至少要有2個Child Node
3. 除了Root與Terminal Nodes外，其餘Nodes符合[m/2] <= degree <= m
Node計算
最多Node數；[m^n-1]/[m-1]
最多鍵值個數：m^n-1
2007年2月4日 星期日
2007年2月2日 星期五
Advanced Tree
高等樹
二元搜尋樹的評估
à依照平均比較次數來看，二元搜尋樹的樹高越低越好，可以縮短搜尋所花費的時間。其中也意味著，左右子樹樹高越平均越好。
那些演算法會受到資料輸入的情況不同而受到影響？
1. Binary Search Treeà會退化成左斜曲或右斜曲
2. Insertion Sort（插入搜尋）
3. Bubble Sort（泡泡搜尋）
4. Quick Sort（快速搜尋）
Extended Binary Search Tree（延伸二元樹）
作法：於任一個二元搜尋樹中，若有n個節點，則有n+1個空連結，而在延伸二元樹中，會於此增加一個節點，稱為外部會是失敗節點。
代號E：稱為外部節點，代號I：稱為內部節點。將用此來計算外部路徑長度與內部路徑長度。定理：E=I+2N，E與I成正比；在無加權的情況下，越平衡的二元樹E.I.越小；加權則結果未必。
最小加權外部路徑長度
通常加權值為階層數，外部節點才有加權值。à求取加權外部路徑長度。
此情況下，斜曲樹情況加權值有可能會小於平均樹。
當有加權值à需考慮加權外部路徑，此時應該如何求得最小值？
即是求「最小加權外部路徑長度」（Minimum Weight External Path Length）
求法：利用Huffman Algorithm（霍夫曼演算法）àM.W.E.P.L的解決方案
作法：每次挑選兩個最小值來建立二元樹，將刪除挑選的加權值，之後將加權總和再加入集合之中，重複前述步驟，直到全部挑完為止。
霍夫曼編碼非唯一解！T(n)=O(n*logn)
應用：解碼問題最短時間、編碼方式、平均編碼長度
編碼規則：出現頻率越低者，編碼長度愈長；出現頻率越高者，編碼長度越短。
解編碼問題技巧：給與頻率的話，表示Root為頻率分母值，各分子為樹末端。依照霍夫曼方式進行二元樹建立。左子樹給予編碼位元0；右子樹給予編碼位元1。各符號的編碼即為0與1的組合長度。若求編碼平均長度，就以每個編碼的長度乘以出現頻率，相加後，即為答案。
About AVL Tree
我們都知道AVL Tree為一個平衡的二元搜尋樹。
這一部分屬於高等樹，不過已經拉到二元樹去講了，畢竟這個部份是不會被拆開來考的。
最重要的莫過於二元搜尋樹的繪圖與
About B-Tree
它不是二元搜尋樹！
Degree=m > 2，這種二元搜尋樹稱為B-Tree。用來解決解決外部搜尋問題，以降低樹高減少搜尋次數。故B-Tree為Balance m-way Search Tree，可以是空樹。非空樹，則同時符合下列條件：Root Child>=2；除Root以外，所有NODE Degree必介於m/2與m的中間，以及所有的Terminal Node皆在同一Level。
B-Tree v.s. Binary Search Tree
Balance Tree = All Terminal Node（leafs）in same level
二元搜尋樹的評估
à依照平均比較次數來看，二元搜尋樹的樹高越低越好，可以縮短搜尋所花費的時間。其中也意味著，左右子樹樹高越平均越好。
那些演算法會受到資料輸入的情況不同而受到影響？
1. Binary Search Treeà會退化成左斜曲或右斜曲
2. Insertion Sort（插入搜尋）
3. Bubble Sort（泡泡搜尋）
4. Quick Sort（快速搜尋）
Extended Binary Search Tree（延伸二元樹）
作法：於任一個二元搜尋樹中，若有n個節點，則有n+1個空連結，而在延伸二元樹中，會於此增加一個節點，稱為外部會是失敗節點。
代號E：稱為外部節點，代號I：稱為內部節點。將用此來計算外部路徑長度與內部路徑長度。定理：E=I+2N，E與I成正比；在無加權的情況下，越平衡的二元樹E.I.越小；加權則結果未必。
最小加權外部路徑長度
通常加權值為階層數，外部節點才有加權值。à求取加權外部路徑長度。
此情況下，斜曲樹情況加權值有可能會小於平均樹。
當有加權值à需考慮加權外部路徑，此時應該如何求得最小值？
即是求「最小加權外部路徑長度」（Minimum Weight External Path Length）
求法：利用Huffman Algorithm（霍夫曼演算法）àM.W.E.P.L的解決方案
作法：每次挑選兩個最小值來建立二元樹，將刪除挑選的加權值，之後將加權總和再加入集合之中，重複前述步驟，直到全部挑完為止。
霍夫曼編碼非唯一解！T(n)=O(n*logn)
應用：解碼問題最短時間、編碼方式、平均編碼長度
編碼規則：出現頻率越低者，編碼長度愈長；出現頻率越高者，編碼長度越短。
解編碼問題技巧：給與頻率的話，表示Root為頻率分母值，各分子為樹末端。依照霍夫曼方式進行二元樹建立。左子樹給予編碼位元0；右子樹給予編碼位元1。各符號的編碼即為0與1的組合長度。若求編碼平均長度，就以每個編碼的長度乘以出現頻率，相加後，即為答案。
About AVL Tree
我們都知道AVL Tree為一個平衡的二元搜尋樹。
這一部分屬於高等樹，不過已經拉到二元樹去講了，畢竟這個部份是不會被拆開來考的。
最重要的莫過於二元搜尋樹的繪圖與
About B-Tree
它不是二元搜尋樹！
Degree=m > 2，這種二元搜尋樹稱為B-Tree。用來解決解決外部搜尋問題，以降低樹高減少搜尋次數。故B-Tree為Balance m-way Search Tree，可以是空樹。非空樹，則同時符合下列條件：Root Child>=2；除Root以外，所有NODE Degree必介於m/2與m的中間，以及所有的Terminal Node皆在同一Level。
B-Tree v.s. Binary Search Tree
| B-Tree | Binary Search Tree |
| m/2 <> | 0 =< degree ="<"> |
| External Search | Internal Search |
| Balance Tree | Not all Balance Tree |
Balance Tree = All Terminal Node（leafs）in same level
Hashing
雜湊
雜湊的定義：為一資料「儲存」與「搜尋擷取」之機制。
最適合靜態資料搜尋。
作法：Xff(X)結果
F(X)函數為透過雜湊表來決定之。
Hashing Table中有B個buckets桶子，一個bucket有s個slot槽，每一個slot可放置一筆資料。
Hashing Problem
碰撞（Collision）
定義：不同的Data x, y有可能雜湊後，f(x)=f(y)，這種狀況謂之碰撞。
溢位（Overflow）
定義：當有碰撞發生時，且Bucket沒有多餘slot可以儲存。
有碰撞不一定有溢位；有溢位必定有碰撞。
One Bucket, One slot. 有碰撞有溢位；有溢位有碰撞。
Hashing Function的設計方法
平方值取中間數：將位值平方，之後擷取中間適當個數值。
Mod法：有b個buckets，則f(x)=x mod b….取餘數
摺疊相加法：
X = 12320324111220
位移摺疊：123+203+241+112+20=699
邊界摺疊：123+302+241+211+20=897
溢位問題處理
1. 線性探測（Linear probing）
2. 二次方探測
3. 再散置
4. Link List
線性探測
由碰撞的空間向下搜尋，未被使用的空間來儲存。
缺點：容易造成資料群聚現象，大量資料會導致碰撞次數增加，搜尋可存空間時間拉長。
二次方探測
解決上述資料群聚現象，當溢位發生時，利用(f(X)+i^2)mod b找另外一個地方。若結果為負值，則需加上b。其中，i值須介於1和(b-1)/2中間。
雜湊的定義：為一資料「儲存」與「搜尋擷取」之機制。
最適合靜態資料搜尋。
作法：Xff(X)結果
F(X)函數為透過雜湊表來決定之。
Hashing Table中有B個buckets桶子，一個bucket有s個slot槽，每一個slot可放置一筆資料。
Hashing Problem
碰撞（Collision）
定義：不同的Data x, y有可能雜湊後，f(x)=f(y)，這種狀況謂之碰撞。
溢位（Overflow）
定義：當有碰撞發生時，且Bucket沒有多餘slot可以儲存。
有碰撞不一定有溢位；有溢位必定有碰撞。
One Bucket, One slot. 有碰撞有溢位；有溢位有碰撞。
Hashing Function的設計方法
平方值取中間數：將位值平方，之後擷取中間適當個數值。
Mod法：有b個buckets，則f(x)=x mod b….取餘數
摺疊相加法：
X = 12320324111220
位移摺疊：123+203+241+112+20=699
邊界摺疊：123+302+241+211+20=897
溢位問題處理
1. 線性探測（Linear probing）
2. 二次方探測
3. 再散置
4. Link List
線性探測
由碰撞的空間向下搜尋，未被使用的空間來儲存。
缺點：容易造成資料群聚現象，大量資料會導致碰撞次數增加，搜尋可存空間時間拉長。
二次方探測
解決上述資料群聚現象，當溢位發生時，利用(f(X)+i^2)mod b找另外一個地方。若結果為負值，則需加上b。其中，i值須介於1和(b-1)/2中間。
Sort and Search
排序與搜尋
搜尋的方法：
1. Linear Search – 線性搜尋
2. Binary Search – 二分法搜尋
3. Fibonacci Search – 費氏搜尋
4. Interploation Search – 插補搜尋
Linear Search
線性搜尋
作法：從頭到尾依照資料順序一筆筆比對搜尋。
時間複雜度：O(n)平均比較次數(n+1)/2
優點：支援循序隨機存取資料，紀錄可不用先行排序。
Binary Search Tree
二元搜尋樹
需要先排序，需先把資料由小到大排好。需要隨機隨取支援，意味只能使用陣列實做，不能使用鏈結。
作法：比中間值大往右搜尋，比中間值小往左搜尋。
二元搜尋樹搜尋演算法
BST Search algorithm
void BSTSearch(T,X)
{
if (T=null)
printf("Not Found");
else if T->data=X
printf("Found");
else if T->data>X
BSTSearch(T->Lchild,X);
else
BSTSearch(T->Rchild,X);
}
二元搜尋樹插入演算法
BST Insert algorithm
void BSTInsert(T,X)
{
if (T=null)
temp=new treepointer;
temp->data=X;
temp->Lchild=null;
temp->Rchild=null;
T=temp;
else if T->data>X
BSTInsert(T->Lchild,X);
else
BSTInsert(T->Rchild,X);
}
Binary Search Decision Tree
二元搜尋決策樹
Decision的建立為Root必為該段中間值。
Sort排序
依存放方式可以分成兩種：
內部排序：排序資料置於Memory中來處理。
外部排序：資料量大，須經由Memory與Disk之間處理之。
依結果可以分成：
穩定的排序法（stable）：不會進行沒有必要的交換步驟。
不穩定的排序法（unstable）：會進行沒有必要的交換步驟。
各種排序法的比較
說明：上面三種為初等排序法，下面三種為高等排序法
（這張表必須記憶，除非你有把握短時間推算）
Insertion Sort（插入排序法）
作法：將第i項資料插入到前面（i-1）項已排好的紀錄中，使得已排序結果變成i項已排序序列。
時間複雜度：
最佳情況（完全排序）：只要資料為n筆，則必做n-1次比較。
最差情況（順序相反）：只要資料為n筆，則必做n^2次比較。
空間複雜度：交換時，僅多使用一個空間來儲存暫存值。
穩定排序：數值等於不會進行交換動作。
插入排序演算法
insertion sort algorithm
void insertion_sort(int a[],int n)
{
int i,j;
for (i=1; i<=n-1; i++) j=i; while (j>0) && (a[j]5的情況，會交換！
選擇排序演算法
selection sort algorithm
void selection_sort(int a[],int n)
{
int i,j,min;
for (i=0; i<=n-2; i++) min=i; for (j=i+1; j<=n-1; j++) if a[j]0; i--)
for (j=0; ja[j+1]
swap(a[j],a[j+1]);
}
Quick Sort（快速排序法）
特性：平均狀況下，執行時間最短的排序法。採用divide and conquer概念。
作法：每回合拿第一筆資料當作C.K.，使用兩個變數，i從第一筆資料開始找筆C.K更大的值，j從第n筆資料開始找比C.K.小的值。當ij，則C.K.跟j互換，並停止。
時間複雜度：
最佳情況（完全排序）：只要資料為n筆，則必做n+c n*logn次比較。
最差情況（順序相反）：只要資料為n筆，則必做n^2次比較。
空間複雜度：
最佳：O(logn)
最差：O(n)
不穩定排序：不管中間排序狀況，只要條件符合，一蓋交換。會有5+>5情況發生。
快速排序演算法
quick sort algorithm
void quick_sort(int a[],int m,int n)
{
int i,j,k;
if m < i="m;" j="n+1;" k="a[m];">k);
if i <> swap(a[m],a[j]);
quick_sort(a,m,j-1);
quick_sort(a,j+1,n);
}
Merge Sort（合併排序法）
特色：較常使用於外部排序法。
作法：有兩種。
Iterative Merge Sort
兩兩一對，一對對比較後合併。
26,5,77,1,61,11,59,15,48,19
[26,5],[77,1],[61,11],[59,15],[48,19]
[5,26],[1,77],[11,61],[15,59],[19,48]
[1,5,26,77],[11,15,59,61],[19,48]
[1,5,11,15,26,59,61,77],[19,48]
1,5,11,15,19,26,48,59,61,77
Recursive Merge Sort
Divide and Conquer
26,5,77,1,61,11,59,15,48,19
[5,26],77,[1,61],[11,59],15,[19,48]
[5,26,77],[1,61],[11,15,59],[19,48]
[1,5,26,61,77],[11,15,19,48,59]
1,5,11,15,19,26,48,59,61,77
時間複雜度：最佳、最差、平均均相同為O(n*logn)。
空間複雜度：O(n)。
穩定排序法：數值等於不會交換。
Heap Sort（堆積排序法）
關於Heap Tree請看Tree章節相關介紹。
進行Heap Sort之前，請先建立Heap Tree。
從Heap Tree中把Root Output出來，就是排序後的結果了。
可以選擇建立Max-Min Heap Tree或是Min-Max Heap Tree，輸出結果就分別是由大到小或是由小到大。
搜尋與排序向來是資結與演算法的重點！~
搜尋的方法：
1. Linear Search – 線性搜尋
2. Binary Search – 二分法搜尋
3. Fibonacci Search – 費氏搜尋
4. Interploation Search – 插補搜尋
Linear Search
線性搜尋
作法：從頭到尾依照資料順序一筆筆比對搜尋。
時間複雜度：O(n)平均比較次數(n+1)/2
優點：支援循序隨機存取資料，紀錄可不用先行排序。
Binary Search Tree
二元搜尋樹
需要先排序，需先把資料由小到大排好。需要隨機隨取支援，意味只能使用陣列實做，不能使用鏈結。
作法：比中間值大往右搜尋，比中間值小往左搜尋。
二元搜尋樹搜尋演算法
BST Search algorithm
void BSTSearch(T,X)
{
if (T=null)
printf("Not Found");
else if T->data=X
printf("Found");
else if T->data>X
BSTSearch(T->Lchild,X);
else
BSTSearch(T->Rchild,X);
}
二元搜尋樹插入演算法
BST Insert algorithm
void BSTInsert(T,X)
{
if (T=null)
temp=new treepointer;
temp->data=X;
temp->Lchild=null;
temp->Rchild=null;
T=temp;
else if T->data>X
BSTInsert(T->Lchild,X);
else
BSTInsert(T->Rchild,X);
}
Binary Search Decision Tree
二元搜尋決策樹
Decision的建立為Root必為該段中間值。
Sort排序
依存放方式可以分成兩種：
內部排序：排序資料置於Memory中來處理。
外部排序：資料量大，須經由Memory與Disk之間處理之。
依結果可以分成：
穩定的排序法（stable）：不會進行沒有必要的交換步驟。
不穩定的排序法（unstable）：會進行沒有必要的交換步驟。
各種排序法的比較
| 排序法/狀況 | 平均狀況 | 最差情況 | 額外空間 | 穩定排序法 |
| 插入排序法 | O(N^2) | O(N^2) | O(1) | YES |
| 選擇排序法 | O(N^2) | O(N^2) | O(1) | NO |
| 氣泡排序法 | O(N^2) | O(N^2) | O(1) | YES |
| 快速排序法 | O(N log2 N) | O(N^2) | O(log2 N) | NO |
| 合併排序法 | O(N log2 N) | O(N log2 N) | O(N) | YES |
| 堆積排序法 | O(N log2 N) | O(N log2 N) | O(1) | NO |
說明：上面三種為初等排序法，下面三種為高等排序法
（這張表必須記憶，除非你有把握短時間推算）
Insertion Sort（插入排序法）
作法：將第i項資料插入到前面（i-1）項已排好的紀錄中，使得已排序結果變成i項已排序序列。
時間複雜度：
最佳情況（完全排序）：只要資料為n筆，則必做n-1次比較。
最差情況（順序相反）：只要資料為n筆，則必做n^2次比較。
空間複雜度：交換時，僅多使用一個空間來儲存暫存值。
穩定排序：數值等於不會進行交換動作。
插入排序演算法
insertion sort algorithm
void insertion_sort(int a[],int n)
{
int i,j;
for (i=1; i<=n-1; i++) j=i; while (j>0) && (a[j]
選擇排序演算法
selection sort algorithm
void selection_sort(int a[],int n)
{
int i,j,min;
for (i=0; i<=n-2; i++) min=i; for (j=i+1; j<=n-1; j++) if a[j]
for (j=0; j
swap(a[j],a[j+1]);
}
Quick Sort（快速排序法）
特性：平均狀況下，執行時間最短的排序法。採用divide and conquer概念。
作法：每回合拿第一筆資料當作C.K.，使用兩個變數，i從第一筆資料開始找筆C.K更大的值，j從第n筆資料開始找比C.K.小的值。當i
時間複雜度：
最佳情況（完全排序）：只要資料為n筆，則必做n+c n*logn次比較。
最差情況（順序相反）：只要資料為n筆，則必做n^2次比較。
空間複雜度：
最佳：O(logn)
最差：O(n)
不穩定排序：不管中間排序狀況，只要條件符合，一蓋交換。會有5+>5情況發生。
快速排序演算法
quick sort algorithm
void quick_sort(int a[],int m,int n)
{
int i,j,k;
if m < i="m;" j="n+1;" k="a[m];">k);
if i <> swap(a[m],a[j]);
quick_sort(a,m,j-1);
quick_sort(a,j+1,n);
}
Merge Sort（合併排序法）
特色：較常使用於外部排序法。
作法：有兩種。
Iterative Merge Sort
兩兩一對，一對對比較後合併。
26,5,77,1,61,11,59,15,48,19
[26,5],[77,1],[61,11],[59,15],[48,19]
[5,26],[1,77],[11,61],[15,59],[19,48]
[1,5,26,77],[11,15,59,61],[19,48]
[1,5,11,15,26,59,61,77],[19,48]
1,5,11,15,19,26,48,59,61,77
Recursive Merge Sort
Divide and Conquer
26,5,77,1,61,11,59,15,48,19
[5,26],77,[1,61],[11,59],15,[19,48]
[5,26,77],[1,61],[11,15,59],[19,48]
[1,5,26,61,77],[11,15,19,48,59]
1,5,11,15,19,26,48,59,61,77
時間複雜度：最佳、最差、平均均相同為O(n*logn)。
空間複雜度：O(n)。
穩定排序法：數值等於不會交換。
Heap Sort（堆積排序法）
關於Heap Tree請看Tree章節相關介紹。
進行Heap Sort之前，請先建立Heap Tree。
從Heap Tree中把Root Output出來，就是排序後的結果了。
可以選擇建立Max-Min Heap Tree或是Min-Max Heap Tree，輸出結果就分別是由大到小或是由小到大。
搜尋與排序向來是資結與演算法的重點！~
Graph
圖形
圖形的定義：
G(V,E)
V：表頂點集合（Vertex）
E：表邊集合（Edge）
圖形的分類：有向圖（每個連結屬於單向性質，有箭號）與無向圖（每個連結屬於雙向性質，無箭號）
完全無向圖最多總邊數為n*(n-1)/2
完全有向圖最多總邊數為n*(n-1)
子圖稱為圖形的一部份
Cycle為一個簡單路徑，且起點與終點相同
Connected Component：圖形中任何一點出發均可以抵達任何一個目的點，EX：TREE
有向圖才有強連結，強連結意味任何一點出發，軍可以到達任一目的地點
About Degree
關於分支度：in-degree, out-degree（無向圖只有Degree）
圖形的表示方式
1. adjacency matrix用陣列表示
節點有幾個便是使用幾維陣列表示。兩軸皆為節點編號，1表示與該節點存在連結，0表示與該節點沒有連接。
故有向圖為不對稱陣列，無向圖為對稱陣列（可以僅存上三角或下三角）。
2. adjacency list 用鏈結表示
無向圖：該節點的所有out-degree表示。例如：1可以連結到節點2和4，則表示為1à2à3（箭號為指標指下下一個串列）
無向圖：表示方法同上，僅表示out-degree。間接連結稱為反相鄰矩陣。
圖形追蹤
目的：拜訪所有的節點一次。
方法：
下面兩種搜尋法皆存在多重解，不會是唯一解！
Depth First Search（DFS）
深度搜尋法
Breadth First Search（BFS）
廣度搜尋法
DFS：是以某一個節點為出發點，不斷前進拜訪重未拜訪過的節點，直到無路可走，或是所有相鄰節點皆已經被拜訪，則重回上一個節點，尋找尚未被拜訪過的節點，直到所有相鄰節點均被拜訪。
實做：使用Stack來實做
BFS：是以某一個節點為出發點，以該節點相連接的節點先行拜訪，未連接的節點則不拜訪。出發點與拜訪過的節點形成子圖，與子圖所相鄰的所有節點再先行拜訪，直到所有節點均正確無誤被拜訪完。
實做：利用Queue來實做。
Spanning Tree
擴張樹、展開樹
定義：該圖必為Connected，且任一節點與頂點路徑必為單一路徑。
特色：若非Connected則無Spanning Tree。Spanning Tree存在多重解。N個節點圖形，連接邊數必為n-1個邊。
實做：DFS Spanning Tree、BFS Spanning Tree。
Minimum cost spanning tree
最小成本擴張樹
定義：在圖形符合Spanning的條件下，圖形邊上附有權值，權值加總連接情況為該圖的最小值稱為最小成本擴張樹。
應用：城市交通連接、電路牽線。
運作方法：
1. Kruskal’s algo（克魯斯克爾演算法）
2. Prime’s algo
3. Sollin’s algo
前面兩個比較重要。
Kruskal’s algo
克魯斯克爾演算法
以加入邊觀念為出發點。
Step 1.將圖形（子圖以外）邊權重由小到大排列。
Step 2.從最小權重的邊開始選擇，形成子圖，已形成子圖的節點連接邊不再選擇。
Step 3.重複執行步驟1-2，直到圖形所有節點均被順利連接（均挑選進子圖）。
Prime’s algo
以加入頂點觀念為出發點。
Step 1.從圖形中挑選任一個出發點進入子圖，計算與該出發點相鄰節點的邊權重。
Step 2.挑選與該子圖所有相鄰的權重邊挑選最小權重連接的節點加入子圖。
Step 3.不斷重複步驟2-3，直到所有節點均順利被連接（均挑選進入子圖）。
請注意！最小擴張樹存再唯一解，不論使用哪一種演算法，均可得到相同答案。
意指：可以使用不同演算法來驗算最小擴張樹的正確與否。
Greedy Algorithm
貪婪演算法的定義：
解決最佳化問題的演算法，其解題過程可以看成是由一連串的決策步驟所組成，每一個步驟都有一組選擇要選定。
Greedy Method在每一步驟執行時，總是選定那看起來到目前為止最好的選擇。
但Greedy Method無法保證到最後的結果是最佳解，唯有在某些時候，可以碰巧得到該問題的最佳解答。Greedy是非常有效率及簡單的演算法，但是很難證明其正確性。
圖形的最短路徑
求單一節點到其他節點的最短路徑：O(n^2)
求所有頂點到其他頂點的最短路徑：O(n^3)
Dijkstra’s Algorithm
為了解決從圖形某一特定點抵達各目的地權重問題而設計。
單一頂點到其他頂點的最短路徑實做：利用陣列儲存。（幾個節點則為幾維乘幾維陣列）請使用表格來表示。
從指定的地點開始計算最短路徑，一一藉由擴張方式把所有節點串接，且更新所有連接節點為最小路徑值，最後一列維度表示的即為答案。
AOV Network
用來表示工作先後順序的圖形，且有多重解存在。有Cycle沒有關係。
Topological Order
沒有Cycle的AOV Network，需確定所有工作都有前導作業，不會形成迴圈情況。
圖形的定義：
G(V,E)
V：表頂點集合（Vertex）
E：表邊集合（Edge）
圖形的分類：有向圖（每個連結屬於單向性質，有箭號）與無向圖（每個連結屬於雙向性質，無箭號）
完全無向圖最多總邊數為n*(n-1)/2
完全有向圖最多總邊數為n*(n-1)
子圖稱為圖形的一部份
Cycle為一個簡單路徑，且起點與終點相同
Connected Component：圖形中任何一點出發均可以抵達任何一個目的點，EX：TREE
有向圖才有強連結，強連結意味任何一點出發，軍可以到達任一目的地點
About Degree
關於分支度：in-degree, out-degree（無向圖只有Degree）
圖形的表示方式
1. adjacency matrix用陣列表示
節點有幾個便是使用幾維陣列表示。兩軸皆為節點編號，1表示與該節點存在連結，0表示與該節點沒有連接。
故有向圖為不對稱陣列，無向圖為對稱陣列（可以僅存上三角或下三角）。
2. adjacency list 用鏈結表示
無向圖：該節點的所有out-degree表示。例如：1可以連結到節點2和4，則表示為1à2à3（箭號為指標指下下一個串列）
無向圖：表示方法同上，僅表示out-degree。間接連結稱為反相鄰矩陣。
圖形追蹤
目的：拜訪所有的節點一次。
方法：
下面兩種搜尋法皆存在多重解，不會是唯一解！
Depth First Search（DFS）
深度搜尋法
Breadth First Search（BFS）
廣度搜尋法
DFS：是以某一個節點為出發點，不斷前進拜訪重未拜訪過的節點，直到無路可走，或是所有相鄰節點皆已經被拜訪，則重回上一個節點，尋找尚未被拜訪過的節點，直到所有相鄰節點均被拜訪。
實做：使用Stack來實做
BFS：是以某一個節點為出發點，以該節點相連接的節點先行拜訪，未連接的節點則不拜訪。出發點與拜訪過的節點形成子圖，與子圖所相鄰的所有節點再先行拜訪，直到所有節點均正確無誤被拜訪完。
實做：利用Queue來實做。
Spanning Tree
擴張樹、展開樹
定義：該圖必為Connected，且任一節點與頂點路徑必為單一路徑。
特色：若非Connected則無Spanning Tree。Spanning Tree存在多重解。N個節點圖形，連接邊數必為n-1個邊。
實做：DFS Spanning Tree、BFS Spanning Tree。
Minimum cost spanning tree
最小成本擴張樹
定義：在圖形符合Spanning的條件下，圖形邊上附有權值，權值加總連接情況為該圖的最小值稱為最小成本擴張樹。
應用：城市交通連接、電路牽線。
運作方法：
1. Kruskal’s algo（克魯斯克爾演算法）
2. Prime’s algo
3. Sollin’s algo
前面兩個比較重要。
Kruskal’s algo
克魯斯克爾演算法
以加入邊觀念為出發點。
Step 1.將圖形（子圖以外）邊權重由小到大排列。
Step 2.從最小權重的邊開始選擇，形成子圖，已形成子圖的節點連接邊不再選擇。
Step 3.重複執行步驟1-2，直到圖形所有節點均被順利連接（均挑選進子圖）。
Prime’s algo
以加入頂點觀念為出發點。
Step 1.從圖形中挑選任一個出發點進入子圖，計算與該出發點相鄰節點的邊權重。
Step 2.挑選與該子圖所有相鄰的權重邊挑選最小權重連接的節點加入子圖。
Step 3.不斷重複步驟2-3，直到所有節點均順利被連接（均挑選進入子圖）。
請注意！最小擴張樹存再唯一解，不論使用哪一種演算法，均可得到相同答案。
意指：可以使用不同演算法來驗算最小擴張樹的正確與否。
Greedy Algorithm
貪婪演算法的定義：
解決最佳化問題的演算法，其解題過程可以看成是由一連串的決策步驟所組成，每一個步驟都有一組選擇要選定。
Greedy Method在每一步驟執行時，總是選定那看起來到目前為止最好的選擇。
但Greedy Method無法保證到最後的結果是最佳解，唯有在某些時候，可以碰巧得到該問題的最佳解答。Greedy是非常有效率及簡單的演算法，但是很難證明其正確性。
圖形的最短路徑
求單一節點到其他節點的最短路徑：O(n^2)
求所有頂點到其他頂點的最短路徑：O(n^3)
Dijkstra’s Algorithm
為了解決從圖形某一特定點抵達各目的地權重問題而設計。
單一頂點到其他頂點的最短路徑實做：利用陣列儲存。（幾個節點則為幾維乘幾維陣列）請使用表格來表示。
從指定的地點開始計算最短路徑，一一藉由擴張方式把所有節點串接，且更新所有連接節點為最小路徑值，最後一列維度表示的即為答案。
AOV Network
用來表示工作先後順序的圖形，且有多重解存在。有Cycle沒有關係。
Topological Order
沒有Cycle的AOV Network，需確定所有工作都有前導作業，不會形成迴圈情況。
Tree and Binary Tree
樹與二元樹
樹的定義：數不允許沒有節點，最少需含有一個樹根節點（Root），含有多個互斥集合（子樹）。
利用鏈結表示樹
Data+Link1+Link2+…
計算樹葉子數演算法
count leaf number algorithm
void countleaf(T)
{
if (T==null) return 0;
else
if (T->Lchild==null) && (T->Rchild==null)
return 1;
else
return(countleaf(T->Lchild)+countleaf(T->Rchild));
}
每個節點擁有的Link數目等於Degree
Binary Tree（二元樹，別名Ordered Tree）
定義：二元樹允許沒有節點，每個節點僅允許Degree介於0-2之間。
二元樹的定理
i level的NODE各數最多為2^(i-1)個
利用數學歸納法證明
樹高為K的二元樹，NODE各數最多有2^k-1個
利用NODE計算式證明
二元樹利用資料結構法來表示
左子樹（指向左子樹樹根） + Data + 右子樹（指向右子樹樹根）
優：刪除與加入節點容易.缺：約浪費掉一半Link空間.對父節點無法得知
二元樹利用陣列表示
將任何二元樹想成完滿二元樹依照編號順序逐步存入陣列中。需耗費一個K維陣列
優：不需要額外的連結空間，找左右節點與父節點均容易。
缺：插入刪除節點不易，對斜曲樹不適用，過於浪費空間。
二元樹的追蹤與走訪：前序（preorder）、中序（inorder）、後序（postorder）
給與中序及任一個前序或後序繪出二元樹技巧。
二元樹追蹤遞迴演算法虛擬碼
範例前序：（採用遞廻方式寫法）
Procedure preorder(T:pointer to B.T. Root)
Begin
If(T!=nul)then begin
Print(T->.Data);
Preorder(T->L.child);
Preorder(T->R.child);
End.
End.
自撰中序：（非recursive）
Inorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL)
s.push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop(T);
printf(T->data);
s.pop();
T=T->rchild;
Else
Done=True;
}
自撰前序：
Preorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL)
Printf(T->data);
s.Push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop();
s.pop();
T=T->Rchild;
Else
Done=True;
}
自撰後序：
Postorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL);
s.push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop();
printf(T->data);
s.pop();
T=T->rchild;
Else
Done=true;
}
二元樹中的應用
Count計算NODE數
計算樹結點數演算法
count node number algorithm
void count(T)
{
if (T==null) return 0;
else
return(count(T->Lchild)+count(T->Rchild)+1);
}
計算樹高：Return(Max(L.child,R.child)+1)
計算樹高度演算法
count height algorithm
void height(T)
{
int Lheight,Rheight;
if (T==null) return 0;
else
Lheight:=height(T->Lchild);
Rheight:=height(T->Rchild);
return(Max(Lheight,Rheight)+1);
}
SWAP二元樹：每個NODE左右子點互換；虛擬碼需用temp暫存元素
交換左右子樹演算法
void SWAP(T)
{
if (T!=null)
SWAP(T->Lchild);
SWAP(T->Rchild);
temp=T->Lchild;
T->Lchild=T->Rchild;
T->Rchild=temp;
}
排序（Sort）二元樹：利用二元搜尋樹（Binary Search Tree）。
二元搜尋樹的定義：
1. 左子樹資料 < Root < 右子樹資料
2. 左右子樹均為二元搜尋樹
特性：使用中序輸出必能將資料數值由小到大排序
搜尋：平均比較次數為O(n)；最佳比較次數為O(logn)à當為完滿二元搜尋樹時
TreeàBinary Tree：所有同階元素連結，刪除所有與父親之聯結，僅保留最左連結，所有連結順時針轉45度完成。
ForestàBinary Tree：各Forest的層級子節點互相連接，刪除所有與父親連結，僅保留最左邊連接，各連結順時針轉45度，將所有Forest Root串接。
Binary TreeàForest：將右邊兒子連結逆時針轉45度拉起，打斷所有水平連結。
轉完，前序、中序會相同，後序不會相同！
N個NODE所能畫出幾種不同的二元樹？ANS：組合2N取N除以N+1
4個NODE可以排出14棵二元樹
何謂動態平衡樹？若增刪節點，有可能影響整棵樹的節點變化稱之動態平衡樹。
AVL Tree
不一定是平衡的Binary Search Tree（動態平衡樹）
Balance Tree = All Terminal Node（leafs）in same level
滿足左子樹高度與右子樹高度差不能超過1；左右子樹亦為AVL Tree；平衡係數必為-1,0,1。
需動態調整不平衡狀態！
調整方式：中間鍵值往上拉；左兒子給左；右兒子給右。
新增元素較Root為大往右掛，較小則往左掛。
AVL TREE的insert、delete、search之時間複雜度皆為O(log n)
形成高度h的AVL TREE最少需要幾個NODE？
需要的個數為F(n+2)-1；F意指費柏納西數列函數
Heap Tree
堆積樹（於下面有堆積樹的補充說明）也是動態平衡樹的一種
滿足左子樹高度與右子樹高度差不能超過1；最後加入的元素於該階層的尾部，透過比較大小的方式進行元素互換維持動態平衡。
兩種堆積樹調整模式：
Max Root（Max-Min Heap）：根目錄值為樹中最大值，新增元素值必須與他的父親重複比較，較大值階層上升，位置互換。
Min Root（Min-Max Heap）：根目錄值為樹中最小值，新增元素值必須與他的父親重複比較，較小值階層上升，位置互換。 - 未說明之堆積樹指的是這種
確定動態平衡時，為同兩個相鄰階層確認數值比較及交換。
Thread Binary Tree
引線二元樹
利用Link List表示具有N個NODE的二元樹，浪費n+1個Links。
將空的Links視為”引線”指標
常用中序引線二元樹
樹在資料結構與演算法中佔有非常重要的地位。這邊的介紹還未包含高等樹！
樹的定義：數不允許沒有節點，最少需含有一個樹根節點（Root），含有多個互斥集合（子樹）。
利用鏈結表示樹
Data+Link1+Link2+…
計算樹葉子數演算法
count leaf number algorithm
void countleaf(T)
{
if (T==null) return 0;
else
if (T->Lchild==null) && (T->Rchild==null)
return 1;
else
return(countleaf(T->Lchild)+countleaf(T->Rchild));
}
每個節點擁有的Link數目等於Degree
Binary Tree（二元樹，別名Ordered Tree）
定義：二元樹允許沒有節點，每個節點僅允許Degree介於0-2之間。
二元樹的定理
i level的NODE各數最多為2^(i-1)個
利用數學歸納法證明
樹高為K的二元樹，NODE各數最多有2^k-1個
利用NODE計算式證明
二元樹利用資料結構法來表示
左子樹（指向左子樹樹根） + Data + 右子樹（指向右子樹樹根）
優：刪除與加入節點容易.缺：約浪費掉一半Link空間.對父節點無法得知
二元樹利用陣列表示
將任何二元樹想成完滿二元樹依照編號順序逐步存入陣列中。需耗費一個K維陣列
優：不需要額外的連結空間，找左右節點與父節點均容易。
缺：插入刪除節點不易，對斜曲樹不適用，過於浪費空間。
二元樹的追蹤與走訪：前序（preorder）、中序（inorder）、後序（postorder）
給與中序及任一個前序或後序繪出二元樹技巧。
二元樹追蹤遞迴演算法虛擬碼
範例前序：（採用遞廻方式寫法）
Procedure preorder(T:pointer to B.T. Root)
Begin
If(T!=nul)then begin
Print(T->.Data);
Preorder(T->L.child);
Preorder(T->R.child);
End.
End.
自撰中序：（非recursive）
Inorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL)
s.push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop(T);
printf(T->data);
s.pop();
T=T->rchild;
Else
Done=True;
}
自撰前序：
Preorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL)
Printf(T->data);
s.Push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop();
s.pop();
T=T->Rchild;
Else
Done=True;
}
自撰後序：
Postorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL);
s.push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop();
printf(T->data);
s.pop();
T=T->rchild;
Else
Done=true;
}
二元樹中的應用
Count計算NODE數
計算樹結點數演算法
count node number algorithm
void count(T)
{
if (T==null) return 0;
else
return(count(T->Lchild)+count(T->Rchild)+1);
}
計算樹高：Return(Max(L.child,R.child)+1)
計算樹高度演算法
count height algorithm
void height(T)
{
int Lheight,Rheight;
if (T==null) return 0;
else
Lheight:=height(T->Lchild);
Rheight:=height(T->Rchild);
return(Max(Lheight,Rheight)+1);
}
SWAP二元樹：每個NODE左右子點互換；虛擬碼需用temp暫存元素
交換左右子樹演算法
void SWAP(T)
{
if (T!=null)
SWAP(T->Lchild);
SWAP(T->Rchild);
temp=T->Lchild;
T->Lchild=T->Rchild;
T->Rchild=temp;
}
排序（Sort）二元樹：利用二元搜尋樹（Binary Search Tree）。
二元搜尋樹的定義：
1. 左子樹資料 < Root < 右子樹資料
2. 左右子樹均為二元搜尋樹
特性：使用中序輸出必能將資料數值由小到大排序
搜尋：平均比較次數為O(n)；最佳比較次數為O(logn)à當為完滿二元搜尋樹時
TreeàBinary Tree：所有同階元素連結，刪除所有與父親之聯結，僅保留最左連結，所有連結順時針轉45度完成。
ForestàBinary Tree：各Forest的層級子節點互相連接，刪除所有與父親連結，僅保留最左邊連接，各連結順時針轉45度，將所有Forest Root串接。
Binary TreeàForest：將右邊兒子連結逆時針轉45度拉起，打斷所有水平連結。
轉完，前序、中序會相同，後序不會相同！
N個NODE所能畫出幾種不同的二元樹？ANS：組合2N取N除以N+1
4個NODE可以排出14棵二元樹
何謂動態平衡樹？若增刪節點，有可能影響整棵樹的節點變化稱之動態平衡樹。
AVL Tree
不一定是平衡的Binary Search Tree（動態平衡樹）
Balance Tree = All Terminal Node（leafs）in same level
滿足左子樹高度與右子樹高度差不能超過1；左右子樹亦為AVL Tree；平衡係數必為-1,0,1。
需動態調整不平衡狀態！
調整方式：中間鍵值往上拉；左兒子給左；右兒子給右。
新增元素較Root為大往右掛，較小則往左掛。
AVL TREE的insert、delete、search之時間複雜度皆為O(log n)
形成高度h的AVL TREE最少需要幾個NODE？
需要的個數為F(n+2)-1；F意指費柏納西數列函數
Heap Tree
堆積樹（於下面有堆積樹的補充說明）也是動態平衡樹的一種
滿足左子樹高度與右子樹高度差不能超過1；最後加入的元素於該階層的尾部，透過比較大小的方式進行元素互換維持動態平衡。
兩種堆積樹調整模式：
Max Root（Max-Min Heap）：根目錄值為樹中最大值，新增元素值必須與他的父親重複比較，較大值階層上升，位置互換。
Min Root（Min-Max Heap）：根目錄值為樹中最小值，新增元素值必須與他的父親重複比較，較小值階層上升，位置互換。 - 未說明之堆積樹指的是這種
確定動態平衡時，為同兩個相鄰階層確認數值比較及交換。
Thread Binary Tree
引線二元樹
利用Link List表示具有N個NODE的二元樹，浪費n+1個Links。
將空的Links視為”引線”指標
常用中序引線二元樹
樹在資料結構與演算法中佔有非常重要的地位。這邊的介紹還未包含高等樹！
2007年2月1日 星期四
Stack and Queue
堆疊與佇列
堆疊（FILO）與佇列（FIFO）的基本性質
堆疊與佇列的實做使用陣列或鏈結
佇列的變形 – 環狀佇列
堆疊的應用：順序反轉、中序轉後序、圖形的DFS、副程式、遞迴
佇列的應用：排隊行為、工作排程、圖形中的BFS、I/O裝置佇列、系統效能模擬
前序、中序、後序互轉
利用堆疊把中序轉後序（陣列可以將順序顛倒）
以陣列表示stack演算法
item stack[N+1]; //stack[0]空間不使用,則可放N個元素,表1~N
int top=0;
void push(int x)
{
if (top==n)
print("stack is full");
else
stack[++top]=x;
}
int pop()
{
if (top==0)
print("stack is empty");
else
x=stack[top--];
return x;
}
以Linked-List表示stack演算法
typedef struct node *pointer;
struct node{
int data;
pointer link;
}
void push(int x)
{
pointer temp;
temp=(pointer)malloc(struct node);
temp->data=x; //temp->data=(*temp).data,記得*temp需加上括號
temp->link=top;
top=temp;
}
int pop()
{
pointer temp;
int x;
if (top==null)
print("stack is empty");
else
temp=top;
top=temp->link;
x=temp->data;
free(temp);
return x;
}
以Linked-List表示Queue演算法
typedef struct node *pointer;
struct node{
int data;
pointer next;
}
pointer Front,Rear;
void AddNode(x)
{
pointer temp;
temp=(pointer)malloc(struct node);
temp->data=x;
temp->next=null;
if (Rear=null) //表Queue是空的
Front=temp;
Rear=temp;
else
Rear->next=temp;
Rear=temp;
}
int DeleteNode()
{
pointer temp;
int x;
if (Front==null)
print("Queue is empty");
else
temp=Front;
Front=temp->next
x=temp->data;
free(temp);
return x;
}
ps:演算法多指虛擬碼(pseudo code)。
堆疊（FILO）與佇列（FIFO）的基本性質
堆疊與佇列的實做使用陣列或鏈結
佇列的變形 – 環狀佇列
堆疊的應用：順序反轉、中序轉後序、圖形的DFS、副程式、遞迴
佇列的應用：排隊行為、工作排程、圖形中的BFS、I/O裝置佇列、系統效能模擬
前序、中序、後序互轉
利用堆疊把中序轉後序（陣列可以將順序顛倒）
以陣列表示stack演算法
item stack[N+1]; //stack[0]空間不使用,則可放N個元素,表1~N
int top=0;
void push(int x)
{
if (top==n)
print("stack is full");
else
stack[++top]=x;
}
int pop()
{
if (top==0)
print("stack is empty");
else
x=stack[top--];
return x;
}
以Linked-List表示stack演算法
typedef struct node *pointer;
struct node{
int data;
pointer link;
}
void push(int x)
{
pointer temp;
temp=(pointer)malloc(struct node);
temp->data=x; //temp->data=(*temp).data,記得*temp需加上括號
temp->link=top;
top=temp;
}
int pop()
{
pointer temp;
int x;
if (top==null)
print("stack is empty");
else
temp=top;
top=temp->link;
x=temp->data;
free(temp);
return x;
}
以Linked-List表示Queue演算法
typedef struct node *pointer;
struct node{
int data;
pointer next;
}
pointer Front,Rear;
void AddNode(x)
{
pointer temp;
temp=(pointer)malloc(struct node);
temp->data=x;
temp->next=null;
if (Rear=null) //表Queue是空的
Front=temp;
Rear=temp;
else
Rear->next=temp;
Rear=temp;
}
int DeleteNode()
{
pointer temp;
int x;
if (Front==null)
print("Queue is empty");
else
temp=Front;
Front=temp->next
x=temp->data;
free(temp);
return x;
}
ps:演算法多指虛擬碼(pseudo code)。
Array and Link List
陣列與鏈結串列
這在資料結構和演算法當中，扮演著重要的工具角色。
觀念與使用技術格外重要。
About Array
計算一維陣列起始位置：
宣告方式A(C,P)A[i]= l + ( i – C ) * d
l：起始位置；d：元素大小；C：第一個元素
Ex：A陣列宣告：A(-3,9)，元素大小=4，起始位置=100，詢問A[5]的起始位置？
A[5]=100+(5-(-3))*4=100+32=132
記算二維陣列起始位置：
宣告方式A(1…c,1…p)列row；行column
Row Major：l + [(i-c)*n+(j-p)]*d
Column Major：l + [(j-1)*m+(i-1)]*d
多項式利用陣列儲存技術
依陣列儲存次序，存入最高次方項，最高次方項係數，依序降冪排列直到0次方項[常數]。
非零次方項儲存法：
X的100次方項加8
不宜用上述方式儲存，應依陣列順序儲存非零次方項數，首位係數+次方項…依次方項降冪排列至0。
利用陣列表示稀疏舉陣：
首列儲存列數.行數.非零元素
從第二列開始儲存所在列數.所在行數.該元素值
直到稀疏矩陣中所有非零元素都被儲存為止
特殊矩陣儲存：上三角或下三角.對稱矩陣
About Link List
Array v.s. Link List
陣列特色：必連續性配置、隨機存取、刪除插入不易、合併不易
鏈結特色：可以不連續配置、只能循序存取、插入刪除容易、合併容易、每筆資料多占一格空間
Link List Cycle
可用來實做環狀佇列
Double Link List
雙向鏈結串列與單向鏈結串列比較
雙鍵可知前後元素、較為強固、刪除無須告知前面節點、插入刪除較麻煩、空間耗損多一。
利用單鏈節串列進行多項式表示法
依序儲存多項式係數、多項式指數、下一個節點位置，重複步驟直到多項式所以元素皆被儲存
鏈結的實際操作…新增節點.刪除節點.串成環狀
這在資料結構和演算法當中，扮演著重要的工具角色。
觀念與使用技術格外重要。
About Array
計算一維陣列起始位置：
宣告方式A(C,P)A[i]= l + ( i – C ) * d
l：起始位置；d：元素大小；C：第一個元素
Ex：A陣列宣告：A(-3,9)，元素大小=4，起始位置=100，詢問A[5]的起始位置？
A[5]=100+(5-(-3))*4=100+32=132
記算二維陣列起始位置：
宣告方式A(1…c,1…p)列row；行column
Row Major：l + [(i-c)*n+(j-p)]*d
Column Major：l + [(j-1)*m+(i-1)]*d
多項式利用陣列儲存技術
依陣列儲存次序，存入最高次方項，最高次方項係數，依序降冪排列直到0次方項[常數]。
非零次方項儲存法：
X的100次方項加8
不宜用上述方式儲存，應依陣列順序儲存非零次方項數，首位係數+次方項…依次方項降冪排列至0。
利用陣列表示稀疏舉陣：
首列儲存列數.行數.非零元素
從第二列開始儲存所在列數.所在行數.該元素值
直到稀疏矩陣中所有非零元素都被儲存為止
特殊矩陣儲存：上三角或下三角.對稱矩陣
About Link List
Array v.s. Link List
陣列特色：必連續性配置、隨機存取、刪除插入不易、合併不易
鏈結特色：可以不連續配置、只能循序存取、插入刪除容易、合併容易、每筆資料多占一格空間
Link List Cycle
可用來實做環狀佇列
Double Link List
雙向鏈結串列與單向鏈結串列比較
雙鍵可知前後元素、較為強固、刪除無須告知前面節點、插入刪除較麻煩、空間耗損多一。
利用單鏈節串列進行多項式表示法
依序儲存多項式係數、多項式指數、下一個節點位置，重複步驟直到多項式所以元素皆被儲存
鏈結的實際操作…新增節點.刪除節點.串成環狀
Recursive program and Interactive program
遞迴程式與反覆程式
簡而化之的說明:
遞廻就是使用重複呼叫副程式(subroutine)的概念。
遞迴會使用到堆疊(Stack)的技術，所以他是堆疊應用之ㄧ。
反覆則是使用廻圈(loop)處理問題。像是for.whiile...等語法。
遞迴演算法精隨：費柏納西數列實作.遞迴階乘實作
費柏納西數列特性一定要記憶：F(n)=F(n-1)+F(n-1)，n是項數。
費柏納西數列：1,1,2,3,5,8,13,21,34,55…
費柏納西數列推導請使用數學歸納法！
補充：其實遞廻這個概念時常被使用，不只是用在程式上。網路環境中也經常使用遞廻的概念。
簡而化之的說明:
遞廻就是使用重複呼叫副程式(subroutine)的概念。
遞迴會使用到堆疊(Stack)的技術，所以他是堆疊應用之ㄧ。
反覆則是使用廻圈(loop)處理問題。像是for.whiile...等語法。
遞迴演算法精隨：費柏納西數列實作.遞迴階乘實作
費柏納西數列特性一定要記憶：F(n)=F(n-1)+F(n-1)，n是項數。
費柏納西數列：1,1,2,3,5,8,13,21,34,55…
費柏納西數列推導請使用數學歸納法！
補充：其實遞廻這個概念時常被使用，不只是用在程式上。網路環境中也經常使用遞廻的概念。
Time Complexity and Space Complexity
T(n) and S(n) 時間複雜度與空間複雜度
Algorithm的時間複雜度和遞迴程式
Time Complexity（時間複雜度）：於演算法中常用漸進式符號來表示其執行時間的複雜度。
時間函數：T（n）指計算程式中指令所執行的次數。
Time Complexity時間複雜度問題請使用代數解決之。
複雜度的大小排序：O(C) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!)
解時間複雜度方法：遞迴代數
Algorithm的時間複雜度和遞迴程式
Time Complexity（時間複雜度）：於演算法中常用漸進式符號來表示其執行時間的複雜度。
時間函數：T（n）指計算程式中指令所執行的次數。
Time Complexity時間複雜度問題請使用代數解決之。
複雜度的大小排序：O(C) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!)
解時間複雜度方法：遞迴代數
Data Structure and Algorithms Definition
資料結構與演算法的定義
何謂資料結構？
資料結構是電腦存儲、組織資料的方式。通常情況下，精心選擇的資料結構可以帶來更高的運行或者存儲效率的演算法。資料結構往往同高效的檢索演算法和指標技術有關。
何謂演算法？
所謂的演算法則是指一組個數有限的步驟，用來描述完成某一個工作或解決某一個問題所使用的方法；如果逐一正確的執行每一動作之後，就能完成一個特定的工作或解決一個特定的問題。
每一個正確的演算法則，皆須具備有以下五個特性：
1. 輸入性（Input）
2. 輸出性（Output）
3. 明確性（Precision）
4. 有限性（Finiteness）
5. 有效性（Determinism）
何謂資料結構？
資料結構是電腦存儲、組織資料的方式。通常情況下，精心選擇的資料結構可以帶來更高的運行或者存儲效率的演算法。資料結構往往同高效的檢索演算法和指標技術有關。
何謂演算法？
所謂的演算法則是指一組個數有限的步驟，用來描述完成某一個工作或解決某一個問題所使用的方法；如果逐一正確的執行每一動作之後，就能完成一個特定的工作或解決一個特定的問題。
每一個正確的演算法則，皆須具備有以下五個特性：
1. 輸入性（Input）
2. 輸出性（Output）
3. 明確性（Precision）
4. 有限性（Finiteness）
5. 有效性（Determinism）
Data Structure and Algorithms
資料結構與演算法
程式？何謂程式呢？ 除了程式語言以外
程式可以分成資料結構和演算法兩大領域
Program = Data Structure + Algorithms
這兩個領域有哪些重點呢？
DATA STRUCTURE
資料結構重點一覽
1. Algorithm的時間複雜度和遞迴程式
2. Array（陣列）
3. Stack and Queue（堆疊和佇列）
4. Link List（鏈結）
5. Tree and Binary Tree（樹以及二元樹）
6. Graph（圖形）
7. Searching and Sort（搜尋和排序）
8. Hashing（雜湊）
9. Advanced Tree（高等樹）
ALGORITHMS
演算法重點一覽
1. Mathematics for Algorithms（演算法的數學）
2. Data Structures（資料結構）
3. Divide and Conquer（分開與征服）
4. Searching（搜尋）
5. Sorting and Selection（排序與選擇）
6. Greedy Algorithms（貪婪演算法）
7. Dynamical Programming（動態規劃）
8. Text Searching（文字搜尋）
9. P and NP（P與NP問題）
10. Coping with NP-Completeness（完全NP的複製）
11. Parallel and Distributed Algorithms（平行和分散演算法）
這樣的歸類方式其實不太好！尤其對於考試或是工具的使用，幾乎沒有什麼整合和交集...
於是我試想將把這兩塊領域的重點自己整理一下。多出了文章群組Data Structure and Algoriths！
程式？何謂程式呢？ 除了程式語言以外
程式可以分成資料結構和演算法兩大領域
Program = Data Structure + Algorithms
這兩個領域有哪些重點呢？
DATA STRUCTURE
資料結構重點一覽
1. Algorithm的時間複雜度和遞迴程式
2. Array（陣列）
3. Stack and Queue（堆疊和佇列）
4. Link List（鏈結）
5. Tree and Binary Tree（樹以及二元樹）
6. Graph（圖形）
7. Searching and Sort（搜尋和排序）
8. Hashing（雜湊）
9. Advanced Tree（高等樹）
ALGORITHMS
演算法重點一覽
1. Mathematics for Algorithms（演算法的數學）
2. Data Structures（資料結構）
3. Divide and Conquer（分開與征服）
4. Searching（搜尋）
5. Sorting and Selection（排序與選擇）
6. Greedy Algorithms（貪婪演算法）
7. Dynamical Programming（動態規劃）
8. Text Searching（文字搜尋）
9. P and NP（P與NP問題）
10. Coping with NP-Completeness（完全NP的複製）
11. Parallel and Distributed Algorithms（平行和分散演算法）
這樣的歸類方式其實不太好！尤其對於考試或是工具的使用，幾乎沒有什麼整合和交集...
於是我試想將把這兩塊領域的重點自己整理一下。多出了文章群組Data Structure and Algoriths！
訂閱：
文章 (Atom)
