课程设计报告
简单计数器
一、问题描述：
设计一元稀疏多项式简单计数器，能够完成多项式相加和相减的运算。
二、基本要求
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 = Pa＋Pb，利用两个多项式的结点构成"和多项式"，并返回和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<stdlib.h>
#include<stdio.h>
#include<ctype.h>
typedef 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; i<=m; ++i) /* 依次输入m个非零项*/
{ scanf("%f,%d",&x,&y);
P->coef=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大小关系是小于，c语言的冒泡排序算法
等于，大于分别返回-1，0，1;*/
{
if (a->expn < b->expn) return -1;
if (a->expn > b->expn) return 1;
return 0;
}
term *AddPolyn(term *Pa, term *Pb) /* 实现多项式加法运算：Pa = Pa＋Pb，利用两个多
项式的结点构成"和多项式"，并返回和Pa的头结点。*/
{ term *h, *qa = Pa, *qb = Pb, *p, *q;
float sum;
h = p = (term*)malloc(sizeof(term));
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论