数据结构课设多项式相乘（C版本）

/*
//   多项式从文件输入,格:3X2 代表系数为3,指数为2,即3乘X的平方
//    读取的时候,当读到0X0时停止读取
//
//    此程序可以自动合并同类项，自动将多项式按升幂排列
//    数据存在X.dat中
//                                                                           */
#include<stdlib.h>
#include<stdio.h>
struct node
{
int x;//指数
float a;//系数
struct node  *next;
} ;
struct node *a,*b,*c;//用全局变量来保存数据，方便，但程序复用性差。具体解释看主程序

void  mutl(struct node *y)//b多项式的一项与a多项式的所有项相乘结果存放在c中
{              //但b的项数必须比a的项数多
struct node *temp,*temp1;
temp=a;
temp1=c;
while(temp1!=NULL)
{
temp1->a=y->a*temp->a;
temp1->x=y->x+temp->x;
temp1=temp1->next;
temp=temp->next;
}

}
void sum(struct node *d,struct node *e)//两个多项式相加
{
struct node *temp,*temp1,*temp2;
temp=d;
temp1=e;
if(temp->a==0)//如果第一次相加
{
d->a=temp1->a;
d->x=temp1->x;
temp1=temp1->next;
while(temp1!=NULL)
{
temp->next=(struct node *)malloc(sizeof(struct node));
temp->next->a=temp1->a;
temp->next->x=temp1->x;
temp=temp->next;
temp1=temp1->next;
}
temp->next=NULL;
}
else
{
while(temp!=NULL&&temp1!=NULL)
{
if (temp->x==d->x&&d->x>temp1->x)//当temp指向d的首项时
{     //当d的首项系数大于c的首项系数,需要将c的
                //首项插入d的首项前
temp2=(struct node *)malloc(sizeof(struct node));
temp2->a=temp->a;
temp2->x=temp->x;  
d=temp2;
temp2->next=temp;
temp1=temp1->next;
continue;

}
if (temp->next==NULL)//当temp指向d的末尾时,需要把c剩下的链表接到d上
{
if (temp->x==temp1->x)
{
temp->a=temp1->a+temp->a;
temp1=temp1->next;
}
else
{
while(temp1!=NULL)
{
temp2=(struct node *)malloc(sizeof(struct node));
temp->next=temp2;
temp2->a=temp1->a;
temp2->x=temp1->x;
temp1=temp1->next;
temp=temp->next;
temp->next=NULL;
}
}
continue;
}
if (temp->x==temp1->x)//如果temp和temp1的系数相同时,直接相加
{
//temp->x=temp1->x+temp->x;
temp->a=temp1->a+temp->a;
//temp=temp->next;
temp1=temp1->next;
continue;
}

if (temp1->x>temp->x)//当temp指向d的中间项
{
if (temp1->x<temp->next->x)//如果temp1的系数在temp的两项中间时
{
temp2=(struct node *)malloc(sizeof(struct node));
temp2->a=temp1->a;
temp2->x=temp1->x;
temp2->next=temp->next;
temp->next=temp2;
temp1=temp1->next;

}
else//出现temp1小于temp的情况在第一各if中已经解决
{
temp=temp->next;
}
}

}
}
temp=NULL;
}
void init()//初始化各链表,从文件读取数据
{                                                      
struct node *temp,*temp1;
int x;
float t;
FILE *fp;
fp=fopen("x.dat","r");
fscanf(fp,"%fx%d",&t,&x);//读取a
if (t==0)
{
printf("有一个多项式为0。错误!");
exit(1);
}
temp=(struct node *)malloc(sizeof(struct node));
a=temp;
temp->a=t;
temp->x=x;
//temp=temp->next;
fscanf(fp,"%fx%d",&t,&x);
while(t!=0)
{
temp->next=(struct node *)malloc(sizeof(struct node));
temp=temp->next;
temp->a=t;
temp->x=x;
//temp=temp->next;
fscanf(fp,"%fx%d",&t,&x);
}
temp->next=NULL;
//读取b,c与b同值
fscanf(fp,"%fx%d",&t,&x);
if (t==0)
{
printf("有一个多项式为0。错误!");
exit(1);
}
temp=(struct node *)malloc(sizeof(struct node));
temp1=(struct node *)malloc(sizeof(struct node));
b=temp;
c=temp1;
temp->a=t;
temp->x=x;
temp1->a=t;
temp1->x=x;
fscanf(fp,"%fx%d",&t,&x);
while(t!=0)
{
temp->next=(struct node *)malloc(sizeof(struct node));
temp=temp->next;
temp->a=t;
temp->x=x;
temp1->next=(struct node *)malloc(sizeof(struct node));
temp1=temp1->next;
temp1->a=t;
temp1->x=x;
fscanf(fp,"%fx%d",&t,&x);
}
temp->next=NULL;
temp1->next=NULL;
}
struct node *sort(struct node *ab)//对数据进行排序,并合并同类项
{ //使数据按从大到小，并没有可再合并的同类项

struct node *temp,*temp1,*temp2;//temp2指向temp的前一个节点
int t=1,i=0;//t存放输入时的多项式个数
temp=ab->next;
temp2=ab;
temp1=ab;
if(temp==NULL)//判断是否为只有一项的式子
{
return(ab);
}
while(temp!=NULL)
{
temp1=ab;
t++;
i=0;
while(temp!=temp1||temp==NULL)
{
if (temp1->x==temp->x)//相等,合并同类项
{
temp1->a=temp1->a+temp->a;
temp=temp->next;

i=1;
/*if (temp==NULL)
{
break;
}*/
free(temp2->next);
temp2->next=temp;
//continue;
break;
}
if(temp1==ab)//和第一项比较,temp指向第二项
{
if(temp->x<temp1->x)//如果第二项的系数小于等于第一项的系数
{


temp2->next=temp->next;
temp->next=temp1;
temp1=temp;
temp=temp2->next;
ab=temp1;
i=1;

if (temp==NULL)
{
break;
}
//continue;
break;

}
/*else
{
//i=0;//temp1=temp1->next;
continue;

}*/
}
if (temp->x<temp1->next->x)
{
temp2->next=temp->next;
temp->next=temp1->next;
temp1->next=temp;
temp=temp2->next;

i=1;
if (temp==NULL)
{
break;
}
//continue;
break;
}
// else
// {
// temp1=temp1->next;
// }
temp1=temp1->next;
}
if(!i)
{
temp=temp->next;
temp2=temp2->next;
}

}
return(ab);
}
int count(struct node *q)//计算多项式的个数，并显示
{
int t=0;
struct node *temp;
temp=q;
while(temp!=NULL)
{
printf("%.fX^%d ",temp->a,temp->x);
t++;
temp=temp->next;
}
printf("\n");
return(t);
}
void daoshu(struct node *a)//求导数，并显示
{
struct node *t,*temp1,*temp2;
temp1=a;
temp2=(struct node*)malloc(sizeof(struct node));
t=temp2;
if(temp1->x==0)
{
temp1=temp1->next;
}
while(temp1!=NULL)
{
temp2->a=temp1->x*temp1->a;
temp2->x=temp1->x-1;
temp1=temp1->next;
temp2->next=(struct node*)malloc(sizeof(struct node));
printf("%.fX^%d ",temp2->a,temp2->x);
temp2=temp2->next;
}
temp2->next=NULL;
printf("\n");
//return t;
}
void main()
{
struct node *t,*d,*e,r={0,0,NULL},f={0,0,NULL};//t临时存放数据,d存放结果
int anum,bnum;//用来存放a,b的项数
d=&r;//d的初值为0
e=&f;
init();//初始化a,b,c，c的初值与a相同
printf("\n此程序可以完成多项式的乘法，加法，并可以实现多项式的自动合并，并按升幂排列。\n");
printf("\n原多项式1为:");
count(a);
printf("\n原多项式2为:");
count(b);
a=sort(a);//整理a,
b=sort(b);//整理b,
c=sort(c);
printf("\n整理后的多项式1:");
anum=count(a);
printf("\n导数1是:");
daoshu(a);
printf("\n");
printf("整理后的多项式2:");
bnum=count(b);
printf("\n导数2是:");
daoshu(b);
sum(e,a);
sum(e,b);
printf("\n\n和是:");
count(e);
if (anum<bnum)
{
t=a;
a=b;
b=t;
}
while(b!=NULL)//用b的每一项与a相乘,直到乘完
{
mutl(b);//b的第一项与a相乘,并把结果保存在c中
sum(d,c);//将相乘的结果加到d中
b=b->next;
}
printf("\n\n");
printf("积是:");
count(d);

}
输出结果：
1。X.dat的数据如下：
4x7 5x5 6x8 9x1 7x0 4x11 2x3 4x7 0x0
7x9 9x10 2x3 3x4 4x5 5x6 9x8 7x6 6x0 3x3 0x0

2。测试数据如下：

此程序可以完成多项式的乘法，加法，并可以实现多项式的自动合并，并按升幂排列。

原多项式为:4X^7 5X^5 6X^8 9X^1 7X^0 4X^11 2X^3 4X^7

整理后的多项式1:7X^0 9X^1 2X^3 5X^5 8X^7 6X^8 4X^11

导数是:9X^0 6X^2 25X^4 56X^6 48X^7 44X^10

原多项式为:7X^9 9X^10 2X^3 3X^4 4X^5 5X^6 9X^8 7X^6 6X^0 3X^3

整理后的多项式2:6X^0 5X^3 3X^4 4X^5 12X^6 9X^8 7X^9 9X^10

导数是:15X^2 12X^3 20X^4 72X^5 72X^7 63X^8 90X^9

和是:13X^0 9X^1 7X^3 3X^4 9X^5 12X^6 8X^7 15X^8 7X^9 9X^10 4X^11

积是:42X^0 54X^1 47X^3 66X^4 85X^5 130X^6 162X^7 132X^8 169X^9 186X^10
237X^11 64X^12 183X^13 127X^14 129X^15 126X^16 162X^17 54X^18 36X^19
28X^20 36X^21

如果各位有自己的见解，请指教
[ 2001-9-10 17:19:06 yz95 修改 ]