内容发布更新时间 : 2024/11/18 2:30:05星期一 下面是文章的全部内容请认真阅读。
第10章 课程设计
10.4 课程设计选题
课程设计的目的、要求和选题详见教材10.4节，及课程设计任务书。
10.4.1 线性表
1. 多项式的表示和运算 题意详见教材2.4节。
（1） 使用排序单链表存储多项式
10-1 ?一元多项式相加，PolySinglyList
//多项式相加，返回this＋list的多项式，不改变this和list，C(x)=A(x)＋B(x)。
//算法不调用深拷贝，将this（A）和list（B）中的所有结点合并（相加）到C多项式单链表 PolySinglyList
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
PolyDoublyList
10-7 ?一元多项式相乘，声明PolyDoublyList
Polynomial multi(Polynomial poly) //返回相乘的多项式 10-8 ?二元多项式相乘，实现10-7题。
10.4.2 栈和队列及递归算法
1. 计算表达式值
在例4.2、例4.6计算算术表达式值的基础上，增加以下功能。 ⑴ 检查表达式语法是否正确。
⑵ 使用散列映射存储运算符集合，建立从运算符到优先级的映射，快速查找指定运算符的优先级。运算
符集合包括位运算符、关系运算符、逻辑运算符、字符串连接运算符等，各运算符的优先级见附录D。
⑶ 整数表达式增加位运算功能。
⑷ 计算逻辑表达式、字符表达式、字符串表达式等，BNF定义见教材实验4-12。
- 0 -
⑸ 以浮点数作为常数，所求算术表达式值为浮点数类型。
⑹ 增加标识符作为变量，识别标识符，为变量赋值。使用散列映射存储变量集合，快速查找指定变量的值。
⑺ 采用文件保存多行表达式字符串，读取表达式，并将结果写入文件。
10-9 ??计算表达式值。改进例4.2，同时使用运算符栈和操作数栈，省略转换成后缀表达式过程；增加运算符、浮点数等功能。
10-10 ???计算表达式值，递归算法。改进例4.6，增加运算符、浮点数等功能。 10-11 ?????带变量的表达式求值，使用栈，增加运算符、浮点数等功能。 10-12 ?????带变量的表达式求值，递归算法，增加运算符、浮点数等功能。
10-13 ??给定一个初始序列，求解素数环问题（例4.3）的所有解，采用回溯法（10.3.4节）。 2. 走迷宫
迷宫题见实验4-13，指定迷宫大小、入口及出口位置和初始状态等，求解一条或多条路径，演示走迷宫过程，显示一条或多条结果路径。
10-14 ??走迷宫，使用栈。 10-15 ??走迷宫，使用队列。 10-16 ??走迷宫，递归算法。
10-17 ??走迷宫求所有路径，采用回溯法（10.3.4节）。
10-18 ??骑士游历问题（见实验题4-18）求多个解，采用回溯法（10.3.4节）。
10.4.3 矩阵和广义表
1. 稀疏矩阵的压缩存储及运算
以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、转置等矩阵运算。 （1） 稀疏矩阵三元组行的排序单/双链表
10-19 ?设LinkedMatrix矩阵类采用行的排序单链表存储（见实验题5-4）。
10-20 ??设LinkedMatrix矩阵类采用行的多项式排序单链表PolySinglyList
10-23 ?设LinkedMatrix矩阵类采用列的排序单链表存储（见实验题5-4）。
10-24 ??设LinkedMatrix矩阵类采用列的多项式排序单链表PolySinglyList
以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、比较相等、转置等矩阵运算。 10-27 ???设CrossLinkedMatrix矩阵类采用十字单链表存储，见图5.13。
10-28 ????设CrossLinkedMatrix矩阵类采用十字双链表存储，改进图5.13，每个结点增加指向行列前驱的指针。
2. 广义表
10-29 ???声明以双链表示的广义表类GenList，实现广义表的遍历、插入、删除、查找原子、比较相等、复制等操作。
- 1 -
10-30 ???以广义表双链表示实现m元多项式的相加、相乘等运算。
10.4.4 二叉树和树
1. 二叉树（二叉链表存储结构）
（1） 二叉树的成员方法，递归算法
已知BinaryTree
//以先根和中根序列构造二叉树 BinaryTree(T prelist[], T inlist[])
void replaceAll(BinaryTree
BinaryTree(T inlist[], T postlist[])
//以中根和后根序列构造二叉树
（2） 二叉树的成员方法，使用栈的非递归算法
10-32 ?以先根和中根序列构造二叉树（使用栈的非递归算法），替换其中所有与pattern匹配的子树。 10-33 ?以中根和后根序列构造二叉树（使用栈的非递归算法），替换其中所有与pattern匹配的子树。 （3） 对二叉树操作的静态方法，递归算法
10-34 ?以中根和后根序列构造二叉树，求二叉树中两结点最近的共同祖先结点。方法声明如下：
T ancestor(BinaryTree
//返回x、y结点最近的共同祖先结点 //输出二叉树的所有直径及其路径长度
10-35 ?以中根和后根序列构造二叉树，求一棵二叉树的所有直径及其路径长度。方法声明如下： 10-36 ??以中根和后根序列构造一棵二叉树，以层次序列构造一棵完全二叉树，调用以下方法：
boolean isComplete(BinaryTree
（5） 表达式二叉树
表达式二叉树类ExpressionBinaryTree（见例6.3）声明以下方法。
10-37 ??? void createByPostfix(String postfix) //以后缀表达式构造表达式二叉树 10-38 ??? void inorder() //输出带括号的中缀表达式，算法必须比较运算符优先级的大小 其中，使用散列映射存储运算符集合，快速查找指定运算符的优先级，Java运算符及其优先级见附录D。（6） 二叉树的其他应用
10-39 ?存储淘汰赛的比赛信息，创建表示比赛过程的满二叉树（教材图1.2），保存比赛结果。 2. 二叉树（三叉链表存储结构）
（1） 二叉树的成员方法，不使用栈的非递归算法
10-40 ??BinaryTree(T prelist[])以标明空子树的先根序列构造二叉树（不使用栈的非递归算法），替换所有与pattern匹配的子树。
10-41 ???BinaryTree(BinaryTree
10-42 ???以中根和后根序列构造二叉树，printGenList()输出二叉树的广义表表示（不使用栈的非递归算法）。
（2） 对二叉树操作的静态方法，不使用栈的非递归算法
10-43 ?以中根和后根序列构造二叉树，求二叉树中两结点最近的共同祖先结点。
10-44 ?以中根和后根序列构造二叉树，求二叉树的所有直径及其路径长度（不使用栈的非递归算法） 。10-45 ????BinaryTree
- 2 -