数据结构——C++版（第四版）（英文影印版） 下载 pdf 百度网盘 epub 免费 2025 电子书 mobi 在线

数据结构——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 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

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++版（第四版）（英文影印版）在线收听

在线购买地址：数据结构——C++版（第四版）（英文影印版）在线购买

暂无原文赏析，正在全力查找中！

暂无其它内容！