简单计数器(C语言).doc

课程设计报告简单计数器一、问题描述： 设计一元稀疏多项式简单计数器，能够完成多项式相加和相减的运算。二、基本要求 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)+(7-5x8+11x9) 2 (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)四、算法思想 1：AddPolyn(Pa,Pb)函数是实现多项式的加法的主要函数，其算法思想是：把两个多项式结合成和多项式Pa，用p记录和多项式Pa中刚连接上的结点，用qa,qb分别从Pa,Pb的头结点开始记录Pa,Pb的各项，当qa与qb都不空时分别执行： (1)当qa的指数小于qb的指数时，连接p与qa，p和qa分别下; (2)当qa的指数等于qb的指数时，求系数和，若系数和为0，释放当前qa,qb,再将qa,qb下移，若系数和不为0，修改qa中的系数域，连接p与qa，p和qa分别下移,释放qb,qb下移; (3)当qa的指数大于qb的指数时,连接p与qb，p和qb分别下移； 重复执行(1)(2)(3)，直到qa或qb为空，最后连接Pa,Pb中剩余 结点，返回头结点。 2：ReducePolyn(Pa,Pb)函数是实现多项式的减法的主要函数，其算法思想是：把两个多项式结合成差多项式Pa，只需将Pb多项式中的各项系数变成相反数，再调用AddPolyn(Pa,Pb)函数即可。五、模块划分： 1 term *CreatPolyn(term *P,int m), 其功能是输入m项的系数和指数，建立表示一元多项式的有序链表P; 2 term *selsort(term *h) , 其功能是保证链表h指数有序(升序)，且相同指数结点只有一个; 3 void PrintfPoly(term *P), 其功能是输出多项式P; 4 int Compare(term *a, term *b) ，比较a,b的大小关系，a与b大小关系是小于，等于，大于分别返回-1，0，1; 5 term *AddPolyn(term *Pa, term *Pb) ， 其功能是多项式加法Pa = PaPb，利用两个多项式的结点构成和多项式，并返回和Pa的头结点。 6 term *AddResult(term *Pa, term *Pb), 其功能是输出Pa各项加Pb各项，并输出加后Pa的结果； 7 term *ReducePolyn(term *Pa, term *Pb) , 其功能是多项式减法：Pa = Pa-Pb，利用两个多项式的结点构成差多项式，并返回差Pa的头结点。 8 term *ReduceResult(term *Pa, term *Pb) ,其功能是 输出Pa各项加Pb各项，并输出减后Pa的结果； 9 void main() 主函数,对两个多项式进行加法和减法运算六、数据结构： 数据类型term的定义如下： typedef struct term float coef; /*系数*/ int expn; /*指数*/ struct term *next;/*下一个结点*/ term;七、源程序：#include#include#includetypedef struct term /*项的表示，多项式的项作为LinkList的数据元素 */ float coef; /*系数*/ int expn; /*指数*/ struct term *next;term;term *CreatPolyn(term *P,int m) /* 输入m项的系数和指数，建立一个表示一 元多项式的有序链表P，并返回头结点 */ term *h,*q; float x; int i,y; P=(term*)malloc(sizeof(term); h=P; if (m=0) return NULL; printf(nPut %d not zero items : ,m); printf(n); for (i=1; icoef=x;P-expn=y; if(P-coef) q = P; P = (term*)malloc(sizeof(term); /* P后移并分配新空间 ,q记录P的前结点 */ q-next=P; q-next = NULL; free(P); return h;term *selsort(term *h) /*保证链表h指数有序，且无同指数结点，返回头结点*/ term *g, *p, *q; float f; int i, fini = 1; if(!h) return NULL; for(g = h;g-next&fini;g = g-next) /*将表中指数排序，思路同冒泡排序*/ fini = 0; for(p = h,q = h-next;q;p = p-next,q = q-next) /* p始终指在q的前面 */ if (p-expn q-expn) /* 如果p大于q的指数就交换*/ f=p-coef;i=p-expn; p-coef=q-coef;p-expn = q-expn; q-coef = f;q-expn = i; fini = 1; for(g = h,p = g-next;p;) /*将指数相等的合并系数*/ if(g-expn=p-expn) g-coef += p-coef;g-next = p-next;q=p;p=p-next; /*只要p下移*/free(q); else if(g-next) g=g-next; /*p，g都下移*/p=p-next; return h;void PrintfPoly(term *P) /*输出代表多项式的链表P*/ term *q; q=P; if(!q) /* 0多项式 */ putchar(0); return; if(q-coef!=1) /* 第一项的系数不为1 */ printf(%f,q-coef); /*输出第一项的系数*/ if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(!q-expn) putchar(1); /* 系数为1，指数为0*/ else if(q-expn=1) putchar(X); else printf(X%d,q-expn); /*以上是针对第一项，因为第一项系数大于0不需要加号*/ q=q-next; while (q) /*从第二项开始输出，正项输出+ */ if(q-coef 0) putchar(+); if(q-coef!=1) printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); q=q-next; int Compare(term *a, term *b) /* 比较a,b的大小关系，a与b大小关系是小于， 等于，大于分别返回-1，0，1;*/ if (a-expn expn) return -1; if (a-expn b-expn) return 1; return 0; term *AddPolyn(term *Pa, term *Pb) /* 实现多项式加法运算：Pa = PaPb，利用两个多 项式的结点构成和多项式，并返回和Pa的头结点。*/ term *h, *qa = Pa, *qb = Pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term); p-next = NULL; while (qa & qb) /* Pa和Pb均非空*/ switch (Compare(qa,qb) case -1: /* 多项式PA中当前结点的指数值小*/ p-next = qa; p = qa; qa = qa-next; break; case 0: /* 两者的指数值相等*/ sum = qa-coef + qb-coef; if (sum != 0.0) /* 修改多项式PA中当前结点的系数值*/ p-next=qa; qa-coef=sum; p=qa; qa=qa-next; else /* 删除多项式PA中当前结点 */ q = qa; qa = qa-next; free(q); q = qb; qb = qb-next; free(q); break; case 1: /* 多项式PB中当前结点的指数值小*/ p-next = qb; p = qb; qb = qb-next; break; if (qa) p-next = qa; /* 链接Pa中剩余结点*/ else if(qb) p-next = qb; /* 链接Pb中剩余结点*/ q = h; h = h-next; free(q); return h;term *AddResult(term *Pa, term *Pb) /* 输出Pa各项加Pb各项，并输出加后Pa的结果*/ PrintfPoly(Pa); if(Pb & Pb-coef0) printf( + ); PrintfPoly(Pb); Pa = AddPolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; term *ReducePolyn(term *Pa, term *Pb) /* 算法2.23 多项式减法：Pa = Pa-Pb， 利用两个多项式的结点构成差多项式，并返回差Pa的头结点。*/ term *p = Pb; while(p) /*将Pb中的各项系数变成相反数*/ p-coef *= -1; p = p-next; return AddPolyn(Pa,Pb);term *ReduceResult(term *Pa, term *Pb) /* 输出Pa各项加Pb各项，并输出减后Pa的结果*/ PrintfPoly(Pa); printf( - ); putchar();PrintfPoly(Pb);putchar(); Pa = ReducePolyn(Pa,Pb); printf( = ); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; void main() /*主函数,对两个多项式进行加法和减法运算*/ int m,n; term *M,*N; puts(nPut 2 Polyn M,N item count); scanf(%d,%d,&m,&n); M = CreatPolyn(M,m); M = selsort(M); printf(nPolyn M:); PrintfPoly(M); N = CreatPolyn(N,n); N = selsort(N); printf(nPolyn N:); PrintfPoly(N); printf(nadded result:n); AddResult(M,N); /*相加的结果*/ printf(nM,N has changed repeate create M N :); /* M,N变了或消失了，从建*/ M = CreatPolyn(M,m); M = selsort(M); N = CreatPolyn(N,n); N = selsort(N); printf(nreduceded result:n); ReduceResult(M,N); /*相减的结果*/八、测试情况： 程序输出为： 2.000000x+5x8-3.1x11+7.000000-5x