南邮数据结构实验一

return out; if (1!= val.coef) out << val.coef; switch (val.exp) {

case 0:break;

case 1:out << \; break;

default:out << \ << 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; }

8

delete theList; }

void Polynominal::AddTerms(istream & in) {

Term* q = theList; int c, e; for (;;) {

cout << \ << 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;

9

if (q->coef == 0) //若相加后系数为0，则删除q {

q1->link = q->link; delete(q);

q = q1->link; //重置q指针 } else {

q1 = q; //若相加后系数不为0，则移动q1和q q = 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的头结点后插入新结点，系数指数均为0 Term *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;

10

}

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 << \ << endl; cin >> choose; Polynominal p, q; switch (choose) {

case 1:

cin >> p; cout << p; cin >> q; cout << q; q = q + p; break; case 2:

11