顺序结构、动态链表下的一元多项式-程序设计报告

1、中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:席旺学 号：学 院:软件学院专 业:软件工程题 目:顺序结构、动态链表下的一元多项式指导教师何志英2011年12月20日1. 设计任务概述（包括系统总体框图及功能描述）在这次的课程设计中我选择的题目是顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。分别采用顺序结构和链式存储结构，利用多项得结果，最后得多项式中不含有重复阶项和零系数得项。除此之外，还得分为降幂和升幂两种排序方式。一元多项式相乘一元多项式输出一元多项式销毁退出一元多项式创建一元多项式相加一元多项式的四则运算一元多项式相减 一元多项式计算器模块调用图2.本设计所

2、采用的数据结构（如：链表、栈、树、图等）顺序存储结构和链式存储结构。3.功能模块详细设计本程序主要分为四大模块：主程序模块输入模块：通过Getpolyn函数输入输出模块（升幂降幂）：PrintPolyn函数实现输出数据处理模块（多项式的加减乘）：通过一元多项式的Polynomial基本操作实现3.1 详细设计思想动态链表结构下的一元多项式的加法、减法、乘法的实现。 设有一元多项式Am(x)和Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn 实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-B

3、n(x)和M(x)= Am(x)Bn(x)。（1）输入形式和输入值范围：输入的系数为float类型，输入的幂为int类型请选择:1请输入你要运算的第一个一元多项式的项数:2请输入第1项的系数和指数:系数:1指数:1请输入第2项的系数和指数:系数:1指数:2（2）输出形式请选择:5一元多项式A为：x+x2一元多项式B为：4x4+5x5+6x6（3）程序所能达到的功能1)首先判定多项式是否稀疏;2)采用动态存储结构实现;3)结果M(x)中无重复阶项和无零系数项；4)要求输出结果的升幂和降幂两种排列情况（4）测试数据：包括正确地输入及其输出结果和含有错误的输入及其输出结果。正确的输入：请选择:5一元

4、多项式A为：x+x2一元多项式B为：4x4+5x5+6x6错误的输入：请输入第1项的系数和指数:系数:1指数:1请输入第2项的系数和指数:系数:2指数:1输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式请输入第1项的系数和指数:.3.2 核心代码#include#includetypedef struct float coef; /系数 int expn; /指数term;typedef struct LNode term data; /term多项式值 struct LNode *next;LNode,*LinkList;typedef LinkList polynoma

5、il;/*比较指数*/int cmp(term a,term b) if(a.expnb.expn) return 1; if(a.expn=b.expn) return 0; if(a.expnnext!=NULL;p=p-next); r=p; for(h=pa;h-next!=r;)/大的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-data,p-next-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向参与比较的最后一

6、个，不断向前移动 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p-next!=NULL;p=p-next); r=p; for(h=pa;h-next!=r;)/小的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-next-data,p-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向参与

7、比较的最后一个，不断向前移动 /*打印多项式,求项数*/int printpolyn(polynomail P) int i; polynomail q; if(P=NULL) printf(无项！n); else if(P-next=NULL) printf(Y=0n); else printf(该多项式为Y=);q=P-next;i=1; if(q-data.coef!=0&q-data.expn!=0) printf(%.2fX%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) printf(%.2f,q-d

8、ata.coef);/打印第一项 q=q-next; if(q=NULL) printf(n);return 1; while(1)/while中，打印剩下项中系数非零的项， if(q-data.coef!=0&q-data.expn!=0) if(q-data.coef0) printf(+); printf(%.2fX%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) if(q-data.coef0) printf(+); printf(%f,q-data.coef); q=q-next; if(q=NULL)

9、 printf(n); break; return 1;/*1、创建并初始化多项式链表*/polynomail creatpolyn(polynomail P,int m) polynomail r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode); r=P; for(i=0;idata.coef,&s-data.expn); r-next=s; r=s; r-next=NULL; if(P-next-next!=NULL) for(q=P-next;q!=NULL/*&q-next!=NULL*/;q=q-next)/合并同类项 for(p=q-n

10、ext,r=q;p!=NULL;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next; p=p-next; return P;/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r;int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode

11、); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef+q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; bre

12、ak; case 1: s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.coef=q-data.coef; s-data.ex

13、pn=q-data.expn; r-next=s; r=s; q=q-next; r-next=NULL; for(q=newp-next;q-next!=NULL;q=q-next)/合并同类项 for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j);

14、 if(j=1) arrange1(newp); else arrange2(newp); return newp;/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r,Q; int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-dat

15、a.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef-q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break;

16、 /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=NULL; if(newp-next!=NULL&newp-next-next!=NUL

17、L)/合并同类项 for(q=newp-next;q!=NULL;q=q-next) for(p=q-next,r=q;p!=NULL;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next; p=p-next; printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return n

18、ewp;/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode); r=newp; for(p=pa-next;p!=NULL;p=p-next) for(q=pb-next;q!=NULL;q=q-next) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef*q-data.coef; s-data.expn=p-data.expn

19、+q-data.expn; r-next=s; r=s; r-next=NULL; printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); for(;i!=0;i-) for(q=newp-next;q-next!=NULL;q=q-next)/合并同类项 for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-da

20、ta.coef; r=p-next; p-next=p-next-next; free(r); return newp;/*5、销毁已建立的两个多项式*/void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; while(p!=NULL) q=p; p=p-next; free(q); p=pb; while(p!=NULL) q=p; p=p-next; free(q); printf(两个多项式已经销毁n);void main() polynomail pa=NULL,pb=NULL; polynomail p,q;

21、 polynomail addp=NULL,subp=NULL,mulp=NULL; int n,m; int sign=y; printf(1、创建两个一元多项式n); printf(2、两多项式相加得一新多项式n); printf(3、两多项式相减得一新多项式n); printf(4、两多项式相乘得一新多项式n); printf(5、销毁已建立的两个多项式n); printf(6、退出n); printf(n); while(sign!=n) printf(请选择：); scanf(%d,&n); switch(n) case 1: if(pa!=NULL) printf(已建立两个一元多

22、项式，请选择其他操作！); break; printf(请输入第一个多项式：n); printf(要输入几项：); scanf(%d,&m); while(m=0) printf(m不能为0，请重新输入m:); scanf(%d,&m); pa=creatpolyn(pa,m); printpolyn(pa); printf(请输入第二个多项式：n); printf(要输入几项：); scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=NULL) printf(请先创建两个一元多项式！n); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=NULL) printf(请先创建两个一元多项式！n); break; subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=NULL) printf(请先创建两个一元多