# 資料結構與演算法 習題解答 奇數題
## 第一章 基本概念
---
### 1. 寫一個程序，將傳入的整數參數 x、y 和 z 由小到大印出。此程序的計算時間為多少？
:::spoiler 可利用 bubble sort 的概念：
```cpp=
# include <stdio.h>
# include <iostream>
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
---- */
:::
---
### 3. 費氏 (Fibonacci) 數列被定義成： <br>   (1) $F_0 = 0, F_1 = 1;$ <br>   (2) $F_n= F_{n−1} + F_{n−2},$ 當 $n≥2$。 <br> 寫出遞迴和迴圈版本（非遞迴）的程序來計算費氏數列（輸入 $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
---- */
:::
:::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<<F[i]<<" ";
cout<<endl<<endl;
}
}
```
/* ---- 執行結果:
3
0 1 1 2
5
0 1 1 2 3 5
10
0 1 1 2 3 5 8 13 21 34 55
20
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
---- */
:::
---
### 5. Ackerman’s 函式 A(m, n) 的定義如下： <br> $\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}$ <br> 這個函式在 $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
(等候逾時)
---- */
:::
::: spoiler 迴圈版本：
```cpp=
#include<iostream>
#include<time.h>
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="<<i<<" nj="<<j<<"Value=";
START = clock();
cout<<ack_nonrecursive(i, j)<<endl;
END = clock();
cout<<"Execution Time: "<<(END - START) /
CLOCKS_PER_SEC<<"s"<<endl<<endl;
}
}
```
/* ---- 執行結果:
 
:::
:::spoiler 遞迴與迴圈執行時間比較 (CPU: RAM: OS: Windows 10)：
| 遞迴版執行時間 | 迴圈版執行時間 |
| -------- | -------- |
|  |  |
:::
---
### 7. 假如 S 是一個含有 $n$ 個元素的集合，則 S 的 power set 就是「所有 S 可能的子集合的集合」，例如：假如 S = {a, b, c} ，則 powerset(S) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}，寫一個遞迴程式來計算 powerset(S)。
:::spoiler 請見下表：
   *S*               powerset(*S*)中元素
|{a, b, c}|{}|{c}|{b}|{b, c}|{a}|{a, c}|{a, b}|{a, b, c}|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
|0/1 Bit|000|001|010|011|100|101|110|111|
由上表可知：求 S = \{a, b, c} 的 power set 相當於求 000 \~ 111 的所有 bit patterns!
可設一 0/1 Bit 陣列 (\|BIT\| = \|S\|) 與 S 的字元相互對應，recursively 求 Bit 的所有0/1 patterns: powerset(Bit[k,n]) = {Bit[k]=0 \|\| powerest(Bit[k+1,n])} ∪ {Bit[k]=1 \|\| powerest(Bit[k+1,n])} 其中 || 表示 0/1 patterns 的串接。呼叫 powerset(Bit[n-1,n]) 時即為 boundary condition 可依 Bit[0:n-1] 的0/1 pattern 印出對應的 subset of S.
```cpp=
# include <stdio.h>
# include <stdlib.h>
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<n; i++)
if (Bit[i]) b[index++] = a[i];
b[index] = '\0';
printf("{%s}", b);
if (++cnt<solCnt) printf(", ");
}
void powerSet(int k, int n)
{ if (k == n) printSubset(Bit, n);
else
{ Bit[k] = 0;
powerSet(k+1, n);
Bit[k] = 1;
powerSet(k+1, n);
}
}
int main()
{ int i, n;
printf("Please input the size (n) of the set: n = ");
while (scanf(" %d", &n), solCnt = pow(2, n), n!=0)
{ printf("{");
powerSet(0, n);
printf("}\nSize of Powerset = %d.\n\nContinue (0 for exit) n = ", cnt);
cnt = 0;
}
return 1;
}
```
/* ---- 執行結果:
Please input the size (n) of the set: n = 3
{{}, {c}, {b}, {bc}, {a}, {ac}, {ab}, {abc}}
Size of Powerset = 8.
Continue (0 for exit) n = 4
{{}, {d}, {c}, {cd}, {b}, {bd}, {bc}, {bcd}, {a}, {ad}, {ac}, {acd}, {ab}, {abd}, {abc}, {abcd}}
Size of Powerset = 16.
Continue (0 for exit) n = 5
{{}, {e}, {d}, {de}, {c}, {ce}, {cd}, {cde}, {b}, {be}, {bd}, {bde}, {bc}, {bce}, {bcd}, {bcde}, {a}, {ae}, {ad}, {ade}, {ac}, {ace}, {acd}, {acde}, {ab}, {abe}, {abd}, {abde}, {abc}, {abce}, {abcd}, {abcde}}
Size of Powerset = 32.
Continue (0 for exit) n = 7
{{}, {g}, {f}, {fg}, {e}, {eg}, {ef}, {efg}, {d}, {dg}, {df}, {dfg}, {de}, {deg}, {def}, {defg}, {c}, {cg}, {cf}, {cfg}, {ce}, {ceg}, {cef}, {cefg}, {cd}, {cdg}, {cdf}, {cdfg}, {cde}, {cdeg}, {cdef}, {cdefg}, {b}, {bg}, {bf}, {bfg}, {be}, {beg}, {bef}, {befg}, {bd}, {bdg}, {bdf}, {bdfg}, {bde}, {bdeg}, {bdef}, {bdefg}, {bc}, {bcg}, {bcf}, {bcfg}, {bce}, {bceg}, {bcef}, {bcefg}, {bcd}, {bcdg}, {bcdf}, {bcdfg}, {bcde}, {bcdeg}, {bcdef}, {bcdefg}, {a}, {ag}, {af}, {afg}, {ae}, {aeg}, {aef}, {aefg}, {ad}, {adg}, {adf}, {adfg}, {ade}, {adeg}, {adef}, {adefg}, {ac}, {acg}, {acf}, {acfg}, {ace}, {aceg}, {acef}, {acefg}, {acd}, {acdg}, {acdf}, {acdfg}, {acde}, {acdeg}, {acdef}, {acdefg}, {ab}, {abg}, {abf}, {abfg}, {abe}, {abeg}, {abef}, {abefg}, {abd}, {abdg}, {abdf}, {abdfg}, {abde}, {abdeg}, {abdef}, {abdefg}, {abc}, {abcg}, {abcf}, {abcfg}, {abce}, {abceg}, {abcef}, {abcefg}, {abcd}, {abcdg}, {abcdf}, {abcdfg}, {abcde}, {abcdeg}, {abcdef}, {abcdefg}}
Size of Powerset = 128.
Continue (0 for exit) n = 0
Process returned 1 (0x1) execution time : 51.907 s
Press any key to continue.
---- */
:::
---
### 9. 比較 $n^3$ 和 $2^n$ 這兩個函式，計算出哪個 $n$ 值會使後者大於前者。
:::spoiler
當 $n$ = 10 時, $n^3$ =1000 < $2^n$ = 1024; 當 $n$ > 10 時, $n^3$ < $2^n$。
:::
---
### 11. 分析下列程式的時間複雜度—計算出 x 的值（初始值皆為0），並以大*O*表示其時間複雜度：
::: spoiler
(a)
```cpp=
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
for (k=1; k<=j; k++)
x++;
```
(a) 利用重複物件的組合來解迴圈執行次數：
$\quad {r+n-1\ \choose r} \\
={3+n-1\ \choose 3} \\
=\frac{n(n+1)(n+2)}{6} \\
= O(n^3)$
(b)
```cpp=
i=1;
while (i<=n)
{ x++;
i++;
}
```
(b) $n$ = *O*($n$)
(c\)
```cpp=
for (i=1; i<=n; i++)
for (j=1; j<=i; j*=2)
x++;
```
(c\) *O*($nlogn$) 列出註標 i, j 的值，與當*時x++的計算次數，之後加總之。
| i | 1 | 2 | 3 | 4 | ... | n |
|- |---| - | --| -|-----|-- |
|j |1| 1, 2 | 1, 2| 1, 2, 4|...|1, 2, 4, ... $n$ |
|# |1| 2 | 2| 3|...|$logn+1$ |
|# |$log1+1$| $log2+1$ | $log3+1$| $log4+1$|...|$logn+1$ |
$log1+1+log2+1+...+logn+1$
$=\sum_{k=1}^{n}logn+n$
$= log(1\times 2\times ... \times n)+n$
$= log(n!)+n \\ \le log(n^n)+n = nlogn+n\\ =O(nlogn)$
(d)
```cpp=
for (i=1; i<=n; i*=2)
for (j=1; j<=i; j++)
x++;
```
(d) *O*($n$)
| i | 1 | 2 | 4 | 8 | ... | n |
|- |---| - | --| -|-----|-- |
|j |1| 1,2 | 1,2,3,4| 1~8|...| 1~$n$ |
|# |1| 2 | 4| 8|...|$n$ |
|# |$2^0$| $2^1$ | $2^2$| $2^3$|...|$2^{logn}$ |
$2^0+2^1+2^2+ ... + 2^{logn} \ (引用等比級數和的公式)\\
=\frac{2^0(2^{logn+1}-1)}{2-1} \\ =2^{logn+1}-1\\
=2^{logn}\times 2-1\\
=2n-1\\
=O(n)$
:::
---
### 13. 證明下列等式是錯誤的： <br>   (a) $10n^2+9 = O(n)$ <br>   (b) $n^2logn = Θ(n^2)$ <br>   ($\text{c}$) $\frac{n^2}{logn} = Θ(n^2)$ <br>   (d) $n^32^n+6n^23^n = O(n^32^n)$
::: spoiler
(a)
$g(n) = n$
$cn ≥ 10n^2+9$
因為找不到合適的 $c, n_0$
使得 $n ≥ n_0$ 後，$cn ≥ 10n^2+9$
(b)
$n^2logn = Θ(n^2)$ 若為真，則存在常數 $c_1、c_2$ 和 $n_0$ (由定義可知 $n > n_0$)，可得
到 $c_1n^2 ≤ n^2logn ≤ c_2n^2$。$n^2logn ≤ c_2n^2 => logn ≤ c_2$ ，
選擇 $n > \max\{n_0, 2c_2\}$，會產生矛盾。
($\text{c}$)
$\frac{n^2}{logn} = Θ(n^2)$ 若為真，則存在常數 $c_1、c_2$ 和 $n_0$ (由定義可知 $n > n_0$)，可得到
$c_1n^2 ≤ n^2/logn ≤ c_2n^2$。$c_1n^2 ≤ n^2/logn=> logn ≤ 1/c_1$ 會產生矛盾，因為左邊當 $n$ 遞增時會跟著遞增，但右邊則為常數。
(d)
$g(n) = n^32^n$
$cn^32^n ≥ n^32^n+6n^23^n => cn2^n ≥ n2^n+6×3^n$
因為找不到合適的 $c, n_0$
使得 $n ≥ n_0$ 後，$cn^32^n ≥ n^32^n+6n^23^n$
:::
---
## 第二章 陣列 習題解答
---
### 1. 有多少元素可以存在以下的陣列中（註標範圍 [x:y] 中 x 表示下界，y表示上界）： <br>   (a) A[0:n]； <br>   (b) B[-23:29]; <br>   ($\text{c}$) C[-1:n][1:m]； <br>   (d) D[-n:0][1:3]；
:::spoiler
(a) n+1
(b) 23+1+29 = 53
($\text{c}$) (1+1+n)×m = m(n+2)
(d) (n+1)×3 = 3(n+1)
註：C 的陣列宣告時只需要陣列型態、名稱和大小；其註標從 0 開始，而且沒有下界、上界範圍的考量。這個題目旨在希望讀者對陣列內的個數／內容與註標定址有較廣泛的聯想。若希望用 "下界...上界" 來定位陣列元素，可以用指標來完成。請看下面的例子：
其中前三行是程式的設定（第3行以 p 指向 A[5] 的住址）、後四行表列展示 A[0], A[1], ... , A[9] 和 *(p-5), *(p-4), ... , *(p+4) 各自存放的內容；可以清楚看出 A[0] 與 *(p-5) 、A[1] 與 *(p-4)、 ... 、A[9] 與 *(p+4) 的值是一樣的；亦即：對 p 而言，可用 -5...9 中的註標來定址陣列 A。用指標的概念，可使陣列的註標定址關係有更大的彈性。
:::
---
### 3. 寫一個程序來估算每個不同的字元在字串中出現的次數，用適當的資料來測試你的函式。
:::spoiler 以下程式以英文小寫字元 'a', 'b', ... , 'z' 為例。
```cpp=
# include <stdio.h>
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<len; i++) freq[s[i]-base]++;
for (i=0; i<26; i++)
if (freq[i] != 0) printf("%c : %d\n", base+i, freq[i]);
}
int main()
{ char s [256];
int len;
while (scanf("%s", s)!=EOF)
{ printf("s = %s\n", s);
for (len=0; s[len] != '\0'; len++);
printf("len = %d\n", len);
charFrequency(s, len);
}
return 1;
}
```
/* ---- 執行結果:
asgfagsfgafsgafsgfagsfagfsg
s = asgfagsfgafsgafsgfagsfagfsg
len = 27
a : 6
f : 7
g : 8
s : 6
trwretwretrwtertwretuqywuyuywueyuwyueywuyeuyw
s = trwretwretrwtertwretuqywuyuywueyuwyueywuyeuyw
len = 45
e : 7
q : 1
r : 6
t : 6
u : 8
w : 9
y : 8
nvjfnjvfnjvnfjnvjfnvjnfjnjfvfnfjnvjfnjvnjfnvjf
s = nvjfnjvfnjvnfjnvjfnvjnfjnjfvfnfjnvjfnjvnjfnvjf
len = 46
f : 11
j : 13
n : 13
v : 9
---- */
:::
---
### 5. 寫一個函式，它會接受一個字串 text 和兩個整數 start 和 length，這個函式會從字串 text 的第 start 個字元起刪除 length 個字元，而傳回產生新的字串。
:::spoiler
```cpp=
char[] deleteText(char text[], int start, int length)
{ int k;
int groot[256];
// int n=text.length();
for (i=0, k=0; i<length; i++)
{ if (i<start || 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$，這些串列所能做的運算就是插入和刪除。 <br>   (a) 找出 front[$i$] 和 rear[$i$] 的適當的起始和終止條件。 <br>   (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。 <br>      <br> 將 $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$。
                
:::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}$ 的例子）。請回答： <br>   (a) 在此帶狀 $D_{n,a}$ 中有多少個元素？ <br>   (b) 對於帶狀 $D_{n,a}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？ <br>   ($\text{c}$) 假設帶狀 $D_{n,a}$ 以對角線為主，並從最低的對角線開始，循序儲存在陣列 A 中。例如，圖 2-21 <br>   (b) 中的帶狀矩陣 $D_{5,2}$ 的表示法如下： <br>  <br> 找出在 $D_{n,a}$ 的下帶狀區域中的任一元素 $d_{ij}$ 的定址公式，即輸入 $i$ 和 $j$，求出 $k$，$d_{ij}$ = A[$k$]。 <br>  <br> 
::: spoiler 題12的解法為求解題13的重要基礎，特列於此
(a) 主對角線有 $n$ 個元素，以其為基準，上方的1, 2, ... , *a*-1 條對角線分別有 $n-1,\ n-2,\ ...\ ,\ n-a+1$ 個元素，如下圖左；
|  |  |
|----|----|
於其下方的 *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) 若 $i<j\ 且\ j-i = t，A[i][j]$ 在 $D$ 上方的第 $t$ 條對角線，$1 \leq t\leq a-1$；
(b.3) 若 $i>j\ 且\ 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<j\ 且\ j-i = t$，$A[i][j]$ 在 $D$ 上方的第 $k$ 條對角線，$1 \leq k\leq a-1$。
$D$ 中元素共有 $n$ 個；所有下帶狀的元素個數為：
$\quad (n-1)+(n-2)+\ ...\ +(n-a+1) \\
=\frac{(n-1+(n-a+1))(a-1)}{2}
=\frac{(2n-a)(a-1)}{2}。$
在 $D$ 上第 $1,\ 2, \ ...\,\ t-1$ 條對角線的元素共有：
$\quad (n-1)+(n-2)+\ ...\ +(n-t+1) \\
=\frac{(n-1+(n-t+1))(t-1)}{2}
=\frac{(2n-t)(t-1)}{2}。$
在 $D$ 中第 $k$ 條對角線上 $A[i][j]$ 之前的元素有 $(j-1)-(t-1)=j-t=j-(j-i)=i$ 個 (或直接想：不管那條上帶狀的對角線，列 $i$ 之前必有 $i$ 個元素)。由以上可得：
$k=i+\frac{(2n-t)(t-1)}{2}+\frac{(2n-a)(a-1)}{2}。$
總結 (c.1)-(c.3) 可得
$k=\begin{cases}
i+\frac{(2n-a)(a-1)}{2}, \ \text{if}\ (i-j)=0; \\
j+\frac{(2n-a-t)(a-t-1)}{2}, \ \text{if}\ (i-j)=t\ \text{where}\ 1\le t \le a-1; \\
i+\frac{(2n-a)(a-1)}{2}+\frac{(2n-t)(t-1)}{2}, \ \text{if}\ (j-i)=t\ \text{where}\ 1\le t \le a-1
\end{cases}$
:::
---
### 13. 一個「一般帶狀矩陣」(generalized band matrix) $D_{n,a,b}$ 是一個 $n×n$ 的矩陣，其中所有可能的非零元素，皆集中在由主對角線以下的 $a−1$ 個對角線，主對角線和主對角線以上的 $b−1$ 個對角線，所形成的帶狀區域上（如圖 2-22）。 <br>   (a) 在此帶狀 $D_{n,a,b}$ 中有多少個元素？ <br>   (b) 對於帶狀 $D_{n,a,b}$ 中的元素 $d_{ij}$ 而言，$i$ 與 $j$ 之間的關係為何？ <br>   ($\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}$ 值。 <br>               
::: 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})$
例子：$a=3,\ b=2,\ n=8$
代入上式可得元素個數共 28 個 (見下圖右下)
亦可用對角線優先的觀點來想：
主對角線 $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<a \\
i-a+n+\frac{(a-1)(2n-a)}{2}+\frac{(s-1)(2n-s)}{2-1}, \ \text{if} \quad j-i =s,\text{and} \quad s<b
\end{cases}$
若要以列為優先，則請依上述邏輯自行推導。讀者可由題12和13得知：用「對角線優先」(diagonal-major) 可以是二維陣列儲存在一維記憶體空間中，有效率地的對應關係。
:::
---
---
## 第三章 堆疊和佇列 習題解答
---
### 1. 圖 3-27 描繪了一個鐵路調度軌道，每一節車廂都編號 1, 2, 3, ..., $n$，並按順序從左到右停放在軌道上，車廂可以從任何一條橫向軌道一次一台的移進垂直軌道，而移進垂直軌道的車廂也可以一次一台的移到任何一條橫向軌道，則垂直軌道就像一個堆疊，新移進車廂都在最上層，能移出的車廂也是最上層的那一個。假設 $n$ = 3 時，我們可以先移車廂 1 進垂直軌道，再來是車廂 2，最後是車廂 3，然後我們就得到一個新的順序 3, 2, 1；當 $n$ = 3和 4 時，可以得到哪幾種有可能的車廂排列？有哪幾種排列是不可能的？ <br>             
:::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 <stdio.h>
# include <iostream>
#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<<endl;
}
int main()
{ string s;
int v;
while(cout<<"前加入(j)/後加入(i)/前刪除(p)/後刪除(q) :",cin>>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. 寫出下列式子的後置式： <br>   (a) A×B×C <br>   (b) -A+B-C+D <br>   ($\text{c}$) A×-B+C <br>   (d) (A+B)×D+E/(F+A×D)+C <br>   (e) A&&B\||C\||!(E>F) <br>   (f) !(A&&!((B<C)\||(C>D)))\||(C<E) <br>   (g) A and B or C or not (E>F) <br>   (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： <br>   (a) 將習題 6 表示成對應的前序表示。 <br>   (b) 寫一個演算法來計算前置表示法 e。 <br>   ($\text{c}$) 寫一個演算法把中置式 e 轉成相等的前置式，假設每個 e 都以符號 "#"做開頭，且其前置式的也要以 "#" 做開頭。 <br> 你的演算法 (b) 和 ($\text{c}$) 的複雜度為多少？每個演算法需要多少空間？
:::spoiler
(a) − − +12 /× /× 34567 / 89
(b)
```cpp=
# include <iostream>
# include <string>
# include <algorithm>
using namespace std;
int top=0;
int opndstk[100000];
int opndstk_pop()
{ if (top==-1) cout<<"empty stack."<<endl;
else return opndstk[--top];
}
int calculate(int o1, int o2, char opr)
{ if (opr == '+') return o1+o2;
if (opr == '-') return o1-o2;
if (opr == '*') return o1*o2;
else return o1/o2;
}
int main()
{ int i=-1;
string s;
cin>>s;
reverse(s.begin(), s.end());
int ans=0;
int opnd1, opnd2;
while (++i<s.size())
{ if (isdigit(s[i])) opndstk[top++] = s[i]-'0';
else
{ opnd1=opndstk_pop();
opnd2=opndstk_pop();
opndstk[top++]=calculate(opnd1, opnd2, s[i]);
cout<<opnd1<<" "<<s[i]<<" "<<opnd2<<" = "<<calculate(opnd1, opnd2, s[i])<<endl;
}
}
cout<<"Ans = "<<opndstk[top]<<endl;
}
```
($\text{c}$)
```cpp=
輸入：中序運算式e
輸出：對應輸入之前序運算法
n = parsing(e, token);
push(“#”);
for (i=0; i<n; i++)
{ s = token(i);
if (s是一運算元) push_opn(s);
else if (s == ”)”) //將堆疊中第一個(之前的運算子皆pop並印出
{ while((x=pop())!=”(”)
push_opn(get_prefix(x));
}
else
{ while ( p(s) <= q(Stack[top]) )
{ x = pop();
push_opn(get_prefix(x));
}
push(s);
}
}
while (Stack[top]!=”#”)
{ x = pop();
push_opn(get_prefix(x)
}
x = pop(); // pop out “#”
return pop_opn();
//—------------------
String get_prefix(x)
{ String a = pop_opn();
return x+pop_opn()+a;
}
```
:::
---
### 11. 有兩個堆疊用這節討論的方法儲存在陣列 M[m]，寫一個演算法 Add 和Delete 在堆疊 i 中，0 ≤ i ≤ 1，做加入和刪除的動作，你的演算法必須保證只要兩個堆疊的元素總和小於 m 就能加入元素，而且執行時間必須在 O(1) 內。
:::spoiler
對 Stack0 做
  push : Stack0[++top] = element;
  pop : return Stack[top--];
| | Stack0 | Stack1 |
|:----- |:-------------------- |:------ |
| Init. | top0 = -1 | top1 = m |
| push | Stack0[++top] = data | Stack1[--top] = data |
| pop | return Stack0[--top] | Stack1[top++] |
| Full | if (top1==top0) | if (top0 == top1) |
| Empty | if (top == -1) | if (top == m) |
:::
---
### 13. 設計一個資料結構，將 $n$ 個資料物件連續對應到陣列 M[$m$]，其中 $n_1$ 個物件為堆疊，剩下的 $n_2$ = $n−n_1$ 為佇列。寫出加入和刪除的演算法，只要陣列中還有空間沒使用到，此演算法就要提供空間給第 $i$ 個資料物件。注意：一個有 $r$ 個空間的環形佇列只能儲存 $r−1$ 個元素。
:::spoiler
```cpp=
#define SIZE 6
#include <iostream>
using namespace std;
int Cqueue[SIZE];
int front = -1,rear = -1;
bool QueueFull() {
if (front == 0 && rear == SIZE - 1)return true;
if (front == rear + 1)return true;
return false;
}
bool isEmpty() {
if (front == -1)return true;
else return false;
}
//增加元素
void Add(int element) {
if (QueueFull())cout << "Queue is full" << endl;
else
{ if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
Cqueue[rear] = element;
cout << "Inserted :" << element << endl;
}
}
//刪除元素
int Delete() {
int element;
if (isEmpty())
{ cout << "Queue is empty" << endl;
return -1;
}
else
{ element = Cqueue[front];
if (front == rear)
{ front = -1;
rear = -1;
}
else front = (front + 1) % SIZE;
return (element);
}
}
int Spop(){
int element;
if (isEmpty())
{ cout << "Queue is empty" << endl;
return -1;
}
else
{ element = Cqueue[rear];
if (rear == front)
{ front = -1;
rear = -1;
}
else rear = (rear - 1) % SIZE;
return (element);
}
}
void display() {
int i;
if (isEmpty()) cout << endl << "Empty Queue" << endl;
else
{ cout << "Front -> " << front;
cout << endl << "Items -> ";
for (i = front; i != rear; i = (i + 1) % SIZE)cout << Cqueue[i];
cout << Cqueue[i];
cout << endl << "Rear -> " << rear <<endl;
}
}
int main(void)
{ int select ,temp;
int loop = 1;
while ( loop )//主迴路開始
{ printf("[1]Add [2]Queue Pop [3]Stack Pop ==>\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;
}
```
:::
---
---
## 第四章 鏈結串列
---
### 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. 設計三個演算法分分別來計算： <br>   (a) 由 first 指標指向開頭節點的雙向鏈結串； <br>   (b) 由 first 指標指向開頭空節點的雙向鏈結串； <br>   ($\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$；且合併過程中不能使用其他節點。請分別考慮： <br>   (a) 單向鏈結串列（含或不含開頭空節點）； <br>   (b) 單向環狀鏈結串列； <br>   ($\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 皆為多項式， <br>   $A(x) = \sum\limits_{i=0}^{n}{a_ix^i}, B(x) = \sum\limits_{i=0}^{n}{b_ix^i}$ <br> 多項式相加的定義為： <br>   $A(x) + B(x) = \sum\limits_{i=0}^{n}{(a_i+b_i)x^i}$ <br> 請參考 3.6.1 節用鏈結串列表示多項式，設計出輸入多項式的程序，並與程式 4-17（多項式相加的程序）搭配，實作兩輸入多項式的相加，並輸出其結果。請分析並驗証使用演算法的時間與空間複雜度。 <br> 提示：可將節點設計成可儲存：非 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
--- */
時間複雜度：*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
--- */
時間複雜度：*O*($n+m$)，其中 $n$ 是多項式 A 中的項數，$m$ 是多項式 B 中的項數。
```cpp=
//Polynomial division
#include <stdio.h>
//#include <stdlib.h> //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
--- */
時間複雜度：*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
--- */
時間複雜度：*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 <stdio.h>
struct node
{ struct node *Left;
int data;
struct node *Right;
};
struct node *root;
int main(){
return 0;
}
```
:::
---
### 5. 參考程式 5-6-1，實作出非遞迴版本的程式，執行二元樹前序走訪。
:::spoiler
```cpp=
# include <stdio.h>
# include <stdlib.h>
//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 <stdio.h>
# include <stdlib.h>
//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 的例子。
:::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<ForrstNode*> s;
Stack<int> 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<<CurrentNode->data<<end1;
s.Add (CurrentNode) ;
t.Add(1);//右子樹需要被走訪
CurrentNode = CurrentNode->Rightchild;//走訪右子樹
}
else CurrentNode =0;// CurrentFlag ==1,左右子樹皆走訪過了
}
}
count<<root->data<<endl;
}
}
```
時間複雜度 *O*($n$)，$n$ 為樹林中節點的個數。
空間複雜度 *O*($n$)，$n$ 為樹林中節點的個數。
:::
---
### 19. 二元樹中的中序和前序順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其前序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由前序與中序可以得到唯一的二元樹。
推論：使 T 為一個有 $n$ 個節點的樹，使它的前序與中序分別為 $p_1, p_2, ..., p_n$ 和 $i_1, i_2, ...i_n$ ，前序的第一個元素為樹根，也就是 $p_1$，找到 $p_1$ 在中序中的位置，稱之為 $i_k$ ，因此，$(i_1, i_2, ..., i_{k-1})$ 與 $(p_2, p_3, ..., p_{k-1})$ 為T的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$ 與 $(p_k, p_{k+1}, ..., p_{n-1})$ 為 T 的右子樹。
T 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的前序與中序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一，因此 T 也為唯一的二元樹。
:::
---
### 21. 寫一個演算法，以所提供的前序和中序順序，建立出對應的二元樹。
:::spoiler
```cpp=
struct BTreeNode * BTree_InfixPrefix ( String infix , String prefix )
{ int k;
struct BTreeNode * node;
if (infix.Length == 0) return NULL;
node = (struct BTreeNode *) malloc (sizeof(struct BTreeNode));
node->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 <iostream>
#include<algorithm>
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<n; k++)
{ int index = -1, MIN = 99999;
for (int i=0; i<n; i++)
{ if (MIN > 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; i++)
parent[i] = -1;
for (int i=0; i<m; i++)
{
int x = Find(parent, e[sorted[i]].v1);
int y = Find(parent, e[sorted[i]].v2);
if (x == y)
return 1;
Union(parent, x, y);
}
return 0;
}
int main()
{ int n, m;
int aryCost[10000];
cin>>n>>m;
for (int i=0; i<n; i++) aryCost[i] = e[i].cost;
SORT(aryCost, n);
int k = 0;
while(m < n-1)
{ edge next_edge = e[sorted[k++]];
}
}
```
---
### 7. 證明 Sollin 演算法可以為所有無向連通圖形建立起最小成本延展樹。
分成多個區域，而每個區域皆以 prim 來記錄，最後加入新的邊其兩端點必位於兩個區域中，並將兩個區域合併，故產生的樹為最小成本延展樹。
---
### 9. 利用最短路徑（演算法 6-7、6-7-1）的概念，設計一個找出最小成本延展樹的演算法，其最糟狀況所花去時間為 *O*($n^2$)。
```cpp=
if (dist[u] + length[u][w] < dist[w])
{ dist[w] = dist[u] + length[u][w];
path[w] = u; // u is currently the previous vertex //on shortest path to w
}
```
---
### 11. 實作任意兩點間最短路徑的程式。
```cpp=
# include <iostream>
using namespace std;
int main ()
{ int n,w[100][100],A[100][100],a,b;
cin>>n;
for(int i=0;i<n;i++)
{ for(int j=0;j<n;j++) cin>>w[i][j];
}
for(int i=0;i<n;i++)
{ for(int j=0;j<n;j++) A[i][j] = w[i][j];
}
for(int k=0;k<n;k++)
{ for(int i=0;i<n;i++)
{ for(int j=0;j<n;j++) if(A[i][k]+A[k][j]<A[i][j] && i!=j) A[i][j] = A[k][j]+A[i][k];
}
}
cin>>a>>b;
cout<<A[a][b];
}
```
---
### 13. 給定一個 n 個頂點的完全連通圖形，證明任意兩點間可能擁有的最多路徑數目是 *O*(($n−1$)!)。
令 G = (V, E) 為完備圖 (complete graph)，n = |V|。既是任意兩點，不失一般性，令為點 1 和 2—考量其間的路徑個數。包含邊數為 1 的路徑只有一個（即 (1, 2)）；而包含兩條邊者（起點 1 終點 2 已固定；點 1 不能連到點 2）有 n-2 個可能（每個可能皆可有邊連到點2）；包含三條邊者，有 (n-2)(n-3) 個可能；依此類推，包含 n-1 條邊者，有 (n-2)! 個可能。整理如下表：
| 邊數 | 1 | 2 | 3 | ... | n-3 | n-2 | n-1 |
|-----|---|---|---|-----|-----|-----|-----|
| 可能路徑數 | 1 | n-2 | (n-2)(n-3) | ... | (n-2)(n-3)...3 | (n-2)(n-3)...2 | (n-2)(n-3)...1 |
| 整理 | $\frac{(n-2)!}{(n-2)!}$ | $\frac{(n-2)!}{(n-3)!}$ | $\frac{(n-2)!}{(n-4)!}$ | ... | $\frac{(n-2)!}{2!}$ | $\frac{(n-2)!}{1!}$ | $\frac{(n-2)!}{0!}$ |
所有路徑個數為：
$(n-2)! + \frac{(n-2)!}{1!} + \frac{(n-2)!}{2!} + … + \frac{(n-2)!}{(n-3)!} + 1
= (n-2)! + (n-2)! [1 + \frac{1}{2!} + \frac{1}{3!} + … + \frac{1}{(n-2)!}]$
當 $n$ 趨近於無限大時，$[1 + 1/2! + 1/3!+ … + 1/n!] = e – 1$，而 $e = 2.718$。
於是所有路徑個數為 $c (n-2)! （< (n-1)!）$，其中 c 為常數，故任意兩點間可能擁有的最多路徑數目是 *O*$((n-1)!)$
---
### 15. 設計一個演算法判斷圖形 G 是否為二分圖形，如果 G 是二分圖形則你的演算法應該要傳回該圖的兩個二分集合。證明如果以相鄰串列表示圓形，這個演算法可以在 *O*($n+e$) 的時間內完成，其中 n 是頂點數， e 是邊數。
input:
(1) 以任意一點為起點，令此點為 0
(2) 將此點所有連接之點設為 1
(3) 檢查為 1 的點所連接之點，若為 1 則非雙分圖；否則令為 0
(4) 檢查為 0 的點所連接之點，若為 0 則非雙分圖；否則令為 1
(5) 重複(3)(4)若所有點都檢查過且都符合條件，則為雙分圖
建立一個矩陣 A 存放相鄰串列
建立一個矩陣 label 存放群組組別(0 或 1)
```cpp=
input: G = (V, E)
output: G 是否為二分圖形
select x∊E
X = {x}; Y = V-X
label[x] = 0;
while ( X ∪ Y ≠ V )
{ for ( each x∊X )
for ( each y∊Y where (x, y)∊E and label[y] is undefined)
{ label[y] = 1;
Y = Y ∪ {y};
}
if (no such y) break;
for (each y∊Y)
for (each z∊(V-Y-X) where (y, z)∊E and label[z] is undefined)
{ label[z] = 0;
X = X ∪ {z};
}
if (no such z) break;
}
return (X ∪ Y == V) ? 1 : 0; // 1:G is bipartite; 0:G is NOT
```
---
### 17. 給定一個無向連通圖形 G，所有邊長皆為 1，設計一個函式利用廣先搜尋找出 G 的延展樹。
```cpp=
struct spNode // Adjacent list for spanning tree T
{ int u;
int v;
};
strut spList
{ struct spNode * link;
};
struct spList T[n];
struct edgeNode // Adjacent list for input graph G
{ int u;
int 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 * 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; i<n; i++) visited[i] = 0;
visited[u] = 1;
T[u].link = NULL;
Add_Queue(u);
while (Queue 仍有頂點資料)
{ v = Delete_Queue();
for (p=G[v].edge; p; p=p->next) // 所有與 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; i<n; i++) visited[i] = 0;
visited[u] = 1;
T[u].radius = 0;
T[u].link = NULL;
Add_Queue(u, 0);
while (Queue 仍有頂點資料)
{ (v, level) = Delete_Queue();
for (p=G[v].edge; p; p=p->next) // 所有與 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<n; i++)
{ if ((r=radiusBFSSP(i)) < minSPRadius) minSPRoot = i;
}
return minSPRoot; // minSPRadius 即為 T[minSPRoot].radius
}
```
---
---
## 第七章 排序
---
### 1. 請比較下列排序演算法的異同： <br>   (a) 挑選排序、氣泡排序和插入排序。 <br>   (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. 請說明本章所有排序演算法在輸入數列以下面兩種排序時的表現： <br>   (a) 排序完成 <br>   (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$) |
---
### 5. 請實作不同版本的快速排序法： <br>   (a) 遞迴版 <br>   (b) 利用堆疊和以迴圈控制版 <br>   (c\) 當 left~right 間的資料量少於 10 時，直接用挑選或排序；不必再遞迴呼叫（或 push 入堆疊） <br>   (d) 取一個 0~n−1 的亂數 i，令 target 為 data[i] <br>   (e) 令 target 為 data[0]、data[n/2]和 data[n-1]的中位數。 <br>   並利用題 2 的實驗設計製作圖表，觀察並討論實驗結果。
(a)
```cpp=
# include <iostream>
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<<data[i]<<" ";
cout<<endl;
}
```
(b)
```cpp=
# include <iostream>
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<<data[i]<<" ";
}
cout<<endl;
}
```
(c)
請自行練習。
(d)
```cpp=
# include <cstdlib>
# include <time.h>
# include <iostream>
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<<arr[i]<<" ";
}
int main()
{ int n;
cin>>n;
int arr[100];
for(int i = 0; i<n;i++)
cin>>arr[i];
quickSort(arr, 0, n - 1);
cout<<"Sorted array:";
printArray(arr, n);
return 0;
}
```
---
### 7. 請實作不同版本的堆積排序法： <br>   (a) 用陣列實作最小（大）堆積 <br>   (b) 用鍵結串列實作最小（大）堆積。 <br>   並利用題 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<n)
{ Reverse(list, 0, n-1);
Reverse(list, 0, p-1);
Reverse(list, p, n-1);
}
}
```
*O*($n$)+*O*($p$)+*O*($n-p$) = *O*($n$)
---
Google Drive
Gist
Clipboard
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
