一元稀疏多项式简单计数器试验报告

1、元稀疏多项式简单计数器题目：编制一个演示一元稀疏多项式简单计数器的程序班级：计算机科学与技术1301班 姓名：刘濛 学号：201321091026 完成日期：201549一、需求分析1.1本演示程序中，多项式是以带头结点的单链表存储的，在单链表中有两个数据域，分别存储多项式的一个节点的系数，指数；还有一个指针域，存储 指向下一个节点的指针。1.2演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示 信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数 据和运算结果显示在其后。1.3程序执行的命令包括：1) 构造多项式a;2)构造多项式b ； 3)输出多项式，并且多项

2、式的序列按指 数的降序排列；4)求a+b ； 5)求a-b ； 6)求a*b ； 7)求多项式a的导函数 a ;8)求多项式在x处的值。1.4测试数据(1) ( 2x+5xA8-3.1xA11 ) +( 7-5xA8+11xA9 ) =(-3.1xA11+11xA9+2x+7)(2) (6xA(-3)-x+4.4xA2-1.2xA9)-(-6xA(-3)+5.4xA2-xA2-xA2+7.8xA15)=(-7.8x A15-1.2xA9+12xA(-3)-x)(3) (1+x+xA2+xA3+xA4+xA5)+(-xA3-xA4)=(1+x+xA2+xA5)(4) (x+xA3)+(-x-xA

3、3)=0(5) (x+xA100)+(xA100+xA200)=(x+2xA100+xA200)(6) (x+xA2+xA3)+0=x+xA2+xA3(7) 互换上述测试数据中的前后两个多项式二、概要设计为实现上述程序的功能，应以带头结点的单链表表示多项式。为此，需要一个抽象数据类型：单链表。2.1单链表的抽象数据类型定义ADT Li nkList数据对象：D=ai|ai TermSet,i=1,2,;m,m 0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1=ai-1,ai D且ai-1中的指数值n ext=n ull;retur n ture; void Fr

4、eeNode(Li nkList &p) II释放p所指结点free(q1);q1=q2; q2=q2-n ext;3.2单链表的基本操作设置如下：void Insert(LinkList p,LinkList h)；/将节点p插入到多项式链表hLinkList CreateLinkList(LinkList head,int m);/建立一个头指针为head、项数为m的一元多项式，并返回该多项式的头结点；/若分配空间失败，则返回FALSEvoid DestroyLinkList(LinkList p);/销毁多项式pvoid PrintLinkList(LinkList P);/输出构造的一

5、元多项式PStatus compare(L in kList a,L in kList b)/节点进行比较：a的指数b的指数 return 1; a的指数=b的指 数 return 0;a的指数 next=NULL;for(i=0;icoef,&p-exp n);In sert(p,head);/调用Insert函数插入结点return head;/ CreateLi nkListStatus compare(L in kList a,L in kList b)if(a&b)if(!b|a-exp nb-exp n) retur n 1;else if(!a|a-exp nexp n) ret

6、ur n -1;else retur n 0;else if(!a&b) return -1;/a多项式已空，但b多项式非空else return 1;/b多项式已空，但a多项式非空/ comparefloat ValueLinkList(LinkList head,int x)/ 输入 x 值，计算并返回多项式的值for(p=head-n ext;p;p=p-n ext)t=1; for(i=p-expn;i!=0;)/ i 为指数的系数pow(x,i)if(icoef*t; retur n sum;/ ValueL in kListLinkList MultiplyLinkList(Lin

7、kList pa,LinkList pb)/ 求解并建立多项式 a*b，返回其 头指针Lin kList qa=pa-n ext;Lin kList qb=pb-n ext;hf=(LinkList)malloc(sizeof(struct LNode);/ 建立头结点hf-n ext=NULL;for(;qa;qa=qa-n ext) for(qb=pb-n ext;qb;qb=qb-n ext)pf=(LinkList)malloc(sizeof(struct LNode);pf-coef=qa-coef*qb-coef;pf-exp n=qa-exp n+qb-exp n;Insert(

8、pf,hf); /调用Insert函数以合并指数相同的项return hf;/ MultiplyL in kList3.3主函数和其他函数的伪码算法void main()/ 主函数Ini tiati on ();/多项式初始化PrintCommand(); 输出菜单while(1) /循环一直为真 知道选择j|J即退出命令时，程序退出 printf(n请选择操作：);sea nf(%c，& flag);In terpter(flag);/ 具体的操作命令 /mainvoid In itiati on()printf(请输入a的项数:);sea nf(%d,&m);pa=CreateLinkLi

9、st(pa,m); 建立多项式 a printf(请输入b的项数:);sea nf(%d,&n);pb=CreateLinkList(pb,n);/ 建立多项式 bprintf( 多项式已创建n);/ Ini tiati onvoid Prin tComma nd()/ 输出菜单显示键入命令的提示信息；Printf( A， B， C， D， E , F , G， H , I , J);/ Prin tComma ndvoid In terpter(char flag) / 具体的操作命令switch(flag) case A: case a: PrintLin kList(pa); break

10、;case B:case b: PrintLin kList(pb); break;caseC: casec: pc=Derivative(pa); PrintLin kList(pc);break;caseD: cased: Derivative(pb); PrintLin kList(pc); break;caseE: casee: ValueLi nkList(pa,x);break;caseF:casef: ValueL in kList(pb,x);break;caseG: caseg: AddL in kList(pa,pb);PrintLin kList(pc); break;

11、caseH: caseh: SubtractLinkList(pa,pb);PrintLinkList(pc); break; caseT:casei:pc=MultiplyL in kList(pa,pb);); PrintLin kList(pc);break;caseJ:casej: DestroyLinkList(pa); DestroyLinkList(pb);exit(O) ;default:printf(n您的选择错误，请重新选择！n); /In terpter3.4函数的调用关系图反映了演示程序的层次结构：Mai nIn itiationPrintcommandIn terpt

12、erCreateLinkList PrintLK Derivative ValueLK AddLK SubtractLK MultiplyLK DestroyLKTTTTPrintLKPrintLK PrintLK PrintLK exit(0)说明LK : LinkList即多项式节点函数说明：In itiatio n();/多项式初始化Prin tComma nd();/输出菜单In terpter();/具体的操作命令PrintLinkList();/打印多项式（降序输出）Derivative();/多项式求导ValueL in kList();/多项式求值AddL in kList()

13、;/两个多项式相加SubtractLi nkList();/两个多项式相减MultiplyL in kList();/两个多项式相乘DestroyL in kList();/销毁多项式compare();/两个节点比较CreateLi nkList();/创建多项式In sert();/将节点插入已知多项式中四、调试分析4.1刚开始的时候由于对多项式的减法考虑不周全， 代码很复杂，后来经过仔 细思考，减法时把每项的系数变成它的相反数， 然后调用加法的函数即可，但是 实现了减法之后要把系数恢复，不然会影响后面的运算。4.2求多项式在x处的值的函数在刚开始的时候出现过警告，虽然警告不会影响程序的运

14、行，但是运算的结果不精确。之前函数的类型是int,但是里面的多项式的系数是浮点型的，而 sum又是整型的，但是这样得不到小数点后面的数 值，导致结果不精确。后来经改进，把函数的类型及sum的类型均改为float型。五、用户使用手册5.1此程序的整体架构：主函数里有三个函数，Initialization（初始化）、PrintCommand（打印命令）、Interpret（解释并执行命令）。在Interpret函数中调用了其他的函数，以达到执行 命令的目的。5.2在输入命令时要注意在输入多项式的每一项的系数和指数必须有空格，否则可能会解释命令出错。在完成每一条的命令输入时要键入En ter.六、测

15、试结果名项式換作程序旅荊出孚项？陶出实顶式bD；输出琥勺异数 代心旳值计贰输出aHb退出程序盲谀择操作I遠E：代入m的值计算*宙输出I:荊出卄h钿琲仙b钿丰操佃c务项云詰的寻画数为I才T9X寫吃吐择操佃d齐项云旳寻画数为|肝-3州寫-恥曾？关命令）七、附录（源代码）：#i nclude#i nclude#in clude#defi neTRUE 1#defi neFALSE 0#defi neOK 1#defi neERROR 0#defi neINFEASIBLE -1#defi neOVERFLOW -2typedef int Status;typedef int ElemType;typ

16、edef struct LNode floatcoef;义项的系数ElemTypeexp n;数struct LNode *n ext;LNode,*Li nkList;/*全局节点初始化多项式节点为空*/static Lin kList pa=NULL;staticLi nkList pb=NULL;staticLi nkList pc=NULL;/*将节点p插入到多项式链表h*/void In sert(L in kList p,L in kList h) if(p-coef=0) free(p);else Lin kList q1,q2;q仁h;/定/定义项的指/指向下一个节点/系数为0

17、的话释放结点q2=h-n ext;while(q2&p-exp nexp n)/查找插入位置q1=q2;q2=q2-n ext;if(q2&p-exp n=q2-exp n)将指数相同相合并q2-coef+=p-coef;free(p);if(!q2-coef)系数为0的话释放结点q1- n ext=q2-n ext;free(q2);else/指数为新时将结点插入p-n ext=q2;q1- n ext=p;/创建一元多项式Lin kList CreateLi nkList(L in kList head,i nt m)/ 建立一个头指针为head、项数为m的一元多项式int i;Lin k

18、List p;p=head=(Li nkList)malloc(sizeof(struct LNode);head- next=NULL;for(i=0;icoef,&p-exp n);In sert(p,head);/调用Insert函数插入结点return head;void DestroyLi nkList(Li nkList p)/销毁多项式pLinkList q1,q2;q1=p-n ext;q2=q1- n ext;while(q1- n ext)free(ql);q1=q2;q2=q2-n ext;/输出构造的一元多项式Pvoid Prin tLi nkList(Li nkLis

19、t P)Lin kList q=P-n ext;int flag=1;/项数计数器if(!q) /若多项式为空，输出0putchar(O);prin tf(n);return;while(q)if(q-coef0&flag!=1) putchar(+); / 系数大于 0 且不是第一项if(q-coef!=1 &q-coef!=-1)/系数非1或-1的普通情况prin tf(%g,q-coef);if(q-exp n=1) putchar(X);else if(q-exp n) pri ntf(XA%d,q-exp n);elseif(q-coef=1)if(!q-exp n) putchar

20、(l);else if(q-exp n=1) putchar(X);else prin tf(XA%d,q-exp n);if(q-coef=-1)if(!q-exp n) pri ntf(-1);else if(q-expn=1) printf(-X);else prin tf(-XA%d,q-exp n);q=q-n ext;flag+;prin tf(n);/节点进行比较/a的指数b的指数return 1/a的指数=b的指数return 0/ a的指数exp nb-exp n) retur n 1;else if(!a|a-exp nexp n) retur n -1;else retu

21、rn 0;else if(!a&b) return -1;/a 多项式已空，但b多项式非空else return 1;/b多项式已空，但a多项式非空LinkList AddLinkList(LinkList pa,LinkList pb) 求解并建立多项式 a+b，返回其头 指针Lin kList qa=pa-n ext;Lin kList qb=pb-n ext;Lin kList headc,hc,qc;hc=(LinkList)malloc(sizeof(struct LNode);/ 建立头结点hc- next=NULL;headc=hc;while(qa|qb)qc=(Li nkLi

22、st)malloc(sizeof(struct LNode);switch(compare(qa,qb)case 1: qc-coef=qa-coef;qc-exp n=qa-exp n; qa=qa-n ext;break;case 0: qc-coef=qa-coef+qb-coef;qc-exp n=qa-exp n;qa=qa-n ext;qb=qb-n ext;break;case -1:qc-coef=qb-coef;qc-exp n=qb-exp n; qb=qb-n ext;break; if(qc-coef!=0)qc- n ext=hc- n ext;hc- n ext=q

23、c;hc=qc;else free(qc);/当相加系数为0时，释放该结点retur n headc;LinkList SubtractLinkList(LinkList pa,LinkList pb) 求解并建立多项式 a-b，返回其 头指针Lin kList h=pb;Lin kList p=pb-n ext;Lin kList pd;while(p) /将pb的系数取反p-coef*=-1;p=p-n ext;pd=AddLi nkList(pa,h);for(p=h-next;p;p=p-next)/ 恢复 pb 的系数p-coef*=-1;return pd;float ValueL

24、inkList(LinkList head,int x)/输入x值，计算并返回多项式的值Lin kList p;int i;int t;float sum=0;for(p=head-n ext;p;p=p-n ext) t=1;for(i=p-expn;i!=0;)/ i 为指数的系数 pow(x,i)if(icoef*t;return sum;/求解并建立导函数多项式，并返回其头指针对多项式进行求导 y=Lin kList Derivative(L in kList head)/求解并建立导函数多项式，并返回其头指针Lin kList q=head-n ext,p1,p2,hd;hd=p1=

25、(LinkList)malloc(sizeof(struct LNode);/ 建立头结点hd- next=NULL;while(q)if(q-exp n!=0)/该项不是常数项时p2=(Li nkList)malloc(sizeof(struct LNode);p2-coef=q-coef*q-exp n;p2-exp n=q-exp n-1;p2- next=p1- next;/连接结点p1- n ext=p2;P仁 p2;q=q-n ext;return hd;Lin kList MultiplyL in kList(Li nkList pa,Li nkList pb)/求解并建立多项式

26、a*b，返回其头指针LinkList hf,pf;Lin kList qa=pa-n ext;Lin kList qb=pb-n ext;hf=(LinkList)malloc(sizeof(struct LNode);/ 建立头结点hf-n ext=NULL;for(;qa;qa=qa-n ext)for(qb=pb-n ext;qb;qb=qb-n ext) pf=(LinkList)malloc(sizeof(struct LNode);pf-coef=qa-coef*qb-coef;pf-exp n=qa-exp n+qb-exp n;Insert(pf,hf);/调用Insert函数

27、以合并指数相同的项return hf;/多项式初始化void In itiati on()int m, n ;printf(请输入a的项数:);sea nf(%d,&m);pa=CreateLinkList(pa,m); 建立多项式 aprintf(请输入b的项数:);sea nf(%d,&n);pb=CreateLinkList(pb,n);/ 建立多项式 bprintf( 多项式已创建n);/输出菜单 void Prin tComma nd()prin tf(*n);prin tf(*n);printf(序*n);多项式:操作程printf(*n);printf(*A:输出多项式aB：输出

28、多项式b*n);printf(*n);printf(*C输出a的导数D:输出b的导数*n);printf(*n);printf(*E代入x的值计算a:代入x的值计算b*n);printf(*n)；printf(*G:输出a+bH:输出a-b*n);printf(*n);printf(*I:输出a*bJ:退出程Word资料printf(*n)；printf(printf(*n);*n);序*n);void In terpter(char flag) int x ;scan f(%c, &flag); switch(flag)case A:/具体的操作命令case a： printf(n 多项式 a=);Prin tLi nkList(pa);break;case B:case b:printf(n多项式 b=);Prin tLi nkList(pb); break;caseC:casec: pc=Derivative(pa);prin tf(nPr