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

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项指数值 (2)一元多项式计算算法用类c语言表示： typedef

5、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（polyn

6、omail 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（polynomai

7、l&p,int m)/输入m项的系数和指数，建立表示一元多项式的有序链表pinitlist（p）；h=gethead（p）；e.coef=0.0；e.expn=-1；sercurelem（h，e）；/设置头结点的数据元素for （i=1；izhishu=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-xis

8、hu0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf(%5.2fx%d,p-xishu,p-zhishu); else if(p-xishuxishu,p-zhishu); one_time=0; else if(p-zhishu=0) /*如果指数为0的话，直接输出系数*/ if(p-xishu0) printf(+%5.2f,p-xishu); /*如果系数是正的话前面就要加+号*/ else if(p-xishu=1) /*如果系数是1的话就直接输出+x号*/ printf(+x%d,p-zhishu); else if(p-xishu=-1) /*如果系数是-1

9、的话就直接输出-x号*/ printf(x%d,p-zhishu); else if(p-xishu0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf(+%5.2fx%d,p-xishu,p-zhishu); else if(p-xishuxishu,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个多项式并

10、向右移动，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(

11、pnode); /*用头插法建立一个新的节点*/ s-xishu=x; s-zhishu=p-zhishu; r-next=s; r=s; q=q-next;p=p-next; /*2个多项式都向右移*/ else if(p-zhishuzhishu) /*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=(

12、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)

13、 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指向

14、第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);

15、/*用头插法建立一个新的节点*/ s-xishu=x; s-zhishu=p-zhishu; r-next=s; r=s; q=q-next;p=p-next; /*2个多项式都向右移*/ else if(p-zhishuzhishu) /*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 *)

16、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=(pnod

17、e *)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,指数为整

18、数.如果需要输入更大的系数，可以对程序中5.2%f进行相应的修改*/#include #include #include #include /*建立结构体*/ 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

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

20、*/ 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-zhishuq-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 on

21、e_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-xishu0) /*如果系数是大于0的话就输出+系数x指数的形式*/ printf(%5.2fx%d,p-xishu,p

22、-zhishu); else if(p-xishuxishu,p-zhishu); one_time=0; else if(p-zhishu=0) /*如果指数为0的话，直接输出系数*/ if(p-xishu0) 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-xishu0) /*如果

23、系数是大于0的话就输出+系数x指数的形式*/ printf(+%5.2fx%d,p-xishu,p-zhishu); else if(p-xishuxishu,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; /*指向第一个多项式的头*

24、/ 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;

25、r=s; q=q-next;p=p-next; /*2个多项式都向右移*/ else if(p-zhishuzhishu) /*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;

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

27、shu; 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); /*开辟空间*

28、/ 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-zhishuzhishu) /*p的系数小于q的系

29、数的话*/ 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

30、(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; /*第一个头没有用到*/ r

31、eturn 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输入第二个一