一、课程题目：一元稀疏多项式计算器
二、需求分析
1、一元稀疏多项式简单计算器的功能是：
1.1 输入并建立多项式；
1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,………cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
1.3多项式a和b相加，建立多项式a+b；
1.4 多项式a和b相减，建立多项式a-b。2、设计思路:
2、设计思路：
2.1 定义线性表的动态分配顺序存储结构；
2.2 建立多项式存储结构，定义指针*next
2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式
2.4演示程序以用户和计算机的对话方式执行，即在计算机终站上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令； 根据相应的输入数据（滤去输入中的非法字符）和运算结果显示在其后。
3、程序执行的命令包括：
1）输入多项式a；2）输入多项式b;3）求a+b;4)求a-b；5）求a*b；6）求a的导数；7）求b的导数；8）退出程序。
4、测试数据：
1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);
2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15)
=(-7.8x^15-1.2x^9+12x^-3-x);
3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);
4、(x+x^3)+(-x-x^3)=0;
5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);
6、(x+x^2+x^3)+0=x+x^2+x^3.
7、互换上述测试数据中的前后两个多项式
三、概要设计
为了实现上述功能需用带表头结点的单链表存储多项式。为此需要两个抽象的数据类型：线性表和多项式。
1.有序表的抽象数据类型定义为：
ADT List{
数据对象：D={ai|ai∈Elemset,i=1,2,?，n,n≥0} 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,?,n} 基本操作：
PolyNode *p,*q,*r,*head; 操作结果:构造一个空的线性表。。 Listinsert(&L,i,e)
初始条件:线性表L存在，0≤i≤L的元素个数。 操作结果:在L中第i个位置之后插入新的结点e。
}ADT List
2、多数据类型定义为：
ADT Polynomial {
数据对象:D={ai,bi|ai为不为0的实数，bi为整数，i=2,?,n}
数据关系:R1={ai，bi}
基本操作：
PrintPolyn(Polyn p)
操作结果:输出多项式p。
DestroyPolyn(Polyn p)
操作结果:销毁多项式p。
Polyn CreatePolyn(Polyn head,int m)
操作结果:创建一个m项的多项式。
Polyn AddPolyn(Polyn pa,Polyn pb)
初始条件:多项式链表pa,pb存在。
操作结果:创建一新多项式链表p，其结点为pa，pb相加。
Polyn SubtractPolyn(Polyn pa,Polyn pb)
初始条件:多项式链表pa，pb存在。
操作结果:创建一新多项式链表p，其结点为怕pa，pb相减。
ValuePolyn(Polyn head,int x)
操作结果:输入x值，计算并返回多项式的值
}ADT Polynomial
四、 详细设计
1、元素类型、结点类型和指针类型
typedef int Status;
typedef struct{
int coef;
int expn;
}Term;
typedef Term ElemType;
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,* LinkList;
2、 主函数和其他函数
void main()
{
int m,n,a,x;
int flag;
Polynomial pa,pb,pc;
printf(" 欢迎使用多项式操作程序\n");
//输出菜单
printf("\n 1: 创建多项式a \n");
printf("\n 2: 创建多项式b \n");
printf("\n 3: 输出多项式a \n");
printf("\n 4: 输出多项式b \n");
printf("\n 5: 输出a+b \n");
printf("\n 6: 输出a-b \n");
printf("\n 7: 输出a的导数 \n");
printf("\n 8: 输出b的导数 \n");
printf("\n 9: 代入x的值计算a \n");
printf("\n 10: 代入x的值计算b \n");
printf("\n 11: 输出a*b \n");
printf("\n 12:退出程序 \n");
while(a)
{
printf("\n请选择操作：");
scanf(" %d",&flag);
switch(flag)
{
case 1 :
{
printf("请输入a的项数:");
scanf("%d",&m);
CreatePolyn(pa,m);
break;
}
case 2 :
{
printf("请输入b的项数:");
scanf("%d",&n);
CreatePolyn(pb,n);
break;
}
case 3 :
{
printf("\n 多项式a=");
PrintPolyn(pa);
break;
}
case 4 :
{
printf("\n 多项式b=");
PrintPolyn(pb);
break;
}
case 5 :
{
AddPolyn(pa,pb,pc);
printf("\n a+b=");
PrintPolyn(pc);
break;
}
case 6 :
{
SubtractPolyn(pa,pb,pc);
printf("\n a-b=");
PrintPolyn(pc);
break;
}
case 7 :
{
Polynomial_derivatePolyn(pa,pc);
printf("\n 多项式a的导函数为：a'=");
PrintPolyn(pc);
break;
}
case 8 :
{
Polynomial_derivatePolyn(pb,pc);
printf("\n 多项式b的导函数为：b'=");
PrintPolyn(pc);
break;
}
case 9 :
{
printf("输入x的值：x=");
scanf("%d",&x);
printf("\n x=%d时，a=%.3f\n",x,ValuePolyn(pa,x));
break;
}
case 10 :
{
printf("输入x的值：x=");
scanf("%d",&x);
printf("\n x=%d时，b=%.3f\n",x,ValuePolyn(pb,x));
break;
}
case 11 :
{
MultiplyPolyn(pa,pb,pc);
printf("\n a*b=");
PrintPolyn(pc);
break;
}
case'12':
{
printf("\n 感谢使用此程序！\n");
DestroyPolyn(pa);
DestroyPolyn(pb);
a=0;
break;
}
default:
printf("\n 您的选择错误，请重新选择!\n");
}
}
}
3、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点
Status CreatePolyn(Polynomial &head,int m){ //建立一个头指针为head、项数为m的一元多项式
int i;
LNode *p;
p=head=(Polynomial)malloc(sizeof(struct LNode));
head->next=NULL;
for(i=0;i<m;i++){
p=(Polynomial)malloc(sizeof(struct LNode)); //建立新结点以接收数据
printf("请输入第%d项的系数与指数:",i+1);
scanf("%d %d",&p->data.coef,&p->data.expn);
Insert(p,head); //调用Insert函数插入结点
}
return OK;
}//CreatePolyn
4、求解并建立多项式a+b
Status AddPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a+b，返回其头指针
LNode *qa=pa->next;
LNode *qb=pb->next;
LNode *headc,*hc,*qc;
hc=(Polynomial)malloc(sizeof(struct LNode)); //建立头结点
hc->next=NULL;
headc=hc;
while(qa||qb)
{
qc=(Polynomial)malloc(sizeof(struct LNode));
switch(compare(qa,qb)){
case 1:
{
qc->data.coef=qa->data.coef;
qc->data.expn=qa->data.expn;
qa=qa->next;
break;
}
case 0:
{
qc->data.coef=qa->data.coef+qb->data.coef;
qc->data.expn=qa->data.expn;
qa=qa->next;
qb=qb->next;
break;
}
case -1:
{
qc->data.coef=qb->data.coef;
qc->data.expn=qb->data.expn;
qb=qb->next;
break;
}
}
if(qc->data.coef!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else free(qc); //当相加系数为0时，释放该结点
}
pc=headc;
return OK;
}
5、求解并建立多项式a-b
Status SubtractPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a-b，返回其头指针
LNode *h=pb;
LNode *p=pb->next;
LNode *pd,*pf;
while(p)
{ //将pb的系数取反
p->data.coef*=-1;
p=p->next;
}
AddPolyn(pa,h,pf);
pd=pf;
for(p=h->next;p;p=p->next) //恢复pb的系数
p->data.coef*=-1;
pc=pd;
return OK;
}
float ValuePolyn(Polynomial head,int x){ //输入x值，计算并返回多项式的值
LNode *p;
int i,t;
float sum=0;
for(p=head->next;p;p=p->next)
{
t=1;
for(i=p->data.expn;i!=0;)
{
if(i<0){t/=x;i++;} //指数小于0，进行除法
else{t*=x;i--;} //指数大于0，进行乘法
}
sum+=p->data.coef*t;
}
return sum;
}
6、求解并建立导函数多项式
Status Polynomial_derivatePolyn(Polynomial P,Polynomial &pc)
//求导
{
LNode *p,*pf,*ph;//用于遍历结点
p=P->next;
ph=(Polynomial)malloc(sizeof(struct LNode));
ph->next=NULL;
//pre=P;
while (p!=NULL)
{
pf=(Polynomial)malloc(sizeof(struct LNode));
if(p->data.expn==0)
{
p=p->next;
//free(p);
//p=pre->next;
}
else
{
pf->data.coef=p->data.coef*p->data.expn;
pf->data.expn=p->data.expn-1;
Insert(pf,ph);
p=p->next;
}
}
pc=ph;
return OK;
}
7、求解并建立多项式a*b
Status MultiplyPolyn(Polynomial pa,Polynomial pb,Polynomial &pc){ //求解并建立多项式a*b，返回其头指针
LNode *hf,*pf;
LNode *qa=pa->next;
LNode *qb=pb->next;
hf=(Polynomial)malloc(sizeof(struct LNode));//建立头结点
hf->next=NULL;
for(;qa;qa=qa->next)
{
for(qb=pb->next;qb;qb=qb->next)
{
pf=(Polynomial)malloc(sizeof(struct LNode));
pf->data.coef=qa->data.coef*qb->data.coef;
pf->data.expn=qa->data.expn+qb->data.expn;
Insert(pf,hf); //调用Insert函数以合并指数相同的项
}
}
pc=hf;
return OK;
}
8、函数的调用关系图
四、 调试分析
5.1 运行该程序的操作平台：
5.1.1 硬件要求：
此程序需在一台PC机上运行,要用INTER或AMD的CPU,其他没多大要求。 5.1.2 软件要求：
本程序能在Visual C++ 6.0下运行。
5.2 错误分析：
1、 函数名拼写错误
2、 括号匹配错误
3、 变量类型名定义错误
4、 分号没有在英文环境下输出，导致运行出错
5、 参数表出现语法错误，函数调用的一组参数之间没有以逗号隔开，并以一个右括号结束
六、 用户手册
1、本程序的执行文件为：Cpp1.exe。
2、进入演示程序后即显示文本方式的用户界面。
3、根据提示数字执行操作。如输入数字“1”
4、执行相应命令后显示操作结果。
七、 测试结果
1、最初的界面
2、选择操作“1”、“2”“3”、“4”，输入数字得到的结果，即创建多项式a和b
3、a+b
4、a-b
5、a*b
6、求导
7、带入x值求a，b
八、 心得体会
通过这次课程设计，我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要勤动手，多实践。真正将这个程序做出来很不容易，但只要只要用心去做，总会有收获,特别是当我遇到问题时，通过向同学请教,最后终于找到方法时,并理解代码的含义时，心中是无比喜悦的。编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。