数据结构程序设计报告.docx
《数据结构程序设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构程序设计报告.docx（16页珍藏版）》请在冰点文库上搜索。
数据结构程序设计报告
淮阴工学院
数据结构课程设计报告
选题名称:
一元稀疏多项式计算器
系（院）:
计算机工程系
专业:
计算机科学与技术
班级:
网络1071
姓名:
张鑫学号:
1071304134
指导教师:
张亚红寇海洲胡荣林夏森
学年学期:
2008~2009学年第2学期
2009年6月12日
摘要：
本文是关于任一元稀疏多项式的求解问题的描述，文中使用链式存储结构（带表头结点的单链表）存储一稀疏元多项式，实现了多项式的建立，多项式的输出，多项式a和b相加，多项式a和b相减和求导等功能。
鉴于C语言的优点，经过分析，将用C语言解决一元稀疏多项式的求解问题算法的描述。
关键词：
链表；函数；多项式；数据结构
目录
1需求分析………………………………………………………………3
2设计概要………………………………………………………………4
3详细设计和实现………………………………………………………5
3.1主函数………………………………………………………………5
3.2求导函数和求和函数…………………………………………………5
3.3其他函数……………………………………………………………10
4调试和操作说明………………………………………………………12
5总结……………………………………………………………………15
6致谢……………………………………………………………………16
7参考文献………………………………………………………………17
1需求分析
课程题目：
一元稀疏多项式计算器
问题描述：
设计一个一元多项式加法器
基本要求：
（1）输入并建立多项式；
（2）两个多项式相加；
（3）输出多项式：
n,c1,e1,c2,e2,…cn,en,其中，n是多项式项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（4）计算多项式在x处的值；
（5）求多项式的导函数。
软件环境：
Windows，UNIX，Linux等不同平台下的VisualC++6.0
硬件环境:
512MB内存,80Gb硬盘,Pentium4CPU,CRT显示器。
2概要分析
本程序有五个函数：
PolyNode*Input（）（输入函数）；
PolyNode*Deri（PolyNode*head）（求导函数）；
PolyNode*Plus（PolyNode*A,PolyNode*B）（求和函数）；
voidOutput（PolyNode*head）（输出函数）；
intmain（）（主函数）
本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：
系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。
适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。
其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。
3详细设计和实现
（1）首先介绍主函数：
intmain（）
{
PolyNode*head_a,*head_b;
intchoice;
head_a=newPolyNode;head_a->next=NULL;
do
{
system（"cls"）;//清屏函数
Output（head_a）;
cout<<"______________________________\n";
cout<<"|---------1.输入公式-----------|\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）;//求导
elseif（choice==3）{head_b=Input（）;head_a=Plus（head_a,head_b）;}//求和
elseif（choice==4）break;
elsecout<<"输入错误，重新输入：
\n";
}
while（choice!
=5）;
return0;
（2）由于此程序是二人合作完成，我在此程序中主要是完成求和和求导函数的
设计。
所以下面着重介绍下求和函数和求导函数。
PolyNode*Deri（PolyNode*head）（求导函数）：
流程图如下：
图3.1求导函数流程图
求导函数部分代码：
PolyNode*Deri（PolyNode*head）//求导
{
PolyNode*p=head;
while（p->next!
=NULL）
{
if（p->next->exp==0）p->next=NULL;//指数为零返回
else
{
p->next->coef*=p->next->exp;//系数乘以指数
p->next->exp--;//指数减一
p=p->next;
}
}
returnhead;
用于对输入的多项式进行求导，求导在链表内进行计算，即运算完成链表的值改变，返回头指针。
PolyNode*Plus（PolyNode*A,PolyNode*B）（求和函数）：
流程图如下：
图3.2求和函数流程图
本函数用于对多项式进行加法计算，需要运用存有两个多项式的头指针，前一头指针可是前一计算的计算结果，也可是调用输入函数，后一头指针是调用输入函数输入的多项式的头接点。
经过计算得到一个新的链表，函数返回链表的头指针。
求和函数部分代码
PolyNode*Plus（PolyNode*A,PolyNode*B）//相加
{
PolyNode*head,*p;
head=newPolyNode;
p=head;
A=A->next;
B=B->next;
while（A!
=NULL||B!
=NULL）
{
if（A==NULL）{p->next=B;break;}//如果A空，把B后面的所有接点接到p之后
if（B==NULL）{p->next=A;break;}//如果B空，把A后面的所有接点接到p之后
if（A->exp==B->exp）//如果两指数数相等，相加
{
if（A->coef+B->coef!
=0）
{p->next=newPolyNode;
p=p->next;
p->exp=A->exp;
p->coef=A->coef+B->coef;
}
A=A->next;
B=B->next;continue;//如果两系数互为倒数，不保存，后指，继续循环
}
if（A->exp>B->exp）//A的指数大于B的指数
{
p->next=newPolyNode;
p=p->next;
p->exp=A->exp;
p->coef=A->coef;
A=A->next;continue;//将A的当前接点接到新链表后面，A后指
}
p->next=newPolyNode;
p=p->next;
p->exp=B->exp;
p->coef=B->coef;
B=B->next;//将B的当前接点接到新链表后面，B后指
}
if（A==NULL&&B==NULL）//如果AB都为空
p->next=NULL;
returnhead;//返回头指针
}
（3）其他函数（同组的成员设计）
#include
#include
usingnamespacestd;
typedefstructnode
{
floatcoef;//系数
intexp;//指数
structnode*next;//指针域指向下一个系数不为0的子项
}PolyNode;
PolyNode*Input（）//输入函数
{
floatc;//系数域
inte;//指数域
PolyNode*p,*q,*r,*head;
cout<<"请输入多项式:
\n";
cout<<"形式：
系数1指数1系数2指数2系数3指数3......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";
}
4调试与操作说明
（1）当程序运行时，进入主界面。
如图：
图4.1主界面
此时输入1-4选择操作
（2）输入1后按回车出现：
图4.2输入主界面
输入12345600后按回车之后会出现界面：
图4.3输入后的界面
（3）求导：
输入2求导后按回车会出现结果：
图4.4求导结果
结果正确。
（4）求和：
如果进入图4.3后输入3后按回车会出现界面：
图4.5求和界面
输入22446600后结果会出来：
图4.6求和结果
结果正确。
此系统在得到计算结果后可以直接用计算的结果进行下一步计算，如果不想用当前的结果，也可按“1”重新输入公式进行下一步计算
总结
经过一个学期对数据结构的学习，使我对其有了很大的了解，也对C++进行了温习和了解；在课程设计期间，我们每个人都做了一个课程设计，在这个过程中，遇到了不少困难，但最终还是在自己的努力和同学的帮助下完成了设计，也使我学到了不少。
这个程序比较简单，在书上面有一道习题，而且有一些提示。
我照着书上的结构体写下来，然后思考那三种计算因该用什么样的算法实现。
前面的问题都很简单，但要操作的时候就困难了，因为有很多特殊的情况需要考虑，课程设计前后没多少时间，但是浪费了我几天的时间来想那些函数，不过还是在同学的帮助下解决了它。
在求和函数中遇到了一些困难，但又在自己的努力和同学的帮助下迎刃而解。
后来的程序流程图又花费了不少时间，不过总算完成了。
现在才发现思维对于学习计算机的人来说是多么重要。
程序设计是做完了，在做设计的过程我学到了不少，使我对数据结构的认识有上升到了一个新的高度，使我对自己所学的专业有了新的认识，对自己的定位也清楚了，对自己以后该怎样学，学什么有了新的目标。
致谢
一个礼拜的课程设计圆满结束了，在这次课程设计的过中我得到了许多人的帮助。
首先我要感谢我计算机工程系给了我这次机会，给我们这么好的实验室，让我有个机会提高自己的综合能力。
其次我要感谢我的课程设计指导老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。
在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力，更加让我知道了自己的不足之处，让我今后的学习有了目标。
其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计上的难题。
在这里还要感谢我的小组队长，他给我的帮助最多。
最后要感谢互联网上的朋友们，谢谢你们无私的提供学习资料
最后再一次诚恳的感谢所有帮助我的人，谢谢你们！
参考文献
1殷人昆.数据结构《用面向对象的方法与C++语言描述》.第二版,北京：
清华大学出版社，2008
2张红霞.《数据结构教程与实训》.北京：
北京理工大学出版社，2006
3揣锦华.《面向对象程序设计与VC++实践》.西安电子科技大学出版社，2006
4吴乃陵，况迎辉.《C++程序设计》.北京：
高等教育出版社，2003
5金远平.数据结构《C++描述》.北京：
清华大学出版社，2005
设计任务书
课题
名称
一元稀疏多项式计算器
设计
目的
本课程设计的目的是通过实践使学生经历一个数据结构开发的全过程并受到一次综合的训练，以便能较全面地理解、掌握和综合运用所学的知识去分析、解决实际问题。
实验
环境
软件环境：
Windows，UNIX，Linux等不同平台下的VisualC++6.0
硬件环境:
512MB内存,80Gb硬盘,Pentium4CPU,CRT显示器。
任务
要求
设计一个一元多项式加法器。
【基本要求】
（1）输入并建立多项式；
（2）两个多项式相加；
（3）输出多项式：
n,c1,e1,c2,e2,…cn,en,其中，n是多项式项数，ci和ei分
别是第i项的系数和指数，序列按指数降序排列。
（4）计算多项式在x处的值；
（5）求多项式的导函数。
工作进度计划
序号
起止日期
工作内容
1
2009.6.8－2009.6.8
需求分析
2
2009.6.9－2009.6.9
概念设计
3
2009.6.10－2009.6.10
调试和操作
4
2009.6.10－2009.6.11
课程设计报告纂写
指导教师（签章）：
年月日
指导教师评语
学号
1071304134
姓名
张鑫
班级
网络1071
选题
名称
一元稀疏多项式计算器
序号
评价内容
权重（%）
得分
1
考勤记录、学习态度、工作作风与表现。
5
2
自学情况：
上网检索机时数、文献阅读情况（笔记）。
10
3
论文选题是否先进，是否具有前沿性或前瞻性。
5
4
成果验收：
是否完成设计任务；能否运行、可操作性如何等。
20
5
报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。
30
6
文献引用是否合理、充分、真实。
5
7
答辩情况：
自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。
25
合计
指导教师（签章）：
2009年月日
升级会员 