本文主要是介绍南邮数据结构实验1.3 一元多项式的相加和相乘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
内容和提示:
1.设计带表头结点的单链表表示的多项式类，在该类上定义和实现教材2.4节中程序2.7的多项式类上的各个运算。
2.在该类上增加成员函数void PolyMul(Polynominal & r)，并重载*运算符。
3.实现菜单驱动的main函数，测试多项式类上各个运算：输入多项式，显示多项式，多项式加法和乘法运算。
4.提示：注意本实习采用带表头的非循环链表存储多项式。除乘法运算外，请通过修改教材2.4节的程序实现各运算。多项式相乘的算法为：将乘数多项式的每一项与被乘数多项式的所有项分别相乘（即系数相乘，指数相加），得到中间多项式；调用函数PolyAdd将这些中间多项式依次加到结果多项式中。值得注意的是，在相成的过程中不能改变两个原始多项式的值。
#include<iostream.h>
class Term // 多项式的每一项类
{private:
int coef;
int exp;
Term *link;
public:
Term(int c, int e);
Term(int c, int e, Term *nxt);
Term * InsertAfter(int c, int e); friend ostream & operator<< (ostream &out, const Term &val); //输出每一项运算符重载friend class Polynominal;
};Term::Term(int c, int e) :coef(c), exp(e)
{
link = 0;
}
Term::Term(int c, int e, Term*nxt) : coef(c), exp(e)
{
link = nxt;
}
Term * Term::InsertAfter(int c, int e) //插入一项 p调用 调用结束 p指向插进来的项
{
link = new Term(c, e, link);
return link;
}ostream & operator<< (ostream &out,const Term &val) //输出每一项运算符重载
{
if (val.coef == 0) return out;
out << val.coef;
switch (val.exp)
{
case 0:break;
case 1:out << "X"; break;
default:out << "X^" << val.exp; break;
}
return out;
}//#include"term.h"
class Polynominal
{private:
Term * first;
public:
Polynominal();
~Polynominal();
void AddTerms(istream& in);
void Output(ostream& out)const;
void PolyAdd(Polynominal &r);
void PolyMul(Polynominal &r);
friend ostream& operator<<(ostream&, const Polynominal &);
friend istream& operator>>(istream&, Polynominal&);
friend Polynominal& operator +(Polynominal&, Polynominal&); //友员可以忽略
friend Polynominal& operator *(Polynominal&, Polynominal&);
};Polynominal::Polynominal() //带表头的 非循环链表
{
first=new Term(0,-1); //创建一个表头 由first指向
first->link = NULL;
}Polynominal::~Polynominal() //带表头结点单链表的析构
{
Term * p=first->link;
while (p)
{first->link=p->link;
delete p;
p=first->link;
}
}void Polynominal::AddTerms(istream& in) //多项式 输入各项
{
Term * q = first;// q指向单链接表的头结点
int c, e;
for (;;)
{
cout << "Input a term(coef,exp):\n" << endl;
cin >> c >> e;
if (e < 0) break;
q = q->InsertAfter(c, e);//调用term类里的 插入项函数 直到指数为负数
}
}void Polynominal::Output(ostream& out)const //多项式 输出各项
{
int a = 1; Term * p = first->link;//p指向单链接表的第一个元素cout << "the polynominal is :\n" <<endl;
do{
if (!a && (p->coef>0)) out << "+";//若a=0并且是正数 输出+
a = 0;
out << *p;
p = p->link;
} while (p);
cout << "\n" << endl;
}ostream& operator<<(ostream& out, const Polynominal& x)
{
x.Output(out); return out;
}istream& operator>>(istream& in, Polynominal& x)
{
x.AddTerms(in); return in;
}Polynominal & operator +(Polynominal& a, Polynominal& b)
{
a.PolyAdd(b); return a;
}Polynominal& operator *(Polynominal& a, Polynominal& b)
{
a.PolyMul(b); return a;
}void Polynominal::PolyAdd(Polynominal& r) //多项式相加
{
Term* q, *q1 = first, *p;//q1指向表头节点
p = r.first->link;//P 指向第一个元素
q = q1->link; //q指向第一个元素while(p) //带表头的链接表遍历 循环单链表可以最后指向头结点的 exp -1
{
while(p->exp < q->exp)
{
if(!q->link) break;
q1 = q; q = q->link; //q后移
} //经过此循环，q里次数比p里所有元素高的都在前面。
if (p->exp == q->exp)
{
q->coef = q->coef + p->coef; if(q->link)
{
q1 = q; q = q->link;
}
}
else if(p->exp >q->exp)
{q1 = q1->InsertAfter(p->coef, p->exp);//q的指数比p小 插入此时q的最前面
}else
{
q = q->InsertAfter(p->coef, p->exp); //插入之后，q指向新插入的结点
}
p = p->link;
}
}void Polynominal::PolyMul(Polynominal& r) //多项式乘法
{Term* q, *q1 = first, *p; //q1指向表头节点
p = r.first->link; //P 指向第一个元素
q = q1->link; //q指向第一个元素
Polynominal T;
Term *t=T.first; //临时指针;while(p)
{
while(q)
{
t=t->InsertAfter(q->coef*p->coef,q->exp+p->exp);
if(!q->link) break;
q1 = q; q = q->link; //q后移}
q1=first; q=q1->link; //q 归位
p=p->link;} Term *t1=T.first->link; //增加的代码Term *b_t=T.first->link; //对T的每一项进行排序，并且合并。 最终降幂排序。
t=b_t->link;
while(t1)
{
while(t)
{
if(t->exp==t1->exp)
{
t1->coef+=t->coef;
b_t->link=t->link;
t->coef=0;
t=b_t->link;
}
else
{
t=t->link;
b_t=b_t->link;
}
}
t1=t1->link;
b_t=t1;
t=t1->link;
if(!t) break;
}while(q)
{
q->coef=0;
q1 = q; q = q->link; //q后移
}
q1=first; q=first->link; //q 归位
PolyAdd(T);
}void Menu()
{cout<<"*****Input Polynominal p - Input 1 *****"<<endl<<endl;cout<<"*****Input Polynominal q - Input 2 *****"<<endl<<endl;cout<<"*****Add two Polynominals - Input 3 *****"<<endl<<endl;cout<<"*****Multiply two Polynominals - Input 4 *****"<<endl<<endl;cout<<"***** Exit -Input 0 *****"<<endl<<endl;cout<<"Input your choice:"<<endl;
}void Choice(int &choice)
{
Polynominal A, B;switch(choice)
{
case 1:cin>>A;cout<<"A---"<<A<<endl;Menu();break;
case 2:cin>>B;cout<<"B---"<<B<<endl;Menu();break;
case 3:cout<<"Please input two Polynominals: "<<endl;cin>>A;cin>>B;cout<<"Add:"<<A+B<<endl;Menu();break;
case 4:cout<<"Please input two Polynominals: "<<endl;cin>>A;cin>>B;cout<<"Multiply:"<<A*B<<endl;Menu();break;
case 0:cout<<"***** See U ! *****"<<endl; break;
}}//#include"polynominal.h"
//#include"a.h"void main()
{
Menu();
cout<<"降幂输入"<<endl;int choice;
do
{
cin>>choice;
Choice(choice);}while(choice);
}
这篇关于南邮数据结构实验1.3 一元多项式的相加和相乘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
