一元稀疏多项式简单计算器.docx
《一元稀疏多项式简单计算器.docx》由会员分享，可在线阅读，更多相关《一元稀疏多项式简单计算器.docx（16页珍藏版）》请在冰点文库上搜索。
一元稀疏多项式简单计算器
数据结构课程设计
系别
计算机与通信工程学院
专业
计算机科学与技术
班级学号
姓名
指导教师
成绩
2012年7月12日
一、需求分析
1、问题描述：
（需求分析和背景意义）
设计一个一元稀疏多项式简单计算器.
2、基本要求：
（设计阶段，概要设计和详细设计）
一元稀疏多项式简单计算器的基本功能是:
（1）输入并建立多项式;
（2）输出多项式,输出形式为整数序列:
n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
（3）多项式a和b相加,建立多项式a+b;（4）多项式a和b相减,建立多项式a-b.
3、测试数据：
（2x+5x8-3.1x11）+（7-5x8+11x9）=（-3.1x11+11x9+2x+7）
（6x-3-x+4.4x-2-1.2x9）-（-6x-3+5.4x2-x2+7.8x15）
（1+x+x2+x3+x4+x5）+（-x3-x4）=（1+x+x2+x5）
（x+x3）+（-x-x3）=0
（x+x100）+（x100+x200）=（x+2x100+x200）
（x+x2+x3）+0=x+x2+x3
互换上述测试数据中的前后两个多项式
4、实现提示：
用带表头结点的单链表存储多项式
5、选做内容：
（1）计算多项式在x处的值.
（2）求多项式a的导函数a′.
（3）多项式a和b相乘,建立乘积多项式ab.
（4）多项式的输出形式为类数学表达式.例如,多项式-3x8+6x3-18的输出形式为-3x∧8+6x∧3-18,x15+（-8）x7-14的输出形式为x∧15-8x∧7-14.注意,系数值为1的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项-1x3的输出形式为-x3.
（5）计算器的仿真界面.
二、详细设计
本程序采用VS2010编写，开始创建了一个工程，本程序的文件有：
头文件：
define.h用以定义全局变量
function.h用以声明函数
源文件：
function.cpp用以定义函数
main.cpp主函数
下面罗列每个文件主要代码
define.h
#ifndefDEFINE_H
#defineDEFINE_H
#include
usingnamespacestd;
#include
structlinklistmultinomial
{
floata;
inte;
structlinklistmultinomial*next;
};
typedefstructlinklistmultinomial*linklist,node;
#endif
function.h
#ifndefFUNCTION_H
#defineFUNCTION_H
#include"define.h"
voidwelcome（）;
voidgoodbye（）;
linklistcreatelinklist（linklisthead,intn）;
voidinsert（linklistp,linklisthead）;
voidprintlinklist（linklisthead）;
voidaddlinklist（linklistpa,linklistpb）;
voidsublinklist（linklistpa,linklistpb）;
voiddlinklist（linklistpa）;
voidcalclinklista（linklistpd,intx）;
voidmenu（）;
#endif
function.cpp
#include"define.h"
//欢迎界面
voidwelcome（）
{
cout<<"\n\n\n\n\n";
cout<<"*********************************************************************\n\n"<cout<<"一元稀疏多项式计算器\n\n"<cout<<"制作者：
王雨辰学号：
4100113\n\n"<cout<<"*********************************************************************\n\n\n\n\n\n\n";
cout<<"请输入请求\n\n"<cout<<"1.进入计算器0.退出\n\n"<}
//结束界面
voidgoodbye（）
{
system（"cls"）;
cout<<"\n\n\n\n\n"<cout<<"*********************************************************************\n\n"<cout<<"谢谢使用，再见\n\n"<cout<<"*********************************************************************\n\n\n\n\n\n\n";
}
//创建链表后按照次方从大到小插入
voidinsert（linklistp,linklisthead）
{
if（p->a==0）free（p）;
else
{
linklistp1,p2;
p1=head;
p2=p1->next;
while（p2&&p2->e>p->e）
{
p1=p2;
p2=p2->next;
}
if（p2&&p2->e==p->e）
{
p2->a=p2->a+p->a;
free（p）;
if（p2->a==0）{p1->next=p2->next;free（p2）;}
}
else
{
p->next=p2;
p1->next=p;
}
}
}
//创建链表
linklistcreatelinklist（linklisthead,intn）
{
linklistp;
inti;
p=head=（linklist）malloc（sizeof（node））;
head->next=NULL;
for（i=1;i<=n;i++）
{
p=（linklist）malloc（sizeof（node））;
cout<<"请输入第"<cin>>p->a;
cout<<"请输入第"<cin>>p->e;
insert（p,head）;
}
returnhead;
}
//输出函数
voidprintlinklist（linklisthead）s
{
linklistp=head->next;
if（!
p）cout<<"0";
else//处理首项，若系数为正，省略+
{
if（p->a==1）
{
if（p->e==0）cout<<"1";
elsecout<<"x^"<e;
}
else
if（p->a==0）;
else
if（p->a<0）
{
if（p->e==0）cout<a;
elsecout<a<<"x^"<e;
}
else
{
if（p->e==0）cout<a;
elsecout<a<<"x^"<e;
}
p=p->next;
}
while（p）
{
if（p->a==1）
{
if（p->e==0）cout<<"+1";
elsecout<<"+x^"<e;
}
else
if（p->a==-1）
{
if（p->e==0）cout<<"-1";
elsecout<<"-x^"<e;
}
else
if（p->a==0）;
else
if（p->a<0）
{
if（p->e==0）cout<a;
elsecout<a<<"x^"<e;
}
else
{
if（p->e==0）cout<<'+'<a;
elsecout<<'+'<a<<"x^"<e;
}
p=p->next;
}
cout<}
//a+b
voidaddlinklist（linklistpa,linklistpb）
{
linklistpc;
linklistp1,p2,p3,p;
p3=pc=（linklist）malloc（sizeof（node））;
p1=pa->next;
p2=pb->next;
if（!
（p1||p2））p3->next=NULL;
else
{
while（p1||p2）
{
p=p3->next=（linklist）malloc（sizeof（node））;
if（p1==NULL）{p->a=p2->a;p->e=p2->e;p2=p2->next;}
elseif（p2==NULL）{p->a=p1->a;p->e=p1->e;p1=p1->next;}
else
{
if（p1->e==p2->e）
{
p->a=p1->a+p2->a;p->e=p1->e;p1=p1->next;p2=p2->next;
}
elseif（p1->e>p2->e）{p->a=p1->a;p->e=p1->e;p1=p1->next;}
elseif（p1->ee）{p->a=p2->a;p->e=p2->e;p2=p2->next;}
}
if（p->a==0）free（p）;
elsep3=p;
}
p3->next=NULL;
}
printlinklist（pc）;
}
//a-b
voidsublinklist（linklistpa,linklistpb）
{
linklistpc;
linklistp1,p2,p3,p;
p3=pc=（linklist）malloc（sizeof（node））;
p1=pa->next;
p2=pb->next;
if（!
（p1||p2））p3->next=NULL;
else
{
while（p1||p2）
{
p=p3->next=（linklist）malloc（sizeof（node））;
if（p1==NULL）{p->a=p2->a;p->e=p2->e;p2=p2->next;}
elseif（p2==NULL）{p->a=p1->a;p->e=p1->e;p1=p1->next;}
else
{
if（p1->e==p2->e）{p->a=p1->a-p2->a;p->e=p1->e;p1=p1->next;p2=p2->next;}
elseif（p1->e>p2->e）{p->a=p1->a;p->e=p1->e;p1=p1->next;}
elseif（p1->ee）{p->a=-p2->a;p->e=p2->e;p2=p2->next;}
}
if（p->a==0）free（p）;
elsep3=p;
}
p3->next=NULL;
}
if（pc->next->next==NULL&&pc->next->a==0）//若a-b=0，输出0
cout<<"0"<elseprintlinklist（pc）;
}
//对a求导
voiddlinklist（linklistpa）
{
linklistpd;
linklistp1,p4;
p1=pa->next;
p4=pd=（linklist）malloc（sizeof（node））;
while（p1!
=NULL）
{
p4->next=（linklist）malloc（sizeof（node））;
p4=p4->next;
if（p1->e==0）{p4->a=0;p4->e=0;}
elseif（p1->e==1）{p4->a=p1->a;p4->e=0;}
else{p4->e=p1->e-1;p4->a=p1->a*p1->e;}
p1=p1->next;
}
p4->next=NULL;
printlinklist（pd）;
}
//计算多项式在x处的值
voidcalclinklista（linklistpe,intx）
{
intsum=0,t,i;
linklistp5;
for（p5=pe->next;p5;p5=p5->next）
{
t=1;
for（i=p5->e;i!
=0;）
{
if（i<0）{t/=x;i++;}//指数小于0，进行除法
else{t*=x;i--;}//指数大于0，进行乘法
}
sum+=p5->a*t;
}
cout<}
//菜单
voidmenu（）
{
intm,n,q=1,x;
linklistpa=0,pb=0;
cout<<"请输入多项式a的项数"<cin>>m;
pa=createlinklist（pa,m）;
cout<<"请输入多项式b的项数"<cin>>n;
pb=createlinklist（pb,n）;
cout<<"*********************************************************************\n\n"<cout<<"功能表\n\n"<cout<<"1.输出多项式a2.输出多项式b"<cout<<"3.输出a+b4.输出a-b"<cout<<"5.输出a的导数6.计算多项式a在x处的值"<cout<<"7.计算多项式b在x处的值0.返回主菜单\n\n"<cout<<"*********************************************************************\n\n\n\n\n\n\n";
while（q!
=0）
{
cout<<"请输入命令"<cin>>q;
switch（q）
{case1:
printlinklist（pa）;break;
case2:
printlinklist（pb）;break;
case3:
addlinklist（pa,pb）;break;
case4:
sublinklist（pa,pb）;break;
case5:
dlinklist（pa）;break;
case6:
cout<<"输入x"<>x;calclinklista（pa,x）;break;
case7:
cout<<"输入x"<>x;calclinklista（pb,x）;break;
case0:
q=0;break;
default:
cout<<"输入错误，请重新输入"<}
}
三、调试分析
在这个程序写完后的调试过程中，出现了以下问题：
1、printlinklist函数刚开是测试会出现首项系数为正，带加号的情况，加了个选择后解决此问题。
2、addlinklist，sublinklist函数当做完后结果为0的情况出现不显示的情况，原因是没有及时释放节点，于是加上了free（p）。
3、calclinklista要分清指数是正是负。
通过本次课程设计我更加了解了单链表是怎样应用的，并学会将数据插入链表，删除链表中的数据等等……
四、用户手册
开始界面
然后根据提示输入多项式
然后根据功能表来选择
五、测试结果
（2x+5x8-3.1x11）+（7-5x8+11x9）=（-3.1x11+11x9+2x+7）
（1+x+x2+x3+x4+x5）+（-x3-x4）=（1+x+x2+x5）
（x+x100）+（x100+x200）=（x+2x100+x200）
（x+x2+x3）+0=x+x2+x3
以上结果经过测试运行皆正确
升级会员 