《数据结构(Java版)(第4版)》课程设计题

1、第10章 课程设计10.4 课程设计选题课程设计的目的、要求和选题详见教材10.4节，及课程设计任务书。10.4.1 线性表1. 多项式的表示和运算题意详见教材2.4节。（1） 使用排序单链表存储多项式10-1 ¶一元多项式相加，PolySinglyList<T>多项式排序单链表类增加以下成员方法，public权限。/多项式相加，返回thislist的多项式，不改变this和list，C(x)=A(x)B(x)。/算法不调用深拷贝，将this（A）和list（B）中的所有结点合并（相加）到C多项式单链表PolySinglyList<T> union(PolyS

2、inglyList<T> list)10-2 ¶二元多项式相加，实现10-1题。10-3 ¶一元多项式相乘，Polynomial多项式类增加以下成员方法。public boolean equals(Object obj) /比较两个多项式是否相等，覆盖public Polynomial multi(Polynomial poly) /相乘，返回this*poly的多项式10-4 ¶二元多项式相乘，实现10-3题。（2） 使用排序循环双链表存储多项式10-5 ¶一元多项式相加，声明PolyDoublyList<T>多项式排序循环双链

3、表类，继承排序循环双链表类，方法声明如下。Polynomial多项式类使用PolyDoublyList<T>对象作为成员变量。PolyDoublyList<T> union(PolyDoublyList<T> list) /返回相加的多项式，不调用深拷贝10-6 ¶二元多项式相加，实现10-5题。10-7 ¶一元多项式相乘，声明PolyDoublyList<T>多项式排序循环双链表类，继承排序循环双链表类，实现二元多项式相乘运算，方法声明如下。Polynomial多项式类使用PolyDoublyList<T>对象作

4、为成员变量。Polynomial multi(Polynomial poly) /返回相乘的多项式10-8 ¶二元多项式相乘，实现10-7题。10.4.2 栈和队列及递归算法1. 计算表达式值在例4.2、例4.6计算算术表达式值的基础上，增加以下功能。 检查表达式语法是否正确。 使用散列映射存储运算符集合，建立从运算符到优先级的映射，快速查找指定运算符的优先级。运算符集合包括位运算符、关系运算符、逻辑运算符、字符串连接运算符等，各运算符的优先级见附录D。 整数表达式增加位运算功能。 计算逻辑表达式、字符表达式、字符串表达式等，BNF定义见教材实验4-12。 以浮点数作为常数，所求算术

5、表达式值为浮点数类型。 增加标识符作为变量，识别标识符，为变量赋值。使用散列映射存储变量集合，快速查找指定变量的值。 采用文件保存多行表达式字符串，读取表达式，并将结果写入文件。10-9 ¶¶计算表达式值。改进例4.2，同时使用运算符栈和操作数栈，省略转换成后缀表达式过程；增加运算符、浮点数等功能。10-10 ¶¶¶计算表达式值，递归算法。改进例4.6，增加运算符、浮点数等功能。10-11 ¶¶¶¶¶带变量的表达式求值，使用栈，增加运算符、浮点数等功能。10-12 ¶¶

6、82;¶¶带变量的表达式求值，递归算法，增加运算符、浮点数等功能。10-13 ¶¶给定一个初始序列，求解素数环问题（例4.3）的所有解，采用回溯法（10.3.4节）。2. 走迷宫迷宫题见实验4-13，指定迷宫大小、入口及出口位置和初始状态等，求解一条或多条路径，演示走迷宫过程，显示一条或多条结果路径。10-14 ¶¶走迷宫，使用栈。10-15 ¶¶走迷宫，使用队列。10-16 ¶¶走迷宫，递归算法。10-17 ¶¶走迷宫求所有路径，采用回溯法（10.3.4节）。10-18 &

7、#182;¶骑士游历问题（见实验题4-18）求多个解，采用回溯法（10.3.4节）。10.4.3 矩阵和广义表1. 稀疏矩阵的压缩存储及运算以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、转置等矩阵运算。（1） 稀疏矩阵三元组行的排序单/双链表10-19 ¶设LinkedMatrix矩阵类采用行的排序单链表存储（见实验题5-4）。10-20 ¶¶设LinkedMatrix矩阵类采用行的多项式排序单链表PolySinglyList<Triple>（见2.4节）存储。10-21 ¶设LinkedMatri

8、x矩阵类采用行的排序循环双链表存储。10-22 ¶¶设LinkedMatrix矩阵类采用行的多项式排序循环双链表存储。（2） 稀疏矩阵三元组列的排序单/双链表10-23 ¶设LinkedMatrix矩阵类采用列的排序单链表存储（见实验题5-4）。10-24 ¶¶设LinkedMatrix矩阵类采用列的多项式排序单链表PolySinglyList<Triple>（见2.4节）存储。10-25 ¶设LinkedMatrix矩阵类采用列的排序循环双链表存储。10-26 ¶¶设LinkedMatrix矩阵类采用

9、列的多项式排序循环双链表存储。（3） 稀疏矩阵三元组十字链表以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、比较相等、转置等矩阵运算。10-27 ¶¶¶设CrossLinkedMatrix矩阵类采用十字单链表存储，见图5.13。10-28 ¶¶¶¶设CrossLinkedMatrix矩阵类采用十字双链表存储，改进图5.13，每个结点增加指向行列前驱的指针。2. 广义表10-29 ¶¶¶声明以双链表示的广义表类GenList，实现广义表的遍历、插入、删除、查找原子、

10、比较相等、复制等操作。 10-30 ¶¶¶以广义表双链表示实现m元多项式的相加、相乘等运算。10.4.4 二叉树和树1. 二叉树（二叉链表存储结构）（1） 二叉树的成员方法，递归算法已知BinaryTree<T>二叉树类采用二叉链表存储结构，增加以下成员方法，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） 对二叉树操作的静态

12、方法，递归算法10-35 ¶以中根和后根序列构造二叉树，求二叉树中两结点最近的共同祖先结点。方法声明如下：T ancestor(BinaryTree<T> bitree, T x, T y) /返回x、y结点最近的共同祖先结点10-36 ¶以中根和后根序列构造二叉树，求一棵二叉树的所有直径及其路径长度。方法声明如下：void diameterAll(BinaryTree<T> bitree) /输出二叉树的所有直径及其路径长度10-37 ¶¶以中根和后根序列构造一棵二叉树，以层次序列构造一棵完全二叉树，调用以下方法：boolean

13、 isComplete(BinaryTree<T> bitree) /判断是否为完全二叉树（4） 对二叉树操作的静态方法，使用栈的非递归算法（5） 表达式二叉树表达式二叉树类ExpressionBinaryTree（见例6.3）声明以下方法。10-38 ¶¶¶ void createByPostfix(String postfix) /以后缀表达式构造表达式二叉树10-39 ¶¶¶ void inorder() /输出带括号的中缀表达式，算法必须比较运算符优先级的大小其中，使用散列映射存储运算符集合，快速查找指定运算符的优

14、先级，Java运算符及其优先级见附录D。（6） 二叉树的其他应用10-40 ¶存储淘汰赛的比赛信息，创建表示比赛过程的满二叉树（教材图1.2），保存比赛结果。2. 二叉树（三叉链表存储结构）（1） 二叉树的成员方法，不使用栈的非递归算法10-41 ¶¶BinaryTree(T prelist)以标明空子树的先根序列构造二叉树（不使用栈的非递归算法），替换所有与pattern匹配的子树。10-42 ¶¶¶BinaryTree(BinaryTree<T> bitree)深拷贝，不使用栈的非递归算法。10-43 ¶&#

15、182;¶以中根和后根序列构造二叉树，printGenList()输出二叉树的广义表表示（不使用栈的非递归算法）。（2） 对二叉树操作的静态方法，不使用栈的非递归算法10-44 ¶以中根和后根序列构造二叉树，求二叉树中两结点最近的共同祖先结点。10-45 ¶以中根和后根序列构造二叉树，求二叉树的所有直径及其路径长度（不使用栈的非递归算法）。10-46 ¶¶¶¶BinaryTree<String> createByGenList(String genlist) /以广义表表示字符串构造二叉树（3） 表达式二叉树10

16、-47 ¶¶¶ createByPostfix(String postfix) /以后缀表达式构造表达式二叉树10-48 ¶¶¶ inorder() /输出带括号的中缀表达式，使用散列映射存储运算符集合3. 线索二叉树以下对中序线索二叉树操作的算法描述见习题解答6.3节。10-49 ¶ ThreadNode<T> parent(ThreadNode<T> node) /返回node结点的父母结点10-50 ¶插入根，插入左/右孩子操作，方法声明如下。void add(T x) /插入x作为根

17、结点，原根作为x的左孩子ThreadNode<T> add(ThreadNode<T> p, T x, boolean leftChild) /插入x作为p的左/右孩子结点10-51 ¶¶删除根，删除指定结点的左孩子结点，2度结点用删除结点的左孩子顶替，方法声明如下。void remove() /删除根，分别用左或右孩子顶替void remove(ThreadNode<T> p, boolean leftChild) /删除p的左或右孩子，用左或右孩子顶替void remove(ThreadNode<T> p) /删除以p结点

18、为根的子树10-52 ¶¶删除根，删除指定结点的右孩子结点，2度结点用删除结点的右孩子顶替，画出算法描述图。4. Huffman树10-53 ¶¶¶采用Huffman编码进行文件压缩，以字符为单位进行压缩，统计字符使用频率。 指定一个文本文件，采用散列映射或树映射统计其中字符使用频率（例8.3、例8.5）。 指定字符集合和权值集合创建一棵Huffman树，获得各字符的Huffman编码（以多个二进制位表示）。 压缩指定文件，计算压缩比。 解压缩文件，指定二进制位文件，采用Huffman编码对二进制位序列进行译码，获得原文本文件。10-54 &#

19、182;¶¶采用Huffman编码进行文件压缩，以单词为单位进行压缩，统计单词的使用频率，单词以空格、标点符号或回车换行符分隔。要求同上。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) /无序树，比较是否相等，忽略孩子结点次序10-58 TreeNode<T> search(Tree<T> pattern) /无序树，查找匹配的子树，忽略孩子结点次序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） 对树操作的静态方法，递归算法10-63 T ancestor(Tree<T> tree, T x, T y) /返回x、y结点最近的共同祖先结点10-64 <T> void diameterAll(Tree<T> tree

22、) /输出树的所有直径及其路径长度10-65 ¶¶¶Tree<String> createGenList(String genlist) /返回以广义表表示genlist构造的树（森林）（4） 对树操作的静态方法，非递归算法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、子结点次序10-71 TreeNode<T> search(Tree<T> pattern) /无序树，查找匹配的子树，忽略孩子结点次序10-72 ¶¶void removeAll(Tree<T> pattern) /无序树，删除所有匹配的子树，忽略孩子次序10-73 ¶¶¶void replaceAll(Tree<T> pattern, Tree<T> tree) /无序树，替换所有匹配子树，忽略孩子次序（2） 树的成员方法，非递归算法10-74 ¶¶¶

25、 void printGenList() /输出树的广义表表示，使用栈的非递归算法（3） 对树操作的静态方法，递归算法10-75 T ancestor(Tree<T> tree, T x, T y) /返回x、y结点最近的共同祖先结点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） 对树操作的静态方法，非递归算法10-79 ¶¶¶Tree<String> createGenList(String genlist) /以广义表构造树，使用栈的非递归算法10.4.5 图1. 图的邻接表存储带权图类实现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） 实现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节）10-95 ¶¶void printPathA

30、ll(int i)/输出从顶点出发的所有深度优先搜索的遍历路径（图7.23），回溯法（2） 实现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节)10-107 ¶¶¶void printPathAll(int i) /输出从出发的所有深度优先搜索的遍历路径（图7.23），回溯法3. 图的邻接多重表存储（1） 以邻接多重表存储带权无向图10-108 ¶¶¶以邻接多重表存储带权无向图，实现插入、删除、遍历操作算法。10-109 ¶¶¶¶void printPathAll(int i) /输出从顶点出发的所有深度优先搜索的遍历路径（图7.23）10-110 ¶¶¶¶以邻接多重表存储带权无向图，采用

34、Prim算法求图的最小生成树。10-111 ¶¶¶¶¶以邻接多重表存储带权无向图，采用Kruskal算法求图的最小生成树。10-112 ¶¶¶¶以邻接多重表存储带权无向图，采用Dijkstra算法求图的单源最短路径。10-113 ¶¶¶¶¶以邻接多重表存储带权无向图，采用Floyd算法求图所有顶点间的最短路径。（2） 以邻接多重表存储带权有向图10-114 ¶¶¶以邻接多重表存储带权有向图，实现插入、删除、遍历操作算法。10-

35、115 ¶¶¶¶void printPathAll(int i) /输出从顶点出发的所有深度优先搜索的遍历路径（图7.23）10-116 ¶¶¶¶以邻接多重表存储带权有向图，采用Dijkstra算法求图的单源最短路径。10-117 ¶¶¶¶¶以邻接多重表存储带权有向图，采用Floyd算法求图所有顶点间的最短路径。4. 图的应用10-118 ¶¶¶绘制一个由若干城市的航班路线构成的带权有向图（图1.3），连接两城市的边表示两地是否开通航班

36、，有直飞或经停，边的权值表示两地间价格。指定两城市，给出多种航班路线方案，在何地中转，标明最短路径。10-119 ¶¶¶绘制一个由若干货币的汇率关系构成的带权有向图，如人民币、美元、欧元、英镑、加元、澳元等，有向边表示汇率关系。有些货币之间无法直接兑换，需要由第三方中转。指定两种货币的若干金额，给出转换结果，由第三方中转的多种方案。例如，将100美元转换成多少人民币；将1000人民币转换成多少土耳其里拉，需要由美元或欧元中转，标明最佳转换方案。10-120 地铁计费，题详见教材10.4节。10-121 ¶¶¶¶公共交通信息综

37、合查询，题详见教材10.4节。10.4.6 查找1. 查找设计（1） 散列10-122 ¶¶HashSet<T>散列表类声明实现Set<T>接口（见1.1.3节），实现集合相等、包含、并、差、交等集合运算，以及读写对象文件操作。10-123 ¶¶实现HashMap<K,V>散列映射类的keySet()、values()等方法。（2） 二叉排序树10-124 BinarySortTree<T> subSet(T begin, T end) /返回取值在beginend范围内的子树，深拷贝10-125 bool

38、ean isSubtree(BinarySortTree<T> bstree) /判断bstree表示排序集合是否是this的子集10-126 void printASL() /输出的计算公式（显示每层的查找次数×结点个数）及结果10-127 ¶¶BinarySortTree<T>二叉排序树类声明实现Set<T>接口，实现集合相等、包含、并、差、交等集合运算。10-128 ¶¶实现TreeMap<K,V>树映射类的keySet()、values()等方法。（3） 平衡二叉树10-129 ¶

39、;¶¶¶声明平衡二叉树类AVL，实现平衡二叉树的插入、删除和查找等操作。使用平衡二叉树存储互异的排序随机数序列，分析其特点、功能和查找效率。2. 查找应用（1） 提供快速查询的存储技术10-130 ¶¶电话簿，按姓氏分块存储。采用索引单链表（图8.8）结构，实现以下功能，分析算法效率。 索引表按姓氏排序，采用排序单链表或排序循环双链表存储。 主表按姓氏分块存储，各块按姓名排序，提供查找、插入、删除操作，可存储一人多号，采用排序单/循环双链表存储。 提供读写对象文件操作。10-131 ¶¶电话簿，按姓氏分块存储，用散列表作为索引表和主表，不排序，要求同上。10-132 ¶¶电话簿，按姓氏分块存储，采用二叉排序树作为索引表和主表，要求同上题。10-133 ¶