单链表之一元多项式求和C++实现

单链表之一元多项式求和

一元多项式求和单链表实现伪代码1、工作指针 pre、p、qre、q 初始化2、while（p 存在且 q 存在）执行下列三种情况之一： 　　2.1、若 p->exp < q->exp：指针 p 后移； 　　2.2、若 p->exp > q->exp，则 　　　　2.2.1、将结点 q 插到结点 p 之前 　　　　2.2.2、指针 p 指向他原指结点的下一个结点； 　　2.3、若 p->exp == q->exp，则 　　　　2.3.1、p->coef = p->coef + q->coef 　　　　2.3.2、若 p->coef == 0,则执行下列操作，否则指针 p 后移， 　　　　　　2.3.2.1、删除结点 p 　　　　　　2.3.2.2、使指针 p 指向它原指结点的下一个结点 　　　　2.3.3、删除结点 q 　　　　2.3.4、使指针 q 指向它原指结点的下一个结点3、如果 q 不为空，将结点 q 链接在第一个单链表的后面。一、一元多项式求和单链表实现头文件：PolynomialOfOneIndeterminateAdd.h

//一元多项式求和头文件#include<iostream>using namespace std;template<class DataType>//定义单链表结点struct Node{ 　　//数据域：非零项的系数和指数 　　DataType coef, exp; 　　//指针域 　　Node<DataType> *next;};//定义存放一元多项式的类template<class DataType>class Linklist{private: 　　Node<DataType> *first; 　　//一元多项式的项数 　　int size;public: 　　//构造函数 　　Linklist(); 　　//初始化一元多项式 　　void Init(); 　　//输出一元多项式 　　void Print(); 　　//定义一元多项式的的加法操作 　　Linklist<DataType> operator+(Linklist &p2);};

//构造函数template<class DataType>Linklist<DataType>::Linklist(){ 　　first = new Node<DataType>; 　　first = NULL; 　　size = 0;}

//实现一元多项式单链表的初始化template<class DataType>void Linklist<DataType>::Init(){ 　　cout << "多项式的元素个数为:"; 　　cin >> size; 　　DataType x, y; 　　cout << "请输入第1项的系数:"; 　　cin >> x; 　　cout << "请输入第1项的指数:"; 　　cin >> y; 　　Node<DataType> *m; 　　m = new Node<DataType>; 　　m->coef = x; 　　m->exp = y; 　　m->next = NULL; 　　first = m; 　　for (int i = 2; i <= size; i++) 　　{ 　　　　cout << "请输入第" << i << "项的系数:"; 　　　　cin >> x; 　　　　cout << "请输入第" << i << "项的指数:"; 　　　　cin >> y; 　　　　Node<DataType> *n; 　　　　n = new Node<DataType>; 　　　　n->coef = x; 　　　　n->exp = y; 　　　　n->next = NULL; 　　　　m->next = n; 　　　　m = n; 　　}}

//实现一元多项式单链表实的输出template<class DataType>void Linklist<DataType>::Print(){ 　　Node<DataType> *m = first; 　　while (m != NULL) 　　{ 　　　　if (m == first) 　　　　{ 　　　　　　if (m->coef != 0 && m->exp != 0) 　　　　　　{ 　　　　　　　　cout << m->coef << "x^" << m->exp; 　　　　　　} 　　　　　　else if (m->coef != 0 && m->exp == 0) 　　　　　　{ 　　　　　　　　cout << m->coef; 　　　　　　} 　　　　} 　　　　else 　　　　{ 　　　　　　if (m->coef > 0 && m->exp != 0){ 　　　　　　　　cout << "+" << m->coef << "x^" << m->exp; 　　　　　　} 　　　　　　else if (m->coef<0 && m->exp != 0) 　　　　　　{ 　　　　　　　　cout << m->coef << "x^" << m->exp; 　　　　　　} 　　　　　　else if (m->coef>0 && m->exp == 0) 　　　　　　{ 　　　　　　　　　cout << "+" << m->coef; 　　　　　　} 　　　　　　else if (m->coef < 0 && m->exp == 0) 　　　　　　{ 　　　　　　　　cout << m->coef; 　　　　　　} 　　　　} 　　　　m = m->next; 　　} 　　cout << endl;}

//实现一元多项式单链表的相加template<class DataType>Linklist<DataType> Linklist<DataType>::operator+(Linklist &p2){ 　　//声明工作指针 　　Node<DataType> *pre, *p, *qre, *q; 　　//初始化工作指针 　　pre = this->first; 　　p = pre->next; 　　qre = p2.first; 　　q = qre->next; 　　while (p != NULL&&q != NULL) 　　{ 　　　　//p->exp < q->exp：指针 p 后移 　　　　if (p->exp < q->exp) 　　　　{ 　　　　　　pre = p; 　　　　　　p = p->next; 　　　　} 　　　　//p->exp > q->exp：将结点 q 插到结点 p 之前，指针 p 指向他原指结点的下一个结点 　　　　if (p->exp > q->exp) 　　　　{ 　　　　　　Node<DataType> *s; 　　　　　　s = q->next; 　　　　　　pre->next = q; 　　　　　　q->next = p; 　　　　　　q = s; 　　　　} 　　　　//p->exp == q->exp： 　　　　if (p->exp == q->exp) 　　　　{ 　　　　　　//p->coef = p->coef + q->coef 　　　　　　p->coef = p->coef + q->coef; 　　　　　　if (p->coef == 0) 　　　　　　{ 　　　　　　　　//使指针 p 指向它原指结点的下一个结点 　　　　　　　　pre->next = p->next; 　　　　　　　　//删除结点 p 　　　　　　　　delete p; 　　　　　　　　p = p->next; 　　　　　　} 　　　　　　else 　　　　　　{ 　　　　　　　　pre = p; 　　　　　　　　p = pre->next; 　　　　　　} 　　　　　　//使指针 q 指向它原指结点的下一个结点 　　　　　　qre->next = q->next; 　　　　　　//删除结点 q 　　　　　　delete q; 　　　　　　q = qre->next; 　　　　} 　　} 　　//如果 q 不为空，将结点 q 链接在第一个单链表的后面。 　　if (q != NULL) 　　{ 　　　　pre->next = q; 　　　　delete p2.first; 　　} 　　return *this;}

二、测试一元多项式单链表实现的源程序：TestPolynomialOfOneIndeterminateAdd.cpp

#include<iostream>//引入一元多项式之单链表实现的头文件#include "PolynomialOfOneIndeterminateAdd.h"using namespace std;

int main(){ 　　//声明一元多项式单链表 　　Linklist<int> p1, p2, p3; 　　cout << "请按指数由小到大的顺序定义多项式A(x):" << endl; 　　p1.Init(); 　　cout << "输入的多项式A(x)为:"; 　　p1.Print(); 　　cout << "\n请按指数由小到大的顺序定义多项式B(x):" << endl; 　　p2.Init(); 　　cout << "输入的多项式B(x)为:"; 　　p2.Print(); 　　//一元多项式相加 　　p3 = p1 + p2; 　　cout << "\n多项式A(x)和多项式B(x)的和为:" << endl; 　　p3.Print(); 　　return 0;}