一元稀疏多项式计算器数据结构.docx
《一元稀疏多项式计算器数据结构.docx》由会员分享，可在线阅读，更多相关《一元稀疏多项式计算器数据结构.docx（11页珍藏版）》请在冰点文库上搜索。
一元稀疏多项式计算器数据结构
中南民族大学
学生实验报告
院系：
计算机科学学院
专业：
软件工程
年级：
2013级
课程名称：
数据结构
姓名：
韦宜（2034）
指导教师：
宋中山
2015年12月15日
题目：
设计一个一元稀疏多项式简单计算器
班级：
软件工程1301姓名：
韦宜学号：
2034完成日期：
12月15日
一、需求分析
问题描述：
设计一个一元多项式加法器
基本要求：
输入并建立多项式；
（2）两个多项式相加；
（3）输出多项式：
n,c1,e1,c2,e2,…cn,en,其中，n是多项式项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（4）计算多项式在x处的值；
（5）求多项式的导函数。
软件环境：
Windows，UNIX，Linux等不同平台下的VisualC++
硬件环境:
512MB内存,80Gb硬盘,Pentium4CPU,CRT显示器。
二、
概要分析
本程序有五个函数：
PolyNode*Input（）（输入函数）；
PolyNode*Deri（PolyNode*head）（求导函数）；
PolyNode*Plus（PolyNode*A,PolyNode*B）（求和函数）；
voidOutput（PolyNode*head）（输出函数）；
intmain（）（主函数）
本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：
系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。
适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。
其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。
三、
详细设计
（1）主函数：
intmain（）
{
PolyNode*head_a,*head_b;
intchoice;
head_a=newPolyNode;head_a->next=NULL;
do
{
system（"cls"）;入公式-----------|\n";
cout<<"|---------2.求导-----------|\n";
cout<<"|---------3.两式求和-----------|\n";
cout<<"|---------4.退出程序-----------|\n";
cout<<"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";
cin>>choice;
if（choice==1）head_a=Input（）;
elseif（choice==2）head_a=Deri（head_a）;
N
N
Y
start
建立以head1为头指针的空链表，A指向后一接点
建立以head2为头指针的空链表，p=head2
q=B的第一个接点
返回指针head1
调用求和函数
head1=head1+head2
A指向后一接点
q指向的接点与A指向的接点相乘，结果保存到head2后面，q指向后一接点
A!
=NULL
q!
=NULL
Y
END
PolyNode
*Mul（PolyNode*A,
PolyNode*B）
start
N
Y
N
Y
N
Y
Y
N
N
Y
N
Y
N
Y
建立链表head，p=head，两头指针A、B均指向各自的next
A、B为空
A的指数大于B的指数
A、B的系数互为倒数
AB指数相等
B为空
A为空
p->next=NULL
将A的当前接点接到新链表后面，A后指
A、B均后指
将B接到p后面
合并相同系数相同项，连接到新链表后面
将A接到p后面
将B的当前接点接到新链表后面，B后指
如果AB都为空
返回头指针
END
PolyNode
*Plus（PolyNode*A,
PolyNode*B）
....00：
\n";
head=newPolyNode;//建立头接点
p=head;p->next=NULL;
for（;;）
{
cin>>c>>e;
if（c==0&&e==0）break;//结束输入
if（c==0）continue;//从新输入，不保存
if（head->next==NULL）//输入第一个接点
{
p->next=newPolyNode;
p=p->next;
p->coef=c,p->exp=e;
p->next=NULL;
continue;
}
p=head;
while（p->next!
=NULL&&e<=p->next->exp）p=p->next;//如果输入的指数小于p的下一个接点，p向后指
if（e==p->exp）{p->coef+=c;continue;}//如果相等，直接加上去，继续循环
q=newPolyNode;
q->coef=c,q->exp=e;
if（p->next!
=NULL&&e>p->next->exp）//如果p的后继接点的指数小于输入的指数，插入到p的当前接点之后
{
r=p->next;
p->next=q;
q->next=r;
continue;
}
p->next=q;//如果输入的值小于所有接点，接在最后一个接点之后
p=p->next;p->next=NULL;
}
returnhead;
}
输出函数
voidOutput（PolyNode*head）//输出
{
PolyNode*p;
p=head->next;
if（p==NULL）{cout<<"当前没有公式或计算结果为0，请选1输入\n";return;}
if（p!
=NULL）
{
cout<<"计算结果：
\n";
cout<coef<<"X~"<exp;p=p->next;
}
while（p!
=NULL）
{
cout<<"+"<coef<<"X~"<exp;
p=p->next;
}
cout<cout<<"如果想重新输入公式，请选1输入\n\n";
}
四、调试分析与操作说明
（1）当程序运行时，进入主界面。
如图：
此时输入1-4选择操作
（2）输入1后按回车出现：
输入12345600后按回车之后会出现界面：
（3）求导：
输入2求导后按回车会出现结果：
结果正确。
（4）求和：
如果进入图后输入3后按回车会出现界面：
图求和界面
输入22446600后结果会出来：
图求和结果
结果正确。
此系统在得到计算结果后可以直接用计算的结果进行下一步计算，如果不想用当前的结果，也可按“1”重新输入公式进行下一步计算
五、心得体会
经过这学期的学习，我对数据结构了解更深了一点，因为第一次修的时候没有认真的去修，所以没有及格，我很惭愧，所以再一次的修让我觉得我该好好学习这么课程，因为对后面的学习都很有影响。
通过做这次实验，我意识到，自己对C语言的掌握稍微熟练了一些；在写程序的过程中，遇到一些问题是在所难免的，但我相信只要用心去做，就一定会有收获。
升级会员 