《数据结构英文课件：ch02 Introduction to Stacks》由会员分享，可在线阅读，更多相关《数据结构英文课件：ch02 Introduction to Stacks（71页珍藏版）》请在金锄头文库上搜索。
1、 Chapter 2 Introduction to StacksnThis chapter introduces the study of stacks, one of the simplest but most important of all data structures. nThe application of stacks to the reversal of data is illustrated with a program that calls on the standard-library stack implementation. nA contiguous implem
2、entation of a stack data structure is then developed and used to implement a reverse Polish calculator and a bracket checking program. nThe chapter closes with a discussion of the general principles of abstract data types and data structures.n本章引入栈的研究，栈是所有数据结构中最简单但也是最重要的数据结构。n本节中先举了一个利用栈的标准库函数完成数据逆置
3、的例子。n然后，实现了一个顺序栈，并且在此结构下完成了逆波兰计算器和括号匹配程序。n本章最后讨论了抽象数据类型和数据结构的基本原则。 Content PointsqStack SpecificationsqImplementation of StacksqApplication: A Desk CalculatorqApplication: Bracket MatchingqAbstract Data Types and Their ImplementationsStack SpecificationqProblem Read an integer n , then read a list o
4、f n numbers,and print the list in reverse order. Solution1: use an array. occupying part of an array of fixed size ,with some of the entries in the array remaining unused. #include using namespace std;int main( )/* Pre: The user supplies an integer n and n decimal numbers.Post: The numbers are print
5、ed in reverse order.*/int n;double item;double numbers ; cout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in reverse order. n;for (int i = 0; i item;numbersi=item;cout endl =0; i-) cout numbersi;cout endl;25nThe difference between list and array表和数组的区别1、the l
6、ength of a list can be changed by insert or delete some items from the list,but the length of an array is an constant. 表的长度是可变的。即表中的数字是可以增加和删除的，因此，如果n=3，那么表中只有3个数字，如果n=19，那么表中就有19个数字。 数组（或称为向量），具体编程时的术语。数组中的元素个数是个常量，也即当程序被编译时，数组的长度就确定了。 2、List is a dynamic data structure, but array is an static data
7、 structure. 表是一个动态数据结构，因为它的长度是可以变化的，然而，数组是一种静态数据结构，因为它的长度是固定的。 3、List is a logical concept and array is a programming feature . 表是一个逻辑层面的概念，数组是编程实现时的概念。The relation between list and arraynA list of variable size can be implemented in a computer by occupying part of an array of fixed size, with some
8、of the entries in the array remained unused. 长度可变的表在计算机中的实现可以用一个定长数组实现，其中定长数组的部分单元并未使用。nBut we will find that there are several ways to implement lists, using an array is only one of them ,we shouldnt confuse the fundamental data structure with the choice of implementations. 然而，我们以后会发现，有很多种方法可以用来完成表
9、的实现，因此我们不能将实现方法的选择和更基本的数据结构的选择和定义相混淆。Solution2: use a stack#include ;using namespace std;int main( )/* Pre: The user supplies an integer n and n decimal numbers.Post: The numbers are printed in reverse order.Uses: The STL class stack and its methods */ int n; double item; stack numbers; / declares a
10、nd initializes a stack of numbers cout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in reverse order. n; for (int i = 0; i item;numbers.push(item); cout endl endl; while (!numbers.empty( ) cout numbers.top( ) ;numbers.pop( ); cout endl;Stack Specificationsq Sp
11、ecifications（定义）（定义） A stack is a list 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 （后进先出）（后进先出）. Empty stack means the stack has no item. Example: plates sitting on t
12、he counter in a busy cafeteria.Customers take trays off the top of stack. employees returned trays back on top of the stack. Other examples methods Push（入栈）（入栈） Pop（出栈）（出栈） empty(判空判空) top(取栈顶元素取栈顶元素) size constructor Important property:Last in,first out -LIFOExample and sketch mapPushing and poppin
13、g a stackPushing and popping a stackA Problem : Suppose we have five items which were pushed into a stack in turn, the order of the push is “abcde”, and the pop turn is “dceba”, please decide the minimum size of the stack. 假设有个元素abcde顺序进栈（进栈过程中可以出栈），出栈序列为dceba，则该栈容量必定不小于多少。Standard Template Library
14、(STL)q First Example: Reversing a List(using STL class stack)#include int main( )/* Pre: The user supplies an integer n and n decimal numbers. Post: The numbers are printed in reverse order. Uses: The STL class stack and its methods */int n;double item;stack numbers; / declares and initializes a sta
15、ck of numberscout Type in an integer n followed by n decimal numbers. endl The numbers will be printed in reverse order. n;Standard Template Library (STL)q First Example: Reversing a Listfor (int i = 0; i item;numbers.push(item);cout endl endl;while (!numbers.empty( ) cout numbers.top( ) ;numbers.po
16、p( );cout endl;/请参考C+ STL中stack类，也可参考msdn或相关书籍。Standard Template Library (STL)qThe standard template library (abbreviated STL) in C+ contains much useful information, many functions, and many classes.q The STL provides convenient implementations for many common data structures（公用数据结构）（公用数据结构）, inclu
17、ding almost all the data structures we shall study in this book.q 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.Standard Template Library (STL)q In C+, a
18、 template construction allows us to create data structures whose entries have different types. Example: stack numbers and stack numbersqThe STL provides several implementations of various data structures such as stacks.（提供各种数据结构的多种实现手段）q The code in a client program should not depend on a particular
19、 choice of implementation, but the performance of the final program may very much depend on the choice of implementation.（客户程序中的代码不依赖于所用类的具体实现，但程序的性能受栈的具体实现手段的影响。）q A second, optional template parameter selects the implementation. To stack the default implementation comes from deque . (double-ended
20、queue)qThe STL implementations are highly efficient, convenient and designed with enough default options to allow programmers to use them easily.(高效、方便、很多可选项)Information Hiding（信息隐藏）（信息隐藏）q information hiding：The methods for handling stacks are implemented in the C+ standard library, and we can use
21、them without needing to know the details of how stacks are kept in memory or of how the stack operations are actually done.q One important difference between practicing information hiding with regard to arrays and practicing information hiding with regard to stacks ： C+ provides just one built-in im
22、plementation of arrays, but the STL has several implementations of stacks. Information Hiding（信息隐藏）（信息隐藏）q advantage of information hiding （信息隐藏的优点）（信息隐藏的优点） If the instructions for manipulating a stack have been written out every time a stack is used, then every occurrence of these instructions wil
23、l need to be changed. If we have practiced information hiding by using separate functions for manipulating stacks, then only the declarations will need to be changed.（用方法封装栈的操作，当栈的实现改变时，修改更容易）-change of implementation Another advantage of information hiding shows up in programs that use stacks where
24、 the very appearance of the words push and pop immediately alert a person reading the program to what is being done, whereas the instructions themselves might be more obscure.- clarity of program We shall find that separating the use of data structures from their implementation will help us improve
25、the top-down design of both our data structures and our programs. -top-down design Implementation of Stack （栈的实现）（栈的实现）q Stack Specification of Methods for Stacks constructor- initialization（构造函数（构造函数-初始化）初始化）The constructor is a function with the same name as the corresponding class and no return t
26、ype. It is invoked automatically whenever an object of the class is declared.Specification of Methods for Stacksq Entry Types, Generics（泛型）（泛型） For generality, we use Stack_entry for the type of entries in a Stack. A client can specify this type with a definition such astypedef int Stack_entry;ortyp
27、edef 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.Specification of Methods for Stacksq Error Processing （出
28、错处理）（出错处理） 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 Later, we shall use several
29、further values of an Error_code.Determine the methods and their specifications for the Stack class , similar as the STL stack class:poppushtopempty Specification of Methods for Stacksq Specification for Methods（方法的定义）（方法的定义）Error_code Stack : push(const Stack_entry &item);pre: None.post: If the Stac
30、k is not full, item is added to the top of the Stack. If the Stack is full, an Error_code of overflow（上溢）（上溢） is returned and the Stack is left unchanged.Error_code Stack : pop( ); pre: None.post: If the Stack is not empty, the top of the Stack is removed. If the Stack is empty, an Error_code of und
31、erflow（下溢）（下溢） is returned and the Stack is left unchanged.Specification of Methods for Stacksq Specification for Methods（方法的定义）（方法的定义）bool Stack : empty( ) const;precondition: None.postcondition: A result of true is returned if the Stack is empty, otherwise false is returned.Error_code Stack : top(
32、Stack_entry &item) const;precondition: None.postcondition: The top of a nonempty Stack is copied to item. A code of fail is returned if the Stack is empty.Determine the data members of the Stack class栈顶First,we must store the data in the stack How to store the data?An array (a contiguous implementat
33、ion)The array has a maxsize fixed sizeThe stack occupy only part of the array spaceSecond,how many?A counterThe Class Specification（类的定义）（类的定义）q We set up an array to hold the entries in the stack and a counter to indicate how many entries there are.const int maxstack = 10; / small value for testing
34、class Stack public:Stack( );bool empty( ) const;Error_code pop( );Error_code top(Stack_entry &item) const;Error_code push(const Stack_entry &item);private:int count;Stack_entry entrymaxstack;Pushing, Popping, and Other Methodsq We note that the data member count represents the number of items in a S
35、tack. Therefore, the top of a Stack occupies entrycount - 1, as shown in Figure 2.4. Pushing, Popping, and Other MethodsError_code Stack : push(const Stack_entry &item)/* Pre: None.Post: If the Stack is not full, item is added to the top of the Stack. If the Stack is full, an Error_code of overflow
36、is returned and the Stack is left unchanged.*/Error_code outcome = success;if (count = maxstack)outcome = overflow;elseentrycount+ = item;return outcome;Pushing, Popping, and Other MethodsError_code Stack : pop( )/* Pre: None.Post: If the Stack is not empty, the top of the Stack is removed. If the S
37、tack is empty, an Error_code of underflow is returned. */Error_code outcome = success;if (count = 0)outcome = underflow;else -count;return outcome;Pushing, Popping, and Other MethodsError_code Stack : top(Stack_entry &item) const/* Pre: None.Post: If the Stack is not empty, the top of the Stack is r
38、eturned in item. If the Stack is empty an Error_code of underflow is returned. */Error_code outcome = success;if (count = 0)outcome = underflow;elseitem = entrycount - 1;return outcome;Pushing, Popping, and Other Methodsbool Stack : empty( ) const/* Pre: None.Post: If the Stack is empty, true is ret
39、urned. Otherwise false is returned. */bool outcome = true;if (count 0) outcome = false;return outcome;Stack : Stack( )/* Pre: None.Post: The stack is initialized to be empty. */count = 0;n算法的时间复杂度nO(1)Encapsulation（封装）（封装）q Notice that our stack implementation forces client code to make use of infor
40、mation hiding. Our 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 official methods push( ), pop( ), and top( ). q One important result of this data privacy is that a Stack can never contain illegal or corrup
41、ted data. Every Stack object will be initialized to represent a legitimate empty stack and can only be modified by the official Stack methods, free of any data corruption. (assurance of data integrity)q We summarize this protection that we have given our Stack objects by saying that they are encapsu
42、lated. In general, data is said to be encapsulated if it can only be accessed by a controlled set of functions.Application: A Desk Calculator （计算器）（计算器）qReverse Polish Calculator（逆波兰计算器）（逆波兰计算器） In a Reverse Polish calculator, the operands (numbers, usually) are entered before an operation (like add
43、ition, subtraction,multiplication, or division) is specified. (a * (b - c) + d-a b c - * d + The advantage of a reverse Polish calculator is that any expression, no matter how complicated, can be specified without the use of parentheses.（括号）（括号）Postfix ExpressionInfix ExpressionApplication: A Desk C
44、alculatorq Reverse Polish Calculator（逆波兰计算器）（逆波兰计算器） We shall write ? to denote an instruction to read an operand; + , -, * , and / represent arithmetic operations; and = is an instruction to print the value just got.Eg1: we write a, b, c, and d to denote numerical values such as 3.14 or -7. The ins
45、tructions ? a ? b + = mean read and store the numbers a and b, calculate and store their sum, and then print the sum. Eg2: The instructions ? a ? b + ? c ? d + * = request four numerical operands, and the result printed is the value of (a + b) * (c + d). Eg3: the instructions ? a ? b ? c - = * ? d +
46、 = mean read the numbers a, b, c , caculate b - c and print its value, then calculate a * (b - c), read d, and finally calculate and print (a * (b - c) + d. 依次输入：?1?2+?3*=后，显示计算结果9算法思想：程序从键盘接受命令符算法思想：程序从键盘接受命令符如输入的命令为“?”则继续读入一个操作数，由于对该操作数执行的运算符还未知，所以暂时将它存储起来；如输入的是“+-*/”等运算符则此时应将最近保存过的数拿出两个作算术运算，并将运算
47、的中间结果存储起来。由于最近存储的操作数（或是最近存储的中间结果）即是即将拿出来作运算的操作数，也即后存储的先取出来，即满足“后进先出”的原则，因此，应把这些操作数存储在栈中。如输入的命令为“=”将刚才的运算结果即栈顶显示出来。?1?2+?3*=? denote an instruction to read an operand and push it onto the stack; + , -, * , and / represent arithmetic operations; When an operation is performed, it pops its operands fro
48、m the stack and pushes its result back onto the stack. = is an instruction to print the value.Application: A Desk Calculatortypedef double Stack_entry;#include “Stack.hint main( )/* Post: The program has executed simple arithmetic commands entered by the user.Uses: The class Stack and the functions
49、introduction, instructions, do_command,and get_command. */Stack stored_numbers;introduction( );instructions( );while (do_command(get_command( ), stored_numbers);The auxiliary function get_command obtains a command from the user, checking that it is valid and converting it to lowercase by using the s
50、tring function tolower( ) that is declared in the standard header file cctype.Application: A Desk Calculatorchar get_command( )char command;bool waiting = true;cout Select command and press :;while (waiting) cin command;command = tolower(command);if (command = ? | command = = | command = + |command
51、= - | command = * | command = / |command = q) waiting = false;else cout Please enter a valid command: endl ?push to stack =print top endl + - * / are arithmetic operations endl Quit. endl;return command;Application: A Desk Calculatorbool do_command(char command, Stack &numbers)/* Pre: The first para
52、meter specifies a valid calculator command.Post: The command specified by the first parameter has been applied to the Stack of numbers given by the second parameter. A result of true is returned unless command = q .Uses: The class Stack. */double p, q;switch (command) case ?: / read cout Enter a rea
53、l number: p;if (numbers.push(p) = overflow)cout Warning: Stack full, lost number endl;break;case =: / print if (numbers.top(p) = underflow) cout Stack empty endl;elsecout p endl;break;Application: A Desk Calculatorcase +:if (numbers.top(p) = underflow)cout Stack empty endl;else numbers.pop( );if (nu
54、mbers.top(q) = underflow) cout Stack has just one entry endl;numbers.push(p);else numbers.pop( );if (numbers.push(q + p) = overflow)cout Warning: Stack full, lost result endl;break;/ Add options for further user commands.Application: A Desk Calculatorcase q: cout Calculation finished.n;return false;
55、return true;q In calling this function, we must pass the Stack parameter by reference, because its value might need to be modified. For example, if the command parameter is +, then we normally pop two values off the Stack numbers and push their sum back onto it: This should certainly change the Stac
56、k.qThe function do_command allows for an additional user command, q, that quits the program.进一步思考n如果是读入一个由后缀表达式组成的字符串呢？3 4 * 5 1 / +n如果是一个中缀表达式呢？(3-4)+(5/1)Application: Bracket Matching （括号匹配）（括号匹配）q We develop a program to check that brackets are correctly matched in an input text file.q We limit o
57、ur attention to the brackets , , (, ), , and .q We read a single line of characters and ignore all input other than bracket characters.q Algorithm: Read the file character by character. qEach opening bracket (, , or that is encountered is considered as unmatched and is stored until a matching bracke
58、t can be found.q 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.Application: Bracket Match
59、ingq The program 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.q These brackets must be retrieved in the exact reverse of their input order, and therefore a Stack provides an attracti
60、ve option for their storage.q Our program need only loop over the input characters, until either a bracketing error is detected or the input file ends.q Whenever a bracket is found, an appropriate Stack operation is applied.3*A+(b*cd)3*A+(b*cd+53*A+(b*cd)dfg3*A+(b*cd)+5Application: Bracket Matchingq
61、Bracket Matching Program（括号匹配程序）（括号匹配程序） #include “Stack.h”int main( )/* Post: The program has notified the user of any bracket mismatch in the standard input file.Uses: The classStack . */ Stack openings;char symbol;bool is_matched = true;while (is_matched & (symbol = cin.get( ) != n) if (symbol =
62、| symbol = ( | symbol = ) openings.push(symbol);if (symbol = | symbol = ) | symbol = ) if (!openings.empty( ) cout Unmatched opening bracket(s) detected. endl; if (openings.empty( ) cout Unmatched closing bracket symbol detected. endl; is_matched = false;else char match; openings.top(match); opening
63、s.pop( ); is_matched = (symbol = & match = )| (symbol = ) & match = () | (symbol = & match = );if (!is_matched) cout Bad match match symbol 0)modu.push(N%8);N=N/8;while (!modu.empty()modu.top(m);modu.pop();coutm;Abstract Data Types and Their Implementations（抽象数据类型及其实现）（抽象数据类型及其实现）q General Definitio
64、ns atomic types: such as int, float, and char structured types：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. such as arrays, classes, and pointers.1、Drawing a clear separation betwe
65、en the logical structure of our data and its implementation in computer memory will help us in designing programs. 2、Sequential（有序）contiguous（连续）-a sequential list in a contiguous implementation.Abstract Data TypesqAbstract Stacks The definition of a finite sequence allows us to define a list of ite
66、ms 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.
67、Abstract Data Typesq DEFINITION: A stack of elements of type T is a finite sequence of elements of T , together with the following operations: Create the stack, leaving it empty. Test whether the stack is Empty. Push a new entry onto the top of the stack, provided the stack is not full. Pop the entr
68、y off the top of the stack, provided the stack is not empty. Retrieve the Top entry from the stack, provided the stack is not empty.qIncluding a statement of these operations with the structural rules defining a finite sequence, we obtainNote that this definition makes no mention of the way in which
69、 the abstract data type stack is to be implemented. In the coming chapters we will study different implementations of stacks, and this new definition fits any of these implementations equally well. This definition produces what is called an abstract data type, often abbreviated as ADT. The important
70、 principle is that the definition of any abstract data type involves two parts: First is a description of the way in which the components are related to each other, and second is a statement of the operations that can be performed on elements of the abstract data type.Abstract Data Typesq Refinement
71、 of Data Specification On the abstract level we decide how the data are related to each other and what operations are needed, but we decide nothing concerning how the data will actually be stored or how the operations will actually be done.（线性表或栈？） On the data structures level we specify enough deta
72、il so that we can analyze the behavior of the methods and make appropriate choices as dictated by our problem.（分析，选择数据结构，如栈） On the implementation level we decide the details of how the data structures will be represented in computer memory.（栈的实现，顺序还是链式？） On the application level we settle all detai
73、ls required for our particular application.（逆置主程序）Abstract Data Types 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 re
74、presenting data and operating with it. The last two levels are specifically concerned with programming.Pointers and Pitfalls1. Use data structures to clarify the logic of your programs.2. Practice information hiding and encapsulation in implementing data structures: Use functions to access your data
75、 structures, and keep these in classes separate from your application program.3. Postpone decisions on the details of implementing your data structures as long as you can.4. Stacks are among the simplest kind of data structures; use stacks when possible.5. In any problem that requires a reversal of
76、data, consider using a stack to store the data.Pointers and Pitfalls6. Avoid tricky ways of storing your data; tricks usually will not generalize to new situations.7. Be sure to initialize your data structures.8. In designing algorithms, always be careful about the extreme cases and handle them grac
77、efully. Trace through your algorithm to determine what happens in extreme cases, particularly when a data structure is empty or full.9. Before choosing implementations, be sure that all the data structures and their associated operations are fully specified on the abstract level.homeworknP56 Exercis
78、e 2.1 E4(a)(b)nP64 Exercise 2.2 E2 E3 (c) (e) E4 double_stack , push_a,pop_bnP69 Exercise 2.3 E2 1、补充习题：所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法（函数） ，以判断一个串是否是回文。2、请写一个算法（函数），将一个数的质因数进行分解并输出。1、STL中的栈与我们自己设计的栈是不同的，逆置中用的是stack，calculate中用的是Stack，模板类，方法更加丰富，而且相同的方法参数也不同，有升级版本。
79、2、Command设计成一个类？3、将求栈的所有元素的平均值写成Stack类的方法？4、头文件之间的包含关系(1)#ifndef UTILITY_H#define UTILITY_H#endif(2) pragma once5、做好的同学着手作代码的优化，程序文档化，我们几位老师编写一个实验教程，希望能用到你的程序，要求程序设计工程化，软件结构模块化，代码清晰，可读性强，采用合适的数据结构。上机中的问题头文件之间的包含关系(1)#ifndef UTILITY_H#define UTILITY_H#endif(2) #pragma oncen实验平台地址：192.168.151.179，需按学号和真实姓名注册周四实验内容已布置
