数据结构实验1(一元多项式的相加和相乘)
最后更新于：2022-04-01 20:51:26
实验要求：
1.设计带表头的结点的单链表表示多项式类。
2.在该类上增加成员函数void PolyMul(Polynominal &r)，并重载*运算符。
3.实现菜单驱动的main函数，测试多项式的各个运算：输入多项式，显示多项式，以及多项式加法和乘法运算。
4.采用带表头的非循环链表存储多项式。
大致结构以及加法的运算书上的代码已经给出。乘法运算：将乘数多项式的每一项与被乘数多项式的所有项分别相乘(系数相乘，指数
相加)，得到中间多项式。调用PolyAdd函数将这些中间多项式依次加到结果多项式中。
实现代码：
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
class Term
{
public:
Term(int c, int e);
Term(int c, int e, Term *nxt);
Term* InsertAfter(int c, int e); // 在this指针指示的结点后插入新节点
private:
int coef, exp; // coef * x^exp
Term* link;
friend ostream & operator << (ostream &, const Term &);
friend class Polynominal;
/* data */
};
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) // 为新项申请结点的存储单元，并用Term函数将c, e, this -> link 的值填入新节点的相应域
{
link = new Term(c, e, link);
return link;
}
ostream & operator << (ostream& out, const Term& val)
{
if(val.coef == 0) return out;
if(val.coef != 1) 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 &);
/* data */
};
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;
while(true) {
cout << "Input a term(coef, exp):" << endl << endl;
cin >> c >> e;
q = q -> InsertAfter(c, e); // 将c，e插入表尾结点q之后
if(e < 0) break; // 当输入指数小于0时，构造结束
}
}
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; // 调用Term类上重载的"<<"操作
}
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 { // 若相加后系数不为0，则移动q1和q
q1 = q;
q = q -> link;
}
}
else q1 = q1 -> InsertAfter(p -> coef, p -> exp); // 若p -> exp > q -> exp则以p的系数和指数生成新结点，插入q1后
p = p -> link;
}
}
void Polynominal::PolyMul(Polynominal& r)
{
Polynominal result; // 存储结果
Term *n = result.theList; // n指向result的头结点
n = n -> InsertAfter(0, 0); // 将0, 0插入result的头结点之后
Term *p = r.theList -> link; // p指向第一个要处理的结点
while(p -> exp >= 0) { // 对r的单链表遍历，直到全部结点都处理完
Polynominal tmp; // 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)); // 生成新结点插入m后
q = q -> link;
}
result.PolyAdd(tmp); // 当前结果加到result上
p = p -> link;
}
Term *q = theList -> link;
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, 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 argc, char const *argv[])
{
cout << "***********" << endl;
cout << " 按1进行多项式加法" << endl;
cout << " 按2进行多项式乘法" << endl;
cout << " 按0退出程序" << endl;
cout << "***********" << endl;
int num;
while(cin >> num && num) {
cout << "请输入多项式p：" << endl;
Polynominal p, q;
cin >> p;
cout << p << endl;
cout << "请输入多项式q：" << endl;
cin >> q;
cout << q << endl;
if(num == 1) {
Polynominal ans = p + q;
cout << "p + q = " << ans << endl;
}
else {
Polynominal ans = p * q;
cout << "p * q = " << ans << endl;
}
cout << "***********" << endl;
cout << " 按1进行多项式加法" << endl;
cout << " 按2进行多项式乘法" << endl;
cout << " 按0退出程序" << endl;
cout << "***********" << endl << endl;
}
cout << endl << "感谢检查" << endl;
return 0;
}
~~~
';