一元多项式基本运算操作.doc

数据结构 课程设计报告课题名称： 一元多项式基本运算操作 专 业： 计算机科学与技术 班 级： T923-1 学 号： 20090230118 姓 名： 吴 卿 指导教师： 马春江、梅 琴 成 绩： 2011年06月29日目 录1 前言12需求分析13概要设计（特殊功能）14详细设计15源代码及调试26特殊问题解决方法27使用说明及测试结果28结论29总结与体会210参考文献3附录.致谢.老师意见.1 前言 数据结构课程设计是理解和掌握数据结构的重要环节，主要任务是实现各种数据组织中的数据逻辑结构，存储结构以及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养学生的数据抽象能力和软件设计的能力。通过全部过程培养和锻炼学生的钻研能力、动手能力、分析问题和解决问题的实际能力。1.1 课题简介 题目名称：一元多项式基本运算操作课设目的：巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。课设意义：（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操 作 （2）能针对给定题目，选择相应的数据结构，分析并设计算法， 进而给出问题的正确求解过程并编写代码实现。 （3）为数据结构的后续课程，诸如算法分析与设计，编译原理等打下坚实的基础具体内容：（1）输入并分别建立多项式A和B (2)输入输出多项式，输出形式为整数序列,含有系数，底数，指数， 以及正负号，序列按指数降序排列。 (3)完成两个多项式的相加、相减，相乘，将结果输出，并将结果存 入文本中。 自己创新：（1）.求出各个多项式的倒数 （2）设计帮助菜单 特别细节：(1)当系数为1时，不予显示系数1 (2)当指数为0时，不予显示X0字符串 (3)当指数为1时，不予显示指数1 预期效果：（1） 实现手动输入和文本输入两种方式（2） 实现两个多项式的相加，相减，相乘的运算（3） 实现单个多项式的求导运算 (4)对于输入有误问题，能实现判断和处理的功能1.2 方案及其论证实验平台：VC+6.0选题原因;自己的编程能力有限，然而深知数据结构课程的重要性以及课设的重要意义，不能去复制他人的代码，只能通过自己独立地编写，只有这样，才能够有所提高。即使自己编写的功能很少，代码量也很少，但是只要是通过自己独立地的完成，那么自己就会在编程上有真正的有所提高，有所进步。而相比于其他课题，一元多项式的计算这一题目，相对来说较为简单，思路也是较为清晰与明朗的，所以综上所述，选择了题目1-一元多项式。编写语言：C + +可行性分析：对于多项式的加减乘的计算，可以使用结构体链表，类模板，其中结构体中有底数，指数和指针三个数据元素。对于加运算，使用循环，将指数相等的项，进行系数的相加减；对于减法运算是加法的另外的一种形式而已，只需将多项式2乘以（-1），然后调用加法运算函数即可；而对于乘法运算，先将两个多项式做乘法运算，对于指数相等的项，进行系数加法运算。时间安排：2011-6-27-上午 选题2011-6-27-下午 思考规划程序设计思路 2011-6-28-全天 编程2011-6-29-全天 编程 2011-6-30-上午 调试，程序细节优化2011-6-30-下午 ,验收程序，撰写报告，细节优化2011-7-01-上午 提交报告2需求分析(1) 本演示程序中，多项式的系数和指数可以是整型，也可以是浮点型，所以在实际的程序设计师采用的是的类模板。输入多项式时，a）手动输入时，依次输入多项式的项数，然后依次输入各个项的系数和指数b）若是文本读入，直接读出。而多项式的输出形式为数学表达式且按指数降序排列，对于指数为0的项加以处理.(2) 演示程序以用户和计算机程序对话的方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入程序中相应的选择，相应的输入数据和运算结果就会依次显示在其后。(3) 程序命令包括：a）输入多项式 b）多项式显示c）多项式加法 d）多项式减法e）多项式乘法f）对多项式求导g）显示帮助菜单 h）退出程序(4)使用者方面：任何人都可以运行本程序，只要点击main.exe文件即可，按着相应的提示操作即可，不会出现什么大的问题，而对于实际使用中出现的问题，只需查看帮助菜单即可加以解决。(5)测试数据：多项式1：f(x)=100*X50+88*X30-51*X20+2*X6+3多项式2：f(x)=-99*X50+50*X20+X10-2*X63概要设计（特殊功能） (1)数据结构：多项式的数据结构可以使用线性表来实现，具体来讲就是链表结构(2)节点结构：*next指针系数 指数(3)项目框图： 功能界面输入多项式显示多项式多项式相加多项式相减多项式相乘多项式求导显示帮助菜单退出此程序手动输入文本输入退出返回功能界面(4)类之间的关系示意图： 私有属性*head,*headp,*headq多项式的各种 友元类 LinkedList L i s t N o d e 类 公有属性即：对于多项式的各种操作公有属性 构造函数和析构函数 私有属性系数，指数，*next说明：a） 在本次课设程序中，共建立了2各类，分别是class LinkedList和class ListNode，其中class LinkedList是class ListNode的友元。b） class LinkedList的公有属性是对于多项式的各种操作,而class ListNode的私有属性就是多项式的每一项的记录信息：系数，指数和*next指针。c） 对于多项式的各种操作包括：输入多项式 ，多项式显示，多项式加法 ，多项式减法，多项式乘法，对多项式求导，也就是项目框图中功能界面下的所有操作。设计顺序： a)定义class LinkedList和class ListNode b)定义class LinkedList和class ListNode公有属性的各种操作函数 c）编写主函数，测试运行，细节优化4详细设计（1）类模板的定义：template <class T> class LinkedList; /向前定义template <class T>class ListNodefriend class LinkedList<T> /定义友元public:ListNode()next = NULL;/构造新结点ListNode();private:ListNode<T> *next;T data; /单项式系数T index; /未知数指数;template<class T>class LinkedListpublic:LinkedList();LinkedList();void creatPloy(ListNode<T> * headp, ListNode<T> * headq); void displayPloy(ListNode<T> *head) const; ListNode<T> * getNode(); void showFace();void menu(); void scanfPloy(ListNode<T> * head); void readPloy(ListNode<T> * head,char *fileName); bool empty(ListNode<T> *head); ListNode<T> * AddPloy(ListNode<T> * headp, ListNode<T> * headq); ListNode<T> * SubPloy(ListNode<T> * headp, ListNode<T> * headq); ListNode<T> * MulPloy(ListNode<T> * headp, ListNode<T> * headq); ListNode<T> * DerPloy(ListNode<T> * h); private:ListNode<T> *head;ListNode<T> *headp;ListNode<T> *headq;（2） 各个函数分析（a）建立多项式函数void creatPloy(ListNode<T> * headp, ListNode<T> * headq);创建多项式有手动输入和文本读入两种方式，在具体地创建多项式时，应该选择是采用哪一种方式加以创建，不论是采用何种方式，在具体的实现上是分别去调用void scanfPloy(ListNode<T> * head)或者是void readPloy(ListNode<T> * head,char *fileName)函数。建立多项式的存储结构，每一个一元多项式的存储结构就是一个有序单链表。有序链表的基本操作定义与线性链表有两处不同，一个是结点的查找定位操作LocateNode有所不同，二是结点的插入操作InsertNode不同。（b）显示多项式函数void displayPloy(ListNode<T> *head) const显示多项式链表。在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“+”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。需要对系数为+1，-1和指数为0的情况加以考虑具体代码为：void LinkedList<T>:displayPloy(ListNode<T> *head) constListNode<T> *p;p = head; /显示头结点休息，需要说明的是：指数已经排序完成if(p->data=1) /对于头结点的系数为1的处理cout << "X" << "" << p->index ;else if(p->data=-1) /对于头结点的系数为-1的处理cout <<"-" <<"X" << "" << p->index ;elsecout << p->data<<"*"<< "X" << "" << p->index ;for (p=head->next; p!=NULL; p=p->next) /利用循环，显示头结点以后节点的信息if(p->data >1) /使用if-else if -else语句对于系数的各种情况加以考虑输出if(p->index=0) /对于指数为0情况的考虑out<<"-"<<p->data;else /对于治顺不为0情况的考虑 cout << "+" << p->data<<"*"<<"X"<< "" << p->index ;else if(p->data=1) /系数为1情况输出的考虑，if(p->index=0)cout<<"-"<<p->data;elsecout<<"+"<<"X"<< "" << p->index;else if(p->data < 1)&&(p->data > 0)if(p->index=0)cout<<"-"<<p->data;else cout << "+" << p->data<<"*"<<"X"<< "" << p->index ;else if (p->data=0) /系数为0情况输出的考虑，if(p->index=0)cout<<"-"<<p->data;elsecout << " " ;else if (p->data < 0)&&(p->data > -1)if(p->index=0)cout<<"-"<<p->data;elsecout << "-" << p->data<<"*"<<"X"<< "" << p->index ;else if(p->data=-1) /系数为-1情况输出的考虑，if(p->index=0)cout<<"-"<<p->data;elsecout<<"-"<<"X"<< "" << p->index;elseif(p->index=0)cout<<"-"<<p->data;elsecout << "-" << p->data<<"*"<<"X"<< "" << p->index ; cout << endl;（c）/多项式相加根据一元多项式相加的运算规则：对于一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式”中相应的位置。根据以上运算规则，其实现算法思路如下：假设headp为指向“和多项式链表”当前尾结点的指针，指针headp和headq分别指向两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项值，有下面三种情况：1.若指针heapd所指结点的指数值大于指针hendq所指结点的指数值，则取headp指针所指向的结点插入到temp指针所指结点之后，分别修改指针headp和temp，使之指向链表的下一个结点；2.若指针headp所指结点的指数值小于指针headq所指结点的指数值，则取headq指针所指向的结点插入到temp指针所指结点之后，分别修改指针headqtemp，使之指向链表的下一个结点；3.若指针headp所指结点的指数值等于指针headq所指结点的指数值，则将两结点中的系数相加，如果其和数不为零，则修改headp指针所指结点中的系数值，将其结点插入到temp指针所指结点之后，分别修改headp、headq和temp，使之指向各自链表的下一个结点，同时删除并释放指针headq原先指向各自链表的下一个结点；如果和数为零，保存headp和headq所指向的结点，修改headq和headp指针使之指向各自链表的下一个结点，然后释放保存的两个结点。再比较指针headp和headq指向节点中的指数项值，分3种情况进行处理.这样的操作一直继续到headp或headq等于NULL为止。最后将未结束的链表后面剩余的节点连接到temp指针所指向结点之后。关键代码部分ListNode<T> * AddPloy(ListNode<T> * headp, ListNode<T> * headq); temp = temq = head;/多项式1的头结点幂方大于多项式2把多项式1的头结点作为新的链表头结点if (headp->index > headq->index)head->data = headp->data;head->index = headp->index;p = headp->next;q = headq;else if (headp->index = headq->index) /幂方相等时，系数相加head->data = headp->data + headq->data;head->index = headp->index;p = headp->next;q = headq->next;elsehead->data = headq->data;head->index = headq->index;q = headq->next;p = headp; /一般情况while (p != NULL && q != NULL)if (p->index > q->index)temp = getNode();temp->data = p->data;temp->index = p->index;temq->next = temp;temq = temp; /指针前移p = p->next;else if (p->index = q->index)temp = getNode();temp->data = p->data + q->data;temp->index = p->index;temq->next = temp;temq = temp;p = p->next;q = q->next;elsetemp = getNode();temp->data = q->data;temp->index = q->index;temq->next = temp;temq = temp;q = q->next;/ /多项式加未完成while (p!=NULL)temp = getNode();temp->data = p->data;temp->index = p->index;temq->next = temp;temq = temp;p = p->next;/while (q != NULL)temp = getNode();temp->data = q->data;temp->index = q->index;temq->next = temp;temq = temp;q = q->next;/(d)/多项式减法多项式的减法只是加法的另外的一种形式而已，多项式2的各个系数乘以-1，然后再做加法运算即可，在这里不予以详述（e）/多项式的乘法运算多项式的乘法运算规则： 用第一个的多项式的每一项去乘以第二个多项式的各个项，将得到的所有项进行合并同类项，然后按照指数从高到底的顺序加以排序显示根据上述运算规则，其编程思路具体如下假设第一个多项式的首指针为*p,第二个多项式的首指针为*q1) 采用双重循环算法，首先用*p去乘以*q,然后*q+，指针后移，这样做就可以实现多项式1的第一项与多项式2的每一项相乘，直到*q=NULL停止操作将相乘的结果存入新创建的链表之中。2) 采用同样的方法，这时，将*p指针后移，重复1）的操作。就会得到一个完整的链表结构，这个链表结构存放了所有的成绩的结构，这个链表是没有结果任何的处理的3） 对链表的处理，合并同类项，对于系数为0的节点加以删除。4） 采用冒泡排序显示ListNode<T> * AddPloy(ListNode<T> * headp, ListNode<T> * headq);ListNode<T> *p, *q, *temp, *temq;head->data = -32768; /用于判断头结点赋值与否temp = temq = head;/双重循环实现多项式相乘for (p=headp; p; p=p->next)for (q=headq; q; q=q->next)if (head->data = -32768) /给头结点赋值head->data = p->data * q->data;head->index = p->index + q->index;elsetemp = getNode();temp->data = p->data * q->data;temp->index = p->index + q->index;temq->next = temp;temq = temp;/合并次方相同的项for (p=head; p; p=p->next)for (q=p; q; q=q->next)temp = q->next; /指向将要判断的结点if (temp) /temp结点不能为空if (temp->index = p->index)p->data += temp->data;q->next = temp->next;delete temp;/多项式按次方降序排列for (p=head; p; p=p->next)temp = p;for (q=p; q; q=q->next) /交换结点if (p->index < q->index)temp = getNode();temp->data = q->data;temp->index = q->index;q->data = p->data;q->index = p->index;p->data = temp->data;p->index = temp->index;delete temp;f）多项式求导运算多项式的求导思路：首先对于指数相同的情况加以处理，然后计算新系数和新指数，其中新系数=旧系数*指数；新指数=旧指数-1；（有一定的次序相关性）。ListNode<T> * DerPloy(ListNode<T> * h)g)菜单使用cout语句即可加以实现，但是亮点在功能菜单使用指针数组加以定义用于显示，有一点的好处。char *pstr=显示内容的代码；菜单界面在此次实验中编写的较好，看起来有耳目一新的感觉。5源代码及调试 见报告末页（附录）6特殊问题解决方法 6.1问题1 多项式乘法的编程部分：在此部分中主要是思路不清晰，在实际地编程处理中，出现了乘的的顺序不正确，比如说我将第一个多项式的第一项乘以第二个多项式的第二项，然后是第一个多项式的第二项乘以第二个多项式的第一项，着样看似正确但是实际上，不能够得到正确的结果，而且执行的效率很低，原因是乘法的顺序混乱，自己在编程上存在思维上的漏洞。仔细分析之后，调整乘法顺序，首先是用第一项的第一项乘以第二个多项式的各个项，将结果存入链表之中，接着是用第一个多项式的第二项乘以第二个多项式的各个项，也将结果存入链表之中，对于之后的项，依次类推。正确的语句为：/双重循环实现多项式相乘for (p=headp; p; p=p->next)for (q=headq; q; q=q->next)if (head->data = -32768) /给头结点赋值 head->data = p->data * q->data;head->index = p->index + q->index;elsetemp = getNode();temp->data = p->data * q->data;temp->index = p->index + q->index;temq->next = temp; temq = temp;最后将指数相同的项，系数进行相加减，若出现系数为0的情况，那么应该将该节点删除。（按指数从大到小的顺序加以排序显示）6.1问题2 文本读入部分：事实上，对于文本读入操作的编程操作，我一直存在着极大的困难，掌握的不熟悉，在这次编程时无法将结果读入。为了解决这个问题，首先我将大二上的C+语言关于文件的知识复习了一遍，编写了C+几个关于文件的操作；然后进行实际的编程操作，但是实际运行时出现了很多出错的提示信息，信心有一丝受挫，但是得到了刘彬，黄伟强同学的帮助，指出了在读入数据时，没有及时地申请空间去存放要读入的数据，而且对于没有将读入的数据存入链表之中。听了两位同学的讲解后，我又将书本重新看了一遍，最后我加入了这段代码：p = q = head; ins >> head->data;ins >> head->index;while (!ins.eof()p = getNode();ins >> p->data;ins >> p->index;q->next = p;q = p;ins.close();运行得到正确的结果（在文本中存放的即是测试数据的系数和指数，并且按照一定顺序）。7使用说明及测试结果（1） 使用说明：方法1：打开文件中main.cpp文件，点击编辑，运行 ，即可方法2：打开debug文件，点击main.exey运行即可弹出窗口。（2）测试结果：a)运行该程序后出现此说明性窗口b）按任意键进入主菜单c）文件读入方式输入数据（以下结果均是建立在此数据的基础上）d）输入数字2，进行显示操作e）输入数字3，进行相加运算f)输入数字4，进行相减运算g）输入数字5，进行相乘运算h）输入数字6，进行求导运算i）输入数字7，显示帮助菜单j）输入78，检查出错功能k）进行手工输入的界面与方法（项数-底数-指数）l）输入数字0，退出界面说明：上述加，减，乘，求导结果，均以验证，正确无误。(3)功能详述：（4）应用价值：可以实现两个多项式的相加，相减，相乘以及相乘的功能。 (5) 特别说明：当在使用程序时，建议仔细阅读说明性文件，说明性文件，仅仅在程序运行中出现一次。若想重新查看说明性文件，需要关闭程序，然后重新运行方可。而对于帮助菜单，在显示主菜单后，只需输入数字7即可查看帮助菜单。说明性文件和帮助菜单仅仅是文字，不会有任何实质性地操作。8结论在此次课程设计中，对于题目1，主要使用的是线性，链接数据结构。在两个数相加减运算中，依次加以比较，对于指数相同的项，只是将系数进行相加减，但需要将相同项中的一项删去，而当产生系数为0的情况时，需要将对应的两项都加以删除，这两点中都使用到了删除操作语句。在多项式乘法运算中，每两项相乘的结果都必须存入新的节点中；在多项式的相加减时，对于系数不同的项，两项都必须加以保存，这两点都涉及到新建并插入节点的语句。按照题目的意思，结果需要按照指数的降序排序加以显示，用到了冒泡排序的算法。为了使程序具有通用性，在此次程序算法中使用了类模板的知识，使得对于浮点型，整型的系数，指数都可以加以处理。仔细地阅读程序代码后，使用的数据结构的概念有：线性表，冒泡排序，链接存储，类模板，友元；细节操作有：新建节点，删除节点，增加节点，插入节点，文件读出写入；程序结构方面：总体上是循环结构（），当输入值不为是便一直执行主菜单中的程序代码，在主菜单程序中使用的是选择结构，使用了语句加以实现；在各个语句内部使用的是顺序结构，如建立多项式代码段部分creatPloy(headp, headq);cout << "多项式建立成功!"当然在其他语句中也是使用了选择语句。由此看来，在此次课设中，将程序的三种结构全部使用到了，同时将线性表中的所有的操作都使用了，更是对C+，数据结构两门课程的复习，也会对理论知识加深理解，使之真正地的转化为实实在在的应用，一方面有利于知识的总结与归纳；另一方面也会使我们感受到知识的价值。通过实际的运行测试，基本上达到了预期的目标，完成了多项式的基本操作运算，最开始在细节上存在一定的问题，诸如：当系数为1,1予以显示；当指数为0时，指数0也加以显示；这在我们与我们实际看到得多项式有较大的不同，这会是使用者有较大的不适应，所以在老师提出这个问题时，对程序加以修改，增加了一些判断语句，具体为：if(p->data=1) /对于头结点的系数为1的处理cout << "X" << "" << p->index ;else if(p->data=-1) /对于头结点的系数为-1的处理cout <<"-" <<"X" << "" << p->index ;elsecout << p->data<<"*"<< "X" << "" << p->index ;for (p=head->next; p!=NULL; p=p->next) /利用循环，显示头结点以后节点的信息if(p->data >1) /使用if-else if -else语句对于系数的各种情况加以考虑输出if(p->index=0) /对于指数为0情况的考虑out<<"-"<<p->data;else /对于治顺不为0情况的考虑 cout << "+" << p->data<<"*"<<"X"<< "" << p->index ;else if(p->data=1) /系数为1情况输出的考虑，if(p->index=0)cout<<"-"<<p->data;elsecout<<"+"<<"X"<< "" << p->index;else if(p->data < 1)&&(p->data > 0)if(p->index=0)cout<<"-"<<p->data;else cout << "+" << p->data<<"*"<<"X"<< "" << p->index ;else if (p->data=0) /系数为0情况输出的考虑，if(p->index=0)cout<<"-"<<p->data;elsecout << " " ;else if (p->data < 0)&&(p->data > -1)if(p->index=0)cout<<"-"<<p->da