本文主要是介绍南邮数据结构实验1 一元多项式的相加和相乘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
内容和提示:
1.设计带表头结点的单链表表示的多项式类，在该类上定义和实现教材2.4节中程序2.7的多项式类上的各个运算。
2.在该类上增加成员函数void PolyMul(Polynominal & r)，并重载*运算符。
3.实现菜单驱动的main函数，测试多项式类上各个运算：输入多项式，显示多项式，多项式加法和乘法运算。
4.提示：注意本实习采用带表头的非循环链表存储多项式。除乘法运算外，请通过修改教材2.4节的程序实现各运算。多项式相乘的算法为：将乘数多项式的每一项与被乘数多项式的所有项分别相乘（即系数相乘，指数相加），得到中间多项式；调用函数PolyAdd将这些中间多项式依次加到结果多项式中。值得注意的是，在相成的过程中不能改变两个原始多项式的值
#include<iostream>
using namespace std;class Term
{
public:Term(int c, int e);Term(int c, int e, Term* nxt);Term* InsertAfter(int c, int e);
private:int coef;int exp;Term* link;friend ostream& operator<<(ostream &, const Term &);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)
{link = new Term(c, e, link);return link;
}ostream& operator<<(ostream& out, const Term& val)
{if (0 == val.coef) return out;if (1 != val.coef)out << val.coef;switch (val.exp){case 0:break;case 1:out << "X"; break;default:out << "X^" << val.exp; break;}return out;
}class Polynominal
{
public:Polynominal();~Polynominal();void AddTerms(istream& in);void Output(ostream& out)const;void PolyAdd(Polynominal& r);void PolyMul(Polynominal& r);
private:Term* theList;friend ostream& operator<<(ostream &, const Polynominal &);friend istream& operator>>(istream&, Polynominal &);friend Polynominal& operator+(Polynominal &, Polynominal &);friend Polynominal& operator*(Polynominal &, Polynominal &);
};Polynominal::Polynominal()
{theList = new Term(0, -1); //头结点theList->link = NULL; //单链表尾结点指针域为空
}Polynominal::~Polynominal()
{Term* p = theList->link;while (p != NULL){theList->link = p->link;delete p;p = theList->link;}delete theList;
}void Polynominal::AddTerms(istream & in)
{Term* q = theList;int c, e;for (;;){cout << "Input a term(coef,exp):\n" << endl;cin >> c >> e;q = q->InsertAfter(c, e);if (0 > e) break;}
}void Polynominal::Output(ostream& out)const
{int first = 1;Term *p = theList->link;for (; p != NULL && p->exp >= 0; p = p->link){if (!first && (p->coef>0)) out << "+";first = 0;out << *p;}cout << endl;
}void Polynominal::PolyAdd(Polynominal& r)
{Term *q, *q1 = theList, *p; //q1指向表头结点p = r.theList->link; //p指向第一个要处理的结点q = q1->link; //q1是q的前驱，p和q就指向两个当前进行比较的项while (p != NULL && p->exp >= 0)//对r的单循环链表遍历，知道全部结点都处理完{while (p->exp < q->exp) //跳过q->exp大的项{q1 = q;q = q->link;}if (p->exp == q->exp) //当指数相等时，系数相加{q->coef = q->coef + p->coef;if (q->coef == 0) //若相加后系数为0，则删除q{q1->link = q->link;delete(q);q = q1->link; //重置q指针}else{q1 = q; //若相加后系数不为0，则移动q1和qq = q->link;}}else //p>exp>q->exp的情况q1 = q1->InsertAfter(p->coef, p->exp); //以p的系数和指数生成新结点，插入q1后p = p->link;}
}void Polynominal::PolyMul(Polynominal& r)
{Polynominal result; //定义相乘后的数据Term *n = result.theList; //n指向result的头结点n = n->InsertAfter(0, 0); //在result的头结点后插入新结点，系数指数均为0Term *p = r.theList->link; //p指向第一个要处理的结点while(p->exp >= 0) //对r的单循环链表遍历{Polynominal tmp; //存储某段相乘后的数据Term *m = tmp.theList; //m指向tmp的头结点Term *q = theList->link; //q指向表头结点的后继结点while(q->exp >= 0) //对当前对象的单循环环链表遍历{m = m->InsertAfter((p->coef)*(q->coef), (p->exp) + (q->exp)); //生成新结点插入n后q = q->link; }result.PolyAdd(tmp); //将temp加到result上p = p->link; }Term *q = theList->link; //q指向表头结点的后继结点while(q != NULL) //删除原对象的所有数据{theList->link = q->link;delete q;q = theList->link;}q = theList;q = q->InsertAfter(0, 0);PolyAdd(result); //将result加到当前对象上
}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;
}int main()
{int choose;cout << "choose calculate type 1.add 2.mul" << endl;cin >> choose;Polynominal p, q;switch (choose){case 1:cin >> p; cout << p;cin >> q; cout << q;q = q + p;break;case 2:cin >> p; cout << p;cin >> q; cout << q;q = q * p;break;}cout << q;return 0;
}
这篇关于南邮数据结构实验1 一元多项式的相加和相乘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
