数据结构与程序设计10-多项式的例子

数据结构与程序设计(10)王丽苹lipingwang@4/21/20231.应用：多项式求解后序波兰式的求解abc-d*(1)如果a，b，c为整数如何求解。(2)如果a，b，c为多项式如何求解。AH=7x14+2x8+-10x6+1

BH=4x18+8x14-3x10+10x6-x44/21/20232.多项式及其相加在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。优点是：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。链接队列和栈的综合应用4/21/20233.多项式链表的相加AH=7x14+2x8+-10x6+1

BH=4x18+8x14-3x10+10x6-x471428-106110^418814-310106-14^4181514-31028-14110^AH.firstBH.firstCH.first4/21/20234.链接队列和栈的综合应用目录Polynomial下例程4/21/20235.链接队列和栈的综合应用top_nodePolynomialnextPolynomialnextclassStack{protected:Node*top_node;};structNode{Polynomialentry;Node*next;};4/21/20236.链接队列和栈的综合应用PolynomialTermnextTermnextclassQueue{protected:SmallNode*front,*rear;};classSmallNode{public:Termentry;SmallNode*next;};Termnextfrontrear4/21/20237.链接队列和栈的综合应用classTerm{public:intdegree;doublecoefficient;};degreecoefficientEg:3x^2degree=2coefficient=34/21/20238.链接队列和栈的综合应用--TermclassTerm{public:Term(intexponent=0,doublescalar=0);intdegree;doublecoefficient;};4/21/20239.链接队列和栈的综合应用--Term#include"Term.h"Term::Term(intexponent,doublescalar)/*Post:TheTermisinitializedwiththegivencoefficientandexponent,orwithdefaultparametervaluesof0.*/{degree=exponent;coefficient=scalar;}4/21/202310.链接队列和栈的综合应用--PolynomialtypedefTermQueue_entry;typedefTermSmallNode_entry;classSmallNode{//datamemberspublic: SmallNode_entryentry; SmallNode*next;//constructors SmallNode(); SmallNode(SmallNode_entryitem,SmallNode*add_on=0);};4/21/202311.链接队列和栈的综合应用--PolynomialclassQueue{public://standardQueuemethods Queue(); boolempty()const; Error_codeappend(constQueue_entry&item); Error_codeserve(); Error_coderetrieve(Queue_entry&item)const;//safetyfeaturesforlinkedstructures ~Queue();protected: SmallNode*front,*rear;};//Queue表示一个多项式4/21/202312.链接队列和栈的综合应用--PolynomialclassExtended_queue:publicQueue{public:intsize()const;voidclear();Error_codeserve_and_retrieve(Queue_entry&item);};4/21/202313.链接队列和栈的综合应用--PolynomialclassPolynomial:privateExtended_queue{//Useprivateinheritance.public:Polynomial();Polynomial::Polynomial(constPolynomial&original);voidoperator=(constPolynomial&original);voidread();voidprint()const;voidequals_sum(Polynomialp,Polynomialq);intdegree()const;};//用Polynomial来封装Queue，Polynomial表示一个多项式4/21/202314.链接队列和栈的综合应用--PolynomialPolynomial::Polynomial(){front=NULL;rear=NULL;}4/21/202315.链接队列和栈的综合应用--PolynomialPolynomial::Polynomial(constPolynomial&original){SmallNode*new_front,*new_copy,*original_front=original.front,*new_rear;if(original_front==NULL){ new_front=NULL; new_rear=NULL;}else{//Duplicatethelinkednodesnew_copy=new_front=newSmallNode(original_front->entry);while(original_front->next!=0){original_front=original_front->next;new_copy->next=newSmallNode(original_front->entry);new_copy=new_copy->next;}new_rear=new_copy;}front=new_front;rear=new_rear;}4/21/202316.LinkedQueues--Queue

original_frontnew_frontnew_copynew_frontnew_copy4/21/202317.链接队列和栈的综合应用--PolynomialvoidPolynomial::operator=(constPolynomial&original){SmallNode*new_front,*new_copy,*original_front=original.front,*new_rear;if(original_front==NULL){ new_front=NULL; new_rear=NULL;}else{//Duplicatethelinkednodesnew_copy=new_front=newSmallNode(original_front->entry);while(original_front->next!=0) {original_front=original_front->next;new_copy->next=newSmallNode(original_front->entry);new_copy=new_copy->next;} new_rear=new_copy;}while(!empty())//CleanoutoldQueueentriesserve();front=new_front;rear=new_rear;}4/21/202318.链接队列和栈的综合应用—Polynomial

p147voidPolynomial::print()const/*Post:ThePolynomialisprintedtocout.*/{SmallNode*print_node=front;boolfirst_term=true;while(print_node!=NULL){Term&print_term=print_node->entry;if(first_term){//Inthiscase,suppressprintinganinitial'+'.first_term=false;if(print_term.coefficient<0)cout<<"-";}elseif(print_term.coefficient<0)cout<<"-";elsecout<<"+";doubler=(print_term.coefficient>=0)?print_term.coefficient:-(print_term.coefficient);if(r!=1)cout<<r;if(print_term.degree>1)cout<<"X^"<<print_term.degree;if(print_term.degree==1)cout<<"X";if(r==1&&print_term.degree==0)cout<<"1";print_node=print_node->next;}if(first_term)cout<<"0";//Print0foranemptyPolynomial.cout<<endl;}4/21/202319.LinkedQueues--Queue

print_node4/21/202320.链接队列和栈的综合应用—Polynomial

p148voidPolynomial::read(){clear();doublecoefficient;intlast_exponent,exponent;boolfirst_term=true;cout<<"Enterthecoefficientsandexponentsforthepolynomial,onepairperline."<<endl<<"Exponentsmustbeindescendingorder."<<endl<<"Enteracoefficientof0oranexponentof0toterminate."<<endl;do{cout<<"coefficient?"<<flush;cin>>coefficient;if(coefficient!=0.0){cout<<"exponent?"<<flush;cin>>exponent;if((!first_term&&exponent>=last_exponent)||exponent<0){exponent=0;cout<<"Badexponent:Polynomialterminateswithoutitslastterm."<<endl;}else{Termnew_term(exponent,coefficient);append(new_term);first_term=false;}last_exponent=exponent;}}while(coefficient!=0.0&&exponent!=0);}4/21/202321.链接队列和栈的综合应用--PolynomialintPolynomial::degree()const/*Post:IfthePolynomialisidentically0,aresultof-1isreturned.OtherwisethedegreeofthePolynomialisreturned.*/{if(empty())return-1;Termlead;retrieve(lead);returnlead.degree;}4/21/202322.链接队列和栈的综合应用—Polynomial

p149voidPolynomial::equals_sum(Polynomialp,Polynomialq){clear();while(!p.empty()||!q.empty()){Termp_term,q_term;if(p.degree()>q.degree()){p.serve_and_retrieve(p_term);append(p_term);}elseif(q.degree()>p.degree()){q.serve_and_retrieve(q_term);append(q_term);}else{p.serve_and_retrieve(p_term);q.serve_and_retrieve(q_term);if(p_term.coefficient+q_term.coefficient!=0){Termanswer_term(p_term.degree,p_term.coefficient+q_term.coefficient);append(answer_term);}}}}4/21/202323.链接队列和栈的综合应用—LinkStacktypedefPolynomialNode_entry;structNode{//datamembersNode_entryentry;Node*next;//constructorsNode();Node(constNode_entryitem,Node*add_on=0);};4/21/202324.链接队列和栈的综合应用—LinkStackclassStack{public://StandardStackmethodsStack();boolempty()const;Error_codepush(constNode_entry&item);Error_codepop();Error_codetop(Node_entry&item)const;//Safetyfeaturesforlinkedstructures~Stack();protected:Node*top_node;};4/21/202325.链接队列和栈的综合应用—Mainvoidmain()/*Post:Theprogramhasexecutedsimplepolynomialarithmeticcommandsenteredbytheuser.Uses:TheclassesStackandPolynomialandthefunctionsintroduction,instructions,do_command,andget_command.*/{Stackstored_polynomials;voidintroduction();voidinstructions();booldo_command(charcommand,Stack&stored_polynomials);charget_command();chartolower(charcommand);introduction();instructions();while(do_command(get_command(),stored_polynomials));}4/21/202326.链接队列和栈的综合应用—Mainvoidintroduction(){cout<<"Thisisapolynomialsprogram."<<endl;}voidinstructions(){cout<<"Pleaseenteravalidcommand:"<<endl <<"[?]ReadaPolynomial"<<endl <<"[=]ReturnTopPolynomial"<<endl<<"[+]SumtwoPolynomial"<<endl<<"[q]Quit."<<endl;}4/21/202327.链接队列和栈的综合应用—Main

p143booldo_command(charcommand,Stack&stored_polynomials)/*Pre:Thefirstparameterspecifiesavalidcalculatorcommand.Post:ThecommandspecifiedbythefirstparameterhasbeenappliedtotheStackofPolynomialobjectsgivenbythesecondparameter.Aresultoftrueisreturnedunlesscommand=='q'.Uses:TheclassesStackandPolynomial.*/{Polynomialp,q,r;

switch(command){

4/21/202328.链接队列和栈的综合应用—Main

case'?':p.read();if(stored_polynomials.push(p)==overflow)cout<<"Warning:Stackfull,lostpolynomial"<<endl;break;case'=':if(stored_polynomials.empty())cout<<"Stackempty"<<endl;else{stored_polynomials.top(p);p.print();}break;4/21/202329.链接队列和栈的综合应用—Main

case'+':if(stored_polynomials.empty())cout<<"Stackempty"<<endl;else{stored_polynomials.top(p);stored_polynomials.pop();if(stored_polynomials.empty()){cout<<"Stackhasjustonepolynomial"<<endl;stor