数据结构与程序设计(王丽苹)10-多项式的例子.ppt

5/27/2023,数据结构与程序设计,1,数据结构与程序设计(10),王丽苹,5/27/2023,数据结构与程序设计,2,应用：多项式求解,后序波兰式的求解abc-d*(1)如果a，b，c为整数如何求解。(2)如果a，b，c为多项式如何求解。,AH=7x14+2x8+-10 x6+1 BH=4x18+8x14-3x10+10 x6-x4,5/27/2023,数据结构与程序设计,3,多项式及其相加在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。优点是：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。,链接队列和栈的综合应用,5/27/2023,数据结构与程序设计,4,多项式链表的相加,AH=7x14+2x8+-10 x6+1 BH=4x18+8x14-3x10+10 x6-x4,7 14,2 8,-10 6,1 10,4 18,8 14,-3 10,10 6,-1 4,4 18,15 14,-3 10,2 8,-1 4,1 10,AH.first,BH.first,CH.first,5/27/2023,数据结构与程序设计,5,链接队列和栈的综合应用,目录Polynomial下例程,5/27/2023,数据结构与程序设计,6,链接队列和栈的综合应用,top_node,Polynomialnext,Polynomialnext,class Stackprotected:Node*top_node;,struct Node Polynomial entry;Node*next;,5/27/2023,数据结构与程序设计,7,链接队列和栈的综合应用,Polynomial,Term next,Term next,class Queue protected:SmallNode*front,*rear;,class SmallNode public:Term entry;SmallNode*next;,Term next,front,rear,5/27/2023,数据结构与程序设计,8,链接队列和栈的综合应用,class Term public:int degree;double coefficient;,degreecoefficient,Eg:3x2degree=2coefficient=3,5/27/2023,数据结构与程序设计,9,链接队列和栈的综合应用-Term,class Term public:Term(int exponent=0,double scalar=0);int degree;double coefficient;,5/27/2023,数据结构与程序设计,10,链接队列和栈的综合应用-Term,#includeTerm.hTerm:Term(int exponent,double scalar)/*Post:The Term is initialized with the given coefficient and exponent,or with default parameter values of 0.*/degree=exponent;coefficient=scalar;,5/27/2023,数据结构与程序设计,11,链接队列和栈的综合应用-Polynomial,typedef Term Queue_entry;typedef Term SmallNode_entry;class SmallNode/data memberspublic:SmallNode_entry entry;SmallNode*next;/constructorsSmallNode();SmallNode(SmallNode_entry item,SmallNode*add_on=0);,5/27/2023,数据结构与程序设计,12,链接队列和栈的综合应用-Polynomial,class Queue public:/standard Queue methodsQueue();bool empty()const;Error_code append(const Queue_entry/Queue表示一个多项式,5/27/2023,数据结构与程序设计,13,链接队列和栈的综合应用-Polynomial,class Extended_queue:public Queue public:int size()const;void clear();Error_code serve_and_retrieve(Queue_entry,5/27/2023,数据结构与程序设计,14,链接队列和栈的综合应用-Polynomial,class Polynomial:private Extended_queue/Use private inheritance.public:Polynomial();Polynomial:Polynomial(const Polynomial/用Polynomial来封装Queue，Polynomial表示一个多项式,5/27/2023,数据结构与程序设计,15,链接队列和栈的综合应用-Polynomial,Polynomial:Polynomial()front=NULL;rear=NULL;,5/27/2023,数据结构与程序设计,16,链接队列和栈的综合应用-Polynomial,Polynomial:Polynomial(const Polynomial,5/27/2023,数据结构与程序设计,17,Linked Queues-Queue,original_frontnew_front new_copynew_front new_copy,5/27/2023,数据结构与程序设计,18,链接队列和栈的综合应用-Polynomial,void Polynomial:operator=(const Polynomial,5/27/2023,数据结构与程序设计,19,链接队列和栈的综合应用Polynomialp147,void Polynomial:print()const/*Post:The Polynomial is printed to cout.*/SmallNode*print_node=front;bool first_term=true;while(print_node!=NULL)Term,5/27/2023,数据结构与程序设计,20,Linked Queues-Queue,print_node,5/27/2023,数据结构与程序设计,21,链接队列和栈的综合应用Polynomialp148,void Polynomial:read()clear();double coefficient;int last_exponent,exponent;bool first_term=true;cout coefficient;if(coefficient!=0.0)cout exponent;if(!first_term,5/27/2023,数据结构与程序设计,22,链接队列和栈的综合应用-Polynomial,int Polynomial:degree()const/*Post:If the Polynomial is identically 0,a result of-1 is returned.Otherwise the degree of the Polynomial is returned.*/if(empty()return-1;Term lead;retrieve(lead);return lead.degree;,5/27/2023,数据结构与程序设计,23,链接队列和栈的综合应用Polynomialp149,void Polynomial:equals_sum(Polynomial p,Polynomial q)clear();while(!p.empty()|!q.empty()Term p_term,q_term;if(p.degree()q.degree()p.serve_and_retrieve(p_term);append(p_term);else if(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)Term answer_term(p_term.degree,p_term.coefficient+q_term.coefficient);append(answer_term);,5/27/2023,数据结构与程序设计,24,链接队列和栈的综合应用Link Stack,typedef Polynomial Node_entry;struct Node/data members Node_entry entry;Node*next;/constructors Node();Node(const Node_entry item,Node*add_on=0);,5/27/2023,数据结构与程序设计,25,链接队列和栈的综合应用Link Stack,class Stackpublic:/Standard Stack methods Stack();bool empty()const;Error_code push(const Node_entry,5/27/2023,数据结构与程序设计,26,链接队列和栈的综合应用Main,void main()/*Post:The program has executed simple polynomial arithmetic commands entered by the user.Uses:The classes Stack and Polynomial and the functions introduction,instructions,do_command,and get_command.*/Stack stored_polynomials;void introduction();void instructions();bool do_command(char command,Stack,5/27/2023,数据结构与程序设计,27,链接队列和栈的综合应用Main,void introduction()coutThis is a polynomials program.endl;void instructions()cout Please enter a valid command:endl?Read a Polynomial endl=Return Top Polynomial endl+Sum two Polynomial endl q Quit.endl;,5/27/2023,数据结构与程序设计,28,链接队列和栈的综合应用Mainp143,bool do_command(char command,Stack switch(command),5/27/2023,数据结构与程序设计,29,链接队列和栈的综合应用Main,case?:p.read();if(stored_polynomials.push(p)=overflow)cout Warning:Stack full,lost polynomial endl;break;case=:if(stored_polynomials.empty()cout Stack empty endl;else stored_polynomials.top(p);p.print();break;,5/27/2023,数据结构与程序设计,30,链接队列和栈的综合应用Main,case+:if(stored_polynomials.empty()cout Stack empty endl;else stored_polynomials.top(p);stored_polynomials.pop();if(stored_polynomials.empty()cout Stack has just one polynomial endl;stored_polynomials.push(p);else stored_polynomials.top(q);stored_polynomials.pop();r.equals_sum(q,p);if(stored_polynomials.push(r)=overflow)cout Warning:Stack full,lost polynomial endl;break;,5/27/2023,数据结构与程序设计,31,链接队列和栈的综合应用Main,case q:cout Calculation finished.endl;return false;return true;,5/27/2023,数据结构与程序设计,32,链接队列和栈的综合应用Main,char get_command()char command;bool waiting=true;cout:;while(waiting)cin command;command=tolower(command);if(command=?|command=|command=+|command=q)waiting=false;else cout Please enter a valid command:endl?Read a Polynomial endl=Return Top Polynomial endl+Sum two Polynomial endl q Quit.endl;return command;,5/27/2023,数据结构与程序设计,33,上机作业,实现polynomial补充功能P151 P2P151 P3,