數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)10-多項(xiàng)式的例子

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)(10)王麗蘋lipingwang@4/21/20231.應(yīng)用：多項(xiàng)式求解后序波蘭式的求解abc-d*(1)如果a，b，c為整數(shù)如何求解。(2)如果a，b，c為多項(xiàng)式如何求解。AH=7x14+2x8+-10x6+1

BH=4x18+8x14-3x10+10x6-x44/21/20232.多項(xiàng)式及其相加在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)增加了一個(gè)數(shù)據(jù)成員link，作為鏈接指針。優(yōu)點(diǎn)是：多項(xiàng)式的項(xiàng)數(shù)可以動(dòng)態(tài)地增長(zhǎng)，不存在存儲(chǔ)溢出問(wèn)題。插入、刪除方便，不移動(dòng)元素。鏈接隊(duì)列和棧的綜合應(yīng)用4/21/20233.多項(xiàng)式鏈表的相加AH=7x14+2x8+-10x6+1

BH=4x18+8x14-3x10+10x6-x471428-106110^418814-310106-14^4181514-31028-14110^AH.firstBH.firstCH.first4/21/20234.鏈接隊(duì)列和棧的綜合應(yīng)用目錄Polynomial下例程4/21/20235.鏈接隊(duì)列和棧的綜合應(yīng)用top_nodePolynomialnextPolynomialnextclassStack{protected:Node*top_node;};structNode{Polynomialentry;Node*next;};4/21/20236.鏈接隊(duì)列和棧的綜合應(yīng)用PolynomialTermnextTermnextclassQueue{protected:SmallNode*front,*rear;};classSmallNode{public:Termentry;SmallNode*next;};Termnextfrontrear4/21/20237.鏈接隊(duì)列和棧的綜合應(yīng)用classTerm{public:intdegree;doublecoefficient;};degreecoefficientEg:3x^2degree=2coefficient=34/21/20238.鏈接隊(duì)列和棧的綜合應(yīng)用--TermclassTerm{public:Term(intexponent=0,doublescalar=0);intdegree;doublecoefficient;};4/21/20239.鏈接隊(duì)列和棧的綜合應(yīng)用--Term#include"Term.h"Term::Term(intexponent,doublescalar)/*Post:TheTermisinitializedwiththegivencoefficientandexponent,orwithdefaultparametervaluesof0.*/{degree=exponent;coefficient=scalar;}4/21/202310.鏈接隊(duì)列和棧的綜合應(yīng)用--PolynomialtypedefTermQueue_entry;typedefTermSmallNode_entry;classSmallNode{//datamemberspublic: SmallNode_entryentry; SmallNode*next;//constructors SmallNode(); SmallNode(SmallNode_entryitem,SmallNode*add_on=0);};4/21/202311.鏈接隊(duì)列和棧的綜合應(yīng)用--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表示一個(gè)多項(xiàng)式4/21/202312.鏈接隊(duì)列和棧的綜合應(yīng)用--PolynomialclassExtended_queue:publicQueue{public:intsize()const;voidclear();Error_codeserve_and_retrieve(Queue_entry&item);};4/21/202313.鏈接隊(duì)列和棧的綜合應(yīng)用--PolynomialclassPolynomial:privateExtended_queue{//Useprivateinheritance.public:Polynomial();Polynomial::Polynomial(constPolynomial&original);voidoperator=(constPolynomial&original);voidread();voidprint()const;voidequals_sum(Polynomialp,Polynomialq);intdegree()const;};//用Polynomial來(lái)封裝Queue，Polynomial表示一個(gè)多項(xiàng)式4/21/202314.鏈接隊(duì)列和棧的綜合應(yīng)用--PolynomialPolynomial::Polynomial(){front=NULL;rear=NULL;}4/21/202315.鏈接隊(duì)列和棧的綜合應(yīng)用--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.鏈接隊(duì)列和棧的綜合應(yīng)用--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.鏈接隊(duì)列和棧的綜合應(yīng)用—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.鏈接隊(duì)列和棧的綜合應(yīng)用—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.鏈接隊(duì)列和棧的綜合應(yīng)用--PolynomialintPolynomial::degree()const/*Post:IfthePolynomialisidentically0,aresultof-1isreturned.OtherwisethedegreeofthePolynomialisreturned.*/{if(empty())return-1;Termlead;retrieve(lead);returnlead.degree;}4/21/202322.鏈接隊(duì)列和棧的綜合應(yīng)用—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.鏈接隊(duì)列和棧的綜合應(yīng)用—LinkStacktypedefPolynomialNode_entry;structNode{//datamembersNode_entryentry;Node*next;//constructorsNode();Node(constNode_entryitem,Node*add_on=0);};4/21/202324.鏈接隊(duì)列和棧的綜合應(yīng)用—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.鏈接隊(duì)列和棧的綜合應(yīng)用—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.鏈接隊(duì)列和棧的綜合應(yīng)用—Mainvoidintroduction(){cout<<"Thisisapolynomialsprogram."<<endl;}voidinstructions(){cout<<"Pleaseenteravalidcommand:"<<endl <<"[?]ReadaPolynomial"<<endl <<"[=]ReturnTopPolynomial"<<endl<<"[+]SumtwoPolynomial"<<endl<<"[q]Quit."<<endl;}4/21/202327.鏈接隊(duì)列和棧的綜合應(yīng)用—Main

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

switch(command){

4/21/202328.鏈接隊(duì)列和棧的綜合應(yīng)用—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.鏈接隊(duì)列和棧的綜合應(yīng)用—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