一元多项式计算数据结构课程设计

1、池 州 学 院CHIZHOU COLLEGE 数据结构课程设计报告学 号： 57 54 39 37 20 25 27 姓 名： 周田 张永鹏 武警 温凯侨 李坤 米昌华 阮健健 班 级： 10计算机科学与技术（2）班 指导教师： 成 绩： 数学与计算机科学系一、 课程设计基本情况1、设计名称 一元多项式计算2、主要功能能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；3、设计平台 电脑、Visual c+ 6.0二、 系统设计1、算法思想 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差

2、）多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。 因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了单链表的插入和删除操作。(1) 一元多项式加法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的指数的话，就应该复制p节点到多项式中。当第

3、二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。(2) 一元多项式的减法运算 它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原

4、来的相反数。2、概要设计(1)主函数流程图：（注：a代表第一个一元二次方程，b代表第二个一元二次方程）开 始 定义结构体定义函数类型及名称 构造指数比较函数 排列顺序(降序） 用单链接储存a,b项目的系数和指数 开 始 进 行 加 减 法 运 算 输 出 构 造 出 的 多 项 式指数不同 输出多项式，求项数 创建并初始化多项式链表 输 入 系 数 和 指 数 指数相同合并同类项 按指数排序 结 束 将 单 链 表 的 节 点 释 放，使 已 建 立 的 多 项 式 销 毁a项的指数值=b项的指数值 选 择 语 句a项指数值<b项指数值 输 出 计 算 后 的 多 项 式摘取b的指数值到

5、“和多项式” 按指数值按降序排列摘取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&a

6、mp;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）

7、；/完成多项式相减运算，即：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（！Loc

8、ateElem（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); /*如果系数是正的话

9、前面就要加+号*/ 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("

10、;%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的话就直

11、接输出-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(&quo

12、t;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&&

13、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->zhi

14、shu<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;

15、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);

16、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

17、个多项式并向右移动*/ 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 *

18、)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-&g

19、t;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=

20、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; /*第一个头没

21、有用到*/ return headc; /*返回头接点*/ 2、 程序代码/*一元多项式计算*/*程序功能：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；*/*提示：输入完一元多项式之后，输入“0 0”结束本一元多项式的输入*/*注意：系数只精确到百分位，最大系数只能为999.99,指数为整数.如果需要输入更大的系数，可以对程序中5.2%f进行相应的修改*/#include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<conio.h> /*建

22、立结构体*/ 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);

23、/*系数*/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 he

24、ad; /*调整多项式*/ 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;

25、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); /

26、*如果系数是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

27、的话，直接输出系数*/ 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的话就输

28、出+系数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

29、,*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;

30、 /*系数就应该相加*/ 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->xish

31、u=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)

32、 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

33、=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&&am

34、p;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->zhis

35、hu<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; /

36、*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; /*建立的节点的

37、系数为原来的相反数*/ 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; p