2008级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 prototype for a Stack destructor is: Stack: -Stack() Policy: Every linked structure should be equipped with a destructor to clear its objects before they go out of scope 4.3.2 Dangers in Assignment P133 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. Overloading the assignment operator C++, we implement special methods, known as overloaded assignment operators to rede effect of assignment. Whenever the C++ compiler translates an assignment expression of the form=y, it first checks whether the class of x has an overloaded assignment operator. Prototype id Stack:: operator =(const Stack &original ); This declares a Stack method called operator = the overloaded assignment operator, that can be invoked with x operator=(y); or x=y; By looking at the type(s) of its operands, the C++ compiler can tell that it should use the overloaded operator rather than the usual assignment Implementation outline: P 134 Make a copy of the data stacked in the calling parameter. Clear out any data already in the Stack object being as- signed to Move the newly copied data to the Stack object Overloaded Assignment of linked Stacks P134 4.3.3 The Copy Constructor P135 Problem example P135 Solution p135 Implementation outline: P135 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 Linked-stack copy constructor: P136 Policy: For every linked class, include a copy constructor, or warn clients that objects are copied with reference semantics 4.3.4 Modified Linked-Stack Specification P136 4.4]Linked Queues P137 4.4.1 Class declaration, linked queues: P138 Constructor Linked Queue Methods Append an entry: P138 Serve an entry: P139 4.4.2 Extended Linked Queues P139 Class definition: P139 Size: P140 [ 4.5Application: Polynomial Arithmetic P141 4.5.1P.141 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 cal culator 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, +,-,*,2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 prototype for a Stack destructor is: Stack :: ~Stack( ); Policy: Every linked structure should be equipped with a destructor to clear its objects before they go out of scope. 4.3.2 Dangers in Assignment P.133 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. Overloading the Assignment Operator In C++, we implement special methods, known as overloaded assignment operators to redefine the effect of assignment. Whenever the C++ compiler translates an assignment expression of the form x = y, it first checks whether the class of x has an overloaded assignment operator. Prototype: void Stack : : operator = (const Stack &original); This declares a Stack method called operator = , the overloaded assignment operator, that can be invoked with x.operator = (y); or x = y; By looking at the type(s) of its operands, the C++ compiler can tell that it should use the overloaded operator rather than the usual assignment. Implementation outline: P.134 ⚫ Make a copy of the data stacked in the calling parameter. ⚫ Clear out any data already in the Stack object being as- signed to. ⚫ Move the newly copied data to the Stack object. Overloaded Assignment of Linked Stacks P.134 4.3.3 The Copy Constructor P.135 Problem example P.135 Solution P.135 Implementation outline: P.135 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. Linked-stack copy constructor: P.136 Policy: For every linked class, include a copy constructor, or warn clients that objects are copied with reference semantics. 4.3.4 Modified Linked-Stack Specification P.136 [4.4] Linked Queues P.137 4.4.1 Class declaration, linked queues: P.138 Constructor: P.138 Linked Queue Methods Append an entry: P.138 Serve an entry: P.139 4.4.2 Extended Linked Queues P.139 Class definition: P.139 Size: P.140 [4.5] Application: Polynomial Arithmetic P.141 4.5.1 P.141 ⚫ 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, + , −, * , /