數據結構與程序設計(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