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