一元稀疏多项式计算器课程设计.docx
《一元稀疏多项式计算器课程设计.docx》由会员分享，可在线阅读，更多相关《一元稀疏多项式计算器课程设计.docx（16页珍藏版）》请在冰点文库上搜索。
一元稀疏多项式计算器课程设计
一元稀疏多项式计算器课程设计
软件学院
课程设计报告书
课程名称数据结构
设计题目一元稀疏多项式计算器
专业班级软件工程11级1班
学号07
姓名
指导教师
2013年1月
1设计时间
2013年1月21日至2013年1月27日
2设计目的
数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。
数据结构是实践性很强的课程。
课程设计是加强学生实践能力的一个强有力手段。
要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。
课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。
严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。
3设计任务
设计一个一元稀疏多项式简单计算器
4设计内容
需求分析
4.1.1.程序所能达到的功能
一元稀疏多项式简单计算器的基本功能是：
（1）输入并建立多项式——creatpolyn（）；
（2）输出多项式，输出形式为整数序列：
n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数升序排列——printpolyn（）；
（3）多项式a和b相加，建立多项式a+b，输出相加的多项式——addpolyn（）；
（4）多项式a和b相减，建立多项式a-b，输出相减的多项式——subpolyn（）。
4.1.2.输入的形式和输入值的范围
一元稀疏多项式计算器需要输入多项式的各项的系数和指数。
系数可以用实数来表示，指数可以用整数来表示，由于整形数据在内存里占用两个字节，所以它的取值范围为-32768—32767。
4.1.3.输出的形式
本程序要输出的是分别把创建的第一个多项式和第二个多项式按指数升序排序，并且把计算加减后的运算结果按指数升序排列输出。
4.1.4.测试数据
（1）正确：
图1程序输出
（2）错误：
图2程序输出
总体设计
4.2.1.本程序中用到的所有抽象数据类型的定义
ADTList{
数据对象：
D={ai|ai∈R,i=1,2,…,n,n≧0}
数据关系：
R1={|ai-1,ai∈D,ai-1,基本操作：
InitList（）
操作结果：
构造一个空的有序表L。
DestroyList（L）
初始条件：
有序表L已存在。
操作结果：
销毁有序表L。
ListLength（L）
初始条件：
有序表L已存在。
操作结果：
返回有序表L的长度。
ClearList（L）
初始条件：
有序表L已存在。
操作结果：
清空链表内容。
Ins_before（N,N）
初始条件：
有序表L已存在。
操作结果：
插入节点到链表。
}ADTOrderedList
ADTPoly{
数据对象：
D={ai|ai为实数，i=1，2，…，n}
数据关系：
R1={}
基本操作：
CreatePoly（L,N）
初始条件：
N为节点，L为有序表。
操作结果：
将N插入多项式的适当位置。
GetPoly（L）
操作结果：
将用户输入转换为节点。
PrintPoly（L）
初始条件：
多项式L已存在。
操作结果：
显示多项式。
AddPoly（L_1,L_2,L_add）
初始条件：
多项式L_1,L_2,L_add已存在。
操作结果：
生成L_1,L_2之和的多项式L_add
DiffPoly（L,L_diff）
初始条件：
多项式L,L_diff已存在。
操作结果：
生成L的导数多项式L_add。
AlterPoly（L）
初始条件：
多项式L已存在。
操作结果：
将L多项式取相反数。
}ADTPoly
4.2.2.主程序的流程
图3主程序流程
4.2.3.各程序模块之间的层次（调用）关系
图4模块层次调用关系
详细设计
4.3.1实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法
TypedefPolynomial4.3.2主程序和其它主要函数伪码算法
主函数和其他函数：
voidmain（）
{
intm,n;
Polynpa=0,pb=0,pc;
printf（"--------------------------------------------------\n"）;
printf（"|软件11-1班***|\n"）;
printf（"--------------------------------------------------\n"）;
printf（"欢迎使用多项式操作程序\n"）;
printf（"请输入a的项数:
"）;
scanf（"%d",&m）;
pa=CreatePolyn（pa,m）;4.3.3数的调用关系图
图5函数调用关系
测试与分析
4.4.1测试
输入：
a=2X+3X^2;b=2X^3+7X^4
输出：
a+b=2X+3X^2+2X^3+7X^4
a-b=2X+3X^2-2X^3-7X^4
图6程序输出
4.4.2分析
此一元稀疏计算器系统基本可能实现计算功能，其“加”与“减”方法都相对比较完整，在调试程序的时候总出现错误，由于知识不全面，不熟练，总需要看书但在输入数据时，要按照严格的格式输入，否则有可能出现死去或崩溃。
若本系统能加上保存功能就更好了，因为一个系统在使用过程中总会关机等，而此系统的缺点却是没有保存功能，关闭之后就要重新建立了。
会慢慢完善。
附录
#include<>
#include<>......插入函数按指数增序插入........*/
voidInsert（Polynp,Polynh）//将p插入到h中
{
if（p->coef==0）free（p）;//若p的系数是0则释放该节点
else
{
Polynq1,q2;
q1=h;
q2=h->next;
while（q2&&q2->expnexpn）//若p的指数大于q2的指数，则继续查找
{
q1=q2;
q2=q2->next;
}
if（q2&&q2->expn==p->expn）//若q2的指数等于p的指数则将两者的系数相加并且赋给q2
{
q2->coef+=p->coef;
free（p）;
if（!
q2->coef）;
q1->next=q2->next;
free（q2）;
}
else
{//把p插入到h当中
q1->next=p;
p->next=q2;
}
}
}
PolynCreatePolyn（Polynhead,intm）{//建立一个头指针为head、项数为m的一元多项式
inti;
Polynp;
p=head=（Polyn）malloc（sizeof（structPolynomial））;
head->next=NULL;
for（i=0;i{
p=（Polyn）malloc（sizeof（structPolynomial））;//建立新结点以接收数据
printf（"请输入第%d项的系数与指数:
",i+1）;
scanf（"%f%d",&p->coef,&p->expn）;
Insert（p,head）;//调用Insert函数插入结点
}
returnhead;
}
voidDestroyPolyn（Polynp）{//销毁多项式p
Polynq1,q2;
q1=p->next;
q2=q1->next;
while（q1->next）
{
free（q1）;
q1=q2;
q2=q2->next;
}
}
voidPrintPolyn（PolynP）{
Polynq=P->next;
intflag=1;//项数计数器
if（!
q）
{//若多项式为空，输出0
putchar（'0'）;
printf（"\n"）;
return;
}
while（q）
{
if（q->coef>0&&flag!
=1）putchar（'+'）;//系数大于0且不是第一项
if（q->coef!
=1&&q->coef!
=-1）
{//系数非1或-1的普通情况
printf（"%g",q->coef）;
if（q->expn==1）putchar（'X'）;
elseif（q->expn）printf（"X^%d",q->expn）;
}
else
{
if（q->coef==1）
{
if（!
q->expn）putchar（'1'）;
elseif（q->expn==1）putchar（'X'）;
elseprintf（"X^%d",q->expn）;
}
if（q->coef==-1）
{
if（!
q->expn）printf（"-1"）;
elseif（q->expn==1）printf（"-X"）;
elseprintf（"-X^%d",q->expn）;
}
}
q=q->next;
flag++;
}
printf（"\n"）;
}
intcompare（Polyna,Polynb）{
if（a&&b）
{
if（!
b||a->expn>b->expn）return-1;
elseif（!
a||a->expnexpn）return1;
elsereturn0;
}
elseif（!
a&&b）return-1;//a多项式已空，但b多项式非空
elsereturn1;//b多项式已空，但a多项式非空
}
PolynAddPolyn（Polynpa,Polynpb）{//求解并建立多项式a+b，返回其头指针
Polynqa=pa->next;
Polynqb=pb->next;
Polynheadc,hc,qc;
hc=（Polyn）malloc（sizeof（structPolynomial））;//建立头结点
hc->next=NULL;
headc=hc;
while（qa||qb）
{
qc=（Polyn）malloc（sizeof（structPolynomial））;
switch（compare（qa,qb））{
case1:
{
qc->coef=qa->coef;
qc->expn=qa->expn;
qa=qa->next;
break;
}
case0:
{
qc->coef=qa->coef+qb->coef;
qc->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case-1:
{
qc->coef=qb->coef;
qc->expn=qb->expn;
qb=qb->next;
break;
}
}
if（qc->coef!
=0）
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
elsefree（qc）;//当相加系数为0时，释放该结点
}
returnheadc;
}
PolynSubtractPolyn（Polynpa,Polynpb）{//求解并建立多项式a-b，返回其头指针
Polynh=pb;
Polynp=pb->next;
Polynpd;
while（p）
{//将pb的系数取反
p->coef*=-1;
p=p->next;
}
pd=AddPolyn（pa,h）;
for（p=h->next;p;p=p->next）//恢复pb的系数
p->coef*=-1;
returnpd;
}
voidmain（）
{
intm,n;
Polynpa=0,pb=0,pc;
printf（"--------------------------------------------------\n"）;
printf（"|软件11-1班***|\n"）;
printf（"--------------------------------------------------\n"）;
printf（"欢迎使用多项式操作程序\n"）;
printf（"请输入a的项数:
"）;
scanf（"%d",&m）;
pa=CreatePolyn（pa,m）;//建立多项式a
printf（"请输入b的项数:
"）;
scanf（"%d",&n）;
pb=CreatePolyn（pb,n）;//建立多项式b
printf（"\n输出多项式a="）;
PrintPolyn（pa）;
printf（"\n输出多项式b="）;
PrintPolyn（pb）;
pc=AddPolyn（pa,pb）;
printf（"\n输出多项式之和a+b="）;
PrintPolyn（pc）;
pc=SubtractPolyn（pa,pb）;
printf（"\n输出多项式之差a-b="）;
PrintPolyn（pc）;
printf（"\n感谢使用此程序！
\n"）;
DestroyPolyn（pa）;
DestroyPolyn（pb）;
}
5总结与展望
在编程过程中很容易发现程序中的错误，要尽快找出这些错误，使程序能正确运行。
平时缺乏锻炼即使在明确的出错提示下也往往找不出错误，不知道该怎么办，而求救于别人。
但更重要的是通过自己的直接实践来累积。
因此，在实验时千万不要在程序通过后就认为万事大吉、完成任务了，而应当在已通过的程序基础上作一些改动，再进行编译、连接和运行。
我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要让我们勤动手，多实践。
刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。
老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次和同学讨论研究，逐渐能自己找出错误，并加以改正。
此次的程序设计能够成功，是我和我的同学共同努力作用的结果。
在这一段努力学习的过程中，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。
现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。
只要努力去学习，就会灵活的去应用它。
参考文献
[1]严蔚敏，吴伟民数据结构（c语言版）清华大学出版社；
[2]谭浩强c程序设计（第四版）清华大学出版社；
成绩评定
成绩教师签字
升级会员 