Microsoft PowerPoint - DS_Ch3_EN [兼容模式]

Transcription

1 Data Structure Ch.3 Stacks & Queues Dr. He Emil Huang School of Computer Science and Technology Soochow University 苏州大学计算机科学与技术学院网络工程系 本章 ppt 与教材对应情况 本章涉及所有内容涵盖了 Kruse 教材以下章节 Chapter 2 ( 栈,Introduction to Stacks) Chapter 3 ( 队列,Queues) Chapter 4 ( 链栈和链队列,Linked Stacks & Queues) huangh@suda.edu.cn Subsection 1 栈 _ 引言 3.0 Stack Specification ( 栈的说明 ) 由下面这个问题引入 Now, let us consider one open issue (Page 50) Read an integer n, then read a list of n numbers, and print the list in reverse order. Solution 1: Use an array ( 使用数组 ). Occupying part of an array of fixed size, with some of the entries in the array remaining unused. 3 #include <iostream> using namespace std; int main( ) /* Pre: The user supplies an integer n and n decimal numbers. Post: The numbers are printed in reverse order.*/ int n; double item; double numbers[ 25n ]; cout << " Type in an integer n followed by n decimal numbers." << endl<< " The numbers will be printed in reverse order." << endl; cin >> n; for (int i = 0; i < n; i++) cin >> item; numbers[i]=item; cout << endl << endl; for ( i = n-1; i >=0; i--) cout << numbers[i]; cout << endl; NOTE: 很多学生会认识到需要一个数组, 但有些学生会试图建立一个长度为 n 的数组, 然后会被提示的错误信息所困扰 因为他企图利用一个变量而不是常量作为数组的长度 The difference between list and array ( 表和数组的区别 ) 1 The length of a list can be changed by insert or delete some items from the list, but the length of an array is an constant. 表的长度是可变的 即表中的数字是可以增加和删除的, 因此, 如果 n=3, 那么表中只有 3 个数字, 如果 n=19, 那么表中就有 19 个数字 ; 数组 ( 或称为向量 ), 具体编程时的术语 数组中的元素个数是个常量, 也即当程序被编译时, 数组的长度就确定了 2 List is a dynamic data structure, but array is an static data structure. 表是一个动态数据结构, 因为它的长度是可以变化的, 然而, 数组是一种静态数据结构, 因为它的长度是固定的 3 List is a logical concept and array is a programming feature. 表是一个逻辑层面的概念, 数组是编程实现时的概念 1

2 The relation between list and array A list of variable size can be implemented in a computer by occupying part of an array with fixed size, andsomeofthe entries in the array are kept unused. 长度可变的表在计算机中的实现可以用一个定长数组实现, 其中定长数组中的部分单元未使用 But we will find that there are several ways to implement lists, using an array is only one of them, we should not confuse the fundamental data structure with the choice of implementations. 然而, 我们以后会发现, 有很多种方法可以用来完成表的实现, 因此我们不能将实现方法的选择和基本的数据结构相混淆 Standard Template Library (STL, P52) The standard template library (abbreviated STL) in C++ contains much useful information, many functions, and many classes. The STL provides convenient implementations for many common data structures (including almost all the data structures we shall study in this book). We can include the STL stack implementation into our programs with the directive #include <stack> and then we can define initially empty stack objects and apply methods called push, pop, top, and empty. 我们可以直接使用 STL 栈定义的方法, 如 push, pop, etc. Standard Template Library (STL, P52) In C++, a template construction allows us to create data structures whose entries have different types. Example: stack<double> numbers and stack<int> numbers The STL provides several implementations of various data structures such as stacks.( 提供各种数据结构的多种实现手段 ) The code in a client program should not depend on a particular choice of implementation, but the performance of the final program may very much depend on the choice of implementation. ( 客户程序中的代码不依赖于所用类的具体实现, 但程序的性能受栈的具体实现手段的影响 ) A second, optional template parameter selects the implementation. To stack the default implementation comes from deque. (double-ended queue) The STL implementations are highly efficient, convenient and designed with enough default options to allow programmers to use them easily. ( 高效 方便 很多可选项 ) Solution 2: by using a stack #include <stack>; //include the STL stack implementation into our program using namespace std; int main( ) /* Pre: The user supplies an integer n and n decimal numbers. Post: The numbers are printed in reverse order. Uses: The STL class stack and its methods */ int n; double item; stack <double> numbers; // declares and initializes a stack of numbers cout << " Type in an integer n followed by n decimal numbers." << endl << " The numbers will be printed in reverse order." << endl; cin >> n; for (int i = 0; i < n; i++) cin >> item; numbers.push(item); C++ STL 标准模板类库提供了一个 stack 类可以实现栈的功能 cout << endl << endl; while (!numbers.empty( )) cout << numbers.top( ) << " "; numbers.pop( ); cout << endl; // 请参考 C++ STL 中 stack 类, 也可参考 msdn 或相关书籍 Information Hiding ( 信息隐藏, P54) Information hiding: The methods for handling stacks are implemented in the C++ standard library, and we can use them without needing to know the details of how stacks are kept in memory or of how the stack operations are actually done. One important difference between practicing information hiding with regard to arrays and practicing information hiding with regard to stacks: C++ provides just one built-in implementation of arrays, but the STL has several implementations of stacks. Information Hiding Advantage of information hiding ( 信息隐藏的优点 ) If the instructions for manipulating a stack have been written out every time a stack is used, then every occurrence of these instructions will need to be changed. If we have practiced information hiding by using separate functions for manipulating stacks, then only the declarations will need to be changed. ( 用方法封装栈的操作, 当栈的实现改变时, 修改更容易 ) ---change of implementation Another advantage of information hiding shows up in programs that use stacks where the very appearance of the words push and pop immediately alert a person reading the program to what is being done, whereas the instructions themselves might be more obscure. --- clarity of program We shall find that separating the use of data structures from their implementation will help us improve the top-down design of both our data structures and our programs. ---top-down design 2

3 Example and sketch map ( 示意图 ) Page 51 in Our Text Book Page 44 in 严蔚敏老师的教材 3.1 Stack Definition & Operations Stack All insertions and deletions of entries are made at one end of the list. Insert Push Delete Pop Top of the stack the end for insertions and deletions 栈顶 Bottom of the stack the other end 栈底 修改原则 : 退栈者总是最近入栈者 服务原则 : last in first out (LIFO) e.g.: Push Pop a n a 2 a Stack Pushing and Popping a stack Logical Structure Specification: A stack is a list in which all insertions and deletions of entries are made at one end, called the top of the stack( 栈顶 ). The last entry inserted is the first one that will be removed ( 后进先出 ). Empty stack means the stack has no item. Example: plates sitting on the counter in a busy cafeteria. Customers take trays off the top of stack. Employees returned trays back on top of the stack. Other examples Methods Push( 入栈 ) Pop( 出栈 ) Empty( 判空 ) Top( 取栈顶元素 ) Size Constructor Pushing and Popping a stack 3.1 Stack Note: The last item pushed into a stack is always the first that will be popped from the stack. 但不排除后者未进栈, 先入栈者先出栈 an,, a, a

4 3.1 Stack Implementation of Stack ( 栈的实现 ) Suppose we have five items which were pushed into a stack in turn, the order of the push is abcde, and the pop turn is dceba, please decide the minimum size of the stack. 假设有 5 个元素 abcde 顺序进栈 ( 进栈过程中可以出栈 ), 出栈序列为 dceba, 则该栈容量必定不小于多少? Stack Specification of Methods for Stacks constructor--- initialization( 构造函数 --- 初始化, P58) The constructor is a function with the same name as the corresponding class and no return type. It is invoked automatically whenever an object of the class is declared. Specification of Methods for Stacks Entry Types, Generics( 泛型, P58) For generality, we use Stack_entry for the type of entries in a Stack. A client can specify this type with a definition such as typedef int Stack_entry; or typedef char Stack_entry; The ability to use the same underlying data structure and operations for different entry types is called generics ( 对不同的元素类型使用同样的基本数据结构和操作的能力称为泛型 ). typedef provides simple generics. Specification of Methods for Stacks Error Processing ( 出错处理, P58) We shall use a single enumerated type ( 枚举类型 ) called Error_code to report errors from all of our programs and functions. The enumerated type Error_code is part of the utility package in Appendix C. Stacks use three values of an Error_code: success, overflow, underflow Later, we shall use several further values of an Error_code. 程序设计规则 Determine the methods and their specifications for the Stack class, similar as the STL stack class: pop push top empty Specification of Methods for Stacks Specification for Methods( 方法的定义 ) Error_code Stack :: push(const Stack_entry &item); pre: None. post: If the Stack is not full, item is added to the top of the Stack. If the Stack is full, an Error_code of overflow( 上溢 )is returned and the Stack is left unchanged. Error_code Stack :: pop( ); pre: None. post: If the Stack is not empty, the top of the Stack is removed. If the Stack is empty, an Error_code of underflow( 下溢 )is returned and the Stack is left unchanged. 4

5 Specification of Methods for Stacks Specification for Methods( 方法的定义 ) Error_code Stack :: top(stack_entry &item) const; precondition: None. postcondition: The top of a nonempty Stack is copied to item. A code of fail is returned if the Stack is empty. 以下内容为顺序栈介绍 Sequential Stack bool Stack :: empty( ) const; precondition: None. postcondition: A result of true is returned if the Stack is empty, otherwise false is returned Sequential Stack ( 顺序栈, 顺序存储结构 ) Bottom is relatively fixed Sequential Stack ( 顺序栈 ) The bottom can be set at either end of an array ( 栈底可以约定在数组的任意一端, 一般用下标为 0 一端做栈底 ) Use position number as pointer of top ( 用数组下标表示栈顶位置 ) Declaration:(C-version) #define StackSize 100 typedef struct DataType data[stacksize]; int top; // 栈顶指针, 随 push, pop 改变 SeqStack; // 顺序栈的结构定义 27 Note:top pointer reflects position number relative to the bottom. top 指针不是指物理地址, 与指针变量含义不同 可理解为相对地址, 是指示元素的所在位置 Sequential Stack If the bottom is at the low end of the array, i.e. data[0], then: Push:top+1 Pop:top-1 Empty:top<0 Full:top=StackSize-1 Overflow:Push an item when the stack is full Underflow:Pop an item when the stack is empty ( 不一定是错误, 可以作为控制转移条件 ) Sequential Stack Implementation in C version: Initialize a stack operation: 初始化置空栈 void InitStack(SeqStack *S) S->top=-1; Is a stack empty: 判定一个栈 S 是否为空 int StackEmpty(SeqStack *S) return S->top == -1; Is a stack full: 判定一个栈 S 是否为满 int StackFull (SeqStack *S) return S->top==StackSize-1; 30 5

6 3.1.1 Sequential Stack Push operation: 入栈操作 void Push(SeqStack *S, DataType x) if ( StackFull(S) ) Error( overflow );// 上溢, 退出运行 S->data[++S->top]=x; // 指针先加 1, 后 x 入栈 Pop operation: 出栈操作 DataType Pop(SeqStack *S) if ( StackEmpty(S) ) Error( UnderFlow ); // 下溢 return S->data[S->top--]; // 返回栈顶后指针减 Sequential Stack Stack Class definition in C++ version: 顺序栈的类定义 #include < > #include<stack.h> class SeqStack : public Stack<T> // 顺序栈类定义 private: T *elements; // 存放栈元素的栈数组 int top; // 栈顶指针, int 型 int maxsize; void overflowprocess(); // 栈最大容量 Top operation: 读栈顶 // 栈的溢出处理 Sequential Stack public: SeqStack(int sz =50); // 构造函数, 建立空栈 ~SeqStack() delete [] elements; // 析构函数 void Push(const T& x); // 进栈, 将元素 x 插入到栈顶 bool Pop(T& x); \\ 栈顶元素出栈,pop 出的元素值通过引用型参数 x 返回栈顶元素值 bool gettop(t& x); // 取栈顶内容 bool IsEmpty ( ) const return top == -1; bool IsFull ( ) const return top == maxsize-1; 33 ; Sequential Stack Implementation in C++: void SeqStack<T>::Push(const T& x) // 若栈不满, 则将元素 x 插入该栈栈顶, 否则溢出处理 if (IsFull( ) == true) overflowprocess( ); // 栈满 elements[++top] = x; // 栈顶指针先加 1, 再进栈 ; bool SeqStack<T>::Pop(T& x) // 函数退出栈顶元素并返回栈顶元素的值 if (IsEmpty( ) == true) return false; x = elements[top--]; // 栈顶指针退 1 return true; // 退栈成功 ; Sequential Stack Implementation in C++ bool Seqstack<T>::getTop(T& x) // 若栈不空则函数返回该栈栈顶元素的地址 if (IsEmpty( ) == true) return false; x = elements[top]; return true; ; 以下 6 页 PPT 涉及内容均为 text book 上的 stack 类 ( 顺序栈 ) 定义及方法说明 35 6

7 The Class Specification (SeqStack 类的定义 ) We set up an array to hold the entries in the stack and a counter to indicate how many entries there are. const int maxstack = 10; // small value for testing class Stack public: Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(stack_entry &item) const; Error_code push(const Stack_entry &item); private: int count; //to indicate how may entries in the sequential stack Stack_entry entry[maxstack]; ; Pushing, Popping, and Other Methods We note that the data member count represents the number of items in a Stack. Therefore, the top of a Stack occupies entry[count - 1], as shown in Figure 2.4. Pushing, Popping, and Other Methods Error_code Stack :: push(const Stack_entry &item) /* Pre: None. Post: If the Stack is not full, item is added to the top of the Stack. If the Stack is full, an Error_code of overflow is returned and the Stack is left unchanged. */ Error_code outcome = success; if (count >= maxstack) outcome = overflow; else entry[count++] = item; return outcome; Pushing, Popping, and Other Methods Error_code Stack :: pop( ) //only remove the top of the stack /* Pre: None. Post: If the Stack is not empty, the top of the Stack is removed. If the Stack is empty, an Error_code of underflow is returned. */ Error_code outcome = success; if (count == 0) outcome = underflow; else --count; return outcome; Pushing, Popping, and Other Methods Error_code Stack :: top(stack_entry &item) const /* Pre: None. Post: If the Stack is not empty, the top of the Stack is returned in item. If the Stack is empty an Error_code of underflow is returned. */ Error_code outcome = success; if (count == 0) outcome = underflow; else item = entry[count - 1]; return outcome; Pushing, Popping, and Other Methods bool Stack :: empty( ) const /* Pre: None. Post: If the Stack is empty, true is returned. Otherwise false is returned. */ bool outcome = true; if (count > 0) outcome = false; return outcome; Stack :: Stack( ) /* Pre: None. Post: The stack is initialized to be empty. */ count = 0; 7

8 以下内容为链栈 (Linked Stack) 介绍 在我们介绍 Linked Stack 之前 请对应我们的 textbook, 再次复习一些有关链式存储结构的基础知识 (P114-P126) 43 POINTERS AND LINKED STRUCTURES Diagram Conventions Variable contain pointers In the diagram, the object Dave is lost, with no pointer referring to it, and therefore there is no way to find it. In such a situation, we shall say that the object has become garbage. Therefore, in our work, we shall always strive to avoid the creation of garbage by ensuring no object is lost. POINTERS AND LINKED STRUCTURES Linked Structures The idea of a linked list is to augment every element of a list structure with a pointer giving the location of the next element in the list. 小心谨慎使用指针, 避免对象丢失, 避免 垃圾 产生 Analogies to a linked list 关于链表的类比 1. The game of Children s treasure hunt. 2. friends passing a popular cassette. 3. following instructions where each instruction is given out only upon completion of the previous task. There is then no inherent limit on the number of tasks to be done, since each task may specify a new instruction, and there is no way to tell in advance how many instructions there are. Analogies to a contiguous list 关于顺序表的类比 1. list of instructions written on a single sheet of paper. It is then possible to see all the instructions in advance, but there is a limit to the number of instructions that can be written on the single sheet of paper. The Basics of Linked Structures Nodes and Type Declarations The only difference between a struct and a class is that, unless modified by the keywords private and public, members of a struct are public whereas members of a class are private. Thus, by using modifiers public and private to adjust the visibility of members, we can implement any structure as either a struct or a class. struct Node // data members Node_entry entry; Node *next; //use before definition // constructors Node( ); Node(Node_entry item, Node *pointer = NULL); ; 8

9 The Basics of Linked Structures The Basics of Linked Structures Node Constructors Node :: Node( ) next = NULL; The second form accepts two parameters for initializing the data members. Node :: Node(Node_entry item, Node *pointer) entry = item; next = pointer; The Basics of Linked Structures For example, the following code will produce the linked nodes illustrated in Figure 4.8. Node first_node( a ); // Node first_node stores data a. Node *p0 = &first_node; // p0 points to first_node. Node *p1 = new Node( b ); // A second node storing b is created. p0->next = p1; // The second Node is linked after first_node. Node *p2 = new Node( c, p0); // A third Node storing c is created. // The third Node links back to the first node, *p0. p1->next = p2; // The third Node is linked after the second Node Linked Stack ( 链栈 ) Top pointer of stack could be used as head pointer, since all operations are performed at top of stack. Declaration typedef struct snode DataType data; struct snode *next; StackNode; // 链栈结点定义 typedef struct StackNode *top; LinkStack; // 链栈定义 Dynamic Memory Allocation, free of overflow ( 链栈动态分配结点, 无需考虑上溢 ) 链栈 void InitStack(LinkStack *S) S->top=NULL; int StackEmpty (LinkStack *S) return S->top==NULL; void Push(LinkStack *S, DataType x) StackNode *p=(stacknode*) malloc (sizeof(stacknode)); p->data=x; p->next=s->top; S->top=p; 链栈 DataType Pop(LinkStack *S) DataType x; StackNode *p=s->top; // 保存栈顶指针 if ( StackEmpty(S) ) Error ( underflow ); // 下溢 x=p->data; // 保存栈顶数据 S->top=p->next; // 将栈顶结点从链头摘下 free(p); // 释放原栈顶结点空间 return x;

10 3.1.1 Linked Stack Class definition in C++ struct StackNode // 栈结点类定义 private: T data; // 栈结点数据 StackNode<T> *link; // 结点链指针 public: StackNode(T d = 0, StackNode<T> *next = NULL) : data(d), link(next) // 构造函数, 初始化列表, 效率更高 ; class LinkedStack : public Stack<T> // 链式栈类定义 private: StackNode<T> *top; Linked Stack public: LinkedStack( ) : top(null) // 构造函数 ~LinkedStack( ) makeempty( ); // 析构函数 void Push(const T& x); // 进栈 bool Pop(T& x); // 退栈 bool gettop(t& x) const; // 取栈顶 bool IsEmpty( ) const return top == NULL; int getsize( ) const; // 求栈的元素个数 void makeempty( ); // 清空栈的内容 friend ostream& operator << (ostream& os, LinkedStack<T>& s); // 输出栈元素的重载操作 << ; Linked Stack Implementation in C++ LinkedStack<T> :: makeempty() // 逐次删去链式栈中的元素直至栈顶指针为空 StackNode<T> *p; while (top!= NULL) // 逐个结点释放 p = top; top = top->link; delete p; ; void LinkedStack<T> :: Push(const T& x) // 将元素值 x 插入到链式栈的栈顶, 即链头 top = new StackNode<T> (x, top); // 创建新结点 assert (top!= NULL); // 创建失败退出 Linked Stack bool LinkedStack<T>::Pop(T& x) // 删除栈顶结点, 返回被删栈顶元素的值 if (IsEmpty() == true) return false; // 栈空返回 StackNode<T> *p = top; // 暂存栈顶元素 top = top->link; // 退栈顶指针 x = p->data; delete p; // 释放结点 return true; ; bool LinkedStack<T>::getTop(T& x) const if (IsEmpty( ) == true) return false; // 栈空返回 x = top->data; // 返回栈顶元素的值 return true; ; ; Linked Stack ostream& operator<<(ostream& os, LinkedStack<T>& s) // 输出栈中所有元素的重载操作 << os<< 栈中元素个数 <<s.getsize( )<<endl; // 输出栈元素个数 LinkNode<T> *p =S.top; // 逐个输出栈元素的值 int i=0; while(p!=null) os<<++i<< : <<p->data<<endl; p=p->link; return os; ; Linked Stacks( 链栈 ) Whether the beginning or the end of the linked structure will be the top of the stack? The only information needed to keep track of the data in a linked stack is the location of its top

11 Linked Stacks declaration of type Stack class Stack public: Stack( ); bool empty( ) const; Error_code push(const Stack_entry &item); Error_code pop( ); Error_code top(stack_entry &item) const; protected: Node *top_node; ; Linked Stacks pushing a linked stack ( 入栈 ) Empty stack( 空栈 ) Linked Stacks Let us start with an empty stack, which now means top_node == NULL, and consider how to add Stack_entry item as the first entry. We must create a new Node storing a copy of item, in dynamic memory. We shall access this Node with a pointer variable new_top. We must then copy the address stored in new_top to the Stack member top_node. Hence, pushing item onto the Stack consists of the Instructions Node *new_top = new Node(item); top_node = new_top; Notice that the constructor that creates the Node *new_top sets its next pointer to the default value NULL. Not empty Node *new_top = new Node(item, top_node); top_node = new_top; pushing a linked stack( 入栈 ) Linked Stacks Error_code Stack :: push(const Stack_entry &item) /* Post: Stack_entry item is added to the top of the Stack; returns success or returns a code of overflow if dynamic memory is exhausted. */ Node *new_top = new Node(item, top_node); if (new_top == NULL) return overflow; top_node = new_top; return success; popping a linked stack( 出栈 ) Linked Stacks Error_code Stack :: pop( ) /* Post: The top of the Stack is removed. If the Stack is empty the method returns underflow; otherwise it returns success. */ Node *old_top=top_node; if (top_node==null) return underflow; top_node=top_node->next; delete old_top; return success; LINKED STACKS WITH SAFEGUARDS 带保护的链栈 (P131-P137) Problem Example for (int i = 0; i < ; i++) Stack small; small.push(some_data); As soon as the object small goes out of scope, the data stored in small becomes garbage. Over the course of a million iterations of the loop, a lot of garbage will accumulate. 11

12 The Destructor The C++ language provides class methods known as destructors that solve our problem. For every class, a destructor is a special method that is executed on objects of the class immediately before they go out of scope. 对于每一个类来说, 析构函数是一个特殊的方法, 在类对象超出范围前立即执行 LINKED STACKS WITH SAFEGUARDS Stack :: ~ Stack( ) // Destructor /* Post: The Stack is cleared. */ while (!empty( )) pop( ); Stack :: ~Stack( ); LINKED STACKS WITH SAFEGUARDS Stack outer_stack; //outer_stack 对象 for (int i = 0; i < ; i++) Stack inner_stack; //inner_stack 对象 inner_stack.push(some_data); inner_stack = outer_stack; Misbehaviors: Lost data space. Two stacks have shared nodes. The destructor on inner stack deletes outer stack. Such a deletion leaves the pointer outer_stack.top_ node addressing what a random memory location. LINKED STACKS WITH SAFEGUARDS Overloading the Assignment Operator 重载赋值操作 void Stack :: operator = (const Stack &original) // Overload assignment /* Post: The Stack is reset as a copy of Stack original. */ Node *new_top, *new_copy, *original_node = original.top_node; if (original_node == NULL) new_top = NULL; else // Duplicate the linked nodes new_copy = new_top = new Node(original_node->entry); while (original_node->next!= NULL) original_node = original_node->next; new_copy->next = new Node(original_node->entry); new_copy = new_copy->next; while (!empty( )) // Clean out old Stack entries pop( ); top_node = new_top; // and replace them with new entries. LINKED STACKS WITH SAFEGUARDS The Copy Constructor ( 拷贝构造函数 ) Problem example: void destroy_the_stack (Stack copy) In this code, a copy of the Stack vital_data is passed to the function. The Stack copy shares int main( ) its nodes with the Stack vital data, and therefore when a Stack Stack vital_data; destructor is applied to copy, at the end of the function, vital_data is also destroyed. destroy_the_stack (vital_data); 12

13 LINKED STACKS WITH SAFEGUARDS Copy constructor Implementation outline: 1. Deal with the case of copying an empty Stack. 2. Copy the first node. 3. Run a loop to copy all of the other nodes. The Modified Linked-Stack Specification class Stack public:// Standard Stack methods Stack( ); bool empty( ) const; Error_code push(const Stack_entry &item); Error_code pop( ); Error_code top(stack_entry &item) const; // Safety features for linked structures ~Stack( ); Stack(const Stack &original); void operator = (const Stack &original); protected: Node *top_node; ; 3.2 Queue 队列 (Queue) Basic Concepts 1. Definitions Queue:A list in which all insert operations are made at one end, and all deletions are made at other end. Features ( 同样是一种运算受限的线性表 ) First in, First out (a.k.a FIFO List) Applications:queues of tasks for printer OS 中虚拟内存一种页替换算法 Operations ( 入队列 出队列, etc.) Append (Enqueue): Serve (Dequeue): Queue Operations ( 队列的基本操作 ) As in our treatment of stacks, we shall implement queues whose entries have a generic type, which we call Queue_entry. Queue :: Queue( ); postcondition: The Queue has been created and is initialized to be empty. Queue Operations ( 队列的基本操作 ) Error_code Queue :: append(const Queue_entry &x); postcondition: If there is space, x is added to the Queue as its rear. Otherwise an Error_code of overflow is returned. Error_code Queue :: serve( ); postcondition: If the Queue is not empty, the front of the Queue has been removed. Otherwise an Error_code of underflow is returned. 13

14 Queue Operations ( 队列的基本操作 ) Error_code Queue :: retrieve(queue_entry &x) const; postcondition: If the Queue is not empty, the front of the Queue has been recorded as x. Otherwise an Error_code of underflow is returned. ( 取队头元素 ) bool Queue :: empty( ) const; postcondition: Return true if the Queue is empty, otherwise return false. Queue Operations ( 队列的基本操作 ) class Queue Add x to rear public: or overflow Remove front Queue( ); Record push front as x or underflow pop bool empty( ) const; or underflow front Error_code append(const Queue_entry &x); Error_code serve( ); Error_code retrieve(queue_entry &x) const; // Additional members will represent queue data. ; Extended Queue Operations Extended Queue Operations: full clear size serve_and_retrieve class Queue methods: Queue (constructor) append serve retrieve empty data members Base class 基类 inheritance class Extended_Queue methods: Extended_queue (constructor) append serve retrieve empty full clear Derived class size serve_and_retrieve 派生类 data members additional data members Extended Queue Operations class Extended_queue: public Queue public: bool full( ) const; int size( ) const; void clear( ); Error_code serve_and_retrieve(queue_entry &item); ; Extended Queue Operations The new operations for our class Extended_queue have the following specifications. bool Extended_queue :: full( ) const; postcondition: Return true if the Extended_queue is full; return false otherwise. void Extended_queue :: clear( ); postcondition: All entries in the Extended_queue have been removed; it is now empty. Extended Queue Operations int Extended_queue :: size( ) const; postcondition: Return the number of entries in the Extended_queue. Error_code Extended_queue :: serve_and_retrieve(queue_entry &item); postcondition: Return underflow if the Extended_queue is empty. Otherwise remove and copy the item at the front of the Extended_queue to item and return success. 14

15 Extended Queue Operations The relationship between the class Extended_queue and the class Queue is often called an is-a relationship. This is because every Extended_queue object is a Queue object with other features namely, the methods serve_and_retrieve, full, size, and clear. Every A is a B Every A has a B 3.2 Queue Implementations Of Queues Contiguous implementation ( 对应课本 chapter 3) 1. The physical model implementation 2. Linear implementation 3. Circular array implementation Linked implementation class A is derived from class B class A has a data member of type B Contiguous implementation 顺序队列 ( 循环队列 ) 介绍 The basic way is the same. We create a queue in memory by setting up an array to hold the entries. To facilitate the operations, we must keep track of the front and the rear of the queue. 基本方法是相同的, 我们使用一个数组来存放队列中的元素, 为了方便操作, 需要保存队列中的队头和队尾位置 87 To keep the front of the queue always in the first location of the array? An entry can be appended to the queue simply by increasing the rear by one and putting the entry in that location. ( 入队时元素添加到最后, 队尾指示器增 1) To remove an entry from the queue, however, would be very expensive indeed. ( 出队时队列中所有元素都向前移动一个位置 ) rear rear front Not a practical way! 1 15

16 3.2 Queue 2. Queue Contiguous Implementation Empty queue:front = rear; Append:insert an element at rear of the queue, then rear++; Serve:delete the front element from the queue, then front++; Contiguous Implementation ( 队列的顺序实现 ) To append an entry to the queue, we simply increase the rear by one and put the entry in that position. To serve an entry, we take it from the position at the front and then increase the front by one. Front pointer points to the head element Rear pointer points to the next position of the last element Job 1 Job 2 Job 3 Job 4 Job 5 Job 6 append Job 1 append Job 2 append Job 3 serve Job 1 append Job 4 append Job 5 append Job 6 serve Job 2 append Job Queue Overflow:Append when the queue is full Underflow:Serve when the queue is empty 伪上溢 : 队非满但不能插入 原因 :f,r 只增不减例如 : 入, 出, 入, 出, 尽管任一时刻, 队中最多只有 1 个元素, 但无论事先定义多大的空间, 均会产生指针越界 Problem: not true overflow ( 假溢出 )happens Fault: discarded space ( 空间无故被丢弃 ) This method has a major defect ( 缺点 ): Both the front and rear indices are increased but never decreased. As the queue moves down the array, the storage space at the beginning of the array is discarded ( 丢弃 ) and never used again. Advantage: for applications where the queue is regularly emptied, then at a time when the queue is empty, the front and rear can both be reset to the beginning of the array, and the simple scheme of using two indices and straight-line storage becomes a very efficient implementation. Inefficient use of space 93 Circular Array( 循环队列 P85~P87) Job 71 Job 2 Job 3 Job 4 Job 5 Job 6 In concept, we can overcome the inefficient use of append Job 7 space simply by thinking of the array as a circle rather than a straight line. Now we need not worry about running out of space unless the array is fully occupied, in which case we truly have overflow. 除非队列真的已满, 否则可以消除假溢出问题 下标计算发生了什么变化? [ 0 ] Job7 [ 5 ] Job6 Job5 [ 4 ] [ 1 ] Job3 [ 2 ] Job4 [ 3 ] 16

17 3.2 Queue 怎样消除伪上溢? 重复利用已删除的结点空间, 将向量视为首尾相接的环 这种用循环向量实现的队列称为循环队列 f,r 在循环意义下的加 1 动作 : 越界时, 令其指向下界 0 i = (i+1==queuesize)? 0:i++; // i 为 front 或 rear 可用模运算简化 : i=(i+1)%queuesize; Circular Arrays 实用顺序队列多为循环队列 Queue Boundary Conditions (P88, possible solution) The front and rear indices are in the same relative positions for an empty queue and for a full queue. 1 Set a boolean flag 2 Leave one empty position 3 Set a counter to record the size Declaration #define QueueSize 100 typedef struct int front; int rear; int count; DataType data [QueueSize]; CirQueue; Queue Implementation Initialize/Clear void InitQueue (CirQueue *Q) Q->front = Q->rear = 0; Q->count = 0; // 队空 Is Empty int QueueEmpty (CirQueue *Q) return Q->count == 0; Is Full int QueueFull (CirQueue *Q) return Q->count ==QueueSize; Queue Append (Enqueue) void EnQueue (CirQueue *Q, DataType x) if (QueueFull (Q) ) Error( overflow ); // 上溢 Q->count++; Q->data [Q->rear] = x; // 插入 Q->rear = (Q->rear+1)%QueueSize; // 尾指针加 1 Serve (Dequeue) 与课本中的 Serve and Retrieve 相同 DataType DeQueue (CirQueue *Q) if (QueueEmpty (Q) ) Error ( underflow ); // 下溢, 不一定是错 temp = Q->data[Q->front]; Q->count--; Q->front= (Q->front+1)%QueueSize; // 头指针加 1 return temp; Queue (Circular Array) Implementation in C++ CirQueue<T>::CirQueue(int sz) : front(0), rear(0), maxsize(sz) // 构造函数 elements = new E[maxSize]; assert ( elements!= NULL ); ; bool CirQueue<T>::EnQueue(const T& x) // 若队列不满, 则将 x 插入到该队列队尾, 否则返回 if (IsFull( ) == true) return false; elements[rear] = x; // 先存入 rear = (rear+1) % maxsize; // 尾指针加一 return true; 3.2 Queue bool CirQueue<T>::DeQueue(T& x) // 若队列不空则函数退队头元素并返回其值 if (IsEmpty( ) == true) return false; x = elements[front]; // 先取队头 front = (front+1) % maxsize; // 再队头指针加一 return true; ; bool CirQueue<T>::getFront(T& x) const // 若队列不空则函数返回该队列队头元素的值 if (IsEmpty() == true) return false; // 队列空 x = elements[front]; // 返回队头元素 return true; ; ;

18 IMPLEMENTATIONS OF QUEUES 课本对应的关于循环队列的实现内容供同学们自学 (P84-P91) 请所有同学注意 : 课本中对空队列的初始设置与严蔚敏等国内教材有差别, 请加以区分, 但本质思想相同 Boundary Conditions ( 边界条件 ) 初值设置 rear = maxqueue - 1; front = 0; 存在问题 : 如何区别队空和队满? rear 指向哪?front 指向哪 CIRCULAR IMPLEMENTATION OF QUEUES IN C++ ( 循环队列实现 ) The implementation in a circular array which uses a counter to keep track of the number of entries in the queue both illustrates techniques for handling circular arrays and simplifies the programming of some of the extended-queue operations. We shall take the queue as stored in an array indexed with the range 0 to (maxqueue - 1) CIRCULAR IMPLEMENTATION OF QUEUES IN C++ const int maxqueue = 10; // small value for testing class Queue public: Queue( ); bool empty( ) const; Error_code serve( ); Error_code append(const Queue_entry &item); Error_code retrieve(queue_entry &item) const; protected: int count; int front, rear; Queue_entry entry[maxqueue]; ; CIRCULAR IMPLEMENTATION OF QUEUES IN C++ CIRCULAR IMPLEMENTATION OF QUEUES IN C++ Queue :: Queue( ) /* Post: The Queue is initialized to be empty. */ count = 0; rear = maxqueue - 1; front = 0; bool Queue :: empty( ) const /* Post: Return true if the Queue is empty, otherwise return false. */ return count == 0; Error_code Queue :: append(const Queue_entry &item) /* Post: item is added to the rear of the Queue. If the Queue is full return an Error_code of overflow and leave the Queue unchanged. */ if (count >= maxqueue) return overflow; count++; rear = ((rear + 1) == maxqueue)? 0 : (rear + 1); entry[rear] = item; return success; 18

19 CIRCULAR IMPLEMENTATION OF QUEUES IN C++ Error_code Queue :: serve( ) /* Post: The front of the Queue is removed. If the Queue is empty return an Error_code of underflow. */ if (count <= 0) return underflow; count--; front = ((front + 1) == maxqueue)? 0 : (front + 1); return success; CIRCULAR IMPLEMENTATION OF QUEUES IN C++ Error_code Queue :: retrieve(queue_entry &item) const /* Post: The front of the Queue retrieved to the output parameter item. If the Queue is empty return an Error_code of underflow. */ if (count <= 0) return underflow; item = entry[front]; return success; int Extended_queue :: size( ) const /* Post: Return the number of entries in the Extended_queue. */ return count; APPLICATION OF QUEUES: SIMULATION Introduction Simulation is the use of one system to imitate the behavior of another system. Simulations are often used when it would be too expensive or dangerous to experiment with the real system. 仿真是指用一个系统模拟另一个系统的行为 经常使用于实际系统比较昂贵或危险的情形 Such as: wind tunnel flight simulators computer simulation: uses the steps of a program to imitate the behavior of the system under study. 3.2 Queue 链队列 (Linked Queue) 3. Linked Queue typedef struct qnode DataType data; struct qnode *next; QNode; typedef struct QNode *front; QNode *rear; LinkQueue; LinkQueue *Q; a1 不带头节点 : an

20 void InitQueue (LinkQueue *Q) Q->front = Q->rear = NULL; // 若有头结点则不同 int QEmpty (LinkQueue *Q) // 无上溢, 故不判满队 return Q->front == NULL; // 头尾指针均为空, 有头结点时 f = r void EnQueue (LinkQueue *Q, DataType x) QNode *p = (QNode *) malloc (sizeof(qnode) ); p->data = x; p->next = NULL; // 新结点作为新的队尾 if ( QEmpty(Q) ) // 若有头结点无需判此项 Q->front = Q->rear = p; // *p 插入空队 else // 插入非空队尾, 有无头结点均要做此项 Q->rear->next = p; // *p 链到原尾结点之后 Q->rear = p; // 指向新尾 *p 3.Linked Queue DataType DeQueue (LinkQueue *Q) if ( QEmpty(Q) ) Error ( underflow ); // 下溢 p = Q->front; // 指向队头 x = p->data; Q->front = p->next; // 队头摘下 if (Q->rear == p) // 原队中只有一个结点, 删去后队变空 Q->rear = NULL; free (p) ; return x; Queue (Linked Queue) Declarations in C++ struct QueueNode // 队列结点类定义 private: T data; // 队列结点数据 QueueNode<T> *link; // 结点链指针 public: QueueNode(T d = 0, QueueNode<T> *next = NULL) : data(d), link(next) ; class LinkedQueue private: QueueNode<T> *front, *rear; // 队头 队尾指针 Queue (Linked Queue) public: LinkedQueue() : rear(null), front(null) ~LinkedQueue(); bool EnQueue(const T& x); bool DeQueue(T& x); bool GetFront(T& x) const; // 查看队头元素的值 void MakeEmpty(); // 实现与 ~Queue() 同 bool IsEmpty() const return front == NULL; friend ostream& operator<<(ostream& os, LinkedQueue<T>& Q) // 输出队列中元素的重载操作 ; Queue (Linked Queue) Implementation in C++ LinkedQueue<T>::~LinkedQueue() // 析构函数 QueueNode<T> *p; while (front!= NULL) // 逐个结点释放 p = front; front = front->link; delete p; ; bool LinkedQueue<T>::EnQueue(const T& x) // 将新元素 x 插入到队列的队尾 3.2 Queue (Linked Queue) if (front == NULL) // 创建第一个结点 front = rear = new QueueNode<T> (x); if (front == NULL) return false; // 分配失败 else // 队列不空, 插入 rear->link = new QueueNode<T> (x); if (rear->link == NULL) return false; rear = rear->link; return true; ; // 如果队列不空, 将队头结点从链式队列中删去

21 3.2 Queue (Linked Queue) bool LinkedQueue<T>::DeQueue(T& x) if (IsEmpty( ) == true) return false; // 判队空 QueueNode<T> *p = front; x = front->data; front = front->link; delete p; return true; ; LINKED QUEUES ( 链队列 ) bool LinkedQueue<T>::GetFront(T& x) const // 若队列不空, 则函数返回队头元素的值 if (IsEmpty( ) == true) return false; x = front->data; return true; ; 121 LINKED QUEUES( 链队列 ) Basic Declarations class Queue public: // standard Queue methods Queue( ); bool empty( ) const; Error_code append(const Queue_entry &item); Error_code serve( ); Error_code retrieve(queue_entry &item) const; // safety features for linked structures ~Queue( ); Queue(const Queue &original); void operator = (const Queue &original); protected: Node *front, *rear; ; LINKED QUEUES Initialize( 初始化 ) Queue :: Queue( ) /* Post: The Queue is initialized to be empty. */ front = rear = NULL; Append( 入队 ) LINKED QUEUES Error_code Queue :: append(const Queue_entry &item) /* Post: Add item to the rear of the Queue and return a code of success or return a code of overflow if dynamic memory is exhausted. */ Node *new_rear = new Node(item); if (new_rear == NULL) return overflow; if (rear == NULL) front = rear = new_rear; else rear->next = new_rear; rear = new_rear; return success; Serve( 出队 ) LINKED QUEUES Error_code Queue :: serve( ) /* Post: The front of the Queue is removed. If the Queue is empty, return an Error_code of underflow. */ if (front == NULL) return underflow; Node *old_front = front; front = old_front->next; if (front == NULL) rear = NULL; delete old_front; return success; 21

22 LINKED QUEUES Extended Linked Queues class Extended_queue: public Queue public: bool full( ) const; int size( ) const; void clear( ); Error_code serve_and_retrieve(queue_entry &item); ; 以下内容为栈的应用介绍 There is no need to supply explicit methods for the copy constructor, the overloaded assignment operator, or the destructor, since the compiler calls the corresponding method of the base Queue object. 128 Application: A Desk Calculator (P66) Reverse Polish Calculator( 逆波兰计算器 ) In a Reverse Polish calculator, the operands (numbers, usually) are entered before an operation (like addition, subtraction, multiplication, or division) is specified. (a * (b - c)) + d --> a b c - * d + The advantage of a reverse Polish calculator is that any expression, no matter how complicated, can be specified without the use of parentheses. ( 括号 ) Infix Expression Postfix Expression Application: A Desk Calculator Reverse Polish Calculator( 逆波兰计算器 ) We shall write? to denote an instruction to read an operand; +, -, *, and / represent arithmetic operations; and = is an instruction to print the value just got. Eg1: we write a, b, c, and d to denote numerical values such as 3.14 or -7. The instructions? a? b + = mean read and store the numbers a and b, calculate and store their sum, and then print the sum. Eg2: The instructions? a? b +? c? d + * = request four numerical operands, and the result printed is the value of (a + b) * (c + d). Eg3: the instructions? a? b? c - = *? d + = mean read the numbers a, b, c, calculate b - c and print its value, then calculate a * (b - c), read d, and finally calculate and print (a * (b - c)) + d. 依次输入 :?1?2+?3*= 后, 显示计算结果 9 算法思想 : 程序从键盘接受命令符?1?2+?3*= 如输入的命令为? 则继续读入一个操作数, 由于对该操作数执行的运算符还未知, 所以暂时将它存储起来 ; 如输入的是 +, -, *, / 等运算符则此时应将最近保存过的数拿出两个作算术运算, 并将运算的中间结果存储起来 由于最近存储的操作数 ( 或是最近存储的中间结果 ) 是即将拿出来作运算的操作数, 也即后存储的先取出来, 即满足 后进先出 的原则, 因此, 应把这些操作数存储在栈中 如输入的命令为 = 将刚才的运算结果即栈顶元素输出 22

23 ? denote an instruction to read an operand and push it onto (onto 很形象 ) the stack; +, -, *, and / represent arithmetic operations; When an operation is performed, it pops its operands from the stack and pushes its result back onto the stack. = is an instruction to print the value. Application: A Desk Calculator typedef double Stack_entry; #include Stack.h" int main( ) /* Post: The program has executed simple arithmetic commands entered by the user. Uses: The class Stack and the functions introduction, instructions, do_command,and get_command. */ Stack stored_numbers; introduction( ); instructions( ); while (do_command(get_command( ), stored_numbers)); The auxiliary function get_command obtains a command from the user, checking that it is valid and converting it to lowercase by using the string function tolower( ) that is declared in the standard header file cctype. Application: A Desk Calculator char get_command( ) char command; bool waiting = true; cout << "Select command and press < Enter > :"; while (waiting) cin >> command; command = tolower(command); if (command ==? command == '=' command == '+' command == '-' command == '*' command == '/' command == 'q') waiting = false; else cout << "Please enter a valid command:" << endl<< "[?]push to stack [=]print top" <<endl<< "[+] [-] [*] [/] are arithmetic operations" << endl<< "[Q]uit." << endl; //endwhile return command; Application: A Desk Calculator bool do_command(char command, Stack &numbers) /* Pre: The first parameter specifies a valid calculator command. Post: The command specified by the first parameter has been applied to the Stack of numbers given by the second parameter. A result of true is returned unless command == ' q '. Uses: The class Stack. */ double p, q; switch (command) case '?': // read cout << "Enter a real number: " << flush; cin >> p; if (numbers.push(p) == overflow) cout << "Warning: Stack full, lost number" << endl; break; case '=': // print if (numbers.top(p) == underflow) cout << "Stack empty" << endl; else cout << p << endl; break; Application: A Desk Calculator case '+': if (numbers.top(p) == underflow) cout << "Stack empty" << endl; else numbers.pop( ); if (numbers.top(q) == underflow) cout << "Stack has just one entry" << endl; numbers.push(p); else numbers.pop( ); if (numbers.push(q + p) == overflow) cout << "Warning: Stack full, lost result" << endl; break; // Add options for further user commands. Application: A Desk Calculator case 'q': cout << "Calculation finished.\n"; return false; return true; In calling this function, we must pass the Stack parameter by reference, because its value might need to be modified. For example, if the command parameter is +, then we normally pop two values off the Stack numbers and push their sum back onto it: This should certainly change the Stack. The function do_command allows for an additional user command, q, that quits the program. 23

24 数据转换 问题 : 一非负十进制整数 N 基为 B 的 B 进制数 例 : 规律 : (3.1) 其中 bi 表示 B 进制数的第 i 位数字十进制数 N 可用长度为位 B 进制数表示为 栈的应用 如何确定? 令, 则 (3.1) 式为 : (3.2) (3.2) 式整除 B, 则余数为, 商为括号内的和式 故 (3.2) 式 可表达为 : // / 为整除 算法思想 : 1 模除求余数 : 2 整除求商 :N/B, 令此为新的 N, 重复 1 求, 反复至某 N 为 0 时结束 上述过程依次求出的 B 进制各位为 ( 从低位至高位 ): 用栈保存, 退栈输出 即为所求 栈的应用 例如 : 141 实现 typedef int DataType; void MultiBaseOutput (int N, int B) // N 为非负十进制整数, B 为基 int i; SeqStack * S; // 顺序栈 S InitStack( S ); // 置空栈 while (N) // 从右向左产生 b i, i=0,1,, j Push( S, N%B); // 将 b i 入栈 N=N/B; while(!stackempty(s) ) // 栈 S 非空 i = Pop(S); printf( %d,i); 时间复杂度 :O(log B N ) 142 APPLICATION: POLYNOMIAL ARITHMETIC ( 多项式运算, Section 4.5 in our textbook, P141) 以下内容为队列应用介绍 We develop a program that simulates a calculator that does addition, subtraction, multiplication, division, and other operations for polynomials rather than numbers. We model a reverse Polish calculator whose operands (polynomials) are entered before the operation is specified. The operands are pushed onto a stack. When an operation is performed, it pops its operands from the stack and pushes its result back onto the stack. We reuse the conventions of Section 2.3:? denotes pushing an operand onto the stack, +, -, *, / represent arithmetic operations, and = means printing the top of the stack (but not popping it off)

25 APPLICATION: POLYNOMIAL ARITHMETIC The Main Program int 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; introduction( ); instructions( ); while (do_command(get_command( ), stored_polynomials)); APPLICATION: POLYNOMIAL ARITHMETIC Polynomial Methods As in Section 2.3, we represent the commands that a user can type by the characters?, =, +, -, *, /, where? requests input of a polynomial from the user, = prints the result of an operation, and the remaining symbols denote addition, subtraction, multiplication, and division, respectively. Most of these commands will need to invoke Polynomial class methods; hence we must now decide on the form of some of these methods. APPLICATION: POLYNOMIAL ARITHMETIC We will need a method to add a pair of polynomials. One convenient way to implement this method is as a method, equals_sum, of the Polynomial class. Thus, if p, q, r are Polynomial objects, the expression p.equals_sum(q, r) replaces p by the sum of the polynomials q and r. We shall implement similar methods called equals_difference, equals_product, and equals_quotient to perform other arithmetic operations on polynomials. The user commands = and? will lead us to call on Polynomial methods to print out and read in polynomials. Thus we shall suppose that Polynomial objects have methods without parameters called print and read to accomplish these tasks. APPLICATION: POLYNOMIAL ARITHMETIC Performing Commands bool do_command(char command, Stack & stored_polynomials) /* Pre: The first parameter specifies a valid calculator command. Post: The command specified by the first parameter has been applied to the Stack of Polynomial objects given by the second parameter. A result of true is returned unless command == q. Uses: The classes Stack and Polynomial. */ Polynomial p, q, r; APPLICATION: POLYNOMIAL ARITHMETIC switch (command) 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; APPLICATION: POLYNOMIAL ARITHMETIC case + : if (stored_polynomials.empty( )) cout << "Stack empty" << endl; else stored_polynomials.top(p); //get the first operand to be added stored_polynomials.pop( ); if (stored_polynomials.empty( )) cout << "Stack has just one polynomial" << endl; stored_polynomials.push(p); else stored_polynomials.top(q); //get the second operand to be added stored_polynomials.pop( ); break; r.equals_sum(q, p); //do command r=q+p; if (stored_polynomials.push(r) == overflow) //push r back to the stack cout << "Warning: Stack full, lost polynomial" << endl; 25

26 APPLICATION: POLYNOMIAL ARITHMETIC // Add options for further user commands. case q : cout << "Calculation finished." << endl; return false; //end switch return true; 一元多项式 p n n 1 2 n( x) pnx pn 1 x... p2x p1x p0 We can represent it as a list : P = (p n, p n-1,,p 0 ) But if we have a polynomial like: S(x) = 2x x Does the representation reasonable? Determine the polynomial implementation: a contiguous or a linked queue? Should we use a contiguous or a linked queue? If, in advance, we know a bound on the degree of the polynomials that can occur and if the polynomials that occur have nonzero coefficients in almost all their possible terms, then we should probably do better with contiguous queues. But if we do not know a bound on the degree, or if polynomials with only a few nonzero terms are likely to appear, then we shall find linked storage preferable. Let us in fact decide to represent a polynomial as an extended linked queue of terms. 事先不知道多项式的长度, 多项式指数不连续, 建议采用链式结构 Any Sparse Polynomial: P n (x) = p m x e m + pi x e i + + p 1 x e 1 + p 0 x e 0 其中 :p i 是指数为 e i 的项的非零系数, 0 e 0 < e 1 < < e m = n 可以下列线性表表示 : ((p m,e m ) (p 1, e 1 ), (p 0, e 0 )) example: P 999 (x) = - 8x 999-2x 12 +7x 3 Can be represented by a list : ((-8, 999), (-2, 12), (7, 3) ) The Polynomial Data Structure We implement a Term as a struct with a constructor as following. struct Term int degree; double coefficient; Term (int exponent = 0, double scalar = 0); ; Term :: 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; 26

27 Determine the polynomial data structure: a stack? A queue or a general list? Consider the sum operation that applies to the polynomial A(x) = 5x x 8 +3x+7 B(x) = -9x x 7 +8x C (x) = A(x)+B(x) = 5x x 7 +11x +7 A polynomial is represented as a list of terms. We must then build into our methods rules for performing arithmetic on two such lists. When we do this work, however, we find that we continually need to remove the first entry from the list, and we find that we need to insert new entries only at the end of the list. In other words, we find that the arithmetic operations treat the list as a queue, or, more precisely, as an extended queue, since we frequently need methods such as clear and serve_and_retrieve, as well as deletion from the front and insertion at the rear. 1. Each node represents one term of a polynomial and is a structure containing a coefficient, an exponent, and a pointer to the next term of the polynomial. 2. The terms of every polynomial are stored in the order of decreasing exponent within the linked queue, and no two terms have the same exponent. 3. Terms with zero coefficient are not stored in the polynomial. 4. The polynomial that is identically 0 is represented by an empty queue. The Polynomial Data Structure class Polynomial: private Extended_queue // Use private inheritance. public: void read( ); void print( ) const; void equals_sum(polynomial p, Polynomial q); void equals_difference(polynomial p, Polynomial q); void equals_product(polynomial p, Polynomial q); Error_code equals_quotient(polynomial p, Polynomial q); int degree( ) const;// 最高次项的指数 private: void mult_term(polynomial p, Term t); ; Reading and Writing Polynomials print Polynomial void Polynomial :: print( ) const /* Post: The Polynomial is printed to cout. */ Node *print_node = front; bool first_term = true; while (print_node!= NULL) Term &print_term = print_node->entry; 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 << " + "; 27

28 Reading and Writing Polynomials double r = (print_term.coefficient >= 0)// r is abs of the coefficient? 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"; // Print 0 for an empty Polynomial. cout << endl; Reading and Writing Polynomials read Polynomial void Polynomial :: read( ) /* Post: The Polynomial is read from cin. */ clear( ); double coefficient; int last_exponent, exponent; bool first_term = true; cout << "Enter the coefficients and exponents for the polynomial, " << "one pair per line. Exponents must be in descending order." << endl << "Enter a coefficient of 0 or an exponent of 0 to terminate." << endl; do cout << "coefficient? " << flush; cin >> coefficient; if (coefficient!= 0.0) cout << "exponent? " << flush; cin >> exponent; Reading and Writing Polynomials if ((!first_term && exponent >= last_exponent) exponent < 0) exponent = 0; cout << "Bad exponent: Polynomial terminates without its last term."<< endl; //the input is invalid! else Term new_term(exponent, coefficient); append(new_term); first_term = false; last_exponent = exponent; while (coefficient!= 0.0 && exponent!= 0); Addition of Polynomials( 多项式相加 ) A(x) = 5x x 8 +3x+7 B(x) = -9x x 7 +8x C (x) = A(x)+B(x) = 5x x 7 +11x +7 A B void Polynomial :: equals_sum(polynomial p, Polynomial q) /* Post: The Polynomial object is reset as the sum of the two parameters. */ 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); Addition of Polynomials ( 多项式相加 ) 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); 28