一元多项式
河南单招-全国大学生广告艺术大赛
2023年2月20日发(作者：制度汇编)一元多项式计算(数据结构课程
设计)
一、系统设计
1、算法思想
根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的
项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中
的一项；对于两个一元多项式中所有指数不相同的项，则分别写到“和（差）
多项式”中去。
因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构
便于实现一元多项式的运算。为了节省空间，我采用两个链表分别存放多项式a
和多项式b，对于最后计算所得的多项式则利用多项式a进行存储。主要用到了
单链表的插入和删除操作。
(1)一元多项式加法运算
它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等
的话，系数就应该相加；相加的和不为零的话，用头插法建立一个新的节点。P
的指数小于q的指数的话就应该复制q的节点到多项式中。P的指数大于q的
指数的话，就应该复制p节点到多项式中。当第二个多项式空，第一个多项式
不为空时，将第一个多项式用新节点产生。当第一个多项式空，第二个多项式
不为空时，将第二个多项式用新节点产生。
(2)一元多项式的减法运算
它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相
等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点。p的
指数小于q的指数的话，就应该复制q的节点到多项式中。P的指数大于q的
指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相
反数；当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点
产生。当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点
产生，并且建立的节点的系数为原来的相反数。
2、概要设计
(1)主函数流程图：
（注：a代表第一个一元二次方程，b代表第二个一元二次方程）
开始
定义结构体
定义函数类型及名称
构造指数比较函数
排列顺序(降序）
指数不同
输出多项式，求项数
创建并初始化多项式链表
输入系数和指数
指数相同
合并同类项
按指数排序
(2)一元多项式计算算法用类C语言表示：
Typedefstruct00{//项的表示，多项式的项作为LinkList的数据元素
Floatcoef；//细数
Intexpn；//指数
}term，ElemType；//两个类型名：term用于本ADT，ElemType为LinkList的
数据对象名
TypedefLinkListpolynomial：//用带表头的节点的有序链表表示多项式
//基本操作的函数原型说明
VoidCreatePolyn（polynomail&P）；
//输入n的系数和指数，建立表示一元多项式的有序链表P销毁一元多项式P
VoidDestroyPolyn（polynomailP）；
销毁一元多项式P
voidPrintPoly（polynomailP）；
//打印输入一元多项式P
IntPolynLength（polynnomailP);
//返回一元多项式P中的项数
voidCreatPolyn（polynomail&mail&Pb);
//完成多项式相加运算，即:Pa=Pa+Pb,并贤惠一元多项式Pb
voidSubtractPolyn（polunomail&Papolunomail&Pb）；
//完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
//基本操作的算法描述
Intcmp(tema，tempb）；
//依a的指数值b的住数值，分别返回-1、0和+1
VoidCreatePolyn（polynomail&P,intm){
//输入m项的系数和指数，建立表示一元多项式的有序链表P
InitList（P）；h=GetHead（P）；
=0.0；=-1；SerCurElem（h，e）；//设置头结点的数据元素
For（i=1；i<=m；++i）{//依次输入m个非零项
Scanf（，）；
If（！LocateElem（P，e，q，（*cmp）（）））{//当前链表中不存在该指数项
If(MakeNode（s，e））InsFirst（q，s）；//生成节点并插入链表
}
}
}//CreatPolun
二、详细设计
1、算法实现
(1)输入一元多项式函数：
voidshuchu(pnode*head)
{
pnode*p;
intone_time=1;
p=head;
while(p!=NULL)/*如果不为空*/
{
if(one_time==1)
{
if(p->zhishu==0)/*如果指数为0的话，直接输出系数*/
printf("%5.2f",p->xishu);/*如果系数是正的话前面就要加+号*/
elseif(p->xishu==1||p->xishu==-1)
printf("X^%d",p->zhishu);/*如果系数是1的话就直接输出+x*/
/*如果系数是-1的话就直接输出-x号*/
elseif(p->xishu>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/
printf("%5.2fX^%d",p->xishu,p->zhishu);
elseif(p->xishu<0)/*如果系数是小于0的话就输出系数x^指数的形式*/
printf("%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);/*如果系数是正的话前面就要加+号*/
}
elseif(p->xishu==1)/*如果系数是1的话就直接输出+x号*/
printf("+X^%d",p->zhishu);
elseif(p->xishu==-1)/*如果系数是-1的话就直接输出-x号*/
printf("X^%d",p->zhishu);
elseif(p->xishu>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/
printf("+%5.2fX^%d",p->xishu,p->zhishu);
elseif(p->xishu<0)/*如果系数是小于0的话就输出系数x^指数的形式*/
printf("%5.2fX^%d",p->xishu,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个多项
式并向右移动，q指向第2个多项式并向右移动*/
floatx;/*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));/*用头插法建立一个新的节点*/
s->xishu=x;
s->zhishu=p->zhishu;
r->next=s;
r=s;
}
q=q->next;p=p->next;/*2个多项式都向右移*/
}
elseif(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;
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->zhishu;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;/*最后指向空*/
headc=headc->next;/*第一个头没有用到*/
returnheadc;/*返回头接点*/
}
(3)减法函数
/*两个多项式的加法运算*/
pnode*add(pnode*heada,pnode*headb)
{
pnode*headc,*p,*q,*s,*r;/*headc为头指针，r,s为临时指针，p指向第1个多项
式并向右移动，q指向第2个多项式并向右移动*/
floatx;/*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));/*用头插法建立一个新的节点*/
s->xishu=x;
s->zhishu=p->zhishu;
r->next=s;
r=s;
}
q=q->next;p=p->next;/*2个多项式都向右移*/
}
elseif(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;
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->zhishu;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;/*最后指向空*/
headc=headc->next;/*第一个头没有用到*/
returnheadc;/*返回头接点*/
}
2、程序代码
/*一元多项式计算*/
/*程序功能：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的
相加、相减，并将结果输出；*/
/*提示：输入完一元多项式之后，输入“00”结束本一元多项式的输入*/
/*注意：系数只精确到百分位，最大系数只能为999.99,指数为整数.如果需要输
入更大的系数，可以对程序中5.2%f进行相应的修改*/
#include
#include
#include
#include
/*建立结构体*/
typedefstructpnode
{
floatxishu;/*系数*/
intzhishu;/*指数*/
structpnode*next;/*下一个指针*/
}pnode;
/*用头插法生成一个多项式，系数和指数输入0时退出输入*/
pnode*creat()
{
intm;
floatn;
pnode*head,*rear,*s;/*head为头指针，rear和s为临时指针*/
head=(pnode*)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;/*第一个头没有用到*/
returnhead;
}
/*调整多项式*/
voidtiaozhen(pnode*head)
{
pnode*p,*q,*t;
floattemp;
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;
p=p->next;
}
}
/*显示一个多项式*/
voidshuchu(pnode*head)
{
pnode*p;
intone_time=1;
p=head;
while(p!=NULL)/*如果不为空*/
{
if(one_time==1)
{
if(p->zhishu==0)/*如果指数为0的话，直接输出系数*/
printf("%5.2f",p->xishu);/*如果系数是正的话前面就要加+号*/
elseif(p->xishu==1||p->xishu==-1)
printf("X^%d",p->zhishu);/*如果系数是1的话就直接输出+x*/
/*如果系数是-1的话就直接输出-x号*/
elseif(p->xishu>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/
printf("%5.2fX^%d",p->xishu,p->zhishu);
elseif(p->xishu<0)/*如果系数是小于0的话就输出系数x^指数的形式*/
printf("%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);/*如果系数是正的话前面就要加+号*/
}
elseif(p->xishu==1)/*如果系数是1的话就直接输出+x号*/
printf("+X^%d",p->zhishu);
elseif(p->xishu==-1)/*如果系数是-1的话就直接输出-x号*/
printf("X^%d",p->zhishu);
elseif(p->xishu>0)/*如果系数是大于0的话就输出+系数x^指数的形式*/
printf("+%5.2fX^%d",p->xishu,p->zhishu);
elseif(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,*r;/*headc为头指针，r,s为临时指针，p指向第1个多项
式并向右移动，q指向第2个多项式并向右移动*/
floatx;/*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));/*用头插法建立一个新的节点*/
s->xishu=x;
s->zhishu=p->zhishu;
r->next=s;
r=s;
}
q=q->next;p=p->next;/*2个多项式都向右移*/
}
elseif(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;
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->zhishu;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;/*最后指向空*/
headc=headc->next;/*第一个头没有用到*/
returnheadc;/*返回头接点*/
}
/*两个多项式的减法运算*/
pnode*sub(pnode*heada,pnode*headb)
{
pnode*headc,*p,*q,*s,*r;
floatx;/*x为系数相减*/
p=heada;/*指向第一个多项式的头*/
q=headb;/*指向第二个多项式的头*/
headc=(pnode*)malloc(sizeof(pnode));/*开辟空间*/
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个多项式都向右移*/
}
elseif(p->zhishuzhishu)/*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;/*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;/*建立的节点的系数为原来的相反数*/
s->zhishu=q->zhishu;
r->next=s;
r=s;
q=q->next;
}
r->next=NULL;/*最后指向空*/
headc=headc->next;/*第一个头没有用到*/
returnheadc;/*返回头接点*/
}
voidadd_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);
}
voidsub_main()
{
pnode*a,*b,*c;
printf("n输入第一个一元多项式:n系数指数n");
a=creat();
tiaozhen(a);
printf("n输入第二个一元多项式:n系数指数n");
b=creat();
tiaozhen(b);
c=sub(a,b);
printf("第一个一元多项式如下:");shuchu(a);
printf("第二个一元多项式如下:");shuchu(b);
printf("两式相减如下:");shuchu(c);
}
voidopen()
{
printf("n
****************************************************n");
printf("功能项:*1两个一元多项式相加;2两个一元多项式相减;0退出
*n");
printf("
****************************************************nn请选择操作:
");
}
voidmain()
{
intchoose;
open();
while(choose!=0)
{
scanf("%d",&choose);
getchar();
switch(choose)
{
case0:return;
case1:
printf("n两个一元多项式相加n");
add_main();choose=-1;open();break;
case2:
printf("n两个一元多项式相减n");
sub_main();choose=-1;open();break;
default:
printf("没有该选项!请重新选择操作!nn");
open();
}
}
}
三、测试方案及结果
1、测试方案
在VisualC++6.0环境中调试运行。
2、结果及分析
程序运行截图如下：
四、结论及体会
经过一周的努力，最终我们的课程设计出来了，主程序完全符合本课程设计
的要求。
本次课程设计对于我们来说难度是很大的。因为对于数据结构课程设计，需
要有扎实的C语言编程能力，而我们这组人C编程都一般。因此我们花了大半
个星期的时间才把主程序写出来。写的过程中有不少的挫折。我们刚开始是先
写出一个能键盘输入两个一元二次方程并先对每一个方程按指数降序排序。但
过了很长时间都没法实现两函数的相加减。后来花了很大力气，查阅了两本资
料书才实现了对两函数的相加（减），其实主要还是对链表的插入和删除操作。
总的来说本次课程设计学到了很多知识，让我们对C语言的知识有了更多的
了解，也更加深了对C语言和数据结构的认识。对有些不懂的知识点现在也掌
握了，学会了链表的建立，受益匪浅。
五、任务分配
周田、张永鹏：编写修改主函数，并对设计报告进行修改。
武警：给出程序设计方案，并画出程序流程图。
李坤：编写C语言伪代码。
温凯侨：编写算法思想。
阮健健、米昌华：资料收集及对课程设计总结。
七、评级
周田、张永鹏：A
武警、温凯侨、李坤：B
阮健健、米昌华：C