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

1、1 课程设计的目的（1）掌握算法的编写方法。（2）掌握类c语言的算法转换成c程序并上机调试的基本方法。（3）设计一个c语言程序，该程序具有能够按照指数降序排列建立并输出多项式，完成两个多项式的相加、相减，并将结果输入的功能。2 设计方案论证2.1 问题描述用c语言编写一段程序，该程序的功能相当于一个一元多项式计算器。它能够实现按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减的运算和将其结果输入的功能。2.2 数据结构设计此程序的数据结构是选择用带表头结点的单链表存储多项式。虽然一元多项式可以用顺序和链式两种存储结构表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时

2、，此时就会浪费了巨大的存储空间，所以应该选择用链式存储结构来存储一元多项式。单链表的结构体可以用来存储多项式的系数，指数，下一个指针3个元属，这样便于实现任意多项式的加法，减法运算。 2.3 设计思路及算法设计图1 功能模块图2.3.2功能模块图思路设计（1）一元多项式的建立输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。（2）显示一元多项式如果系数是大于0的话就输出+系数x指数的形式；如果系数是小于0的话就输出系数x指数

3、的形式；如果指数为0的话，直接输出系数；如果系数是1的话就直接输出+x；如果系数是-1的话就直接输出-x。（3）一元多项式加法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二多项式用新节点产生。（4）一元多项式减法运算它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等

4、的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。（5）帮助 提供正确的输入多项式的方法，以及程序中多项式是如何表示的。2.3.3 算法设计（1）结构体的定义 typedef struct pnodeint coef; int exp;struct pnode *n

5、ext; pnode;（2）一元多项式的输入 pnode * creat() head=(pnode *)malloc(sizeof(pnode);rear=head; while(n!=0) s=(pnode *)malloc(sizeof(pnode);s-coef=n;s-exp=m;s-next=null;rear-next=s; rear=s; head=head-next; return head;（3）显示一元多项式void display(pnode *head) ;int one_time=1; p=head; while(p!=null) if(one_time=1) if

6、(p-exp=0) printf(%d,p-coef); else if(p-coef=1|p-coef=-1) printf(x%d,p-exp); else if(p-coef0) printf one_time=0; else if(p-exp=0) if(p-coef0) printf(+%d,p-coef); else if(p-coef=1) printf(+x%d,p-exp); else if(p-coef=-1) printf(x%d,p-exp); else if(p-coef0) printf(+%dx%d,p-coef,p-exp); else if(p-coefcoe

7、f,p-exp);p=p-next; （4）一元多项式的加法运算 pnode * add(pnode *heada,pnode *headb) p=heada;q=headb;headc=(pnode *)malloc(sizeof(pnode); r=headc; while(p!=null&q!=null) if(p-exp=q-exp) x=p-coef+q-coef;；if(x!=0) s=(pnode *)malloc(sizeof(pnode); s-coef=x;s-exp=p-exp;r-next=s;r=s;q=q-next;p=p-next; s-exp=q-exp;r-n

8、ext=s;r=s;q=q-next; elses=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-exp=p-exp;r-next=s;r=s;p=p-next; while(p!=null) s=(pnode *)malloc(sizeof(pnode); s-coef=p-coef;s-exp=p-exp;r-next=s;r=s;q=q-next; r-next=null;headc=headc-next; return headc; （5）一元多项式减法pnode * sub(pnode *heada,pnode *headb) p=hea

9、da;q=headb; headc=(pnode *)malloc(sizeof(pnode);r=headc; while(p!=null&q!=null) if(p-exp=q-exp) x=p-coef-q-coef; if(x!=0) s=(pnode *)malloc(sizeof(pnode); s-coef=x; s-exp=p-exp; r-next=s; r=s; q=q-next;p=p-next; else if(p-expexp) s=(pnode *)malloc(sizeof(pnode);s-coef=-q-coef; s-exp=q-exp;r-next=s;r

10、=s;q=q-next;elses=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-exp=p-exp;r-next=s;r=s;p=p-next;while(p!=null)s=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-exp=p-exp;r-next=s;s-coef=-q-coef; s-exp=q-exp;r-next=s;r=s;q=q-next;r-next=null;headc=headc-next;return headc2.5 源程序#include#include#include#

11、includetypedef struct pnodefloat coef;int exp;struct pnodepnode;pnode * creat()int m;float n; pnode *head,*rear,*s;head=(pnode *)malloc(sizeof(pnode);rear=head;printf(input coef:);scanf(%f,&n);printf(input exp:);scanf(%d,&m);while(n!=0)s=(pnode *)malloc(sizeof(pnode);s-coef=n;s-exp=m;s-next=null;rea

12、r-next=s;rear=s;printf(input coef:);scanf(%f,&n);printf(input exp:);scanf(%d,&m);head=head-next;return head;void tiao_zheng(pnode *head)pnode *p,*q,*t;float temp;p=head;while(p!=null)q=p;t=q-next;while(t!=null)if(t-expq-exp)q=t;t=t-next;temp=p-coef;p-coef=q-coef;q-coef=temp;temp=p-exp;p-exp=q-exp;p=

13、p-next;void display(pnode *head)pnode *p;int one_time=1; p=head;while(p!=null)if(one_time=1)if(p-exp=0)printf(%f,pelse if(p-coef=1|p-coef=-1)printf(x%d,p-exp);else if(p-coef0)printf(%fx%d,p-coef,p-exp);else if(p-coefcoef,p-exp);one_time=0;elseif(p-exp=0)if(p-coef0)printf(+%f,p-coef);else if(p-coef=1

14、)printf(+x%d,p-exp);else if(p-coef=-1)printf(x%d,p-exp);else if(p-coef0)printf(+%fx%d,p-coef,p-exp);else if(p=p-next;printf(n);pnode * add(pnode *heada,pnode *headb)r=headc;while(p!=null&q!=null)if(p-exp=q-exp)x=p-coef+q-coef;if(x!=0)s=(pnode *)malloc(sizeof(pnode);s-coef=x;s-exp=p-exp;r-next=s;r=s;

15、q=q-next;p=p-next;else if(p-expexp)s=(pnode *)malloc(sizeof(pnode);s-coef=q-coef;s-exp=q-exp;r-next=s;r=s;q=q-next;else 数据结构一元多项式计算s=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-exp=p-exp;=s;r=s;p=p-next;while(p!=null)s=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-exp=p-exp;r-next=s;r=s;p=p-next;w

16、hile(q!=null)s=(pnode *)malloc(sizeof(pnode);s-coef=q-coef;s-exp=q-exp;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;p=heada;q=headb;headc=(pnode *)malloc(sizeof(pnode);r=headc;while(p!=null&q!=null)if(p-exp=q-e

17、xp)x=p-coef-q-coef;if(x!=0)s=(pnode *)malloc(sizeof(pnode);s-coef=x;s-exp=p-exp;r-next=s;r=s;q=q-next;p=p-next;else if(p-expexp)s=(pnode *)malloc(sizeof(pnode);s-coef=-q-coef;s-exp=q-exp;r-next=s;r=s;q=q-next;elses=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-expr-next=s;r=s;p=p-next;while(p!=null)

18、s=(pnode *)malloc(sizeof(pnode);s-coef=p-coef;s-exp=p-exp;r-next=s;r=s;p=p-next;s-exp=q-exp;r-next=s;r=s;q=q-next;r-next=null;headc=headc-next;return headc;void add_main()pnode * a,*b,*c;printf(input the first:n);a=creat();tiao_zheng(a);printf(input the second:n);b=creat();tiao_zheng(b);c=add(a,b);p

19、rintf(the first:);display(a);printf(the second:);display(b);printf(sum is:);display(c);void sub_main()pnode * a,*b,*c;printf(input the first:n);a=creat();tiao_zheng(a);printf(the second:);display(b);printf(sub is:);display(c);void open()printf(*n);printf( 一元多项式计算器n); 数据结构一元多项式计算printf(*n); printf(请选

20、择操作:n); printf(0.退出n); printf(1.两个一元多项式相加n); printf(2.两个一元多项式相减n); printf(3.帮助n);void help() printf(*帮助*n); printf(1.输入时只输入多项式的系数与指数(0 0表示结束)n); printf(2.请按指数升幂形式输入.n); printf(3.例如输入 1 1 2 2 0 0 表示 1*x1+2*x2n);void main() int choose; open(); while(choose!=0) scanf(%d,&choose); getchar(); switch(choo

21、se) case 0: return; case 1: printf(你选择的操作是多项式相加:n); add_main(); choose=-1; open(); break; case 2: printf(你选择的操作是多项式相减:n); sub_main(); choose=-1;open(); break; case 3: help(); default: printf(输入有误!请重新选择操作!n); open(); 3 运行结果分析此时可以选择输入的数字:0代表退出程序；“1”代表两个多项式相加；“2”代表两个多项式相减；“3”提供帮助。若想程序实现两个多项式相加的功能时则输入数字

22、“1”， input the firstinput coef:就是输入第一个多项式的每一项的系数和指数。（注意：输入是随便输入的，输入0和0时退出）coef:是一项的系数，exp：是一项的指数输入第一个多项式为4x4+3x3+ 5x5过程如下：input the first:input coef:4input exp:4input coef:3input exp:3input coef:5input exp:5 数据结构一元多项式计算input coef:0input exp:0输入第2个多项式为3x3+4x4,输入过程同上。输入完显示结果：the first：5x5+4x4+ 3x3the

23、second：4x4+3x3sum is：5x5+8x4+ 6x3若想程序实现两个多项式相减的功能时则输入数字“2”，如图5所示。图5 程序实现减法运算的运行结果图输入的第一个多项为4x4+5x5+ 3x3，输入的第二个多项式3x4+4x5+ 2x3,输入过程同上。输入完显示结果：the first：5x5+4x4+ 3x3the second：4x5+3x4+ 2x3sub is：x5+x4+ x3若想寻求帮助则输入数字“3”数据结构一元多项式计算4 设计体会这次课程设计是通过用我们所学过的带有头结点的单链表的数据结构为基础建立一元多式。再进一步设计一个一元多项式简单计算器。该计算器能够按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减，并将结果输出。通过这次课程设计，我了解c语言这门课的重要性，我们一定要学好c语言。c语言功能强,使用灵活, 可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件,而且c语言语法限制不严格,程序设计自由度