设计一个一元稀疏多项式计算器论文(1).doc

课程设计（论文）

课程名称： 数据结构课程设计
题 目：一元稀疏多项式简单计算器
院 （系）： 信息与控制工程学院
专业班级： 计算机0901
姓 名： 张 强
学 号： 090620119
指导教师： 李智杰

2011年 9 月 9日

西安建筑科技大学课程设计（论文）任务书
专业班级： 计算机0901 学生姓名： 张强 指导教师（签名）：
一、课程设计（论文）题目
问题描述：设计一个一元稀疏多项式简单计算器。
二、本次课程设计（论文）应达到的目的
数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。
本题目要达到目的：熟练掌握数组、链表的各种应用。
三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）
[基本要求]
（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：n,c1,e1, c2,e2,,,,,,, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；
（3）多项式a和b相加，建立多项式a+b；
（4）多项式a和b相减，建立多项式a-b；
（5）计算多项式在x处的值。
（6）计算器的仿真界面。
四、应收集的资料及主要参考文献：
由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“数组、线性表”及其有关的基本操作。
参考文献：
1．本年级用的教材：数据结构与算法分析（C++版）（第二版）影印版 2005，7；
2．C++程序设计技能百练，中国铁道出版社，2004，1 蒋立翔编著；
3. 数据结构与C++，西安交通大学出版社，1999，11 周叶著；
4．C/C++与数据结构，清华大学出版社，2002，3，1 王立柱；
5．数据结构使用C++语言描述，东南大学出版社，2001，1，1 陈慧南；
五、审核批准意见

教研室主任（签字）

设计总说明

本文介绍了用C++语言编写一个一元稀疏多项式计算器。其内容包括输入并建立多项式, 两个多项式相加以及输出多项式：n, c1, e1, c2, e2, …cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。利用这个程序可以方便的计算简单的一元稀疏多项式的基本运算。本课程设计就是对这样一个简单的计算器进行设计，用以实现一元稀疏多项式基本的运算问题。设计从小处着手，以小见大。运用所学的一些c++知识，构成整个计算器的形成框架。并在程序中定义了各种类型的运算的模块，本程序要求能够实现从键盘键入两个多项式的系数、指数相关数据后，能够进行多项式输出、多项式相加、多项式相减、多项式求值、多项式求积，多项式求商的运算，通过主程序的调用来完成他们之间的配合。来实现输入并建立多项式,两多项式的相加以及多项式的输出。

目录

一． 问题描述················ 1
二． 需求分析················ 1
三． 概要设计················ 2
四． 详细设计················ 3
五． 源代码················· 4
六． 程序测试················17
七． 使用说明················21
八． 课设总结················22
九． 参考文献················23

西安建筑科技大学课程设计（论文）

数据结构课程设计
——一元稀疏多项式简单计算器

一、问题描述

1、基本要求
（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：n,c1,e1, c2,e2,,,,,,, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；
（3）多项式a和b相加，建立多项式a+b；
（4）多项式a和b相减，建立多项式a-b；
（5）计算多项式在x处的值。
（6）计算器的仿真界面。
2、设计目的
数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用
二、 需求分析
1、 设计开发环境：
软件方面：系统 windows xp 编程软件：VC++ 6.0
2、思路分析：
①一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+……+pmxem
其中，p1是指数为ei的项的非零系数，且满足0≦e1<e2<……<em=n ,若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表（（p1,e1）,(p2,e2),……,(pm,em)）便可惟一确定多项式pn(x)。
②用两个带表头结点的单链表分别存储两个多项式
③根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；
④只需要将第二个多项式的系数改为其相反数，然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式”

三、概要设计
菜单
加法
AddPolyn(ma,mb)
减法SubtractPolyn(ma,mb)
乘法
MultiplyPolyn(ma,mb)
求值ValuePolyn(ma,x)
输入Insert(Polyn p,Polyn h)
除法DevicePolyn(ma,mb)
输出desktop()
图3-1功能模块图

为实现上述程序功能，用带表头结点的单链表存储多项式。元素类型，节点类型，和指针类型：typedef struct Polynomial{
int coe; //系数
int exp;//指数
struct Polynomial *next;
}*Polyn,Polynomial;
各个模块之间的调用如图3-1所示，调用insert（）函数将输入的多项式按降幂排列，通过主函数main（）中swith语句，选择用户所选择的对应的模块，然后又模块对应的功能函数对用户输入的数据进行相应的操作，最后通过desktop（）模块将最后结果输出。
开始运行
四、详细设计

多项式加法计算器

退出

求积、商
求和（差）
输入多项式

关闭运行
多项式相加求和
（差）
多项式求积、商
建立2个多项式

输出结果
输出求和（差）
结果
按任意键退出

图4-1 功能实现流程图
4.1 输入模块
用户可通过本模块来输入一个多项式，在每次输入一个多项式时，本模块会先判断谁否是第一次输入，如果是，创建节点，如果不是则模块会通过判断本次输入的数的指数与第一项输入的指数的大小，如果第一项的指数较大，则刚输入的这一项继续与第二项比较指数，以此类推，如果发现刚输入的这一项的指数比比较的这一项的指数要大，则插入比较项的前面。
4.2 求和、差模块
用户通过本模块可以实现两个多项式的求和或差值，此模块先调用输入模块，进行对两个要运算的多项式进行初始化，并按降幂排列。然后将两个多项式的幂进行一个对比，如果第一个数的第一项的系数大于第二个多项式的第一个项的系数，那么直接将第一项赋值于刚开始创建的链表的第一项，作为答案的最后一项，反之亦然，如果第一个数的第一项，与第二个数的第一项的系数相同，那么将两个数的系数与指数分别相加或者相减并将对应值赋值给答案相对应的项。以此类推。最后有输出模块输出最后答案。
4.3求积、商模块
用户可通过该模块实现两个多项式的相乘（相除），此模块先调用输入模块，进行对两个要运算的多项式的初始化，并按降幂排列。然后将第一个数的系数、指数与第二个数的系数、指数分别相乘（相除），相加（相减），并且赋值给答案相应的系数、指数。完成后执行第一个数的第一项与第二个数的第二项进行相应的操作…….执行完之后最后调用输出模块将结果输出到屏幕上。
4.4求值模块
用户可通过此模块实现多项式的求值，此模块调用输入模块，完成相对应的操作，然后需要用户输入此时变量的值，并且将变量的值赋值给变量，最后将答案通过输出模块输出到屏幕上。

五、 源代码
我真诚地保证：
我自己独立地完成了整个程序从分析、设计到编码的全过程。
如果在上述过程中，我遇到了困难而求教于人，那么，我将在程序报告中详细地列举我所遇到的问题，以及别人给我的提示。
在此，我感谢 同学老师对我的启发和帮助。下面的报告中，我还会具体地提到他们在各个方法对我的帮助。
我的程序里中凡是引用到其他程序或文档之处，例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,我都已经在程序的注释里很清楚地注明了引用的出处。
我从未抄袭过别人的程序，也没有盗用别人的程序，无论是修改式地抄袭还是原封不动地抄袭。
我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
<张强>

第 5 页 共 23 页
#include<iostream.h>
#include <stdlib.h>
#include <math.h>
typedef struct Polynomial{
int coe; //系数
int exp;//指数
struct Polynomial *next;
}*Polyn,Polynomial;
Polyn ma,mb;
void Insert(Polyn p,Polyn h)
{
if(p->coe==0) delete p;
else{
Polyn q1,q2;
q1=h;q2=h->next;
while(q2&&p->exp<q2->exp)
{
q1=q2;
q2=q2->next;
}
if(q2&&p->exp==q2->exp)
{
q2->coe+=p->coe;
delete p;
if(!q2->coe)
{
q1->next=q2->next;
delete q2；}
}
else
{
p->next=q2;
q1->next=p;
}
}
}

Polyn CreatePolyn(Polyn head,int m)
{
int i;
Polyn p;
p=head=new Polynomial;
head->next=NULL;
for(i=0;i<m;i++){
p=new Polynomial;;
cout<<"请输入第"<<i+1<<"项的系数:";
cin>>p->coe;
cout<<" 指数:";
cin>>p->exp;
Insert(p,head);
}
return head;
}
void DestroyPolyn(Polyn p)
{
Polyn t;
while(p!=NULL)
{
t=p;
p=p->next;
delete t;
}
}

void PrintPolyn(Polyn Pm)
{
Polyn qa=Pm->next;
int flag=1;
if(!qa)
{
cout<<"0";
cout<<endl;
return;
}
while (qa)
{
if(qa->coe>0&&flag!=1) cout<<"+";
if(qa->coe!=1&&qa->coe!=-1)
{
cout<<qa->coe;
if(qa->exp==1) cout<<"X";
else if(qa->exp) cout<<"X^"<<qa->exp;
}
else
{
if(qa->coe==1)
{
if(!qa->exp) cout<<"1";
else if(qa->exp==1) cout<<"X";
else cout<<"X^"<<qa->exp;
}
if(qa->coe==-1)
{
if(!qa->exp) cout<<"-1";
else if(qa->exp==1) cout<<"-X";
else cout<<"-X^"<<qa->exp;
}
}
qa=qa->next;
flag++;
}
cout<<endl;
}

int compare(Polyn a,Polyn b)
{
if(a&&b)
{
if(!b||a->exp>b->exp) return 1;
else if(!a||a->exp<b->exp) return -1;
else return 0;
}
else if(!a&&b) return -1;
else return 1;
}

Polyn AddPolyn(Polyn pa,Polyn pb)
{
Polyn qa=pa->next;
Polyn qb=pb->next;
Polyn headc,hc,qc;
hc=new Polynomial;
hc->next=NULL;
headc=hc;
while(qa||qb)
{
qc=new Polynomial;
switch(compare(qa,qb))
{
case 1:
{
qc->coe=qa->coe;
qc->exp=qa->exp;
qa=qa->next;
break;
}
case 0:
{
qc->coe=qa->coe+qb->coe;
qc->exp=qa->exp;
qa=qa->next;
qb=qb->next;
break;
}
case -1:
{
qc->coe=qb->coe;
qc->exp=qb->exp;
qb=qb->next;
break;
}
}
if(qc->coe!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else delete qc;
}
return headc;
}

Polyn SubtractPolyn(Polyn pa,Polyn pb)
{
Polyn h=pb;
Polyn p=pb->next;
Polyn pd;
while(p)
{
p->coe*=-1;
p=p->next;
}
pd=AddPolyn(pa,h);
for(p=h->next;p;p=p->next)
p->coe*=-1;
return pd;
}
Polyn MultiplyPolyn(Polyn pa,Polyn pb)
{
Polyn hf,pf;//
Polyn qa=pa->next; //新建一个结点作为pa的后继结点
Polyn qb=pb->next; //新建一个结点作为pb的后继结点
hf=new Polynomial;
hf->next=NULL;
while(qa)//使用while循环，使得多项式的每项得以运算
{
qb=pb->next;
while(qb)
{
pf=new Polynomial;
pf->coe=qa->coe*qb->coe;
pf->exp=qa->exp+qb->exp;
Insert(pf,hf);//调用插入函数，将新的结点插入到新建链表中，并合并同类项
qb=qb->next;
}
qa=qa->next;
}

return hf;//返回所得链表的头指针
}
void DevicePolyn(Polyn pa,Polyn pb)
{
Polyn quotient,remainder,temp1,temp2;
Polyn qa=pa->next;
Polyn qb=pb->next;
quotient=new Polynomial; //建立头结点,存储商
quotient->next=NULL;
remainder=new Polynomial; //建立头结点，存储余数
remainder->next=NULL;
temp1=new Polynomial;
temp1->next=NULL;
temp2=new Polynomial;
temp2->next=NULL;
temp1=AddPolyn(temp1,pa);
while(qa!=NULL&&qa->exp>=qb->exp)
{
temp2->next=new Polynomial;
temp2->next->coe=(qa->coe)/(qb->coe);
temp2->next->exp=(qa->exp)-(qb->exp);
Insert(temp2->next,quotient);
pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2));
qa=pa->next;
temp2->next=NULL;
}
remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb));
pb=temp1;
cout<<endl<<"shang"<<endl;//printf("\t商：");
PrintPolyn(quotient);
cout<<"yushu"<<endl;//printf("\t余数：");
PrintPolyn(remainder);
}
float ValuePolyn(Polyn head,float x)
{
Polyn p;
p=head->next;
float result=0;
while(p!=NULL)
{
result+=(p->coe)*(float)pow(x,p->exp);
p=p->next;
}
return result;
}

void desktop()
{
system("cls");
cout<<endl<<endl<<endl<<" 一元多项式的计算"<<endl;
cout<<" **********************************************"<<endl;
cout<<" ** 1.输出多项式a和b **"<<endl;
cout<<" ** 2.建立多项式a+b **"<<endl;
cout<<" ** 3.建立多项式a-b **"<<endl;
cout<<" ** 4.建立多项式a*b **"<<endl;
cout<<" ** 5.建立多项式a/b **"<<endl;
cout<<" ** 6.计算多项式a的值 **"<<endl;
cout<<" ** 7.退出 **"<<endl;
cout<<" **********************************************"<<endl<<endl;
cout<<" 执行操作:";
}
void input(){
int m,n;
//Polyn pa,pb;
cout<<"请输入多项式a的项数:";
cin>>m;
ma=CreatePolyn(ma,m);
cout<<endl;
cout<<"请输入多项式b的项数:";
cin>>n;
mb=CreatePolyn(mb,n);}
void main()
{
//int m,n;
float x,result;
char key;
//Polyn pa,pb;
cout<<endl<<endl<<endl<<endl<<" 欢迎您的使用！"<<endl;
cout<<" 系统正在初始化数据，请稍后..."<<endl;
_sleep(3*1000);
system("cls");
while(key)
{
desktop();
cin>>key;
switch (key)
{
case'1':input();
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
break;
case'2':input();
//pc=AddPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a+b：";
PrintPolyn(AddPolyn(ma,mb));
//DestroyPolyn(pc);
break;
case'3':input();
//pd=SubtractPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a-b：";
PrintPolyn(SubtractPolyn(ma,mb));
//DestroyPolyn(pd);
break;
case'4':input();
//pd=SubtractPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a*b：";
PrintPolyn(MultiplyPolyn(ma,mb));
//DestroyPolyn(pd);
break;
case'5':input();
//pd=SubtractPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a/b：";
DevicePolyn(ma,mb);
//DestroyPolyn(pd);
break;
case'6':input();
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"输入x的值：x=";
cin>>x;
result=ValuePolyn(ma,x);
cout<<"多项式a的值:"<<result<<endl;
break;
case'7':
DestroyPolyn(ma);
DestroyPolyn(mb);
exit(0);
break;
default:
cout<<"Error!!!"<<endl;
}
cout<<endl<<endl;
system("pause");
}
}
六 、程序测试
测试软件：Microsoft Visual C++ 6.0
测试的数据：
(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2

(2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7

(3) A*B A= 5x6+4x5+3x4 B= 6x6+5x5

(4) A= 5x6+4x5+3x4 X=2

(5) A/B A=2x2 B=x2+1

测试过程与结果：
(1) A= 3x14-8x8+6x2+2
B=2x10+4x8+-6x2
A+B=3x14+2x10-4x8+2

图6-1加法测试图
(2)A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7
A- B=9x14+3x10-x8+5x6-2

图6-2减法测试图
6-2减法测试图
(3)A= 5x6+4x5+3x4 B= 6x6+5x5
A*B =30x12+49x11+38x10+15x9

图6-3乘法测试图
(4)A= 5x6+4x5+3x4 X=2 A=496
、

图6-4求值测试图
（5）A=2x2 B=x2+1
A/B=2余数是-2；

图6-5除法测试图

七、 使用说明
程序开始运行后，出现如图界面：

图7-1界面初始图
1、如果要进行加法运算，请输入2，出现
请输入a的项数：
请输入第一项的系数：
就是输入第一个多项式的每一项的系数和指数。
注意：输入是随便输入的。
如第一个多项式为5x^5;
过程如下：
请输入a的项数：1
请输入a的系数：5
请输入a的指数：5
接着输入第2个多项式的每一项的系数和指数。

输入完以后就直接显示结果了：
2、如果要进行减法运算，请输入3，过程和输入加法一样，输入个多项式即可。
3、如果要退出的话，请输入7即可结束程序的运行。

八、 课设总结
学完数据结构线性表一章后做此题，自觉就想到用带头结点的单链表来存储多项式，只需用结点记录多项式的系数和指数，此数据结构即节省空间又好进行操作，且进行运算的主要设计思路也易想到，大体设计结构在较短时间内能够完成。但当设计到具体细节代码时遇到了不少困难，主要困难是进行结点操作时，对指针考虑得不够细致，调试时常出现指针指错的情况，没有认真理清条件层次。完成此程序后，受益匪浅，它巩固了线性表一章学到的知识，而且重温了函数传参等重点知识。尽管对程序进行大量的调试分析修改，可还有些代码写得十分啰嗦，程序也不够健壮，对多项式的操作只限于2个多项式，还有在界面设计上没花太大心思，界面不美观。这些问题在日后还需进行改善。本次课程设计采用C++语言实现.这次设计基本上能实现指导书上的要求。我们可以通过这个程序实现计算器的一些基本功能,实现相关操作。通过本次课程设计,让我进一步了解了c++的一些知识,C++的字符串处理功能完全依靠字符串数组来实现，很多在其他高级语言中实现的字符串比较等操作，在这里完全依靠函数来实现，因此调试中字符串处理函数的调试很多本次课程设计培养了我们对这些实际问题的分析能力以及解决一些实际问题的能力。通过编程，巩固了我们对编程思想和写程序的能力。课程设计是对我们的学习很有利的一个环节。在这个阶段，我们学会把理论与实际的结合、懂得人与人沟通的重要性，明白合作的可贵。当然，在编写的过程中也出现了很多问题，但通过调试和看书解决了，大大的提高了我自学的能力，学会了遇到问题，如何利用资源去解决问题也明白了要完成一项设计，首先要有扎实的基础知识，这就要求我们在平时的学习中要不断提高自己。其次，要充分利用身边的各种资源，图书馆有很多相关的书，网上也有不少的知识解答，要好好的利用。第三，要多向身边的同学多请教，在交流中提高自己的实力。理论联系实践，在实践中提高。通过这次课程设计中，我加深了对课本知识的理解。

九、参考文献
[1] 王挺，周会平，贾丽丽，许锡山. C++程序设计[M]. 北京：清华大学出版社，2005
[2] 严蔚敏，吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社，2005
[3] 李根强. 数据结构（C++版）习题解答及实训指导[M]. 北京：中国水利水电出版社，2009

第 23 页 共 23 页