数据结构——C++版（第四版）（英文影印版） mobi 下载 网盘 caj lrf 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 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

Preconditi*** and Postconditi***

Using Functi*** 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 C***tants

Clarifying the C***t Keyword Part 1:Declared C***tants

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++ Functi***

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

Soluti*** to Self-Test Exercises

CHAPTER 2 ABSTRACT DATA TYPES AND C++ CLASSES

2.1 Classes and Members

Programming Example:The Throttle Class

Clarifying the C***t Keyword Part 2:C***tant Member Functi***

Using a Class

A Small Dem***tration Program for the Throttle Class

Implementing Member Functi***

Member Functi*** May Activate Other Members

Programming Tip:Style for Boolean Variables

Self-Test Exercises for Section 2.1

2.2 C***tructors

The Throttle恠 C***tructor

What Happens If You Write a Class with No C***tructors?

Programming Tip:Always Provide C***tructors

Revising the Throttle恠 Member Functi***

Inline Member Functi***

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 C***tructor Can Be Provided by Using Default Arguments

Parameters

Pitfall:Using a Wrong Argument Type for a Reference Parameter

Clarifying the C***t Keyword Part 3:C***t Reference Parameters

Programming Tip:Use c***t C***istently

When the Type of a Function恠 Return Value Is a Class

Self-Test Exercises for Section 2.4

2.5 *** Overloading

Overloading Binary Comparison ***s

Overloading Binary Arithmetic ***s

Overloading Output and Input ***s

Friend Functi***

Programming Tip:When to Use a Friend Function

The Point Class凱utting Things Together

Summary of *** Overloading

Self-Test Exercises for Section 2.5

2.6 The Standard Template Libary and the Pair Class

Chapter Summary

Soluti*** 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 C***t Keyword Part 4:Static Member C***tants

Older Compilers Do Not Support Initialization of Static Member C***tants

The Bag Class凞ocumentation

Documenting the Value Semantics

The Bag Class凞em***tration Program

The Bag Class凞esign

Pitfall:The value_type Must Have a Default C***tructor

The Invariant of a Class

The Bag Class処mplementation

Pitfall:Needing to Use the Full Type Name bag::size_type

Programming Tip:Make Asserti*** 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 In***ctive 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 I***tor

The Multiset Template Class

Some Multiset Members

I***tors and the[...)Pattern

Pitfall:Do Not Access an I***tor恠 Item After Reaching end()

Testing I***tors for Equality

Other Multiset Operati***

Invalid I***tors

Clarifying the C***t Keyword Part 5:C***t I***tors

Pitfall:Changing a Container Object Can Invalidate Its I***tors

Self-Test Exercises for Section 3.4

Chapter Summary

Soluti*** to Self-Test Exercises

Programming Projects

CHAPTER 4 POINTERS AND DYNAMIC ARRAYS

4.1 Pointers and Dynamic Memory

Pointer Variables

Using the Assignment *** with Pointers

Dynamic Variables and the new ***

Using new to Allocate Dynamic Arrays

The Heap and the bad_alloc Exception

The delete ***

Programming Tip:Define Pointer Types

Self-Test Exercises for Section 4.1

4.2 Pointers and Arrays as Parameters

Clarifying the C***t Keyword Part 6:C***t 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 Functi*** 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 C***tructor

Pitfall:Using Dynamic Memory Requires a Destructor,a Copy C***tructor,and an Overloaded Assignment ***

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

C***tructor for the String Class

Overloading the ***[]

Some Further Overloading

Other Operati*** for the String Class

The String Class凞esign

The String Class処mplementation

Dem***tration Program for the String Class

Chaining the Output ***

Declaring C***tant Objects

C***tructor-Generated Conversi***

Using Overloaded Operati*** in Expressi***

Our String Class Versus the C++ Library String Class

Self-Test Exercises for Section 4.5

4.6 Programming Project:The Polynomial

Chapter Summary

Soluti*** 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 C***tructor

The Node Member Functi***

The Member Selection ***

Clarifying the C***t Keyword Part 7:The C***t Keyword with a Pointer to a Node,and the Need for Two Versi*** of Some Member Functi***

Programming Tip:A Rule for a Node恠 C***tant Member Functi***

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:F***etting 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 *** 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 Suggesti***

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

Soluti*** to Self-Test Exercises

Programming Projects

CHAPTER 6 SOFTWARE DEVELOPMENT WITH TEMPLATES,ITERATORS,AND THE STL

6.1 Template Functi***

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 Functi***

Parameter Matching for Template Functi***

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 Functi*** 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 I***tors

STL Algorithms

Standard Categories of I***tors

I***tors for Arrays

Self-Test Exercises for Section 6.3

*** The Node Template Class

Functi*** That Return a Reference Type

What Happens When a Reference Return Value Is Copied Elsewhere

The Data Member Function Now Requires Two Versi***

Header and Implementation Files for the New Node

Self-Test Exercises for Section ***

6.5 An I***tor for Linked Lists

The Node I***tor

The Node I***tor Is Derived from std::i***tor

Pitfall:std::i***tor Might Not Exist

The Node I***tor恠 Private Member Variable

Node I***tor凜***tructor

Node I***tor則he****

Node I***tor凾wo Versi*** of the ++ ***

Programming Tip:++p Is More Efficient Than p++

I***tors for C***tant Collecti***

Programming Tip:When to Use a C***t I***tor

Self-Test Exercises for Section 6.5

6.6 Linked-List Version of the Bag Template Class with an I***tor

How to Provide an I***tor for a Container Class That You Write

The Bag I***tor

Why the I***tor Is Defined Inside the Bag

Self-Test Exercises for Section 6.6

Chapter Summary and Summary of the Five Bags

Soluti*** 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 Applicati***

Programming Example:Balanced Parentheses

Programming Example:Evaluating Arithmetic Expressi***

Evaluating Arithmetic Expressi***凷pecification

Evaluating Arithmetic Expressi***凞esign

Evaluating Arithmetic Expressi***処mplementation

Functi*** Used in the Calculator Program

Evaluating Arithmetic Expressi***凾esting and Analysis

Evaluating Arithmetic Expressi***凟nhancements

Self-Test Exercises for Section 7.2

7.3 Implementati*** 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 Applicati***

Evaluating Postfix Expressi***

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

Soluti*** 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 Applicati***

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 Implementati*** of the Queue Class

Array Implementation of a Queue

Programming Tip:Use Small Helper Functi*** 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 functi***, and use the C++ assert facility to test preconditi***.

recognize quadratic, linear, and logariindicesthmic running time behavior in *** algorithms, and write bigO expressi*** to describe this behavior.

create and recognize test data that is appropriate for *** problems, including testing boundary conditi*** and fully exercising code.

CHAPTER CONTENTS

1.1 Specification, Design, Implementation

1.2 Running Time Analysis

1.3 Testing and Debugging Chapter Summary Soluti*** 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 ***anized collecti*** ofdata. These ***anized collecti*** 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 enginee***riting large systems in ***ecialized area, perhaps computer graphics or artificial intelligence. Suchfuturistic applicati*** will be exciting and stimulating, and within you***orkyou 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 ***ysis of a solution’s efficiency may occurhand in hand with the design, before any coding. Or low-level design decisi***may 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 ***ysis 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 ***ing 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-mentati***.

There are many different C++ compilers that you may successfully use with this text. Ideally, the compiler should *** 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 *** 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 you***ork 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 chapte***ill 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 ***ysis: the running time ***ysis 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 decisi*** 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 ***s 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 c***ists 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 instructi*** 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++ o***hat-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, functi*** 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 othe***ays to decom-what makes a pose the problem into subtasks? What are the ***ects 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 c***iderati*** 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 c***iderati***.

Step 1 opens an output device, *** 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 collecti*** of related C++ functi*** that are made available in packages to be reused over and ove***ith many different application programs. Late***e 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 ti*** 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, thefuncti*** that you write need to be genuinely separated from one another. An***ogy 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 functi***, then you have

procedural abstraction

traded one hard problem for three easier problems. Your total job has becomeeasier—provided that you design the functi*** separately. When you are work-ing on one function, you should not worry about how the other functi*** performtheir jobs. But the functi*** do in***ct. So when you are designing one function,you need to know something about what the other functi*** 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 yourfuncti***’ behavior using preconditi*** and postconditi***.

Preconditi*** and Postconditi***

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 instructi***, 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 c***ider functi*** 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++版（第四版）（英文影印版）在线购买

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

暂无其它内容！