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, the2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 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