华北水利水电大学数据结
构试验报告
------二元多项式相加
2013160班
/*二元多项式的相加*/
#include <stdio.h>
#include <stdlib.h>
struct node{
int coefficient;
int expoentx;
int exponety;
struct node *next;
};
typedef struct node *ptrtonode;
ptrtonode bulidnode( void )//建立多项式链表
{
int i, j;
ptrtonode head, pnew, p;
printf("请输入多项式含有的项数\n");
scanf("%d", &i);
getchar();
if( (head = (ptrtonode)malloc( sizeof( struct node ))) == NULL ) return NULL;
head->expoentx = 0;
head->exponety = 0;
head->next = NULL;
head->coefficient = i;//将多项式的项数存在首节点
p = head;
for( j = 0; j < i; j++ )
{
if( (pnew = (ptrtonode)malloc( sizeof( struct node ))) == NULL ) return NULL;
printf("请输入系数x和y的次幂中间用空格隔开\n");
scanf("%d%d%d", &pnew->coefficient, &pnew->expoentx, &pnew->exponety);
fflush(stdin);
p->next = pnew;
p = pnew;
p->next = NULL;
}
return head;
}
ptrtonode deletezero( ptrtonode c )//删除系数为0的项
{
ptrtonode p, tmpcell;
p = c;
while( p->next != NULL )
{
if( 0 == p->next->coefficient )
{
tmpcell = p->next;
p->next = tmpcell->next;
free(tmpcell);
c->coefficient--;
}
else
p = p->next;
}
return c;
}
ptrtonode add( ptrtonode poly1, ptrtonode poly2 )
{
ptrtonode p1, p2, head, pnew, p3;
int flag;
if( (head = (ptrtonode)malloc( sizeof( struct node ))) == NULL ) return NULL;
head->expoentx = 0;
head->exponety = 0;
head->coefficient = 0;
head->next = NULL;
p1 = poly1->next;
p2 = poly2->next;
p3 = head;
while( NULL != p1 )
{
flag = 1;
p2 = poly2->next;
while( NULL != p2 )
{
if( p2->expoentx == p1->expoentx && p2->exponety == p1->exponety )
{
if( (pnew = (ptrtonode)malloc( sizeof( struct node ))) == NULL )
return NULL;
pnew->coefficient = p1->coefficient + p2->coefficient;
pnew->expoentx = p1->expoentx;
pnew->exponety = p1->exponety;
p3->next = pnew;
pnew->next = NULL;
p3 = pnew;
head->coefficient++;//得到的多项式项数
flag = 0;
break;
}
p2 = p2->next;
}
if(flag)//p2中未找到和p1可以相加的
{
if( (pnew = (ptrtonode)malloc( sizeof( struct node ))) == NULL )
return NULL;
pnew->coefficient = p1->coefficient;
pnew->expoentx = p1->expoentx;
pnew->exponety = p1->exponety;
p3->next = pnew;
pnew->next = NULL;
p3 = pnew;
head->coefficient++;
}
p1 = p1->next;
}
p1 = poly1->next;
p2 = poly2->next;
while( NULL != p2 )
{
flag = 1;
p1 = poly1->next;
while( NULL != p1 )
{
if( p2->expoentx == p1->expoentx && p2->exponety == p1->exponety )
{
flag = 0;
break;
}
p1 = p1->next;
}
if(flag)//p2中未相加的项
{
if( (pnew = (ptrtonode)malloc( sizeof( struct node ))) == NULL )
return NULL;
pnew->coefficient = p2->coefficient;
pnew->expoentx = p2->expoentx;
pnew->exponety = p2->exponety;
p3->next = pnew;
pnew->next = NULL;
p3 = pnew;
head->coefficient++;
}
p2 = p2->next;
}
return deletezero( head );
}
void printandfree( ptrtonode c )//打印并且释放内存
{
ptrtonode p1, p2;
p1 = c->next;
free(c);
while( NULL != p1 )
{
p2 = p1;
printf("%dx^%dy^%d+", p1->coefficient, p1->expoentx, p1->exponety);
p1 = p1->next;
free(p2);
}
printf("\b \n");
}。