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

1、BNF 定義見教材實(shí)驗(yàn) 4-12。第 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) 使用排序單鏈表存儲多項(xiàng)式10-1 一元多項(xiàng)式相加， PolySinglyList 多項(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)式單鏈表PolySinglyLi

2、st union(PolySinglyList 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)雙鏈表存儲多項(xiàng)式10-5一元多項(xiàng)式相加，聲明PolyDoublyList 多項(xiàng)式排序循環(huán)雙鏈表類，繼承排序循環(huán)雙鏈表類，方法聲明如下。 P

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

4、0.4.2棧和隊(duì)列及遞歸算法1.計(jì)算表達(dá)式值在例 4.2、例 4.6 計(jì)算算術(shù)表達(dá)式值的基礎(chǔ)上，增加以下功能。 檢查表達(dá)式語法是否正確。 使用散列映射存儲運(yùn)算符集合，建立從運(yùn)算符到優(yōu)先級的映射，快速查找指定運(yùn)算符的優(yōu)先級。運(yùn)算 符集合包括位運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符、字符串連接運(yùn)算符等，各運(yùn)算符的優(yōu)先級見附錄D。 整數(shù)表達(dá)式增加位運(yùn)算功能。 計(jì)算邏輯表達(dá)式、字符表達(dá)式、字符串表達(dá)式等， 以浮點(diǎn)數(shù)作為常數(shù)，所求算術(shù)表達(dá)式值為浮點(diǎn)數(shù)類型。 增加標(biāo)識符作為變量，識別標(biāo)識符，為變量賦值。使用散列映射存儲變量集合，快速查找指定變量的 值。 采用文件保存多行表達(dá)式字符串，讀取表達(dá)式，并將結(jié)果寫入文件。

5、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帶變量的表達(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

6、-15 走迷宮，使用隊(duì)列。10-16 走迷宮，遞歸算法。10-17 走迷宮求所有路徑，采用回溯法（ 10.3.4 節(jié)）。10-18 騎士游歷問題（見實(shí)驗(yàn)題 4-18）求多個(gè)解，采用回溯法（ 10.3.4 節(jié)）。10.4.3矩陣和廣義表1. 稀疏矩陣的壓縮存儲及運(yùn)算以下各題實(shí)現(xiàn)深拷貝、矩陣相加（ addAll（） 和 union（） 見實(shí)驗(yàn)題 5-3）、轉(zhuǎn)置等矩陣運(yùn)算。（1）稀疏矩陣三元組 行 的排序單 /雙鏈表10-19 設(shè) LinkedMatrix 矩陣類采用行的排序單鏈表存儲（見實(shí)驗(yàn)題5-4）。10-20 設(shè) LinkedMatrix 矩陣類采用行的多項(xiàng)式排序單鏈表 PolySinglyL

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

8、鏈表存儲。（3）稀疏矩陣三元組 十字 鏈表以下各題實(shí)現(xiàn)深拷貝、矩陣相加（ addAll（） 和 union（） 見實(shí)驗(yàn)題 5-3）、比較相等、轉(zhuǎn)置等矩陣運(yùn)算。10-27 設(shè) CrossLinkedMatrix 矩陣類采用十字單鏈表存儲，見圖5.13。10-28 設(shè) CrossLinkedMatrix 矩陣類采用十字雙鏈表存儲，改進(jìn)圖5.13，每個(gè)結(jié)點(diǎn)增加指向行列前驅(qū)的指針。2.廣義表10-29 聲明以雙鏈表示的廣義表類 GenList ，實(shí)現(xiàn)廣義表的遍歷、插入、刪除、查找原子、比較相 等、復(fù)制等操作。10-30（ 4） 對二叉樹操作的靜態(tài)方法，使用棧的非遞歸算法（ 5） 表達(dá)式二叉樹表達(dá)式二叉

9、樹類 ExpressionBinaryTree （見例 6.3）聲明以下方法。 10-3810-39 其中，（6）10-40void createByPostfix （String postfix）void inorder （） / 輸出帶括號的中綴表達(dá)式， 使用散列映射存儲運(yùn)算符集合，快速查找指定運(yùn)算符的優(yōu)先級， 二叉樹的其他應(yīng)用存儲淘汰賽的比賽信息，創(chuàng)建表示比賽過程的滿二叉樹（教材圖/以后綴表達(dá)式構(gòu)造表達(dá)式二叉樹 算法必須比較運(yùn)算符優(yōu)先級的大小Java運(yùn)算符及其優(yōu)先級見附錄1.2），保存比賽結(jié)果。D。以廣義表雙鏈表示實(shí)現(xiàn) m 元多項(xiàng)式的相加、相乘等運(yùn)算。10.4.4二叉樹和樹1. 二叉樹（

10、二叉鏈表存儲結(jié)構(gòu)）（ 1） 二叉樹的成員方法，遞歸算法已知 BinaryTree 二叉樹類采用二叉鏈表存儲結(jié)構(gòu)，增加以下成員方法， public 權(quán)限。10-31 以先根和中根序列構(gòu)造二叉樹，替換其中所有與 pattern 匹配的子樹。成員方法聲明如下： BinaryTree （T prelist, T inlist）/ 以先根和中根序列構(gòu)造二叉樹void replaceAll （BinaryTree pattern, BinaryTree bitree） / 替換所有與 pattern 匹配子樹（深拷貝）10-32 以中根和后根序列構(gòu)造二叉樹，替換其中所有與 pattern 匹配的子樹。方法

11、聲明如下：BinaryTree （T inlist, T postlist）/ 以中根和后根序列構(gòu)造二叉樹（ 2） 二叉樹的成員方法，使用棧的非遞歸算法10-33 以先根和中根序列構(gòu)造二叉樹（使用棧的非遞歸算法），替換其中所有與 pattern 匹配的子樹。10-34 以中根和后根序列構(gòu)造二叉樹（使用棧的非遞歸算法），替換其中所有與 pattern 匹配的子樹。（ 3） 對二叉樹操作的靜態(tài)方法，遞歸算法10-35 以中根和后根序列構(gòu)造二叉樹，求二叉樹中兩結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)。方法聲明如下：T ancestor（BinaryTree bitree, T x, T y）/返回 x、 y 結(jié)點(diǎn)最近

12、的共同祖先結(jié)點(diǎn)10-36 以中根和后根序列構(gòu)造二叉樹，求一棵二叉樹的所有直徑及其路徑長度。方法聲明如下：void diameterAll （BinaryTree bitree）/ 輸出二叉樹的所有直徑及其路徑長度10-37 以中根和后根序列構(gòu)造一棵二叉樹，以層次序列構(gòu)造一棵完全二叉樹，調(diào)用以下方法：boolean isComplete（BinaryTree bitree）/ 判斷是否為完全二叉樹2. 二叉樹（三叉鏈表存儲結(jié)構(gòu)）（ 1） 二叉樹的成員方法，不使用棧的非遞歸算法10-41 BinaryTree （T prelist） 以標(biāo)明空子樹的先根序列構(gòu)造二叉樹（不使用棧的非遞歸算法） ，替換

13、 所有與 pattern 匹配的子樹。10-42BinaryTree （BinaryTree bitree） 深拷貝，不使用棧的非遞歸算法。10-43以中根和后根序列構(gòu)造二叉樹， printGenList （） 輸出二叉樹的廣義表表示（不使用棧的非遞歸算法）。（ 2） 對二叉樹操作的靜態(tài)方法，不使用棧的非遞歸算法10-44 以中根和后根序列構(gòu)造二叉樹，求二叉樹中兩結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)。10-45 以中根和后根序列構(gòu)造二叉樹，求二叉樹的所有直徑及其路徑長度（不使用棧的非遞歸算法）10-46BinaryTree createByGenList （String genlist）/以廣義表表示字符串

14、構(gòu)造二叉樹（ 3） 表達(dá)式二叉樹(1)10-5510-5610-5710-5810-5910-60樹的成員方法，遞歸算法void replaceAll(Tree pattern, Tree tree) void printGenList () boolean equalsIgnoreOrder (Tree tree) TreeNode search(Tree pattern) void removeAll (T re e pattern)/ 替換所有與 pattern 匹配子樹為 tree /輸出樹(森林)的廣義表表示字符串 /無序樹，比較是否相等，忽略孩子結(jié)點(diǎn)次序 /無序樹，查找匹配的子樹，

15、忽略孩子結(jié)點(diǎn)次序 /無序樹，刪除所有匹配的子樹，忽略孩子次序void replaceAll(Tree pattern, Tree tree)/無序樹，替換所有匹配子樹， 忽略孩子次序( 2) 樹的成員方法，非遞歸算法10-61void printGenList ()10-62void printGenList ()( 3) 對樹操作的靜態(tài)方法，遞歸算法10-63 T ancestor(Tree tree, T x, T y)10-64 void diameterAll (Tree tree)10-65Tree createGenList (String genlist)( 4) 對樹操作的靜態(tài)

16、方法，非遞歸算法10-66Tree createGenList (String genlist)10-67Tree createGenList (String genlist)6.樹(孩子兄弟鏈表存儲)/輸出樹的廣義表表示，使用棧的非遞歸算法/輸出樹的廣義表表示，不使用棧的非遞歸算法/返回 x、y 結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)/輸出樹的所有直徑及其路徑長度/ 返回以廣義表表示 genlist 構(gòu)造的樹(森林)/以廣義表構(gòu)造樹，使用棧的非遞歸算法/以廣義表構(gòu)造樹，不使用棧的非遞歸算法Tree樹類采用孩子兄弟鏈表存儲，方法聲明同上。10-47createByPostfix(String postfix)

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

18、，刪除指定結(jié)點(diǎn)的左孩子結(jié)點(diǎn)， 2 度結(jié)點(diǎn)用刪除結(jié)點(diǎn)的左孩子頂替，方法聲明如下。void remove()/刪除根，分別用左或右孩子頂替void remove(ThreadNode p, boolean leftChild)/刪除 p 的左或右孩子，用左或右孩子頂替void remove(ThreadNode p)/刪除以 p 結(jié)點(diǎn)為根的子樹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ì)其

19、中字符使用頻率(例8.3、例 8.5 )。 指定字符集合和權(quán)值集合創(chuàng)建一棵 Huffman 樹，獲得各字符的 Huffman 編碼(以多個(gè)二進(jìn)制位表示) 壓縮指定文件，計(jì)算壓縮比。 解壓縮文件，指定二進(jìn)制位文件，采用 Huffman 編碼對二進(jìn)制位序列進(jìn)行譯碼，獲得原文本文件。 10-54 采用 Huffman 編碼進(jìn)行文件壓縮，以單詞為單位進(jìn)行壓縮，統(tǒng)計(jì)單詞的使用頻率，單詞以 空格、標(biāo)點(diǎn)符號或回車換行符分隔。要求同上。5.樹(父母孩子兄弟鏈表存儲)Tree樹類采用父母孩子兄弟鏈表存儲。/ 替換所有與 pattern 匹配子樹為 tree/輸出樹（森林）的廣義表表示字符串 /無序樹，比較是否相

20、等，忽略孩子結(jié)點(diǎn)次序 /無序樹，查找匹配的子樹，忽略孩子結(jié)點(diǎn)次序 /無序樹，刪除所有匹配的子樹，忽略孩子次序/輸出樹的廣義表表示，使用棧的非遞歸算法/返回 x、y 結(jié)點(diǎn)最近的共同祖先結(jié)點(diǎn)/輸出樹的所有直徑及其路徑長度/以橫向凹入表示構(gòu)造樹/ 返回以廣義表表示 genlist 構(gòu)造的樹（森林）/以廣義表構(gòu)造樹，使用棧的非遞歸算法public 權(quán)限。/返回帶權(quán)圖的代價(jià)（無向圖每邊只計(jì)算一次） /返回帶權(quán)圖中權(quán)值最小的邊 /判斷是否完全圖/以頂點(diǎn)集合構(gòu)造一個(gè)完全圖 /拷貝構(gòu)造方法，深拷貝 /拷貝構(gòu)造方法，深拷貝/比較兩個(gè)圖是否相等，忽略頂點(diǎn)次序/判斷是否子圖/判斷是否生成子圖/判斷一個(gè)無向圖是否為連

21、通圖 /判斷一個(gè)有向圖是否為強(qiáng)連通圖 /判斷一個(gè)無向圖是否為一棵樹 /判斷由頂點(diǎn)序列表示的一條路徑是否為回路 /判斷由單鏈表存儲的頂點(diǎn)序列是否是圖的一條路徑 vi、vj 之間的所有路徑及其路徑長度， 回溯法（10.3.4 節(jié)） vi 出發(fā)的所有深度優(yōu)先搜索的遍歷路徑（圖 7.23），回溯法/比較兩個(gè)圖是否相等，忽略頂點(diǎn)次序/判斷是否子圖/ 判斷是否子圖， graph 圖鄰接矩陣存儲1） 樹的成員方法，遞歸算法10-68 void replaceAll (Tree pattern, Tree tree)10-69 void printGenList ()10-70 boolean equalsI

22、gnoreOrder (Tree tree)10-71 TreeNode search(Tree pattern)10-72 void removeAll (Tree pattern)10-73void replaceAll (Tree pattern, Tree tree) /無序樹，替換所有匹配子樹， 忽略孩子次序( 2) 樹的成員方法，非遞歸算法10-74 void printGenList ()( 3) 對樹操作的靜態(tài)方法，遞歸算法10-75 T ancestor(Tree tree, T x, T y)10-76 void diameterAll (Tree tree)10-77 T

23、ree create(String prelist)10-78Tree createGenList (String genlist)( 4) 對樹操作的靜態(tài)方法，非遞歸算法10-79Tree createGenList (String genlist)10.4.5圖1.圖的鄰接表存儲帶權(quán)圖類 實(shí)現(xiàn) AdjListGraph 類聲明的以下成員方法， 10-80 int cost()10-81 Triple minWeightEgde ()10-82 boolean isComplete()10-83 AdjListGraph createComplete (T vertices)10-84 Ad

24、jListGraph (AdjListGraph graph)10-85 AdjListGraph (MatrixGraph graph)2. 抽象圖類關(guān)于圖的連通性操作( 1) 實(shí)現(xiàn) AbstractGraph 類以下對圖的操作，圖的鄰接矩陣存儲。10-86 boolean equals(Object obj)10-87 boolean isSubgraph (AbstractGraph graph)10-88 boolean isSpanSubgraph (AbstractGraph graph)10-89 boolean stronglyConnected()10-90 boolean

25、stronglyConnected()10-91 boolean isTree()10-92 boolean isCyclePath (int vertexs)10-93 boolean isPath(SinglyList pathlink)10-94 void printPathAll (int i, int j) / 輸出頂點(diǎn)10-95 void printPathAll (int i)/ 輸出從頂點(diǎn)2） 實(shí)現(xiàn) AbstractGraph 類以下對圖的操作，圖的鄰接表存儲。10-96boolean equals(Object obj)10-97boolean isSubgraph (Abs

26、tractGraph graph)10-98boolean isSubgraph(MatrixGraph graph)Prim 算法求圖的最小生成樹。Kruskal 算法求圖的最小生成樹。Dijkstra 算法求圖的單源最短路徑。Floyd 算法求圖所有頂點(diǎn)間的最短路徑。10-99boolean isSpanSubgraph(AbstractGraph graph)/ 判斷是否生成子圖10-100 boolean isSpanSubgraph(MatrixGraph graph) / 判斷是否生成子圖， graph 鄰接矩陣存儲10-101boolean stronglyConnected()

27、/判斷一個(gè)無向圖是否為連通圖10-102boolean stronglyConnected()/判斷一個(gè)有向圖是否為強(qiáng)連通圖10-103boolean isTree()/ 判斷一個(gè)無向圖是否為一棵樹10-104boolean isCyclePath (int vertexs)/ 判斷由頂點(diǎn)序列表示的一條路徑是否為回路10-105boolean isPath(SinglyList pathlink)/判斷由單鏈表存儲的頂點(diǎn)序列是否是圖的一條路徑10-106 void printPathAII (int i, int j)/輸出W、Vj之間的所有路徑及其路徑長度，回溯法(10.3.4節(jié))10-10

28、7void printPathAII (int i) /輸出從V出發(fā)的所有深度優(yōu)先搜索的遍歷路徑(圖 7.23),回溯法3.圖的鄰接多重表存儲1 ) 以鄰接多重表存儲帶權(quán)無向圖10-108以鄰接多重表存儲帶權(quán)無向圖，實(shí)現(xiàn)插入、刪除、遍歷操作算法。10-109void printPathAII (int i) /輸出從頂點(diǎn)W出發(fā)的所有深度優(yōu)先搜索的遍歷路徑(圖 7.23)10-110以鄰接多重表存儲帶權(quán)無向圖，采用10-111以鄰接多重表存儲帶權(quán)無向圖，采用10-112以鄰接多重表存儲帶權(quán)無向圖，采用10-113以鄰接多重表存儲帶權(quán)無向圖，采用2) 以鄰接多重表存儲帶權(quán)有向圖10-114以鄰接多

29、重表存儲帶權(quán)有向圖，實(shí)現(xiàn)插入、刪除、遍歷操作算法。10-115void printPathAII (int i) /輸出從頂點(diǎn)w出發(fā)的所有深度優(yōu)先搜索的遍歷路徑(圖 7.23)10-116以鄰接多重表存儲帶權(quán)有向圖，采用 Dijkstra 算法求圖的單源最短路徑。10-117以鄰接多重表存儲帶權(quán)有向圖，采用 Floyd 算法求圖所有頂點(diǎn)間的最短路徑。4.圖的應(yīng)用10-118 繪制一個(gè)由若干城市的航班路線構(gòu)成的帶權(quán)有向圖(圖1.3)，連接兩城市的邊表示兩地是否開通航班，有直飛或經(jīng)停，邊的權(quán)值表示兩地間價(jià)格。指定兩城市，給出多種航班路線方案，在何地中轉(zhuǎn)， 標(biāo)明最短路徑。10-119繪制一個(gè)由若干貨

30、幣的匯率關(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公共交通信息綜合查詢，題詳見教材 10.4節(jié)。10.4.6查找1. 查找設(shè)計(jì)1 ) 散列10-122HashSet散列表類聲明實(shí)現(xiàn) Set接口(見1.1.3節(jié))，實(shí)現(xiàn)集合相等、包含、并、差、交等集合運(yùn)

31、算，以及讀寫對象文件操作。10-123 實(shí)現(xiàn) HashMap 散列映射類的 keySet()、values()等方法。( 2) 二叉排序樹10-124 BinarySortTree subSet(T begin, T end)返回取值在 begin end 范圍內(nèi)的子樹，深拷貝10-125 boolean isSubtree(BinarySortTree bstree) 判斷 bstree表示排序集合是否是 this 的子集10-126 void printASL （）/輸出ASL成功的計(jì)算公式（顯示每層的查找次數(shù)能吉點(diǎn)個(gè)數(shù)）及結(jié)果10-127BinarySortTree二叉排序樹類聲明實(shí)現(xiàn)

32、Set接口，實(shí)現(xiàn)集合相等、包含、并、差、交等集合運(yùn)算。10-128 實(shí)現(xiàn) TreeMap 樹映射類的 keySet（）、values（）等方法。（ 3） 平衡二叉樹10-129聲明平衡二叉樹類 AVL ，實(shí)現(xiàn)平衡二叉樹的插入、刪除和查找等操作。使用平衡二叉樹存儲互異的排序隨機(jī)數(shù)序列，分析其特點(diǎn)、功能和查找效率。2.查找應(yīng)用（ 1 ） 提供快速查詢的存儲技術(shù)10-130 電話簿，按姓氏分塊存儲。采用索引單鏈表（圖8.8）結(jié)構(gòu)，實(shí)現(xiàn)以下功能，分析算法效率。 索引表按姓氏排序，采用排序單鏈表或排序循環(huán)雙鏈表存儲。 主表按姓氏分塊存儲，各塊按姓名排序，提供查找、插入、刪除操作，可存儲一人多號，采用排序單 /循環(huán)雙鏈表存儲。 提供讀寫對象文件操作。10-131電話簿，按姓氏分塊存儲，用散列表作為索引表和主表，不排序，要求同上。10-132電話簿，按姓氏分塊存儲，采用二叉排序樹作為索引表和主表，要求同上題。10-133電話簿，按樹形關(guān)系分塊存儲，實(shí)現(xiàn)以下功能，分析算法效率。 索引表是樹結(jié)構(gòu)，顯示人物關(guān)系分類，以廣義表表示一棵樹。例如：全部（家人，同學(xué)（中學(xué)同學(xué)，大學(xué)同學(xué)，研究生同學(xué)） ，同事（計(jì)算機(jī)系，通信系） ，朋友）