基于单链表的多项式问题
上学期的东西了，不想再去细究思路了，直接贴代码，注释很详细
#include"Polynomial.h"#include<iostream>using namespace std;Polynomial::Polynomial(){first = new LinkNode;//开辟头结点，初始化指数域为-1rear = first;}Polynomial::Polynomial(LinkNode * fir){first = new LinkNode;first->link = fir;//在头结点的后面接上一串}Polynomial::Polynomial(Polynomial &P){LinkNode *srcptr = P.GetHead();if(srcptr == NULL)exit(1);LinkNode *destptr = first = new LinkNode;//初始化当前多项式LinkNode *newNode;float current_coef;//用于记录当前系数int current_expn;//记录当前指数while(srcptr->link != NULL){current_coef = srcptr->link->coef;current_expn = srcptr->link->expn;newNode = new LinkNode(current_coef,current_expn);destptr->link = newNode;srcptr = srcptr->link;destptr = destptr->link;}}Polynomial::~Polynomial(){//makeEmpty();//是在不懂为什么不行 先注释掉}void Polynomial::makeEmpty(){LinkNode * del;while(first->link != NULL)//如果为空表则头结点的指针域为NULL不会执行循环{del = first->link ;//不为空表第一次循环的情况下，把第1个结点的指针赋给了del指针first->link = del->link ;//把当前要删除的结点的后面一个节点接在头结点指针域上, 在最后循环结束之前最后结点的NULL赋给了first->link,所以会跳出delete del ;}}istream& operator>> (istream& input,Polynomial &P){LinkNode *last = P.GetHead();//头指针赋值一份LinkNode *newNode;float current_coef;//用于记录当前系数int current_expn;//记录当前指数input>>current_coef>>current_expn;while(current_coef != 0){newNode = new LinkNode(current_coef,current_expn);last->link = newNode;newNode->plink = last;last = last->link;input>>current_coef>>current_expn;}P.rear = last;P.Sort();//输入完毕后开始合并 并排序默认升序P.Settle();//在排序后直接合并同类项return input;}ostream& operator<< (ostream& output,Polynomial &P){LinkNode *current = P.GetHead()->link;while(current != NULL){cout<<*current;current = current->link;}return output;}void Polynomial::Sort()//指数升序排序{LinkNode *current1,*current2 ;for(current1=first->link;current1!=NULL;current1=current1->link){for(current2=current1->link;current2!=NULL;current2=current2->link){if(current1->expn > current2->expn){int expn_temp;//指数临时存储变量expn_temp = current1->expn;current1->expn = current2->expn;current2->expn = expn_temp;float coef_temp;//系数临时存储变量coef_temp = current1->coef;current1->coef = current2->coef;current2->coef = coef_temp;}}}}int Polynomial::Length(){LinkNode * current = first ;int elemnum = 0;while(current->link != NULL)//如果头结点指针域为NULL则不执行循环直接返回0值{current = current->link ;elemnum++;}return elemnum;}LinkNode * Polynomial::GetHead(){return first;}LinkNode * Polynomial::Getrear(){return rear;}void Polynomial::reverse_order(){int elemnum = Length();//调用求长度函数 获取多项式的元素个数LinkNode *current1 = first->link; //首端LinkNode *current2 = rear;//尾端 开始逆置for(int idx = 0; idx < elemnum/2 ;idx++){int expn_temp;//指数临时存储变量expn_temp = current1->expn;current1->expn = current2->expn;current2->expn = expn_temp;float coef_temp;//系数临时存储变量coef_temp = current1->coef;current1->coef = current2->coef;current2->coef = coef_temp;current1 = current1->link;current2 = current2->plink;}}Polynomial operator+ (Polynomial &P1,Polynomial &P2){P1.Sort(); P2.Sort();//先对两个多项式进行指数升序排序,便于后面的合并LinkNode *current1 = P1.GetHead() ->link;//获取两个头指针LinkNode *current2 = P2.GetHead() ->link;LinkNode *current3;//用于循环跳出后的指针承接LinkNode *newNode;//每次重新开辟结点LinkNode *last,*pol;//用于记录最后相加结果的头指针,最后要以他为参数返回一个Polynomial类last = pol = new LinkNode;float coef_elem;int expn_elem;while(current1!=NULL && current2!=NULL)//在两个指针都不为空的时候进行指数比较,否则跳出{if(current1->expn < current2->expn){coef_elem = current1->coef;expn_elem = current1->expn;newNode = new LinkNode(coef_elem,expn_elem);last->link = newNode;//新开辟的结点连接在last的后面last = last->link;current1 = current1->link;continue;}if(current1->expn > current2->expn){coef_elem = current2->coef;expn_elem = current2->expn;newNode = new LinkNode(coef_elem,expn_elem);last->link = newNode;//新开辟的结点连接在last的后面last = last->link;current2 = current2->link;continue;}if(current1->expn == current2->expn)//当比较到两个指数相同时候{if(current1->coef + current2->coef == 0)//系数相加为0 则两指针都后移{current1 = current1->link;current2 = current2->link;continue;//如果在指数相等的情况下系数相加为0则两个指针全都后移一位 直接调相下一次循环比较}if(current1->coef + current2->coef != 0)//如果不等于0 则指定一个加到另一个上 也都后移{coef_elem = current1->coef + current2->coef;//系数相加expn_elem = current1->expn; newNode = new LinkNode(coef_elem,expn_elem); last->link = newNode;//新开辟的结点连接在last的后面 last = last->link; current1 = current1->link;//两个指针都后移一位current2 = current2->link;continue;}}}if(current1==NULL && current2==NULL)//如果循环跳出时 可能是都结束了则直接返回多项式避免了后面的操作{return Polynomial(pol->link);}//跳出循环进入NULL判断current3 = ((current1 == NULL) ? current2 : current1);while(current3 != NULL){coef_elem = current3->coef;expn_elem = current3->expn;newNode = new LinkNode(coef_elem,expn_elem);last->link = newNode;//新开辟的结点连接在last的后面last = last->link;current3 = current3->link;}return Polynomial(pol->link);//最正常情况下的返回}void Polynomial::operator= (Polynomial &P){//makeEmpty();LinkNode *srcptr = P.GetHead();if(srcptr == NULL)exit(1);LinkNode *destptr = first;//初始化当前多项式LinkNode *newNode;float current_coef;//用于记录当前系数int current_expn;//记录当前指数while(srcptr->link != NULL){current_coef = srcptr->link->coef;current_expn = srcptr->link->expn;newNode = new LinkNode(current_coef,current_expn);destptr->link = newNode;srcptr = srcptr->link;destptr = destptr->link;}}void Polynomial::Settle(){LinkNode *current1,*current2;//在默认升序排序后的合并同类项LinkNode *del;for(current1=first->link;current1->link!=NULL;current1=current1->link)//循环终止条件是关键 外层只需进行到倒数第二个{//外层开始从第一个开始循环current2 = current1->link;//把后一个的指针赋给2for(; ;){//这里的死循环是为了解决 合并后 指针后一问题if(current2->expn != current1->expn)//只要条件成立 说明可以跳出内层死循环 外层开始下一次循环break;if(current2->expn == current1->expn){//2始终在1的后面，确保这一点非常有利于写合并于删除算法current1->coef = current1->coef + current2->coef;//系数相加del = current2;current1->link = del->link;delete del;current2 = current1->link;if(current2 == NULL)//此步骤 是合并算法的最后一步判断标准return ;}}}}Polynomial operator* (Polynomial &P1,Polynomial &P2){P1.Sort();P1.Settle();//分别合并同类项 减少运算次数P2.Sort();P2.Settle();LinkNode *current1 = P1.GetHead()->link;LinkNode *last,*pol;LinkNode *newNode;last = pol = new LinkNode;//开辟新头结点 用于承接相乘之后的多项式float elem_coef;int elem_expn;for(; current1 != NULL; current1 =current1->link){LinkNode *current2 = P2.GetHead()->link;//每次外层循环开始都需要把内层指针置为首指针for(; current2 != NULL; current2 = current2->link){elem_coef = (current1->coef) * (current2->coef);//系数相乘elem_expn = (current1->expn) + (current2->expn);//指数相加newNode = new LinkNode(elem_coef,elem_expn);//每一次相乘的结果做成结点last->link = newNode;//接在pol的后面last = last->link;//last指针后移}}Polynomial POL(pol->link);//生成一个多项式POL.Sort();POL.Settle();//合并同类项return POL;//返回一个多项式对象}