《数据结构与程序设计 多项式的例子》由会员分享，可在线阅读，更多相关《数据结构与程序设计 多项式的例子（32页珍藏版）》请在金锄头文库上搜索。
1、7/26/2024数据结构与程序设计 1应用：多项式求解n后序波兰式的求解后序波兰式的求解nabc- d*n(1) 如果如果a，b，c为整数如何求解。为整数如何求解。n(2) 如果如果a，b，c为多项式如何求解。为多项式如何求解。AH = 7x14 + 2x8 + - 10x6 + 1 BH = 4x18 + 8x14 - 3x10 + 10x6 - x47/26/2024数据结构与程序设计 2n n多项式及其相加n n在多项式的链表表示中每个结点增加了在多项式的链表表示中每个结点增加了一个数据成员一个数据成员link，作为链接指针。，作为链接指针。n n优点是：优点是：n n 多项式的项数可
2、以动态地增长，不存在多项式的项数可以动态地增长，不存在存储溢出问题。存储溢出问题。n n 插入、删除方便，不移动元素。插入、删除方便，不移动元素。链接队列和栈的综合应用7/26/2024数据结构与程序设计 3多项式链表的相加多项式链表的相加AH = 7x14 + 2x8 + - 10x6 + 1 BH = 4x18 + 8x14 - 3x10 + 10x6 - x47 142 8-10 61 10 4 188 14-3 1010 6-1 4 4 1815 14-3 102 8-1 4 1 10 AH.firstBH.firstCH.first7/26/2024数据结构与程序设计 4链接队列和栈
3、的综合应用n目录Polynomial下例程7/26/2024数据结构与程序设计 5链接队列和栈的综合应用ntop_nodePolynomialnextPolynomialnextclass Stackprotected: Node *top_node;struct Node Polynomial entry; Node *next;7/26/2024数据结构与程序设计 6链接队列和栈的综合应用nPolynomialTerm nextTerm nextclass Queue protected: SmallNode *front, *rear;class SmallNode public: Te
4、rm entry; SmallNode *next;Term nextfrontrear7/26/2024数据结构与程序设计 7链接队列和栈的综合应用nclass Term npublic:n int degree;n double coefficient;n;degreecoefficientEg: 3x2degree=2coefficient=37/26/2024数据结构与程序设计 8链接队列和栈的综合应用-Termnclass Term npublic:n Term (int exponent = 0, double scalar = 0);n int degree;n double c
5、oefficient;n;7/26/2024数据结构与程序设计 9链接队列和栈的综合应用-Termn#includeTerm.hnTerm:Term(int exponent, double scalar)n/*nPost: The Term is initialized with the given coefficient and exponent, or with default parameter values of 0.n*/nn degree = exponent;n coefficient = scalar;n7/26/2024数据结构与程序设计 10链接队列和栈的综合应用-Pol
6、ynomialntypedef Term Queue_entry;ntypedef Term SmallNode_entry;nclass SmallNode n/ data membersnpublic:nSmallNode_entry entry;nSmallNode *next;n/ constructorsnSmallNode();nSmallNode(SmallNode_entry item, SmallNode *add_on = 0);n;7/26/2024数据结构与程序设计 11链接队列和栈的综合应用-Polynomialnclass Queue npublic:n/ stan
7、dard Queue methodsnQueue();nbool empty() const;nError_code append(const Queue_entry &item);nError_code serve();nError_code retrieve(Queue_entry &item) const;n/ safety features for linked structuresnQueue();nprotected:nSmallNode *front, *rear;n;/Queue表示一个多项式7/26/2024数据结构与程序设计 12链接队列和栈的综合应用-Polynomial
8、nclass Extended_queue: public Queue npublic:n int size() const;n void clear();n Error_code serve_and_retrieve(Queue_entry &item);n;7/26/2024数据结构与程序设计 13链接队列和栈的综合应用-Polynomialnclass Polynomial: private Extended_queue n/ Use private inheritance.npublic:n Polynomial();n Polynomial:Polynomial(const Poly
9、nomial &original);n void operator=(const Polynomial &original);n void read();n void print() const;n void equals_sum(Polynomial p, Polynomial q);n int degree() const;n; /用用Polynomial来封装Queue， Polynomial表示一个多项式表示一个多项式7/26/2024数据结构与程序设计 14链接队列和栈的综合应用-PolynomialnPolynomial:Polynomial()n front=NULL;n rea
10、r=NULL; n7/26/2024数据结构与程序设计 15链接队列和栈的综合应用-PolynomialnPolynomial:Polynomial(const Polynomial &original)nn SmallNode *new_front, *new_copy, *original_front = original.front, *new_rear;n if (original_front = NULL) n n new_front=NULL;n new_rear=NULL;n n else / Duplicate the linked nodesn new_copy = new_
11、front= new SmallNode(original_front-entry);n while (original_front-next != 0) n n original_front = original_front-next;n new_copy-next = new SmallNode(original_front-entry);n new_copy = new_copy-next;n n new_rear=new_copy;n n front= new_front;n rear=new_rear;n7/26/2024数据结构与程序设计 16Linked Queues-Queue
12、 original_frontnew_front new_copynew_front new_copy7/26/2024数据结构与程序设计 17链接队列和栈的综合应用-Polynomialnvoid Polynomial:operator =(const Polynomial &original)nn SmallNode *new_front, *new_copy, *original_front = original.front, *new_rear;n if (original_front = NULL) n n new_front=NULL;n new_rear=NULL;n n els
13、e / Duplicate the linked nodesn new_copy = new_front= new SmallNode(original_front-entry);n while (original_front-next != 0) n n original_front = original_front-next;n new_copy-next = new SmallNode(original_front-entry);n new_copy = new_copy-next;n n new_rear=new_copy;n n while (!empty() / Clean out
14、 old Queue entriesn serve();n front= new_front;n rear=new_rear;n7/26/2024数据结构与程序设计 18链接队列和栈的综合应用Polynomialp147void Polynomial:print() const/*Post: The Polynomial is printed to cout.*/ SmallNode *print_node = front; bool first_term = true; while (print_node != NULL) Term &print_term =print_node-entry
15、; if (first_term) / In this case, suppress printing an initial +. first_term = false; if (print_term.coefficient 0) cout - ; else if (print_term.coefficient 0) cout - ; else cout = 0) ? print_term.coefficient : -(print_term.coefficient); if (r != 1) cout 1) cout X print_term.degree; if (print_term.d
16、egree = 1) cout X; if (r = 1 & print_term.degree = 0) cout next; if (first_term) cout 0; / Print 0 for an empty Polynomial. cout endl;7/26/2024数据结构与程序设计 19Linked Queues-Queue print_node7/26/2024数据结构与程序设计 20链接队列和栈的综合应用Polynomialp148nvoid Polynomial:read()nn clear();n double coefficient;n int last_exp
17、onent, exponent;n bool first_term = true;n cout Enter the coefficients and exponents for the polynomial,one pair per line. endln Exponents must be in descending order. endln Enter a coefficient of 0 or an exponent of 0 to terminate. endl;n do n cout coefficient? coefficient;n if (coefficient != 0.0)
18、 n cout exponent? exponent;n if (!first_term & exponent = last_exponent) | exponent 0) n exponent = 0;n cout Bad exponent: Polynomial terminates without its last term.n q.degree() n p.serve_and_retrieve(p_term);n append(p_term);n n else if (q.degree() p.degree() n q.serve_and_retrieve(q_term);n appe
19、nd(q_term);n n else n p.serve_and_retrieve(p_term);n q.serve_and_retrieve(q_term);n if (p_term.coefficient + q_term.coefficient != 0) n Term answer_term(p_term.degree,n p_term.coefficient + q_term.coefficient);n append(answer_term);n n n n7/26/2024数据结构与程序设计 23链接队列和栈的综合应用Link Stackntypedef Polynomial
20、 Node_entry;nstruct Node n/ data membersn Node_entry entry;n Node *next;n/ constructorsn Node();n Node(const Node_entry item, Node *add_on = 0);n;7/26/2024数据结构与程序设计 24链接队列和栈的综合应用Link Stacknclass Stacknpublic:n/ Standard Stack methodsn Stack();n bool empty() const;n Error_code push(const Node_entry &
21、item);n Error_code pop();n Error_code top(Node_entry &item) const;n/ Safety features for linked structuresn Stack();nprotected:n Node *top_node;n;7/26/2024数据结构与程序设计 25链接队列和栈的综合应用Mainnvoid main()n/*nPost: The program has executed simple polynomial arithmeticn commands entered by the user.nUses: The c
22、lasses Stack and Polynomial and the functionsn introduction, instructions, do_command, and get_command.n*/nn Stack stored_polynomials;n void introduction();n void instructions();n bool do_command(char command, Stack &stored_polynomials);n char get_command();n char tolower(char command);n introductio
23、n();n instructions();n while (do_command(get_command(), stored_polynomials);n7/26/2024数据结构与程序设计 26链接队列和栈的综合应用Mainnvoid introduction()nn coutThis is a polynomials program.endl;nnvoid instructions()nn cout Please enter a valid command: endln ? Read a Polynomial endln = Return Top Polynomial endln + Su
24、m two Polynomial endln q Quit. endl;n7/26/2024数据结构与程序设计 27链接队列和栈的综合应用Mainp143nbool do_command(char command, Stack &stored_polynomials)n/*nPre: The first parameter specifies a valid calculator command.nPost: The command specified by the first parametern has been applied to the Stack of Polynomialn ob
25、jects given by the second parameter.n A result of true is returned unless command = q.nUses: The classes Stack and Polynomial.n*/nn Polynomial p, q, r;n n switch (command) n 7/26/2024数据结构与程序设计 28链接队列和栈的综合应用Mainn case ?:n p.read();n if (stored_polynomials.push(p) = overflow)n cout Warning: Stack full
26、, lost polynomial endl;n break;n case =:n if (stored_polynomials.empty()n cout Stack empty endl;n else n stored_polynomials.top(p);n p.print();n n break;7/26/2024数据结构与程序设计 29链接队列和栈的综合应用Mainn case +:n if (stored_polynomials.empty()n cout Stack empty endl;n else n stored_polynomials.top(p);n stored_po
27、lynomials.pop();n if (stored_polynomials.empty() n cout Stack has just one polynomial endl;n stored_polynomials.push(p);n n else n stored_polynomials.top(q);n stored_polynomials.pop();n r.equals_sum(q, p);n if (stored_polynomials.push(r) = overflow)n cout Warning: Stack full, lost polynomial endl;n
28、n n break;7/26/2024数据结构与程序设计 30链接队列和栈的综合应用Mainn case q:n cout Calculation finished. endl;n return false;n n return true;n7/26/2024数据结构与程序设计 31链接队列和栈的综合应用Mainnchar get_command()nn char command;n bool waiting = true;n cout Select command and press :;n while (waiting) n cin command;n command = tolower(
29、command);n if (command = ? | command = = |n command = + | command = q ) waiting = false;n else n cout Please enter a valid command: endln ? Read a Polynomial endln = Return Top Polynomial endln + Sum two Polynomial endln q Quit. endl;n n n return command;n7/26/2024数据结构与程序设计 32上机作业n实现实现polynomialn补充功能补充功能nP151 P2nP151 P3
