一元多项式的表示及相加

一元多项式的表示及相加
【实验目的】
掌握C语言中结构类型和指针类型,指针是逻辑关系的映像.
掌握线性链表的操作特点和动态产生、输出单链表的方法.
掌握单链表的插入、删除操作的特点和方法.
【实验内容】
试用单链表表示两个多项式：A＝4＋6x3＋5x8＋4x12,B＝5＋2x4＋6x7＋3x12.
设计此两个多项式的数据结构；
写出两个多项式相加的算法,要求除两个多项式所占空间外,不开辟新的存储空间.
【实验要求】
输出和多项式的各项系数、指数；从键盘输入x,能够计算出和多项式A＋B的值并输出.
【实验提示】
可用两个带头结点的单链表分别表示多项式A和B,链表结点的结构可包含：coef（系数）、exp（指数）、next（指向下一结点的指针）.结点可按指数升序排列.
可分两步完成：
先求出“和多项式”A＋B的表达式（如C＝9＋6x3＋2x4＋6x7＋5x8＋7x12）,存放到带头结点的链表C中；
再将x代入,从而求得和多项式的值.
求和多项式C的方法：
C中的结点无需另生成,可看成是将多项式B加到多项式A上,由此可得下列运算规则：设p和q分别指向A和B中某一结点,比较结点中的指数项,
若p->exp < q->exp,则p结点应是“和多项式”中的一项,令p指针向后移；
若p->exp > q->exp,则q结点应是“和多项式”中的一项,将q结点插入在p结点之前,且q指针在原来的链表上后移；
若p->exp＝q->exp,则将两个结点中的系数相加,当和不为零时修改p结点中的系数,释放q结点,p,q后移；反之,“和多项式”中没有此项,从A表中删去p结点,同时释放p和q结点,p,q后移.

＃include<stdio.h>
＃include<malloc.h>
＃include<stdlib.h>
#define LEN sizeof(node)
typedef struct polynode /*用单链表存储多项式的结点结构*/
{
int coef; /*多项式的系数*/
int exp; /*指数*/
struct polynode *next; /*next是struct polynode类型中的一个成员,它又指向
struct polynode类型的数据,以此建立链表*/
}node;/*若定为"node,*list;",意即node*与list同为结构指针类型*/
node * create(void) /*指针函数,返回指针类型；用尾插法建立一元多项式的链表的函数*/
{
node *h,*r,*s;
int c,e;
h=(node *)malloc(LEN); /*建立多项式的头结点,为头结点分配存储空间*/
r=h; /*r指针始终动态指向链表的当前表尾,以便于做尾插入,其初值指向头结点*/
printf("coef:");
scanf("%d",&c); /*输入系数*/
printf("exp: ");
scanf("%d",&e); /*输入指针*/
while(c!=0) /*输入系数为0时,表示多项式的输入结束*/
{
s=(node *)malloc(LEN); /*申请新结点*/
s->coef=c; /*申请新结点后赋值*/
s->exp=e; /*申请新结点后赋值*/
r->next=s; /*做尾插,插入新结点*/
r=s; /*r始终指向单链表的表尾*/
printf("coef:");
scanf("%d",&c);
printf("exp: ");
scanf("%d",&e);
}
r->next=NULL; /*将表的最后一个结点的next置NULL,以示表结束*/
return(h);
}
void polyadd(node *polya, node *polyb)/*一元多项式相加函数,用于将两个多项式相加,然后将和多项式存放在多项式polya中,并将多项式ployb删除*/
{
node *p,*q,*pre,*temp;
int sum;
p=polya->next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/
q=polyb->next;
pre=polya; /*位置指针,指向和多项式polya*/
while(p!=NULL&&q!=NULL) /*当两个多项式均未扫描结束时,执行以下操作*/
{
if(p->exp<q->exp) /*若p指向的多项式指数小于q指的指数*/
{
pre->next=p; /*将p结点加入到和多项式中*/
pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp) /*若指数相等,则相应的系数相加*/
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;p=p->next;
temp=q;q=q->next;free(temp);
}
else /*如果系数和为零,则删除结点p与q,并将指针指向下一个结点*/
{
temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
else /*若p指数大于q指数*/
{
pre->next=q; /*p结点不动,将q结点加入到和多项式中*/
pre=pre->next;
q=q->next;
}
}
if(p!=NULL) /*多项式A中还有剩余,则将剩余的结点加入到和多项式中*/
pre->next=p;
else /*否则将B的结点加入到和多项式中*/
pre->next=q;
}
void print(node * p) /*输出函数,打印出一元多项式*/
{
while(p->next!=NULL)
{
p=p->next;
printf(" %d*x^%d",p->coef,p->exp);
}
}
main() /*主函数*/
{
node * polya,* polyb;
printf("Welcome to use!\n");
printf("\nPlease input the ploya include coef && exp:\n");
polya=create(); /*调用建立链表函数,创建多项式A*/
print(polya);
printf("\nPlease input the ployb include coef && exp:\n");
polyb=create(); /*同理,创建B*/
print(polyb);
printf("\nSum of the poly is:\n");
polyadd(polya,polyb); /*调用一元多项式相加函数*/
print(polya); /*调用输出函数,打印结果*/
printf("\n");一元多项式相加程序（C语言）