--- # System prepended metadata title: 資料結構與演算法 習題解答 奇數題 --- # 資料結構與演算法 習題解答 奇數題 ## 第一章 基本概念 --- ### 1. 寫一個程序，將傳入的整數參數 x、y 和 z 由小到大印出。此程序的計算時間為多少？ :::spoiler 可利用 bubble sort 的概念： ```cpp= # include # include using namespace std; void print_nondecreasingly(int x, int y, int z) { int t; if (x > y) SWAP(x, y, t); if (y > z) SWAP(y, z, t); if (x > y) SWAP(x, y, t); cout << "sorted: " << x << " " << y << " " << z << endl << endl; } int main() { int x, y, z; while (cout << "x y z = ", scanf("%d %d %d",&x,&y,&z), x!=0) print_nondecreasingly(x, y, z); } ``` 時間複雜度為 *O*(1)。 /* ---- 執行結果: x y z = 34 12 9 sorted: 9 12 34 x y z = 23 45 28 sorted: 23 28 45 x y z = 9 2 7 sorted: 2 7 9 x y z = 0 9 11 ---- */ ![](https://i.imgur.com/FiBk7NR.png) ::: --- ### 3. 費氏 (Fibonacci) 數列被定義成：
  (1) $F_0 = 0, F_1 = 1;$
  (2) $F_n= F_{n−1} + F_{n−2},$ 當 $n≥2$。
寫出遞迴和迴圈版本（非遞迴）的程序來計算費氏數列（輸入 $n$，求 $F_1, F_2, … , F_n$）。 :::spoiler 遞迴版本: ```cpp= int F(int n) { int ans; if (n==0) return 0; if (n==1) return 1; return F(n-1)+F(n-2); } int main(void) { int n, i; while(cin >> n) { for (i=0; i<=n; i++) cout << F(i )<< " "; } } ``` /* ---- 執行結果: 3 0 1 1 2 5 0 1 1 2 3 5 10 0 1 1 2 3 5 8 13 21 34 55 15 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 20 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ---- */ ![](https://i.imgur.com/lZOxbmN.png) ::: :::spoiler 迴圈版本: ```cpp= int main() { int n, i; while (cin>>n) { int F[n+1] = {0}; F[1] = 1; for (i=2; i<=n; i++) F[i]=F[i-1]+F[i-2]; for (i=0; i<=n; i++) cout< $\qquad \quad A(m,n)=\begin{cases}\qquad \quad n+1 \qquad \qquad \quad \ \ \text{ if } \ \ m=0 \\\qquad A(m-1,1) \qquad \quad \ \ \ \text{ if } \ \ n=0 \\A(m-1,A(m,n-1)) \quad \text{ otherwise }\end{cases}$
這個函式在 $m$ 和 $n$ 的值還不是很大的時候，就已成長的非常快。寫一個遞迴程序和非遞迴程序計算它。 :::spoiler 遞迴版本: ```cpp= int Ackerman(int m,int n) { if (m==0) return n+1; else if (n==0) Ackerman(m-1,1); else Ackerman(m-1, Ackerman(m,n-1)); } int main(void) { int m, n; while(cin>>m>>n) { cout << "Answer = " << Ackerman(m,n); cout << endl << endl; } } ``` /* ---- 執行結果: 1 10 Answer = 12 3 10 Answer = 8189 2 15 Answer = 33 4 5 (等候逾時) ---- */ ![](https://i.imgur.com/Y6ofI0k.png) ::: ::: spoiler 迴圈版本： ```cpp= #include #include using namespace std; int ack_nonrecursive(int m, int n) { int value[500000]; int Size = 0; for (;;) { if (m == 0) { n++; if (Size-- == 0) break; m = value[Size]; continue; } if (n == 0) { m--; n = 1; continue; } int index = Size++; value[index] = m - 1; n--; } return n; } int main() { int m, n; cin>>m>>n; double START,END; for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) { cout<<"mi="< # include char a[10] = { "abcdefgh" }; char b[10]; int Bit[10]; int cnt = 0; int solCnt; void printSubset(int Bit [], int n) { int i, index = 0; for (i=0; i void charFrequency(char s[], int len) { int freq[26], i; char base = 'a'; for (i=0; i<26; i++) freq[i] = 0; for (i=0; i= (start+length) ) groot[k++]=text[i]; } // if ( text[i] == “\0”) return text; groot[k] = '\0'; return groot; } // 胡乃文、楊駘、史孟仟 提供 1036 ``` ::: --- ### 7. 假設有 $n$ 個串列，$n > 1$，它們用一維陣列 space[$m$] 來表示。令 front[$i$] 是指到第 $i$ 個串列第一個元素的前一個位置，rear[$i$] 是指到第 $i$ 個串列最後一個元素的位置，假設 rear[$i$] ≤ front[$i+1$]，$0 ≤ i < n$，且 front[$n$] = $m−1$，這些串列所能做的運算就是插入和刪除。
  (a) 找出 front[$i$] 和 rear[$i$] 的適當的起始和終止條件。
  (b) 寫一個程序 Insert(int i, int j, int item)，使其能在串列 $i$ 的第 ($j-1$) 個元素後面插入 item，這個程序在 space 已經有了 $m$ 個元素的情況下，不允許插入的動作。 :::spoiler (a) 起始條件：front[$i$] = rear[$i$] = $i * ⎣\frac{m}{n}⎦ -1$， $0 ≦ i＜n$ 且 front[$n$] = $m-1$。 刪除終止條件：只有當 front[$i$] = rear[$i$]成立時，第 $i$ 條字串會為空。 新增終止條件：只有當 rear[$i$] = front[$i+1$]成立時，第 $i$ 條字串已滿。 (b) ```cpp= int Insert(int i, int j, int item) { if ( rear[i] - front[i] < j-1) return 0; if (rear[i] == front[i+1]) //判斷第 i 條字串是否已滿 ListFull( ); if (rear[i] < front[i+1]) //space found { for (int k = rear[i]; k >= j; k--) space[k+1] = space[k]; space[j] = item; return 1; } else return 0; } ``` ::: --- ### 9. 當一個陣列的所有元素都排在其主對角線及其下方或上方，這個矩陣就叫做「三角矩陣」(triangular matrix)。圖 2-19 表示出「下三角」(lower triangular) 和「上三角」(upper triangular) 矩陣，其中非 0 元素標示為 X。
    ![](https://i.imgur.com/fXB6wr1.png)
將 $n×n$ 的下（上）三角矩陣存放在記憶體中，0 的值不存，請為陣列元素[$i$][$j$] 求出其位址公式，$0 ≤ i, j ≤ n−1$（每個元素佔 $l$ 個字元組，而 α 為陣列第一個非 0 元素（位於[0][0]）在記憶體中的位址）。 ::: spoiler (a) 下三角 以列為主： A[$i$][$j$]（$i ≥ j$） = $α + l[\frac{i(i+1)}{2} + j]$ 以行為主： A[$i$][$j$]（$i ≥ j$） = $α + l[\frac{(2n-j+1)j}{2} + (i −j)]$ ::: ::: spoiler (b) 上三角 以列為主：A[$i$][$j$]（$i ≤ j$） = $α + l[\frac{(2n-i+1)i}{2} + (j−i)]$ 以行為主：A[$i$][$j$]（$i ≤ j$） = $α + l[\frac{j(j+1)}{2} + i]$ ::: --- ### 11. 一個「三對角線矩陣」(tri-diagonal matrix) 為一個方陣，其中在主對角線及其相鄰的兩個對角線以外的元素均為 0 (如圖 2-20)。令 A 為一 $n×n$ 的三對角線矩陣，將 A 中三個對角線所形成帶狀區域上的元素，以列為優先，儲存在一個一維陣列 M 中（A[0][0] 存放在 M[0] 中）。設計一個計算公式，輸入 A[$i$][$j$] 時，可求得 $k$—A[$i$][$j$] 存在 M[$k$] 中，$0 ≤ i, j ≤ n−1$。                 ![](https://i.imgur.com/EzuLV82.png) :::spoiler $k = 2i+j$ (讀者可與以下表格比對。) | |0 |1 |2 |3 |4 |...| |:-:|:-:|:-:|:-:|:-:|:-:|:-:| |0 |0 |1 | | | | | |1 |2 |3 |4 | | | | |2 | |5 |6 |7 | | | |3 | | |8 |9 |10 | | |...| | | | | | | ::: --- ### 12. 一個「方形帶狀矩陣」(square band matrix) $D_{n,a}$ 是一個 $n×n$ 的矩陣，其中所有可能的非零元素，均集中在以主對角線為中心的帶狀區域上（此帶狀區域外的元素皆為 0）；此帶狀區域包括了主對角線與其上和其下各 a−1 條對角線（如圖 2-21 (a) 和 (b)，圖 2-21 (b) 是一 $D_{5,2}$ 的例子）。請回答：
  (a) 在此帶狀 $D_{n,a}$ 中有多少個元素？
  (b) 對於帶狀 $D_{n,a}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？
  ($\text{c}$) 假設帶狀 $D_{n,a}$ 以對角線為主，並從最低的對角線開始，循序儲存在陣列 A 中。例如，圖 2-21
  (b) 中的帶狀矩陣 $D_{5,2}$ 的表示法如下：
![](https://i.imgur.com/R1IPfO6.png)
找出在 $D_{n,a}$ 的下帶狀區域中的任一元素 $d_{ij}$ 的定址公式，即輸入 $i$ 和 $j$，求出 $k$，$d_{ij}$ = A[$k$]。
![](https://i.imgur.com/cIZcJgX.png)
![](https://i.imgur.com/tTiijFe.png) ::: spoiler 題12的解法為求解題13的重要基礎，特列於此 (a) 主對角線有 $n$ 個元素，以其為基準，上方的1, 2, ... , *a*-1 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-a+1$ 個元素，如下圖左； | ![](https://i.imgur.com/wkNsnYS.png) | ![](https://i.imgur.com/1EyicUD.png) | |----|----| 於其下方的 *a*-1 條對角線亦然。加總所有元素可得： $\begin{split} \quad &n+2\sum\limits_{t=1}^{n-a+1}{n-t}\\ &=n+2[(n-1)+(n-2)+...+(n-a+1)] \\ &=n+2\frac{(2n-a)(a-1)}{2} \\ &=n+(2n-a)(a-1) \\ &=n+(2na-a^2-2n+a) \\ &=2na-a^2-n+a \end{split}$ 上式亦可列為： $\begin{eqnarray} n+2\sum\limits_{t=n-a+1}^{n-1}{t} &=& n+2[(n-a+1)+(n-a+2)+...+(n-1)] \nonumber \\ ~&=& n+2\frac{(2n-a)(a-1)}{2} \nonumber \\ ~&=& n+(2n-a)(a-1) \end{eqnarray}$ (b) 請參考上圖右，令主對角線為 $D$： (b.1) 若 $i=j$，$A[i][j]$ 恰在 $D$ 上； (b.2) 若 $ij\ 且\ i-j = t，A[i][j]$ 在 $D$ 下方的第 $t$ 條對角線，$1 \leq t\leq a-1$。 總結以上討論：$|i - j| < a$。 (c\) 令 $k$ 為由最低對角線開始存放一維陣列中 $A[i][j]$ 的對應註標。如 (b) 所列： (c.1) 若 $i=j$，$A[i][j]$ 恰在 $D$ 上； 所有下帶狀元素先存，所以有 $n+2[(n-1)+(n-2)+...+(n-a+1) = \frac{(2n-a)(a-1)}{2}$ 個 存在 $D$ 元素之前；而且在 $A[i][j]=A[i][i]$ 之前，還有 $i$ 個 $D$ 中元素，所以 $k = i+\frac{(2n-a)(a-1)}{2}$。 (c.2) 先考慮 (b.3) 的情況：若 $i>j\ 且\ i-j = t$，$A[i][j]$ 在 $D$ 下方的第 $t$ 條對角線，$1 \leq t\leq a-1$。 此 $D$ 下方的第 $t$ 條對角線，元素有 $n-t$ 個且其起點的列註標即為 $t$，再往下共有註標為 $t+1,\ t+2,\ ...\,\ a-1$ 的$a-t-1$條對角線，元素分別為 $n-t-1,\ n-t-2,\ ...\,\ n-a+1$，所有下帶狀元素先存，所以元素有 $\quad (n-t-1)+(n-t-2)+\ ...\ +(n-a+1) \\ =\frac{(n-a+1+(n-t-1))(a-t-1)}{2} =\frac{(2n-a-t)(a-t-1)}{2}$ 在 $D$ 下第 $t$ 條對角線的 $A[i][j]$ 之前的元素，其列註標起點分別位於 $t,\ t+1,\ ...\,\ i-1$，計有 $(i-1)-t+1 = i-t = i-(i-j) = j$ 個(或直接想：不管那條下帶狀的對角線，行 $j$ 之前必有 $j$ 個元素)。於是 $A[i][j]$ 之前的元素總個數為： $\quad k = j+\frac{(2n-a-t)(a-t-1)}{2}$。 (c.3) 若 $i   (a) 在此帶狀 $D_{n,a,b}$ 中有多少個元素？
  (b) 對於帶狀 $D_{n,a,b}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？
  ($\text{c}$) 找出此帶狀 $D_{n,a,b}$ 在一維陣列 $B$ 中的循序表示法。對此表示法，設計一個函數 $address(n, a, b, i, j, B)$，根據傳入的參數 $n, a, b, i, j, B$，來決定在陣列 B 中，矩陣 $D_{n,a,b}$ 中的 $d_{ij}$ 值。
              ![](https://i.imgur.com/cgQnzpI.png) ::: spoiler (a) (by S. J.) $\sum\limits_{i=0}^{a-1}{(b+i)}+\sum\limits_{i=a}^{n-b-1}{(a+b-1)}+\sum\limits_{i=n-b}^{n-1}{[(a+b-1)-(n-b-i)]}$ $=ab+ \frac{a(a-1)}{2}+(n-a-b)(a+b-1)+ab+\frac{b(b-1)}{2}$ $(=n(a+b-1)-\frac{a(a-1)+b(b-1)}{2})$ ![](https://i.imgur.com/O1fXEHK.jpg) 例子：$a=3,\ b=2,\ n=8$ 代入上式可得元素個數共 28 個 (見下圖右下) ![](https://i.imgur.com/TxABLQo.png) 亦可用對角線優先的觀點來想： 主對角線 $D$ 共 $n$ 個元素；其下帶狀 $a-1$ 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-a+1$ 個元素；其上帶狀共 $b-1$ 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-b+1$ 個元素；總共有 $\begin{aligned} \quad &n+\sum\limits_{k=n-a+1}^{n-1}{k}+\sum\limits_{k=n-b+1}^{n-1}{k} \\ &= n+[(n-a+1)+(n-a+2)+...+(n-1)]+[(n-b+1)+(n-b+2)+...+(n-1)] \\ &= n+\frac{(a-1)(2n-a)}{2}+\frac{(b-1)(2n-b)}{2} \\ &=\frac {2n+2na-2n-a^2+a+2nb-2n-b^2+b}{2} \\ &=n(a+b-1)-\frac{a(a-1)+b(b-1)}{2} \end{aligned}$ (b) 若 $d_{ij}$ (b.1) 在主對角線 $D$ 上，$i=j$； (b.2) 在下帶狀區域內，則 $(i-j)\le a-1$； (b.3) 在上帶狀區域內，則 $(j-i)\le b-1$；$|i - j| < \text{max}(a, b)$ 不在 (b.1)-(b.3) 範圍內的 $i, j$ 其 $d_{ij}$ = 0。 ($\text{c}$) 若以最低對角線開始存放元素(如題12)，則 $address(n, a, b, i, j, B)$ 可以下式設計，回傳位址：$\&B[k]\ (=B+k (= \alpha+k\times l))$，其中 $k=\begin{cases} i+\frac{(a-1)(2n-a)}{2}, \ \text{if} \quad i-j=0 \\ j-a+\frac{(a-1-s)(2n-a-s)}{2-1}, \ \text{if} \quad i-j =s, \text{and} \quad s             ![](https://i.imgur.com/awFSI5T.png) :::spoiler 數量可藉由離散數學中介紹的 Catalan 數列求一般解 當 n = 3 時   可能的排列有 5 種：123，132，213，231，321   不可能的排列有 1 種：312 當 n = 4 時   可能的排列有 14 種：1234，1243，1324，1342，1432，2134，2143，2314，2341， 2431，3421，3241，3214，4321   不可能的排列有10 種：1423，2413，3124，3142，3412，4123，4132，4213，4231，4312 註：Catalan Number $C_n = {2n\choose {n}}-{2n\choose {n+1}}$, or $C_n =\frac {1}{n+1}{2n \choose {n}}$ ::: --- ### 3. 一個「雙端佇列」（double-ended queue，也稱 deque）是一個線性串列，它可以在佇列任一端加入或刪除元素。設計一個表示法，使用一維陣列來表示雙端佇列，再寫出從任一端加入或刪除雙向佇列的演算法。 :::spoiler ```cpp= # include # include #define MAXSIZE 10 using namespace std; int queue[MAXSIZE]; int head = -1, tail = -1; void Insert(int v) { if(tail == MAXSIZE) cout << "overflow" << endl; else { if(head == -1 && tail == -1) { head = 0; tail = 0; } else tail++; queue[tail] = v; } } void f_Insert(int v) { if(tail == MAXSIZE) cout << "overflow" << endl; else { if(head == -1 && tail == -1) { head = 0; tail = 0; } else tail++; for(int i = tail; i>0; i--) { queue[i] = queue[i-1]; } queue[head] = v; } } int Pop() { if(head == -1 || head > tail) { cout << "No element" << endl; return -1; } else { int v = queue[head]; head++; if(head > tail) { head = -1; tail = -1; } return v; } } int b_Pop() { if(head == -1 || head > tail) { cout << "No element" << endl; return -1; } else { int v = queue[tail]; tail--; if(head > tail) { head = -1; tail = -1; } return v; } } void Display() { for(int i = head; i <= tail; i++) { cout << queue[i] << " "; } cout<>s) { if(s=="p")Pop(); if(s=="q")b_Pop(); if(s=="i") { cout<<"n :"; cin>>v; Insert(v); } if(s=="j") { cout<<"n :"; cin>>v; f_Insert(v); } if(head != -1)Display(); } } ``` ::: --- ### 5. 一個 m×p 的迷宮，全部有可能的路徑中，最長的長度為多少？ :::spoiler 路徑最長的長度(即為最差的情況)：$\text{max}( \frac{m}{2}×(p+1),\ + \frac{p}{2}×(m+1))$ ::: --- ### 7. 寫出下列式子的後置式：
  (a) A×B×C
  (b) -A+B-C+D
  ($\text{c}$) A×-B+C
  (d) (A+B)×D+E/(F+A×D)+C
  (e) A&&B\||C\||!(E>F)
  (f) !(A&&!((BD)))\||(C   (g) A and B or C or not (E>F)
  (h) (A+B)*C^(D+E*F-G*(H+J)) :::spoiler (a) AB ×C × (b) A − B + C − D + ($\text{c}$) AB − ×C + (d) AB + D× EFAD× + /+ C + (e) AB &&C \|| EF >!\|| (f) ABC < CD >\||!&&!CE <|| (g) ABandCorEF > notor (h) AB+CDEF*+GHJ+*-^* ::: --- ### 9. 另外一種容易計算且不必加括號式子的表示法就是前序表示，這種表示法就是將運算子放在運算元的前面，請見範例 3-13：
  (a) 將習題 6 表示成對應的前序表示。
  (b) 寫一個演算法來計算前置表示法 e。
  ($\text{c}$) 寫一個演算法把中置式 e 轉成相等的前置式，假設每個 e 都以符號 "#"做開頭，且其前置式的也要以 "#" 做開頭。
你的演算法 (b) 和 ($\text{c}$) 的複雜度為多少？每個演算法需要多少空間？ :::spoiler (a) − − +12 /× /× 34567 / 89 (b) ```cpp= # include # include # include using namespace std; int top=0; int opndstk[100000]; int opndstk_pop() { if (top==-1) cout<<"empty stack."<>s; reverse(s.begin(), s.end()); int ans=0; int opnd1, opnd2; while (++i " << front; cout << endl << "Items -> "; for (i = front; i != rear; i = (i + 1) % SIZE)cout << Cqueue[i]; cout << Cqueue[i]; cout << endl << "Rear -> " << rear <\n"); cin >> select;//讀入選項 switch ( select ) { case 1: printf("input value(%d,%d) ==> ",front,rear); cin >> temp; Add(temp); display(); break; case 2: if (isEmpty()) cout << "No Data" << endl ; else { temp = Delete(); cout << "Queue Pop :" << temp << endl; } cout << "front -> " << front << endl; cout << "Rear -> " << rear << endl; break; case 3: if (isEmpty()) cout << "No Data" << endl ; else { temp = Spop(); cout << "Stack Pop :" << temp << endl; } cout << "front -> " << front << endl; cout << "Rear -> " << rear << endl; break; case 4: loop = 0; break; } } system("PAUSE"); return 0; } ``` ![](https://i.imgur.com/geczlSX.png) ::: --- --- ## 第四章 鏈結串列 --- ### 1. 設計一個演算法來計算一個由 first 指標指向開頭節點的單向鏈結串列所含的節點總數目，串列中最後一個節點的 link 欄為 NULL。計算此演算法的時間複雜度。 :::spoiler ```cpp= while (first!=null) { first = first->next; counter++; } ``` ```cpp= int CountNodes(struct node * first) { int cnt; for (cnt=0, p=first; p; cnt++, p=p->next); return cnt; } ``` 時間複雜度：*O*($n$)，其中 $n$ 為串列節點個數。 ::: --- ### 3. 設計三個演算法分分別來計算：
  (a) 由 first 指標指向開頭節點的雙向鏈結串；
  (b) 由 first 指標指向開頭空節點的雙向鏈結串；
  ($\text{c}$) 由 p 指標指向其中一節點的雙向鏈結串；所含的非空節點總數目，串列中最後一個節點的 link 欄為 NULL。分析此三個演算法的時間複雜度。 :::spoiler (a) ```cpp= count = 0; while(first != NULL) { first = first->next; count++; } for (cnt=0, p=first; p; cnt++, p=p->link); ``` *O*($n$) (b) ```cpp= count = 0; while(first != NULL) { first = first->next; count++; } count--; int CountNodesHead(struct node * first) { int cnt; for (cnt=0, p=first->link; p; cnt++, p=p->link); return cnt; } ``` *O*($n$) (c\) ```cpp= count = 0; if(p != NULL) { q = p->pre; while(p != NULL) { p = p->next; count++; } while(q != NULL) { q = q->pre; count++; } } for (cnt=1, a=p->link; a; cnt++, a=a->link); for (b=p->prev; b; cnt++, b=b->prev); ``` 時間複雜度：*O*($n$) ::: --- ### 5. 令兩個鏈結串列分別為：$x = (x_1, x_2, ..., x_n)$ 與 $y = (y_1, y_2, ..., y_m)$，其穿插合併串列 z 定義成：若 m ≤ n 則 $z = (x_1, y_1, x_2, y_2, ..., x_m, y_m, x_{m+1}, x_{m+2}, ..., x_n)$ ，若 $m > n$ 則 $z = (x_1, y_1, x_2, y_2, ..., x_n, y_n, y_{n+1}, x_{n+2}, ..., y_m)$；而合併後，$x$ 與 $y$ 其原先每一節點現在都存於 $z $中，所以 $x$ 與 $y$ 將變為空串列。請設計演算法求得 $x$ 與 $y$ 的穿插合併串列 $z$；且合併過程中不能使用其他節點。請分別考慮：
  (a) 單向鏈結串列（含或不含開頭空節點）；
  (b) 單向環狀鏈結串列；
  ($\text{c}$) 雙向環狀鏈結串列；並計算演算法的時間複雜度。 :::spoiler 令節點結構如下： ```cpp= struct node { int data; struct node * next; }; ``` 或 ```cpp= struct Dnode { struct Dnode * prev; int data; struct Dnode * next; }; struct node *first_x, *first_y, *first_z; // 前兩者分別指向串列 X, Y，而後者為空指標/開頭空白節點；或 struct Dnode *first_x, *first_y, *first_z; ``` (a) Singly linked list ```cpp= //不含開頭空節點 struct node * MergeList(struct node *first_x, struct node *first_y) { struct node *a, *b, *first_z, *last; // cnt_x = CountNodes(first_x); // CountNodes() 請參考習題 1 // cnt_y = CountNodes(first_y); if (!first_x) return first_z = first_y; if (!first_y) return first_z = first_x; first_z = first_x; a = first_z->next; first_z->next = first_y; b = first_y->next; first_z->next = b; for (last=first_z->next; a && b; ) { last->next = a; a = a->next; last->next->next = b; b = b->next; last = b; } last->next = (a) ? a : b; first_x = first_y = NULL; return first_z; } ``` ```cpp= // 含開頭空節點 struct node * MergeListHead(struct node *first_x, struct node *first_y, struct node *first_z) // Note: *first_z has been created in main() { struct node *a, *b, *last; if (!first_x->next) return first_z = first_y; if (!first_y->next) return first_z = first_x; for (a=first_x->next, b=first_y->next, last=first_z; a && b; ) { last->next = a; a = a->next; last->next->next = b; b = b->next; last = b; } last->next = (a) ? a : b; first_x->next = first_y = NULL; return first_z; } ``` 時間複雜度：*O*($m+n$) (b) Singly cyclic linked list ```cpp= //不含開頭空節點 struct node * MergeList(struct node *first_x, struct node *first_y) { struct node *a, *b, *p, *first_z, *last; if (!first_x) return first_z = first_y; // if X is empty if (!first_y) return first_z = first_x; // if Y is empty first_z = first_x; a = first_x->next; first_z->next = first_y; b = first_y->next; for (last=first_z->next; a!=first_x && b!=first_y; ) { last->next = a; a = a->next; last->next->next = b; b = b->next; last = b; } last->next = (a) ? a : b; for (p=last->next; p->next!=first_x && p->next!=first_y; p=p->next); p->next = first_z; first_x = first_y = NULL; return first_z; } ``` ```cpp= // 含開頭空節點 struct node * MergeListHead(struct node *first_x, struct node *first_y, struct node *first_z) // Note: *first_z has been created in main() { struct node *a, *b, *first_z, *last; if (first_x->next==first_x) return first_z = first_y; if (first_y->next==first_y) return first_z = first_x; for (a=first_x->next, b=first_y->next, last=first_z; a && b; ) { last->next = a; a = a->next; last->next->next = b; b = b->next; last = b; } last->next = (a) ? a : b; for (p=last->next; !p->next!=first_x && p->next!=first_y; p=p->next); p->next = first_z first_x->next = first_x; first_y->next = first_y; return first_z; } ``` 時間複雜度：*O*($m+n$) (c) Doubly cyclic linked list ```cpp= //不含開頭空節點 struct Dnode * MergeList(struct Dnode *first_x, struct Dnode *first_y) { struct Dnode *a, *b, *p, *first_z, *last; if (!first_x) return first_z = first_y; // if X is empty if (!first_y) return first_z = first_x; // if Y is empty first_z = first_x; a = first_x->next; first_z->next = first_y; b = first_y->next; first_z->next->prev = first_z; for (last=first_z->next; a!=first_x && b!=first_y; ) { last->next = a; a->prev = last; //last->next->prev = last; a->next = b; b->prev = a; //last->next->prev = last->next; a = a->next; b = b->next; last = b; } last->next = (a) ? a : b; for (p=last->next; p->next!=first_x && p->next!=first_y; p=p->next); p->next = first_z; first_z->prev = p; first_x = first_y = NULL; return first_z; } ``` ```cpp= // 含開頭空節點 struct Dnode * MergeListHead(struct Dnode *first_x, struct Dnode *first_y, struct Dnode *first_z) // Note: *first_z has been created in main() { struct Dnode *a, *b, *first_z, *last; if (first_x->next==first_x) return first_z = first_y; if (first_y->next==first_y) return first_z = first_x; for (a=first_x->next, b=first_y->next, last=first_z; a && b; ) { last->next = a; a->prev = last; a->next = b; b->prev = a; a = a->next; b = b->next; last = b; } last->next = (a) ? a : b; for (p=last->next; !p->next!=first_x && p->next!=first_y; p=p->next); p->next = first_z; first_z->prev = p; first_x->prev = first_x->next = first_x; first_y->prev = first_y->next = first_y return first_z; } ``` 時間複雜度：*O*($m+n$) ::: --- ### 7. 令 p 為指向環形鏈結串列的一指標，如何將此串列當作一佇列使用？（亦即寫出其新增與刪除元素的程序）。 :::spoiler ```cpp= struct node { int data; struct node *next; };//使 p 指向環狀串列任一個當開頭，令 q 指向 p 的前一個當環狀串列的結尾 struct node * p,*q; q = p->next; while(q->next != p) q = q->next; int delete()//delete：將p 指到下一個即可刪除原本 p 所指的元素 { r = p; p = p->next; return r->data; } void add( v ) //add：加到 q 後面 { struct node *s; s->data = v; s->next = NULL; q->next = s; q = q->next; } ``` ::: --- ### 9. 令 A 和 B 皆為多項式，
  $A(x) = \sum\limits_{i=0}^{n}{a_ix^i}, B(x) = \sum\limits_{i=0}^{n}{b_ix^i}$
多項式相加的定義為：
  $A(x) + B(x) = \sum\limits_{i=0}^{n}{(a_i+b_i)x^i}$
請參考 3.6.1 節用鏈結串列表示多項式，設計出輸入多項式的程序，並與程式 4-17（多項式相加的程序）搭配，實作兩輸入多項式的相加，並輸出其結果。請分析並驗証使用演算法的時間與空間複雜度。
提示：可將節點設計成可儲存：非 0 係數 $c_i$、其對應冪次 $i$ 與下一非 0 項指標的節點。注意在多項式的 $n$ 很大而非 0 項數很少時，鏈結串列的表示可節省空間。 :::spoiler 繼第8題 ```cpp= //Polynomial addition Term Add(Term a, Term b) //a and b are descending polynomial { Term result = NewTerm(-1, -1), term = result; a = a->next; b = b->next; //Skip blank nodes while (a && b) //If a and b are not empty, enter the loop { if (a->pow > b->pow) { term->next = NewTerm(a->coef, a->pow); a = a->next; term = term->next; } else if (a->pow < b->pow) { term->next = NewTerm(b->coef, b->pow); b = b->next; term = term->next; } else { if (a->coef - b->coef) term = term->next = NewTerm(a->coef + b->coef, a->pow); a = a->next; b = b->next; } } for (a = a ? a : b; a; a = a->next, term = term->next) term->next = NewTerm(a->coef, a->pow); return result; } ``` /* --- 執行結果 5 5 6 1 7 3 3 5 6 3 Ans : 8x^5 + 13x^3 + 6x^1 1 2 3 7 6 6 5 2 5 3 Ans : 3x^7 + 6x^6 + 5x^3 + 6x^2 57 6 7 3 32 5 -12 1 33 5 -12 3 -8 0 Ans : 57x^6 + 65x^5 - 5x^3 - 12x^1 - 8 --- */ ![](https://i.imgur.com/03PVoNp.png) 時間複雜度：*O*($n+m$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。 ::: --- ### 11. 仿照 8、9 和 10 的題意，設計出多項式相減和相除的演算法。請分析所用演算法的時間與空間複雜度。 :::spoiler ```cpp= //Polynomial subtraction Term Sub(Term a, Term b) //a and b are descending polynomial { Term result = NewTerm(-1, -1), term = result; a = a->next; b = b->next; //Skip blank nodes while (a && b) //If a and b are not empty, enter the loop { if (a->pow > b->pow) { term->next = NewTerm(a->coef, a->pow); a = a->next; term = term->next; } else if (a->pow < b->pow) { term->next = NewTerm(-b->coef, b->pow); b = b->next; term = term->next; } else { if (a->coef - b->coef) term = term->next = NewTerm(a->coef - b->coef, a->pow); a = a->next; b = b->next; } } int pn = a ? 1 :-1; for (a = a ? a : b; a; a = a->next, term = term->next) term->next = NewTerm(a->coef * pn, a->pow); return result; } ``` /* --- 執行結果 5 5 6 1 7 3 3 5 6 3 Ans : 2x^5 + 1x^3 + 6x^1 1 2 3 7 6 6 5 2 5 3 Ans : 3x^7 + 6x^6 - 5x^3 - 4x^2 57 6 7 3 32 5 -12 1 33 5 -12 3 -8 0 Ans : 57x^6 - 1x^5 + 19x^3 - 12x^1 + 8 --- */ ![](https://i.imgur.com/G3vXPNQ.png) 時間複雜度：*O*($n+m$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。 ```cpp= //Polynomial division #include //#include //CodeBlock會跟內建函式衝到 #define swap(type, a, b) { type t = a; a = b, b = t; } typedef struct Fraction //Fraction { int num, den; //Numerator and Denominator } Frac; typedef struct NodeOfPolynomial { struct Fraction coef; //Coefficient int pow; //Power struct NodeOfPolynomial *next; //Next term } *Term; // Functions of Fraction inline Frac Red(struct Fraction frac) //Reduction of fraction { int a = abs(frac.num), b = abs(frac.den), c; while (b) c = b, b = a%b, a = c; //GCD return (Frac){frac.num / a, frac.den / a}; } inline struct Fraction add(Frac a, Frac b) //Addition { return Red((Frac){a.num*b.den+b.num*a.den, a.den*b.den}); } inline struct Fraction sub(Frac a, Frac b) //Subtraction { return Red((Frac){a.num*b.den-b.num*a.den, a.den*b.den}); } inline struct Fraction mul(Frac a, Frac b) //Multiplication { return Red((struct Fraction){a.num*b.num, a.den*b.den}); } inline struct Fraction div(Frac a, Frac b) //Division { return Red((struct Fraction){a.num*b.den, b.num*a.den}); } inline void output(struct Fraction frac) { if (frac.den == 1) printf("%d", abs(frac.num)); else printf("(%d/%d)", abs(frac.num), frac.den); } // Functions of Polynomial Term NewTerm(struct Fraction ceof, int pow) { Term term = (Term)malloc(sizeof(struct NodeOfPolynomial)); term->coef = ceof; term->pow = pow; term->next = NULL; return term; } void Sub(Term A, Term B) //Polynomial subtraction { Term pre = A, a = A->next, b = B->next, next; free(B); while (a && b) //If a and b are not empty, enter the loop { if (a->pow > b->pow) { pre = a; a = a->next; } else if (a->pow < b->pow) { b->coef.num = -b->coef.num; pre->next = b; pre = b; next = b->next; b->next = a; b = next; } else { a->coef = sub(a->coef, b->coef); if (a->coef.num) pre = a = a->next; else pre->next = a->next, free(a), a = pre->next; next = b->next; free(b); b = next; } } if (b) pre->next = b; } Term *Div(Term a, Term b) //Polynomial division { Term result = NewTerm((struct Fraction){-1, 1}, -1), t, term = result, tmp = NewTerm((Frac){-1, 1}, -1); for (a=a->next, t=tmp; a; a=a->next, t=t->next) t->next = NewTerm(a->coef, a->pow); a = tmp; while (a->next->pow >= b->next->pow) { Term mcl = NewTerm((Frac){-1, 1}, -1), m = mcl; term = term->next = NewTerm(div(a->next->coef, b->next->coef), a->next->pow - b->next->pow); for (Term bi = b->next; bi; bi = bi->next, m = m->next) m->next = NewTerm(mul(bi->coef, term->coef), bi->pow+term->pow); Sub(a, mcl); } Term *ans = (Term *)malloc(sizeof(Term)*2); ans[0] = result; //Quotient ans[1] = a; //Remainder return ans; } inline void Clear(Term pol) { for (Term next; pol; next = pol->next, free(pol), pol = next); } void Output(Term polynomial) { int i = 0; for (Term term = polynomial->next; term; term = term->next, ++i) { printf(term->coef.num > 0 ? " + "+(!i<<1) : " - "); output(term->coef); if (term->pow) printf("x^%d", term->pow); } puts(""); } void Sort(int *cbegin, int *cend, int *pbegin, int *pend) //Quick Sort { if (pbegin < pend-1) { int split = *pbegin, *i = pbegin, *ci = cbegin; for (int *j = pbegin+1, *cj = cbegin+1; j != pend; ++j, ++cj) { if (*j > split) { ++i; ++ci; swap(int, *i, *j); swap(int, *ci, *cj); } } swap(int, *i, *pbegin); swap(int, *ci, *cbegin); Sort(cbegin, ci, pbegin, i); Sort(ci + 1, cend, i + 1, pend); } } int main() { int coefs1[100], pows1[100], size1 = 1; int coefs2[100], pows2[100], size2 = 1; //Input coefficients and powers for (int *coef = coefs1, *pow = pows1; scanf("%d %d", coef, pow) != EOF && getchar() != '\n'; ++coef, ++pow, ++size1); for (int *coef = coefs2, *pow = pows2; scanf("%d %d", coef, pow) != EOF && getchar() != '\n'; ++coef, ++pow, ++size2); //Sorting to achieve descending power polynomials Sort(coefs1, coefs1 + size1, pows1, pows1 + size1); Sort(coefs2, coefs2 + size2, pows2, pows2 + size2); Term polynomial1 = NewTerm((struct Fraction){-1, 1}, -1), term1 = polynomial1, polynomial2 = NewTerm((struct Fraction){-1, 1}, -1), term2 = polynomial2; for (int i = 0; i < size1; ++i, term1 = term1->next) term1->next = NewTerm((Frac){coefs1[i], 1}, pows1[i]); for (int i = 0; i < size2; ++i, term2 = term2->next) term2->next = NewTerm((Frac){coefs2[i], 1}, pows2[i]); Term *polynomial3 = Div(polynomial1, polynomial2); printf("Quotient :"); Output(polynomial3[0]); printf("Remainder:"); Output(polynomial3[1]); Clear(polynomial3[0]); Clear(polynomial3[1]); free(polynomial3); return 0; } ``` /* --- 執行結果 2 2 3 1 1 0 1 1 3 0 Quotient : 2x^1 - 3 Remainder: 10 3 2 2 1 1 0 2 1 3 0 Quotient : (3/2)x^1 - (5/4) Remainder: (19/4) 2 5 1 4 -2 1 1 0 5 2 4 1 Quotient : (2/5)x^3 - (3/25)x^2 + (12/125)x^1 - (48/625) Remainder: - (1058/625)x^1 + 1 --- */ ![](https://i.imgur.com/3ICfAVp.png) 時間複雜度：*O*($max(nm, n(em-en))$)，其中 $m$ 是多項式 A 中的項數，$n$ 是多項式 B 中的項數，$em$ 是多項式 A 的最大冪，$en$ 是多項式 B 的最大冪。 ::: --- ### 13. 利用環形串列重做習題 7~10。請比較兩做法的時間複雜度。 :::spoiler   一般而言，線性串列、環狀串列、含開頭空白節點的環狀串列、或雙向串列在搜尋、新增(至某節點後)、刪除... 皆有相同的時間複雜度(即令處理的細節互有所異)；唯在邊界條件 (first?=NULL、head?=NULL、...)判定時，含開頭空白節點的環狀串列可省下檢測是否為空串列的考量。 ::: --- ### 15. 如節 4.7 所介紹：當矩陣的非 0 元素很多時，稱此矩陣為稀疏矩陣 (sparse matrix)。請設計儲存非 0 元素的節點結構。若所設計的結構與圖 4-31 不同，請比較並討論其優劣。 :::spoiler ```cpp= typedef struct Matrix_Node { int data; struct Pos { int i, j; } pos; struct Matrix_Node *next_r, *next_c; } *Node; ``` ::: --- ### 17. 請設計演算法，解決兩稀疏矩陣的相加。請分析演算法的複雜度。 :::spoiler ```cpp= void Mul(Sparse_Matrix a, Sparse_Matrix b, int m, int p, int q) { Initialization(&result, m, q); for (int i = 0; i < m; i++) { for (int j = 0, n; j < q; j++) { Node ap = a.row_f[i], bp = b.col_f[j], x; n = 0; while (ap && bp) { if (ap->pos.j < bp->pos.i) ap = ap->next_r; else if (ap->pos.j > bp->pos.i) bp = bp->next_c; else { n += ap->data * bp->data; ap = ap->next_r; bp = bp->next_c; } } if (n) { x = NewNode(n, i, j); InsertLastR(&result.row_f[i], &result.row_l[i], x); InsertLastC(&result.col_f[j], &result.col_l[j], x); } } } } int main() { int m, p, q; scanf("%d %d %d", &m, &p, &q); Build(m, p, q); Mul(a, b, m, p, q); printf("\nResult:"); Output(result, m, q); } ``` /* --- 執行結果 5 5 5 0 0 3 0 6 0 7 0 0 0 5 3 0 0 0 0 0 0 5 0 0 7 0 0 0 0 0 5 0 0 0 2 0 0 8 3 0 0 0 2 0 0 0 2 1 0 0 3 0 0 Result: 9 0 18 0 6 0 14 0 0 56 0 6 25 0 24 0 0 0 10 5 0 14 0 0 56 --- */ ![](https://i.imgur.com/3HCZJFi.png) 時間複雜度：*O*($nm + pq$)，其中 $n$ 是稀疏矩陣 A 中非零元素的數量，$m$ 是稀疏矩陣 B 中非零元素的數量，$p$ 是稀疏矩陣 A 中的行數，$q$ 是稀疏矩陣 B 中的列數 。 ::: --- --- ## 第五章 樹 --- ### 1. 針對程式 5-1 一般化串列鏈結節點的宣告，設計樹的輸入，寫出必要的程序，使能完成樹的一般化鏈結串列的建構。 :::spoiler ```cpp= Add (struct TreeNode *p, struct TreeNode *subtree) { struct TreeNode *s; s->tag = 1; s->link = p->link; p->link = s; s->node = subtree; } ``` ::: --- ### 3. 在5.2.3節中我們討論了分支度為2的樹表示法，請寫出此節點的程式宣告。 :::spoiler ```cpp= # include struct node { struct node *Left; int data; struct node *Right; }; struct node *root; int main(){ return 0; } ``` ::: --- ### 5. 參考程式 5-6-1，實作出非遞迴版本的程式，執行二元樹前序走訪。 :::spoiler ```cpp= # include # include //BinaryTreeNode struct node { struct node *LeftChild; int data; struct node *RightChild; }; struct node *NewNode(int x) { struct node *Node = (struct Node *)malloc(sizeof(struct node)); Node->data = x; Node->LeftChild = NULL; Node->RightChild = NULL; return Node; } struct node *Insert(struct node *Node,int x){ if (Node == NULL) return NewNode(x); if (x < Node->data) Node->LeftChild = Insert(Node->LeftChild, x); else Node->RightChild = Insert(Node->RightChild, x); return Node; } struct node *root; //Stack struct node **Stack; int top = -1; void push(struct node *element) { if (top >= 1000) return; else Stack[++top] = element; } struct node *pop(){ if (top == -1)return NULL; else return Stack[top--]; } int StackEmpty() { return top == 1000; } //preorder void preorder() { struct node *p = root; while (!StackEmpty()||p) { while (p) { printf("%d\n", p->data); push(p); p = p->LeftChild; } if (!StackEmpty()) { p = pop(); p = p->RightChild; } } } int main() { Stack = (struct Node **)malloc(1000 * sizeof(struct node*));//Insert 100 random number(0~32767) for(int i=0; i<100; i++) { int number = rand(); root = Insert(root,number); } preorder(); } ``` ::: --- ### 7. 參考程式 5-7 實作出階層走訪 (level-order travesal) 的程式，走訪一二元樹。 :::spoiler ```cpp= # include # include //BinaryTreeNode struct node { struct node *LeftChild; int data; struct node *RightChild; }; struct node *NewNode(int x) { struct node *Node = (struct Node *)malloc(sizeof(struct node)); Node->data = x; Node->LeftChild = NULL; Node->RightChild = NULL; return Node; } struct node *Insert(struct node *Node,int x){ if (Node == NULL) return NewNode(x); if (x < Node->data) Node->LeftChild = Insert(Node->LeftChild, x); else Node->RightChild = Insert(Node->RightChild, x); return Node; } struct node *root; //Queue struct node **Queue; int front = -1, rear = -1; void AddQueue(struct node *element) { if (front >= 1000) return; else Queue[++rear] = element; } struct node *DeleteQueue(){ if (rear == front)return NULL; else return Queue[++front]; } int QueueEmpty() { return front == rear; } //levelOrder void LevelOrder() { AddQueue(root); struct node *p = NULL; while (!QueueEmpty()) { p = DeleteQueue(); printf("%d\n", p->data); if (p->LeftChild ) AddQueue(p->LeftChild); if (p->RightChild) AddQueue(p->RightChild); } } int main() { Queue = (struct Node **)malloc(1000 * sizeof(struct node*)); //Insert 100 random number(0~32767) for(int i=0; i<100; i++) { int number = rand(); root = Insert(root,number); } LevelOrder(); } ``` ::: --- ### 9. 寫出一演算法將輸入的二元樹 T，以 SwapTree(T)交換每一個節點的左右子點。請看圖 5-55 的例子。 ![](https://i.imgur.com/h5jpP6O.png) :::spoiler ```cpp= SwapTree(Tree T) { for( T 上每一個點) { node = T->leftchild; T->leftchild = T->rightchild; T->rightchild = node; } } ``` ::: --- ### 11. 請參考程式 5-12，寫出程序—使可插入節點 new 成為引線二元樹的節點 p 的左子節點。 :::spoiler ```cpp= void Threaded::InsertLeft ( ThreadedNode *s, char ch)//建立node h; 將ch 存入h; 插入h 作為s 的左兒子 { ThreadedNode *h = new ThreadNode(ch); h->LeftChild = s->LeftChild; h->LeftThread = s->LeftThread; h->RightChild = s; h->RightThread = TRUE; // 左兒子為引線 s->LeftChild = h; //把h 加到s s->LeftThread = FALSE; if(!LeftThread) { ThreadedNode *temp = InorderPred(1); Temp->RightCgild = 1; } } ``` ::: --- ### 13. 寫一演算法以在最小堆積中作插入動作。這個演算法的複雜度應為O(logn)，請證明。 :::spoiler ```cpp= void InsertHeap(int x) { if (n == maxsize) HeapFull(); else { n++; i = n; while ((i > 1) && (x < heap[i/2])) { heap[i] = heap[i/2]; i /= 2; } heap[i] = x; } } ``` 新增節點的位置若在 k 處，則新增資料可能的位置，會在 k 往上走至樹根的任何節點上，亦即最差情況程式迴圈會執行 ⎡log(k+1)⎤ 次，這也是此完備二元樹的深度。因此程序 InsertHeap 在插入第 $n$ 個資料時，需要的時間複雜度為 *O*($logn$)。 ::: --- ### 15. 證明一樹林的前序走訪與其對應二元樹的前序走訪，結果相同。 :::spoiler 假設$(T_1, T_2, ..., T_n)$視為一樹林且$PO(T_1, T_2, ..., T_n)$為樹林的前序走訪，將森林的樹個別做前序走訪並依序合併寫作$PO(T_1), PO(T_2), ..., PO(T_n)$，可將$T_1$視為是跟以及左子樹，$T_2, T_3, ..., T_n$視為右子樹，顯然的，$T_1$ 在其他樹的元素前先做了前序走訪，重複這個假設，我們可以得到 $T_1, T_2, ..., T_n$ 的前序走訪會與樹林的前序走訪有相同的順序。 ::: --- ### 17. 以樹林後序走訪法，寫一個非遞迴程序走訪一樹林的對應二元樹。並計算你的程序之時間與空間複雜度。 :::spoiler ```cpp= Void Forest :: postorder() { Stack s; Stack t; int CurrentFlag; ForestNode *CurrentNode = root; while (1) { while (CurrentNode) { s.Add(CurrentNode);//存此點,之後會走其右子樹 t.Add(0);//左右子樹需要被走訪 CurrentNode = CurrentNode->Leftchild;//走訪左子樹 if(!s.Empty () { CurrentNode = *s.Delete (CurrentNode); CurrentFlag = *t.***Dr1rte (CurrentFlsg); if(CurrentFlag==0)//右子樹尚未走訪 { if(CurrentNode !=root) cout<data<Rightchild;//走訪右子樹 } else CurrentNode =0;// CurrentFlag ==1,左右子樹皆走訪過了 } } count<data<data = prefix[1]; k = find(prefix[1], infix); node->leftchild = BTree_InfixPrefix (infix[1,k-1], prefix[2,k-1]); node->rightchild = BTree_InfixPrefix (infix[k+1,infix.Length-k],prefix[k+1,prefix.Length-k]); return node; } ``` ::: --- ### 23. 實作程式 5-23 新增資料至 AVL 樹中。 :::spoiler 程式 5-23 已編譯正確。 ::: --- --- ## 第六章 圖形 --- ### 1. 證明當我們對一個無向連通圖形 G 執行深先搜尋 DFS（演算法 6-1）時，T 中的所有邊會形成一棵樹。  首先證明 H 是 connected，若 H 不是 connected，令 x 為 dfs 程序結束後，尚 未被標示為 true 的點，既然 G 為 connected，那麼一定存在至少一點連接標示為 true 的某一點和 x 內的某一點，這是矛盾的!(當一點被走訪，所有與其連接的點皆會被標示為 true)所以 H 是 connected。  接下來我們得證明 H 中沒有 cycle，一開始{ H=ψ，每當一條 edge(u,v)要加 入 H 時，我們一定是找 visited[v]=false 者，然後設 visited[v]=true，假設(u,v)即為 令 H 造成 cycle 的 edge，表示當初 visited[u]和 visited[v]皆為 ture，既然兩者皆為 true，我們不可能考慮(u,v)的加入，所以 H 不會有 cycle。 --- ### 3. 假設 G 是一個無向連通圖形。證明 G 裡的邊沒有重複出現在 G 的兩個雙向連通成分 (biconnected component) 裡。 假設 G 裡的邊 (u, v) 重複出現在 2 個雙向連通成分 $C_1$ 和 $C_2$ 中，那麼 $C_1$ 的點可經由 (u, v) 雙向地往返 $C_2$ 的點，反之亦然；於是可將 $C_1$ 和 C2 組成更大的雙向連通成分—這與「雙向連通成分已是最大子圖」的限制產生矛盾！故 G 裡的邊不會重複出現在 2 個或以上的連通成分。 --- ### 5. 把 Kruskal 最小成本延展樹的演算法寫成完整的程式。 ```cpp= # include #include using namespace std; struct edge { char v1, v2; int cost; }; edge e[10000];s int sorted[10000]; void SORT(int ary[], int n) { for (int k=0; k ary[i]) { index = i; MIN = ary[i]; } } sorted[k] = index; ary[index] = 99999; } } int Find(int parent[], int n) { if (parent[i] == -1) return i; return Find(parent, parent[n]); } void Union(int parent[], int x, int y) { int setX = Find(parent, x); int setY = Find(parent, y); parent[setX] = setY; } bool isCycle(edge e, int n, int m) { int parent = new int[n]; for (int i=0; i>n>>m; for (int i=0; i using namespace std; int main () { int n,w[100][100],A[100][100],a,b; cin>>n; for(int i=0;i>w[i][j]; } for(int i=0;i>a>>b; cout<next = first->next; first->next = q; } struct spNode * newSPNode(edgeNode * p) { struct spNode * q = new struct spNode; q->u = p->u; q->v = p->v; return q; } void BFSSP(int u) // 以 u 為起點做 BFS { int v, i, visited[SIZE]; struct spNode * q; for (i=0; inext) // 所有與 v 相鄰的頂點 w) { if (visited[p->v] == 0) { visited(p->v) = 1; q = newSPNode(p); addAsFirst(T[u].link, q); Add_Queue(p->v); } } } // T[u].edge 所指串列即為 “以 u 為起點做 BFS 後延展樹邊” 的集合; } ``` --- ### 19. 一棵樹的「半徑」(radius) 是指從根節點到其中某個葉 (leaf) 的最長長度。給定一個無向連通圖形 G，所有邊長皆為 1，設計一個函式找出 G 中有最小半徑的延展樹。 ```cpp= struct spNode // Adjacent list for spanning tree T { int u, v; int level; }; strut spList { int radius; struct spNode * link; }; struct spList T[n]; struct edgeNode // Adjacent list for input graph G { int u, v; struct edgeNode * next; }; struct vertexList { struct edgeNode * edge; }; struct vertexList G[n]; void addAsFirst(struct spNode * first, struct spNode * q) { q->next = first->next; first->next = q; } struct spNode * newSPNodeLevel(edgeNode * p, int level) { struct spNode * q = new struct spNode; q->u = p->u; q->v = p->v; q->level = level+1; return q; } int radiusBFSSP(int u) // 以 u 為起點做 BFS { int v, i, visited[SIZE], level; struct spNode * q; for (i=0; inext) // 所有與 v 相鄰的頂點 w) { if (visited[p->v] == 0) { visited(p->v) = 1; q = newSPNodeLevel(p, level); addAsFirst(T[u].link, q); Add_Queue(p->v, q->level); if (q->level>T[u].radius) T[u].radius = q->level; } } } return T[u].radius; } int findSPMinRadius() { int i, r, minSPRadius = MAXINT; minSPRoot; for (i=0; i   (a) 挑選排序、氣泡排序和插入排序。
  (b) Shell 排序和合併排序。 (a) | |額外儲存空間|時間複雜度|穩定性| |:------:|:------:|:------:|:------:| | 挑選排序 | *O*(1) | *O*($n^2$) | X | | 氣泡排序 | *O*(1) | *O*($n^2$) | O | | 插入排序 | *O*(1) | *O*($n^2$) | O | (b) | |額外儲存空間|時間複雜度|穩定性| |:------:|:------:|:------:|:------:| | Shell排序 | X | *O*(n logn) | X | | 合併排序 | X | *O*(n logn) | O | --- ### 3. 請說明本章所有排序演算法在輸入數列以下面兩種排序時的表現：
  (a) 排序完成
  (b) 反向排序完成 | 排序法 |排序完成|反向排序完成| |:------:|:------:|:------:| | 挑選排序 | *O*($n^2$) | *O*($n^2$) | | 插入排序 | *O*($n$) | *O*($n^2$) | | 氣泡排序 | *O*($n$) | *O*($n^2$) | |Shell排序| 與資料是否已排序無關 | | 合併排序 | 與資料是否已排序無關，皆為 *O*($nlogn$) | | 快速排序 | *O*($n^2$) | *O*($n^2$) | | 基數排序 | 與資料是否已排序無關，皆為 *O*($nlogn$) | | 堆積排序 | 與資料是否已排序無關，皆為 *O*($nlogn$) | ![](https://i.imgur.com/fOjRfgT.png) --- ### 5. 請實作不同版本的快速排序法：
  (a) 遞迴版
  (b) 利用堆疊和以迴圈控制版
  (c\) 當 left~right 間的資料量少於 10 時，直接用挑選或排序；不必再遞迴呼叫（或 push 入堆疊）
  (d) 取一個 0~n−1 的亂數 i，令 target 為 data[i]
  (e) 令 target 為 data[0]、data[n/2]和 data[n-1]的中位數。
  並利用題 2 的實驗設計製作圖表，觀察並討論實驗結果。 (a) ```cpp= # include using namespace std; void swap(int *x, int *y) { int t; t = *x; *x = *y; *y = t; } void Quick(int data[], int left, int right) { int i, j, target; if(left < right) { i = left + 1; j = right; target = data[left]; do { while((data[i] < target) && (i <= j)) i++; while((data[j] >= target) && (i <= j)) j--; if(i < j) swap(&data[i], &data[j]); }while(i < j); if(left < j) swap(&data[left], &data[j]); Quick(data, left, j-1); Quick(data, j+1, right); } } int main () { int n, i, count = 1; int data[100], temp[100]; cin>>n; for (i = 0; i < n; i++) cin>>data[i]; Quick(data, 0, n-1); for (i = 0; i < n; i++) cout< using namespace std; void swap(int *x, int *y) { int t; t = *x; *x = *y; *y = t; } int top=-1; struct StackNode { int l, r; }*stack; void push(int left, int right) { stack[++top].l = left; stack[top].r = right; } struct StackNode *pop() { struct StackNode *p = new StackNode; *p = stack[top--]; return p; } void QuickSort(int data[], int n) { stack = new StackNode[n]; int left = 0; int right = n - 1; int i, j, target; push(left, right); while(top != -1) { struct StackNode *p = pop(); left = p->l; right = p->r; target = data[left]; i = left +1 ; j = right; do { while((data[i] < target) && (i <= j)) i++; while((data[j] >= target) && (i <= j)) j--; if(i < j) swap(&data[i], &data[j]); }while(i < j); if(left < j) swap(&data[left], &data[j]); if((j+1) < right) push(j+1, right); if(left < (j-1)) push(left, j-1); } } int main () { int n, i, count = 1; int data[100], temp[100]; cin>>n; for (i = 0; i < n; i++) { cin>>data[i]; } QuickSort(data, n); for (i = 0; i < n; i++) { cout< # include # include using namespace std; int partition(int arr[], int left, int right) { int pivot = arr[right]; int i = (left - 1); for (int j = left; j <= right - 1; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[right]); return (i + 1); } int partition_r(int arr[], int left, int right) { srand(time(NULL)); int random = left + rand() % (right - left); swap(arr[random], arr[right]); return partition(arr, left, right); } void quickSort(int arr[], int left, int right) { if (left < right) { int pi = partition_r(arr, left, right); quickSort(arr, left, pi - 1); quickSort(arr, pi + 1, right); } } void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) cout<>n; int arr[100]; for(int i = 0; i>arr[i]; quickSort(arr, 0, n - 1); cout<<"Sorted array:"; printArray(arr, n); return 0; } ``` ![](https://i.imgur.com/niCcKTX.png) --- ### 7. 請實作不同版本的堆積排序法：
  (a) 用陣列實作最小（大）堆積
  (b) 用鍵結串列實作最小（大）堆積。
  並利用題 2 的實驗設計製作圖表，觀察並討論實驗結果。 請依演算法 7-12 實作本習題，並比較行結果。 --- ### 9. 證明當較小的子串列先排序時，那麼快速排序中的遞迴，可以用深度為*O*($logn$) 的堆疊來模擬。 快速排序演算法，最好的情況就是每次剛好分割一半，時間複雜度就可達到 *O*($nlogn$)，需要 *O*($logn$) 次的分割；而一次分割後先執行某一半資料的排序，另一半（的起點和終點）放堆疊，需要*O*(1) 的堆疊空間，總共分割 *O*($logn$) 次，會需要有 *O*($logn$) 的堆疊空間。若分割不平均，且較小的子數列先排序，較大的子數列要先放堆疊，空間 *O*(1)。小的子數列排序時所用的堆疊空間肯定少於 *O*($logn$)，而它排序完成後，曾用到的堆疊空間（少於 *O*($logn$)）會釋放出來，堆疊剩當時分割後較大的子數列（起點、終點）在堆疊。pop 後堆疊已空；數列又分割，又是小數列先排序—所用的堆疊空間肯定少於 *O*($logn$)…。以此類推，深度為 *O*($logn$) 的堆疊空間肯定足夠。 --- ### 11. 請舉例說明基數排序的最差情形。 當要比較的數字中，大部分的數字位數為 s，但只有極少部分的數字位數為 k，當 s 極小而 k 極大時會有最差情形；也就是說因為有極大的 k 值，使得所有 位數皆要做一次排序，排了 k 次，但大部分只的值其實只須排 s 次就完成。例如： 3，1，5，20，20360051470009000358454718 --- ### 13. 設計一個程序，將數列 $(x_1, x_2, ... , x_n)$ 向右環形移動 $p$ 個位置，其中 $0 ≤ p ≤ n$。此程序應有 *O*($n$) 的時間複雜度，而其空間複雜度應為 *O*(1)。 ```cpp= void Reverse(int *list, int first, int last) { int firstindex = first, lastindex = last; while(firstindex < lastindex) { //swap int temp = list[firstindex]; list[firstindex] = list[lastindex]; list[lastindex] = temp; firstindex++; lastindex--; } } void RightCircularShift(int *list, int p, int n) { if (p>0 && p