#include"stdio.h"
#include"malloc.h"
#include"conio.h"
#include"stdlib.h"
#include"process.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
#define MAX 20 //多项式最多项数
typedef struct //定义存放多项式的数组类型
{
float coef; //系数
int expn; //指数
}Polyn[MAX];
typedef struct LNode //定义单链表结点类型
{
float coef; //系数
int expn; //指数
struct LNode *next;
}Polynomial;
void PrintPolyn(Polynomial *P) //打印输出一元多项式P
{
Polynomial *L;
L=P->next;
while(L!=NULL)
{
printf("%gx^%d ",L->coef,L->expn);
L=L->next;
}
printf("\n");
}
void CreatPolyn(Polynomial *&P,Polyn a,int n)
//输入n项的系数和指数,建立表示一元多项式的有序链表P
{
Polynomial *e,*L;int i;
P=(Polynomial *)malloc(sizeof(Polynomial)); //创建头结点
P->next=NULL;
L=P; //L始终指向尾结点,开始时指向头结点
for(i=0;i<n;i++)
{
e=(Polynomial *)malloc(sizeof(Polynomial)); //创建新结点
e->coef=a[i].coef;
e->expn=a[i].expn;
L->next=e; //将*e插入*r之后
L=e;
}
L->next=NULL; //尾结点next域置为NULL
}
void Sort(Polynomial *&head) //按指数递减排序
{
Polynomial *p,*q,*r;
p=head->next;
if(p!=NULL) //若原单链表中有一个或以上的数据结点
{
r=p->next; //r保存*p结点后继结点的指针
p->next=NULL; //构造只含一个数据结点的有序表
p=r;
while(p!=NULL)
{
r=p->next; //r保存*p结点后继结点的指针
q=head;
while(q->next!=NULL&&q->next->expn>p->expn) q=q->next;
//在有序表中找插入*p的前驱结点*q
p->next=q->next; //将*p插入到*q之后
q->next=p;
p=r;
}
}
}
void AddPolyn(Polynomial *pa,Polynomial *pb,Polynomial *&pc)
//完成多项式相加运算
{
float c;
Polynomial *ha=pa->next,*hb=pb->next,*s,*hc;
pc=(Polynomial *)malloc(sizeof(Polynomial)); //创建头结点
hc=pc;
while(ha!=NULL&&hb!=NULL) //当链表ha,hb不为空时
{
if(ha->expn>hb->expn) //当链表ha的指数大于hb的指数时
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制头结点
s->expn=ha->expn;s->coef=ha->coef; //链表ha的系数和指数赋给s
hc->next=s;hc=s;
ha=ha->next; //把链表ha指向的下一个元素赋给ha
}
else if(ha->expn<hb->expn) //当链表ha的指数小于hb的指数时
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制头结点
s->expn=hb->expn;s->coef=hb->coef; //链表hb的系数和指数赋给s
hc->next=s;hc=s;
hb=hb->next; //把链表hb指向的下一个元素赋给hb
}
else //当链表ha的指数等于hb的指数时
{
c=ha->coef+hb->coef; //系数相加
if(c!=NULL) //系数之和不为0时创建新结点
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制结点
s->expn=ha->expn;s->coef=c;
hc->next=s;hc=s;
}
ha=ha->next; //把链表ha指向的下一个元素赋给ha
hb=hb->next; //把链表hb指向的下一个元素赋给hb
}
}
if(hb!=NULL) ha=hb; //复制余下的结点
while(ha!=NULL)
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制结点
s->expn=ha->expn;s->coef=ha->coef;
hc->next=s;hc=s;
ha=ha->next; //把链表ha指向的下一个元素赋给ha
}
hc->next=NULL;
}
void SubtractPolyn(Polynomial *pa,Polynomial *pb,Polynomial *&pc)
//完成多项式相减运算
{
float c;
Polynomial *ha=pa->next,*hb=pb->next,*s,*hc;
pc=(Polynomial *)malloc(sizeof(Polynomial)); //创建头结点
hc=pc;
while(ha!=NULL&&hb!=NULL) //当链表ha,hb不为空时
{
if(ha->expn>hb->expn) //当链表ha的指数大于hb的指数时
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制头结点
s->expn=ha->expn;s->coef=ha->coef; //链表ha的系数和指数赋给s
hc->next=s;hc=s;
ha=ha->next; //把链表ha指向的下一个元素赋给ha
}
else if(ha->expn<hb->expn) //当链表ha的指数小于hb的指数时
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制头结点
s->expn=hb->expn;s->coef=-(hb->coef); //链表hb的系数和指数赋给s
hc->next=s;hc=s;
hb=hb->next; //把链表hb指向的下一个元素赋给hb
}
else //当链表ha的指数等于hb的指数时
{
c=ha->coef-hb->coef; //系数相减
if(c!=NULL) //系数之差不为0时创建新结点
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制结点
s->expn=ha->expn;s->coef=c;
hc->next=s;hc=s;
}
ha=ha->next; //把链表ha指向的下一个元素赋给ha
hb=hb->next; //把链表hb指向的下一个元素赋给hb
}
}
if(hb!=NULL) ha=hb; //复制余下的结点
while(ha!=NULL)
{
s=(Polynomial *)malloc(sizeof(Polynomial)); //复制结点
s->expn=ha->expn;s->coef=-ha->coef;
hc->next=s;hc=s;
ha=ha->next; //把链表ha指向的下一个元素赋给ha
}
hc->next=NULL;
}
Print() //屏幕输出
{
int i;
printf("\n\n --------------------多项式运算器--------------------\n\n");
printf(" 1.多项式加法 2.多项式减法\n");
printf(" 3.退出 \n\n");
printf(" ----------------------------------------------------\n\n");
printf("请选择你要进行的操作:");
scanf("%d",&i);
return i;
}
void main()
{
int i,j,n=0,m=0;
Polynomial *ha,*hb,*hc,*hd;
Polyn a,b;
printf("\n\n --------------------欢迎使用多项式运算器--------------------\n\n");
printf(" 请先依次输入多项式A、B的系数和指数,然后选择多项式的运算\n\n");
printf(" ------------------------------------------------------------\n\n");
printf("请输入多项式A的系数和指数,按ESC键结束:\n");
for(i=0;i<=MAX;i++) //输入多项式A的系数和指数
{
scanf("%g,%d",&a[i].coef,&a[i].expn);
n++;
if(getch()==0x1b) goto flag1; //当按ESC时跳到flag1
}
flag1:printf("请输入多项式B的系数和指数,按ESC键结束:\n");
for(j=0;j<=MAX;j++) //输入多项式B的系数和指数
{
scanf("%g,%d",&b[j].coef,&b[j].expn);
m++;
if(getch()==0x1b) goto flag2; //当按ESC时跳到flag2
}
flag2:CreatPolyn(ha,a,n); //建立表示一元多项式的有序链表ha
CreatPolyn(hb,b,m); //建立表示一元多项式的有序链表hb
system("cls.exe"); //清屏
printf("多项式A的项数:%d",n);printf(" 多项式A:");PrintPolyn(ha);
printf("多项式B的项数:%d",m);printf(" 多项式B:");PrintPolyn(hb);
printf("\n");
Sort(ha); //按指数递减排序ha
Sort(hb); //按指数递减排序hb
printf("有序多项式A:");PrintPolyn(ha);
printf("有序多项式B:");PrintPolyn(hb);
printf("\n");
AddPolyn(ha,hb,hc); //完成多项式相加运算
SubtractPolyn(ha,hb,hd); //完成多项式相减运算
flag:switch(Print())
{
case 1:PrintPolyn(hc);goto flag;break;
case 2:PrintPolyn(hd);goto flag;break;
case 3:break;
default:printf("操作错误!请重新选择!\n");goto flag;
}
}