数据结构程序设计作业——《一元多项式的四则运算》.doc

数据结构实验报告题目一元多项式四则运算学生姓名王某某 专业班级测控120X班 学 号U2012XXXXX 1 问题描述利用已学过的数据结构来构造二个存储多项式的结构，接着把输入，加，减，乘，除运算分成四个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。最后，编写main主函数以实现对多项式输入输出以及加、减、乘、除。2 相关函数介绍说明（1）程序定义的数据结构类型为线性表的链式存储结构类型变量：typedef struct linknode（2）程序定义的其它函数：linnode *Sort(linnode *S);/多项式按指数从大到小排序linnode *CreateList(); /创建多项式Void ShowList(linnode *head) ; /显示多项式linnode *Copy(linnode *copy); /拷贝多项式（因为做减法运算时会破坏原来输入的多项式）linnode *SearchList(linnode *head,int x);/查找函数Linnode *Mulr(linnode *s,linnode *p)/用一个节点去乘与一个多项式（辅助除法运算）Linnode *AddSame(linnode *head);/和并多项式的同类项linnode *Add(linnode *head1,linnode *head2); / 加法linnode *Mul(linnode *head1,linnode *head2); / 乘法linnode *Sub(linnode *head1,linnode *head2); / 减法Void Div(linnode *head1,linnode *head2)/除法int main( )/主函数3 程序设计3.1 多项式存储的实现 多项式是由若干项构成的一个数学式子，其每一项包含系数与指数。然而我们可以把每一项看成是一个节点，再由这些节点连接成多项式。根据所学数据结构，采用线性表的链式存储来存储多项式的每一个项的系数与指数。其结构为：typedef struct linknode /链表节点的结构体float coe; /系数int index; /指数struct linknode *next; linnode; 3.2 加减乘除算法 在多项式运算的程序设计中，每一部分都会调用一些其它函数来辅助完成运算（例如：对输入的多项式进行排序，查找，合并等），在这里主要说明加减乘除运算的程序设计，其它函数的程序设计和具体调用关系请查看程序清单。3.2.1加法运算的实现加法计算还是比较容易实现的，将两个传递过来的多项式链表进行复制操作（加法运算会破坏原来两个链表的结构），再将复制出来的两链表进行连接操作，即将第一个多项式链表的尾指针next指向第二个链表的第一个节点，最后进行合并同类项操作。 开始复制两个多项式连接两个多项式合并连接好的多项式的同类项返回合并同类项后的多项式头指针结束对于加法运算我们并不用考虑多项式是否为空的情况，为空时连接后合并同类项处理后仍然返回空的多项式。3.2.2减法运算的实现多项式的减法与加法类似，先将传递进来的两个多项式进行判断是否为空，若被减数为空时，减数按逐项系数取反操作。不为空时，被减数的每一项的指数去查找减数中与之对应的项，找到后并同类项相减，把值赋给被减数与之对应的同类项，再在减数中删除查找到的那个项（节点）。彻底查找后，将减数剩余的节点取反后再连接到被减数的末尾，在进行合并同类项操作并返回头指针。开始被减数是否为空 是被减数每一项查找减数与之对应的项 否 找到未找到加法操作，并将值赋给被减数 被减数与减数取反后连接 合并同类项 结束 3.2.3乘法运算的实现开始 多项式的乘法运算，首先是判断多项式都不为空，为空时直接输出结过为0。否则将其中一个多项式的每一项去乘于另外个多项式的每一项，将乘得每一项的结果连接成一个完整的多项式，然后在对其进行合并同类项操作。最后返回结果头指针。判断两个多项式是否都为空多项式两两相乘 否 合并同类项 结束 是3.2.4除法运算的实现 首先将相除的两个多项式降序排列，两个多项式为非空时。判断被除数的最高次幂大于或等于除数的最高次幂，然后用被除数的第一项去除于除数的第一项所得商的第一项，在用所得商的这一项去乘除数的所有项所得的多开始项式与被减数作差，在用所得差作为被减数。循环上述步骤，当被减数最高次幂小于减数最高次幂是终止循环，输出相应的结果。判断两个多项式是否都为空 判断最高次幂被减数=减数 否相除得商的第一项 是 乘与被除数被除数减去所得多项式得到的结果作为被除数输出商和余数否 结束 是 在程序设计时应注意: 由于在输入多项式的时候就调用了Sort（）函数进行降序排序，因此在除法运算时并不需要从新排序。4 运行测试 主界面效果图 按1输入多项式 输入测试数据 显示输入的测试多项式 多项式相加 多项式相减 多项式相乘 多项式相除5 实验收获通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。同时，在设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。附录：程序清单#include stdlib.h#include iostreamtypedef struct linknode /定义节点的结构体float coe; int index;struct linknode *next; linnode; /定义节点类型linnkodelinnode *Sort(linnode *S) /多项式按降序排列linnode *z,*s;s=S;z=new linnode;z-next=NULL;while(S-next!=NULL)for(linnode *x=S-next;x-next!=NULL;x=x-next)if(S-next-indexnext-index) z-coe=x-next-coe; x-next-coe=S-next-coe;S-next-coe=z-coe;z-index=x-next-index;x-next-index=S-next-index;S-next-index=z-index;S=S-next;return s;linnode *CreateList() /创建线性表int n=0,z=1;linnode *p,*s,*head;float coe;int index;head=new linnode;head-next=NULL;p=head;while(z) printf(ntt请输入：); scanf(%f,&coe); scanf(%d,&index); getchar(); if(coe!=0|index!=0) s=new linnode; s-coe=coe; s-index=index; p-next=s; s-next=NULL; p=s; else z=0;return Sort(head);void ShowList(linnode *head)/ 显示线性表linnode *P= Sort(head);if(head-next=NULL)printf(多项式为空！ );else while(P-next!=NULL) if(P-next-coe)!=0)(P-next-coe)0?printf(+%5.2f ,P-next-coe):printf(%5.2f ,P-next-coe); (P-next-index)!=0?printf(X%d,P-next-index):printf(); P=P-next;linnode *Copy(linnode *copy) linnode *d,*head3,*a;d=new linnode;head3=d;if(copy-next!=NULL)while(copy-next!=NULL)a=new linnode;a-coe=copy-next-coe;a-index=copy-next-index;d-next=a;a-next=NULL;d=a;copy=copy-next;return head3;elsereturn copy;linnode *SearchList(linnode *head,int x) /查找函数linnode *p;if(head!=NULL)p=head-next;while(p!=NULL&p-index!=x) p=p-next;if(p!=NULL)return p;elsereturn NULL;else return NULL;linnode *AddSame(linnode *head) /合并同类项linnode *heads,*s,*z;heads=head;while(head-next!=NULL)linnode *x=SearchList(head-next,head-next-index); /搜索相同节点if(x!=NULL)head-next-coe+=x-coe;for(s=head-next;(s-next-index)!=x-index;)s=s-next;s-next=x-next;delete x;else head=head-next;return heads;linnode *Sub(linnode *head1,linnode *head2) /多项式做减法函数,并向函数传递两个链表（即两个待相加的多项式）linnode *s,*p,*head3; /定义三个节点指针变量s=head1; head3=s; /用于存储第一个传进来的链表的头指针p=head2;while(s-next!=NULL) /当第一个链表不为空时依次循环获取每一个节点的index值linnode *z=SearchList(p,s-next-index); /用于搜索第一链表的每个节点的index值在第二链表中是否存在并返回其节点if(z!=NULL) /条件为真是，即在第二链表中查找到与第一链表中相同index值的节点s-next-coe-=z-coe; while(p-next-index)!=z-index) /用于查找搜索到节点在第二链表中的位置p=p-next;p-next=z-next; delete z; /在第二链表中删除查找到的节点 s=s-next; /头指针向后移动for(s-next=head2-next;s-next!=NULL;s=s-next)s-next-coe=-(s-next-coe);return AddSame(head3); /返回第一链表的头指针linnode *Add(linnode *head1,linnode *head2) /多项式加法函数linnode *s,*p,*d,*a,*head3;s=head1;p=head2;d=new linnode;head3=d;while(s-next!=NULL)a=new linnode;a-coe=s-next-coe;a-index=s-next-index;d-next=a;a-next=NULL;d=a;s=s-next;while (p-next!=NULL)a=new linnode;a-coe=p-next-coe;a-index=p-next-index;d-next=a;a-next=NULL;d=a;p=p-next;return AddSame(head3); /合并同类项后返回linnode *Mul(linnode *s,linnode *p) /多项式作乘法运算函数，两个参数用于传进两个待相乘的多项式链表linnode *head1,*head2,*head3,*n,*head4; /定义链表指针用于存储多项式的节点指针head1=s; /将第一个用于存储多项式的链表的头指针赋值给head1head2=p; /将第二个用于存储多项式的链表的头指针赋值给head2head4=new linnode;/创建一个头节点head4-next=NULL;head3=head4; /用于存储新创建的链表的头指针if(head1-next!=NULL&head2-next!=NULL) /两个多项式不为空时for(;head1-next!=NULL;head2=p,head1=head1-next) /此循环用于实现多项式中的乘法运算for(;head2-next!=NULL;head2=head2-next) /此循环用于实现多项式中的乘法运算 n=new linnode; /新建一个节点用于存储多项式相乘之后每一项的结果n-coe=(head1-next-coe*head2-next-coe); /系数相乘n-index=(head1-next-index+head2-next-index); /指数相加head3-next=n;n-next=NULL;head3=n; return AddSame(head4);elsereturn head4;linnode *Mulr(linnode *s,linnode *p) /一个节点乘与整个多项式（辅助除法运算）linnode *head2,*n,*head1,*head;head2=new linnode;head2-next=NULL;head=head2;head1=p;while(p-next!=NULL&s-coe!=0)n=new linnode;n-coe=s-coe*p-next-coe;n-index=s-index+p-next-index;n-next=NULL;head2-next=n;head2=n;p=p-next;p=head1;return head;void Div(linnode *head1,linnode *head2) /除法linnode *temp1,*head3,*head4,*z;temp1=new linnode;temp1-next=NULL;head3=temp1; /商while(head1!=NULL&head1-next!=NULL&head1-next-index=head2-next-index) /判断指数大小z=new linnode;z-coe=head1-next-coe/head2-next-coe;z-index=head1-next-index-head2-next-index;temp1-next=z;z-next=NULL;temp1=z;head4=Mulr(z,head2);linnode *head5=head1;while(head1-next!=NULL)head1=head1-next;head1-next=head4-next;head1=AddSame(head5); /合并while(head1-next!=NULL&head1-next-coe=0)head1=head1-next; printf(nF(X)/G(X);printf(n商：);ShowList(head3);printf(n余数：);ShowList(head1);int main() system(color 0F);int choice,j=1;linnode *head1,*head2,*add,*sub,*mul,*copy1,*copy2;add=new linnode;sub=new linnode;mul=new linnode;head1=new linnode; head2=new linnode;copy1=new linnode;copy2=new linnode;head1-next=NULL; head2-next=NULL;head1-index=NULL; head2-index=NULL;add-next=NULL;sub-next=NULL;mul-next=NULL;copy1-next=NULL;copy2-next=NULL;while(j)system(Color E0);printf(n);printf(ntt 一 元 多 项 式 的 四 则 运 算 );printf(n);printf(ntt 1-输入多项式 );printf(ntt 2-显示多项式 );printf(ntt 3-相 加 );printf(ntt 4-相 减 );printf(ntt 5-相 乘 );printf(ntt 6-相 除 );printf(ntt 0-退 出 ); printf(n);printf(ntt 请选择菜单号（0-6）进行操作:);scanf(%d,&choice);getchar();if(choice=1)head1-next=NULL; head2-next=NULL;printf(ntt请逐个输入第1个多项式的结点，以“0 0”作为结束标记! n