《数据结构(Java版)(第4版)》设计题论述.docVIP

课程设计 课程设计选题 课程设计的目的、要求和选题详见教材10.4节，及课程设计任务书。 线性表 多项式的表示和运算 题意详见教材2.4节。 使用排序单链表存储多项式 (一元多项式相加，PolySinglyListT多项式排序单链表类增加以下成员方法，public权限。 //多项式相加，返回this＋list的多项式，不改变this和list，C(x)=A(x)＋B(x)。 //算法不调用深拷贝，将this（A）和list（B）中的所有结点合并（相加）到C多项式单链表 PolySinglyListT union(PolySinglyListT list) (二元多项式相加，实现10-1题。 (一元多项式相乘，Polynomial多项式类增加以下成员方法。 public boolean equals(Object obj) //比较两个多项式是否相等，覆盖 public Polynomial multi(Polynomial poly) //相乘，返回this*poly的多项式 (二元多项式相乘，实现10-3题。 使用排序循环双链表存储多项式 (一元多项式相加，声明PolyDoublyListT多项式排序循环双链表类，继承排序循环双链表类，方法声明如下。Polynomial多项式类使用PolyDoublyListT对象作为成员变量。 PolyDoublyListT union(PolyDoublyListT list) //返回相加的多项式，不调用深拷贝 (二元多项式相加，实现10-5题。 (一元多项式相乘，声明PolyDoublyListT多项式排序循环双链表类，继承排序循环双链表类，实现二元多项式相乘运算，方法声明如下。Polynomial多项式类使用PolyDoublyListT对象作为成员变量。 Polynomial multi(Polynomial poly) //返回相乘的多项式 (二元多项式相乘，实现10-7题。 栈和队列及递归算法 计算表达式值 在例4.2、例4.6计算算术表达式值的基础上，增加以下功能。 ⑴ 检查表达式语法是否正确。 ⑵ 使用散列映射存储运算符集合，建立从运算符到优先级的映射，快速查找指定运算符的优先级。运算符集合包括位运算符、关系运算符、逻辑运算符、字符串连接运算符等，各运算符的优先级见附录D。 ⑶ 整数表达式增加位运算功能。 ⑷ 计算逻辑表达式、字符表达式、字符串表达式等，BNF定义见教材实验4-12。 ⑸ 以浮点数作为常数，所求算术表达式值为浮点数类型。 ⑹ 增加标识符作为变量，识别标识符，为变量赋值。使用散列映射存储变量集合，快速查找指定变量的值。 ⑺ 采用文件保存多行表达式字符串，读取表达式，并将结果写入文件。 ((计算表达式值。改进例4.2，同时使用运算符栈和操作数栈，省略转换成后缀表达式过程；增加运算符、浮点数等功能。 (((计算表达式值，递归算法。改进例4.6，增加运算符、浮点数等功能。 (((((带变量的表达式求值，使用栈，增加运算符、浮点数等功能。 (((((带变量的表达式求值，递归算法，增加运算符、浮点数等功能。 ((给定一个初始序列，求解素数环问题（例4.3）的所有解，采用回溯法（10.3.4节）。 走迷宫 迷宫题见实验4-13，指定迷宫大小、入口及出口位置和初始状态等，求解一条或多条路径，演示走迷宫过程，显示一条或多条结果路径。 ((走迷宫，使用栈。 ((走迷宫，使用队列。 ((走迷宫，递归算法。 ((走迷宫求所有路径，采用回溯法（10.3.4节）。 ((骑士游历问题（见实验题4-18）求多个解，采用回溯法（10.3.4节）。 矩阵和广义表 稀疏矩阵的压缩存储及运算 以下各题实现深拷贝、矩阵相加（addAll()和union()见实验题5-3）、转置等矩阵运算。 稀疏矩阵三元组行的排序单/双链表 (设LinkedMatrix矩阵类采用行的排序单链表存储（见实验题5-4）。 ((设LinkedMatrix矩阵类采用行的多项式排序单链表PolySinglyListTriple（见2.4节）存储。 (设LinkedMatrix矩阵类采用行的排序循环双链表存储。 ((设LinkedMatrix矩阵类采用行的多项式排序循环双链表存储。 稀疏矩阵三元组列的排序单/双链表 (设LinkedMatrix矩阵类采用列的排序单链表存储（见实验题5-4）。 ((设LinkedMatrix矩阵类采用列的多项式排序单链表PolySinglyListTriple（见2.4节）存储。 (设LinkedMatrix矩阵类采用列的排序循环双链表存储。 ((设LinkedM