数据结构一元多项式计算
1 课程设计的目的
（1）掌握算法的编写方法。
（2）掌握类C语言的算法转换成C程序并上机调试的基本方法。
（3）设计一个C语言程序，该程序具有能够按照指数降序排列建立并输出多项式，
完成两个多项式的相加、相减，并将结果输入的功能。
2 设计方案论证
2.1 问题描述
用C语言编写一段程序，该程序的功能相当于一个一元多项式计算器。它能够实现按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减的运算和将其结果输入的功能。
2.2 数据结构设计
此程序的数据结构是选择用带表头结点的单链表存储多项式。虽然一元多项式可以用顺序和链式两种存储结构表示，但顺序结构的最大长度很难确定。比如当多项式的系数较大时，此时就会浪费了巨大的存储空间，所以应该选择用链式存储结构来存储一元多项式。单链表的结构体可以用来存储多项式的系数，指数，下一个指针3个元属，这样便于实现任意多项式的加法，减法运算。
2.3 设计思路及算法设计
2.3.1功能模块图 如图1所示。 若图片无法显示请联系QQ3710167,本论文免费,转发请注明源于www.lwfree.cn
图1 功能模块图
2.3.2功能模块图思路设计
（1）一元多项式的建立
输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。
（2）显示一元多项式
如果系数是大于0的话就输出+系数x^指数的形式；如果系数是小于0的话就输出系数x^指数的形式；如果指数为0的话，直接输出系数；如果系数是1的话就直接输出+x；如果系数是-1的话就直接输出-x。
（3）一元多项式加法运算
它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二多项式用新节点产生。
（4）一元多项式减法运算
它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。
p的指数小于q的指数的话，就应该复制q节点到多项式中。p的指数大于q的指数的话，就应该复制p节点到多项式中，并且建立的节点的系数为原来的相反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。
（5）帮助
提供正确的输入多项式的方法，以及程序中多项式是如何表示的。
2.3.3 算法设计
（1）结构体的定义
typedef struct pnode{int coef; int exp; struct pnode *next; }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(p->exp==0) printf("%d",p->coef); else if(p->coef==1||p->coef==-1) printf("x^%d",p->exp); else if(p->coef>0) printf one_time=0; } else{ if(p->exp==0) {if(p->coef>0) 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->coef>0) printf("+%dx^%d",p->coef,p->exp); else if(p->coef<0)71
数据结构一元多项式计算
printf("%dx^%d",p->coef,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->next=s; r=s; q=q->next; } else
{s=(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;需要完整内容的请联系QQ3710167，本文免费，转发请注明源于www.lwfree.cn q=q->next; } r->next=NULL;
headc=headc->next; return headc;
（5）一元多项式减法
pnode * sub(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; } else if(p->exp
exp)
{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; 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 headc
数据结构一元多项式计算
2.4 流程图 如图2所示。 需要完整内容的请联系QQ3710167，本文免费，转发请注明源于www.lwfree.cn
图2 一元多项式输入功能模块的流程图
2.5 源程序
#include
#include
#include
#include
typedef struct pnode
{float coef;
int exp;
struct pnode
}pnode;
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;
rear->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->exp>q->exp)
q=t;
t=t->next;
}
temp=p->coef;p->coef=q->coef;q->coef=temp;
temp=p->exp;p->exp=q->exp;;
p=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",p
else if(p->coef==1||p->coef==-1)
printf("x^%d",p->exp);
else if(p->coef>0)
printf("%fx^%d",p->coef,p->exp);
else if(p->coef<0)
printf("%fx^%d",p->coef,p->exp);
one_time=0;
}
else{
if(p->exp==0)
{if(p->coef>0)
printf("+%f",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->coef>0)
printf("+%fx^%d",p->coef,p->exp);
else if(
}
p=p->next;
}
printf("\n");
}
pnode * add(pnode *heada,pnode *headb)
{
需要完整内容的请联系QQ3710167，本文免费，转发请注明源于www.lwfree.cn
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=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;
}
while(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->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=s;
q=q->next;
}
else
{s=(pnode *)malloc(sizeof(pnode));
s->coef=p->coef;
s->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;
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);
printf("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("请选择操作:\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*X^1+2*X^2\"\n");
}
void main()
{
int choose;
open();
while(choose!=0)
{
scanf("%d",&choose);
getchar();
switch(choose)
{
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 运行结果分析
程序运行成功之后如图3所示。
图3 程序运行成功界面图
此时可以选择输入的数字:0代表退出程序；“1”代表两个多项式相加；“2”代表两个多项式相减；“3”提供帮助。
若想程序实现两个多项式相加的功能时则输入数字“1”，如图4所示。
需要完整内容的请联系QQ3710167，本文免费，转发请注明源于www.lwfree.cn
图4 程序实现加法运算的运行结果图
图中出现
input the first
input coef:
就是输入第一个多项式的每一项的系数和指数。
（注意：输入是随便输入的，输入0和0时退出）
coef:是一项的系数，exp：是一项的指数
输入第一个多项式为4x^4+3x^3+ 5x^5
过程如下：
input the first:
input coef:4
input exp:4
input coef:3
input exp:3
input coef:5
input exp:5
数据结构一元多项式计算
input coef:0
input exp:0
输入第2个多项式为3x^3+4x^4,输入过程同上。
输入完显示结果：
the first：5x^5+4x^4+ 3x^3
the second：4x^4+3x^3
sum is：5x^5+8x^4+ 6x^3
若想程序实现两个多项式相减的功能时则输入数字“2”，如图5所示。
图5 程序实现减法运算的运行结果图
输入的第一个多项为4x^4+5x^5+ 3x^3，输入的第二个多项式3x^4+4x^5+ 2x^3,输入过程同上。
输入完显示结果：
the first：5x^5+4x^4+ 3x^3
the second：4x^5+3x^4+ 2x^3
sub is：x^5+x^4+ x^3
需要完整内容的请联系QQ3710167，本文免费，转发请注明源于www.lwfree.cn
若想寻求帮助则输入数字“3”，如图6所示。
图6 帮助界面图
图中提示正确的输入方法以及程序是怎样表示一元多项式。
数据结构一元多项式计算
4 设计体会
这次课程设计是通过用我们所学过的带有头结点的单链表的数据结构为基础建立一元多式。再进一步设计一个一元多项式简单计算器。该计算器能够按照指数降序排列建立并输出多项式，并且能够完成两个多项式的相加、相减，并将结果输出。
通过这次课程设计，我了解C语言这门课的重要性，我们一定要学好C语言。C语言功能强,使用灵活, 可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件,而且c语言语法限制不严格,程序设计自由度大。所以我们要学会正确的使用C语言编程. 而《数据结构》学的怎么样直接影响到我们对其它专业课的学习和今后业务的成长。我觉得我们对于《数据结构》的学习不
仅包括理论部分的学习，还要让我们勤动手，多实践。通过了这次课程设计使我得到了充分的锻炼，并使自己得到了较大的提高。
在编程过程中善于发现程序中的错误，并且能很快地排除这些错误，使程序能正确运行。经验丰富的人，当编译时出现“出错信息”时，能很快地判断出错误所在，并改正之。而缺乏经验的人即使在明确的出错提示下也往往找不出错误而求救于别人。调试程序的经验固然可以借鉴他人的现成经验，但更重要的是通过自己的直接实践来累积，而且有些经验是只能“会意”难以“言传”。因此，在实验时千万不要在程序通过后就认为万事大吉、完成任务了，而应当在已通过的程序基础上作一些改动(例如修改一些参数、增加程序一些功能、改变输入数据的方法等)，再进行编译、连接和运行。
最后我要衷心的感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利!
5 参考文献
[1] 严蔚敏,吴伟民.数据结构(C语言版)[M]. 北京:清华大学出版社, 2007.4：39-43
[2]李春葆. 数据结构(C语言版)习题与解析[M].北京:清华大学出版社, 2001.1：47-55
[3]李云清，杨庆红，揭安全.数据结构（C语言版）[M]. 北京:人民邮电出版社，2006.1：44-67
[4]赵文静. 数据结构与算法[M]. 北京:科学出版社，2005.8：41-65
[5]刘大有.数据结构[M]. 北京：高等教育出版社, 2001.3：39-48
[6]王敬华，林萍，.陈静. C语言程序设计[M]. 北京: 清华大学出版社, 2005.10 :29-39
[7]傅清祥,王晓东. 数据结构与算法设计[M]. 北京: 电子工业出版社, 2002.3：33-46
[8]朱若愚.数据结构[M].北京: 电子工业出版社, 2004.1:44-55
