第一章 導論(Introduction).

Presentation on theme: "第一章 導論(Introduction)."— Presentation transcript:

0 http://mail.im.tku.edu.tw/~ychou ftp://mail.im.tku.edu.tw/Prof_Hou
資料與檔案結構 淡江大學 資訊管理系 侯 永 昌 ftp://mail.im.tku.edu.tw/Prof_Hou

1 第一章 導論(Introduction)

2 演算法 演算法(Algorithm)︰在有限步驟中，解決數學問題的程序 演算法具有以下5個特性︰ 準確描述的輸入(Input)
每個指令必須具有明確性(Definiteness) 每個指令必須具有正確性(Correctness) 每個指令必須具有有限性(Finiteness) 結果的描述和輸出(Output)

3 資料結構 演算法＋資料結構＝程式 資料結構是在演算法中，將需要計算處理的資料加以建立組織，而成的結構
資料結構是演算法所處理的對象；演算法是處理資料結構的方法 描述演算法的方式包括︰自然語言、流程圖、結構化英文、虛擬碼、程式語言

4 程式的好壞 一個好的程式，必須滿足下列的條件︰ 正確完成預期的工作 可維護性高 效率高 記憶體需求低

5 可維護性 編寫程式是否符合模組化(modularity)的原則，提供由上而下(Top-down)的理解思路
所有的常數、變數與函式(Function)名稱是否有意義 所有函式的輸入、輸出及功能是否明確地被定義 是否在適當的地方加上註解 說明文件是否詳實完備

6 執行效率 程式的執行效率通常由迴圈的執行次數來決定 for (i=1; i<n; i++)
result=result+1; 執行n-1次 for (i=1; i<=n; i++) for (j=1; j<n; j++) result=result+1; 執行n*(n-1)次 for (j=i+1; j<=n; j++) result=result+1; 執行n*(n-1)/2次

7 時間複雜度︰O(f(n)) n f(n) 2 10 100 103 104 106 1 logn 3.3 6.6 13 20 n 1000
33 660 1.3*105 2*107 n2 4 108 1012 n3 8 109 1018 2n 1024 1030 10300 103000 n! 3.6*106 10158 102567 

8 時間複雜度︰O(f(n)) 如果電腦一秒鐘可以做十億個運算，1030個動作需要1030/109*60*60*24*365  3*1013年
計算時間複雜度時，只計算最高次項，而且不考慮係數的因素 例︰5n2 + 6n + 9 = O(n2) 例︰3nlogn + 9n + 10 =O(nlogn) 例︰9n nlogn + 9 = O(n2) 例︰2n n2 + 6n + 9 = O(2n)

9 時間複雜度︰O(f(n)) 假設在某個PC上執行一個時間複雜度為O(n2)的演算法，發現它一分鐘可以處理1000筆資料，如果將這個演算法移到一個快100倍的工作站上去執行，試問這個工作站一分鐘可以處理多少筆資料？ 這個PC一分鐘可以執行10002 = 106個動作，快100倍的工作站一分鐘可以執行108個動作，假設它可以處理X筆資料  X2 = 108  X = 104

10 課程內容 陣列(Array)：比較容易使用 陣列資料都儲存在連續的記憶體內，因此需要事先宣告陣列的大小 通常陣列內的資料都會被排序
利用二分搜尋法在查尋資料時會比較快速，O(logn) 因為陣列內的資料都儲存在連續的記憶體內，因此在新增與刪除資料時需要做實體資料的搬移，動作會比較慢，O(n) 資料 …

11 課程內容 堆疊(Stack)： 堆疊內的資料具有後進先出的特性(Last In First Out; LIFO) 例如：餐廳中餐盤的使用
佇列(Queue)： 佇列內的資料具有先進先出的特性(First In First Out; FIFO) 例如：餐廳中排隊的人群

12 課程內容 串列(Linked List)： 資料不再儲存在連續的記憶體內，而是利 用指標將一筆筆的資料串接在一起
當資料量不確定時，就不方便使用陣列， 而串列則可以很容易的改變它的大小 但是在搜尋、新增與刪除資料時會比較慢， O(n)，但是在新增與刪除資料時不需要做 實體資料的搬移 而且需要浪費額外的指標(pointer)空間 … 資料 指標

13 課程內容 二元搜尋樹(Binary search tree)： 是一種多串列的結構，因此在搜尋、新增與刪除資料時會比較快，O(logn)
51 39 70 20 42 49 75 10 45 63 80 課程內容 二元搜尋樹(Binary search tree)： 是一種多串列的結構，因此在搜尋、新增與刪除資料時會比較快，O(logn) 需要浪費兩倍指標 (pointer)的空間 運算比較複雜，隨時需要保持樹的平衡

14 課程內容 高度平衡樹： AVL tree B-tree, B+-tree Graph：
樹狀結構適合表現一對多的關係，而圖形結構則適合表現多對多的關係 Sort：排序技術 Search：搜尋技術

15 第二章 陣列(Array)

16 陣列 陣列是由多個相同型別的元素所組成的集合，這些元素共用一個名稱，並且加上編號(註標)，以資區別 記憶體 起始位置 1000 1004
1008 1012 1016 1020 1024 一維陣列 A [0] [1] [2] [3] [4] [5] [6] 佔記憶體 位元組數 4 存放資料 的值 38 21 33 7 35 43 27

17 陣列 這些元素在記憶體中會佔用連續的位置，也就是說中間不可以有空位出現
例︰A[0]的位址為X，假設每個元素的大小為len個bytes，則A[i]的位址為X + i*len 例︰陣列int A[60]，假設每個元素的大小為2個bytes，則陣列A共需60*2=120位元組的記憶體 例︰假設A[0]在記憶體中的位置為03C416，則 A[20] = 03C *2 = 03C = 03EC16 A[39] = 03C *2 = 03C E16 = 例︰A[5]在記憶體的位置為220，則A[15]在哪裡？ A[5] = X + 5*2 = 220  X = 210 A[15] = X + 15*2 = = 240

18 數字系統：十進位 我們習慣說的百分位、十分位、個位、十位、百位、千位、…，其實有點誤導，比較精確的說法應該是第-2位、第-1位、第0位、第1位、第2位、第3位、… 十進位：只有0 ~ 9十個數字，逢十進一 如何看待 這個數字？ 1983 = 1× × ×10 + 3×1 + 6× ×0.01 = 1× × × × × ×10-2 你怎麼知道1983的第-2位是4？第1位是8？…？ 將整數的部份不斷的除10，所得到的每一個餘數，依序就是第0位、第1位、第2位、第3位、…的數字；而小數的部份不斷的乘10，所得到的每一個整數，依序就是第-1位、第-2位、…的數字

19 數字系統：其他數字系統 二進位：只有0 ~ 1兩個數字，逢二進一
= 1×27 + 1×26 + 1×24 + 1×23 + 1×20 + 1×2-1 八進位：只有0 ~ 7八個數字，逢八進一 = 3×83 + 4×82 + 5×81 + 6×80 + 1× ×8-2 十六進位：有16個數字(0 ~ F)，逢16進一 2D4.A16 = 2× × × ×16-1

20 數字系統 如何將其他進位系統換成十進位？ 二進位：11011001.1012
= 1×27 + 1×26 + 1×24 + 1×23 + 1×20 + 1× ×2-3 = = 八進位： = 3×83 + 4×82 + 5×81 + 6×80 + 1× ×8-2 = 3× ×64 + 5×8 + 6×1 + 1× × = 十六進位： 2D4.A16 = 2× × × ×16-1 = 2× ×16 + 4×1 + 10× =

21 數字系統 如何將十進位系統換成其他進位？ 整數的部份不斷的除，求餘數，第一個餘數就是第0位，第二個餘數就是第1位，…
二進位：217÷2 = 108餘1、108÷2 = 54餘0 54÷2 = 27餘0、27÷2 = 13餘1、13÷2 = 6餘1 6÷2 = 3餘0、3÷2 = 1餘1、1÷2 = 0餘1  八進位：1838÷8 = 229餘6、229÷8 = 28餘5 28÷8 = 3餘4、3÷8 = 0餘3  34568 十六進位： 724÷16 = 45餘4、45÷16 = 2餘13 2÷16 = 0餘2  2D416

22 數字系統 如何將十進位系統換成其他進位？ 小數的部份不斷的乘，求整數，第一個整數就是第-1位，第二個整數就是第-2位，…
二進位：0.625×2 = 1.25、0.25×2 = 0.5 、0.5×2 = 1.0  八進位：0.1875×8 = 1.5、0. 5×8 = 4.0  0.148 十六進位： 0.625×16 = 10.0  0.A16 電腦中的數字系統有不盡小數的問題，通常只準確到小數後面的第五、六位

23 二維陣列︰list[r][c] 以列為主(row major)︰大多數語言採用
0, 0 0, 1 0, 2 … 0, c-1 1, 0 1, 1 1, 2 i, j r -1, 0 r -1, 1 r -1, c-1 以列為主(row major)︰大多數語言採用 list[i][j]的位址=X+((i-0)*c+(j-0))*len =X+(i*c+j)*len 以行為主(column major) list[i][j]的位址=X+((j-0)*r+(i-0))*len =X+(j*r+i)*len 寫程式前，應先查清楚該語言採用哪種設計

24 二維陣列︰list[r][c] 例：假設3列7行的二維陣列A的起始位置為1000， 每一個元素的大小為4個位元組，則A[1][5]所在的記憶體位置為何？ Row-major︰ (1*7 + 5)*4 = 1048 Column-major︰ (5*3 + 1)*4 = 1064 A [0] [1] [2] [3] [4] [5] [6] 38 21 33 7 35 43 27 32 1 22 31 5 3 23 13 12 24 15

25 二維陣列︰list[r][c] 例：假設一陣列A[10][20]，其A[2][3]的位置為2000，每一個元素的大小為2個位元組，則A[7][13]所在的記憶體位置為何？ Row-major︰X + (2*20 + 3)*2 = 2000  X = 1914 (7* )*2 = = 2220 Colum-major︰X + (3*10 + 2)*2 = 2000  X = 1936 (13*10 + 7)*2 = = 2210

26 二維陣列︰list[r][c] 例：假設一陣列A[m][n]，其A[0][2], A[1][2], A[2][1]的位置分別為為104, 118, 130，則A[3][4]所在的記憶體位置為何？ 一定是Row-major，why？ X + (0*n + 2)*len = 104 X + (1*n + 2)*len = 118 X + (2*n + 1)*len = 130  len = 2, n = 7, X = 100 A[3][4]：X + (3*n + 4)*len = *2 = 150 至於m = ？不知道

27 三維陣列︰A[c1][c2][c3] c1 c2 c3 A[i][j][k]距離A[0][0][0]有整整i層(每層有c2*c3個元素)，在同層中在它之前有整整j列(每列有c3個元素)，而同列中在它之前有還有k個元素。因此row-major時A[i][j][k]距離A[0][0][0]有i*c2*c3+j*c3+k個元素 例︰int A[3][3][2] – row-major 第0個平面有A[0][0][0], A[0][0][1], A[0][1][0], A[0][1][1], A[0][2][0], A[0][2][1] 第1個平面有A[1][0][0], A[1][0][1], A[1][1][0], A[1][1][1], A[1][2][0], A[1][2][1] 第2個平面有A[2][0][0], A[2][0][1], A[2][1][0], A[2][1][1], A[2][2][0], A[2][2][1]

28 c1 c2 c3 三維陣列︰A[c1][c2][c3] Column-major時A[i][j][k]距離A[0][0][0]有k*c1*c2+j*c1+i個元素 例︰int A[3][3][2] – column-major 第0個平面有A[0][0][0], A[1][0][0], A[2][0][0], A[0][1][0], A[1][1][0], A[2][1][0], A[0][2][0], A[1][2][0], A[2][2][0] 第1個平面有A[0][0][1], A[1][0][1], A[2][0][1], A[0][1][1], A[1][1][1], A[2][1][1], A[0][2][1], A[1][2][1], A[2][2][1] Row-major最後一個維度最先變化，依序向前推，column-major第一個維度最先變化，依序向後推

29 三維陣列︰A[c1][c2][c3] 例︰假設一個陣列宣告為int A[3][3][2]，每一個int的大小為2個位元組，其起始位置為12345，試問A[1][2][0]的記憶體位置為何？ 解：row-major：它的前面只有一整面，在這一面上前面還有兩列，在這一列上前面還有0個元素，所以在它的前面有10個元素 A[1][2][0] = (1*3*2+2*2+0)*2 = 12365 解：column-major：它的前面有0個面，在這一面上前面還有兩行，在這一列上前面還有1個元素，所以在它的前面有7個元素 A[1][2][0] = (0*3*3+2*3+1)*2 = 12359

30 陣列運算︰搜尋、讀出、寫入 在陣列中搜尋值為value 的元素位置 讀出編號為i的元素的內容；A=list[i]
int ArraySearch(int list[], int n, int value) { int i = 0; while (i < n) //還沒有試完n筆資料 { if (list[i] = = value) return (i); //找到了 i++; //試下一筆資料 } return (-1); //沒有找到 } 讀出編號為i的元素的內容；A=list[i] 將新值寫入編號為i的元素位置；list[i]=A

31 陣列運算︰插入 在編號為i的位置上插入一個新元素，原來的i和i之後的元素各往後移一個位置
void ArrayInsert(int list[], int n, int i, int value) { int counter; if (i < 0 || i >= n) return; //例外條件 //由後往前處理，以便空出位置i來 for (counter = n-1; counter > i; counter--) // for (初始條件; 迴圈繼續執行的條件; 迴圈增量) list[counter] = list[counter-1]; list[i] = value; //將值插入 }

32 陣列運算︰刪除 刪除編號為i的元素，原來i之後的元素各往前移一個位置(中間不可以出現空位)
void ArrayDelete(int list[], int n, int i) { int counter; if (i < 0 || i >= n) return; //例外狀況 for (counter = i; counter < n-1; counter++) list[counter] = list[counter+1]; } //由前往後處理 要搬移資料實在太麻煩，而且也怕你後悔，因此實務上都只在上面加上一個刪除的符號，而不立即刪除，累積到一定數量後，再一併刪除

33 陣列運算︰複製 將陣列的所有元素複製到另一個陣列中 讀出、寫入︰O(1) 搜尋、插入、刪除、複製︰O(n)
void ArrayCopy(int list1[], int list2[], int n) { int counter; for (counter = 0; counter < n; counter++) list1[counter] = list2[counter]; } 讀出、寫入︰O(1) 搜尋、插入、刪除、複製︰O(n)

34 二維陣列的應用 矩陣的轉置(transpose)︰行列互換
void ArrTrans(int A[Rows][Cols], int B[Cols][Rows]) { int i, j; for (i = 0; i < Rows; i++) for (j = 0; j < Cols; j++) B[j][i] = A[i][j]; }

35 二維陣列的應用 矩陣的相加 void ArrAdd(int A[Rows][Cols], int B[Cols][Rows] , int C[Cols][Rows]) { int i, j; for (i = 0; i < Rows; i++) for (j = 0; j < Cols; j++) C[i][j] = A[i][j] + B[i][j]; }

36 矩陣的相乘 Cij = Ai1*B1j + Ai2*B2j + Ai3*B3j + … + Ain*Bnj

37 二維陣列的應用 矩陣的相乘 void ArrMul(int A[m][n], int B[n][t] , int C[m][t])
{ int i, j, k; for (i = 0; i < m; i++) for (j = 0; j < t; j++) { C[i][j] = 0; //初始條件 for (k = 0; k < n; k++) //累加 C[i][j] = C[i][j] + A[i][k]*B[k][j]; }}

38 變數的左值和右值 變數出現在等式的左邊時，該變數代表一個地址，出現在等式的右邊時，則代表該變數的值 例：i = i + 1 address
value 1  i (1234) 5 pi 1M 6 代表 i 的值，i = 5 將6存入 i 這個位置，i = 1234

39 整數變數 address value 1  i (1234) 5 pi j 1M int i, j; 整數變數 i = 5; j = i;

40 指標變數(Pointer) *：指標變數，代表指向的意思
int *pi, *pj; *pi與*pj為指向整數的變數(稱為指標變數)，而pi、pj中存放的是它所指向的地址，也就是某個整數變數的地址。 pi中儲存的資料不是被當成數值來處理，而是被當成是記憶體的位址，*pi代表指向(跳到)pi中所儲存的那一個位置

41 指標與取址符號 &︰取址符號 pi = &i; 將變數i的地址放到變數pi中 address value 1  i (1234) 5 pi
j 1M &︰取址符號 pi = &i; 將變數i的地址放到變數pi中

42 指標與取址符號 *pi = 10; *pi代表指向pi中所儲存的那一個位置，而pi中所儲存的位置是i ，因此*pi就代表變數i
address value 1  i (1234) 10 pi 1234 j 5 1M *pi = 10; *pi代表指向pi中所儲存的那一個位置，而pi中所儲存的位置是i ，因此*pi就代表變數i *pi在左邊，代表左值 將10放到pi所指到的位置

43 指標與取址符號 j = *pi *pi代表指向pi中所儲存的那一個位置，而pi中所儲存的位置是i，因此*pi就代表變數i
address value 1  i (1234) 10 pi 1234 j 1M j = *pi *pi代表指向pi中所儲存的那一個位置，而pi中所儲存的位置是i，因此*pi就代表變數i *pi在右邊，代表右值 將pi所指到的值放到變數j中

44 結構(Structure) 將不同型別的元素集合起來，形成一種新的資料型別(結構) 宣告︰struct student s1, s2;
{ char name[8]; int age; int height; } 宣告︰struct student s1, s2; 應用︰s1.age = 20; //以欄位名稱來存取 s1.height = 170; strcpy(s1.name, “Mary”);

45 自訂型別︰typedef 宣告︰STUDENT s1, s2; 方便定義使用者需要的資料結構 typedef struct student
{ char name[8]; int age; int height; } STUDENT; 宣告︰STUDENT s1, s2;

46 字串(String) 字串以字元陣列來表示，並用一個空字元(NULL; \0)做為字串的結束
例︰char name[10] = {“Merry”}; char str[12]; [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] name M e r y \0 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] str \0

47 計算字串長度 int strlen(char s[]) { int len;
for (len = 0; s[len] != ‘\0’; len++); return(len); } 應用︰len = strlen(name)

48 複製字串 int strcpy(char s1[], char s2[]) { int i;
for (i = 0; s2[i] != ‘\0’; i++) s1[i] = s2[i]; //將s2複製到s1 s1(i) = ‘\0’; //加上空字串 } 另解︰for (i = 0; (s1[i] = s2[i]) != ‘\0’; i++); 或︰for ( ; (*s1 = *s2) != ‘\0’; s1++, s2++);

49 比較字串 比較兩個字串的內容，若完全相等，則傳回0， s1>s2傳回1， s1<s2傳回-1
int strcmp(char s1[], char s2[]) { int i; for (i = 0; s1[i] == s2[i]; i++) //字串相等就往後比對 if (s1[i] == ‘\0’ && s2[i] == ‘\0’) return 0; if (s1(i) > s2(i)) return (1); //字串1比較大 else return (-1); //字串2比較大 }

50 擷取字串 從s字串中第i個字元開始，擷取n個字元，將它們存入s1字串中。若n = 0，就表示擷取到字串的結束為止
void substr(char s1[], char s[], int i, int n) { int len, end, j, k; len = strlen(s); //計算字串有多長 end = i + n; //計算擷取的結束位置 if ((end > len) || (n == 0)) end = len; //例外處理 for (j = i, k = 0; j < end; j++, k++) s1[k] = s[j]; //擷取資料 s1(k) = ‘\0’; }

51 第三章 鏈結串列(Linked List)

52 串列及鏈結串列 串列(List)是許多同類型元素有順序的排列 用陣列結構來儲存一連串資料的優缺點是
優點︰利用註標可以快速的讀寫某一個元素 的資料。O(1) 缺點︰資料在插入和刪除時，需要進行實體 資料的搬移，以便維持資料的順序。O(n) 用鏈結的方式來儲存一連串資料，其元素 之間不必實體上連續(連續的記憶體位址)， 而是利用鏈結(link)來維持邏輯上的順序， 方便資料的插入與刪除作業

53 利用陣列結構來實作鏈結串列 但是在實作上，我們仍然可以利用陣列結構來模擬鏈結(串列)的資料 Head 3 1 6 7 3 Free 8 4
data next Table[0] 5 Table[1] 美國 6 Table[2] Table[3] 中國 1 Table[4] 2 Table[5] -1 Table[6] 英國 7 Table[7] 蘇俄 Table[8] 4 Head 3 1 6 7 3 中 1 美 6 英 7 蘇 -1 Free 8 4 2 8 4 2 5 5 -1

54 利用陣列結構來實作鏈結串列 typedef struct ListNode { char data[8]; /* 資料欄位 */
int next; /* 鏈結欄位 */ } NODE; typedef struct List { int Head, Free; NODE table[MAXNODE]; } LIST; 這個結構有三個東西，除了陣列外，還有兩個指標Head, Free data next Table[0] Table[1] Table[2] Table[3] Table[4] Table[5] Table[6] Table[7] Table[8]

55 利用陣列結構來實作鏈結串列 初始化︰Head = NULL; Free = 0;
一開始的時候，串列中沒有任何資料，所有的儲存空間都是空的、可用的空間 插入資料時就到Free list中取出(刪除)一個空間來存資料，刪除資料時就要將儲存空間還給(插入)Free list data next Table[0] 1 Table[1] 2 Table[2] 3 Table[3] 4 Table[4] 5 Table[5] 6 Table[6] 7 Table[7] 8 Table[8] -1

56 利用陣列結構來實作鏈結串列 Head 3 1 6 7 3 Free 8 4 2 8 5 data next Table[0] 5
美國 6 Table[2] Table[3] 中國 1 Table[4] 2 Table[5] -1 Table[6] 英國 7 Table[7] 蘇俄 Table[8] 4 Head 3 1 6 7 3 中 1 美 6 英 7 蘇 -1 Free 8 4 2 8 4 2 5 5 -1

57 狀況1：將法國插入在第一節點之前(例如：中國)
data next Table[0] 5 Table[1] 美國 6 Table[2] Table[3] 中國 1 Table[4] 2 Table[5] -1 Table[6] 英國 7 Table[7] 蘇俄 Table[8] 法國 43 Head 6 7 38 中 1 … 蘇 -1 8 (4’) 法 43 (3’) Free 8 4 2 84 4 2 … (1) (2) 刪從前面刪

58 狀況2：將法國插入在某一節點之後(例如：英國)
data next Table[0] 5 Table[1] 美國 6 Table[2] Table[3] 中國 1 Table[4] 2 Table[5] -1 Table[6] 英國 78 Table[7] 蘇俄 Table[8] 法國 47 Head Free 2 4 8 7 6 3 … 英 78 蘇 -1 (4) (3) 法 47 84 4 2 … (1) (2) 刪從前面刪

59 尋找插入點 代表法國 代表串列 void GetInsertNode(LIST A, char d[], int PreNode, int CurNode); { //假設串列中的資料是由小到大排列 CurNode = A.Head; //代表正在處理的節點 PreNode = -1; //代表它的前一個節點 while (CurNode != -1 && //代表空串列 (strcmp(A.table[CurNode].data, d) <= 0)) //代表還沒越過插入點 { PreNode = CurNode; //記錄前一個串列 CurNode = A.table[CurNode].next ; //找下一個節點 }}

60 插入節點 int ListInsert(LIST A, char d[]); { unsigned EmptyNode;
GetInsertNode(A, d, PreNode, CurNode); /*找插入位置*/ if (A.Free == -1) return FALSE; /*Free list中沒有空位*/ EmptyNode = A.Free; /*取出Free list中的編號*/ A.Free = A.table[A.Free].next; /*更新Free list中的編號*/ strcpy (A.table[EmptyNode].data, d); /*複製資料*/ if (PreNode == -1) /*空串列或加在第一節點之前*/ { A.table[EmptyNode].next = A.head; //修正資料串列 A.head = EmptyNode; } /*修正head*/ else { A.table[EmptyNode].next = CurNode; /*加在後面*/ A.table[PreNode].next = EmptyNode; } return TURE; } (1) (2) (3’) (4’) (3) (4)

61 狀況1：刪除中間節點(英國) Head 1 6 8 3 Free 4 2 5 46 6 Free list其實是一個Stack!!
data next Table[0] 5 Table[1] 美國 68 Table[2] Table[3] 中國 1 Table[4] 2 Table[5] -1 Table[6] 英國 84 Table[7] 蘇俄 Table[8] 法國 7 3 … 美 68 英 8 法 7 (1) Free 4 2 5 46 2 … 6 (2) (3) Free list其實是一個Stack!! 4 加從前面加

62 狀況2：刪除第一節點(中國) Head 3 1 6 31 Free 4 2 5 43 3 Free list其實是一個Stack!!
data next Table[0] 5 Table[1] 美國 6 Table[2] Table[3] 中國 14 Table[4] 2 Table[5] -1 Table[6] 英國 8 Table[7] 蘇俄 Table[8] 法國 7 31 中 14 美 6 英 8 (1’) Free 4 2 5 43 2 … 3 (2) (3) Free list其實是一個Stack!! 4 加從前面加

63 尋找刪除點 CurNode = -1表示是空串列，或是找不到合適的節點，一直比到結束的位置 strcmp(…)不等於0表示這筆資料不是英國
代表英國或中國 void GetDeleteNode(LIST A, char d[], int PreNode, int CurNode); { PreNode = CurNode = A.Head; while (CurNode != -1 && /*還不到結束的地方*/ (strcmp(A.table[CurNode].data, d))) { PreNode = CurNode; CurNode = A.table[CurNode].next ; } } CurNode = -1表示是空串列，或是找不到合適的節點，一直比到結束的位置 strcmp(…)不等於0表示這筆資料不是英國

64 刪除節點 void ListDelete(LIST A, char d[]); { int PreNode, CurNode;
GetDeleteNode(A, d, PreNode, CurNode); //尋找刪除點 if (CurNode == -1) return FALSE; //找不到 /*處理鏈結*/ if (A.head == CurNode) A.head = A.table[CurNode].next; //刪除第一節點 else A.table[PreNode].next = A.table[CurNode].next; //刪除其它節點 /*處理Free list*/ A.table[CurNode].next = A.Free; /*修正資料串列*/ A.Free = CurNode; /*修正free*/ return TURE; } (1’) (1) (2) (3)

65 例︰法國之後加入德國、再刪除中國 Head=3 Free=6 Free=4 Head=1 Free=3 data next Table[0]
5 Table[1] 美國 8 Table[2] Table[3] 中國 1 4 Table[4] 2 Table[5] -1 Table[6] 德國 7 Table[7] 蘇俄 Table[8] 法國 6

66 利用陣列結構來實作鏈結串列的用途 有些語言沒有pointer data type，因此只能用這種方法來模擬linked list
雖然是Array-base，但是它免除了陣列在insert/delete方面的缺失 如果這一次所建的linked list日後還要再使用，則動態配置(dynamic allocation)將無法滿足這個需求。因為下一次執行時，可能用的是另外一塊memory。因此指標欄位中的memory address，在下一次執行時就已經不再有意義了。以陣列(靜態配置static allocation)中的註標當作指標，就可以避免這方面的問題

67 利用陣列結構來實作鏈結串列 缺點︰必須事先宣告陣列的大小。宣告太多、而使用太少則浪費記憶體空間，宣告太少又不夠使用。因此，在記憶體的使用上比較缺乏彈性 解決之道︰利用動態配置空間來實作鏈結串列(但是它會造成前一頁動態配置的問題) 所謂動態配置就是在指標欄位中(next)存的是真正的記憶體位置(actual address)，而不是陣列結構中的註標(relative address)

68 利用動態配置空間來實作鏈結串列 typedef struct listnode { int data; /* 資料欄位 */
struct listnode *next; /* 鏈結欄位 */ } NODE; NODE *listA; C︰listA = (NODE*) malloc(sizeof(NODE)); C++︰listA = new NODE; 例︰listA->data = 20; listA->next = NULL; (*listA).data = 20; (*listA).next = NULL;

69 插入節點 int InsertAfter(NODE *p, int value); //加在p節點之後 { NODE *newnode;
newnode = (NODE*) malloc(sizeof(NODE)); //向OS要一塊記憶體 if (newnode == NULL) return FALSE; //記憶體不足 /*連接串列*/ newnode->next = p->next; p->next = newnode; newnode->data = value; return TRUE; } … p newnode

70 刪除節點 Head prenode node int DeleteNode(NODE *head, NODE *node);
… int DeleteNode(NODE *head, NODE *node); { NODE *prenode; //刪除node節點 if (head == NULL) return FALSE; /*空串列*/ if (head == node) head = node->next; /*第一節點*/ else { prenode = GetPreNode(head, node);//見下一頁 if (prenode == NULL) return FALSE; /*要刪除的節點不在串列中*/ else prenode->next = node->next; } free(node); /*回收被刪除的節點*/ return TRUE; }

71 取得前一個節點 NODE *GetPreNode(NODE *head, NODE *node); { NODE *p, *q;
p = q = head; //串列的走訪通常需要記錄前後 //兩個指標，p代表前一個指標， // q代表後一個指標 while ((q != NULL) && (q != node)) //繼續搜尋 { p = q; q = q->next; } if (q != NULL) return (p); //找到了 else return (NULL); //沒找到 }

72 串列的走訪 void ListTraverse(NODE *head); { NODE *p = head; //p從head開始
while (p); //只要p還是true，不是null //就表示串列還沒有結束 { printf(“\n%d”, p->data); p = p->next; } }

73 鏈結串列的建立︰加在串列前端 int InsertHead(NODE *head, int value);
{ NODE *newnode, *head; if ((newnode = (NODE*) malloc(sizeof(NODE)) == NULL) return FALSE; newnode->next = head; //加在最前面 newnode->data = value; head = newnode; //修正head return TRUE; }

74 鏈結串列的建立︰加在串列尾端 int InsertTail(NODE *head, int value);
{ NODE *newnode, *head; if ((newnode = (NODE*) malloc(sizeof(NODE)) ==NULL) return FALSE; newnode->next = NULL; //加在最後面 newnode->data = value; if (head ==NULL) head = newnode; //加到空串列 else { for (p = head; p->next != NULL; p = p->next); //找到串列結束的位置 p->next = newnode; } return TRUE; }

75 環狀鏈結串列 Head指向最後一個節點(最大的元素值) (head->next == head) A B C D head D
-1 Head︰空串列

76 走訪環狀鏈結串列 int CInsertTraverse(NODE *head); { NODE *p = head;
if (p == NULL) //空串列 { printf (“Empty list.”); return FALSE; } do { p = p->next; //由第一個元素開始找起 printf (“\n%d”, p->data); } while (p != head); }

77 雙向鏈結串列 可以方便的找到predecessor，安全性也比較高 Typedef struct dlist_node
{ struct dlist_node *left int data; struct dlist_node *right } head A B C D

78 插入節點 int InsertAfter(Dnode *p, int value); { Dnode *newnode;
newnode = (Dnode*) malloc(sizeof(Dnode)); if (newnode == NULL) return FALSE; newnode->data = value; newnode->left = p; newnode->right = p->right; p->right->left = newnode; p-> right = newnode; return TRUE; } … p 2 3 4 1 newnode

79 刪除節點 Head p int DeleteNode(NODE *head, NODE *p); { NODE *prenode;
… int DeleteNode(NODE *head, NODE *p); { NODE *prenode; if (head == NULL) return FALSE; //空串列 if (head == p) head = p->right; //第一節點 if (p == NULL) return FALSE; //節點不存在 p->left->right = p->right; p->right->left = p->left; } free(p); /*回收被刪除的節點*/ return TRUE; }

80 雙向環狀鏈結串列 Head是指向第一個節點或是最後一個節點都沒有關係 typedef struct dlist_node
{ struct dlist_node *left int data; struct dlist_node *right } head A B C D

81 計算串列長度 int ListLenght(NODE *head); { int counter = 0; NODE *p = head;
while (p != NULL) { counter++; //累加長度 p = p->next; } return counter; }

82 串接兩個鏈結串列 int ListConcate(NODE *listA, NODE *listB);
{ NODE *p = listA; //由listA開始做起 if (p ==NULL) listA = listB; else { while (p->next != NULL) //找到listA的結束位置 p = p->next; p->next = listB; } } listA listB

83 將一個鏈結串列之鏈結反轉 int ListConcate(NODE *listA, NODE *listB);
{ NODE *p = listA, *q = NULL; while (p != NULL) { r = q; q = p; p = p->next; q->next = r; } listB = q; } r q p listA listB

84 多項式的表示與運算 typedef struct plistnode { float coef; /*係數*/
int expo; /*冪次*/ struct plistnode *next; /*鏈結指標*/ } Pnode; 例︰A(x) = 5x x x + 6 B(x) = 9x x2 - 4x + 5 A 5 4 6.1 2 2.9 1 6 B 9 5 3.2 2 -4 1

85 多項式的表示與運算 兩個多項式分別從高冪次項往右掃描 比較兩多項式第一節點冪次的大小 凡是已經被處理(複製)的節點，多項式就 往右移一項
冪次大者，複製到輸出多項式C(x) 如果冪次相同，則兩多項式係數相加。如果 結果不為0，才將結果複製到輸出多項式 C(x)，否則就不必處理 凡是已經被處理(複製)的節點，多項式就 往右移一項 重複步驟2-3，直到兩多項式都處理完畢 為止

86 多項式的表示與運算 Pnode *PolyAdd(Pnode *pa, Pnode *pb); { Pnode *c, *ctail;
c = (Pnode *)malloc(sizeof(Pnode)); ctail = c; while (pa && pb) { if (pa->expo > pb->expo) /*a的冪次大*/ { ctail = AddTail(ctail, pa->coef, pa->expo); pa = pa->next; //將a輸出，並往下移一項 } else if (pa->expo < pb->expo) /*b的冪次大*/ { ctail = AddTail(ctail, pb->coef, pb->expo); pb = pb->next; //將b輸出，並往下移一項 }

87 多項式的表示與運算 else /*冪次相等*/
{ if ((pa->coef + pb->coef) !=0) //檢查係數是否為0 ctail = AddTail(ctail, pa->coef+pb->coef, pa->expo); pa = pa->next; pb = pb->next; } } while(pa) /*最後的處理，處理a多項式*/ { ctail = AddTail(ctail, pa->coef, pa->expo); pa = pa->next; } while (pb) /*最後的處理，處理b多項式*/ { ctail = AddTail(ctail, pb->coef, pb->expo); pb = pb->next; } return (c); }

88 稀疏矩陣(Sparse matrix) 矩陣中大多數的資料均為0，用二維矩陣來存資料太浪費了
typedef struct mlistnode { float data; /*係數*/ int col, row; /*行列位置*/ struct mlistnode *right, *down; //鏈結指標 } Pnode; row col data down right

89 1 2 3 4 5 2 1 4 2 1 1 5 1 3 6 2 2 1 3 3 3 5 1 4 4 2 4 5 6

90 串列的其他應用 Very large integer︰電腦中之整數有其範圍，例如︰2 byte的整數在-32768~32767之間。因此對於很大的整數可以用linked list的方式來處理 例︰ 倒過來存會比較好 8 3 5 6 No good! 4 3 2

91 串列的其他應用 Variable length string︰
固定長度的字串一般多用Array處理，但變動長度的字串則多用linked list 每一個節點可以存一個字元或多個字元 OS的process control block (PCB)是由linked list queue所組成 OS的動態memory management是由doubly linked list of variable size所組成 count …

92 第四章 堆疊(Stack)與佇列(Queue)

93 堆疊(Stack) 堆疊在觀念上就像是一疊盤子，資料的存取都只能由頂端來操作，具有後進先出的特性(Last In First Out; LIFO) 堆疊的相關運算︰ Push︰將新項目加在堆疊的頂端 Pop︰從堆疊頂端拿走一個項目 IsEmpty︰取資料時看堆疊是否為空集合，空則傳回TURE，不空則傳回FALSE IsFull ︰加資料時看堆疊是否已滿，滿則傳回TURE，不滿則傳回FALSE

94 利用陣列結構實作堆疊 #define MAX_ITEM 5 Typedef struct TagStack
{ char Item[MAX_ITEM]; /*資料欄位*/ int Top; //記錄目前頂端元素所在的位置 } STACK; STACK S; 當堆疊為空集合時，S.Top = -1 當堆疊已滿時，S.Top = MAX_ITEM - 1

95 利用陣列結構實作堆疊 int Push(STACK *S, int X)
{ if (IsFull(S)) return FALSE; //檢查堆疊是否已滿 S->top ++; //處理指標 S->item[S->top] = X; //加入新元素 return TRUE; } int IsFull(STACK *S) { if (S->top == (MAX_ITEM - 1) return TRUE; else return FALSE; } 例︰Push(&S, 5); Push(&S, 29); Push(&S, 35); Item [4] [3] [2] 35 [1] 29 [0] 5 Top = 2

96 利用陣列結構實作堆疊 int Pop(STACK *S, int *X)
{ if (IsEmpty(S)) return FALSE; //檢查堆疊是否為空 *X = S->item[S->top]; //取出元素 S->top --; //處理指標 return TRUE; } int IsEmpty(STACK *S) { if (S->top == -1) return TRUE; else return FALSE; } 例︰Pop(&S, &First); Pop(&S, &Second); Item [4] [3] [2] [1] [0] 5 Top = 0

97 利用鏈結串列結構實作堆疊 Typedef struct listnode { char data; /*資料欄位*/
struct listnode *next; //鏈結指標 } NODE; NODE *STop; 例︰Push(&S, 5); Push(&S, 29); Push(&S, 35); 堆疊串列的Push運算，相當於insert新節點於串列前端；而Pop運算相當於delete串列前端的節點 S (STop) 35 29 5

98 利用鏈結串列結構實作堆疊 int Push(NODE *S, int X) { NODE *p;
if ((p = (NODE *) malloc(sizeof(NODE)) == NULL) return FALSE; p->data = X; p->next = S; S = p; return TRUE; } 例︰int PushFlag; PushFlag = Push(&STop, 30); if (PushFlag) { …};

99 利用鏈結串列結構實作堆疊 int Pop(NODE *S, int *X) { NODE *p = S;
if ((p == NULL) return FALSE; *X = p->data; S = p->next; free(p); return TRUE; } 原先Stack的top必須要先儲存起來(p)，否則就無法做garbage collection 例︰int PopFlag, PopValue; PopFlag = Pop(&STop, &PopValue); if (PopFlag) { …};

100 堆疊的應用︰副程式的呼叫與返回 Call Return Call Return Call Return A B C D D C B A
STACK

101 堆疊的應用︰運算式的轉換及求值 算術運算式(arithmatic expression)是由運算元(operand)和運算子(operator)所組成 中序表示法(infix)︰運算子在運算元的中間，例如︰A+B。利用優先次序和括號來決定計算的順序 後序表示法(postfix)︰運算子在運算元的後面，例如︰AB+ 前序表示法(prefix)︰運算子在運算元的前面，例如︰+AB

102 中序轉換為後序(前序) 先將運算式加上所有的括號 (A+B)*C-D/E  (((A+B)*C)-(D/E))
將每個運算子移到它右(左)邊最接近而且未配對的右(左)括號之後(前) ( ( (A + B) * C) - (D / E) ) 去掉所有的括號 AB+C*DE/- -*+ABC/DE

103 中序轉換為後序︰堆疊的應用 遇到operand︰輸出到後序表示法 遇到左括號︰一律Push到Stack中
遇到右括號︰一直做Pop，直到遇到左括號為止。左右括號均丟棄不要 遇到operator︰(比堆疊大則push，小於等於堆疊則pop)與Stack頂端的運算子比較，如果優先次序比堆疊的STop大，則Push operator；如果小於等於就做Pop，一直Pop到遇到優先次序較小的運算子或是Stack變空為止，然後將operator Push到Stack中。左括號在Stack中優先次序最小 遇到 \0 鍵︰一直Pop到Stack變空為止

104 中序轉換為後序︰堆疊的應用 (A+B)*C-D/E 讀取 字元 運算子 堆疊 後序 表示法 ( C * AB+C A - AB+C* +
+( D AB+C*D B AB / /- ) AB+ E AB+C*DE \0 AB+C*DE/-

105 中序轉換為後序︰堆疊的應用 A-B/C+(D-E)*F 讀取 字元 運算子 堆疊 後序 表示法 A D (+ ABC/-D - -(+ B
*+ ABC/- F ABC/-DE-F ( \0 ABC/-DE-F*+

106 中序轉換為後序︰堆疊的應用 (4 + 8 - 5) * ( (2 + 4) / 3) 讀取 字元 運算子 堆疊 後序 表示法 ( ((*
4 2 + +( +((* 8 4 8 - -( 4 8 + ) (* 5 / /(* 3 * / \0 / *

107 運算符號的優先性與結合性 優先性愈高代表要愈先做 左結合代表在相同的優先權下，左邊要先做； 右結合代表在相同的優先權下，右邊要先做
例：8-4-3=1(左結合)、2^3^2=2^9=512(右結合) 優先性 運算子 結合性 7 ^(乘方), -(負號) 右結合 6 *, / 左結合 5 +, -(減號) 4 <, =, >, ≧, ≦, ≠ 3 ~(NOT) 2 &(AND) 1 |(OR)

108 中序轉換為後序︰堆疊的應用 A/B*C+B*D^E-A/C*F 讀取 字元 運算子 堆疊 後序 表示法 A ^ ^*+ AB/C*BD /
/- + AB/C* AB/C*BDE^*+AC AB/C*B *- AB/C*BDE^*+AC/ *+ F AB/C*BDE^*+AC/F D \0 AB/C*BDE^*+AC/F*-

109 中序轉換為後序︰堆疊的應用 #define MAX_OP 5
#define operator(c) (c==‘+’)||(c==‘-’)||(c==‘*’)|| (c==‘/’) ? 1 : 0 #define operand(c) ((c)>=’a’ && (c)<=’z’) ? 1 : 0 #define MAX_ITEM 100 Typedef struct TagStack { char Item[MAX_ITEM]; int Top; } STACK; STACK S; char op[MAX_OP] ={ ‘(’,‘+’,‘-’,‘*’,‘/’}; char prio[MAX_op] = {0,1,1,2,2};

110 中序轉換為後序︰堆疊的應用 void Push(int x) { if (S.top < MAX_ITEM - 1)
S.item[S.top] = x; }} int Pop(int *x) { if (S.top >= 0) { *x = S.item[S.top]; S->top --; }} int Priority(int c) /*查詢運算子的優先次序*/ { for (int i = 0; i < MAX_OP, i++) if (op[i] == c) return(prio[i]); return (-1); }

111 中序轉換為後序︰堆疊的應用 void in_to_post(char *infix, char *postfix)
{ int i, j, element; char token; S.top = -1; i = j = 0; //i, j分別代表中序與後序的註標 while ((token = infix[i]) != ‘\0’) { i = i + 1; if (operands(token)) postfix[j++] = token; //遇到運算元 else if (token == ‘(’) push(token); //遇到左括號

112 中序轉換為後序︰堆疊的應用 else if (token == ‘)’) //遇到右括號 while (S.top >= 0)
{ pop(&(int)element); if(element == ‘(’) break; postfix[j++] = element; } else if (operator(token)) //遇到運算子 { while (S.top >= 0) { element = S.item[S.top]; if (priority(token) <= priority(element)) { pop(&(int) element) else break; } push(token); } }

113 中序轉換為後序︰堆疊的應用 while (S.top >= 0) //運算元處理完畢，遇到\0 { pop(&element);
postfix[j++] = element; } postfix[j] =‘\0’; }

114 後序式求值法 遇到運算元︰一律Push到Stack中
遇到運算子︰Pop兩個運算元(op2, op1)，做對應的運算，然後將結果再存回到Stack中 遇到\0：堆疊中的值即為所求的結果 /*  ( ( (4 + 8) - 5) * ( (2 + 4) / 3) ) 讀取字元 運算元堆疊 4 8 8 4 + 6 7 12 3 3 6 7 5 5 12 / 2 7 - 7 * 14 2 4 4 2 7 \0

115 後序式求值法 A-B/C+(D-E)*F  ABC/-DE-F*+ 假設A=10, B=12, C=3, D=2, E=6, F=4
 / – 4 * + 讀取字元 運算元堆疊 4 4 -4 6 / 4 10 * -16 6 - 6 + -10 2 6 6 2 6 \0 -4 6

116 後序式求值法 假設A=20, B=5, C=4, D=2, E=4, F=3
A/B*C+B*D^E-A/C*F  AB/C*BDE^*+AC/F*- 假設A=20, B=5, C=4, D=2, E=4, F=3  20 5 / 4 * ^ * / 3 * – 讀取字元 運算元堆疊 20 5 5 20 + 96 / 4 20 4 4 4 5 96 * 16 3 3 5 96 5 2 4 15 96 ^ - 81 80 16 \0

117 後序式求值法 int post_evaluate(char *postfix)
{ int evaluate(), op1, op2, result, i = 0; char token; while ((token = postfix[i]) != ‘\0’) { i = i + 1; if (operands(token)) push(token-’0’);//文字變數值 else if (operator(token)) { Pop(&op2); Pop(&op1); result = evaluate(token, op1, op2); push(result); } } Pop(&result); return(result); }

118 後序式求值法 int evaluate(char optr, int op1, int op2) { int result;
switch(optr) { case ‘+’ : result = op1 + op2; break; case ‘-’ : result = op1 - op2; break; case ‘*’ : result = op1 * op2; break; case ‘/’ : result = op1 / op2; break; } return(result); }

119 遞迴(Recursion) fact(n) = n * fact(n-1) = n * (n-1) * fact(n-2) 
在解題時，如果呼叫的副程式就是自己，這種自己呼叫自己的現象，稱之為遞迴 遞迴程式中一定有一個讓程式結束的條件和讓問題逐漸變小的方式(遞迴)

120 遞迴︰階乘(factorial) int fact(int n) { if (n == 0) return (1); /*終止條件*/
return(n*fact(n-1)); /*遞迴呼叫*/ }

121 遞迴︰Fibonacci polynomial
Int Fib(int n) { if (n == 0) return (0); /*終止條件*/ if (n == 1) return (1); return(Fib(n-1) +Fib(n-2)); /*遞迴呼叫*/ }

122 遞迴︰Ackerman’s function
Int Ackerman(int m, int n) { if (m == 0) return (n+1); /*終止條件*/ if (n == 0) return (Ackerman(m-1,1)); return (Ackerman(m-1, Ackerman(m, n-1)); /*遞迴呼叫*/ }

123 遞迴︰Hanoi Towers 有A、B、C三個塔柱，A上插有n個大小不相 同的圓盤，由大到小依序向上排列。試問如 何將圓盤由A塔柱移到C塔柱？遊戲規則為︰ 一次只能移動一個圓盤 圓盤只能在三個塔柱之間移動 任何時間、任何塔柱上，直徑較大的圓盤都不能 壓在較小的圓盤上

124 遞迴︰Hanoi Towers 演算法︰ 將1 ~ n-1號圓盤由A搬 到B，以C作為緩衝區 將n號圓盤由A搬到C
將1 ~ n-1號圓盤由B搬 到C，以A作為緩衝區

125 遞迴︰Hanoi Towers 以n = 3為例 Hn-1 1

126 遞迴︰Hanoi Towers 將n個圓盤由A搬到C，以B作為緩衝區 將1~n-1號圓盤由A搬到B，以C作為緩衝區 將n號圓盤由A搬到C
將1~n-1號圓盤由B搬到C，以A作為緩衝區 void Hanoi(int n, char from, char by, char to) { if (n>0) { Hanoi(n-1, from, to, by); printf(“move no. %d disk from ‘%c’ to ‘%c’ \n”, n, from, to); Hanoi(n-1, by, from, to); } }

127 遞迴︰Hanoi Towers的時間複雜度
An = An An-1 = 2 * An-1 + 1 = 2 * (2 * An-2 + 1) + 1 = 22 * An = 22 * (2 * An-3 + 1) = 23 * An  = 2k * An-k + 2k-1 + 2k-2 + … = 2n-1*A1 + 2n-2 + 2n-3 + … /*k=n-1*/ = 2n-1 + 2n-2 + 2n-3 + … /* A1 = 1*/ = 2n - 1

128 如何在一個陣列中儲存兩個堆疊 int Push(int i, STACK *S, int X)
item [0] [1] [2] [m] … Stack 1 Stack 2 int Push(int i, STACK *S, int X) { if (i = 1) //i代表堆疊的編號 { S.top1 ++; if (S.top1 >= S.top2) return FALSE; //堆疊已滿 else S.item[S.top1] = X } else { S.top2 --; if (S.top2 <= S.top1) return FALSE;//堆疊已滿 else S.item[S.top2] = X } }

129 如何在一個陣列中儲存兩個堆疊 Int Pop(int i, STACK *S, int *X)
item [0] [1] [2] [m] … Stack 1 Stack 2 Int Pop(int i, STACK *S, int *X) { if (i = 1) //i代表堆疊的編號 { if (S.top1 = -1) return FALSE; //堆疊已空 else { *X = S.item[S.top1]; //取出元素 S.top1 --; //處理指標 } else { if (S.top2 = m+1) return FALSE; //堆疊已空 else { *X = S.item[S.top2]; //取出元素 S.top2 ++; //處理指標 } }

130 將一個鏈結串列之鏈結反轉 利用堆疊的概念來處理 一開始題目給定listA，而listB是空串列 listA只管pop (由串列前面刪除資料)
listB只管push (由串列前面加入資料) listA 淡 江 資 管 listB 管 資 江 淡

131 迴文 輸入一個字串然後反向輸出，利用堆疊的概念來處理 將字串“淡江資管”輸入到堆疊中(push)，直到遇到\0，代表輸入結束
然後開始做輸出的動作(pop)，直到堆疊變成空的為止

132 佇列(Queue) 佇列在觀念上就像是排隊買票的隊伍，新加入者從佇列的後端(rear)進入佇列，買完票者由佇列的前端(front)離開，具有先進先出(First In First Out; FIFO)的特性 佇列的相關運算︰ Enqueue︰將新項目加在佇列的後端 Dequeue︰從佇列的前端拿走一個項目 IsEmpty︰看佇列是否為空集合，空則傳回TURE，不空則傳回FALSE IsFull ︰看佇列是否已滿，滿則傳回TURE，不滿則傳回FALSE

133 利用陣列結構實作佇列 #define MAX_ITEM 5 Typedef struct TagQueue
{ char Item[MAX_ITEM]; /*資料欄位*/ int front, rear; /*記錄指標*/ } QUEUE; QUEUE q; front指向剛剛被delete掉的位置，rear指向剛剛才加入資料的位置 初始化時， q.front = q.rear = -1 當佇列為空集合時，q.front = q.rear

134 佇列(Queue) Enqueue(q, x)︰q.rear = q.rear +1 q(q.rear) = x
Dequeue(q, x)︰q.front = q.front + 1 x = q(q.front) 1 2 3 Enq(q, 2) Enq(q, 5) 5 Enq(q, 7) 7 Deq(q, x) 2 5 7 Enq(q, x) X=2 X=5

135 環狀佇列(Circular Queue) 時間一久，Queue可用的空間就越來越小，因為front和rear都跑到後面去了
為了提高空間的利用率，每一次Dequeue以後，就將Queue整個往前移(和人的排隊行為相同)，保持front永遠都在-1的位置  waste time for moving 將Queue視為是一個環狀的陣列 rear = (rear + 1) % MAX_ITEM //求餘數 front = (front + 1) % MAX_ITEM

136 如何分辨Queue是Full or Empty
.. 4 7 2 5 8 9 3 …  Deq(q, x) .. 4 7 2 5 8 6 3 … X=7 Empty  Enq(q, 6) Full 另外加一個計數器counter 每做一次Enq，counter = counter + 1 每做一次Deq，counter = counter – 1 if counter == 0  Empty == MAX_ITEM  Full

137 如何分辨Queue是Full or Empty
只允許Queue中最多儲存MAX_ITEM-1個元素，浪費一個空間，就可以分清楚Queue是Full or Empty Full︰ q.rear+1 == q.front Empty︰ q.rear == q.front 初始化︰q.front = q.rear = MAX_ITEM - 1 2 5 8 9 3 … 7

138 環狀佇列 int Enqueue(char x) { if ((q.rear + 1) % MAX_ITEM == q.front)
return (0); /*佇列已滿*/ q.rear = (q.rear + 1) % MAX_ITEM; q.item[q.rear] = x; return (1); } int Dequeue(char *xptr) { if (q.front == q.rear) return (0); //佇列已空 q.front = (q.front + 1) % MAX_ITEM; *xptr = q.item[q.front];

139 利用鏈結串列結構實作佇列 Typedef struct listnode { char data; /*資料欄位*/
struct listnode *next; } Queue; Queue *front, *rear; front與rear分別指到第一筆和最後一筆資料上 佇列串列的Enqueue運算，相當於insert新節點於串列後端(rear.next = newnode; rear = newnode)；而Dequeue運算相當於delete串列前端的節點(front = front.next) 67 35 29 5

140 利用鏈結串列結構實作佇列 front與rear的指標可否調換？
最好不要！雖然Enqueue的問題不大(newnode.next = rear; rear = newnode)，雖然Dequeue時，經由front也可以很容易刪除最後一筆資料(67)，但是要將front改為它的前一筆資料(35)的地址和將(35)的next要改成Null，就很麻煩，因為沒有很容易的辦法可以找到前一筆，只能從Rear一路找下來，很慢 5 29 35 67

141 佇列的應用 任何只要跟排隊、訂優先順序有關的應用都 可以由佇列來處理 CPU的job scheduling (FCFS)
Disk I/O scheduling (FCFS) 印表機的spooling (FCFS) Virtual memory的page replacement (FIFO) Graph或tree的廣先走訪(BFS)

142 佇列的應用(1) 例：假設Queue以鏈結串列來實現，此串列 被存放在記憶體內，如下表所示，其中X為 資料被插入或移出時所暫時存放的區域
Front：7，Rear：1，Avail (Free)：2，X：70 請從頭開始依序寫出佇列中的所有元素 解：2, 30, 43, 56, 18, 19, 38 位置 1 2 3 4 5 6 7 8 9 10 資料 38 70 19 56 79 18 66 30 43 鏈結 -1

143 佇列的應用(2) 在該佇列中插入一個99的值，試問上述的結 構有什麼改變？ 刪除一個元素後，上述的結構有什麼改變？
Front：7，Rear：2，Avail (Free)：5，X：99 刪除一個元素後，上述的結構有什麼改變？ Front：9，Rear：2，Avail (Free)：7，X：2 位置 1 2 3 4 5 6 7 8 9 10 資料 38 99 19 56 79 18 66 30 43 鏈結 -1 位置 1 2 3 4 5 6 7 8 9 10 資料 38 99 19 56 79 18 66 30 43 鏈結 -1

144 佇列的應用(3) 如果將上述這個鏈結串列視為是一般的串列 結構，也就是不把它視為是佇列，資料可以 由任何一個地方移去，但一定要在尾端插入， 則先移除18，移除30，再插入80後，試問上 述結構有什麼改變？ Front：10，Rear：9，Avail (Free)：6，X：80 回收的空間一般都加在Free list的前面 位置 1 2 3 4 5 6 7 8 9 10 資料 38 99 19 56 79 18 66 80 43 鏈結 -1

145 第五章 樹狀結構(Tree)

146 樹(Tree) 樹根(root) 子樹(subtree) 父節點(parent) 子節點(children) 內部節點(internal)
F G I H J 1 2 3 4 階層(LEVEL) 樹根(root) 子樹(subtree) 父節點(parent) 子節點(children) 內部節點(internal) 樹葉(leaf)、外部節點(external)、終端節點(terminal) 高度(height)：最高的階層數

147 由Linked-list到樹(Tree)
雖然在資料插入與刪除時，linked-list不需要像array一樣，需要做實質的資料搬移的動作 但是在資料搜尋時，只能做循序搜尋。運氣好時，只要找一次就找到，運氣不好，卻可能要找到最後一筆才找到，平均來說大約要搜尋(n+1)/2筆資料，才能找到你要的資料。因此在linked-list上搜尋的時間複雜度為O(n) Tree可以視為多個串列的組合，可以加快搜尋的速度O(log n)，改善了linked-list的缺點

148 樹的基本性質 如果一棵樹的總節點數為V，總邊數為E，則V = E + 1。證明如下︰
假設V = 1 ~ k時，Vk = Ek + 1都成立 當V = k + 1時，除了一個root以外，其餘的k個節點，假設構成m個子樹 1 k … Vi = Ei + 1 m

149 樹的基本性質 每一個子樹 Vi = Ei + 1  Vk = Vi = (Ei + 1) = Ei + m
Vk+1 = Vk + 1= Ei + m + 1= Ek+1 + 1 因此得證

150 二元樹的基本性質 如果一棵樹的內部節點最多只有兩個子節點，稱為二元樹 二元樹上第i階節點的數目最多為2i-1個，最少是1個
高度為k的二元樹總節點的數目 最多為2k-1個 最少為k個

151 二元樹的基本性質 完滿二元樹(full binary tree)︰所有的leaf都在同一階，而且每一個內部節點都有兩個son，高度為k的完滿二元樹總節點數為2k-1 正規二元樹(formal binary tree)︰所有內部節點都剛好有兩個子節點 完整二元樹(complete binary tree)︰除了最後一階以外，它是full binary tree，並且最後一階的節點都是往左補滿伍

152 二元樹的基本性質 正規二元樹的內部節點數比外部節點數少1。證明如下︰ V = E + 1 樹的基本性質
E = 2 * i 每個內部節點都有兩個edge V = i + t 節點總數等於內部節點加外 部節點 V = E + 1 = i + t  2 * i + 1 = i + t  t = i + 1

153 二元樹的基本性質 具有n個節點的完整二元樹，其高度為logn +1
高度為k的完整二元樹，節點數最多為2k - 1，最少為高度k-1的完滿二元樹再加上一個節點，即(2k-1-1) + 1 = 2k-1 0 < 2k-1  n  2k-1 < 2k 取對數  log(2k-1)  logn < log(2k) k - 1  logn < k logn = k - 1 k = logn +1

154 二元樹的基本性質 完整二元樹可以利用Array來儲存，而不需要利用pointer
父節點編號為i，則子節點的編號為2i + 1和2i + 2(如果子節點存在的話) 子節點編號為i，則父節點的編號為(i-1)/2 請注意︰節點的編號是由0開始編

155 二元樹的儲存方式︰一維陣列 A B C D E F G H A B C D F E G H A C F G B D E H A C G F
1 2 6 7 5 4 3 A C G F B D E H 1 2 6 14 13 8 3 1 2 3 4 5 6 7 A B C D E F G H 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D F E G H

156 二元樹的儲存方式︰一維陣列 適合用來儲存完整二元樹︰當二元樹趨近完整二元樹時，陣列空間浪費較少；如果不完整時，儲存空間浪費較多
陣列必須事先宣告陣列的大小。宣告太多、而使用太少則浪費記憶體空間，宣告太少又不夠使用。因此，在記憶體的使用上比較缺乏彈性 優點是簡單，從陣列註標就可以得知節點在二元樹中的位置

157 二元樹的儲存方式︰二維陣列 相當於以陣列來儲存串列資料 data L R [0] A 1 2 [1] B 3 4 -1 [2] C 5 6
[3] D 7 [4] E [5] F [6] G [7] H

158 二元樹的儲存方式︰二維陣列 適合用來儲存任何形式的二元樹︰不論樹長成什麼樣子，所佔用的空間都是一樣大的(只跟節點的數目有關)，沒有什麼浪費
雖然是Array-base，但是它免除了陣列在insert/delete方面的缺失 陣列需要事先預估，並宣告大小，事後擴充不易 需要浪費一點儲存指標的空間

159 二元樹的儲存方式︰動態配置 以鏈結和動態配置來儲存樹狀結構，不需要事先宣告樹的大小，可以隨需要而調整大小，在儲存空間的應用上比較有彈性
Typedef struct Tnode { struct Tnode *left; /*指向左子樹*/ char data; /*資料欄位*/ struct Tnode *right; /*指向右子樹*/ } NODE; left data right

160 二元樹的走訪︰前序走訪 先拜訪節點 再以前序拜訪左子樹 再以前序拜訪右子樹 void preorder(NODE *p)
{ if (p != NULL) { printf(“%c”,p->data); preorder(p->left); preorder(p->right); }}

161 二元樹的走訪︰中序走訪 先以中序拜訪左子樹 再拜訪節點 再以中序拜訪右子樹 void inorder(NODE *p)
{ if (p != NULL) { inorder(p->left); printf(“%c”,p->data); inorder(p->right); }}

162 二元樹的走訪︰後序走訪 先以後序拜訪左子樹 再以後序拜訪右子樹 再拜訪節點 void postorder(NODE *p)
{ if (p != NULL) { postorder(p->left); postorder(p->right); printf(“%c”,p->data); }}

163 二元樹的走訪 前序︰ABDJKECFHGI 中序︰JKDBEAHFCGI 後序︰KJDEBHFIGCA A C F G B D E J H

164 二元樹的走訪 前序︰ABDEFCHGI 中序︰DBFEAHCGI 後序︰DFEBHIGCA A C H G B D E F I

165 二元算式樹(Binary Expression Tree)
內部節點代表運算子，它的左右son分別代表運算元1和運算元2 數學式的優先次序可以用不同的tree level來表示，越低的層級代表要越先做 下圖哪一個代表A+B+C？都可以嗎？試試看ABC或AB+C！ + B C A + C A B

166 二元算式樹(Binary Expression Tree)
二元算式樹以前序、中序、後序的方式走訪後，就可以得到該數學式的前序、中序、後序式的結果 前序︰+-AE*B/CD 中序︰A-E+B*C/D 人們的習慣是寫成A-E+B*(C/D) 後序︰AE-BCD/*+ + * B / - A E C D

167 引線二元樹(Threaded Binary Tree)
在樹的走訪時，必須記住來的位置，以方便在樹中上上下下。因為它是遞迴式的處理，必須藉助額外的記憶體來當做堆疊之用，執行的效率並不高 n個節點的二元樹，一共有2n個pointer，但是二元樹只有n-1個邊，因此有n+1個指標是NULL，非常浪費 不如將NULL指標改為引線指標，左引線指向此節點的中序前行者，右引線指向此節點的中序後繼者

168 引線二元樹(Threaded Binary Tree)
J K C F G H I 為了處理的方便，增加一個假的根節點 它的左指標指向root，右指標指向自己 空樹時，左指標和右指標指向自己

169 引線二元樹(Threaded Binary Tree)
#define THREAD 0 #define POINTER 1 Typedef struct tagNode { char left_thread; struct tagNode *left; char data; char right_thread; struct tagNode *right; } tNODE; left_thread left data right_thread right

170 找尋中序立即後繼者 如果是右引線︰右引線所指到的節點就是後繼者
如果是右指標︰先往右走一步，再一路沿著左指標往左，一直到遇到左引線為止，該節點即為後繼者 tNODE *InorderSuccessor(tNODE *p) { if (p->right_thread == THREAD) p = p->right; else { p = p->right; while (p->left_thread == POINTER) p = p->left; } return (p); }

171 找尋中序立即前行者 如果是左引線︰左引線所指到的節點就是前行者
如果是左指標︰先往左走一步，再一路沿著右指標往右，一直到遇到右引線為止，該節點即為前行者 tNODE *InorderPredecessor(tNODE *p) { if (p->left_thread == THREAD) p = p->left; else { p = p->left; while (p->right_thread == POINTER) p = p->right; } return (p); }

172 建立引線二元樹 加入的新節點(p)是指標(r)所指到的節點的右兒子 p r 2 1 3 p r 

173 建立引線二元樹 加入的新節點(p)是指標(r)所指到的節點的左兒子 p 2 1 3 r p r 

174 建立引線二元樹 tNODE *r, *p p->left_thread = THREAD;
p->right_thread = THREAD; if (insert into right son) { p->left = r; /* 1 */ p->right = r->right; /* 2 */ r->right = p; /* 3 */ r->right_thread = POINTER; /* 3 */ } else { p->right = r; /* 1 */ p->left = r->left; /* 2 */ r->left = p; /* 3 */ r->left_thread = POINTER; /* 3 */}

175 二元搜尋樹(Binary Search Tree)
對於二元搜尋樹中每一個內部節點而言，它的左子樹的所有節點的資料值都比它小；右子樹的所有節點的資料值都比它大，有利於資料的搜尋工作 Left son < father Right son > father 中序走訪的結果， 恰好是由小到大的 排序順序 51 39 70 20 42 49 75 10 45 63 80

176 二元搜尋樹的建立 如果是空樹，則新節點為樹根 否則將新節點的資料與樹根的資料相比，小於樹根則往左子樹搜尋，大於樹根則往右子樹搜尋
重複步驟2，直到指標成為NULL為止 將新節點加在最後停留處

177 二元搜尋樹的建立 例︰加入51, 70, 39, 45, 63, 80, 20, 42, 75, 10, 49 51 39 70 51  70  51 70 39  51 51 39 70 45 63 51 39 70 45 45  63 

178 二元搜尋樹的建立 51 39 70 20 45 63 80 51 39 70 45 63 80 80  20  51 39 70 20 42 75 45 63 80 51 39 70 20 42 45 63 80 42  75 

179 二元搜尋樹的建立 10  49  51 39 70 20 42 75 10 45 63 80 51 39 70 20 42 49 75 10 45 63 80

180 二元搜尋樹的插入節點 tNODE *bst_insert(tNODE *t, tNODE *p) //t指向樹根，p指向新節點
{ tNODE *r, *q; char direction; if (t == NULL) //空樹；新節點是第一節點 { t = p; return (t); } q = t; //開始搜尋

181 二元搜尋樹的插入節點 while (q != NULL) //一直搜尋到空節點
{ if (p->data < q->data) //往左搜尋 { direction = 1; //記錄方向 r = q; //記錄父節點 q = q->left; } //往左走一步 else if (p->data > q->data) //往右搜尋 { direction = 0; //記錄方向 r = q; //記錄父節點 q = q->right; } //往右走一步 else return (t); } //資料已經存在 if (direction == 1) r->left = p; //判斷如何連結 else r->right = p; return (t); }

182 二元搜尋樹的插入節點 當q=NULL時，代表已經找到新節點應加入到的位置 指標r用來記錄指標q的父節點的位置，以便用來連接新節點
direction用來記錄新節點應該加到父節點的左邊(=1)還是右邊(=0) while最多執行樹的高度那麼多次

183 二元搜尋樹的建立 tNODE *bst_create(void) { FILE *filedata; int data;
tNODE *t, *p; filedata = fopen(“bst.dat”, “r”); // 開啟檔案 t = NULL; while (!feof(filedata)) //只要檔案還沒結束 { fscan(filedata,”%d”,&data); p = malloc(sizeof(tNODE)); //建立節點 p->data = data; p->left = p->right = NULL; t = bst_insert(t, p); } //插入到二元樹 return (t); }

184 二元搜尋樹的刪除節點 要刪除的節點(p)是樹葉︰只需要將parent的pointer設為NULL即可 例︰  r p 51 39 70
20 42 49 75 45 63 80 51 39 70 20 42 49 75 10 45 63 80 r p 

185 二元搜尋樹的刪除節點 要刪除的節點(p)只有一個兒子︰p的child變成p的father的child 例︰ r  p 51 39 70
42 49 75 45 63 80 r p 51 70 75 63 80 42 49 45 

186 二元搜尋樹的刪除節點 要刪除的節點(p)有兩個兒子︰將p左子樹中最右邊的兒子，提昇到p的位置
P的左子樹沒有右son︰ s->left = q->left r p 51 39 70 20 49 75 10 45 63 80 q s 51 20 70 10 49 75 45 63 80 

187 二元搜尋樹的刪除節點 P的左子樹有右son︰ s->right = q->left r p  s q 51 39 70 20
30 49 75 10 45 63 80 32 35 s 51 35 70 20 30 49 75 10 45 63 80 32

188 二元搜尋樹的刪除節點 tNODE *bst_delete(tNODE *t, int key)
{ int found = 0, direction = 0; tNODE *R, *q, *s, *t; r = q = s = NULL; p = t; while (p != NULL && !found) { if (key == p->data) found = 1; //搜尋成功 else if (key < p->data) //往左搜尋 { direction = 1; r = p; p = p->left; } else { direction = 0; //往右搜尋 p = p->right; } }

189 二元搜尋樹的刪除節點 if (p ==NULL) return (NULL); //找不到節點
if (r == NULL) //刪除root，而它只有一個兒子 { if (p->right ==NULL) return(p->left); else if (p->left ==NULL) return(p->right) } if (p->right ==NULL) //只有左son，或葉節點 { if (direction == 1) r->left = p->left; else r->right = p->left; } else if (p->left ==NULL) //只有右son { if (direction == 1) r->left = p->right; else r->right = p->right; } r p r p r p r p

190 二元搜尋樹的刪除節點 else //有兩個son，包括它可能是root { s = p; q == p->left; //往左子樹走
while (q->right != NULL) //找最右邊的son { s=q; q = q->right; } p->data = q->data; if (p == s) s->left = q->left;//左子樹沒有右son else s->right = q->left; } //左子樹有右son return (t); }

191 二元搜尋樹的建立 二元搜尋樹的形狀與資料輸入的順序直接相關，相同的資料、不同的輸入順序會造成不同的BST
例︰加入10, 20, 39, 42, 45, 49, 51, 63, 70, 75, 80以後，BST退化為linked list 42 45 49 51 63 70 75 80 10 20 39

192 高度平衡二元樹(AVL Tree) 二元搜尋樹的運算，其處理效率取決於樹的高度
具有n個節點的二元樹，其高度最大為n，最小為logn +1。如果二元樹愈趨近完滿，其高度愈小 在二元搜尋樹的插入與刪除時，我們並沒有考慮對於樹的高度的影響。因此，經過一段時的操作以後，二元樹的高度差可能越來越大，執行效率也會越來越差

193 高度平衡二元樹(AVL Tree) 為了使樹的高度趨於最小，使操作效率保持在O(logn)，在每次插入和刪除的動作以後，有可能需要對二元樹做一些高度的調整 AVL(Adelson-Velsky and Landis) tree︰在AVL樹上，所有內部節點的左子樹高度和右子樹高度的差值小於等於1 需要一個平衡係數來追蹤每一個節點是否處於高度平衡狀態 平衡係數=左子樹的高度-右子樹的高度 當某一個node的|平衡係數| = 2時，就表示tree不平衡了，需要調整

194 高度平衡二元樹(AVL Tree) 51 51 35 70 20 49 45 63 1 -1 51 35 70 80 -1

195 二元樹的平衡 51 35 70 90 63 80 -2 -1 70 51 80 35 63 90 -1 

196 二元樹的平衡(RR型)  中的左子樹 n 中的右子樹 n+1 小的左子樹 中的左子樹 n 中的右子樹 n+1 小的左子樹 -2 62 41
中的右子樹 n+1 小的左子樹 41 中的左子樹 n 62 -1 -2 中的右子樹 n+1 小的左子樹  < 41 41 ~ 62 > 62

197 二元樹的平衡 60 41 70 20 29 52 2 1 41 29 60 20 52 70 1 

198 二元樹的平衡(LL型)  中的右子樹 n 大的右子樹 中的左子樹n+1 中的右子樹 n 大的右子樹 中的左子樹n+1 2 62 70 1
大的右子樹 中的左子樹n+1 中的右子樹 n 70 62 1 2 大的右子樹 中的左子樹n+1  > 70 62 ~ 70 < 62

199 二元樹的平衡 51 35 70 20 90 75 45 63 80 72 -2 1 51 35 75 20 90 63 45 70 80 72 -1  以最低階的2為調整的基準

200 二元樹的平衡(RL型)  中的右子樹n+1 大的右子樹n+1 中的左子樹 n 小的左子樹n+1 中的右子樹n+1 大的右子樹n+1
41 70 62 -1 1 -2 大的右子樹n+1 中的左子樹 n 小的左子樹n+1 中的右子樹n+1 41 70 62 1 大的右子樹n+1 中的左子樹 n 小的左子樹n+1 < 41 > 70  41 ~ 62 62 ~ 70

201 二元樹的平衡 70 41 75 32 58 20 62 51 80 68 -1 1 2 62 41 70 32 80 20 51 68 75 58 -1 1 

202 二元樹的平衡(LR型)  中的右子樹n+1 大的右子樹n+1 中的左子樹 n 小的左子樹n+1 中的右子樹n+1 大的右子樹n+1
41 70 62 -1 2 大的右子樹n+1 中的左子樹 n 小的左子樹n+1 < 41 > 70 41 ~ 62 62 ~ 70 中的右子樹n+1 41 70 62 1 大的右子樹n+1 中的左子樹 n 小的左子樹n+1 

203 二元樹的平衡 例︰輸入Jan, Feb, Mar, …, Dec，建立AVL tree  Jan Aug Mar Apr Feb Jul
Jun May -1 2 Jan Aug Mar Apr Feb Jul Jun May 

204 二元樹的平衡   1 -2 Jan Aug Mar Apr Feb Jul Jun May Sep Oct -1 Apr Jan Aug

205 二元樹的平衡   -1 -2 Jan Aug Mar Apr Feb Jul Jun May Sep Oct Nov Mar Jan

206 二元樹的平衡 例︰輸入Jan, Feb, Mar, …, Dec，建立AVL tree  -1 Mar Jan Jul Jun Aug
Apr Feb May Sep Oct Nov Dec 1 

207 二元樹的平衡 例︰輸入20, 40, 60, 10, 15, 12, 11 20 40 60 -2 -1 40 20 60   40 20 60 15 10 2 -1 40 15 60 20 10  

208 40 15 60 12 20 10 2 1 -1 15 10 40 12 20 60    15 10 40 11 12 20 60 1 -2 15 11 40 10 12 20 60 

209 m元搜尋樹 每一個node可以儲存m-1個資料(鍵值)和m個鍵結，即每個節點最多可以有m個子樹
n表示鍵值的實際個數，其中K1<K2<…<Kn 做搜尋時，若K<K1 ，則往L0所指的子樹；若K1<K<K2 ，則往L1所指的子樹；… ；若K>Kn ，則往Ln所指的子樹 若K=Ki ，則搜尋成功，如果找到null則代表沒找到 n L0 K1 L1 K2 L2 … Ln-1 Kn Ln Km-1 Lm-1

210 m元搜尋樹 搜尋K=57 n L0 k1 L1 k2 L2 2 1 - 2 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1
30 60 搜尋K=57 1 15 - 2 38 59 - 1 72 - 1 - 10 1 - 51 1 35 - 1 - 70 1 - 32 1 57 - 1 - 55

211 為何m元搜尋樹會不平衡 m元搜尋樹雖然可以降低樹的高度，但是它一樣會碰到樹的不平衡的問題
當我們從root開始建一個tree時，比較前面輸入的key一定在比較接近root的地方，因此如果一開始就輸入了一些比較大或比較小的值，就很容易造成tree的不平衡 如何能將m-tree建成一個比較平衡的tree？ 如何能讓適當的key放在同一個node中？ 如何確保每一個node中都有適當數目的資料？

212 如何解決樹的不平衡問題 建tree時，不是由root開始比較，找新節點的插入位置；而是由leaf開始比較，找新節點的插入位置，讓internal node和root自然浮現，就可以很容易的解決上述的三個問題，建構出一個平衡樹 反向思考

213 Order-m的B Tree 每一個節點至多有m個子樹，也就是它最多有m-1個key
除了root以外，其餘的節點至少有m/2-1個key，也就是除了root和leaf以外，其餘的內部節點至少有m/2個子樹  (3) root至少有2個子樹，除非它也是leaf 所有的leaf都在同一階，也就是從root到任何一個leaf所經過的路徑都一樣長  (1) 每一個節點內的鍵值均由小到大排序  (2) 分裂、提昇(splitting, promoting)和合併、重分配(concatenation, redistribution)是B tree最主要的操作動作  (1)(2)(3)

214 分裂和提昇 例如︰order-8 B tree︰7 keys and 8 pointers
當我們再加入S時，一個node已經放不下了，於是平均分為兩半(splitting, (2, 3)) 為了要保持它仍然是一個tree，因此在上面加上一個root，將後一半的第一個key提升上去，變成root node的key(promoting (1)) A D F H M P T 排序好的資料 A D F H M P S T M A D F H P S T

215 分裂和提昇 插入C, S, D 插入T後，開始分裂和提升 插入A, M後，開始分裂 插入P, I, B, W，No Action
order-4 B tree 插入C, S, D 插入T後，開始分裂和提升 插入A, M後，開始分裂 插入P, I, B, W，No Action C D S S C D S T C D T D S A C D M A C M T D S A B C I M P T W

216 分裂和提昇 插入N後，開始分裂 插入G, U, R，No Action 插入K後，開始分裂和提升 I M N P D N S A B C I
W D N S A B C G I M P R T U W N D K N S D K S G I K M A B C G I M P R T U W

217 分裂和提昇 插入E, H後，開始分裂 插入O, L, J，No Action Always balanced N E G H I D H K
M P R T U W N D H K S A B C E G I J L M O P R T U W

218 分裂和提昇 插入Y, Q後，開始分裂 Always working up from the bottom(leaf)
Always balanced N D H K Q S W A B C L M O P Y E G I J R T U O P Q R T U W Y

219 合併和重分配 當我們刪除S時，node中的key值已經少於m/2-1個，於是需要重分配、甚至需要合併(2, 3)
重分配(redistribution)︰如果左、右兄弟有多於m/2-1個key值 合併(concatenation)︰如果左、右兄弟都只有m/2-1個key值 order-8 B tree H T A D F G M P S U V Z

220 合併和重分配 刪除J︰No Action leaf 刪除M︰先與後繼者交換，然後再刪除M We only delete leaf !
order-6 B tree leaf D H Q U A C E F I J K N O P R S V W X Y Z internal node M N We only delete leaf ! D H Q U A C E F I K M N O P R S V W X Y Z

221 合併和重分配 刪除Q︰重分配  N D H Q R U A C E F I K O P Q R S V W X Y Z S U V W X

222 合併和重分配 刪除A︰合併 合併後再合併  N D H R W A C E F I K O P S U V X Y Z N H N R W

223 合併和重分配 Always Balanced 降低樹的高度
如果在插入資料造成overflow時，不立即分裂節點(因為只產生兩個50%左右利用率的節點)，而是看看其sibling能否做重分配。這樣子可以增進節點的利用率(可提高至85%左右)，也間接達到減少B tree高度的目的 H N R W C D E F I K O P S U V X Y Z

224 B tree結構 typedef struct btnode { int n; //鍵值的實際個數
char data[m]; //第0個資料位置沒有用到 struct btnode *Link[m]; } bNODE; n data Link 1 … m-1

225 搜尋節點 bNODE *BtreeSearch(char key, bNODE *t, int *num)
{ int i; while (t != NULL) //只要不是空樹 { for (i = 0; i < t->n && key > t->data[i+1]; i++); if (key == t->data[i+1]) //找到了 { *num = i + 1; //傳回位置編號 return (t); } //傳回節點指標 t = t->Link[i]; } //往下一層搜尋 *num = 0; //找不到 return (NULL); }

226 刪除B tree節點 If the key to be deleted is not in a leaf, swap it with its immediate successor, which is a leaf. Delete the key. If the leaf now contains at least the minimum number of keys, no further action is required. If the leaf now contains one too few keys, look at the left and right siblings. If a sibling has more than the minimum number of keys(m/2-1), redistribute.

227 刪除B tree節點 If neither sibling has more than the minimum (m/2-1), concatenate the two leaves and the median key from the parent into one leaf. If leaves are concatenated, apply steps 3-4 to the parent. If the last key from the root is removed, then the height of the tree decreases.