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

链接队列和栈的综合应用—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);}}}}链接队列和栈的综合应用—LinkStacktypedefPolynomialNode_entry;structNode{//datamembersNode_entryentry;Node*next;//constructorsNode();Node(constNode_entryitem,Node*add_on=0);};数据结构与程序设计数据结构与程序设计数据结构与程序设计数据结构与程序设计思路：队列的第一个点的系数单独输出，第一项前不需要有加号。然后输出剩余点的系数，处理系数为1时的特殊情况。输出X和指数：处理指数为1，常数项的情况。处理一般的情况。必须要按照指数从大到小的顺序产生整个队列。//返回队列头部的指数。将p，q求和，其结果存放到当前的队列栈中的一个元素就是一个队列*数据结构与程序设计*数据结构与程序设计(10)王丽苹应用：多项式求解*数据结构与程序设计*后序波兰式的求解abc-d*如果a，b，c为整数如何求解。如果a，b，c为多项式如何求解。AH=7x14+2x8+-10x6+1BH=4x18+8x14-3x10+10x6-x4多项式及其相加在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。优点是：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。链接队列和栈的综合应用12多项式链表的相加AH=7x14+2x8+-10x6+1BH=4x18+8x14-3x10+10x6-x471428-106110^418814-310106-14^4181514-31028-14110^AH.firstBH.firstCH.first链接队列和栈的综合应用*数据结构与程序设计*目录Polynomial下例程链接队列和栈的综合应用*数据结构与程序设计*top_nodePolynomialnextPolynomialnextclassStack{protected:Node*top_node;};structNode{Polynomialentry;Node*next;};链接队列和栈的综合应用*数据结构与程序设计*PolynomialTermnextTermnextclassQueue{protected:SmallNode*front,*rear;};