2008级计算机专业数据结构课 内部资料,仅供课堂教学使用 Chapter 4 LINKED STACKS AND QUEUES P49 1. Pointers and Linked Structures 4. Linked Queues 2. Linked Stacks 5. Application: Polynomial Arithmetic 3. Linked Stacks with Safeguards 6. Abstract Data Types and Implementations [4. 1] Pointers and Linked Structures Pointers and a linked list P114 4.1.1 Key terms Overflow: Running out of space. P113 Pointer: An object, often a variable, that stores the location( that is the machine address) of some other object, typically of a structure containing data that we wish to manipulate. Also sometimes called a link rence) P 1 13 Linked list: A list in which each entry contains a pointer giving the location of the next entry. P 1 14 Contiguous: Next to each other, touching, adjoining; used in contrast to linked. P. 15 e Automatic object: An object that exists as long as the block of program declaring it is active; referenced by giving it a name when writing the program. P 116 Dynamic object: An object that is created (and perhaps destroyed) while the program is running accessed indirectly via pointers. P1 16 4.1.2 Pointers in C++ Notation: C++ uses an asterisk* to denote a pointer. If Item is a type, then a pointer to such an Item object has the type Item *. For example, Item *item ptr; declares item ptr as a pointer variable to an Item object. P116 Creating dynamic objects: item ptr new Item; creates a new dynamic object of type Item and assigns its location to the pointer variable item ptr. The dynamic objects that we create are kept in an area of computer memory called the free store (or the heap). P 117 Deleting dynamic objects: delete item ptr; disposes of the dynamic object to which item ptr points and returns the space it occupies to the free store so it can be used again. After this delete statement is executed, the pointer variable item ptr is undefined and so should not be used until it is assigned a new value. P117 Following pointers: "item ptr denotes the object to which item ptr points. The action of taking *item ptr is called"dereferencing the pointer *item ptr. P 117-118 NULL pointers: If a pointer variable item ptr has no dynamic object to which it currently refers, then it should be given the special value item ptr= NULL, In diagrams we reserve the electrical ground symbol for NULL pointers. The value NULL is used as a constant for all pointer types and is generic in that the same value can be assigned to a variable of any pointer type. P 1 19 Undefined pointers versus NULL pointers: item ptr -NULL means that item ptr currently points to no dynamic object. If the value of item ptr is undefined, then item ptr might point to any random P.I19 Programming Precept: Uninitialized or random pointer objects should always be reset to NULL. After deletion, a pointer object should be reset to NULL. P 119 Dynamically Allocated Arrays: The declaration item array new Item [array size]; creates a dynamic array of Item objects, indexed from O up to array size- 1. Consider, for example int size, *dynamic array, i cout size dynamic array new int[size for (i=0; i< size; i ++ dynamic array[i=i r value and p is a pointer to an Item, then p+i is an expression of type Item * The value of p+i gives the memory address offset from p by iltem objects. That is, the expression p+i actually yields the address p+nxi where n is the number of bytes of storage occupied by a simple object of type Item Addresses of automatic objects: If x is a variable of type Item, then &x is a value of type Item that
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 4 LINKED STACKS AND QUEUES P.49 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. Pointers and Linked Structures 2. Linked Stacks 3. Linked Stacks with Safeguards 4. Linked Queues 5. Application: Polynomial Arithmetic 6. Abstract Data Types and Implementations [4.1] Pointers and Linked Structures Pointers and a Linked List P.114 4.1.1 Key Terms ⚫ Overflow: Running out of space. P.113 ⚫ Pointer: An object, often a variable, that stores the location (that is the machine address) of some other object, typically of a structure containing data that we wish to manipulate. (Also sometimes called a link or a reference) P.113 ⚫ Linked list: A list in which each entry contains a pointer giving the location of the next entry. P.114 ⚫ Contiguous: Next to each other, touching, adjoining; used in contrast to linked. P.115 ⚫ Automatic object: An object that exists as long as the block of program declaring it is active; referenced by giving it a name when writing the program. P.116 ⚫ Dynamic object: An object that is created (and perhaps destroyed) while the program is running; accessed indirectly via pointers. P.116 4.1.2 Pointers in C++ ⚫ Notation: C++ uses an asterisk * to denote a pointer. If Item is a type, then a pointer to such an Item object has the type Item *. For example, Item *item_ptr; declares item_ptr as a pointer variable to an Item object. P.116 ⚫ Creating dynamic objects: item_ptr = new Item; creates a new dynamic object of type Item and assigns its location to the pointer variable item_ptr. The dynamic objects that we create are kept in an area of computer memory called the free store (or the heap). P.117 ⚫ Deleting dynamic objects: delete item_ptr; disposes of the dynamic object to which item ptr points and returns the space it occupies to the free store so it can be used again. After this delete statement is executed, the pointer variable item_ptr is undefined and so should not be used until it is assigned a new value. P.117 ⚫ Following pointers: *item_ptr denotes the object to which item_ptr points. The action of taking *item_ptr is called “dereferencing the pointer *item_ptr.” P.117-118 ⚫ NULL pointers: If a pointer variable item_ptr has no dynamic object to which it currently refers, then it should be given the special value item_ptr = NULL; In diagrams we reserve the electrical ground symbol for NULL pointers. The value NULL is used as a constant for all pointer types and is generic in that the same value can be assigned to a variable of any pointer type. P.119 ⚫ Undefined pointers versus NULL pointers: item_ptr ==NULL means that item_ptr currently points to no dynamic object. If the value of item_ptr is undefined, then item_ptr might point to any random location in memory. P.119 Programming Precept: Uninitialized or random pointer objects should always be reset to NULL. After deletion, a pointer object should be reset to NULL. P.119 ⚫ Dynamically Allocated Arrays: The declaration item_array = new Item[array_size]; creates a dynamic array of Item objects, indexed from 0 up to array_size − 1. Consider, for example: int size, *dynamic array, i; cout > size; dynamic array = new int[size]; for (i = 0; i < size; i ++) dynamic_array[i] = i; The statement delete [ ]dynamic_array; returns the storage in dynamic_array to the free store. If i is an integer value and p is a pointer to an Item, then p+i is an expression of type Item *. The value of p+i gives the memory address offset from p by i Item objects. That is, the expression p+i actually yields the address p+n×i , where n is the number of bytes of storage occupied by a simple object of type Item. P.119-120 ⚫ Addresses of automatic objects: If x is a variable of type Item, then &x is a value of type Item* that
2008级计算机 教学笔记 内部资料,仅供课堂教学使用 gives the address of x In this case, a declaration and assignment such as Item *ptr =&x would establish a pointer, ptr, to the object x. P 121-122 e Address of an array: The address of the initial element of an array is found by using the arrays nam without any attached 0 operators. For example, given a declaration Item x[20] the assignment Item*ptr ce x sets up a pointer ptr to the initial element of the array x Observe that an assignm ent expression ptr (xlOn could also be used to find this address. P 121-122 Pointers to structures: If p is a pointer to a structure object that has a data member called the data, then we could access this data member with the expression(p). the data, but C++ provides the operator->as a shorthand, so we can replace the expression (*p).the data by the equivalent, but more convenient expression p->the data. P 122 4.1.3 The Basics of linked structures A linked structure is made up of nodes, each containing both the information that is to be stored as an entry of the structure and a pointer telling where to find the next node in the structure. We shall refer to these nodes making up a linked structure as the nodes of the structure, and the pointers we often call links. Since the link in each node tells where to find the next node of the structure. we shall use the name next to designate this link We shall use a struct rather than a class to implement nodes. P 123 Node constructors P125 [4.2]Linked Stacks P 127 Class Declaration for Linked Stack P128 Benefits of Class Implementation P128 Maintain encapsulation: If we do not use a class to contain our stack, we lose the ability to set up methods for the stack Maintain the logical distinction between the stack itself, made up of all of its entries(each in a node), and the top of the stack, which is a pointer to a single node Maint ain consi stency with other data structures and other implementations, where structures are needed to collect several methods and pieces of information. e Help with debugging by allowing the compiler to perform better type checking Pushing a linked Stack P129 Popping a linked Stack P130 [ 4.3Linked Stacks with Safeguards P131 Client code can apply the methods of linked stacks in ways that lead to the accumulation of gar bage or that break the encapsulation of Stack objects. C++ provides three devices(additional class methods)to alleviate these problems destructors copy constructors, overloaded assignment operators These new methods replace compiler generated default behavior and are often called silently(that is, without explicit action by a client) 4.3.1 Problem Example P131 for(inti=0,i<1000000;i++){ Stack small all push( some data) Suppose that the linked Stack implementation is used. 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 where all allocated space for member data is released every time a Stack object goes out of scope entation, accumulate. The loop would have executed without any problem with a contiguous Stack impler The destructor P131-132 Definition: A destructor is a special method in a class that is automatically executed on objects of the class immediately before they go out of scope. The client does not need to call a destructor explicitly and does not even need to know it is present. Destructors are often used to delete dynamically allocated objects that would otherwise become garbage Declaration: The destructor must be declared as a class method without return type and without parameters. Its name is given by adding a- prefix to the corresponding class name. Hence, the
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 gives the address of x. In this case, a declaration and assignment such as Item *ptr = &x would establish a pointer, ptr, to the object x. P.121-122 ⚫ Address of an array: The address of the initial element of an array is found by using the array’s name without any attached [] operators. For example, given a declaration Item x[20] the assignment Item *ptr = x sets up a pointer ptr to the initial element of the array x. Observe that an assignment expression ptr = &(x[0]) could also be used to find this address. P.121-122 ⚫ Pointers to structures: If p is a pointer to a structure object that has a data member called the data, then we could access this data member with the expression (*p).the_data, but C++ provides the operator -> as a shorthand, so we can replace the expression (*p).the_data by the equivalent, but more convenient, expression p->the_data. P.122 4.1.3 The Basics of Linked Structures A linked structure is made up of nodes, each containing both the information that is to be stored as an entry of the structure and a pointer telling where to find the next node in the structure. We shall refer to these nodes making up a linked structure as the nodes of the structure, and the pointers we often call links. Since the link in each node tells where to find the next node of the structure, we shall use the name next to designate this link. We shall use a struct rather than a class to implement nodes. P.123 Node Constructors P.125 [4.2] Linked Stacks P.127 Class Declaration for Linked Stack P.128 Benefits of Class Implementation P.128 ⚫ Maintain encapsulation: If we do not use a class to contain our stack, we lose the ability to set up methods for the stack. ⚫ Maintain the logical distinction between the stack itself, made up of all of its entries (each in a node), and the top of the stack, which is a pointer to a single node. ⚫ Maintain consistency with other data structures and other implementations, where structures are needed to collect several methods and pieces of information. ⚫ Help with debugging by allowing the compiler to perform better type checking Pushing a Linked Stack P.129 Popping a Linked Stack P.130 [4.3] Linked Stacks with Safeguards P.131 Client code can apply the methods of linked stacks in ways that lead to the accumulation of garbage or that break the encapsulation of Stack objects. C++ provides three devices (additional class methods) to alleviate these problems: destructors, copy constructors, overloaded assignment operators These new methods replace compiler generated default behavior and are often called silently (that is, without explicit action by a client). 4.3.1 Problem Example P.131 for (int i = 0; i < 1000000; i ++) { Stack small; small.push(some data); } Suppose that the linked Stack implementation is used. 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. The loop would have executed without any problem with a contiguous Stack implementation, where all allocated space for member data is released every time a Stack object goes out of scope. The Destructor P.131-132 Definition: A destructor is a special method in a class that is automatically executed on objects of the class immediately before they go out of scope. The client does not need to call a destructor explicitly and does not even need to know it is present. Destructors are often used to delete dynamically allocated objects that would otherwise become garbage. Declaration: The destructor must be declared as a class method without return type and without parameters. Its name is given by adding a ~ prefix to the corresponding class name. Hence, the
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, + , −, * , /
2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教 represent arithmetic operations, and= means printing the top of the stack(but not popping it off) 4.5.2 The Main Program P.142 Performing Commands P 142-143 Stubs and testing P144 4.5.3 Data Structures for Polynomials P144-147 4.5.4 writing a polynomial P147 Reading a polynomial P148 4.5.5 Addition of Polynomials P149 4.5.6 Group Project responsibilities 1. Allocation of tasks 2. Determining capabilities and specifications 3. Timetable 4. Stubs, drivers, and testing 5. Modifications. extensions. and revisions 6. Coordination and supervision 7. Documentation and reporting [4.6 Abstract Data Types and Their Implementations P152 Abstract Queues P153 Refinementof a Queue P154 Pointers and pitfalls 13 items P 155 Errata p. 118, Fig 4.3: The column of code(on the right)is C, not C++. The four lines should read: p=NULL, P new Item; *p p. 140, line 1 of E5: Change"Figure 4.13" to"Figure 4.14 p. 147, line 13: Change " to"." before word"Thus
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 represent arithmetic operations, and = means printing the top of the stack (but not popping it off). 4.5.2 The Main Program P.142 Performing Commands P.142-143 Stubs and Testing P.144 4.5.3 Data Structures for Polynomials P.144 -147 4.5.4 Writing a Polynomial P.147 Reading a Polynomial P.148 4.5.5 Addition of Polynomials P.149 4.5.6 Group Project Responsibilities 1. Allocation of tasks 2. Determining capabilities and specifications 3. Timetable 4. Stubs, drivers, and testing 5. Modifications, extensions, and revisions 6. Coordination and supervision 7. Documentation and reporting [4.6] Abstract Data Types and Their Implementations P.152 Abstract Queues P.153 Refinement of a Queue P.154 Pointers and Pitfalls 13 items P.155 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 118, Fig. 4.3: The column of code (on the right) is C, not C++. The four lines should read: p = NULL; p = new Item; *p = 1378; delete p; p. 140, line 1 of E5: Change "Figure 4.13" to "Figure 4.14". p. 147, line 13: Change ":" to "." before word "Thus". -------------------------------------------------------------------------------------------------------------------------------