1、数据结构课程设计报告数据结构课程设计报告 姓名姓名 学号学号 2009 2009 级级 7 7 组组 实验室：实验室： 提交日期提交日期 成绩成绩 指导教师指导教师 实验题目：实验题目： 多项式计算器多项式计算器 问题解析（对问题的分析、理解和解题方法） ：问题解析（对问题的分析、理解和解题方法） ： 我们先对数据结构进行了分析，对其运算进行了详细的分解。我们先对数据结构进行了分析，对其运算进行了详细的分解。 我们把整个程序我们分为我们把整个程序我们分为 6 6 个部分加减法，乘法，除法，排序整理，多项式解析，输入个部分加减法，乘法，除法，排序整理，多项式解析，输入 输出的格式及用户界面。输出
2、的格式及用户界面。 一一 1. 1. 多元多项式加法：直接加，进行排序整理。多元多项式加法：直接加，进行排序整理。 2. 2. 多元多项式减法即加法的取反运算。多元多项式减法即加法的取反运算。 3. 3. 如何进行解析是一个难点，我们中如何进行解析是一个难点，我们中序表达式转后序表达式的方法进行解析。序表达式转后序表达式的方法进行解析。 二二 4.4. 多元多项式乘法是前一个多项式的每一项与后一项的每一项相乘相加，然后排序整多元多项式乘法是前一个多项式的每一项与后一项的每一项相乘相加，然后排序整 理。理。 5. 5. 由于上述分析中提到对多项式进行排序整理，则我们就要先写一个由于上述分析中提到
3、对多项式进行排序整理，则我们就要先写一个 sort()sort()的函数，的函数， 对多项式进行排序整理。 其原理是按照其中一个字母的次数的降次排序， 使用的是冒泡算法。对多项式进行排序整理。 其原理是按照其中一个字母的次数的降次排序， 使用的是冒泡算法。 三三 6. 6. 一元多项式除法即比较前一项与后一项的最高次数一元多项式除法即比较前一项与后一项的最高次数, ,若被除数的最高次数大于等于若被除数的最高次数大于等于 除数的最高次数除数的最高次数, ,则被除数的用最高次项除以除数的最高次项则被除数的用最高次项除以除数的最高次项, ,得到一个临时的商得到一个临时的商. .再用被除再用被除 数减
4、去这个商乘以除数的积作为新的被除数。如此循环数减去这个商乘以除数的积作为新的被除数。如此循环，就可以得到商。，就可以得到商。 7. 7. 一元多项式的模，模就是除法中最后的被除数。一元多项式的模，模就是除法中最后的被除数。 8. 8. 对整个多项式进行输入输出的界面比较容易设计，但是对多项式的输出格式很难调对整个多项式进行输入输出的界面比较容易设计，但是对多项式的输出格式很难调 试，有很多情况（去符号，去试，有很多情况（去符号，去 0 0，指数是，指数是 0 0 的情况等等） 。的情况等等） 。 数据结构选择、算法设计：数据结构选择、算法设计： 我们用我们用 javajava 语言编辑程序，应
5、为它里面含有很多可以直接引用的的方法。语言编辑程序，应为它里面含有很多可以直接引用的的方法。 多项式用多项式用 ListList（线性表）存储，其中每一个节点为一个单项式，单项式内部有系数和（线性表）存储，其中每一个节点为一个单项式，单项式内部有系数和 指数，系数为一个指数，系数为一个 doubledouble 型数字，指数用一个型数字，指数用一个 TreeMapTreeMap（可排序映射表）（可排序映射表） 表示，字符串存单表示，字符串存单项式的字母项式的字母, ,对应的值为该字母的指数对应的值为该字母的指数. . 多项式内部封装了加减乘除模运算和转换为字符串，作为支持，又封装了多项式内部封
6、装了加减乘除模运算和转换为字符串，作为支持，又封装了 getMaxExpgetMaxExp （取最高次数） ，（取最高次数） ，sortsort（排序整理，去（排序整理，去 0 0 项） ，项） ，negatenegate（取反）（取反）. .这些计算需要用到单项式的这些计算需要用到单项式的 计算，所以也对单项式封装了多种方法。计算，所以也对单项式封装了多种方法。 单项式封装了单项式封装了 addadd（加） ，（加） ，multiplemultiple（乘）（乘）dividedivide（除） ，（除） ，compareTocompareTo（比较） ，（比较） ，remove0remove0 （去除指数为（去除指数为 0 0 的项） ，的项） ，isNegativeisNegative（判断是否为负数项） ，转换为字符串。（判断是否为负数项） ，转换为字符串。 另外还有解析运算类，用于把字符串解析成多项式和运算符，然后通过多项式类另外还有解析运算类，用于把字符串解析成
