实习一 一元稀疏多项式简单计算器.docx
《实习一 一元稀疏多项式简单计算器.docx》由会员分享，可在线阅读，更多相关《实习一 一元稀疏多项式简单计算器.docx（21页珍藏版）》请在冰点文库上搜索。
实习一一元稀疏多项式简单计算器
实习一
1．需求分析：
【问题描述】：
设计一个一元稀疏多项式简单计算器。
【基本要求】：
（1）输入并建立两个多项式；
（2）多项式a与b相加，建立和多项式c；
（3）多项式a与b相减，建立和多项式d；
（4）输出多项式a,b,c,d。
输出格式：
比如多项式a为：
，其中，
和
分别为第i项的系数和指数，且各项按指数的升幂排列，即0≤
＜
＜…＜
。
【开发环境】：
系统：
windows7
编程软件：
VC++6.0
2.设计：
在数学上，一个n次一元多项式可表示为
=
+
+
+…+
它由（n+1）个系数序列
、
、…、
唯一确定。
因此，在计算机中，可用一个线性表P表示：
P=（
…,
）
其中，
代表
中的i次项系数。
一般情况下，一元n次多项式写成：
其中，0≤
＜
＜…＜
且
记作线性表P=（（
）,（
）…（
））
其中，元素为二元组（系数，指数）
多项式的单链表示意图:
图示分别为多项式
A（x）=7+3x+9x8+5x17
B（x）=8x+22x7-9x8
两个多项式相加运算规则：
两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复制到“和多项式”中。
两个多项式相减运算规则：
两个多项式中所有指数相同的项对应系数相减，若差不为零，则构成“减多项式”中的一项；对于指数不同的项，A中项复制到“减多项式”中，B中各项符号变化（原来为“+”的项符号变为“-”；为“-”的项符号变为“+”）复制到“减多项式”中。
模块图：
具体思想：
设p和q分别指示多项式A和B中某一结点，
当p和q均非空时，比较p->exp与q->exp：
若p->expexp，加法则p所指结点是“和多项式”中的一项，令指
针p后移；减法则p所指结点是“减多项式”中的一项，令指针p后移。
若p->exp>q->exp，
加法则q所指结点是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；减法则将q->coef=-q->coef,将q其插入结点p之前，且令指针q在原来的链表上后移。
若p->exp==q->exp，
加法则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。
减法则将两个结点中的系数相减，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。
if（q==null）A即为“和多项式”结果（加法）；A即为“减多项式”结果（减法）。
if（p==null）（加法）将剩余的q表全部链接至原A最后一个结点的后继；（减法）将剩余的q并且令q->coef=-q->coef全部链接至原A最后一个结点的后继。
其中结点结构体定义如下：
typedefstructLinklistomial{
floatcoef;
intexpn;
structLinklistomial*next;
}*Linklist;
建立链表函数如下：
voidInsert（Linklistp,Linklisth）{
if（p->coef==0）free（p）;//系数为0的话释放结点
else
{
Linklistq1,q2;
q1=h;
q2=h->next;
while（q2&&p->expn>q2->expn）{//查找插入位置
q1=q2;
q2=q2->next;
}
if（q2&&p->expn==q2->expn）{//将指数相同相合并
q2->coef+=p->coef;
free（p）;
if（!
q2->coef）{//系数为0的话释放结点
q1->next=q2->next;
free（q2）;
}
}
else{//指数为新时将结点插入
p->next=q2;
q1->next=p;}
}
}
LinklistCreateLinklist（Linklisthead,intm）{
//建立一个头指针为head、项数为m的一元多项式
inti;
Linklistp;
head=（Linklist）malloc（sizeof（structLinklistomial））;
head->next=NULL;
for（i=0;ip=（Linklist）malloc（sizeof（structLinklistomial））;//建立新结点以接收数据
printf（"请输入第%d项的系数与指数:
",i+1）;
scanf（"%f%d",&p->coef,&p->expn）;
Insert（p,head）;//调用Insert函数插入结点
}
returnhead;
}
3.调试分析
1.一元稀疏多项式计算器在调试时，问题主要出现在多项式相加和相减后所建立的多项式，将其输出时，符号和系数的错误,即PrintLinklist函数有问题。
在进行相加减时要考虑第一项的系数，第一项的系数为正数时不需要‘+’，而为负数数时，则需要加上‘—’，系数为零时，将其释放掉；系数为1时，也不需要将其显示出来。
经过反复调试，最终解决了这些问题。
2.算法的时空分析：
对多项式进行加减运算的空间复杂度和时间复杂度都是O（n）。
4.用户手册
运行程序后，上面会提示你输入所建多项式a的项数，每次输入两个数，一个为系数，另一个为指数，多项式a建立完成后，然后再建多项式b，最后出现一个相当于菜单的框，输入前面的字母就会显示所得结果。
5.测试结果
6.源代码
………………………...................................................cal.h……………………………………….
typedefstructLinklistomial{
floatcoef;
intexpn;
structLinklistomial*next;
}*Linklist;
voidInsert（Linklistp,Linklisth）{
if（p->coef==0）free（p）;//系数为0的话释放结点
else
{
Linklistq1,q2;
q1=h;
q2=h->next;
while（q2&&p->expn>q2->expn）{//查找插入位置
q1=q2;
q2=q2->next;
}
if（q2&&p->expn==q2->expn）{//将指数相同相合并
q2->coef+=p->coef;
free（p）;
if（!
q2->coef）{//系数为0的话释放结点
q1->next=q2->next;
free（q2）;
}
}
else{//指数为新时将结点插入
p->next=q2;
q1->next=p;}
}
}
LinklistCreateLinklist（Linklisthead,intm）{
//建立一个头指针为head、项数为m的一元多项式
inti;
Linklistp;
head=（Linklist）malloc（sizeof（structLinklistomial））;
head->next=NULL;
for（i=0;ip=（Linklist）malloc（sizeof（structLinklistomial））;//建立新结点以接收数据
printf（"请输入第%d项的系数与指数:
",i+1）;
scanf（"%f%d",&p->coef,&p->expn）;
Insert（p,head）;//调用Insert函数插入结点
}
returnhead;
}
voidDestroyLinklist（Linklistp）{//销毁多项式p
Linklistq1,q2;
q1=p->next;q2=q1->next;
while（q1->next）{
free（q1）;
q1=q2;
q2=q2->next;}
}
voidPrintLinklist（Linklistp）{
Linklistq=p->next;
intflag=1;//项数计数器
if（!
q）{//若多项式为空，输出0
printf（"0"）;
printf（"\n"）;
}
while（q）
{
if（q->coef>0&&flag!
=1）
printf（"+"）;//系数大于0且不是第一项
if（q->coef!
=1&&q->coef!
=-1）{//系数非1或-1的普通情况
printf（"%g",q->coef）;
if（q->expn==1）
printf（"X"）;
elseif（q->expn）printf（"X^%d",q->expn）;
}
else{
if（q->coef==1）
{
if（!
q->expn）
printf（"1"）;
elseif（q->expn==1）
printf（"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（Linklista,Linklistb）{
if（a&&b）
{if（!
a||a->expnexpn）return1;
elseif（!
b||a->expn>b->expn）return-1;
elsereturn0;
}
elseif（!
a&&b）return-1;//a多项式已空，但b多项式非空
elsereturn1;//b多项式已空，但a多项式非空
}
LinklistAddLinklist（Linklistpa,Linklistpb）{//求解并建立多项式a+b，返回其头指针
Linklistqa=pa->next;
Linklistqb=pb->next;
Linklistheadc,hc,qc;
hc=（Linklist）malloc（sizeof（structLinklistomial））;//建立头结点
hc->next=NULL;
headc=hc;
while（qa||qb）
{
qc=（Linklist）malloc（sizeof（structLinklistomial））;
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;
}
LinklistSubLinklist（Linklistpa,Linklistpb）{//求解并建立多项式a-b，返回其头指针
Linklistqa=pa->next;
Linklistqb=pb->next;
Linklistheadd,hd,qd;
hd=（Linklist）malloc（sizeof（structLinklistomial））;//建立头结点
hd->next=NULL;
headd=hd;
while（qa||qb）
{
qd=（Linklist）malloc（sizeof（structLinklistomial））;
switch（compare（qa,qb））{
case1:
{
qd->coef=qa->coef;
qd->expn=qa->expn;
qa=qa->next;
break;}
case0:
{
qd->coef=qa->coef-qb->coef;
qd->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case-1:
{
qd->coef=-qb->coef;
qd->expn=qb->expn;
qb=qb->next;
break;}
}
if（qd->coef!
=0）
{
qd->next=hd->next;
hd->next=qd;
hd=qd;
}
elsefree（qd）;//当相加系数为0时，释放该结点
}
returnheadd;
}
…………………………………….main.cpp……………………………………………………..
#include
#include
#include"cal.h"
#definemaxlen10
#definelarge999
voidmain（）
{intm,n,a;
charflag;
Linklistpa=0,pb=0,pc;
printf（"欢迎使用多项式操作程序\n\n"）;
printf（"请输入a的项数:
"）;
scanf（"%d",&m）;
pa=CreateLinklist（pa,m）;//建立多项式a
printf（"请输入b的项数:
"）;
scanf（"%d",&n）;
pb=CreateLinklist（pb,n）;//建立多项式
//输出菜单
printf（"*******************************************************\n"）;
printf（"*多项式操作程序*\n"）;
printf（"**\n"）;
printf（"*A:
输出多项式aB:
输出多项式b*\n"）;
printf（"**\n"）;
printf（"*C:
输出a+bD:
输出a-b*\n"）;
printf（"**\n"）;
printf（"*E:
返回主菜单*\n"）;
printf（"**\n"）;
printf（"*******************************************************\n"）;
while（a）
{
printf（"\n请选择操作：
"）;
scanf（"%c",&flag）;
switch（flag）
{case'A':
case'a':
{
printf（"\n多项式a="）;
PrintLinklist（pa）;
break;}
case'B':
case'b':
{
printf（"\n多项式b="）;
PrintLinklist（pb）;
break;}
case'C':
case'c':
{
pc=AddLinklist（pa,pb）;
printf（"\na+b="）;
PrintLinklist（pc）;
break;
}
case'D':
case'd':
{
pc=SubLinklist（pa,pb）;
printf（"\na-b="）;
PrintLinklist（pc）;
break;
}
case'E':
case'e':
{
DestroyLinklist（pa）;
DestroyLinklist（pb）;
a=0;
break;}
default:
printf（"\n您的选择错误，请重新选择!
\n"）;
}
}
}
升级会员 