資料結構與演算法勘誤

# 資料結構與演算法第五版(高立512326)勘誤 | 徐熊健 上次更新日期：Nov. 2024, Aug. 2024, July 2024, Feb. 2024, Sep. 2023; 2023, 7, 22/ 2023, 2, 19/2023, 2, 9, (2023/1/26 前者已更正) 若有其他發現，請利用留言功能(頁面右上角圖示) 留下更正或建議，謝謝！ | ![image](https://hackmd.io/_uploads/HyWkDhnZJl.png) | |--|--| | $頁數$ |行數/區段| 錯誤 | 更正 | | --- | --- | -------- |--| | 1-33 | 頁末最後 一段落 | ![image](https://hackmd.io/_uploads/ryEeNn3-Jl.png) | ![image](https://hackmd.io/_uploads/SkJBN2h-1g.png)| | 2-24 | 經驗法則 2-7騎士 巡迴問題 |5$\qquad\qquad$for (0 $\le$ k $\le$ n-1) | 5$\qquad\qquad$for (0 $\le$ k $\le$ 7)| | 2-24 | 經驗法則 2-7騎士 巡迴問題 |15$\qquad\qquad$for (0 $\le$ k $\le$ n-1) | 15$\qquad\qquad$for (0 $\le$ k $\le$ 7)| |3-18 | 7 | CQueue[(front+1)%maxsize]方為環狀佇列 | CQueue[++front%maxsize]方為環狀佇列 | |3-18 | 8 | CQueue[rear%maxsize]則為環狀佇列 | CQueue[++rear%maxsize]則為環狀佇列 | | 3-28 | -6 | 重覆再試已走過的步伐 | 重複再試已走過的步伐| | 4-24 |程式4-6 修正紅框 內容成為 藍框者 | ![image](https://hackmd.io/_uploads/rkN3nYWA1e.png) | ![image](https://hackmd.io/_uploads/HyCypKZCyl.png) | |4-44 | -1 | 以重覆呼叫 | 以重複呼叫 | |5-100|程式5-26| 88 $\qquad$ { temp = InorderAVLSucc(node->rightchild); | 88 $\qquad$ { temp = InorderAVLSucc(node); | | 6-8 | -3 | 相同的邊不得重覆 | 相同的邊不得重複 | | 7-19 | 演算法7-6 | 輸入：data陣列 輸出：排序陣列data...data[i]$\le$data[j] | 輸入：data陣列 輸出：排序陣列data...data[i]$\le$data[j] | ## 資料結構與演算法第四版(高立512326)勘誤 | 徐熊健 上次更新日期：Aug. 2024, July 2024, Feb. 2024, Sep. 2023; 2023, 7, 22/ 2023, 2, 19/2023, 2, 9, (2023/1/26 前者已更正) 若有其他發現，請利用留言功能(頁面右上角圖示) 留下更正或建議，謝謝！ | ![image](https://hackmd.io/_uploads/S195va12a.png) | |--|--| | $頁數$ |行數/區段| 錯誤 | 更正 | | --- | --- | -------- |--| | 2-3 | 程式2-2 下第3行 | 迴圈變數 i（i=0,1,2,3,4）加1亦即1,2,3,4,5； | 迴圈變數 i（i=0、1、2、3、4）加1亦即$\ 1、2、3、4、5$ (註：(1) 紅色"0,1,2,3,4" 字體 courier new 不變，且逗號改為頓號！ (2) 紅色"1,2,3,4,5" 字體由 courier new 改為 Times New Roman，且逗號改為頓號！)| | 2-14 | 2 | 宣告矩陣 $A$ 如下： | 宣告矩陣 A 如下：(註："A" 不須斜體，字體為 courier new。)| | 2-15 | 範例2-7 | 則 $\qquad$ *C* = ![image](https://hackmd.io/_uploads/rJe3M1R5A.png =50%x) |則 $\qquad$$C=A+B=$ ![image](https://hackmd.io/_uploads/rJe3M1R5A.png =30%x) 註："*C* =" 改為 "*C* = A+B ="(字體為 Times New Roman)。| | 2-18 | 演算法2-6 行號6 | ![image](https://hackmd.io/_uploads/r1xJiOi2jA.png) | 紅框中的空格請刪去。| | 2-24 |經驗法則 2-7行號2 | 2$\quad$K[x][y]=1;$\quad$//讀入起始點 | 2$\quad$K[x][y]=1;$\quad$//設定起始點 | | 2-24 |經驗法則 2-7行號4 | ![image](https://hackmd.io/_uploads/SkbAso3j0.png) | 行號4"//"請請加空格 使與行號2的"//"對齊。 | | 2-24 |經驗法則 2-7 | ![image](https://hackmd.io/_uploads/ByOb0inoC.png) | 註：(1) 紅框、橘框中的 n 皆改為 n-1；(2)橘框內的文字請改為 "(0$\le$tx$\le$n-1 && 0$\le$ty$\le$n-1)" (刪去"$\le$"前後的空格，以防此行 佔兩行。) | | 2-27 | 2 | 可描繪如圖 2-13。其中... | 可描繪如圖 2-13；其中... | | 4-12 | 圖4-7 | ![image](https://hackmd.io/_uploads/Sy2CkhTj0.png) | 將紅框中的 "[s1]" 刪去。 |； | 4-12 | 9 | 將 x->next 改為 q（原來的 p->next） | 將 x->next 改為 p->next|； |4-49 | 3 | 的精髓（矩陣中... | 的精髓（此處矩陣中... | | 6-13 | 圖6-13 | ![image](https://hackmd.io/_uploads/By1Y5ppo0.png) | 紅框內 "C2" 文字請刪除。| | 6-40 | 演算法 6-7，輸入 | 輸入：... 相鄰矩陣 或相鄰串列 *E* | 輸入：... 相鄰矩陣 *E* (註：刪去"或相鄰串列"。) | | 6-53 | 演算法 6-8，輸入 | 輸入：... 相鄰矩陣 或相鄰串列 *E* | 輸入：... 相鄰矩陣 *E* (註：刪去"或相鄰串列"。) | | 6-57 | 本頁第二段 與演算法6-9 | 本頁第二段與演算法6-9多處重新描述與改寫！ | 請見附檔 06_p6-57.doc；其中更新處標記藍色，並有進行排版；更新前後皆為p.6-57，頁數不變 (可見06_p6-57.pdf)。可以直接複製檔案06_p6-57.doc 的藍色文句後貼入成果檔中！ | |6-59 |演算法6-10 | ![image](https://hackmd.io/_uploads/S1YP4GRiC.png =93%x)|(1) "起點" 該行請向左對齊； (2)行號4 "r" 前請加空格使與上 "(" 對齊。 | | 7-31 | 演算法 7-10| ![image](https://hackmd.io/_uploads/rkg29P32oR.png =93%x) | 行號10的左側請與藍色虛線對齊。 | | 7-32 | 5 | 數字 i 在排列後的排位（或排序陣列中的註標） | 數字 i 在排序後的排位（或排序陣列B中的註標） (註："B"字體為 Courier new)| |7-33 | 1-3 | ![image](https://hackmd.io/_uploads/Hk0Mjnni0.png)| 紅框內字體應為 Courier new；無標記者請維持原樣。(亦可參考之前寄出的 07_sjshyu.doc)| | 7-33 | 4-6 | ![image](https://hackmd.io/_uploads/B1e2nh2j0.png) | 紅框內字體應為 Courier new；無標記者請維持原樣。(亦可參考之前寄出的 07_sjshyu.doc)| | $頁數$ |行數/區段| 錯誤 | 更正 | | --- | --- | -------- |--| | 1-13 |註脚6 行1 | 即 調程式碼應同時 | 即强調程式碼應同時 (註："强"因字體關係 未能正確顯示，可以換字體、亦可用"強")| | 2-3 | 程式2-2 下第3行 | 迴圈變數 i（i=0,1,2,3,4）加1亦即1,2,3,4,5； | 迴圈變數 i（i=0、1、2、3、4）加1亦即$\ 1、2、3、4、5$ (註：(1) 紅色"0,1,2,3,4" 字體 courier new 不變，且逗號改為頓號！ (2) 紅色"1,2,3,4,5" 字體由 courier new 改為 Times New Roman，且逗號改為頓號！)| | 2-9 | 7(範例2-4下1行) | 資料：9、8、4、7、2、3，... | 資料：$9、8、4、7、2、3$，... (註：字體由 courier new 改為 Times New Roman，頓號不變。)| | 2-14 | 4 | ![image](https://hackmd.io/_uploads/H1et7NEsC.png) | (1) 紅框一內斜體A改為不斜體，字體由 Times New Roman courier new 改為 courier new; (2) 紅框二內斜體A、i、j 字型改為標準(不斜體)，字體依然為 courier new。| | 2-15 | 範例2-7 | *C*![image](https://hackmd.io/_uploads/SkFWmyAq0.png =90%x) |*C* = ![image](https://hackmd.io/_uploads/rJe3M1R5A.png =60%x) = 註：(1) 紅框一"*C*" 改為 "*C* = "(字體依舊為 Times New Roman)； (2) 紅框二中"="請往右移(大約兩~三格)。| | 2-16 | 7 | ![image](https://hackmd.io/_uploads/ryehE1A9C.png =120%x) | 註：請將"n-1"中的"-"，改為其前 "m-1"中的"-" (字體為 Symbol)。| | 2-17 |演算法2-5行號1 | ![image](https://hackmd.io/_uploads/HyA8D1CcA.png) | 註：紅框中的 j, j(下標), i, i(下標) 分別改為 k, k(下標), k, k(下標)。 | | 2-19 |程式2-5 行號7 | // cerr$\quad$ 調錯誤訊 息的輸出，作用與 cout 同 | // cerr 强調錯誤訊 息的輸出，作用與 cout 同 (註："强"因字體關係未能正確顯示，可以換字體、亦可用"強")| | 2-19 |程式2-5 行號9,10 | ![image](https://hackmd.io/_uploads/SJa_WS1oC.png) | 註：紅框中的 "," 請改為 ";" 。 | | 2-24 |經驗法則2-7 | ![image](https://hackmd.io/_uploads/H1yysJ090.png) | 註：(1) 紅框中的 7 皆改為 n；(2)紫框內的文字請刪去。 | | 2-24 |經驗法則2-7 | ![image](https://hackmd.io/_uploads/rJBFsJRqR.png) | 註：紅框中的 7 皆改為 n。 | | 2-27 | 2 | 在記憶體中的配置位置，... | 在記憶體中的配置空間A，... (註：A的字體為 Courier new。)| | 2-27 | 3 | 憶體中的位址為 | 憶體A[i]中的位址為 (註："A[i]"的字體為 Courier new。)| | 2-27 | -7 | ...組（16 位元佔 2 個位元組）| ...組（16 位元電腦僅佔 2 個位元組） (註：加入"電腦僅"三字。)| | 3-30 | 演算法3-1 | 輸入：迷宮，以二維陣列...出口在(m,p)。 | 輸入：迷宮—以二維陣列...出口在(m,p) (註：(1)逗號改為破折號；(2) 省略句號。)| | 3-33 | 程式3-15 | 39$\quad$輸出：”此迷宮無出路” | 39$\quad$//輸出：”此迷宮無出路” (註：加入"//"。) | | 3-33 | 2 | 第 20 行用了 d<=NW | 第 21 行用了 d<=NW | | 3-33 | 4 | 第 25 行的 step.dir=d+1 | 第 26 行的 step.dir=d+1 | | 3-33 | 5 | （之後 18~19 行 pop 出 | （之後 19~20 行 pop 出| | 3-33 |6 | —在第 28~29 行中輸出 | —在第 29~30 行中輸出 | | 3-33 | 8 | 第 2 行中堆疊的大小宣告為$m×p$，這...的上限值，這是把直覺 | 第 2、13 行中堆疊的大小動態宣告為$m×p$ （使用後於31或40行回收），這...的上限值—將直覺 | | 3-33 | 10 | 的上限值。堆疊使用的實際 最差狀況可... | 的上限值。實際上堆疊使用的 最佳和最差狀況可... | | 3-37 | 5 | 選用包含二維陣列的 x-y | 選用包含二維陣列的 x-y (字體由 Times New Roman 改為 Courier new ) | | 3-38 | 1 | 第 6 行判斷 | 第 6 行判斷 (字體由 Times New Roman 改為 Courier new )| | 3-38 | -1 |並改寫第 6 為 | 並改寫第 6 為 (字體由 Times New Roman 改為 Courier new )| | 3-46 | 3 | 識別字元 # 且令 q(#)...—此 # 可使第 | 識別字元 # 且令 q(#)...—此 # 可使第 (字體由 Times New Roman 改為 Courier new ；與前者"#"相同。)| | 4-13 |程式4-3 下一行 | 有了程式 4-3 的定義| 有了程式 $4-3$ 的定義 (字體由 Courier new 改為 Times New Roman。)| | 4-14 | 程式4-4 前兩行 | $\quad$請留意...下面的程序 可完成這個需求。 | 請留意 ... 下面的程序可完成 這些檢測與需求。 (註：此段與上段為同一段，不必因跳行而縮排。)| | 4-19 | 行-3 | 更新 first 為原最後節點， | 更新 first 為最後節點s， (註：(1)刪除"原"；(2)加入"s"，字體為Courier new。) | |4-47 | -7~-6 | 而本節介紹二維串列的架構來 存放，這些非 0 值對二維矩 陣的運算（如：矩陣相加、相乘）大抵會比較方便。 | 在此介紹以二維串列的架構來 存放稀疏矩陣，既有節省空間 的好處，對二維矩陣的 運算（如：矩陣相加、相乘）也比用一維串列更為直覺與方便。| |4-48 | 2-3 | ...如此繪製僅為方便後續 畫出稀疏矩陣如圖4-32，但各指標欄位實體空間的 大小是相同的！ | ...如此繪製僅為方便後續 畫出稀疏矩陣如圖4-32。 (註：紅色文字刪除、句末有句號。)| |4-48 | 4 | 圖 4-32 描繪了一個 稀疏矩陣與其對應串列的範例 | 圖 4-32 描繪了一個 以二維串列表示稀疏矩陣的範例 | |4-48 | 6 | (1) 矩陣的開頭空白節點 | (1) 二維串列的開頭空白節點 | |4-48 | -1 | 指向矩陣的開頭空白節點。 | 指向稀疏矩陣的開頭空白節點。對一個 $m\times n$ 含有 $k$ 個非 $0$ 元素的稀疏矩陣而言，以二維陣列 儲存的空間需求為 $O(mn)$，而以二維串列存放則為 $O(n+m+k)$。 (註：段尾加入藍色文字，變數字體為 Times New Roman。)| |4-49 | 1-2 | 串列、稀疏矩陣、甚至於是稀疏多維矩陣、…等結構，都有節省空間的優點，讀者宜掌握儲存必要資料的精髓（非必要者毋須儲存）；至於其輸入... | 稀疏矩陣（二維、甚至於是多維）， 可用串列（二維、或多維）存放，以收節省空間之效；讀者宜掌握 儲存必要資料於串列節點中的精髓（矩陣中的元素 0 即為非必要者）。至於其輸入...| |4-49 | 圖4-32 標題 | 稀疏矩陣的例子 | 以二維串列表示稀疏矩陣的例子 | | 5-6 |註脚3 行3 | 無根樹較為 調點之 間的連結關係 | 無根樹較為强調點之 間的連結關係 (註："强"因字體關係未能正確顯示，可以換字體、亦可用"強")| | 5-6 |註脚4 行1 | ...習慣的畫法，當然... | ...習慣的畫法；當然... (註：逗號改為句號)| |5-88 | -2 | - height(x->rightchild); |- height(p->rightchild); | |5-89 | 程式5-23 | ![image](https://hackmd.io/_uploads/rkb-13us0.png) |紅框中的空格請刪除 | |5-106 | 演算法5-2 | ![image](https://hackmd.io/_uploads/ryfiCACqA.png) | (1)刪除行號5下一行的句號(紅雙刪除線)； (2)加入藍色文字於行號6的下一行： ![image](https://hackmd.io/_uploads/SyVEekyoC.png =93%x)| |5-107 | 圖5-56 | 圖5-56(a)、(b)品質不佳 | 請參用05-p106-p107.doc 的圖5-56(a)、(b)；輸出如~.pdf。兩圖的相對大小可參考之。| | 6-59 | 演算法 6-10| 輸入：... 演算法 6-8或6-9所得出的 頂點連接矩陣 *C* | 輸入：... 演算法6-8 或6-9所得出的頂點 連接陣列 *C* | | 6-83 | -3 | .count 則記錄了 i 所有直接 | .count 則記錄了 頂點 i 所有直接| | 7-12 | 演算法 7-3| ![image](https://hackmd.io/_uploads/BkVaFgwiC.png) | 行號6紅框處共兩個空格，請取代為一個空格。 | | 7-12 | 演算法 7-3| ![image](https://hackmd.io/_uploads/BkXcq11sC.png) | 行號7、8紅框處請各多加入二個 空格(比照行號4)。 | | 7-30~ 7-34 | 7.2.7 計數排序法 | 本小節多處重新描述；含新增、刪除、改寫字句、加入演算法7-10的諸多程式註解！ | 請見附檔 07_sjshyu.doc；其中更新處標記藍色，並有進行排版；更新前後皆為7-30~7-34，頁數不變(可見07-30_34.pdf)。可以直接複製檔案的 p.7-30~p.7-34 後貼入成果檔中！ | 以下僅供參考。 | $頁數$ |行數/區段| 錯誤 | 更正 | | --- | --- | -------- |--| | 7-30 | 5 | 小到大的排序數列中應排在第 31（或 32，如果有 2 個 11）個位置。|小到大的排序數列中應排在第 31（或 32，如果它是第 2 個 11）個位置。 | | 7-30 |9-10 | 7 的排名位置為 1~2、8 的排位應為 3~5、而 9 則為 6|小到大的排序數列中應排在第 31（或 32，如果它是第 2 個 11）個位置。 | | 7-31 | 演算法 7-10| ![image](https://hackmd.io/_uploads/BJPe6lkjR.png) | 行號10的左側請與藍色虛線對齊。 | | 7-32 | 範例7-8下一行|...後的結果-前綴和後 | 後的結果—前綴和後 請改成破折號！| | 7-32 | 範例 7-8|![image](https://hackmd.io/_uploads/SyjSLQkoR.png) | 紅框內的 9 9 9 10 請改成藍框內的 10 10 10 11。 | | 7-33 | 範例 7-8|![image](https://hackmd.io/_uploads/BkIcv7koC.png) | 紅框內的 9 9 9 10 請改成如上藍框內的 10 10 10 11。 | 下面的程序 ### 2024/07/21 以前 | $頁數$ |行數/區段| 錯誤 | 更正 | | --- | --- | -------- |--| | 1-18 | 程式1-5 | ![image](https://hackmd.io/_uploads/HJVqkYSFa.png) |![image](https://hackmd.io/_uploads/S13L1FHK6.png) | | 2-4 |程式2-2 標題 | ... 對應元素相加 | ... 對應元素相乘 | | 2-19 |程式2-5 | 6$\quad$ ... $\quad$ "輸入方塊過大或小... | 6$\quad$ ... $\quad$ "輸入方陣過大或小... | | 2-19 |程式2-5 | 8$\quad$ ... $\quad$ "輸入方塊邊長... | 6$\quad$ ... $\quad$ "輸入方陣邊長... | | 2-24 |經驗法則2-7 | 輸出： ... 以 1~64的編號 | 輸出： ... 以 1~n*n的編號 | | 2-24 |經驗法則2-7 | 23$\quad${$\quad$if (next_moves[t] < next_moves[min]) | 23$\quad${$\quad$if (next_move[t] < next_move[min]) | | 2-25 |8 | ... 令其為 next_moves[min]) | ... 令其為 next_move[min]) | | 2-27 | 1 | ... 的起點為 $\alpha$ | ... 的起始位址為 $\alpha$ | | 2-31 |圖2-18 $\text{(c)}$|![image](https://hackmd.io/_uploads/r1uGF5Fd6.png) | ![image](https://hackmd.io/_uploads/Hygwc5Yd6.png) | | 3-5 | 範例3-3下一行 | ...的例子 | ...的例子，如圖3-3。 | | 3-5 | 圖3-3(a) | ![image](https://hackmd.io/_uploads/ry2C8uBuA.png) | 請刪去紅框中的Label1 | | 3-5 | 圖3-3(b) | ![image](https://hackmd.io/_uploads/BkiNcdHuC.png =70%x) | ![image](https://hackmd.io/_uploads/SkewFq_H_A.png =70%x) | | 3-30 | 演算法3-1 | 輸入：...表示。 | 輸入：...表示，大小為 m*p；入口在 (1, 1)、出口在 (m, p) | | 3-30 | 演算法3-1 | 輸出：...的路徑。 | 輸出：...的路徑 (省略"。")| | 3-32 | 程式3-15 | 2 $\quad$ struct position Stack[m*p]; | 2 $\quad$ struct position * Stack; | | 3-32 | 程式3-15 | 12$\quad${$\quad$ struct position step; | 12$\quad${$\quad$ struct position step; 13$\quad \quad$ Stack = new struct position [m*p]; (註：12行s~ 與 13行S~ 請對齊) | | 3-32 | 程式3-15 | 行號 13-29 | 行號 14-30 | | 3-32 | 程式3-15 | 30$\quad\quad$return; | 31$\quad\quad$delete [] Stack; 32$\quad\quad$return; | | 3-32 | 程式3-15 | 行號 31-37 | 行號 33-39 | | 3-32 | 程式3-15 | 37$\quad\quad$//輸出：”此迷宮無出路” 38$\;\;$} | 39$\quad\quad$輸出：”此迷宮無出路”； 40 $\ \ \quad$ delete [] Stack; 41 $\;\;$} | | 3-51 | 演算法3-5 |22 $\quad$while (x=pop() != “#”) output(x); | 22 $\quad$while (x=pop() != “#”) push_opn(get_prefix(x)); | | 4-12 | -4~-2 | ![image](https://hackmd.io/_uploads/HyQCppN_0.png =100%x) | ...包括 3 個鏈結的異動。事實上 (2) 和 (3) 可同時完成（如程式 4-3 所示）。我們還得考慮 p 為 NULL 的情形，亦即整個串列是空的(程式中 p->next 在 p 是 NULL 時會中斷執行)！ 此時 ... (註：此兩段請合併，加入"亦即整個...中斷執行)！"程式碼字體是 courier new。)| | 4-14 | 程式4-4前一行 | 下面的程序... | 請留意 p 甚至於 p->next 有可能是 NULL 的情形！ 下面的程序... (註：程式碼字體是 courier new。)| | 4-19 | 行-7 | s->link 應為 NULL（它本是...最後節點），此時 r 應為 | s->link 應為 NULL（它本是...最後節點），此時 t 應為 (註：NULL/t 字體皆是 courier new。)| | 4-19 | 行-4 | 由圖 14 \(c)-(e) 可知 ... 順勢平移（見圖 14 (f)） | 由圖 14-11 \(c)-(e) 可知 ... 順勢平移（見圖 14-11 (f)）| | 4-19 | 行-3 | s-link，各節點... | s-link (設之為t)，各節點... (註：(、) 是全形括號、 t 字體是 courier new。)| | 4-21 | 行1 | t、s、r 的處理， | t、s、r 的處理(見圖4-11 (f))， (註：外層括號(、) 是全形、"(f)" 則是半形。)| | 4-21 | 行2 | (s->link = t;)； | (s->link = t;)(見圖 \(c))； (註：外層括號(、) 是全形、"\(c)" 則是半形。)| | 4-21 | 行3 | 屆時 r 必為 NULL！ | 屆時 r 必為 NULL(見圖 (e))； (註：外層括號(、) 是全形、"(e)" 則是半形。)| | 4-21 | 行3 | 初始化指標 r、s （見圖11 (f)） | 初始化指標 r、s (註：刪除之)| | 4-21 | 行4 | ... 態（比較圖 11 (d)、(f)） | ... 態（比較圖 (d)、(f)） (註：刪除之)| | 4-23 | 程式 4-10，行號17 | 17$\qquad$if (top == NULL) top = x; | 17$\qquad$if (top == NULL) top = x;$\qquad$// 17、18行非必要，可省略；解釋於後 (註：加在行末)| | 4-40 | 程式4-18 | 37$\quad$while (p!=head_a && p!=head_b)| 37$\quad$while (p!=head_a && q!=head_b)| | 4-41 | 註腳19，行2-3 | $\quad$ $\quad$x = NewTerm(coef, expo); InsertLast(x, last_a);| x = NewTerm(coef, expo); InsertLast(x, last_a); (註：此兩行左緣對齊)| | 4-44 | 7-8 | A(x) = -4x²+1 B(x) = 4x³-9x²+2x-3 | A(x) = 3x²+1 B(x) = 6x³+9x²+2x-3 | | 4-44 | 圖4-30 | ![image](https://hackmd.io/_uploads/rkuqGY1hT.png =95%x) | ![image](https://hackmd.io/_uploads/Sy1HztJnT.png =80%x)| |4-48 | 1-2 | 並不完全相同（如此繪製 僅為方便後續畫出 稀疏矩陣如圖4-32），但各指標欄位實體 空間的大小是相同的！ | 並不完全相同 （例如： row和col是整數、value可能是整數 或其它、down和 right則是節點指標)，如此繪製僅為方便 後續畫出稀疏矩陣 如圖4-32。[註： 上列 row, col, value, down 和 right 的字型 請用 courier new] | |4-66 | 第5題，行-1 | $x_n, y_n, y_{n+1},$ $x$$_{n+2}, ... ,y_m$ | $x_n, y_n, y_{n+1},$ $y$$_{n+2}, ... ,y_m$ | |5-88 | 程式5-2，行8 | AVLRoot | AVLRoot; | | 6-11 | 行6 | 除了起點和終點可能 相同外，其它的頂點 皆不同的路徑。 | 除了起點和終點可能相同（該點走訪恰兩次）外，其它的頂點皆不同（走訪僅一次）的路徑。 | | 6-52 | 行-1 | ...即可得解。 | ...即可得解。為求出最短路徑，可加入「頂點連接陣列」*C*，容後解釋。 | | 6-53 | 演算法 6-8，輸出 | 輸出：*G* 中 *u* 到 *v* 的最短距離，*v*∈*V*，*v*≠*u* | 輸出：*G* 中 *u* 到 *v* 的最短距離*D*[*v*]，*v*∈*V*，*v*≠*u*；頂點連接陣列*C* | | 6-53 | 演算法 6-8，輸出、行1-5 |![image](https://hackmd.io/_uploads/Hk3g_p7dA.png =90%x) | ![image](https://hackmd.io/_uploads/rkMk40XuA.png =80%x) | | 6-57 | 行8 | 倘若用空間 *O*(*n*+*e*) 的相鄰串列 | 亦可用空間 *O*(*n*+*e*) 的相鄰串列 | | 6-57 | 演算法 6-9，輸入 | 輸入：...，相鄰串列*E*，... | 輸入：...，相鄰串列或矩陣*E*， | | 6-57 | 演算法 6-9，輸出 | 輸出：*u* 到 *v* 的最短距離，*v*∈*V*，*v*≠*u* | 輸出：*G* 中 *u* 到 *v* 的最短距離*D*[*v*]，*v*∈*V*，*v*≠*u*；頂點連接陣列*C* | | 6-59 | 演算法 6-10，輸入第2行 | 輸入：... 演算法6-8所得出的頂點 連接矩陣 *C* | 輸入：... 演算法6-8 或6-9 所得出的頂點 連接陣列 *C* | | 6-59 | 演算法 6-10，行號2 | // *toString*(*v*) 將 *v* 轉成字元資料型態 | // *toString*(*v*) 將整數 *v* 轉成字元資料型態 | |6-67 | 圖 6-41 | ![image](https://hackmd.io/_uploads/H14yxm4dA.png =100%x) | ![image](https://hackmd.io/_uploads/H1uvk7EOA.png =90%x) 註：去除分隔垂直線 | |6-83 | 程式6-5 行號65、66 | ![image](https://hackmd.io/_uploads/ry157XEOC.png =90%x) | ![image](https://hackmd.io/_uploads/B1NgNmEOR.png =90%x) 註：65行 "p->"之前加一空格，使與65行向左對齊 | | 7-52 | 第7題 | (b) 用鍵結串列實作最小（大）堆積 | (b) 用鏈結串列實作最小（大）堆積 | # -- 以下皆為備份資訊 -- ## 第四版 (2023/9 後) | $頁數$ |行數/區段| 錯誤 | 更正 | | --- | --- | -------- |--| | 1-18 | 程式1-5 | ![image](https://hackmd.io/_uploads/HJVqkYSFa.png =70%x) |![image](https://hackmd.io/_uploads/S13L1FHK6.png =50%x) | | 2-4 |程式2-2 標題 | ... 對應元素相加 | ... 對應元素相乘 | | 2-19 |程式2-5 | 6$\quad$ ... $\quad$ "輸入方塊過大或小... | 6$\quad$ ... $\quad$ "輸入方陣過大或小... | | 2-19 |程式2-5 | 8$\quad$ ... $\quad$ "輸入方塊邊長... | 6$\quad$ ... $\quad$ "輸入方陣邊長... | | 2-24 |經驗法則2-7 | 輸出： ... 以 1~64的編號 | 輸出： ... 以 1~n*n的編號 | | 2-24 |經驗法則2-7 | 23$\quad${$\quad$if (next_moves[t] < next_moves[min]) | 23$\quad${$\quad$if (next_move[t] < next_move[min]) | | 2-25 |8 | ... 令其為 next_moves[min]) | ... 令其為 next_move[min]) | | 2-27 | 1 | ... 的起點為 $\alpha$ | ... 的起始位址為 $\alpha$ | | 2-31 |圖2-18 $\text{(c)}$|![image](https://hackmd.io/_uploads/r1uGF5Fd6.png =90%x) | ![image](https://hackmd.io/_uploads/Hygwc5Yd6.png =50%x) | | 3-5 | 範例3-3下一行 | ...的例子 | ...的例子，如圖3-3。 | | 3-5 | 圖3-3(a) | ![image](https://hackmd.io/_uploads/ry2C8uBuA.png =70%x) | 請刪去紅框中的Label1 | | 3-5 | 圖3-3(b) | ![image](https://hackmd.io/_uploads/BkiNcdHuC.png =60%x) | ![image](https://hackmd.io/_uploads/SkewFq_H_A.png =60%x) | | 3-30 | 演算法3-1 | 輸入：...表示。 | 輸入：...表示，大小為 m*p；入口在 (1, 1)、出口在 (m, p) | | 3-30 | 演算法3-1 | 輸出：...的路徑。 | 輸出：...的路徑 (省略"。")| | 3-32 | 程式3-15 | 2 $\quad$ struct position Stack[m*p]; | 2 $\quad$ struct position * Stack; | | 3-32 | 程式3-15 | 12$\quad${$\quad$ struct position step; | 12$\quad${$\quad$ struct position step; 13$\quad \quad$ Stack = new struct position [m*p]; (註：12行s~ 與 13行S~ 請對齊) | | 3-32 | 程式3-15 | 行號 13-29 | 行號 14-30 | | 3-32 | 程式3-15 | 30$\quad\quad$return; | 31$\quad\quad$delete [] Stack; 32$\quad\quad$return; | | 3-32 | 程式3-15 | 行號 31-37 | 行號 33-39 | | 3-32 | 程式3-15 | 37$\quad\quad$//輸出：”此迷宮無出路” 38$\;\;$} | 39$\quad\quad$輸出：”此迷宮無出路”； 40 $\ \ \quad$ delete [] Stack; 41 $\;\;$} | | 3-51 | 演算法3-5 |22 $\quad$while (x=pop() != “#”) output(x); | 22 $\quad$while (x=pop() != “#”) push_opn(get_prefix(x)); | | 4-12 | -4~-2 | ![image](https://hackmd.io/_uploads/HyQCppN_0.png =90%x) | ...包括 3 個鏈結的異動。事實上 (2) 和 (3) 可同時完成（如程式 4-3 所示）。我們還得考慮 p 為 NULL 的情形，亦即整個串列是空的(程式中 p->next 在 p 是 NULL 時會中斷執行)！ 此時 ... (註：此兩段請合併，加入"亦即整個串列是空的(程式中 p->next 在 p 是 NULL 時會中斷執行)！"程式碼字體是 courier new。)| | 4-14 | 程式4-4前一行 | 下面的程序可完成這個需求。 | 請留意 p 甚至於 p->next 有可能是 NULL 的情形！ 下面的程序... (註：程式碼字體是 courier new。)| | 4-19 | 行-7 | s->link 應為 NULL（它本是第一節點，反向後則成最後節點），此時 r 應為 | s->link 應為 NULL（它本是第一節點，反向後則成最後節點），此時 t 應為 (註：NULL/t 字體皆是 courier new。)| | 4-19 | 行-4 | 由圖 14 \(c)-(e) 可知 ... 順勢平移（見圖 14 (f)） | 由圖 14-11 \(c)-(e) 可知 ... 順勢平移（見圖 14-11 (f)）| | 4-19 | 行-3 | s-link，各節點... | s-link (設之為t)，各節點... (註：(、) 是全形括號、 t 字體是 courier new。)| | 4-21 | 行1 | t、s、r 的處理， | t、s、r 的處理(見圖4-11 (f))， (註：外層括號(、) 是全形、"(f)" 則是半形。)| | 4-21 | 行2 | (s->link = t;)； | (s->link = t;)(見圖 \(c))； (註：外層括號(、) 是全形、"\(c)" 則是半形。)| | 4-21 | 行3 | 屆時 r 必為 NULL！ | 屆時 r 必為 NULL(見圖 (e))； (註：外層括號(、) 是全形、"(e)" 則是半形。)| | 4-21 | 行3 | 初始化指標 r、s （見圖11 (f)） | 初始化指標 r、s (註：刪除之)| | 4-21 | 行4 | ... 態（比較圖 11 (d)、(f)） | ... 態（比較圖 (d)、(f)） (註：刪除之)| | 4-23 | 程式 4-10，行號17 | 17$\qquad$if (top ++ NULL) top = x; | 17$\qquad$if (top ++ NULL) top = x;$\qquad$// 17、18行非必要，可省略；解釋於後 (註：加在行末)| | 4-40 | 程式4-18 | 37$\quad$while (p!=head_a && p!=head_b)| 37$\quad$while (p!=head_a && q!=head_b)| | 4-41 | 註腳19，行2-3 | $\quad$ $\quad$x = NewTerm(coef, expo); InsertLast(x, last_a);| x = NewTerm(coef, expo); InsertLast(x, last_a); (註：此兩行左緣對齊)| | 4-44 | 7-8 | A(x) = -4x²+1 B(x) = 4x³-9x²+2x-3 | A(x) = 3x²+1 B(x) = 6x³+9x²+2x-3 | | 4-44 | 圖4-30 | ![image](https://hackmd.io/_uploads/rkuqGY1hT.png =90%x) | ![image](https://hackmd.io/_uploads/Sy1HztJnT.png =60%x)| |4-48 | 1-2 | 並不完全相同（如此繪製僅為方便後續畫出稀疏矩陣如圖4-32），但各指標欄位實體空間的大小是相同的！ | 並不完全相同（例如：row和col是整數、value可能是整數或其它、down和right則是節點指標)，如此繪製僅為方便後續畫出稀疏矩陣如圖4-32。 [註：上列 row, col, value, down 和 right 的字型請用 courier new] | |4-66 | 第5題，行-1 | $x_n, y_n, y_{n+1},$ $x$$_{n+2}, ... ,y_m$ | $x_n, y_n, y_{n+1},$ $y$$_{n+2}, ... ,y_m$ | |5-88 | 程式5-2，行8 | AVLRoot | AVLRoot; | | 6-11 | 行6 | 除了起點和終點可能相同外，其它的頂點皆不同的路徑。 | 除了起點和終點可能相同（該點走訪恰兩次）外，其它的頂點皆不同（走訪僅一次）的路徑。 | | 6-52 | 行-1 | ...即可得解。 | ...即可得解。為求出最短路徑，可加入「頂點連接陣列」*C*，容後解釋。 | | 6-53 | 演算法 6-8，輸出 | 輸出：*G* 中 *u* 到 *v* 的最短距離，*v*∈*V*，*v*≠*u* | 輸出：*G* 中 *u* 到 *v* 的最短距離*D*[*v*]，*v*∈*V*，*v*≠*u*；頂點連接陣列*C* | | 6-53 | 演算法 6-8，輸出、行1-5 |![image](https://hackmd.io/_uploads/Hk3g_p7dA.png =90%x) | ![image](https://hackmd.io/_uploads/rkMk40XuA.png =80%x)| | 6-57 | 行8 | 倘若用空間 *O*(*n*+*e*) 的相鄰串列 | 亦可用空間 *O*(*n*+*e*) 的相鄰串列 | | 6-57 | 演算法 6-9，輸入 | 輸入：...，相鄰串列*E*，... | 輸入：...，相鄰串列或矩陣*E*， | | 6-57 | 演算法 6-9，輸出 | 輸出：*u* 到 *v* 的最短距離，*v*∈*V*，*v*≠*u* | 輸出：*G* 中 *u* 到 *v* 的最短距離*D*[*v*]，*v*∈*V*，*v*≠*u*；頂點連接陣列*C* | | 6-59 | 演算法 6-10，輸入第2行 | 輸入：... 演算法6-8所得出的頂點連接矩陣 *C* | 輸入：... 演算法6-8或6-9 所得出的頂點連接陣列 *C* | | 6-59 | 演算法 6-10，行號2 | // *toString*(*v*) 將 *v* 轉成字元資料型態 | // *toString*(*v*) 將整數 *v* 轉成字元資料型態 | |6-67 | 圖 6-41 | ![image](https://hackmd.io/_uploads/H14yxm4dA.png =90%x) | ![image](https://hackmd.io/_uploads/H1uvk7EOA.png =70%x) 註：去除分隔垂直線 | |6-83 | 程式6-5 行號65、66 | ![image](https://hackmd.io/_uploads/ry157XEOC.png =90%x) | ![image](https://hackmd.io/_uploads/B1NgNmEOR.png =60%x) 註：65行 "p->"之前加一空格 | | 7-52 | 第7題 | (b) 用鍵結串列實作最小（大）堆積 | 用鏈結串列實作最小（大）堆積 | #### [以下僅供參考，毋庸修改] | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| | 4-23 | 程式4-10 | 16$\quad\quad$x = NewNode(element); 17$\quad\quad$if (top == NULL) top = x; 18$\quad\quad$else 19$\quad\quad${$\quad$ x->link = top; 20$\quad$ $\quad\quad$ top = x; 21$\quad\quad$}| 16$\quad\quad$x = NewNode(element); 17$\quad\quad$x->link = top; 18$\quad$$\quad$top = x; | | 4-24 | 程式4-10 | 行號 22-35 | 行號 19-32 | ## 修訂第三版 (2023/2/14 ~ 2023/9) | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| |1-3| 第3段第2行 | 與演算法之間確實有緊密結合的關係 | 與演算法之間確實有緊密結合的關係$^\color{green}1$ (插入註脚1如下) 1 瑞士計算機學家 Niklaus Emil Wirth 寫過名為Algorithms + Data Structures = Programs 的鉅著，顯見資料結構與演算法唇齒相依、相輔相成的關係。Wirth 教授因在程式語言設計上的貢獻，於1984年獲頒圖靈獎 (Turing Award)。 (其它註脚編號依序遞增)| |1-4 | 註脚3第3行 | 作者認為 C++或Java (C++ Builder 或J Builder) 也是 | 作者認為C++、Java（視窗化的C++ Builder、J Builder）或Python 也是) | |1-4 | 註脚3第4-5行 | 放在資料結構本身上，降低因物件導向設計或視窗程式設計的引入 | 放在深耕資料結構本身上，降低因物件導向設計、視窗程式設計或各類函式庫的引入 | |1-6 | -1 | 演算法的明確定義 | 演算法明確的定義 | |1-8 | 5 | 以程序 (procedure) 或函數 (function) | 以「程序」 (procedure) 或「函數」 (function) | |1-11 | 1 | 程式1-1第1行定義了一個巨集 (macro) | 程式1-1第1行定義了一個「巨集」 (macro) | |1-11 |7-8 | 第2行參數中的data為欲排序元素所在的整數陣列 | 第2行程序selectionSort的參數data[]為欲排序元素所在的整數陣列 | |1-11 |10 | 並記得測試足量的資料。 | 並務必測試足量的資料。程式1-2 是個實作的結果—仍有修繕優化的空間，但已可提供驗証和測試的需求。 | |1-11 |10行之後 | 目前無程式1-2 | $\color{green}{(加入程式1-2)}$ | |1-11 |註脚4 | 4 $\quad$ 請留意其定義方式可能因編譯器不同而有所不同 | 5 $\quad$ 請留意：定義方式可能因編譯器不同而有所不同| |1-11~13 |程式1-2之後 | 程式1-2之後 | 程式1-2第2行引用了 time.h，它包含計時型態clock_t（長整數）、計時函數clock()與時間常數CLOCK_PER_SEC，可用來取得處理器執行程式的時間（請見第9、14、16、18行；其中第18行以double型態執行(tx-t0)求算執行selectionSort程序前後的clock間隔數目，將之除以CLOCK_PER_SEC即可取得以秒為單位的執行時間），方便做演算法的效能評估 (performance evaluation)。第5~7行對副程式（程序、函數）genRndData、selectionSort、printData做預先宣告 (prototype declaration)，其正式宣告即可在主程式main()之後詳述，目的是讓檢視程式者可及早讀到主程式，瞭解程式的概觀；此三個副程式也讓整個流程因不同目的而歸納命名，使主程式釋義清晰條理，便於閱讀，提高了可讀性$^6$ (readability) ；還可以重複使用（第17、25行皆呼叫了printData），於是整個程式更加精簡順暢。第23和24行分別有srand(time(NULL)) 和rand()，前者取得當時時間做為隨機亂數種子 (seed) ，後者取得隨機亂數（在此因 % MAX_SIZE，其範圍為0~MAX_SIZE）。請留意：在此的輸入和輸出指令用的是scanf和printf$^7$ 。| |1-1x |程式1-2之後 | 上面所加內文含註脚6 | 6 $\quad$ Donald Knuth提倡的文學程式設計 (literal programming)，即强調程式碼應同時讓編譯器和人看懂！Knuth教授因其在演算法分析、程式語言設計和系列著作The Art of Computer Programming的貢獻，於1974年獲得圖靈獎。| |1-1x |程式1-2之後 | 上面所加內文含註脚7 | 7$\quad$ 習慣用cin和cout指令的讀者，請於程式適當處加入： $\text{# include <iostream>}$ $\\ \mbox{using namespace std;}$ | |1-10 |14 | 對程式碼 再利用 (reuse) 和除錯 (debug) | 對程式碼 「再利用」 (reuse) 和「除錯」 (debug) | |1-12 |12~13 | 程式的流程將在 呼叫程序 (procedure call) | 程式的流程將在 「呼叫程序」 (procedure call) | |1-12 |14 | 的正確性由系統堆疊 (system stack) | 的正確性由「系統堆疊」 (system stack) | |1-13 |-3 | 傳回 n\*X(n-1)。 請看程式1-2。| 傳回 n\*X(n-1)； 請看程式1-3。 | |1-13 |-2 | 整數 n 已為 1 時| 整數 n 已為 0 時 (0 字體為Courier New)| |1-13 |-1 | 回 1 繼續呼叫X(0)是沒有意義 | 回1（亦可定n==1為終結條件；繼續呼叫X(-1)是沒有意義| |1-13 |程式1-2標題 | 程式1-2 | 程式1-3| |1-13 |程式1-2 (行2) | 2$\qquad$ {$\quad$if (n == 1) return 1; | 2$\qquad$ {$\quad$if (n == 0) return 1;| | 2-14 | 演算法2-3 | 4$\qquad$B[j][i]=A[i][j]; | 4$\qquad$B[j][i] = A[i][j]; (等號前後加一空格) | | 2-15 | 演算法2-4 | 輸出：矩陣C ... | 輸出：mxn矩陣C ... | |4-23| 程式4-10 | 9 if (p == null) { ... } | 9 if (p == NULL) { ... } | |4-24| 程式4-10 | 25 if (top == NULL); | 25 if (top == NULL) | |4-35| 程式4-16 | 3 for (p=header->next; (p->data!=target && p!=header); p=p->next) ; | 3 for (p=head->next; (p->data!=target && p!=header); p=p->next) ; | |4-35| 程式4-16 | 3 for (p=header->next; (p->data!=target && p!=header); p=p->next) ; | 3 for (p=header->next; (p->data!=target && p!=head); p=p->next) ; | |4-35| 程式4-16 | 3 for (p=header->next; (p->data!=target && p!=header); p=p->next) ; | 3 for (p=header->next; (p->data!=target && p!=header); p=p->next); (去除空格) | |4-35| 1 | ... p 的初始值是 header->next，... | ... p 的初始值是 head-->next，...| |4-35| 3 | ... (p->data!=target && p!=header)... | ... (p->data!=target && p!=head)... | |4-35| 4 | ...由 p!=header 來確認... | ...由 p!=head 來確認... | |4-35| 5 | ...，至 p==header 則遍訪所有節點）；... | ...，至 p==head 則遍訪所有節點）；... | |4-35| 7 | ...(p->data!=target && p!=header)兩條件順序可以更動，... | ...(p->data!=target && p!=head)兩條件順序可以更動，... | |4-35| 4-16-1 | 3 for (q=first, p= header->next; (p->data!=target && p!=header); q=p, p=p->next); | 3 for (q=first, p=head->next; (p->data!=target && p!=head); q=p, p=p->next); (刪除p= head->next間空格) | |4-35| 4-16-1 | 3 for (q=first, p=header->next; (p->data!=target && p!=header); q=p, p=p->next); | 3 for (q=head, p=head->next; (p->data!=target && p!=head); q=p, p=p->next); | |4-35| 4-16-1 | 4 if (p==header) return -1; | 4 if (p==head) return -1; | |4-36| 1 |(p->data!=target && p!=header)；... | (p->data!=target && p!=head)；... | |4-42| 程式4-18 |62 { struct Polynode *p... | 62 { struct PolyNode *p... | |4-45| 程式4-19 | 1 struct PolyNode * ClearTerm(struct node * head) | 1 struct PolyNode * ClearTerm(struct PolyNode * head) | |4-46| 程式4-19 | 14 last_s_ = AttachLast(z, last_s); | 14 last_s = AttachLast(z, last_s); | |4-57| 程式4-25 | 7 void DeleteHDList(truct Dnode *x) | 7 void DeleteHDList(struct Dnode *x) | |5-5| 圖5-2 (c) | 嘉義、台南之間無權重(票價)値| 139 (自强號票價139)| |5-6| -7 | 「中間節點」（intenal node）。 | 「中間節點」（internal node）。 | |5-15| -2 | 其中$v_1+v_2+...+v_m=$$K$ 。... | 其中$v_1+v_2+...+v_m=$$k$ 。... | |5-31| 圖5-24欄3第10列 | Inorder(C的左子樹指標) | inorder(C的左子樹指標) | |5-32| 圖5-24欄3第3列 | Inorder(D的左子樹指標) | inorder(D的左子樹指標) | |5-32| 圖5-24欄3第6列 | Inorder(E的左子樹指標) | inorder(E的左子樹指標) | |5-32| 圖5-24欄3第7列 | Inorder(-的左子樹指標) | inorder(-的左子樹指標) | |5-33| 6 | Node->data | node->data | |5-35| 程式5-6 | 13 { struct stackNode old_top; | 13 { struct StackNode old_top; | |5-35| 程式5-6 | 23$\quad\quad$StackEmpty(); | 23 $\quad\quad$return NULL; | |5-39| 程式5-6-1 | 51 } // 印入node->data、... | 51 } // 印出node->data、... | |5-39| -4 | (恰為 $LRV$ 的反轉) | (恰為 $LRV$ 的反轉) (字體請與內文同) | |5-40| 程式5-6-2 | 12 void push_data (... | 12 void push_node (... | |5-40| 程式5-6-2 | 13 { struct stackNode *old_top; | 13 { struct StackNode *old_top; | |5-47| -3 | 呼叫copy程序，... | 呼叫Copy程序，... | |5-49| 程式5-10 | 1 ...(struct BTreeNodes * node) | 1 ...(struct BTreeNode * node) | |5-49| 程式5-12 | 5 new->rightthead = p->rightthread; | 5 new->rightthread = p->rightthread; | |5-49| 程式5-12 | 9 p->rightthead = 0; | 9 p->rightthread = 0; | |5-57| -4 | 著名的堆疊排序 | 著名的堆積排序 | |5-59| 程式5-13 | 5 { if (n == maxsize) HeapFull(); | 5 { if (n == maxsize - 1) HeapFull(); | |5-59| -5 | 為x在堆疊中的適當存放位置 | 為x在堆積中的適當存放位置 | |5-60| 圖 5-37 名 | 圖 5-37 最大堆疊的刪除 | 圖 5-37 最大堆積的刪除 | |5-69| 程式5-17-1 | 25 { struct BSTreeNode *p(空格)*q; | 25 { struct BSTreeNode *p, *q; | |5-89| 表5-5第4列 | *w* 在 *p* 左子樹的右子樹內(空格) | *w* 在 *p* 右子樹的右子樹內(空格) | |5-95| 表5-7欄4第4列 | ...右子樹 *T*~2~ 不低於右子樹 *T*~1~... | ...右子樹 *T*~2~ 不低於左子樹 *T*~1~... | | 6-2 | -5 | 早在 1763 年 | 早在 1736 年 | |6-3| 8 | 若且唯若恰有兩個（或沒有）項點 | 若且唯若恰有兩個（或沒有）頂點 |6-5| 圖6-5(c)| (a) | (c) |6-10| 3 | 而 B 相鄰到 A（或從 A 相鄰） | 而 B 相鄰自 A（或從 A 相鄰） | |6-10| 子圖 | 必須滿足 *V'*∈*V* 且 *E'*∈*E*。 | 必須滿足 *V'*⊆*V* 且 *E'*⊆*E*。 | |6-19| 演算法6-1 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1} | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列) | |6-20| 演算法6-2 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1} | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列) | |6-20| 演算法6-2 | 8 for (...即 visted[w] ≠ 1) | 8 for (...即 visited[w] ≠ 1) | |6-21| 演算法6-3 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1} | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列) | |6-22| 演算法6-3 | 13 Add_Queue[w]; | 13 Add_Queue(w); | |6-23| 演算法6-4 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1} | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列) | |6-26| 演算法6-5 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，\| *V* \|=n，\| *E* \|=e | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，\| *V* \|=n，\| *E* \|=e | |6-36| 演算法6-6 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，\| *E* \|=e，... | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，\| *E* \|=e，... | |6-41| 演算法6-6-1 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，\| *E* \|=e，... | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，\| *E* \|=e，... | |6-53| 演算法6-7 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，... | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，... | |6-57| 演算法6-7-1 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，... | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，... | |6-57| -2 | ...建立最小堆疊-以距離短者為優先。... | ...建立最小堆積-以距離短者為優先。... | |6-58| 演算法6-8 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，... | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，... | |6-59| 演算法6-8 | 4 ..."]==>"\|\|r; | 4 ..."]==>"+r; | |6-59| 演算法6-8 | 5 ..."]==>"\|\|r; | 5 ..."]==>"+r; | |6-64| 演算法6-9 | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，... | 輸入：圖形 *G*=(*V*,*E*)，*V*={0,1,2,...,*n*-1}，E(相鄰矩陣 or 相鄰串列)，... | |6-78| -1 | ... AOV[i] = NULL | ... (換行) { AOV[i].arc = NULL; AOV[i].count = 0; (換行) } | |6-79| 程式6-4| 23 if (head == last) head->next = q; | (直接刪除) | |6-80| 程式6-4| 46 preparePrint(id) ... | 46 preparePrint(id); ... | |6-82| 程式6-5| 53 for (j=0; j<n ;j++) | 53 for (j=n-1; j>=0 ;j--) | |6-82| 程式6-5 | 行號47下一行(目前無行號)| 加入行號48 | |6-82| 程式6-5 | 行號48~58| 行號49~59 | |6-82| 1 | 程式6-5第47~49行 | 程式6-5第47~50行 | |6-82| 5 | 相鄰陣列*W* (52~57 行... | 相鄰陣列W (53~58行...(W字體為Courier New、無斜體) | |6-82| 7 | (55行... | (56行... | |6-82| -4 | (56行)...當52~57 | (57行)...當53~58 | |6-82| -2 | ... AOV[i].arc則記錄了i 直接前接點的個數，| ... AOV[i].count則記錄了 i 直接前接點的個數(56行)， | |7-12| 演算法7-3 | 6$\quad$... (j-h)>0 | 6$\quad$... (j-h)>=0 | |7-24| 演算法7-7 | 2 { int i, j; | 2 { int i, j, target; | |7-27| 演算法7-8 | 14 if (left<j) swap(&data[i], &data[j]) | 14 if (left<j) swap(&data[i], &data[j]); (新增 ; ) | |7-31| 演算法7-9 | 1 for (q=0, i=1; i<n; i++) | 1 for (q=A[0], i=1; i<n; i++) | |7-31| 演算法7-9 | 2 if (data[i]>q) q = data[i]; | 2 if (A[i]>q) q = A[i]; | |7-31| 演算法7-9 | 4 int * C = int new [m] |4 int * C = int new [m+1] | |7-31| 演算法7-9 | 5 for (i=0; i<m; i++)... |5 for (i=0; i<=m; i++)... | |7-31| 演算法7-9 | 7 for (i=0; i<m; i++)... |7 for (i=0; i<=m; i++)... | |7-31| 演算法7-9 | 8 for (j=1; j<n; j++) | 8 for (j=0; j<n; j++) | |7-34| 6 | 它的大小比較是與 ... 位數有關。 | 它排序的方式與 ... 位數有關。 | |7-34| 12 | ...。我們先看... | ...；各位數的排序並不使用比較大小的運算，而是用資料搬移 (data movement) 和佇列的結構來完成；我們先看... | |7-38| 演算法7-10 | 7$\quad$for (j=0; j<10; j++) | 7$\quad$for (j=0; j<n; j++) | |7-52| 頁碼 | 1-52 | 7-52 | |7-52| 1 | 直接用挑選或排序 | 直接用挑選排序(刪去"或") | ## 第三版 (2023/2/9 前) ![](https://i.imgur.com/TmLHJcI.jpg) ### 第一章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| | 1-2 | -3 | 「資料結構」(data structurs) | 「資料結構」(data structures)| | 1-10 | 程式1-1行號2 | SelectionSort | selectionSort | | 1-13 | 圖1-2兩處 | SelectionSort | selectionSort | | 1-14 | 註釋8行1~3 | 費氏數列出現於1202年 Leonardo Fibonacci的著作*Liber Abaci* ；其中有個假設介紹的費氏兔子問題 ... 可長為成兔，並生出一對費氏小兔，且費氏兔子不會死去 ... 此即為第$n$項費氏數列！ | 費氏數列出現於1202年Leonardo Fibonacci的著作*Liber Abaci*；其中介紹的費氏兔子問題 ... 可長為成兔，再一個月即可生育出一對小兔，之後每月皆然，且費氏兔子不會死去 ... 此即為第$n$項費氏數列：$F_n = F_{n-1}$ （上個月的兔子對數）$+F_{n-1}$ （上上個月的兔子會生出小兔的對數）；$F_0 = 0，F_1 = 1$。 | | 1-16 | 演算法1-2 | 行號 2, 3, 4, 5 | 3, 4, 5, 6 || 1-16 | 演算法1-2 | 行號 2, 3, 4, 5 | 3, 4, 5, 6 | | 1-16 | 演算法1-2 | 5$\quad\quad$towerHanoi(n-1, B, C, A) | 5$\quad\quad$towerHanoi(n-1, B, A, C) | | 1-16 | 程式1-4 | 行號 4(兩個中的第二個) | 6 | | 1-18 | -8 | $n$個元素的排列共有$n!$種。 | 一般而言，$n$個相異元素的排列共有$n!$種。 | | 1-20 | 4 | 假設c[0~3]={‘A’, ‘B’, ‘C’, ‘D’}； | 假設char c[4]={‘A’, ‘B’, ‘C’, ‘D’}； | |1-27 | 5 | $9n^2+11\le cn$ | $9n^2\color{cyan}{+n}+11\le cn$ | |1-31 | -9 |程式1-4提供了 $n$ 個陣列元素 ... | 程式1-6提供了 $n$ 個陣列元素 ... | |1-32 | 1 | 根據定義可知：程式1-7 ... | 根據定義可知：程式1-9 ... | |1-33 | 1 | ... 的代價），根據定義可知：程式1-7 ... | ... 的代價），根據定義可知：程式1-9 ... | | 1-37 | 9 | (j) $n^k\color{red}{+ \varepsilon}+n^klogn=\Theta(n^k\color{red}{+ \varepsilon})$ | (j) $n^{k\color{cyan}{+ \varepsilon}}+n^klogn=\Theta(n^{k\color{cyan}{+ \varepsilon}})$ | | 1-37 | 10 | (k) ... = *O*($\color{red}{100}n^22^n$) | (k) ... = *O*($n^22^n$) | ### 第二章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| | 2-7 | 圖2-4三處 | SelectionSort | selectionSort | | 2-8 | 註釋5 | n 用傳位法傳遞 | n 用傳值法傳遞 | | 2-14 | 演算法2-3 | 輸出：矩陣B ... | 輸出：nxm矩陣B ... || 2-15 | 演算法2-4 | 輸出：矩陣C ... | 輸出：mxn矩陣C ... | | 2-17 | 演算法2-5 | 輸出：矩陣C ... | 輸出：mxp矩陣C ... | | 2-18 | 演算法2-6 | 7 $\qquad$M[i][i] | 7 $\qquad$M[i][j] | | 2-25 | 7 | 皆為一樣。 | 皆為一樣。此現象稱為「隨機存取」(random access)；陣列即為隨機存取結構。 || 2-31 | -2 | 求得其位址值。圖2-18演算法 ... | 求得其位址值—隨機存取的性質展露無遺。圖2-18演算法 ... | | 2-34 | 11題末句 | 設計一個演算法 | 設計一個計算式 | ### 第三章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| |3-11|-6|定義Stack為一結構物件;此後... | 定義Stack為一結構物件（第6行為靜態宣告；亦可在程式中以 StackType * x; 動態宣告結構物件x）；此後...| | 3-25 | 圖3-14 第1列第1欄 | dir | d | |3-25 | 圖3-14 第2列第1欄 | move[dir].x | move[d].dx | | 3-25 | 圖3-14 第3列第1欄 | move[dir].y | move[d].dy | |3-28|-10 |前一步為(7,6,E) | 前一步為(7,6,SE) | |3-28|-7 |目前位置和前往方向W)：(7,6,W) | 目前位置和前往方向的下一個可能NW：(7,6,NW) | |3-29| 演算法3-1 -5行| 14 $\quad\quad$ i=u; j=v; dir=N; |14 $\quad\quad$ i=u; j=v; d=N;| |3-36|-1|...請看範例3-13|...請看範例3-15| ### 第四章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| |4-3|7|(a)$\quad$apple、peach、strawberry ... |(c)$\quad$apple、peach、strawberry ... | |4-15|程式4-5|5$\quad$... (!p && p->data ... |5$\quad$... (p && p->data ... | |4-16|6|其中 !p 與 p!=NULL ... |其中 p 與 p!=NULL ... | |4-17|程式4-6|3$\quad$... (!p && p->data ... |3$\quad$... (p && p->data ... | |4-17|程式4-6|4$\quad$if (!p) return ... |4$\quad$if (p) return ... | |4-39|程式4-17|6$\quad$struct PolyNode head_a, head_b, head_c; |6$\quad$struct PolyNode $\color{cyan}*$head_a, $\color{cyan}*$head_b, $\color{cyan}*$head_c; | |4-39|程式4-17|7$\quad$struct PolyNode last_a, last_b, last_c; |7$\quad$struct PolyNode $\color{cyan}*$last_a, $\color{cyan}*$last_b, $\color{cyan}*$last_c; | |4-39|程式4-17|8$\quad$struct node * NewTerm |8$\quad$struct PolyNode * NewTerm | |4-39|程式4-17|32 {$\quad$struct node * p |32 {$\quad$struct PolyNode * NewTerm | |4-40|程式4-17|51$\quad${$\quad$r = CopyTerm(p ); p = p->next; } |51$\quad${$\quad$r = CopyTerm(p ); InsertLast(r, last_c); p = p->next; } | |4-40|程式4-17|52$\quad$while (p!=head_a) |52$\quad$while (q!=head_b) | |4-40|程式4-17|53$\quad${$\quad$r = CopyTerm(p); p = p->next; } |53$\quad${$\quad$r = CopyTerm(q); InsertLast(r, last_c); q = q->next; } | |4-40|程式4-17第2個行號54|54$\quad$} |55$\quad$}| |4-41|-7程式區行號20|20 struct PolyNode AttachLast(... |20 struct PolyNode * AttachLast(...| |4-42|程式4-18|62$\quad$struct node * p |62$\quad$struct Polynode * p | |4-42|-3|51$\quad${$\quad$r = CopyTerm(p ); p = p->next; } |51$\quad${$\quad$r = CopyTerm(p ); InsertLast(r, last_c); p = p->next; } | |4-42|-2|52$\quad$while (p!=head_a) |52$\quad$while (q!=head_b) | |4-42|-1|53$\quad${$\quad$r = CopyTerm(p); p = p->next; } |53$\quad${$\quad$r = CopyTerm(q); InsertLast(r, last_c); q = q->next; } | |4-44|圖4-30| D $\quad$ 18 $\quad$ 27 ... |$\color{cyan}{D(x)}\quad$ 18 $\quad$ 27 ...| |4-45|3| ...旨在除本回合 |...旨在清除本回合| |4-45|程式4-19| 4$\quad$// 環狀串列只 利開頭空白節點 |4$\quad$//清空環狀串列只留開頭空白節點| |4-46|2|「稀疏矩陣」|「稀疏矩陣」 (sparse matrix)| |4-46|-9|... head_a 和 _head_b|... head_a 和 head_b| |4-47|10|...五個欄位並不|... 五個欄位大小並不| |4-47|11~12|...各欄位皆為指標-實體空間的大小|各指標欄位實體空間的大小| |4-52|程式4-22| 6 $\quad \quad${ $\quad$p = head;|6 $\quad \quad${ $\quad$p = first;| |4-52|2| 自head起逐一|自first起逐一| |4-52|-5| $\quad$for (p=head; |$\quad$for (p=first;| |4-55|程式4-24| 行號7~13 |行號6~12| |4-57|程式4-25| 8$\quad${$\quad$if (x == first) |8$\quad${$\quad$if (x == head)| ### 第五章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| |5-6|註釋3|無根樹較為$\quad$調點之間|無根樹較為強調點之間 | |5-13|-2|我們在一下節|我們在下一節 | |5-22|-3|會十分浪費時間|會十分浪費空間 | |5-36|程式5-6行43|while ((top != NULL) ... (node !=NULL); | while ((top != NULL) ... (node !=NULL)); | |5-44|程式5-7行33、34|33$\quad$return Tnode; 34$\quad$}| 33$\quad$} 34$\quad$return Tnode; | |5-48| -5 |程式5-9第7行中|程式5-9第1行中| |5-48| -3 |在第8行中|在第2行中 | |5-48| -2 |當第9、10、11、12行中|在第3~6行中 | |5-48| -1 |其中的第11行中|其中的第5行中 | |5-49| 2 |第12行亦然|第6行亦然 | |5-49| 4 |這也沿用了 ... 的精神|程式5-9的設計也沿用了 ... 的精神！ | |5-49| -7 |... 樹的成員；第4行|... 樹的成員；第5行 | |5-54| -7 | 中序後繼節*q*點。此時...|中序後繼節*q*點—此時... (註：破折號) | |5-54| -6 | 指向p（q是p的中序前接節點）！|指向p（p是q的中序前接節點）！ | | 5-59 | 程式5-13 | 行號16 |行號15 | |5-68| 程式5-17行8 | 8$\quad$struct BSTreeNode * InsertBST|8$\quad$struct BSTreeNode * InsertBSTree | |5-68| 程式5-17行11 | 11$\quad\quad$ ... = InsertBST(node->leftchild,x);|11$\quad\quad$ ... = InsertBSTree(node->leftchild,x); | |5-68| 程式5-17行13 | 13$\quad\quad$ ... = InsertBST(node->rightchild,x);|11$\quad\quad$ ... = InsertBSTree(node->rightchild,x); (註：可刪=前後空格使其不跳行)| |5-77| 程式5-19行47 | 47$\quad$Struct BSTreeNode|47$\quad$struct BSTreeNode| |5-77| 程式5-19行71 | 71$\quad\quad$k = k ->leaftchild; | 71$\quad\quad$k = k->leaftchild; (刪去空k -之間空格)| |5-82| 1~2 | 使之形成圖右的二元樹 | 使之形成圖左的二元樹| |5-84| 程式5-22行22 | 22 ... * y = x->rightchild; | 22 ... * x = y->leftchild;| |5-84| 程式5-22行23 | 23 ... *T2 = y->leftchild; | 23 ... *T2 = x->rightchild; | |5-84| 程式5-22行24 | 24$\quad$y->leftchild = x; | 24$\quad$x->rightchild= y; | |5-84| 程式5-22行25 | 25$\quad$x->rightchild = T2; | 24$\quad$y->leftchild = T2; | |5-84| 程式5-22行26 | 26$\quad$x->height = MAX(height(x->leftchild), height(x->rightchild)+1; | 26$\quad$y->height = MAX(height(y->leftchild), height(y->rightchild)+1; | |5-84| 程式5-22行27 | 27$\quad$y->height = MAX(height(y->leftchild), height(y->rightchild)+1; | 27$\quad$x->height = MAX(height(x->leftchild), height(x->rightchild)+1; | |5-86|-4(第二段句尾) | 。。 |。 | |5-88|表5-4欄2標題 | 失衡節點右兒子向左旋轉 |失衡節點右兒子向右旋轉 | |5-88|表5-4欄3標題 | 失衡節點向右旋轉 |失衡節點向左旋轉 | |5-88|6 |「失衡節點向右旋轉」。 |「失衡節點向左旋轉」。| |5-88|-4 |即可恢復平衡. |即可恢復平衡。 (句號字型請修改) | |5-91|程式5-23 |行號37 |37 (字型用 Courier New) | |5-92|-5 |（node->leftchild->data）的大小... |（node->rightchild->data）的大小... | |5-93| 9 |（於節 5.10.4 討論），... |（於節 5.10.5 討論），... | |5-95| 程式5-22行號103~108 |行號103~108 |行號104~109 | |5-96| 5 |（於節 5.10.4 討論）！ |（於節 5.10.5 討論）！ | |5-96| -1 |左子樹高為*h*-2 |右子樹高為*h*-2 | |5-97| 7 |首項為1的費氏數列 |首、次項為1、2的費氏數列 | |5-98| 5 | $F_h=\varphi ^h/$ $\color{red}{(5)^{1/2}}$， $\varphi$ =(1+$(5)^{1/2}$)/2 |$F_h=\varphi ^h/$ $\color{cyan}{\sqrt{5}}$， $\varphi$ =(1+$\color{cyan}{\sqrt{5}}$)/2 | ### 第六章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| |6-4|-3| e, f 五條邊 | e, f 六條邊 | | 6-6|-3|利用範例6-3說明明此…|利用範例6-3說明此… | | 6-13|-6|6.6）和拓樸…|6.7）和拓樸…| | 6-20|演算法6-2|8$\quad$for (...visted[w]|8$\quad$for (...visited[w]| | 6-20|演算法6-2|行號10~15 (自第二個10開始)|行號11~16| | 6-23|2|只要對G中過的點u|只要對G中的點u (刪去”過”) | | 6-27|10|可以互換的|可以互換的。| | 6-29|7|最小邊的取得|之後最小邊的取得| | 6-29|9|邊都會與第3行|邊都會參與第3行| | 6-34|程式6-2行號6|6 struct UFNode vertex [SIZE];|6 struct UFNode * vertex [SIZE];| | 6-34|9|邊都會與第3行|邊都會參與第3行| | 6-59|3~4|如圖 6-34 最右側的邊。|如圖 6-35 最右側的邊。| | 6-59|-5|與範例6-22相似|與範例6-23相似| | 6-59|-1|與範例6-22者幾乎一樣|與範例6-23者幾乎一樣| | 6-71|圖6-43 |(a) … 矩陣A (b) … 矩陣A+|(a) … 矩陣$A\quad$(b) … 矩陣$A^+$ (A為斜體、+為上標) | | 6-72|圖6-45 |(a) … 矩陣A (b) … 矩陣A+|(a) … 矩陣$A\quad$(b) … 矩陣$A^+$ (A為斜體、+為上標) | ### 第七章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| | 7-12|演算法7-3|6$\quad$while ((data[j-h]>target) && (j>0))|6$\quad$while ((j-h>0) && (data[j-h]>target)) (j>0==>j-h>0、兩條件互換) | | 7-21|-6|9~10行（…|8~9行（…| | 7-24|7|它不必該次分割...|它不必與該次分割... | | 7-30|1|破壞值相同資料的...|破壞相同數值資料的... | | 7-30|-4|8為排序數列中第六位|9為排序數列中第六位| | 7-37|2|進行十位數字依序計數|進行百位數字依序計數| | 7-38|演算法7-10|1$\quad$q = 0;|1$\quad$q = data[0]; | | 7-48|演算法7-13|3$\quad$if（y<=z）|3$\quad$if（b<=c）| | 7-48|演算法7-13|4$\quad$else if（x<=z）|4$\quad$else if（a<=c）| ### 第一章 | $頁數$ | 行數或區段 | 錯誤 | 更正 | | --- | --- | -------- |--| | 1-10 | -3 | 請看程式 1-2。 | 請看程式 1-2。(字體請用 Courier New)| ![image](https://hackmd.io/_uploads/rJKVNAIhkx.png) ![image](https://hackmd.io/_uploads/rJs9V0InJx.png) |![image](https://hackmd.io/_uploads/S1BkB0Lhyl.png) ![image](https://hackmd.io/_uploads/Sk_ZrRIhkx.png) | | 15$\qquad\qquad$for (0 $\le$ k $\le$ 7)|