数据结构一元多项式的计算.docx
《数据结构一元多项式的计算.docx》由会员分享，可在线阅读，更多相关《数据结构一元多项式的计算.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构一元多项式的计算
课程设计成果
学院:
计算机工程学院班级:
13计科一班
学生姓名:
学号:
设计地点（单位）：
设计题目：
一元多项式的计算
完成日期：
年月日
成绩（五级记分制）:
_________________
教师签名:
_________________________
1、需求分析
建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果。
随着科学技术的发展，计算机领域不断取得新的研究成果。
计算机在代替和延伸脑力劳动方面发挥越来越重要的作用，不仅在工业方面而且在日常生活中也越来越离不开计算机。
尤其是在学校里，要处理大量的学生数据。
随着科学技术的不断提高,计算机科学日渐成熟,其强大的功能已为人们深刻认识,它已进入人类社会的各个领域并发挥着越来越重要的作用.
一元多项式在日常生活中应用也比较广泛，在数学领域，我们看似简单的问题，用程序编码出来其实要考虑很多思想，一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项，链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数，指数以及指向下一个多项式结点的指针，创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加，相减操作。
算法不像我们平时用眼睛直观观察到的，电脑只会运行在逻辑上有条理合理的东西，不会进行变通，在编写算法时，要认真考虑算法的每一步的运算，之后程序该做什么等问题。
1能够按照多项式变量的指数降序创建一个多项式；
2能够对已创建的多项式进行显示；
3能够对已创建的多项式之间的加法运算；
4能够对已创建的多项式之间的减法运算；
5能够对已创建的多项式进行删除；
6能够实现计算器退出操作；
2概要设计
2.1一元多项式的建立
输入多项式采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头结点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入。
2.2显示一元多项式
如果系数是大于0的话就直接输出系数，如果系数是正的话前面就要加+号，如果系数是1的话就直接输出+x，如果系数是-1的话就直接输出-x号，如果系数是大于0的话就输出+系数x^指数的形式，如果系数小于0的话就输出系数x^指数的形式。
2.3一元多项式减法运算
它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相减；相加的和不为零的话，用头插法建立一个新的节点，p的指数小于q的指数的话，就应该复制q的节点到多项式中，p的指数大于q的指数的话就应该复制p的节点到多项式中，并且建立的节点的系数为原来的相反数，当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生，当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生，并且建立的节点的系数为原来的相反数。
2.4一元多项式加法运算
它从两个多项式的头部开始，两个多项式的某一项都不为空时，如果指数相等的话，系数就相加；相加的和不为零的话，用头插法建立一个新的节点，p的指数小于q的指数的话，就应该复制q的节点到多项式中，p的指数大于q的指数的话就应该复制p的节点到多项式中，当第二个多项式空，第一个多项式不为空时，将第一个多项式用新节点产生，当第一个多项式空，第二个多项式不为空时，将第二个多项式用新节点产生。
2.5设计优缺点
优点：
1.能够实现一元多项式的加，减运算，算法也不是很复杂，容易理解，在空间复杂度上比较节省存储空间。
2.所有的操作大多是在内存中实现，增加操作的速度，在操作的时候我们可以利用链表来实现随机的操作，十分的方便。
缺点：
1.这个算法具有一般性，对于有些特殊的一元多项式采用顺序存储会比较方便，在时间复杂度上可以节省很多算法的时间。
2.在最坏的情况下，即n+1个系数都不为零，则比只存储系数的方法（顺序存储）多存储一倍的数据，对于非零系数多的多项式则不宜采用这种表示。
3详细设计
3.1一元多项式的输入输出流程图
1、输入输出
（1）功能：
将要进行运算的多项式输入输出。
（2）数据流入：
要输入的多项式的系数与指数。
（3）数据流出：
合并同类项后的多项式。
程序流程图：
多项式输入流程图如图3-1所示。
（4）测试要点：
输入的多项式是否正确，若输入错误则从新输入。
图3-1多项式输入流程图
3.2一元多项式的加法流程图
2、一元多项式的加法
（1）功能：
将两多项式相加。
（2）数据流入：
输入函数。
（3）数据流出：
多项式相加后的结果。
（4）程序流程图：
多项式的加法流程图如图3-2所示。
测试要点：
两多项式是否为空，为空则提示重新输入，否则，进行运算
图3-2多项式的加法流程图
3.3一元多项式的减法流程图
3、一元多项式的减法
（5）功能：
将两多项式相减。
（6）数据流入：
输入函数。
（7）数据流出：
多项式相减后的结果。
（8）程序流程图：
多项式的减法流程图如图3-3所示。
测试要点：
两多项式是否为空，为空则提示重新输入，否则，进行运算
图3-3多项式的减法流程图
3.4用户操作函数
Typedefstructpnode{//项的表示，多项式的项作为pnode的数据元素
Floatxishu;//系数
Intzhishu；//指数
/*用头插法生成一个多项式，系数和指数输入0时退出输入*/
pnode*creat（）
/*调整多项式*/
voidtiaozhen（pnode*head）
/*输出一元多项式函数：
*/
voidshuchu（pnode*head）
/*两个多项式的加法运算*/
pnode*add（pnode*heada,pnode*headb）
/*相加的函数*/
voidadd_main（）
/*减法函数*/
voidsub_main（）
4编码
函数流程：
pnodeL=NULL;//定义一个链表，即我们所操作的链表信息都可从这个变量获得
voidmain（）{
//初始化链表
InitList（L）;
//调用用户界面，接受用户的操作选择
switch（）;
}
创建链表（程序开始）—>
初始化链表—>
调用用户界面，接受用户的操作选择—>
错误提示，请用户重新操作->
#include
#include
#include
#include
5调试分析
主要的调试过程有三个：
1.对一元多项式的输出，输出函数voidshuchu（pnode*head），在开始界面上调整，字段的布局，刚开始时由于换行没有加上，界面如下
图5-1调试之前
经过修改之后，界面变得整洁一点，用户更能接受一点，修改之后的图如下：
图5-2调试之后
测试输入“1“页面正常，说明逻辑设计正确。
2.链表的调试。
总得来说链表的调试是相对简单的，毕竟都是在内存里运行的，记录和显示数据的。
调试阶段最重要的还是耐性和细心。
要有足够的耐性去对待令人烦躁的错误，一步步细心的调试，就会查出错误的所在。
我们进行调试、测试是为了让我们的代码、程序更加健壮，质量更高。
所以，我们不要畏惧报错，这是个学习进步的过程。
我们应在错误中，认识到自己的不足与薄弱的知识点，提高自己的编写代码能力和改正错误的能力。
6.测试结果及运行效果
运行程序后的登陆后的界面，在其中，可以选择：
两个一元多项式相加、两个一元多项式相减，可以按1,2，或者按0键退出。
图6-1登陆后的界面
输入1进入一元多项式相加页面后，需要输入第一个一元多项式的系数和指数，注意这里的指数是按降序排列的，系数可以是正的，负的也可以是小数，以输入00为结束标志，再按Enter键，输入第二个一元多项式的系数和指数。
图6-2进入一元多项式的操作界面
操作完成之后，界面出现的结果如图所示：
图6-3一元多项式运行的结果界面
一元多项式的减法操作也是一样的进行，运行的结果如下：
图6-4一元多项式减法的运行结果
图6-5退出界面
7.系统开发所用到的技术
操作系统：
Windows7
开发软件:
Devc++
技术：
功能模块（函数）；指针；结构；链表；
模块与函数:
功能模块：
求解较小问题的算法与程序称作“功能模块”，各功能模块可以先单独设计，然后将求解所有的子问题的模块组合成求解原问题的程序。
将一个大问题分解成多个解决小问题的模块的设计思想。
由功能模块组成程序的结构：
主控模块和模块组成。
模块还可细分。
自顶向下，逐步分解的设计思想
函数：
完成相对独立功能和程序。
模块独立：
功能独立的子功能模块之间的关系简单，使用独立变量，模块规模适当：
分解模块要注意层次：
（1）对问题抽象化
（2）设计时细化
设计原则：
高内聚，低耦合
指针就是指向变量和对象的地址。
指针的用途非常广泛，比如如果你想通过函数改变一个变量的值，就得用指针而不能用值传递。
还有在很多时候变量，特别是对象的数据量实在太大，程序员就会用指针来做形参，只需要传递一个地址就行，大大提高了效率。
指针就是指向变量和对象的地址。
指针的用途非常广泛，比如如果你想通过函数改变一个变量的值，就得用指针而不能用值传递。
还有在很多时候变量，特别是对象的数据量实在太大，程序员就会用指针来做形参，只需要传递一个地址就行，大大提高了效率。
c语言之所以强大，以及其自由性，很大部分体现在其灵活的指针运用上。
因此，说指针是c语言的灵魂，一点都不为过。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：
一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相比于线性表顺序结构，链表比较方便插入和删除操作。
参考文献
[1]李素若,陈万华等编著.数据结构（c语言描述）.北京：
中国水利水电出版社,2014.
[2]李素若,琚辉,严永松等编著.数据结构习题解答及上机指导.北京：
中国水利水电出版社,2014.
[3]任正云，李素若编著.C语言程序设计.北京：
中国水利水电出版社,2011.
附录全部代码
//一元多项式计算
//程序功能：
能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出
//提示；输入完一个多项式之后，输入“00”结束本一元多项式的输入
//注意；系数只精确到百分位，最大系数只能为999.99，指数为整数，如果需要输入更大的系数，可以对程序中5.2%f进行相应的修改
#include
#include
#include
#include
//建立结构体
typedefstructpnode
{
floatxishu;//系数
intzhishu;//指数
structpnode*next;//下一个指针
}pnode;
voidopen_（）
{
printf（"\n*********************************************\n"）;
printf（"功能项:
\n1两个一元多项式相加；\n2两个一元多项式相减:
\n0退出*\n"）;
printf（"***********************************************\n\n请选择操作：
"）;
}
//调整多项式
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;
}
}
//用头插法生成一个多项式，系数和指数输入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）;//输入指数
}
//12//
head=head->next;//第一个头没有用到
returnhead;
}
//输出一元多项式函数：
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）;//如果系数是正的话前面就要加+号
else
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指向第一个多项式并向右移动，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向右移动
}
}//当第二个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生
while（p!
=NULL）
{
s=（pnode*）malloc（sizeof（pnode））;
s->xishu=p->xishu;
r->next=s;
r=s;
p=p->next;
}
//当第一个多项式空，第一个数不为空时，将第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;//headc为头指针，r,s为临时指针，p指向第一个多项式并向右移动，q指向第二个多项式并向右移动
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）
{
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向右移动
}
elseif（p->zhishu>q->zhishu）//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向右移动
}
}
//当第二个多项式空，第一个数不为空时，将第一个数剩下的全用新节点产生
while（p!
=NULL）
{
s=（pnode*）malloc（sizeof（pnode））;
s->xishu=p->xishu;
s->zhishu=p->zhishu;
r->next=s;
r=s;
p=p->next;
}
//当第一个多项式空，第一个数不为空时，将第二个数剩下的全用新节点产生
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;//返回头接点
}
voidadd_main（）
{
pnode*a,*b,*c;
printf（"\n输入第一个一元多项式:
\n系数指数\n"）;
a=creat（）;
tiaozhen（a）;
//17
printf（"\n输入第二个一元多项式：
\n系数指数\n"）;
b=creat（）;
tiaozhen（b）;
c=add（a,b）;
printf（"第一个一元多项式如下：
"）;shuchu（a）;
printf（"第二个一元多项式如下：
"）;shuchu（b）;
printf（"两式相加如下：
升级会员 