一元多项式计算(数据结构课程设计).doc

池 州 学 院CHIZHOU COLLEGE 数据结构课程设计报告学 号： 57 54 39 37 20 25 27 姓 名： 周田 张永鹏 武警 温凯侨 李坤 米昌华 阮健健 班 级： 10计算机科学与技术（2）班 指导教师： 成 绩： 数学与计算机科学系一、 课程设计基本情况1、设计名称 一元多项式计算2、主要功能能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；3、设计平台 电脑、Visual c+ 6.0二、 系统设计1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。(1) 一元多项式加法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。(2) 一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。2、概要设计(1)主函数流程图：（注：a代表第一个一元二次方程，b代表第二个一元二次方程）开 始 定义结构体定义函数类型及名称 构造指数比较函数 排列顺序(降序） 用单链接储存a,b项目的系数和指数 开 始 进 行 加 减 法 运 算 输 出 构 造 出 的 多 项 式指数不同 输出多项式，求项数 创建并初始化多项式链表 输 入 系 数 和 指 数 指数相同合并同类项 按指数排序 结 束 将 单 链 表 的 节 点 释 放，使 已 建 立 的 多 项 式 销 毁a项的指数值=b项的指数值 选 择 语 句a项指数值<b项指数值 输 出 计 算 后 的 多 项 式摘取b的指数值到“和多项式” 按指数值按降序排列摘取a指数值到“和多项式” 释放a和b的结点将a和b的系数相加(减) a项指数值>b项指数值 (2)一元多项式计算算法用类C语言表示： Typedef struct00 /项的表示，多项式的项作为LinkList的数据元素Float coef； /细数Int expn；/指数term，ElemType；/两个类型名：term用于本ADT，ElemType为LinkList的数据对象名Typedef LinkList polynomial： /用带表头的节点的有序链表表示多项式/基本操作的函数原型说明Void CreatePolyn（polynomail&P）；/输入n的系数和指数，建立表示一元多项式的有序链表P 销毁一元多项式PVoid DestroyPolyn（polynomailP）；销毁一元多项式PvoidPrintPoly（polynomail P）；/打印输入一元多项式PIntPolynLength（polynnomail P);/返回一元多项式P中的项数void CreatPolyn（polynomail&Pa.polunomail&Pb);/完成多项式相加运算，即:Pa=Pa+Pb,并贤惠一元多项式PbvoidSubtractPolyn（polunomail&Papolunomail&Pb）；/完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb/基本操作的算法描述Int cmp(tem a，temp b）；/依a的指数值<（或=）（或>b的住数值，分别返回-1、0和+1Void CreatePolyn（polynomail&P,int m)/输入m项的系数和指数，建立表示一元多项式的有序链表PInitList（P）；h=GetHead（P）；E.coef=0.0；e.expn=-1；SerCurElem（h，e）；/设置头结点的数据元素For （i=1；i<=m；+i）/依次输入m个非零项Scanf（e.coef，e.epn）；If（！LocateElem（P，e，q，（*cmp）（）/当前链表中不存在该指数项If(MakeNode（s，e）InsFirst（q，s）；/生成节点并插入链表/CreatPolun三、 详细设计1、算法实现(1) 输入一元多项式函数：void shuchu(pnode *head) pnode *p; int one_time=1; p=head; while(p!=NULL) /*如果不为空*/ if(one_time=1) if(p->zhishu=0) /*如果指数为0的话，直接输出系数*/ printf("%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/ else if(p->xishu=1|p->xishu=-1) printf("X%d",p->zhishu); /*如果系数是1的话就直接输出+x*/ /*如果系数是-1的话就直接输出-x号*/ else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系数是小于0的话就输出系数x指数的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); one_time=0; else if(p->zhishu=0) /*如果指数为0的话，直接输出系数*/ if(p->xishu>0) printf("+%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/ else if(p->xishu=1) /*如果系数是1的话就直接输出+x号*/ printf("+X%d",p->zhishu); else if(p->xishu=-1) /*如果系数是-1的话就直接输出-x号*/ printf("X%d",p->zhishu); else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf("+%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系数是小于0的话就输出系数x指数的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); p=p->next; /*指向下一个指针*/ printf("n"); (2) 加法函数/*两个多项式的加法运算*/ pnode * add(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; /*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并向右移动*/ float x; /*x为系数的求和*/ p=heada; /*指向第一个多项式的头*/ q=headb; /*指向第二个多项式的头*/ headc=(pnode *)malloc(sizeof(pnode); /*开辟空间*/ r=headc; while(p!=NULL&&q!=NULL) /*2个多项式的某一项都不为空时*/ if(p->zhishu=q->zhishu) /*指数相等的话*/ x=p->xishu+q->xishu; /*系数就应该相加*/ if(x!=0) /*相加的和不为0的话*/ s=(pnode *)malloc(sizeof(pnode); /*用头插法建立一个新的节点*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2个多项式都向右移*/ else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话，就应该复制q节点到多项式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q向右移动*/ else/*p的系数大于q的系数的话，就应该复制p节点到多项式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p向右移动*/ /*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ while(p!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ while(q!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一个头没有用到*/ return headc; /*返回头接点*/ (3) 减法函数/*两个多项式的加法运算*/ pnode * add(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; /*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并向右移动*/ float x; /*x为系数的求和*/ p=heada; /*指向第一个多项式的头*/ q=headb; /*指向第二个多项式的头*/ headc=(pnode *)malloc(sizeof(pnode); /*开辟空间*/ r=headc; while(p!=NULL&&q!=NULL) /*2个多项式的某一项都不为空时*/ if(p->zhishu=q->zhishu) /*指数相等的话*/ x=p->xishu+q->xishu; /*系数就应该相加*/ if(x!=0) /*相加的和不为0的话*/ s=(pnode *)malloc(sizeof(pnode); /*用头插法建立一个新的节点*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2个多项式都向右移*/ else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话，就应该复制q节点到多项式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q向右移动*/ else/*p的系数大于q的系数的话，就应该复制p节点到多项式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p向右移动*/ /*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ while(p!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ while(q!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一个头没有用到*/ return headc; /*返回头接点*/ 2、 程序代码/*一元多项式计算*/*程序功能：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；*/*提示：输入完一元多项式之后，输入“0 0”结束本一元多项式的输入*/*注意：系数只精确到百分位，最大系数只能为999.99,指数为整数.如果需要输入更大的系数，可以对程序中5.2%f进行相应的修改*/#include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<conio.h> /*建立结构体*/ typedef struct pnode float xishu; /*系数 */ int zhishu; /*指数 */ struct pnode *next; /*下一个指针*/ pnode; /*用头插法生成一个多项式，系数和指数输入0时退出输入*/ pnode * creat() int m; float n; pnode *head,*rear,*s; /*head为头指针，rear和s为临时指针*/ head=(pnode *)malloc(sizeof(pnode); rear=head; /*指向头*/ scanf("%f",&n); /*系数*/scanf("%d",&m); /*输入指数*/while(n!=0) /*输入0退出*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=n; s->zhishu=m; s->next=NULL; rear->next=s; /*头插法*/ rear=s; scanf("%f",&n); /*输入系数*/ scanf("%d",&m); /*输入指数*/ head=head->next; /*第一个头没有用到*/ return head; /*调整多项式*/ void tiaozhen(pnode *head) pnode *p,*q,*t; float temp; p=head; while(p!=NULL) q=p; t=q->next; while(t!=NULL) if(t->zhishu>q->zhishu) q=t; t=t->next; temp=p->xishu;p->xishu=q->xishu;q->xishu=temp; temp=p->zhishu;p->zhishu=q->zhishu;q->zhishu=temp; p=p->next; /*显示一个多项式*/ void shuchu(pnode *head) pnode *p; int one_time=1; p=head; while(p!=NULL) /*如果不为空*/ if(one_time=1) if(p->zhishu=0) /*如果指数为0的话，直接输出系数*/ printf("%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/ else if(p->xishu=1|p->xishu=-1) printf("X%d",p->zhishu); /*如果系数是1的话就直接输出+x*/ /*如果系数是-1的话就直接输出-x号*/ else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系数是小于0的话就输出系数x指数的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); one_time=0; else if(p->zhishu=0) /*如果指数为0的话，直接输出系数*/ if(p->xishu>0) printf("+%5.2f",p->xishu); /*如果系数是正的话前面就要加+号*/ else if(p->xishu=1) /*如果系数是1的话就直接输出+x号*/ printf("+X%d",p->zhishu); else if(p->xishu=-1) /*如果系数是-1的话就直接输出-x号*/ printf("X%d",p->zhishu); else if(p->xishu>0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf("+%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系数是小于0的话就输出系数x指数的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); p=p->next; /*指向下一个指针*/ printf("n"); /*两个多项式的加法运算*/ pnode * add(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; /*headc为头指针，r,s为临时指针，p指向第1个多项式并向右移动，q指向第2个多项式并向右移动*/ float x; /*x为系数的求和*/ p=heada; /*指向第一个多项式的头*/ q=headb; /*指向第二个多项式的头*/ headc=(pnode *)malloc(sizeof(pnode); /*开辟空间*/ r=headc; while(p!=NULL&&q!=NULL) /*2个多项式的某一项都不为空时*/ if(p->zhishu=q->zhishu) /*指数相等的话*/ x=p->xishu+q->xishu; /*系数就应该相加*/ if(x!=0) /*相加的和不为0的话*/ s=(pnode *)malloc(sizeof(pnode); /*用头插法建立一个新的节点*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2个多项式都向右移*/ else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话，就应该复制q节点到多项式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q向右移动*/ else/*p的系数大于q的系数的话，就应该复制p节点到多项式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p向右移动*/ /*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ while(p!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ while(q!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一个头没有用到*/ return headc; /*返回头接点*/ /*两个多项式的减法运算*/ pnode * sub(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; float x; /*x为系数相减*/ p=heada; /*指向第一个多项式的头*/ q=headb; /*指向第二个多项式的头*/ headc=(pnode *)malloc(sizeof(pnode); /*开辟空间*/ r=headc; while(p!=NULL&&q!=NULL) /*两个多项式的某一项都不为空时*/ if(p->zhishu=q->zhishu) /*指数相等的话*/ x=p->xishu-q->xishu; /*系数相减*/ if(x!=0) /*相减的差不为0的话*/ s=(pnode *)malloc(sizeof(pnode); /*用头插法建立一个新的节点*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2个多项式都向右移*/ else if(p->zhishu<q->zhishu) /*p的系数小于q的系数的话*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=-q->xishu; /*建立的节点的系数为原来的相反数*/ s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; else s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p向右移动*/ while(p!=NULL) /*当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; while(q!=NULL) /*当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=-q->xishu; /*建立的节点的系数为原来的相反数*/ s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一个头没有用到*/ return headc; /*返回头接点*/ void add_main() pnode * a,*b,*c; printf("n输入第一个一元多项式:n系数 指数n"); a=creat(); tiaozhen(a); printf("n输入第二个一元多项式:n系数 指数n"); b=creat(); tiaozhen(b); c=add(a,b); printf("第一个一元多项式如下:");shuchu(a); printf("第二个一元多项式如下:");shuchu(b); printf("两式相加如下:");shuchu(c); void sub_main() pnode * a,*b,*c; printf("n输入第一个一元多项式:n系数 指数n"); a=creat(); tiaozhen(a); printf("n输入第二个一元多项式:n系数 指数n"); b=creat(); tiaozhen(b); c=sub(a,b); printf("第一个一元多项式如下:");shuchu(a); printf("第二个一元多项式如下:");shuchu(b); printf("两式相减如下:");shuchu(c); void open() printf("n *n"); printf(" 功能项: * 1 两个一元多项式相加;2 两个一元多项式相减;0 退出 *n"); printf(" *nn请选择操作: "); void main() int choose; open(); while(choose!=0) scanf("%d",&choose); getchar(); switch(choose) case 0:return; case 1: printf("n 两个一元多项式相加n"); add_main();choose=-1;open();break; case 2: printf("n 两个一元多项式相减n"); sub_main();choose=-1;open();break; default: printf("没有该选项!请重新选择操作!nn"); open(); 四、 测试方案及结果1、测试方案 在Visual C+ 6.0环境中调试运行。2、结果及分析 程序运行截图如下：五、 结论及体会 经过一周的努力，最终我们的课程设计出来了，主程序完全符合本课程设计的要求。 本次课程设计对于我们来说难度是很大的。因为对于数据结构课程设计，需要有扎实的C语言编程能力，而我们这组人C编程都一般。因此我们花了大半个星期的时间才把主程序写出来。写的过程中有不少的挫折。我们刚开始是先写出一个能键盘输入两个一元二次方程并先对每一个方程按指数降序排序。但过了很长时间都没法实现两函数的相加减。后来花了很大力气，查阅了两本资料书才实现了对两函数的相加（减），其实主要还是对链表的插入和删除操作。 总的来说本次课程设计学到了很多知识，让我们对C语言的知识有了更多的了解，也更加深了对C语言和数据结构的认识。对有些不懂的知识点现在也掌握了，学会了链表的建立，受益匪浅。六、 任务分配周田、张永鹏：编写修改主函数，并对设计报告进行修改。武警：给出程序设计方案，并画出程序流程图。李坤：编写C语言伪代码。温凯侨：编写算法思想。阮健健、米昌华：资料收集及对课程设计总结。七、评级周田、张永鹏：A武警、温凯侨、李坤：B阮健健、米昌华：C