求解多项式
发布网友
发布时间：2022-05-31 21:46
共1个回答
热心网友
时间：2023-10-30 13:57
#include<iostream>
#define MaxExp 1000
#define Max 100
using namespace std;
typedef struct Node{
int coef; //系数
int exp; //指数
struct Node *link;//指向下一个节点的指针
}LinkList;
////////////////////////////////////////////////////////
//建立循环链表
void CreateLinkList(LinkList *&L,int Coef[],int Exp[],int n)
{
L=(LinkList *)malloc(sizeof(LinkList));//
L->link=L;
LinkList *p,*s;
p=L; int i; //L指向头结点
for(i=0;i<n;i++){
s=(LinkList*)malloc(sizeof(LinkList)); //创建新结点
s->coef=Coef[i];s->exp=Exp[i];
s->link=L;
p->link=s;
p=s;
}
}
////////////////////////////////////////////////////////////
/*返回X的值*/
int Calc(LinkList *L)
{
LinkList *p;
p=L->link;
int q=0;
while(p!=L)
{
if(p->exp==1){q+=p->coef;}//查找指数为1的项，并返回系数的和
p=p->link;
}
return q;
}
//////////////////////////////////////////////////////////
/*多项式相乘的算法*/
LinkList* Add(LinkList *L1,LinkList *L2)
{/*两多项式相加*/
LinkList *p,*q,*r,*L3,*s;
L3=(LinkList *)malloc(sizeof(LinkList));//创建新链表的头结点
L3->link=L3;
p=L1->link;q=L2->link;r=L3->link;
int sum;
while(p!=L1&&q!=L2)
{
if(p->exp==q->exp)
{ //若指数相等，系数相加，链入链表
sum=p->coef+q->coef;
if(sum!=0)
{s=(LinkList*)malloc(sizeof(LinkList));
s->coef=sum;
s->exp=p->exp;
r->link=s;
r=s;
}
p=p->link;
q=q->link;
}
else
{//若指数不等，取指数较小的一项链入链表
if(p->exp>q->exp)
{s=(LinkList*)malloc(sizeof(LinkList));
s->coef=q->coef;
s->exp=q->exp;
r->link=s;
r=s;
q=q->link;
}
else
{s=(LinkList*)malloc(sizeof(LinkList));
s->coef=p->coef;
s->exp=p->exp;
r->link=s;
r=s;
p=p->link;
}
}
}
while(p!=L1)
{ //链入表1的剩余部分
s=(LinkList*)malloc(sizeof(LinkList));
s->coef=p->coef;
s->exp=p->exp;
r->link=s;
r=s;
p=p->link;
}
while(q!=L2)
{ //链入表2的剩余部分
s=(LinkList*)malloc(sizeof(LinkList));
s->coef=q->coef;
s->exp=q->exp;
r->link=s;
r=s;
q=q->link;
}
r->link=L3;//构成循环链表
return L3;
}
LinkList* Alone(const LinkList *L,int a,int b)
{// 用一个多项式的其中一项乘以另一个多项式，返回新多项式的表头指针
//a为该项的系数，b为该项的指数
LinkList *p,*r,*q;
LinkList *L1;
L1=(LinkList*)malloc(sizeof(LinkList));//创建新链表，使原多项式不改变
L1->link=L1;
p=L->link;
r=L1->link;
while(p!=L)
{ //将改变后的各项系数及指数存入新链表中
q=(LinkList*)malloc(sizeof(LinkList));
q->exp=p->exp+b;
q->coef=p->coef*a;
q->link=L1;
r->link=q;
r=q;
p=p->link;
}
return L1;
}
LinkList* Mulpty(LinkList *a,LinkList *b)
{//多项式相乘，利用相加运算，分解多项式
LinkList *p,*q;
p=a->link;
q=b->link;
LinkList *newl;
newl=(LinkList*)malloc(sizeof(LinkList));
newl->link=newl;
while(p!=a)
{
newl=Add(newl,Alone(b,p->coef,p->exp));
p=p->link;
}
return newl;
}
//////////////////////////////////////////////////////////////////////
void output(LinkList *a)
{ //输出多项式的信息（合并同类项）
int A[MaxExp]={0};
LinkList *p=a->link;
int t=0,i;
while(p!=a) //合并同类项按指数大小从小到大依次输出
{
if(p->exp>t)t=p->exp;
A[p->exp]+=p->coef;p=p->link;
}
cout<<"各项信息："<<endl;
for(i=0;i<=MaxExp;i++)
{
if(A[i]!=0)cout<<'('<<A[i]<<','<<i<<')';
}
cout<<endl;
}
///////////////////////////////////////////////////////////////////////
int main()
{
LinkList *a;
LinkList *b;
int CoefA[Max],ExpA[Max];
int CoefB[Max],ExpB[Max];
int na,nb,i;
cout<<"请输入多项式A的项数："<<endl;
cin>>na;
cout<<"输入各项的系数及指数："<<endl;
for(i=0;i<na;i++)
cin>>CoefA[i]>>ExpA[i];
CreateLinkList(a,CoefA,ExpA,na);
cout<<"请输入多项式B的项数："<<endl;
cin>>nb;
cout<<"输入各项的系数及指数："<<endl;
for(i=0;i<nb;i++)
cin>>CoefB[i]>>ExpB[i];
CreateLinkList(b,CoefB,ExpB,nb);
LinkList *c;
cout<<"A中X的值:"<<Calc(a)<<endl;
cout<<"B中X的值:"<<Calc(b)<<endl;
cout<<"多项式A+B:"<<endl;
output(Add(a,b));
c=Mulpty(a,b);
cout<<"***********************************"<<endl;
cout<<"多项式A*B:"<<endl;
output(c);
cout<<"************************************"<<endl;
cout<<"多项式A:"<<endl; //输出原来的多项式，并未改变
output(a);
cout<<"多项式B:"<<endl;
output(b);
system("pause");
return 0;
}
五、输入输出示例
/*
输入示例：
4
1 0
2 3
5 4
6 2
5
1 1
2 2
2 3
4 6
6 5
输出示例：
A中X的值:0
B中X的值:1
多项式A+B:
各项信息：
(1,0)(1,1)(8,2)(4,3)(5,4)(6,5)(4,6)
***********************************
多项式A*B:
各项信息：
(1,1)(2,2)(8,3)(14,4)(27,5)(18,6)(46,7)(36,8)(38,9)(20,10)
***********************************
多项式A:
各项信息：
(1,0)(6,2)(2,3)(5,4)
多项式B:
各项信息：
(1,1)(2,2)(2,3)(6,5)(4,6)
请按任意键继续. . .
打字不易，如满意，望采纳。
