数据结构——C++版（第四版）（英文影印版）pdf/txt下载_在线阅读全文

内容简介

数据结构——C++版（第四版）（英文影印版）是一本基于C++的思想、介绍数据结构和算法的大学教材，已经在全球多个国家的大学用作数据结构课程的基础教材。数据结构——C++版（第四版）（英文影印版）以C++语言作为实现语言，利用面向对象的方法，从规格说明出发，使用基础的数据类型来描述程序算法的设计与实现。书中主要内容包括：软件开发的各个阶段，抽象数据类型与C++类，容器类，指针与动态数组，链表，用模板、迭代器和STL进行软件开发，堆栈，队列，递归思想，树，平衡树，查找，排序，派生类与继承，图表。通过学习数据结构——C++版（第四版）（英文影印版），可使读者具备使用数据类型的能力，学会利用多种方法来实现数据类型，以及从不同的实现中进行取舍。
数据结构——C++版（第四版）（英文影印版）可作为计算机、电类专业本科生和非信息技术专业硕士研究生的教材，也可供工程技术人员参考。

目　　录

Chapter List
CHAPTER 1 THE PHASES OF SOFTWARE DEVELOPMENT
CHAPTER 2 ABSTRACT DATA TYPES AND C++ CLASSES
CHAPTER 3 CONTAINER CLASSES
CHAPTER 4 POINTERS AND DYNAMIC ARRAYS
CHAPTER 5 LINKED LISTS
CHAPTER 6 SOFTWARE DEVELOPMENT WITH TEMPLATES,ITERATORS,AND THE STL
CHAPTER 7 STACKS
CHAPTER 8 QUEUES
CHAPTER 9 RECURSIVE THINKING
CHAPTER 10 TREES
CHAPTER 11 BALANCED TREES
CHAPTER 12 SEARCHING
CHAPTER 13 SORTING

Chapter List CHAPTER 1 THE PHASES OF SOFTWARE DEVELOPMENT CHAPTER 2 ABSTRACT DATA TYPES AND C++ CLASSES CHAPTER 3 CONTAINER CLASSES CHAPTER 4 POINTERS AND DYNAMIC ARRAYS CHAPTER 5 LINKED LISTS CHAPTER 6 SOFTWARE DEVELOPMENT WITH TEMPLATES,ITERATORS,AND THE STL CHAPTER 7 STACKS CHAPTER 8 QUEUES CHAPTER 9 RECURSIVE THINKING CHAPTER 10 TREES CHAPTER 11 BALANCED TREES CHAPTER 12 SEARCHING CHAPTER 13 SORTING CHAPTER 14 DERIVED CLASSES AND INHERITANCE CHAPTER 15 GRAPHS APPENDIXES INDEX Contents CHAPTER 1 THE PHASES OF SOFTWARE DEVELOPMENT 1.1 Specification,Design,Implementation Design Concept:Decomposing the Problem Preconditions and Postconditions Using Functions Provided by Other Programmers Implementation Issues for the ANSI/ISO C++ Standard C++ Feature:The Standard Library and the Standard Namespace Programming Tip:Use Declared Constants Clarifying the Const Keyword Part 1:Declared Constants Programming Tip:Use Assert to Check a Precondition Programming Tip:Use EXIT_SUCCESS in a Main Program C++ Feature:Exception Handling Self-Test Exercises for Section 1.1 1.2 Running Time Analysis The Stair-Counting Problem Big-O Notation Time Analysis of C++ Functions Worst-Case,Average-Case,and Best-Case Analyses Self-Test Exercises for Section 1.2 1.3 Testing and Debugging Choosing Test Data Boundary Values Fully Exercising Code Debugging Programming Tip:How to Debug Self-Test Exercises for Section 1.3 Chapter Summary Solutions to Self-Test Exercises CHAPTER 2 ABSTRACT DATA TYPES AND C++ CLASSES 2.1 Classes and Members Programming Example:The Throttle Class Clarifying the Const Keyword Part 2:Constant Member Functions Using a Class A Small Demonstration Program for the Throttle Class Implementing Member Functions Member Functions May Activate Other Members Programming Tip:Style for Boolean Variables Self-Test Exercises for Section 2.1 2.2 Constructors The Throttle恠 Constructor What Happens If You Write a Class with No Constructors? Programming Tip:Always Provide Constructors Revising the Throttle恠 Member Functions Inline Member Functions Programming Tip:When to Use an Inline Member Function Self-Test Exercises for Section 2.2 2.3 Using a Namespace,Header File,and Implementation File Creating a Namespace The Header File Describing the Value Semantics of a Class Within the Header File Programming Tip:Document the Value Semantics The Implementation File Using the Items in a Namespace Pitfall:Never Put a Using Statement Actually in a Header File Self-Test Exercises for Section 2.3 2.4 Classes and Parameters Programming Example:The Point Class Default Arguments Programming Tip:A Default Constructor Can Be Provided by Using Default Arguments Parameters Pitfall:Using a Wrong Argument Type for a Reference Parameter Clarifying the Const Keyword Part 3:Const Reference Parameters Programming Tip:Use const Consistently When the Type of a Function恠 Return Value Is a Class Self-Test Exercises for Section 2.4 2.5 Operator Overloading Overloading Binary Comparison Operators Overloading Binary Arithmetic Operators Overloading Output and Input Operators Friend Functions Programming Tip:When to Use a Friend Function The Point Class凱utting Things Together Summary of Operator Overloading Self-Test Exercises for Section 2.5 2.6 The Standard Template Libary and the Pair Class Chapter Summary Solutions to Self-Test Exercises Programming Projects CHAPTER 3 CONTAINER CLASSES 3.1 The Bag Class The Bag Class凷pecification C++ Feature:Typedef Statements Within a Class Definition C++ Feature:The std::size_t Data Type Clarifying the Const Keyword Part 4:Static Member Constants Older Compilers Do Not Support Initialization of Static Member Constants The Bag Class凞ocumentation Documenting the Value Semantics The Bag Class凞emonstration Program The Bag Class凞esign Pitfall:The value_type Must Have a Default Constructor The Invariant of a Class The Bag Class処mplementation Pitfall:Needing to Use the Full Type Name bag::size_type Programming Tip:Make Assertions Meaningful C++ Feature:The Copy Function from the C++ Standard Library The Bag Class凱utting the Pieces Together Programming Tip:Document the Class Invariant in the Implementation File The Bag Class凾esting Pitfall:An Object Can Be an Argument to Its Own Member Function The Bag Class凙nalysis Self-Test Exercises for Section 3.1 3.2 Programming Project:The Sequence Class The Sequence Class凷pecification The Sequence Class凞ocumentation The Sequence Class凞esign The Sequence Class凱seudocode for the Implementation Self-Test Exercises for Section 3.2 3.3 Interactive Test Programs C++ Feature:Converting Input to Uppercase Letters C++ Feature:The Switch Statement Self-Test Exercises for Section 3.3 3.4 The STL Multiset Class and Its Iterator The Multiset Template Class Some Multiset Members Iterators and the[...)Pattern Pitfall:Do Not Access an Iterator恠 Item After Reaching end() Testing Iterators for Equality Other Multiset Operations Invalid Iterators Clarifying the Const Keyword Part 5:Const Iterators Pitfall:Changing a Container Object Can Invalidate Its Iterators Self-Test Exercises for Section 3.4 Chapter Summary Solutions to Self-Test Exercises Programming Projects CHAPTER 4 POINTERS AND DYNAMIC ARRAYS 4.1 Pointers and Dynamic Memory Pointer Variables Using the Assignment Operator with Pointers Dynamic Variables and the new Operator Using new to Allocate Dynamic Arrays The Heap and the bad_alloc Exception The delete Operator Programming Tip:Define Pointer Types Self-Test Exercises for Section 4.1 4.2 Pointers and Arrays as Parameters Clarifying the Const Keyword Part 6:Const Parameters That Are Pointers or Arrays Self-Test Exercises for Section 4.2 4.3 The Bag Class with a Dynamic Array Pointer Member Variables Member Functions Allocate Dynamic Memory as Needed Programming Tip:Provide Documentation about Possible Dynamic Memory Failure Value Semantics The Destructor The Revised Bag Class凜lass Definition The Revised Bag Class処mplementation Programming Tip:How to Check for Self-Assignment Programming Tip:How to Allocate Memory in a Member Function The Revised Bag Class凱utting the Pieces Together Self-Test Exercises for Section 4.3 4.4 Prescription for a Dynamic Class Four Rules Special Importance of the Copy Constructor Pitfall:Using Dynamic Memory Requires a Destructor,a Copy Constructor,and an Overloaded Assignment Operator Self-Test Exercises for Section 4.4 4.5 The STL String Class and a Project Null-Terminated Strings Initializing a String Variable The Empty String Reading and Writing String Variables Pitfall:Using = and == with Strings The strcpy Function The strcat Function Pitfall:Dangers of strcpy,strcat,and Reading Strings The strlen Function The strcmp Function The String Class凷pecification Constructor for the String Class Overloading the Operator[] Some Further Overloading Other Operations for the String Class The String Class凞esign The String Class処mplementation Demonstration Program for the String Class Chaining the Output Operator Declaring Constant Objects Constructor-Generated Conversions Using Overloaded Operations in Expressions Our String Class Versus the C++ Library String Class Self-Test Exercises for Section 4.5 4.6 Programming Project:The Polynomial Chapter Summary Solutions to Self-Test Exercises Programming Projects CHAPTER 5 LINKED LISTS 5.1 A Fundamental Node Class for Linked Lists Declaring a Class for Nodes Using a Typedef Statement with Linked-List Nodes Head Pointers,Tail Pointers The Null Pointer The Meaning of a Null Head Pointer or Tail Pointer The Node Constructor The Node Member Functions The Member Selection Operator Clarifying the Const Keyword Part 7:The Const Keyword with a Pointer to a Node,and the Need for Two Versions of Some Member Functions Programming Tip:A Rule for a Node恠 Constant Member Functions Pitfall:Dereferencing the Null Pointer Self-Test Exercises for Section 5.1 5.2 A Linked-List Toolkit Linked-List Toolkit凥eader File Computing the Length of a Linked List Programming Tip:How to Traverse a Linked List Pitfall:Forgetting to Test the Empty List Parameters for Linked Lists Inserting a New Node at the Head of a Linked List Inserting a New Node That Is Not at the Head Pitfall:Unintended Calls to delete and new Searching for an Item in a Linked List Finding a Node by Its Position in a Linked List Copying a Linked List Removing a Node at the Head of a Linked List Removing a Node That Is Not at the Head Clearing a Linked List Linked-List Toolkit凱utting the Pieces Together Using the Linked-List Toolkit Self-Test Exercises for Section 5.2 5.3 The Bag Class with a Linked List Our Third Bag凷pecification Our Third Bag凜lass Definition How to Make the Bag value_type Match the Node value_type Following the Rules for Dynamic Memory Usage in a Class The Third Bag Class処mplementation Pitfall:The Assignment Operator Causes Trouble with Linked Lists Programming Tip:How to Choose Between Approaches The Third Bag Class凱utting the Pieces Together Self-Test Exercises for Section 5.3 5.4 Programming Project:The Sequence Class with a Linked List The Revised Sequence Class凞esign Suggestions The Revised Sequence Class刅alue Semantics Self-Test Exercises for Section 5.4 5.5 Dynamic Arrays vs. Linked Lists vs. Doubly Linked Lists Making the Decision Self-Test Exercises for Section 5.5 5.6 STL Vectors vs. STL Lists vs. STL Deques Self-Test Exercises for Section 5.6 Chapter Summary Solutions to Self-Test Exercises Programming Projects CHAPTER 6 SOFTWARE DEVELOPMENT WITH TEMPLATES,ITERATORS,AND THE STL 6.1 Template Functions Syntax for a Template Function Programming Tip:Capitalize the Name of a Template Parameter Using a Template Function Pitfall:Failed Unification Errors A Template Function to Swap Two Values Programming Tip:Swap,Max,and Min Functions Parameter Matching for Template Functions A Template Function to Find the Biggest Item in an Array Pitfall:Mismatches for Template Function Arguments A Template Function to Insert an Item into a Sorted Array Self-Test Exercises for Section 6.1 6.2 Template Classes Syntax for a Template Class Programming Tip:Use the Name Item and the typename Keyword Pitfall:Do Not Place Using Directives in a Template Implementation More About the Template Implementation File Parameter Matching for Member Functions of Template Classes Using the Template Class Details of the Story-Writing Program Self-Test Exercises for Section 6.2 6.3 The STL恠 Algorithms and Use of Iterators STL Algorithms Standard Categories of Iterators Iterators for Arrays Self-Test Exercises for Section 6.3 6.4 The Node Template Class Functions That Return a Reference Type What Happens When a Reference Return Value Is Copied Elsewhere The Data Member Function Now Requires Two Versions Header and Implementation Files for the New Node Self-Test Exercises for Section 6.4 6.5 An Iterator for Linked Lists The Node Iterator The Node Iterator Is Derived from std::iterator Pitfall:std::iterator Might Not Exist The Node Iterator恠 Private Member Variable Node Iterator凜onstructor Node Iterator則he*Operator Node Iterator凾wo Versions of the ++ Operator Programming Tip:++p Is More Efficient Than p++ Iterators for Constant Collections Programming Tip:When to Use a Const Iterator Self-Test Exercises for Section 6.5 6.6 Linked-List Version of the Bag Template Class with an Iterator How to Provide an Iterator for a Container Class That You Write The Bag Iterator Why the Iterator Is Defined Inside the Bag Self-Test Exercises for Section 6.6 Chapter Summary and Summary of the Five Bags Solutions to Self-Test Exercises Programming Projects CHAPTER 7 STACKS 7.1 The STL Stack Class The Standard Library Stack Class Programming Example:Reversing a Word Self-Test Exercises for Section 7.1 7.2 Stack Applications Programming Example:Balanced Parentheses Programming Example:Evaluating Arithmetic Expressions Evaluating Arithmetic Expressions凷pecification Evaluating Arithmetic Expressions凞esign Evaluating Arithmetic Expressions処mplementation Functions Used in the Calculator Program Evaluating Arithmetic Expressions凾esting and Analysis Evaluating Arithmetic Expressions凟nhancements Self-Test Exercises for Section 7.2 7.3 Implementations of the Stack Class Array Implementation of a Stack Linked-List Implementation of a Stack The Koenig Lookup Self-Test Exercises for Section 7.3 7.4 More Complex Stack Applications Evaluating Postfix Expressions Translating Infix to Postfix Notation Using Precedence Rules in the Infix Expression Correctness of the Conversion from Infix to Postfix Self-Test Exercises for Section 7.4 Chapter Summary Solutions to Self-Test Exercises Programming Projects CHAPTER 8 QUEUES 8.1 The STL Queue The Standard Library Queue Class Uses for Queues Self-Test Exercises for Section 8.1 8.2 Queue Applications Programming Example:Recognizing Palindromes Self-Test Exercises for Middle of Section 8.2 Programming Example:Car Wash Simulation Car Wash Simulation凷pecification Car Wash Simulation凞esign Car Wash Simulation処mplementing the Car Wash Classes Car Wash Simulation処mplementing the Simulation Function Self-Test Exercises for End of Section 8.2 8.3 Implementations of the Queue Class Array Implementation of a Queue Programming Tip:Use Small Helper Functions to Improve Clarity Discussion of the Circular Array Implementation of a Queue Linked-List Implementation of a Queue Implementation Details Programming Tip:Make Note of 岲on恡 Care

显示全部信息

在线试读部分章节

The Phases of
1
Software Development
chapter
Chapter the first which explains how, why, when, and where there was ever any problem in the first place
NOEL LANGLEY
The Land of Green Ginger
LEARNING OBJECTIVES
When you complete Chapter 1, you will be able to...
write precondition/postcondition contracts for small functions, and use the C++ assert facility to test preconditions.
recognize quadratic, linear, and logariindicesthmic running time behavior in simple algorithms, and write bigO expressions to describe this behavior.
create and recognize test data that is appropriate for simple problems, including testing boundary conditions and fully exercising code.
CHAPTER CONTENTS
1.1 Specification, Design, Implementation
1.2 Running Time Analysis
1.3 Testing and Debugging Chapter Summary Solutions to SelfTest Exercises
Chapter 1 / The Phases of Software Development
the phases blur into each other

The Phases of 1 Software Development chapter Chapter the first which explains how, why, when, and where there was ever any problem in the first place NOEL LANGLEY The Land of Green Ginger LEARNING OBJECTIVES When you complete Chapter 1, you will be able to... write precondition/postcondition contracts for small functions, and use the C++ assert facility to test preconditions. recognize quadratic, linear, and logariindicesthmic running time behavior in simple algorithms, and write bigO expressions to describe this behavior. create and recognize test data that is appropriate for simple problems, including testing boundary conditions and fully exercising code. CHAPTER CONTENTS 1.1 Specification, Design, Implementation 1.2 Running Time Analysis 1.3 Testing and Debugging Chapter Summary Solutions to SelfTest Exercises Chapter 1 / The Phases of Software Development the phases blur into each other This chapter illustrates the phases of software development.These phases occur in all software, including the small programs that you’ll seein this first chapter. In subsequent chapters, you’ll go beyond these small pro-grams, applying the phases of software development to organized collections ofdata. These organized collections of data are called data structures, and the main topics of this book revolve around proven techniques for representing andmanipulating such data structures. Years from now you may be a software engineer writing large systems in aspecialized area, perhaps computer graphics or artificial intelligence. Suchfuturistic applications will be exciting and stimulating, and within your workyou will still see the phases of software development and fundamental datastructures that you learn and practice now. Here is a list of the phases of software development:: The Phases of Software Development Specification of the task Design of a solution Implementation (coding) of the solution Analysis of the solution Testing and debugging Maintenance and evolution of the system Obsolescence Do not memorize this list: Throughout the book, your practice of these phaseswill achieve far better familiarity than mere memorization. Also, memorizing an“official list” is misleading because it suggests that there is a single sequence ofdiscrete steps that always occur one after another. In practice, the phases blurinto each other; for instance, the analysis of a solution’s efficiency may occurhand in hand with the design, before any coding. Or low-level design decisionsmay be postponed until the implementation phase. Also, the phases might notoccur one after another. Typically there is back-and-forth travel between thephases. Most of the work in software development does not depend on any particularprogramming language. Specification, design, and analysis can all be carried outwith few or no ties to a particular programming language. Nevertheless, when weget down to implementation details, we do need to decide on one particular pro-gramming language. The language we use in this book is C++. Specification, Design, Implementation 33 What You Should Know About C++ Before Starting This Text The C++ language was designed by Bjarne Stroustrup at AT&T Bell Lab-oratories as an extension of the C language, with the purpose of supporting object-oriented programming (OOP)—a technique that encourages important strategies of information hiding and component reuse. Throughout this book, we introduce you to important OOP principles to use in your designs and imple-mentations. There are many different C++ compilers that you may successfully use with this text. Ideally, the compiler should support the latest features of the ANSI/ISO C++ Standard, which we have incorporated into the text. However, there are sev-eral workarounds that can be applied to older compilers that don’t fully support the standard. (See Appendix K, “Downloading the GNU Compiler Software,” and Appendix E, “Dealing with Older Compilers.”) Whichever programming environment you use, you should already be com-fortable writing, compiling, and running short C++ programs built with a top-down design. You should know how to use the built-in types (the number types, char, and bool), and you should be able to use arrays. Throughout the text, we will introduce the important roles of the C++ Stan-dard Library, though you do not need any previous knowledge of the library. Studying the data structures of the Standard Library can help you understand trade-offs between different approaches, and can guide the design and imple-mentation of your own data structures. When you are designing your own data structures, an approach that is compliant with the Standard Library has twofold benefits: Other programmers will understand your work more easily, and your own work will readily benefit from other pieces of the Standard Library, such as the standard searching and sorting algorithms. The rest of this chapter will prepare you to tackle the topic of data structures in C++, using an approach that is compliant with the Standard Library. Section 1.1 focuses on a technique for specifying program behavior, and you’ll also see some hints about design and implementation. Section 1.2 illustrates a particular kind of analysis: the running time analysis of a program. Section 1.3 provides some techniques for testing and debugging programs. 1.1 SPECIFICATION, DESIGN, IMPLEMENTATION One begins with a list of difficult design decisions which are likely to change. Each module is then designed to hide such a decision from the others. D. L. PARNAS “On the Criteria to Be Used in Decomposing Systems into Modules” OOP supports information hiding and component reuse you should already know how to write, compile, and run short C++ programs C++ Standard Library CONVERSIONS FROM -50.0 to 50.0 Celsius -50.0C -40.0C -30.0C -20.0C -10.0C 0.0C 10.0C 20.0C 30.0C 40.0C 50.0C Break down a task into a few subtasks; then decompose each subtask into smaller subtasks. Fahrenheit The actual Fahrenheit temperatures will be computed and displayed on this side of the table. As an example of software development in action, let’s examine the specification, design, and implementation for a particular problem. The specification is a precise description of the problem; the design phase consists of formulating the steps to solve the problem; the imple-mentation is the actual C++ code that carries out the design. The problem we have in mind is to display a table for converting Celsius temperatures to Fahrenheit, similar to the table shown in the margin. For a small problem, a sample of the desired output is a sufficient specification. Such a sample is a good specification because it is precise, leaving no doubt about what the program must accomplish. The next step is to design a solution. An algorithm is a set of instructions for solving a problem. An algorithm for the temperature problem will print the conversion table. During the design of the algorithm, the details of a particular programming language can be distracting, and can obscure the simplicity of a solution. Therefore, during the design we generally write in English. We use a rather corrupted kind of English that mixes in C++ when it’s convenient. This mixture of English and a programming language is called pseudocode. When the C++ code for a step is obvious, then the pseudocode may use C++. When a step is clearer in English, then we will use English. Keep in mind that the reason for pseudocode is to improve clarity. We’ll use pseudocode to design a solution for the temperature problem, and we’ll also use the important design technique of decomposing the problem. Design Concept: Decomposing the Problem A good technique for designing an algorithm is to break down the problem at hand into a few subtasks, then decompose each subtask into smaller subtasks, then replace the smaller subtasks with even smaller subtasks, and so forth. Eventually the subtasks become so small that they are trivial to implement in C++ or what-ever language you are using. When the algorithm is translated into C++, each subtask is implemented as a separate C++ function. In other programming lan-guages, functions are called “methods” or “procedures,” but it all boils down to the same thing: The large problem is decomposed into subtasks, and subtasks are implemented as separate pieces of your program. For example, the temperature problem has at least two good subtasks: (1) converting a temperature from Celsius degrees to Fahrenheit, and (2) printing a line of the conversion table in the specified format. Using these subproblems, the first draft of our pseudocode might look like this: Specification, Design, Implementation 35 1. Do preliminary work to open and set up the output device properly. 2. Display the labels at the top of the table. 3. For each line in the table (using variables celsius and fahrenheit): a. Set celsius equal to the next Celsius temperature of the table. b. fahrenheit = the celsius temperature converted to Fahrenheit. c. Print the Celsius and Fahrenheit values with labels on an output line. We have identified the major subtasks. But aren’t there other ways to decom-what makes a pose the problem into subtasks? What are the aspects of a good decomposition? goodOne primary guideline is that the subtasks should help you produce short decomposition? pseudocode—no more than a page of succinct description to solve the entire problem, and ideally much less than a page. In your designs, you can also keep in mind two considerations for selecting good subtasks: the potential for code reuse, and the possibility of future changes to the program. Let’s see how our subtasks embody these considerations. Step 1 opens an output device, making it ready for output in a particular form. code reuse This is a common operation that many programs must carry out. If we write a function for Step 1 with sufficient flexibility, we can probably reuse the function in other programs. This is an example of code reuse, in which a function is writ-ten with sufficient generality that it can be reused elsewhere. In fact, program-mers often produce collections of related C++ functions that are made available in packages to be reused over and over with many different application programs. Later we will use the C++ Standard Library as this sort of package, and we will also write our own packages of this kind. For now, just keep in mind that the function for Step 1 should be written with some reuse in mind. Decomposing problems also produces a good final program in the sense that easily modified the program is easy to understand, and subsequent maintenance and modifica-code tions are relatively easy. Our temperature program might be modified to convert to Kelvin degrees instead of Fahrenheit, or even to do a completely different con-version such as feet to meters. If the conversion task is performed by a separate function, much of the modification will be confined to this one function. Easily modified code is vital since real-world studies show that a large proportion of programmers’ time is spent maintaining and modifying existing programs. In order for a problem decomposition to produce easily modified code, thefunctions that you write need to be genuinely separated from one another. Ananalogy can help explain the notion of “genuinely separated.” Suppose you aremoving a bag of gold coins to a safe hiding place. If the bag is too heavy to carry,you might divide the coins into three smaller bags and carry the bags one by one.Unless you are a character in a comedy, you would not try to carry all three bagsat once. That would defeat the purpose of dividing the coins into three groups.This strategy works only if you carry the bags one at a time. Something similarhappens in problem decomposition. If you divide your programming task intothree subtasks and solve these subtasks by writing three functions, then you have procedural abstraction traded one hard problem for three easier problems. Your total job has becomeeasier—provided that you design the functions separately. When you are work-ing on one function, you should not worry about how the other functions performtheir jobs. But the functions do interact. So when you are designing one function,you need to know something about what the other functions do. The trick is toknow only as much as you need, but no more. This is called information hiding. One technique for incorporating information hiding involves specifying yourfunctions’ behavior using preconditions and postconditions. Preconditions and Postconditions When you write a complete function definition, you specify how the functionperforms its computation. However, when you are using a function, you onlyneed to think about what the function does. You need not think about how the function does its work. For example, suppose you are writing the temperatureconversion program and you are told that a function is available for you to use,as described here: // Convert a Celsius temperature c to Fahrenheit degreesdouble celsius_to_fahrenheit(double c); Your program might have a double variable called celsius that contains a Cel-sius temperature. Knowing this description, you can confidently write the fol-lowing statement to convert the temperature to Fahrenheit degrees, storing theresult in a double variable called fahrenheit: fahrenheit = celsius_to_fahrenheit(celsius); When you use the celsius_to_fahrenheit function, you do not need to knowthe details of how the function carries out its work. You need to know what the function does, but you do not need to know how the task is accomplished. When we pretend that we do not know how a function is implemented, we areusing a form of information hiding called procedural abstraction. This tech-nique simplifies your reasoning by abstracting away irrelevant details—that is,by hiding the irrelevant details. When programming in C++, it might make moresense to call it “functional abstraction,” since you are abstracting away irrelevantdetails about how a function works. However, the term procedure is a more gen-eral term than function. Computer scientists use the term procedure for anysequence of instructions, and so they use the term procedural abstraction. Pro-cedural abstraction can be a powerful tool. It simplifies your reasoning by allow-ing you to consider functions one at a time rather than all together. To make procedural abstraction work for us, we need some techniques for documenting what a function does without indicating how the function works. We could just write a short comment as we did for celsius_to_fahrenheit. However, the short comment is a bit incomplete—for instance, the comment doesn’t indicate what happens if the parameter c is smaller than the lowest Celsius temperature (.273.15°C,which is absolute zero for Celsius temperatures).

显示全部信息

数据结构——C++版（第四版）（英文影印版）下载

数据结构——C++版（第四版）（英文影印版）

发布书评

相关图书推荐