一元稀疏多项式计算器实现完整实现版详细源码Word格式.docx
《一元稀疏多项式计算器实现完整实现版详细源码Word格式.docx》由会员分享,可在线阅读,更多相关《一元稀疏多项式计算器实现完整实现版详细源码Word格式.docx(23页珍藏版)》请在冰点文库上搜索。
返回L中第1个与e满足关系cmp()的元素的位序。
若这样的元素不存在,则返回值为0。
SetCurElem(&
p,e)
线性表L已存在,且非空。
用元数e更新p所指结点中元数的值。
GetCurElem(p)
返回p所指结点中数据元数的值。
InsFirst(&
L,h,s)
线性表L已存在,h结点在L中。
在L的s所指结点插入在h结点之后,L的长度加1。
DelFirst(&
L,h,q)
线性表L已存在且非空,q结点在L中且不是尾结点
删除链表L中的h结点之后的结点q,L的长度减1。
MakeNode(&
p,e)
创建了一个结点p,其data部分为e。
FreeNode(&
p)
结点p存在且非空。
释放结点p空间。
Append(LinkList&
L,Links)
s及s以后的结点链接到了原L之后,L的长度增加链上的结点数。
ListEmpty(L)
若线性链表L为空表,则返回TRUE,否则返回FALSE。
GetHead(L)
返回线性链表L中头结点的位置。
NextPos(L,p)
返回p所指结点的直接后继的位置,若没后继,则返回NULL。
intcmp(a,b)
存在两个元数。
比较a,b的数值,分别返回-1,0,1。
}ADTLinkList
2.一元多项式的抽象数据类型定义为:
ADTPolynomial{
D={ai|ai∈TermSet,i=1,2,...,m,m≥0
TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}
|ai-1,ai∈D,且ai-1中的指数值<
ai中的指数值,i=2,……,n}
CreatPolyn(&
P,m)
输入m项的系数和指数,建立一元多项式P。
DestroyPolyn(&
P)
一元多项式P已存在。
销毁一元多项式P。
AddPolyn(&
Pa,&
Pb)
一元多项式Pa和Pb已存在。
完成多项式相加运算,即:
Pa=Pa+Pb,并销毁一元多项式Pb。
SubtractPolyn(&
Pa,&
完成多项式相减运算,即:
Pa=Pa-Pb,并销毁一元多项式Pb。
MultiplyPolyn(&
完成多项式相乘运算,即:
Pa=Pa×
Pb,并销毁一元多项式Pb。
DerivPolyn(&
Pa)
一元多项式Pa已存在。
多项式求导。
CalPolyn(Pa,x)
求多项式在x处的值。
PrintPolyn(p,m)
一元多项式p已存在,且已知多项式项数。
打印输出一元多项式p的项数、系数和指数。
Expression(p,m)
打印输出一元多项式的类数学表达式。
SortPolyn(&
一元多项式p已存在。
对多项式p进行排序
}ADTPolynomial
3.本程序包含4个模块:
(1)主程序模块:
intmain(){
初始化;
接受命令;
while(命令!
=推出){
处理命令;
}
return0;
(2)一元多项式单元模块——实现一元多项式的抽象数据类型;
(3)链表单元模块——实现链表的抽象数据类型;
(4)结点结构单元模块——定义链表的节点结构。
各模块之间的调用关系如下:
主程序模块一元多项式单元模块链表单元模块
结点结构单元模块
三、详细设计
1.设计好的数据类型:
typedefstruct{//项的表示,多项式的项作为Linklist的数据元素
floatcoef;
//系数
intexpn;
//指数
}term,ElemType;
//两个类名:
term用于本ADT,ElemType为Linklist的数据对象名
typedefstructLNode{//结点类型
ElemTypedata;
structLNode*next;
}*Link,*Position;
typedefstruct{//链表类型
Linkhead,tail;
//分别指向线性链表中的头结点和最后一个结点
intlen;
//指示线性链表中数据个数
}LinkList;
typedefLinkListpolynomial;
//基于带头结点的线性链表定义的多项式数据类型
2.基于链表、结点的操作(部分伪码如下)
//分配由p指向值为e的结点,并返回OK,若分配失败,则返回ERROR。
StatusMakeNode(Link&
p,ElemTypee);
//释放p所指结点
voidFreeNode(Link&
p);
//构造一个空的线性链表L
StatusInitList(LinkList&
L);
{
L.head=L.tail=(Link)malloc(sizeof(LNode));
L.len=0;
L.head->
next=L.tail->
next=NULL;
returnOK;
//返回线性表L中头结点的位置。
PositionGetHead(LinkList&
//已知p指向线性链表L中的一个结点,返回p所指结点的直接后驱的位置
//若无后继,返回NULL
PositionNextpos(LinkList&
L,Linkp);
//已知p指向线性表L中的一个结点,返回p所指结点中数据元素的值。
ElemTypeGetCurElem(Linkp);
//已知p指向线性链表L中的一个结点,用e更新p所指结点中数据元素的值。
StatusSetCurElem(Link&
p,floate);
//已知h指向线性链表的某个结点,将q所指的结点插入在h之后。
StatusInsFirst(Linkh,Linkq);
s->
next=h->
next;
h->
next=s;
L.len++;
if(!
s->
next)
L.tail=s;
}
//已知h指向线性链表的头结点,删除线性链表第一个指结点并以q返回
StatusDelFirst(Linkh,Link&
q);
//若线性链表L为空,则返回TRUE,否则返回FALSE。
StatusListEmpty(LinkListL);
if(L.head==L.tail==NULL)
returnTRUE;
elsereturnFALSE;
//将指针s所指的一连串结点连接在线性表L的最后一个结点之后,并改变链表L的尾指针指向新的尾结点。
StatusAppend(polynomial&
L,Links);
i=0;
q=s;
while(s){//找到新的tail,计数s长度
p=s;
s=s->
i++;
}
L.tail->
next=q;
L.tail=p;
L.len+=i;
//判断已知链表中,是否存在相同的元素e,若存在返回TURE,且q指示L中第一个与e相同的结点元素;
//否则返回FALSE,并q指示L中第一个稍大于e的元素的直接前驱的位置
StatusLocateElem(LinkListL,ElemTypee,Position&
p=L.head;
while(p->
next){
s=p;
p=p->
m=p->
data;
if(cmp(e,m)==0){
q=p;
returnFALSE;
//整表删除
voidClearList(LinkList&
if(L.head!
=L.tail){
p=q=L.head->
while(p!
p=q->
free(q);
L.tail=L.head;
//依a的指数值<
(或=)(或>
)b的指数数值,分别返回-1,0,+1
intcmp(terma,termb);
if(a.expn<
b.expn)
return-1;
if(a.expn==b.expn)
return0;
if(a.expn>
return1;
3.基于多项式的操作(部分伪码如下)
//输入m项的系数和指数,建立表示一元多项式的有序链表P
voidCreatPolyn(polynomial&
p,intm);
InitList(p);
h=GetHead(p);
e.coef=0.0;
e.expn=-1;
SetCurElem(h,e);
for(inti=1;
i<
=m;
i++){
cout<
<
"
请输入第"
项的系数和指数(按指数降序):
;
cin>
>
e.coef>
e.expn;
endl;
LocateElem(p,e,q))//当前链表中不存在该指数项
if(MakeNode(s,e))InsFirst(p,q,s);
//生成节点并插入链表
elsereturn;
else{
q->
data.coef+=e.coef;
++c;
m=m-c;
//销毁一元多项式P
voidDestroyPolyn(polynomial&
while(p.head->
next!
=NULL){
k=p.head;
p.head=p.head->
free(k);
free(&
//打印输出一元多项式P
voidPrintPolyn(polynomialp);
ha=GetHead(p);
cout<
m<
'
'
for(inti=1;
i++){
qa=NextPos(p,ha);
e=GetCurElem(qa);
e.coef<
'
e.expn<
ha=qa;
//打印输出一元多项式的类数学表达式
voidExpression(polynomialp,intm);
//完成多项式的相加运算,即:
Pa=Pa+Pb,并销毁一元多项式Pb
voidAddPolyn(polynomial&
Pa,polynomial&
Pb);
{
ha=GetHead(Pa);
hb=GetHead(Pb);
//ha和hb分别指向pa和pb的头节点
qa=NextPos(Pa,ha);
qb=NextPos(Pb,hb);
while(qa&
&
qb){//qa,qb均非空
a=GetCurElem(qa);
b=GetCurElem(qb);
switch(cmp(a,b)){//a和b为两表比较元数
case-1:
//a的指数小于b的指数
DelFirst(Pb,hb,qb);
InsFirst(Pa,ha,qb);
qb=NextPos(Pb,hb);
ha=NextPos(Pa,ha);
break;
case0:
//a的指数等于b的指数
a.coef=a.coef+b.coef;
if(a.coef!
=0.0){//修改多项式Pa中当前结点的系数
SetCurElem(qa,a);
ha=qa;
}
else{//删除多项式Pa中当前结点
DelFirst(Pa,ha,qa);
FreeNode(qa);
FreeNode(qb);
qb=NextPos(Pb,hb);
qa=NextPos(Pa,ha);
case1:
//a的指数大于b的指数
ha=qa;
qa=NextPos(Pa,qa);
}
if(!
ListEmpty(Pb))Append(Pa,qb);
//链接Pb中剩余结点
FreeNode(hb);
//释放Pb的结点
//完成多项式的相减运算,即:
Pa=Pa-Pb,并销毁一元多项式Pb
voidSubtractPolyn(polynomial&
Pb,并销毁一元多项式Pb
voidMultiplyPolyn(polynomial&
InitList(Pc);
qa=GetHead(Pa);
qa=qa->
hc=GetHead(Pc);
while(qa){
a=GetCurElem(qa);
qb=GetHead(Pb);
qb=qb->
while(qb){
b=GetCurElem(qb);
c.coef=a.coef*b.coef;
c.expn=a.expn+b.expn;
MakeNode(qc,c);
InsFirst(Pc,hc,qc);
hc=NextPos(Pc,hc);
qc=NextPos(Pc,qc);
DestroyPolyn(Pb);
ClearList(Pa);
Pa.head=Pc.head;
Pa.tail=Pc.tail;
Pa.len=Pc.len;
//计算多项式在x处的值
doubleEvaluation(doublex,polynomialp);
//计算多项式P的导函数P'
voidDerivative(polynomial&
p);
InitList(Pb);
hb=GetHead(Pb);
b.coef=a.coef*a.expn;
b.expn=a.expn-1;
MakeNode(qb,b);
InsFirst(Pb,hb,qb);
hb=NextPos(Pb,hb);
qb=NextPos(Pb,qb);
qb=NULL;
Pa.head=Pb.head;
Pa.tail=Pb.tail;
Pa.len=Pb.len;
4.主函数和其他函数的伪码算法
intmain()
Initialization();
ReadCommand(cmd);
while(cmd!
='
q'
&
cmd!
Q'
)
{
Interpret(cmd);
display();
ReadCommand(cmd);
voidInitialization()
pre_cmd='
'
cmd='
InitList(La);
InitList(Lb);
voiddisplay()
system("
cls"
);
//清屏
在屏幕上方显示操作命令清单:
CreatePolynomial_a->
1CreatePolynomial_b->
2a+b->
a-b–>
a*b->
*Derivationofa->
dCalculateainx->
cQuit->
q
在屏幕下方显示操作命令提示框:
Enteraoperationcode(1,2,+,_,*,c,dORq):
"
voidReadCommand(char&
cmd)
//读入操作命令符
显示检入操作命令符的提示信息;
do
cin>
cmd;
}while(!
strchr(cmdsets,cmd));
voidInterpret(charcmd)
{//解释执行操作命令cmd
switch(cmd)
case'
1'
:
ClearList(La);
cout<
请输入第一个一元多项式的项数"
n;
cout<
endl;
CreatPolyn(La,n);
//输入多项式
SortPolyn(La);
break;
2'
ClearList(Lb);
endl<
请输入第二个一元多项式的项数"
m;
CreatPolyn(Lb,m);
SortPolyn(Lb);
+'
两多项式相加的结果:
AddPolyn(La,Lb);
PrintPolyn(La,La.len);
Expression(La,La.len);
getchar();
-'
两多项式相减的结果:
SubtractPolyn(La,Lb);
*'
两多项式相乘的结果:
MultiplyPolyn(La,Lb);
c'
C'
请输入x的值"
<
x;
多项式a在"
x<
处的值为"
CalPolyn(La,x);
d'
D'
DerivPolyn(La);
求导结果为"
default:
输入错误"
5.函数的调用关系图反映了演示程序的层次结构
四、调试分析
1.一开始写求导部分代码时没有考虑常数项求导变零的情况,结果输出后常数项以系数为0指数为-1的形式输出,不符合规范。
调试后加入if判断语句让常数项求导