验证中...
語言: C/C++
分類: 编程语言基础
最後更新於 2018-01-14 12:39
稀疏多项式.cpp
原始數據 複製代碼
#include <iostream>
using namespace std;
typedef struct LNode{
int expn; //指数
float coef; //系数
struct LNode *next;
}LNode, *Polynomial;
void CreatPolyn(Polynomial &P,int m)
{
//输入m项的系数和指数,建立表示一个多项式的有序链表P
LNode *q,*pre,*s;
int i;
P=new LNode;
P->next=NULL; //先建立一个带头结点的单链表
for(i=1;i<=m;i++) //依次输入m个非零项
{
s=new LNode; //生成新结点
cin>>s->coef>>s->expn; //输入元素值
if(s->coef != 0){
pre=P; //pre用于保存q的前驱,初值为头结点
q=P->next;
while(q && q->expn > s->expn) //通过比较指数找到第一个小于或等于输入项指数的项q
{
pre=q;
q=q->next;
}
if(q && q->expn == s->expn){
//如果输入元素和链表中已有的元素指数相等,则合并,否则,插入到它的前面
q->coef= q->coef + s->coef;
delete s;
}
else{
s->next=q;
pre->next=s;
}
}
}
} //CreatPolyn
void AddPolyn(Polynomial &Pa,Polynomial &Pb) {
//多项式加法:Pa=Pa+Pb,利用两个多项式的结点构成“和多项式”
LNode *r,*p1,*p2,*p3;
float sum;
p1=Pa->next;p2=Pb->next; //p1和p2初值分别指向Pa和Pb的第一个结点
p3=Pa; //p3指向和多项式的当前结点,初值为Pa
while(p1 && p2) //p1和p2均非空
{
if(p1->expn == p2->expn) //指数相等
{
sum=p1->coef+p2->coef; //sum保存两项的系数和
if(sum!=0) //系数和不为0
{
p1->coef=sum; //修改Pa当前结点p1的系数值为两项系数的和
p3->next=p1;p3=p1; //将修改后的Pa当前结点p1链在p3之后,p3指向p1
r=p2;p2=p2->next;delete r; //删除Pb当前结点r
p1=p1->next; //p1指向后一项
}
else //系数和为0
{
r=p1;p1=p1->next;delete r; //删除Pb当前结点p1
r=p2;p2=p2->next;delete r; //删除Pb当前结点p2
}
}
else if(p1->expn > p2->expn) //Pa指数大
{
p3->next=p1; //将p1链在p3之后
p3=p1; //p3指向p1
p1=p1->next; //p1指向后一项
}
else //Pb指数大
{
p3->next=p2; //将p2链在p3之后
p3=p2; //p3指向p2
p2=p2->next; //p2指向后一项
}
}
p3->next=p1?p1:p2; //插入非空多项式的剩余段
delete Pb; //释放Pb的头结点
} //AddPolyn
void MinusPolyn(Polynomial &Pa,Polynomial &Pb) {
//多项式加法:Pa=Pa+Pb,利用两个多项式的结点构成“和多项式”
LNode *r,*p1,*p2,*p3;
float sum;
p1=Pa->next;p2=Pb->next; //p1和p2初值分别指向Pa和Pb的第一个结点
p3=Pa; //p3指向和多项式的当前结点,初值为Pa
while(p1 && p2) //p1和p2均非空
{
if(p1->expn == p2->expn) //指数相等
{
sum=p1->coef - p2->coef; //sum保存两项的系数差
if(sum != 0) //系数和不为0
{
p1->coef=sum; //修改Pa当前结点p1的系数值为两项系数的差
p3->next=p1;p3=p1; //将修改后的Pa当前结点p1链在p3之后,p3指向p1
r=p2;p2=p2->next;delete r; //删除Pb当前结点r
p1=p1->next; //p1指向后一项
}
else //系数和为0
{
r=p1;p1=p1->next;delete r; //删除Pb当前结点p1
r=p2;p2=p2->next;delete r; //删除Pb当前结点p2
}
}
else if(p1->expn > p2->expn) //Pa指数大
{
p3->next=p1; //将p1链在p3之后
p3=p1; //p3指向p1
p1=p1->next; //p1指向后一项
}
else //Pb指数大
{
p2->coef=-p2->coef;
p3->next=p2; //将p2链在p3之后
p3=p2; //p3指向p2
p2=p2->next; //p2指向后一项
}
}
p3->next=p1?p1:p2; //插入非空多项式的剩余段
delete Pb; //释放Pb的头结点
}
int main()
{//将输入项s插入到q和其前驱结点pre之间
Polynomial Pa,Pb;
LNode *p;
int temp,i,flag;
//判断是相加还是相减
cout<<"加运算请输1,减运算请输0: ";
cin>>flag;
//创建多项式Pa
cout<<"请输入多项式Pa的项数:";
cin>>temp; //输入多项式Pa的个数
cout<<"请输入多项式Pa的系数和指数,中间用一个空格隔开,一个项一行:\n";
CreatPolyn(Pa,temp); //调用函数,输入Pa每一项的系数和指数
//创建多项式Pb
cout<<"请输入多项式Pb的项数:";
cin>>temp; //输入多项式Pa的个数
cout<<"请输入多项式Pb的系数和指数,中间用一个空格隔开,一个项一行:\n";
CreatPolyn(Pb,temp); //调用函数,输入Pa每一项的系数和指数
if(flag)
AddPolyn(Pa,Pb);
else
MinusPolyn(Pa,Pb);
cout<<"多项式Pa和Pb相加后的结果是:\n";
p=Pa->next;
if(p == NULL)
cout<<0;
i=0;
while(p) //输出相加后的结果,每一项以x^n表示
{
if(i && p->coef > 0)
cout<<"+";
if((p->coef == 1)&&p->expn != 0)
cout << "x^" << p->expn;
else if((p->coef == -1)&&p->expn != 0)
cout << "-x^" << p->expn;
else if(p->expn == 0)
cout<<p->coef;
else
cout<<p->coef<<"x^"<<p->expn;
p=p->next;
i++;
}
cout<<endl;
return 0;
}

評論列表( 0 )

你可以在登錄後,發表評論

11_float_left_people 11_float_left_close