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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、182;¶¶采用Huffman編碼進行文件壓縮，以單詞為單位進行壓縮，統(tǒng)計單詞的使用頻率，單詞以空格、標點符號或回車換行符分隔。要求同上。5. 樹（父母孩子兄弟鏈表存儲）Tree<T>樹類采用父母孩子兄弟鏈表存儲。（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é)點次序10-58 TreeNode<T> search(Tree<T> pattern) /無序樹，查找匹配的子樹，忽略孩子結(jié)點次序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） 對樹操作的靜態(tài)方法，遞歸算法10-63 T ancestor(Tree<T> tree, T x, T y) /返回x、y結(jié)點最近的共同祖先結(jié)點10-64 <T> void diameterAll(Tree<T> tree

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

23、義表構造樹，不使用棧的非遞歸算法6. 樹（孩子兄弟鏈表存儲）Tree<T>樹類采用孩子兄弟鏈表存儲，方法聲明同上。（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é)點次序10-71 TreeNode<T> search(Tree<T> pattern) /無序樹，查找匹配的子樹，忽略孩子結(jié)點次序10-72 ¶¶void removeAll(Tree<T> pattern) /無序樹，刪除所有匹配的子樹，忽略孩子次序10-73 ¶¶¶void replaceAll(Tree<T> pattern, Tree<T> tree) /無序樹，替換所有匹配子樹，忽略孩子次序（2） 樹的成員方法，非遞歸算法10-74 ¶¶¶

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

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

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

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

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

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

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

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

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

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

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

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

37、合查詢，題詳見教材10.4節(jié)。10.4.6 查找1. 查找設計（1） 散列10-122 ¶¶HashSet<T>散列表類聲明實現(xiàn)Set<T>接口（見1.1.3節(jié)），實現(xiàn)集合相等、包含、并、差、交等集合運算，以及讀寫對象文件操作。10-123 ¶¶實現(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() /輸出的計算公式（顯示每層的查找次數(shù)×結(jié)點個數(shù)）及結(jié)果10-127 ¶¶BinarySortTree<T>二叉排序樹類聲明實現(xiàn)Set<T>接口，實現(xiàn)集合相等、包含、并、差、交等集合運算。10-128 ¶¶實現(xiàn)TreeMap<K,V>樹映射類的keySet()、values()等方法。（3） 平衡二叉樹10-129 ¶

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