《數(shù)據(jù)結(jié)構(gòu)(Java版)(第4版)》課程設(shè)計(jì)題

1、第10章 課程設(shè)計(jì)10.4 課程設(shè)計(jì)選題課程設(shè)計(jì)的目的、要求和選題詳見教材10.4節(jié)，及課程設(shè)計(jì)任務(wù)書。10.4.1 線性表1. 多項(xiàng)式的表示和運(yùn)算題意詳見教材2.4節(jié)。（1） 使用排序單鏈表存儲(chǔ)多項(xiàng)式10-1 ¶一元多項(xiàng)式相加，PolySinglyList<T>多項(xiàng)式排序單鏈表類增加以下成員方法，public權(quán)限。/多項(xiàng)式相加，返回thislist的多項(xiàng)式，不改變this和list，C(x)=A(x)B(x)。/算法不調(diào)用深拷貝，將this（A）和list（B）中的所有結(jié)點(diǎn)合并（相加）到C多項(xiàng)式單鏈表PolySinglyList<T> union(PolyS

2、inglyList<T> list)10-2 ¶二元多項(xiàng)式相加，實(shí)現(xiàn)10-1題。10-3 ¶一元多項(xiàng)式相乘，Polynomial多項(xiàng)式類增加以下成員方法。public boolean equals(Object obj) /比較兩個(gè)多項(xiàng)式是否相等，覆蓋public Polynomial multi(Polynomial poly) /相乘，返回this*poly的多項(xiàng)式10-4 ¶二元多項(xiàng)式相乘，實(shí)現(xiàn)10-3題。（2） 使用排序循環(huán)雙鏈表存儲(chǔ)多項(xiàng)式10-5 ¶一元多項(xiàng)式相加，聲明PolyDoublyList<T>多項(xiàng)式排序循環(huán)雙鏈

3、表類，繼承排序循環(huán)雙鏈表類，方法聲明如下。Polynomial多項(xiàng)式類使用PolyDoublyList<T>對(duì)象作為成員變量。PolyDoublyList<T> union(PolyDoublyList<T> list) /返回相加的多項(xiàng)式，不調(diào)用深拷貝10-6 ¶二元多項(xiàng)式相加，實(shí)現(xiàn)10-5題。10-7 ¶一元多項(xiàng)式相乘，聲明PolyDoublyList<T>多項(xiàng)式排序循環(huán)雙鏈表類，繼承排序循環(huán)雙鏈表類，實(shí)現(xiàn)二元多項(xiàng)式相乘運(yùn)算，方法聲明如下。Polynomial多項(xiàng)式類使用PolyDoublyList<T>對(duì)象作

4、為成員變量。Polynomial multi(Polynomial poly) /返回相乘的多項(xiàng)式10-8 ¶二元多項(xiàng)式相乘，實(shí)現(xiàn)10-7題。10.4.2 棧和隊(duì)列及遞歸算法1. 計(jì)算表達(dá)式值在例4.2、例4.6計(jì)算算術(shù)表達(dá)式值的基礎(chǔ)上，增加以下功能。 檢查表達(dá)式語法是否正確。 使用散列映射存儲(chǔ)運(yùn)算符集合，建立從運(yùn)算符到優(yōu)先級(jí)的映射，快速查找指定運(yùn)算符的優(yōu)先級(jí)。運(yùn)算符集合包括位運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符、字符串連接運(yùn)算符等，各運(yùn)算符的優(yōu)先級(jí)見附錄D。 整數(shù)表達(dá)式增加位運(yùn)算功能。 計(jì)算邏輯表達(dá)式、字符表達(dá)式、字符串表達(dá)式等，BNF定義見教材實(shí)驗(yàn)4-12。 以浮點(diǎn)數(shù)作為常數(shù)，所求算術(shù)

5、表達(dá)式值為浮點(diǎn)數(shù)類型。 增加標(biāo)識(shí)符作為變量，識(shí)別標(biāo)識(shí)符，為變量賦值。使用散列映射存儲(chǔ)變量集合，快速查找指定變量的值。 采用文件保存多行表達(dá)式字符串，讀取表達(dá)式，并將結(jié)果寫入文件。10-9 ¶¶計(jì)算表達(dá)式值。改進(jìn)例4.2，同時(shí)使用運(yùn)算符棧和操作數(shù)棧，省略轉(zhuǎn)換成后綴表達(dá)式過程；增加運(yùn)算符、浮點(diǎn)數(shù)等功能。10-10 ¶¶¶計(jì)算表達(dá)式值，遞歸算法。改進(jìn)例4.6，增加運(yùn)算符、浮點(diǎn)數(shù)等功能。10-11 ¶¶¶¶¶帶變量的表達(dá)式求值，使用棧，增加運(yùn)算符、浮點(diǎn)數(shù)等功能。10-12 ¶¶

6、82;¶¶帶變量的表達(dá)式求值，遞歸算法，增加運(yùn)算符、浮點(diǎn)數(shù)等功能。10-13 ¶¶給定一個(gè)初始序列，求解素?cái)?shù)環(huán)問題（例4.3）的所有解，采用回溯法（10.3.4節(jié)）。2. 走迷宮迷宮題見實(shí)驗(yàn)4-13，指定迷宮大小、入口及出口位置和初始狀態(tài)等，求解一條或多條路徑，演示走迷宮過程，顯示一條或多條結(jié)果路徑。10-14 ¶¶走迷宮，使用棧。10-15 ¶¶走迷宮，使用隊(duì)列。10-16 ¶¶走迷宮，遞歸算法。10-17 ¶¶走迷宮求所有路徑，采用回溯法（10.3.4節(jié)）。10-18 &

7、#182;¶騎士游歷問題（見實(shí)驗(yàn)題4-18）求多個(gè)解，采用回溯法（10.3.4節(jié)）。10.4.3 矩陣和廣義表1. 稀疏矩陣的壓縮存儲(chǔ)及運(yùn)算以下各題實(shí)現(xiàn)深拷貝、矩陣相加（addAll()和union()見實(shí)驗(yàn)題5-3）、轉(zhuǎn)置等矩陣運(yùn)算。（1） 稀疏矩陣三元組行的排序單/雙鏈表10-19 ¶設(shè)LinkedMatrix矩陣類采用行的排序單鏈表存儲(chǔ)（見實(shí)驗(yàn)題5-4）。10-20 ¶¶設(shè)LinkedMatrix矩陣類采用行的多項(xiàng)式排序單鏈表PolySinglyList<Triple>（見2.4節(jié)）存儲(chǔ)。10-21 ¶設(shè)LinkedMatri

8、x矩陣類采用行的排序循環(huán)雙鏈表存儲(chǔ)。10-22 ¶¶設(shè)LinkedMatrix矩陣類采用行的多項(xiàng)式排序循環(huán)雙鏈表存儲(chǔ)。（2） 稀疏矩陣三元組列的排序單/雙鏈表10-23 ¶設(shè)LinkedMatrix矩陣類采用列的排序單鏈表存儲(chǔ)（見實(shí)驗(yàn)題5-4）。10-24 ¶¶設(shè)LinkedMatrix矩陣類采用列的多項(xiàng)式排序單鏈表PolySinglyList<Triple>（見2.4節(jié)）存儲(chǔ)。10-25 ¶設(shè)LinkedMatrix矩陣類采用列的排序循環(huán)雙鏈表存儲(chǔ)。10-26 ¶¶設(shè)LinkedMatrix矩陣類采用

9、列的多項(xiàng)式排序循環(huán)雙鏈表存儲(chǔ)。（3） 稀疏矩陣三元組十字鏈表以下各題實(shí)現(xiàn)深拷貝、矩陣相加（addAll()和union()見實(shí)驗(yàn)題5-3）、比較相等、轉(zhuǎn)置等矩陣運(yùn)算。10-27 ¶¶¶設(shè)CrossLinkedMatrix矩陣類采用十字單鏈表存儲(chǔ)，見圖5.13。10-28 ¶¶¶¶設(shè)CrossLinkedMatrix矩陣類采用十字雙鏈表存儲(chǔ)，改進(jìn)圖5.13，每個(gè)結(jié)點(diǎn)增加指向行列前驅(qū)的指針。2. 廣義表10-29 ¶¶¶聲明以雙鏈表示的廣義表類GenList，實(shí)現(xiàn)廣義表的遍歷、插入、刪除、查找原子、

10、比較相等、復(fù)制等操作。 10-30 ¶¶¶以廣義表雙鏈表示實(shí)現(xiàn)m元多項(xiàng)式的相加、相乘等運(yùn)算。10.4.4 二叉樹和樹1. 二叉樹（二叉鏈表存儲(chǔ)結(jié)構(gòu)）（1） 二叉樹的成員方法，遞歸算法已知BinaryTree<T>二叉樹類采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，增加以下成員方法，public權(quán)限。10-31 ¶以先根和中根序列構(gòu)造二叉樹，替換其中所有與pattern匹配的子樹。成員方法聲明如下：BinaryTree(T prelist, T inlist) /以先根和中根序列構(gòu)造二叉樹void replaceAll(BinaryTree<T> pat

11、tern, BinaryTree<T> bitree)/替換所有與pattern匹配子樹（深拷貝）10-32 以中根和后根序列構(gòu)造二叉樹，替換其中所有與pattern匹配的子樹。方法聲明如下：BinaryTree(T inlist, T postlist) /以中根和后根序列構(gòu)造二叉樹（2） 二叉樹的成員方法，使用棧的非遞歸算法10-33 ¶以先根和中根序列構(gòu)造二叉樹（使用棧的非遞歸算法），替換其中所有與pattern匹配的子樹。 10-34 ¶以中根和后根序列構(gòu)造二叉樹（使用棧的非遞歸算法），替換其中所有與pattern匹配的子樹。 （3） 對(duì)二叉樹操作的靜態(tài)

12、方法，遞歸算法10-35 ¶以中根和后根序列構(gòu)造二叉樹，求二叉樹中兩結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)。方法聲明如下：T ancestor(BinaryTree<T> bitree, T x, T y) /返回x、y結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)10-36 ¶以中根和后根序列構(gòu)造二叉樹，求一棵二叉樹的所有直徑及其路徑長(zhǎng)度。方法聲明如下：void diameterAll(BinaryTree<T> bitree) /輸出二叉樹的所有直徑及其路徑長(zhǎng)度10-37 ¶¶以中根和后根序列構(gòu)造一棵二叉樹，以層次序列構(gòu)造一棵完全二叉樹，調(diào)用以下方法：boolean

13、 isComplete(BinaryTree<T> bitree) /判斷是否為完全二叉樹（4） 對(duì)二叉樹操作的靜態(tài)方法，使用棧的非遞歸算法（5） 表達(dá)式二叉樹表達(dá)式二叉樹類ExpressionBinaryTree（見例6.3）聲明以下方法。10-38 ¶¶¶ void createByPostfix(String postfix) /以后綴表達(dá)式構(gòu)造表達(dá)式二叉樹10-39 ¶¶¶ void inorder() /輸出帶括號(hào)的中綴表達(dá)式，算法必須比較運(yùn)算符優(yōu)先級(jí)的大小其中，使用散列映射存儲(chǔ)運(yùn)算符集合，快速查找指定運(yùn)算符的優(yōu)

14、先級(jí)，Java運(yùn)算符及其優(yōu)先級(jí)見附錄D。（6） 二叉樹的其他應(yīng)用10-40 ¶存儲(chǔ)淘汰賽的比賽信息，創(chuàng)建表示比賽過程的滿二叉樹（教材圖1.2），保存比賽結(jié)果。2. 二叉樹（三叉鏈表存儲(chǔ)結(jié)構(gòu)）（1） 二叉樹的成員方法，不使用棧的非遞歸算法10-41 ¶¶BinaryTree(T prelist)以標(biāo)明空子樹的先根序列構(gòu)造二叉樹（不使用棧的非遞歸算法），替換所有與pattern匹配的子樹。10-42 ¶¶¶BinaryTree(BinaryTree<T> bitree)深拷貝，不使用棧的非遞歸算法。10-43 ¶&#

15、182;¶以中根和后根序列構(gòu)造二叉樹，printGenList()輸出二叉樹的廣義表表示（不使用棧的非遞歸算法）。（2） 對(duì)二叉樹操作的靜態(tài)方法，不使用棧的非遞歸算法10-44 ¶以中根和后根序列構(gòu)造二叉樹，求二叉樹中兩結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)。10-45 ¶以中根和后根序列構(gòu)造二叉樹，求二叉樹的所有直徑及其路徑長(zhǎng)度（不使用棧的非遞歸算法）。10-46 ¶¶¶¶BinaryTree<String> createByGenList(String genlist) /以廣義表表示字符串構(gòu)造二叉樹（3） 表達(dá)式二叉樹10

16、-47 ¶¶¶ createByPostfix(String postfix) /以后綴表達(dá)式構(gòu)造表達(dá)式二叉樹10-48 ¶¶¶ inorder() /輸出帶括號(hào)的中綴表達(dá)式，使用散列映射存儲(chǔ)運(yùn)算符集合3. 線索二叉樹以下對(duì)中序線索二叉樹操作的算法描述見習(xí)題解答6.3節(jié)。10-49 ¶ ThreadNode<T> parent(ThreadNode<T> node) /返回node結(jié)點(diǎn)的父母結(jié)點(diǎn)10-50 ¶插入根，插入左/右孩子操作，方法聲明如下。void add(T x) /插入x作為根

17、結(jié)點(diǎn)，原根作為x的左孩子ThreadNode<T> add(ThreadNode<T> p, T x, boolean leftChild) /插入x作為p的左/右孩子結(jié)點(diǎn)10-51 ¶¶刪除根，刪除指定結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，2度結(jié)點(diǎn)用刪除結(jié)點(diǎn)的左孩子頂替，方法聲明如下。void remove() /刪除根，分別用左或右孩子頂替void remove(ThreadNode<T> p, boolean leftChild) /刪除p的左或右孩子，用左或右孩子頂替void remove(ThreadNode<T> p) /刪除以p結(jié)點(diǎn)

18、為根的子樹10-52 ¶¶刪除根，刪除指定結(jié)點(diǎn)的右孩子結(jié)點(diǎn)，2度結(jié)點(diǎn)用刪除結(jié)點(diǎn)的右孩子頂替，畫出算法描述圖。4. Huffman樹10-53 ¶¶¶采用Huffman編碼進(jìn)行文件壓縮，以字符為單位進(jìn)行壓縮，統(tǒng)計(jì)字符使用頻率。 指定一個(gè)文本文件，采用散列映射或樹映射統(tǒng)計(jì)其中字符使用頻率（例8.3、例8.5）。 指定字符集合和權(quán)值集合創(chuàng)建一棵Huffman樹，獲得各字符的Huffman編碼（以多個(gè)二進(jìn)制位表示）。 壓縮指定文件，計(jì)算壓縮比。 解壓縮文件，指定二進(jìn)制位文件，采用Huffman編碼對(duì)二進(jìn)制位序列進(jìn)行譯碼，獲得原文本文件。10-54 &#

19、182;¶¶采用Huffman編碼進(jìn)行文件壓縮，以單詞為單位進(jìn)行壓縮，統(tǒng)計(jì)單詞的使用頻率，單詞以空格、標(biāo)點(diǎn)符號(hào)或回車換行符分隔。要求同上。5. 樹（父母孩子兄弟鏈表存儲(chǔ)）Tree<T>樹類采用父母孩子兄弟鏈表存儲(chǔ)。（1） 樹的成員方法，遞歸算法10-55 ¶void replaceAll(Tree<T> pattern, Tree<T> tree) /替換所有與pattern匹配子樹為tree10-56 ¶¶¶ void printGenList() /輸出樹（森林）的廣義表表示字符串10-57 b

20、oolean equalsIgnoreOrder(Tree<T> tree) /無序樹，比較是否相等，忽略孩子結(jié)點(diǎn)次序10-58 TreeNode<T> search(Tree<T> pattern) /無序樹，查找匹配的子樹，忽略孩子結(jié)點(diǎn)次序10-59 ¶¶void removeAll(Tree<T> pattern) /無序樹，刪除所有匹配的子樹，忽略孩子次序10-60 ¶¶¶void replaceAll(Tree<T> pattern, Tree<T> tree)

21、/無序樹，替換所有匹配子樹，忽略孩子次序（2） 樹的成員方法，非遞歸算法10-61 ¶¶¶ void printGenList() /輸出樹的廣義表表示，使用棧的非遞歸算法10-62 ¶¶¶ void printGenList() /輸出樹的廣義表表示，不使用棧的非遞歸算法（3） 對(duì)樹操作的靜態(tài)方法，遞歸算法10-63 T ancestor(Tree<T> tree, T x, T y) /返回x、y結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)10-64 <T> void diameterAll(Tree<T> tree

22、) /輸出樹的所有直徑及其路徑長(zhǎng)度10-65 ¶¶¶Tree<String> createGenList(String genlist) /返回以廣義表表示genlist構(gòu)造的樹（森林）（4） 對(duì)樹操作的靜態(tài)方法，非遞歸算法10-66 ¶¶¶Tree<String> createGenList(String genlist) /以廣義表構(gòu)造樹，使用棧的非遞歸算法10-67 ¶¶¶Tree<String> createGenList(String genlist) /以廣

23、義表構(gòu)造樹，不使用棧的非遞歸算法6. 樹（孩子兄弟鏈表存儲(chǔ)）Tree<T>樹類采用孩子兄弟鏈表存儲(chǔ)，方法聲明同上。（1） 樹的成員方法，遞歸算法10-68 ¶void replaceAll(Tree<T> pattern, Tree<T> tree) /替換所有與pattern匹配子樹為tree10-69 ¶¶¶ void printGenList() /輸出樹（森林）的廣義表表示字符串10-70 boolean equalsIgnoreOrder(Tree<T> tree) /無序樹，比較是否相等，忽略孩

24、子結(jié)點(diǎn)次序10-71 TreeNode<T> search(Tree<T> pattern) /無序樹，查找匹配的子樹，忽略孩子結(jié)點(diǎn)次序10-72 ¶¶void removeAll(Tree<T> pattern) /無序樹，刪除所有匹配的子樹，忽略孩子次序10-73 ¶¶¶void replaceAll(Tree<T> pattern, Tree<T> tree) /無序樹，替換所有匹配子樹，忽略孩子次序（2） 樹的成員方法，非遞歸算法10-74 ¶¶¶

25、 void printGenList() /輸出樹的廣義表表示，使用棧的非遞歸算法（3） 對(duì)樹操作的靜態(tài)方法，遞歸算法10-75 T ancestor(Tree<T> tree, T x, T y) /返回x、y結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)10-76 <T> void diameterAll(Tree<T> tree) /輸出樹的所有直徑及其路徑長(zhǎng)度10-77 ¶Tree<String> create(String prelist) /以橫向凹入表示構(gòu)造樹10-78 ¶¶¶Tree<String> c

26、reateGenList(String genlist) /返回以廣義表表示genlist構(gòu)造的樹（森林）（4） 對(duì)樹操作的靜態(tài)方法，非遞歸算法10-79 ¶¶¶Tree<String> createGenList(String genlist) /以廣義表構(gòu)造樹，使用棧的非遞歸算法10.4.5 圖1. 圖的鄰接表存儲(chǔ)帶權(quán)圖類實(shí)現(xiàn)AdjListGraph<T>類聲明的以下成員方法，public權(quán)限。10-80 int cost() /返回帶權(quán)圖的代價(jià)（無向圖每邊只計(jì)算一次）10-81 Triple minWeightEgde() /返回帶權(quán)

27、圖中權(quán)值最小的邊10-82 boolean isComplete() /判斷是否完全圖10-83 AdjListGraph<T> createComplete(T vertices) /以頂點(diǎn)集合構(gòu)造一個(gè)完全圖10-84 AdjListGraph(AdjListGraph<T> graph) /拷貝構(gòu)造方法，深拷貝10-85 ¶AdjListGraph(MatrixGraph<T> graph) /拷貝構(gòu)造方法，深拷貝2. 抽象圖類關(guān)于圖的連通性操作（1） 實(shí)現(xiàn)AbstractGraph<T>類以下對(duì)圖的操作，圖的鄰接矩陣存儲(chǔ)。10-8

28、6 ¶boolean equals(Object obj) /比較兩個(gè)圖是否相等，忽略頂點(diǎn)次序10-87 ¶boolean isSubgraph(AbstractGraph<T> graph) /判斷是否子圖10-88 ¶boolean isSpanSubgraph(AbstractGraph<T> graph) /判斷是否生成子圖10-89 ¶boolean stronglyConnected() /判斷一個(gè)無向圖是否為連通圖10-90 ¶boolean stronglyConnected() /判斷一個(gè)有向圖是否為強(qiáng)

29、連通圖10-91 ¶boolean isTree() /判斷一個(gè)無向圖是否為一棵樹10-92 ¶boolean isCyclePath(int vertexs) /判斷由頂點(diǎn)序列表示的一條路徑是否為回路10-93 ¶boolean isPath(SinglyList<T> pathlink) /判斷由單鏈表存儲(chǔ)的頂點(diǎn)序列是否是圖的一條路徑10-94 ¶void printPathAll(int i, int j) /輸出頂點(diǎn)、之間的所有路徑及其路徑長(zhǎng)度，回溯法（10.3.4節(jié)）10-95 ¶¶void printPathA

30、ll(int i)/輸出從頂點(diǎn)出發(fā)的所有深度優(yōu)先搜索的遍歷路徑（圖7.23），回溯法（2） 實(shí)現(xiàn)AbstractGraph<T>類以下對(duì)圖的操作，圖的鄰接表存儲(chǔ)。10-96 ¶¶boolean equals(Object obj) /比較兩個(gè)圖是否相等，忽略頂點(diǎn)次序10-97 ¶¶boolean isSubgraph(AbstractGraph<T> graph) /判斷是否子圖10-98 ¶¶¶boolean isSubgraph(MatrixGraph<T> graph) /判斷是否子

31、圖，graph圖鄰接矩陣存儲(chǔ)10-99 ¶¶boolean isSpanSubgraph(AbstractGraph<T> graph) /判斷是否生成子圖10-100 ¶¶¶boolean isSpanSubgraph(MatrixGraph<T> graph) /判斷是否生成子圖，graph鄰接矩陣存儲(chǔ)10-101 ¶¶boolean stronglyConnected() /判斷一個(gè)無向圖是否為連通圖10-102 ¶¶boolean stronglyConnected() /

32、判斷一個(gè)有向圖是否為強(qiáng)連通圖10-103 ¶¶boolean isTree() /判斷一個(gè)無向圖是否為一棵樹10-104 ¶¶boolean isCyclePath(int vertexs) /判斷由頂點(diǎn)序列表示的一條路徑是否為回路10-105 ¶¶boolean isPath(SinglyList<T> pathlink) /判斷由單鏈表存儲(chǔ)的頂點(diǎn)序列是否是圖的一條路徑10-106 ¶¶void printPathAll(int i, int j) /輸出、之間的所有路徑及其路徑長(zhǎng)度，回溯法(10.3

33、.4節(jié))10-107 ¶¶¶void printPathAll(int i) /輸出從出發(fā)的所有深度優(yōu)先搜索的遍歷路徑（圖7.23），回溯法3. 圖的鄰接多重表存儲(chǔ)（1） 以鄰接多重表存儲(chǔ)帶權(quán)無向圖10-108 ¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)無向圖，實(shí)現(xiàn)插入、刪除、遍歷操作算法。10-109 ¶¶¶¶void printPathAll(int i) /輸出從頂點(diǎn)出發(fā)的所有深度優(yōu)先搜索的遍歷路徑（圖7.23）10-110 ¶¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)無向圖，采用

34、Prim算法求圖的最小生成樹。10-111 ¶¶¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)無向圖，采用Kruskal算法求圖的最小生成樹。10-112 ¶¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)無向圖，采用Dijkstra算法求圖的單源最短路徑。10-113 ¶¶¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)無向圖，采用Floyd算法求圖所有頂點(diǎn)間的最短路徑。（2） 以鄰接多重表存儲(chǔ)帶權(quán)有向圖10-114 ¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)有向圖，實(shí)現(xiàn)插入、刪除、遍歷操作算法。10-

35、115 ¶¶¶¶void printPathAll(int i) /輸出從頂點(diǎn)出發(fā)的所有深度優(yōu)先搜索的遍歷路徑（圖7.23）10-116 ¶¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)有向圖，采用Dijkstra算法求圖的單源最短路徑。10-117 ¶¶¶¶¶以鄰接多重表存儲(chǔ)帶權(quán)有向圖，采用Floyd算法求圖所有頂點(diǎn)間的最短路徑。4. 圖的應(yīng)用10-118 ¶¶¶繪制一個(gè)由若干城市的航班路線構(gòu)成的帶權(quán)有向圖（圖1.3），連接兩城市的邊表示兩地是否開通航班

36、，有直飛或經(jīng)停，邊的權(quán)值表示兩地間價(jià)格。指定兩城市，給出多種航班路線方案，在何地中轉(zhuǎn)，標(biāo)明最短路徑。10-119 ¶¶¶繪制一個(gè)由若干貨幣的匯率關(guān)系構(gòu)成的帶權(quán)有向圖，如人民幣、美元、歐元、英鎊、加元、澳元等，有向邊表示匯率關(guān)系。有些貨幣之間無法直接兌換，需要由第三方中轉(zhuǎn)。指定兩種貨幣的若干金額，給出轉(zhuǎn)換結(jié)果，由第三方中轉(zhuǎn)的多種方案。例如，將100美元轉(zhuǎn)換成多少人民幣；將1000人民幣轉(zhuǎn)換成多少土耳其里拉，需要由美元或歐元中轉(zhuǎn)，標(biāo)明最佳轉(zhuǎn)換方案。10-120 地鐵計(jì)費(fèi)，題詳見教材10.4節(jié)。10-121 ¶¶¶¶公共交通信息綜

37、合查詢，題詳見教材10.4節(jié)。10.4.6 查找1. 查找設(shè)計(jì)（1） 散列10-122 ¶¶HashSet<T>散列表類聲明實(shí)現(xiàn)Set<T>接口（見1.1.3節(jié)），實(shí)現(xiàn)集合相等、包含、并、差、交等集合運(yùn)算，以及讀寫對(duì)象文件操作。10-123 ¶¶實(shí)現(xiàn)HashMap<K,V>散列映射類的keySet()、values()等方法。（2） 二叉排序樹10-124 BinarySortTree<T> subSet(T begin, T end) /返回取值在beginend范圍內(nèi)的子樹，深拷貝10-125 bool

38、ean isSubtree(BinarySortTree<T> bstree) /判斷bstree表示排序集合是否是this的子集10-126 void printASL() /輸出的計(jì)算公式（顯示每層的查找次數(shù)×結(jié)點(diǎn)個(gè)數(shù)）及結(jié)果10-127 ¶¶BinarySortTree<T>二叉排序樹類聲明實(shí)現(xiàn)Set<T>接口，實(shí)現(xiàn)集合相等、包含、并、差、交等集合運(yùn)算。10-128 ¶¶實(shí)現(xiàn)TreeMap<K,V>樹映射類的keySet()、values()等方法。（3） 平衡二叉樹10-129 ¶

39、;¶¶¶聲明平衡二叉樹類AVL，實(shí)現(xiàn)平衡二叉樹的插入、刪除和查找等操作。使用平衡二叉樹存儲(chǔ)互異的排序隨機(jī)數(shù)序列，分析其特點(diǎn)、功能和查找效率。2. 查找應(yīng)用（1） 提供快速查詢的存儲(chǔ)技術(shù)10-130 ¶¶電話簿，按姓氏分塊存儲(chǔ)。采用索引單鏈表（圖8.8）結(jié)構(gòu)，實(shí)現(xiàn)以下功能，分析算法效率。 索引表按姓氏排序，采用排序單鏈表或排序循環(huán)雙鏈表存儲(chǔ)。 主表按姓氏分塊存儲(chǔ)，各塊按姓名排序，提供查找、插入、刪除操作，可存儲(chǔ)一人多號(hào)，采用排序單/循環(huán)雙鏈表存儲(chǔ)。 提供讀寫對(duì)象文件操作。10-131 ¶¶電話簿，按姓氏分塊存儲(chǔ)，用散列表作為索引表和主表，不排序，要求同上。10-132 ¶¶電話簿，按姓氏分塊存儲(chǔ)，采用二叉排序樹作為索引表和主表，要求同上題。10-133 ¶