2008级计算机专业数据结构 内部资料,仅供课堂教学使用 Chapter 2 INTRODUCTION TO STACKs P49 1. Stack Specific ations 4. Application: Bracket Matching 2. Implementation of Stacks 5. Abstract Data Types and Their Implementations 3. Application: A Desk Calculator 2. 1]Stack Specifications P50 A stack is a data structure in which all insertions and deletions of entries are made at one end. called he top of the stack. The last entry which is inserted is the first one that will be removed P 52 Pushing and popping a stack 2.1.3 Standard Temp late Library P 52-53, P.55(2.1.5) 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 e We can include the STl stack implementation into our programs with the directive #include numbers The STl provides several implementations of various data structures such as stack The code in a client program should not depend on a particular choice of implementation, but the berformance of the final program may very much depend on the choice of implementation. A second, optional template parameter selects the implementation. First Example: Reversing a List P53 2.2] Implementation of Stacks 2.2. Constructor P57-58 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 Stack: Stack() P None Post The Stack exists and is initialized to be empty 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. Starting in Chapter 6, we shall use C++ templates for greater generality Error Processing P58-59 We shall use a single enumerated type called Error code to report errors from all of our programs and functions of an the enumerated type Error code is part of the utility package in Appendix C Stacks use three values overflow. underflow
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 2 INTRODUCTION TO STACKS P.49 ----------------------------------------------------------------------------------------------------------------------------------------------- 1. Stack Specific ations 2. Implementation of Stacks 3. Application: A Desk Calculator 4. Application: Bracket Matchin g 5. Abstract Data Types and Their Implementations [2.1] Stack Specifications 2.1.2 P.50 A stack is a data structure in which all insertions and deletions of entries are made at one end, called the top of the stack. The last entry which is inserted is the first one that will be removed. P.52 Pushing and popping a stack 2.1.3 Standard Template Library P.52-53, P.55(2.1.5) ⚫ 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 and then we can define initially empty stack objects and apply methods called push, pop, top, and empty. ⚫ In C++, a template construction allows us to create data structures whose entries have different types. Example : stack numbers and stack 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. First Example: Reversing a List P.53 [2.2]Implementation of Stacks 2.2.1 Constructor P.57-58 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. Stack :: Stack( ); Pre: None. Post: The Stack exists and is initialized to be empty. Entry Types, Generics P.58 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. Starting in Chapter 6, we shall use C++ templates for greater generality. Error Processing P.58-59 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
2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教学使用 Later. we shall use several further values of an error code Programming Precept: After a client uses a class method, it should decide whether to check the resulting error status. Classes should be designed to allow clients to decide how to respond to errors. P 59 C++ also provides more sophisticated error processing called exception handling. The standard library implementations of classes use exception handling, but we shall opt for the simplicity of returning error codes in all our implementations Specification for Methods P 59-60 Error code Stack: pop(): Error code Stack: push(const Stack entry &item) Error code Stack: top(Stack entry &item)const bool Stack: empty( )const 2.2.2 Class Specification, Contiguous stack We set up an array to hold the entries in the stack and a counter to indicate how many entries there are P60 Class Specification 2.2.4P63 The declaration of private visibility for the data makes it is impossible for a client to access the data stored in a Stack except by using the methods push( ) pop(), and top() Important result: A Stack can never contain illegal or corrupted data. In general, data is said to be encapsulated if it can only be accessed by a controlled set of functions Programming Precept: The public methods for a data structure should be implemented without preconditions. The data members should be kept private. P 63 Representation of Data in a Contiguous Stack P62 2.2.3 Stack Methods P61 Further stack methods p61-62 2.3 Application: A Desk Calculator Reverse Polish Calculator P66-67 In a Reverse Polish calculator, the operands(numbers, usually) are entered before an operation(like addition, subtraction, multiplication, or division) 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 Obtaining a command p67-68 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 ectype 2. 4 Application: Bracket Matching P69-71 We develop a program to check that brackets are correctly matched in an input text file e We limit our attention to the brackets,i,(), and I e We read a single line of characters and ignore all input other than bracket characters e Algorithm: Read the file character by character. Each opening bracket i that is encountered is considered as unmatched and is stored until a matching bracket can be Any closing bracket ),I, or) must correspond, in bracket style, to the last unmatched opening bracket, which should now be retrieved and removed from storage. Finally, at the end of the program, we must check that no unmatched opening brackets are left over a program to test the matching of brackets needs to process its input file character by character, and, as it works its way through the input, it needs some way to remember any currently unmatched brackets These brackets must be retrieved in the exact reverse of their input order, and therefore a Stack provides an attractive option for their storage Our program need only loop over the input characters, until either a bracketing error is detected or the input file ends. Whenever a bracket is found an appropriate Stack operation is applied
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Later, we shall use several further values of an Error code. Programming Precept: After a client uses a class method, it should decide whether to check the resulting error status. Classes should be designed to allow clients to decide how to respond to errors. P.59 C++ also provides more sophisticated error processing called exception handling. The standard library implementations of classes use exception handling, but we shall opt for the simplicity of returning error codes in all our implementations. Specification for Methods P.59-60 Error code Stack :: pop( ); Error code Stack :: push(const Stack entry &item); Error code Stack :: top(Stack entry &item) const; bool Stack :: empty( ) const; 2.2.2 Class Specification, Contiguous Stack We set up an array to hold the entries in the stack and a counter to indicate how many entries there are. P60 Class Specification 2.2.4 P.63 The declaration of private visibility for the data makes it is impossible for a client to access the data stored in a Stack except by using the methods push( ), pop( ), and top( ). Important result: A Stack can never contain illegal or corrupted data. In general, data is said to be encapsulated if it can only be accessed by a controlled set of functions. Programming Precept: The public methods for a data structure should be implemented without preconditions. The data members should be kept private. P.63 Representation of Data in a Contiguous Stack P.62 2.2.3 Stack Methods P.61 Further Stack Methods P.61-62 [2.3] Application: A Desk Calculator Reverse Polish Calculator P.66-67 In a Reverse Polish calculator, the operands (numbers, usually) are entered before an operation (like addition, subtraction, multiplication, or division) 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. Obtaining a Command P.67-68 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. [2.4] Application: Bracket Matching P.69-71 ⚫ We develop a program to check that brackets are correctly matched in an input text file. ⚫ We limit our attention to the brackets {, }, ( , ), [, and ]. ⚫ We read a single line of characters and ignore all input other than bracket characters. ⚫ Algorithm: Read the file character by character. Each opening bracket ( , [, or { that is encountered is considered as unmatched and is stored until a matching bracket can be found. Any closing bracket ), ], or } must correspond, in bracket style, to the last unmatched opening bracket, which should now be retrieved and removed from storage. Finally, at the end of the program, we must check that no unmatched opening brackets are left over. ⚫ A program to test the matching of brackets needs to process its input file character by character, and, as it works its way through the input, it needs some way to remember any currently unmatched brackets. ⚫ These brackets must be retrieved in the exact reverse of their input order, and therefore a Stack provides an attractive option for their storage. ⚫ Our program need only loop over the input characters, until either a bracketing error is detected or the input file ends. Whenever a bracket is found, an appropriate Stack operation is applied
2008级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 Bracket Matching program P 70-71 2.5 Abstract Data Types and Their Implementations P71-75 2.5.2 Abstract Data Types P73-74 DEFINITION: A type is a set, and the elements of the set are called the values of the type ypes such as int, float, and char are called atomic types because we think of their values as single entities only, not something we wish to subdivide Computer languages like C++ provide tools such as arrays, classes, and pointers with which we can build new types, called structured types. A single value of a structured type(that is, a single element of its set)is a structured object such as a contiguous stack. a value of a structured type has two ingredients: It is made up of component elements, and there is a structure, a set of rules for putting the components together DEFINITION: A sequence of length is empty. A sequence of length n>1 of elements from a set T is an ordered pair(Sn-1, t)where Sn-I is a sequence of length n- l of elements from T, and t is an element of T We shall always draw a careful distinction between the word sequential, meaning that the elements form a sequence, and the word contiguous, which we take to mean that the elements have adjacent addresses in memory. Hence we shall be able to speak of a sequential list in a contiguous implementation ⊥ bstract stacks p74 The definition of a finite sequence allows us to define a list of items of a type T as a fir elements of the set t Next we wish to define a stack. But there is nothing regarding the sequence of items to distinguish a stack from a list. The primary characteristic of a stack is the set of operations or methods by which changes or accesses can be made. Including a statement of these operations with the structural rules defining a finite sequence, we obtain the definition of stack 2.5.3 Refinement of Data Specification 4 levels of the refinement process: abstract, data structures, implementation, application level The first two levels are often called conceptual because at these levels we are more concerned with problem solving than with programming. The middle two levels can be called algorithmic because they concern precise methods for representing data and operating with it. The last two levels are specifically concerned with programming Programming Precept: Let your data structure your program. Refine your algorithms and data structures at the same time. P. 75 Programming Precept: Once your data are fully structured, your al gorithms should almost write themselves Pointers and Pitfalls 9 items P76 一---------- Errata p 64, El, private data members: " int top"should be "int count
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Bracket Matching Program P.70-71 [2.5] Abstract Data Types and Their Implementations P.71-75 2.5.2 Abstract Data Types P.73-74 DEFINITION: A type is a set, and the elements of the set are called the values of the type. Types such as int, float, and char are called atomic types because we think of their values as single entities only, not something we wish to subdivide. Computer languages like C++ provide tools such as arrays, classes, and pointers with which we can build new types, called structured types. A single value of a structured type (that is, a single element of its set) is a structured object such as a contiguous stack. A value of a structured type has two ingredients: It is made up of component elements, and there is a structure, a set of rules for putting the components together. DEFINITION: A sequence of length 0 is empty. A sequence of length n ≥ 1 of elements from a set T is an ordered pair (Sn−1 , t ) where Sn−1 is a sequence of length n − 1 of elements from T, and t is an element of T . We shall always draw a careful distinction between the word sequential, meaning that the elements form a sequence, and the word contiguous, which we take to mean that the elements have adjacent addresses in memory. Hence we shall be able to speak of a sequential list in a contiguous implementation. Abstract Stacks P.74 The definition of a finite sequence allows us to define a list of items of a type T as a finite sequence of elements of the set T. Next we wish to define a stack. But there is nothing regarding the sequence of items to distinguish a stack from a list. The primary characteristic of a stack is the set of operations or methods by which changes or accesses can be made. Including a statement of these operations with the structural rules defining a finite sequence, we obtain the definition of stack. 2.5.3 Refinement of Data Specification P.74-75 4 levels of the refinement process: abstract, data structures, implementation, application level The first two levels are often called conceptual because at these levels we are more concerned with problem solving than with programming. The middle two levels can be called algorithmic because they concern precise methods for representing data and operating with it. The last two levels are specifically concerned with programming. Programming Precept: Let your data structure your program. Refine your algorithms and data structures at the same time. P.75 Programming Precept: Once your data are fully structured, your algorithms should almost write themselves. P.75 Pointers and Pitfalls 9 items P.76 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 64, E1, private data members: "int top" should be "int count". -------------------------------------------------------------------------------------------------------------------------------