数据结构优秀课程设计优质报告一元稀疏多项式计算器.doc

课程设计汇报
1. 需求分析
【问题描述】
设计一个一元稀疏多项式简单计算器.
【基础要求】
一元稀疏多项式基础功效包含：
1) 输入并建立多项式；
2) 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2, … , cn, en，其中n是多项式项数，ci和ei分别是第i项系数和指数，序列按指数降序排列；
3) 多项式a和b相加，建立多项式a+b；
4) 多项式a和b相减，建立多项式a-b；
【测试数据】
1) (2x+5x8-3.1x11)+(11x9-5x8+7)=(-3.1x11+11x8+2x+7)
2) (-1.2x9+6x-3+4.4x2-x)-(7.8x15+4.4x2-6x-3)=(-7.8x15-1.2x9+12x-3-x)
3) (x5+x4+x3+x2+x+1)-(-x4-x3)=(x5+x2+x+1)
4) (x3+x)-(-x3-x)=0
5) (x100+x)+(x200+x100)=(x200+2x100+x)
6) (x3+x2+x)+0=x3+x2+x
7) 交换上述测试数据中前后两个多项式.
2. 概要设计
ADT Polynomial{
数据对象: D={ai|aiÎTermSet, i=1,2,…,m,m≥0,TermSet中每个元素包含一个表示系数实数和表示指数整数}
数据对象: R1={<ai,ai-1>|ai,ai-1ÎD,且ai-1中指数值小于ai中指数,i=2,…,m}
基础操作：
CreatePolyn(void)
Result: 指数由大到小输入m项系数和指数,建立一元多项式p
PrintPoly (LNode Head)
Result: 输出一元多项式
AddPoly (LNode H1,LNode H2)
Condition: 一元多项式pa,pb已存在
Result: 完成多项式相加运算,即pa=pa+pb,并销毁一元多项式pb.
SubtractPoly (LNode H1,LNode H2)
Condition: 一元多项式pa,pb已存在
Result: 完成多项式相减运算,即pa=pa-pb,并销毁一元多项式pb.
}ADT Polynomial

3. 具体设计
【数据类型定义】
typedef struct node{
int expn,coef;
struct node *next;
}Nodetype,*LNode; //定义结点类型
【函数原型定义】
LNode CreatePolyn(void);
Void PrintPoly (LNode Head);
LNode AddPolyn(LNode H1,LNode H2);
LNode SubPolyn(LNode H1,LNode H2);

【关键算法描述】
CreatePolyn()
LNode CreatePolyn(void) //创建表示式
{
LNode Head,p,pre,pree;
int x,z;
Head=(LNode)malloc(sizeof(Nodetype));
Head->next=NULL;
printf("当你输入系数为0时，输入将结束！\n");
printf("请输入第一项系数:");
scanf("%d",&x);
if(x==0)
{
p=(LNode)malloc(sizeof(LNode));
p->coef=0;
p->expn=0;
Head->next=p;
p->next=NULL;
}
while(x!=0)
{
printf("请输入指数:");
scanf("%d",&z);
p=(LNode)malloc(sizeof(Nodetype));
p->coef=x;
p->expn=z;
pre=Head;
while(pre->next&&pre->next->expn>=z)//原有项指数大于插入项
{
pree=pre;
pre=pre->next;
}
p->next=pre->next;//插入项
pre->next=p;
if(pre->expn==p->expn)//原有项指数等于插入项
{
pre->coef+=p->coef;
pre->next=p->next;
free(p);
}
if(pre->coef==0)//系数为0
{
pree->next=pre->next;
free(pre);
}
printf("请输入系数:");
scanf("%d",&x);
}
if(Head->next==NULL)//多项式空
{
pre=(LNode)malloc(sizeof(LNode));
pre->coef=0;
pre->expn=0;
pre->next=Head->next;
Head->next=pre;
}
return Head;
}

PrintPolyn()
void PrintPolyn(LNode Head) //输出表示式
{
LNode pre;
pre=Head->next;
if(pre->expn==0)//指数为0
printf("%d",pre->coef);
else
printf("%d*X(%d)",pre->coef,pre->expn);
pre=pre->next;
while(pre)//系数不为0
{
if(pre->expn==0)//指数为0
{
if(pre->coef>0)
printf("+%d",pre->coef);
else if(pre->coef<0)
printf("%d",pre->coef);
}
else//指数不为0
{
if(pre->coef>0)
printf("+%d*X(%d)",pre->coef,pre->expn);
else if(pre->coef<0)
printf("%d*X(%d)",pre->coef,pre->expn);
}
pre=pre->next;//遍历每一项
}
printf("\n");
}
AddPolyn()
LNode AddPolyn(LNode H1,LNode H2) //表示式相加
{
LNode H3,p1,p2,p3,pre;//p1第一个多项式项，pre p前一项
H3=(LNode)malloc(sizeof(LNode));
H3->next=NULL; //建立一个空多项式
p1=H1->next; //第一个多项式第一项
p2=H2->next;
pre=H3; //
while(p1&&p2)
{
if(p1->expn>p2->expn)//第一个多项式项指数大于第二个
{
p3=(LNode)malloc(sizeof(LNode));
p3->expn=p1->expn;
p3->coef=p1->coef;
p3->next=pre->next;
pre->next=p3;
pre=p3;
p1=p1->next;
}
else if(p1->expn<p2->expn)//第一个多项式项指数小于第二个
{
p3=(LNode)malloc(sizeof(LNode));
p3->expn=p2->expn;
p3->coef=p2->coef;
p3->next=pre->next;
pre->next=p3;
pre=p3;
p2=p2->next;
}
else if(p1->coef+p2->coef!=0)//相加为不0，指数相同系数相加
{
p3=(LNode)malloc(sizeof(LNode));
p3->expn=p1->expn;
p3->coef=p1->coef+p2->coef;
p3->next=pre->next;
pre->next=p3;
pre=p3;
p1=p1->next;
p2=p2->next;
}
else//相加为0
{
p1=p1->next;
p2=p2->next;
}
}

while(p2)
{
p3=(LNode)malloc(sizeof(LNode));
p3->expn=p2->expn;
p3->coef=p2->coef;
p3->next=pre->next;
pre->next=p3;
pre=p3;
p2=p2->next;
}

while(p1)
{
p3=(LNode)malloc(sizeof(LNode));
p3->expn=p1->expn;
p3->coef=p1->coef;
p3->next=pre->next;
pre->next=p3;
pre=p3;
p1=p1->next;
}

return H3;
}
Substract()
LNode SubstractPolyn(LNode H1,LNode H2) //表示式相减
{//让系数变负，代入加法
LNode H3,pre;
pre=H2->next;
while(pre)
{
pre->coef=-pre->coef;
pre=pre->next;
}
H3=AddPolyn(H1,H2);
pre=H2->next;
while(pre)
{
pre->coef=-pre->coef;
pre=pre->next;
}
return H3;
}
【函数调用关系】
main()调用CreatePoly()，PrintPoly()，AddPoly()，scanf()函数输入，printf()函数输出。

4. 运行统计

5. 总结
首次做课程设计题目，小激动，小担心，编程基础比较差，所以把第二章学习内容仔仔细细看完了一遍，但还不够，在老师问我问题时，我才发觉我对next了解犯错了，对for语句也不太熟悉，所以找了好多个同学请教，最终了解多了一层，不轻易啊。下次要是还有机会做课程设计话，一定要给自己多些时间，来把程序研究透，这跟实习一样，对编程技能很有提升效果，在过程中碰到不了解或不熟悉地方就会翻书本，找课件，查资料，也学会了部分以前很不熟悉函数使用和作用。