《数据结构》课程设计报告-多项式计算器.docVIP

《数据结构》课程设计报告 姓名 学号 2009 级 5班 7组 实验室： A110 提交日期 8.25 成绩 指导教师 实验题目： 多项式计算器 问题解析（对问题的分析、理解和解题方法）： 我们先对数据结构进行了分析，对其运算进行了详细的分解。 我们把整个程序我们分为6个部分加减法，乘法，除法，排序整理，多项式解析，输入输出的格式及用户界面。 一· 1. 多元多项式加法：直接加，进行排序整理。 2. 多元多项式减法即加法的取反运算。 3. 如何进行解析是一个难点，我们中序表达式转后序表达式的方法进行解析。 二· 多元多项式乘法是前一个多项式的每一项与后一项的每一项相乘相加，然后排序整理。 5. 由于上述分析中提到对多项式进行排序整理，则我们就要先写一个sort()的函数，对多项式进行排序整理。其原理是按照其中一个字母的次数的降次排序，使用的是冒泡算法。 三· 6. 一元多项式除法即比较前一项与后一项的最高次数,若被除数的最高次数大于等于除数的最高次数,则被除数的用最高次项除以除数的最高次项,得到一个临时的商.再用被除数减去这个商乘以除数的积作为新的被除数。如此循环，就可以得到商。 7. 一元多项式的模，模就是除法中最后的被除数。 8. 对整个多项式进行输入输出的界面比较容易设计，但是对多项式的输出格式很难调试，有很多情况（去符号，去0，指数是0的情况等等）。 数据结构选择、算法设计： 我们用java语言编辑程序，应为它里面含有很多可以直接引用的的方法。 多项式用List（线性表）存储，其中每一个节点为一个单项式，单项式内部有系数和指数，系数为一个double型数字，指数用一个TreeMapString,Integer（可排序映射表）表示，字符串存单项式的字母,对应的值为该字母的指数. 多项式内部封装了加减乘除模运算和转换为字符串，作为支持，又封装了 getMaxExp（取最高次数），sort（排序整理，去0项），negate（取反）.这些计算需要用到单项式的计算，所以也对单项式封装了多种方法。 单项式封装了add（加），multiple（乘）divide（除），compareTo（比较），remove0（去除指数为0的项），isNegative（判断是否为负数项），转换为字符串。 另外还有解析运算类，用于把字符串解析成多项式和运算符，然后通过多项式类进行运算，这样的好处就是程序入口简单，降低耦合性，便于代码复用. 用户界面单独编写，并通过解析运算类进行多项式处理，返回结果。用户界面只有输入框,输出框和一个按钮，用法简单，报错功能完善。 中缀表达式转后缀表达式: 　　·开始扫描； 　　·数字时，加入后缀表达式； 　　·运算符： 　　a. 若为最高级的运算符，入栈； 　　b. 若为 (，入栈； 　　c. 若为 )，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删除( ； 　　d. 若为不是最高级的运算符，则将从栈顶到第一个优先级不大于（小于，低于或等于）它的运算符（或 (,但优先满足前一个条件）之间的运算符加入后缀表达式中，该运算符再入栈·构建一个空堆栈,扫描后缀表达式; ·多项式时,入栈; ·运算符时,从堆栈中弹出两个多项式运算,将结果再次入栈; ·最后的栈顶元素就是结果多项式. 任务分工及进度计划： 任务分工： 我的任务是解析字符串,按顺序转换成后缀表达式,并调用多项式的计算.以及编辑多项式的加法和减法运算。 进度： 我们在8.24下午进行分组，大家讨论整个程序的大体构架，并且进行任务的划分。 8.25白天在各自的程序完成后，进行合并以及大量的调试，晚上把输入输出界面编辑出来了，并开始写了各自的实验报告。 8.26早上交付程序并提交实验报告。 用户手册： 1. 在用户界面的第一行输入你想要计算的多项式。 2. 用户要记住多元多项式只能计算加，减，乘法而不能进行除法和模运算；一元多项式可以进行加，减，乘，除，模运算。 3. 输入完毕后，请检查多项式是否输入错误。 4. 检查完毕后，请按“计算”按钮，你会在下一行得出你想要运算的多项式的结果。 测试结果： 一元多项式加法： 一元多项式减法： 一元多项式乘法： 一元多项式除法： 一元多项式模运算： 多元多项式加法： 多元多项式减法： 多元多项式乘法： 程序清单： 解析并计算: package polynomial; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; imp