第1页 / 共734页
第2页 / 共734页
第3页 / 共734页
第4页 / 共734页
第5页 / 共734页
第6页 / 共734页
第7页 / 共734页
第8页 / 共734页
数据结构与程序设计——C++语言描述（英文版）.pdf
Navigating the Disk
Hints for Page Navigation
Synopsis
Course Structure
Supplementary Materials
Book Production
Acknowledgments
1 Programming Principles
1.1 Introduction
1.2 The Game of Life
1.2.1 Rules for the Game of Life
1.2.2 Examples
1.2.3 The Solution: Classes, Objects, and Methods
1.2.4 Life: The Main Program
1.3 Programming Style
1.3.1 Names
1.3.2 Documentation and Format
1.3.3 Refinement and Modularity
1.4 Coding, Testing, and Further Refinement
1.4.1 Stubs
1.4.2 Definition of the Class Life
1.4.3 Counting Neighbors
1.4.4 Updating the Grid
1.4.5 Input and Output
1.4.6 Drivers
1.4.7 Program Tracing
1.4.8 Principles of Program Testing
1.5 Program Maintenance
1.5.1 Program Evaluation
1.5.2 Review of the Life Program
1.5.3 Program Revision and Redevelopment
1.6 Conclusions and Preview
1.6.1 Software Engineering
1.6.2 Problem Analysis
1.6.3 Requirements Specification
1.6.4 Coding
Pointers and Pitfalls
Review Questions
References for Further Study
C++
Programming Principles
The Game of Life
Software Engineering
2 Introduction to Stacks
2.1 Stack Specifications
2.1.1 Lists and Arrays
2.1.2 Stacks
2.1.3 First Example: Reversing a List
2.1.4 Information Hiding
2.1.5 The Standard Template Library
2.2 Implementation of Stacks
2.2.1 Specification of Methods for Stacks
2.2.2 The Class Specification
2.2.3 Pushing, Popping, and Other Methods
2.2.4 Encapsulation
2.3 Application: A Desk Calculator
2.4 Application: Bracket Matching
2.5 Abstract Data Types and Their Implementations
2.5.1 Introduction
2.5.2 General Definitions
2.5.3 Refinement of Data Specification
Pointers and Pitfalls
Review Questions
References for Further Study
3 Queues
3.1 Definitions
3.1.1 Queue Operations
3.1.2 Extended Queue Operations
3.2 Implementations of Queues
3.3 Circular Implementation of Queues in C++
3.4 Demonstration and Testing
3.5 Application of Queues: Simulation
3.5.1 Introduction
3.5.2 Simulation of an Airport
3.5.3 Random Numbers
3.5.4 The Runway Class Specification
3.5.5 The Plane Class Specification
3.5.6 Functions and Methods of the Simulation
3.5.7 Sample Results
Pointers and Pitfalls
Review Questions
References for Further Study
4 Linked Stacks and Queues
4.1 Pointers and Linked Structures
4.1.1 Introduction and Survey
4.1.2 Pointers and Dynamic Memory in C++
4.1.3 The Basics of Linked Structures
4.2 Linked Stacks
4.3 Linked Stacks with Safeguards
4.3.1 The Destructor
4.3.2 Overloading the Assignment Operator
4.3.3 The Copy Constructor
4.3.4 The Modified Linked-Stack Specification
4.4 Linked Queues
4.4.1 Basic Declarations
4.4.2 Extended Linked Queues
4.5 Application: Polynomial Arithmetic
4.5.1 Purpose of the Project
4.5.2 The Main Program
4.5.3 The Polynomial Data Structure
4.5.4 Reading and Writing Polynomials
4.5.5 Addition of Polynomials
4.5.6 Completing the Project
4.6 Abstract Data Types and Their Implementations
Pointers and Pitfalls
Review Questions
5 Recursion
5.1 Introduction to Recursion
5.1.1 Stack Frames for Subprograms
5.1.2 Tree of Subprogram Calls
5.1.3 Factorials: A Recursive Definition
5.1.4 Divide and Conquer: The Towers of Hanoi
5.2 Principles of Recursion
5.2.1 Designing Recursive Algorithms
5.2.2 How Recursion Works
5.2.3 Tail Recursion
5.2.4 When Not to Use Recursion
5.2.5 Guidelines and Conclusions
5.3 Backtracking: Postponing the Work
5.3.1 Solving the Eight-Queens Puzzle
5.3.2 Example: Four Queens
5.3.3 Backtracking
5.3.4 Overall Outline
5.3.5 Refinement: The First Data Structure and Its Methods
5.3.6 Review and Refinement
5.3.7 Analysis of Backtracking
5.4 Tree-Structured Programs: Look-Ahead in Games
5.4.1 Game Trees
5.4.2 The Minimax Method
5.4.3 Algorithm Development
5.4.4 Refinement
5.4.5 Tic-Tac-Toe
Pointers and Pitfalls
Review Questions
References for Further Study
6 Lists and Strings
6.1 List Definition
6.1.1 Method Specifications
6.2 Implementation of Lists
6.2.1 Class Templates
6.2.2 Contiguous Implementation
6.2.3 Simply Linked Implementation
6.2.4 Variation: Keeping the Current Position
6.2.5 Doubly Linked Lists
6.2.6 Comparison of Implementations
6.3 Strings
6.3.1 Strings in C++
6.3.2 Implementation of Strings
6.3.3 Further String Operations
6.4 Application: A Text Editor
6.4.1 Specifications
6.4.2 Implementation
6.5 Linked Lists in Arrays
6.6 Application: par penalty -500 Generating Permutations
Pointers and Pitfalls
Review Questions
References for Further Study
7 Searching
7.1 Searching: Introduction and Notation
7.2 Sequential Search
7.3 Binary Search
7.3.1 Ordered Lists
7.3.2 Algorithm Development
7.3.3 The Forgetful Version
7.3.4 Recognizing Equality
7.4 Comparison Trees
7.4.1 Analysis for $n = 10$
7.4.2 Generalization
7.4.3 Comparison of Methods
7.4.4 A General Relationship
7.5 Lower Bounds
7.6 Asymptotics
7.6.1 Introduction
7.6.2 Orders of Magnitude
7.6.3 The Big-O and Related Notations
7.6.4 Keeping the Dominant Term
Pointers and Pitfalls
Review Questions
References for Further Study
8 Sorting
8.1 Introduction and Notation
8.1.1 Sortable Lists
8.2 Insertion Sort
8.2.1 Ordered Insertion
8.2.2 Sorting by Insertion
8.2.3 Linked Version
8.2.4 Analysis
8.3 Selection Sort
8.3.1 The Algorithm
8.3.2 Contiguous Implementation
8.3.3 Analysis
8.3.4 Comparisons
8.4 Shell Sort
8.5 Lower Bounds
8.6 Divide-and-Conquer Sorting
8.6.1 The Main Ideas
8.6.2 An Example
8.7 Mergesort for Linked Lists
8.7.1 The Functions
8.7.2 Analysis of Mergesort
8.8 Quicksort for Contiguous Lists
8.8.1 The Main Function
8.8.2 Partitioning the List
8.8.3 Analysis of Quicksort
8.8.4 Average-Case Analysis of Quicksort
8.8.5 Comparison with Mergesort
8.9 Heaps and Heapsort
8.9.1 Two-Way Trees as Lists
8.9.2 Development of Heapsort
8.9.3 Analysis of Heapsort
8.9.4 Priority Queues
8.10 Review: Comparison of Methods
Pointers and Pitfalls
Review Questions
References for Further Study
9 Tables and Information Retrieval
9.1 Introduction: Breaking the lowercase {lg n} Barrier
9.2 Rectangular Tables
9.3 Tables of Various Shapes
9.3.1 Triangular Tables
9.3.2 Jagged Tables
9.3.3 Inverted Tables
9.4 Tables: A New Abstract Data Type
9.5 Application: Radix Sort
9.5.1 The Idea
9.5.2 Implementation
9.5.3 Analysis
9.6 Hashing
9.6.1 Sparse Tables
9.6.2 Choosing a Hash Function
9.6.3 Collision Resolution with Open Addressing
9.6.4 Collision Resolution by Chaining
9.7 Analysis of Hashing
9.8 Conclusions: Comparison of Methods
9.9 Application: The Life Game Revisited
9.9.1 Choice of Algorithm
9.9.2 Specification of Data Structures
9.9.3 The Life Class
9.9.4 The Life Functions
Pointers and Pitfalls
Review Questions
References for Further Study
10 Binary Trees
10.1 Binary Trees
10.1.1 Definitions
10.1.2 Traversal of Binary Trees
10.1.3 Linked Implementation of Binary Trees
10.2 Binary Search Trees
10.2.1 Ordered Lists and Implementations
10.2.2 Tree Search
10.2.3 Insertion into a Binary Search Tree
10.2.4 Treesort
10.2.5 Removal from a Binary Search Tree
10.3 Building a Binary Search Tree
10.3.1 Getting Started
10.3.2 Declarations and the Main Function
10.3.3 Inserting a Node
10.3.4 Finishing the Task
10.3.5 Evaluation
10.3.6 Random Search Trees and Optimality
10.4 Height Balance: AVL Trees
10.4.1 Definition
10.4.2 Insertion of a Node
10.4.3 Removal of a Node
10.4.4 The Height of an AVL Tree
10.5 Splay Trees: A Self-Adjusting Data Structure
10.5.1 Introduction
10.5.2 Splaying Steps
10.5.3 Algorithm Development
10.5.4 Amortized Algorithm Analysis: Introduction
10.5.5 Amortized Analysis of Splaying
Pointers and Pitfalls
Review Questions
References for Further Study
11 Multiway Trees
11.1 Orchards, Trees, and Binary Trees
11.1.1 On the Classification of Species
11.1.2 Ordered Trees
11.1.3 Forests and Orchards
11.1.4 The Formal Correspondence
11.1.5 Rotations
11.1.6 Summary
11.2 Lexicographic Search Trees: Tries
11.2.1 Tries
11.2.2 Searching for a Key
11.2.3 C++ Algorithm
11.2.4 Searching a Trie
11.2.5 Insertion into a Trie
11.2.6 Deletion from a Trie
11.2.7 Assessment of Tries
11.3 External Searching: B-Trees
11.3.1 Access Time
11.3.2 Multiway Search Trees
11.3.3 Balanced Multiway Trees
11.3.4 Insertion into a B-Tree
11.3.5 C++ Algorithms: Searching and Insertion
11.3.6 Deletion from a B-Tree
11.4 Red-Black Trees
11.4.1 Introduction
11.4.2 Definition and Analysis
11.4.3 Red-Black Tree Specification
11.4.4 Insertion
11.4.5 Insertion Method Implementation
11.4.6 Removal of a Node
Pointers and Pitfalls
Review Questions
References for Further Study
12 Graphs
12.1 Mathematical Background
12.1.1 Definitions and Examples
12.1.2 Undirected Graphs
12.1.3 Directed Graphs
12.2 Computer Representation
12.2.1 The Set Representation
12.2.2 Adjacency Lists
12.2.3 Information Fields
12.3 Graph Traversal
12.3.1 Methods
12.3.2 Depth-First Algorithm
12.3.3 Breadth-First Algorithm
12.4 Topological Sorting
12.4.1 The Problem
12.4.2 Depth-First Algorithm
12.4.3 Breadth-First Algorithm
12.5 A Greedy Algorithm: Shortest Paths
12.5.1 The Problem
12.5.2 Method
12.5.3 Example
12.5.4 Implementation
12.6 Minimal Spanning Trees
12.6.1 The Problem
12.6.2 Method
12.6.3 Implementation
12.6.4 Verification of Prim's Algorithm
12.7 Graphs as Data Structures
Pointers and Pitfalls
Review Questions
References for Further Study
13 Case Study: The Polish Notation
13.1 The Problem
13.1.1 The Quadratic Formula
13.2 The Idea
13.2.1 Expression Trees
13.2.2 Polish Notation
13.3 Evaluation of Polish Expressions
13.3.1 Evaluation of an Expression in Prefix Form
13.3.2 C++ Conventions
13.3.3 C++ Function for Prefix Evaluation
13.3.4 Evaluation of Postfix Expressions
13.3.5 Proof of the Program: Counting Stack Entries
13.3.6 Recursive Evaluation of Postfix Expressions
13.4 Translation from Infix Form to Polish Form
13.5 An Interactive Expression Evaluator
13.5.1 Overall Structure
13.5.2 Representation of the Data: Class Specifications
13.5.3 Tokens
13.5.4 The Lexicon
13.5.5 Expressions: Token Lists
13.5.6 Auxiliary Evaluation Functions
13.5.7 Graphing the Expression: The Class Plot
13.5.8 A Graphics-Enhanced Plot Class
References for Further Study
A Mathematical Methods
A.1 Sums of Powers of Integers
A.2 Logarithms
A.2.1 Definition of Logarithms
A.2.2 Simple Properties
A.2.3 Choice of Base
A.2.4 Natural Logarithms
A.2.5 Notation
A.2.6 Change of Base
A.2.7 Logarithmic Graphs
A.2.8 Harmonic Numbers
A.3 Permutations, Combinations, Factorials
A.3.1 Permutations
A.3.2 Combinations
A.3.3 Factorials
A.4 Fibonacci Numbers
A.5 Catalan Numbers
A.5.1 The Main Result
A.5.2 The Proof by One-to-One Correspondences
A.5.3 History
A.5.4 Numerical Results
References for Further Study
B Random Numbers
B.1 Introduction
B.2 Strategy
B.3 Program Development
References for Further Study
C Packages and Utility Functions
C.1 Packages and C++ Translation Units
C.2 Packages in the Text
C.3 The Utility Package
C.4 Timing Methods
D Programming Precepts, Pointers, and Pitfalls
D.1 Choice of Data Structures and Algorithms
D.1.1 Stacks
D.1.2 Lists
D.1.3 Searching Methods
D.1.4 Sorting Methods
D.1.5 Tables
D.1.6 Binary Trees
D.1.7 General Trees
D.1.8 Graphs
D.2 Recursion
D.3 Design of Data Structures
D.4 Algorithm Design and Analysis
D.5 Programming
D.6 Programming with Pointer Objects
D.7 Debugging and Testing
D.8 Maintenance
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Y
Z
Data Structures
and
Program Design
in C++
NAVIGATING THE DISK
For information on using the Acrobat toolbar and other Acrobat commands, consult
the Help document within Acrobat. See especially the section “Navigating Pages.”
Material displayed in green enables jumps to other locations in the book, to
transparency masters, and to run sample demonstration programs. These come in
three varieties:
The green menu boxes in the left margin of each page perform jumps to fre-
quently used parts of the book:
Green material in the text itself will jump to the place indicated. After taking
such a jump, you may return by selecting the // icon (go back) in the Acrobat
toolbar.
The transparency-projector icon (
) brings up a transparency master on the
current topic. Return by selecting the // icon (go back) in the Acrobat toolbar.
The Windows (
) icon in the left margin select and run a demonstration pro-
gram, which will operate only on the Windows platform.
This CD contains a folder textprog that contains the source code for all programs
and program segments appearing in the book. These files cannot be compiled
directly, but they can be copied and used for writing other programs.
HINTS FOR PAGE NAVIGATION
Each chapter (or other major section) of the book is in a separate pdf file, so
you may start Acrobat directly on a desired chapter.
To find a particular section in the current chapter, hit the Home key, or select
j/ in the Acrobat toolbar or
in the green menu bar, which will jump to the
first page of the chapter where there is a table of contents for the chapter.
After jumping to a new location in the book, you can easily return to your
previous location by selecting // (go back) in the Acrobat toolbar.
To find a particular topic, select the index icon (
To find a particular word in the current chapter, use the binoculars icon in the
Acrobat toolbar.
The PgDown and Enter (or Return) keys advance one screenful, whereas ., #,
!, and
advance one page. Of these, only will move from the last page of
one chapter to the first page of the next chapter.
To move backwards, PgUp and Shift+Enter move up one screenful, whereas
/, ", , and move back one page. Of these, only will move from the first
page of one chapter to the last page of the previous chapter.
) in the left margin.
Data Structures
and
Program Design
in C++
Robert L. Kruse
Alexander J. Ryba
CD-ROM prepared by
Paul A. Mailhot
Prentice Hall
Upper Saddle River, New Jersey 07458
Library of Congress Cataloging–in–Publication Data
KRUSE, ROBERT L.
p.
cm.
Data structures and program design in C++ / Robert L. Kruse,
Alexander J. Ryba.
Includes bibliographical references and index.
ISBN 0–13–087697–6
1. C++ (Computer program language) 2. Data Structures
(Computer Science)
1998
I. Ryba, Alexander J.
II. Title.
QA76.73.C153K79
005.13’3—dc21
98–35979
CIP
Publisher: Alan Apt
Editor in Chief: Marcia Horton
Acquisitions Editor: Laura Steele
Production Editor: Rose Kernan
Managing Editor: Eileen Clark
Art Director: Heather Scott
Assistant to Art Director: John Christiana
Copy Editor: Patricia Daly
Cover Designer: Heather Scott
Manufacturing Buyer: Pat Brown
Assistant Vice President of Production and
Manufacturing: David W. Riccardi
Editorial Assistant: Kate Kaibni
Interior Design: Robert L. Kruse
Page Layout: Ginnie Masterson (PreTEX, Inc.)
Art Production: Blake MacLean (PreTEX, Inc.)
Cover art: Orange, 1923, by Wassily Kandinsky (1866-1944), Lithograph in Colors.
Source: Christie’s Images
© 2000 by Prentice-Hall, Inc.
Simon & Schuster/A Viacom Company
Upper Saddle River, New Jersey 07458
The typesetting for this book was done with PreTEX, a preprocessor and macro package for the TEX typesetting system
and the POSTSCRIPT page-description language. PreTEX is a trademark of PreTEX, Inc.; TEX is a trademark of the American
Mathematical Society; POSTSCRIPT is a registered trademarks of Adobe Systems, Inc.
The authors and publisher of this book have used their best efforts in preparing this book. These efforts include the re-
search, development, and testing of the theory and programs in the book to determine their effectiveness. The authors
and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documenta-
tion contained in this book. The authors and publisher shall not be liable in any event for incidental or consequential
damages in connection with, or arising out of, the furnishing, performance, or use of these programs.
All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writ-
ing from the publisher.
Printed in the United States of America
10
9
8
7 6 5
4
3
2
1
ISBN 0-13-087697-6
Prentice-Hall International (U.K.) Limited, London
Prentice-Hall of Australia Pty. Limited, Sydney
Prentice-Hall Canada Inc., Toronto
Prentice-Hall Hispanoamericana, S.A., Mexico
Prentice-Hall of India Private Limited, New Delhi
Prentice-Hall of Japan, Inc., Tokyo
Simon & Schuster Asia Pte. Ltd., Singapore
Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
Contents
Preface
ix
xii
Synopsis
Course Structure
Supplementary Materials
Book Production
Acknowledgments
xiv
xvi
xvi
1 Programming
Principles
1.1 Introduction
2
1.2 The Game of Life
4
1.4.7 Program Tracing
1.4.8 Principles of Program Testing
28
29
xv
1
1.5 Program Maintenance
34
1.5.1 Program Evaluation
34
1.5.2 Review of the Life Program
1.5.3 Program Revision
and Redevelopment
1.6 Conclusions and Preview
1.6.1 Software Engineering
1.6.2 Problem Analysis
1.6.3 Requirements Specification
1.6.4 Coding
40
41
38
39
39
1.2.1 Rules for the Game of Life
1.2.2 Examples
1.2.3 The Solution: Classes, Objects,
5
and Methods
7
1.2.4 Life: The Main Program
8
1.3 Programming Style
10
1.3.1 Names
1.3.2 Documentation and Format
1.3.3 Refinement and Modularity
10
1.4 Coding, Testing,
20
20
and Further Refinement
1.4.1 Stubs
1.4.2 Definition of the Class Life
1.4.3 Counting Neighbors
23
1.4.4 Updating the Grid
1.4.5 Input and Output
1.4.6 Drivers
24
25
27
4
13
15
22
Pointers and Pitfalls
Review Questions
References for Further Study
45
46
47
C++
Programming Principles
The Game of Life
47
Software Engineering
47
47
48
2 Introduction
to Stacks
2.1 Stack Specifications
2.1.1 Lists and Arrays
2.1.2 Stacks
2.1.3 First Example: Reversing a List
2.1.4 Information Hiding
2.1.5 The Standard Template Library
50
50
54
50
35
41
49
51
55
v
vi
Contents
2.2 Implementation of Stacks
57
2.2.1 Specification of Methods
for Stacks
57
2.2.2 The Class Specification
2.2.3 Pushing, Popping,
and Other Methods
63
2.2.4 Encapsulation
60
61
2.3 Application: A Desk Calculator
2.4 Application: Bracket Matching
66
69
2.5 Abstract Data Types
and Their Implementations
2.5.1 Introduction
71
2.5.2 General Definitions
2.5.3 Refinement of Data Specification
71
73
Pointers and Pitfalls
76
Review Questions
76
References for Further Study
77
3 Queues
3.1 Definitions
79
74
78
3.1.1 Queue Operations
3.1.2 Extended Queue Operations
79
81
3.2 Implementations of Queues
84
3.3 Circular Implementation
89
of Queues in C++
3.4 Demonstration and Testing
93
3.5 Application of Queues: Simulation
96
96
3.5.1 Introduction
3.5.2 Simulation of an Airport
3.5.3 Random Numbers
99
3.5.4 The Runway Class Specification
3.5.5 The Plane Class Specification
3.5.6 Functions and Methods
96
of the Simulation
101
99
100
3.5.7 Sample Results
107
Pointers and Pitfalls
110
Review Questions
110
References for Further Study
111
4 Linked Stacks
and Queues
4.1 Pointers and Linked Structures
113
4.1.1 Introduction and Survey
4.1.2 Pointers and Dynamic Memory
113
in C++
116
4.1.3 The Basics of Linked Structures
112
122
131
141
144
157
158
170
136
139
4.2 Linked Stacks
4.3 Linked Stacks with Safeguards
127
4.3.1 The Destructor
4.3.2 Overloading the
131
Assignment Operator
4.3.3 The Copy Constructor
4.3.4 The Modified
Linked-Stack Specification
132
135
4.4 Linked Queues
137
4.4.1 Basic Declarations
137
4.4.2 Extended Linked Queues
4.5 Application: Polynomial Arithmetic
141
4.5.1 Purpose of the Project
4.5.2 The Main Program
4.5.3 The Polynomial Data Structure
4.5.4 Reading and Writing
147
Polynomials
141
4.5.5 Addition of Polynomials
4.5.6 Completing the Project
148
150
4.6 Abstract Data Types
and Their Implementations
152
Pointers and Pitfalls
Review Questions
154
155
5 Recursion
5.1 Introduction to Recursion
158
5.1.1 Stack Frames for Subprograms
5.1.2 Tree of Subprogram Calls
5.1.3 Factorials:
159
A Recursive Definition
160
5.1.4 Divide and Conquer:
The Towers of Hanoi
163
5.2 Principles of Recursion
170
5.2.1 Designing Recursive Algorithms
5.2.2 How Recursion Works
5.2.3 Tail Recursion
174
5.2.4 When Not to Use Recursion
5.2.5 Guidelines and Conclusions
171
176
180
5.3 Backtracking: Postponing the Work
5.3.1 Solving the Eight-Queens Puzzle
5.3.2 Example: Four Queens
5.3.3 Backtracking
5.3.4 Overall Outline
5.3.5 Refinement: The First Data Structure
184
185
186
183
183
191
194
199
201
and Its Methods
188
5.3.6 Review and Refinement
5.3.7 Analysis of Backtracking
198
5.4 Tree-Structured Programs:
198
Look-Ahead in Games
5.4.1 Game Trees
5.4.2 The Minimax Method
5.4.3 Algorithm Development
5.4.4 Refinement
5.4.5 Tic-Tac-Toe
Pointers and Pitfalls
Review Questions
References for Further Study
203
204
209
210
6 Lists and
Strings
6.1 List Definition
213
6.1.1 Method Specifications
211
214
6.2 Implementation of Lists
217
6.2.1 Class Templates
6.2.2 Contiguous Implementation
6.2.3 Simply Linked Implementation
6.2.4 Variation: Keeping the Current
218
Position
225
6.2.5 Doubly Linked Lists
6.2.6 Comparison of Implementations
227
6.3 Strings
233
6.3.1 Strings in C++
6.3.2 Implementation of Strings
6.3.3 Further String Operations
233
242
6.4 Application: A Text Editor
242
6.4.1 Specifications
6.4.2 Implementation
6.5 Linked Lists in Arrays
6.6 Application:
243
251
Generating Permutations
260
Pointers and Pitfalls
Review Questions
References for Further Study
265
266
7 Searching
7.1 Searching:
Contents
vii
268
Introduction and Notation
269
7.2 Sequential Search
271
7.3 Binary Search
278
7.3.1 Ordered Lists
7.3.2 Algorithm Development
7.3.3 The Forgetful Version
7.3.4 Recognizing Equality
278
280
281
284
7.4 Comparison Trees
286
7.4.1 Analysis for n 10
7.4.2 Generalization
7.4.3 Comparison of Methods
7.4.4 A General Relationship
290
287
294
296
7.5 Lower Bounds
297
7.6 Asymptotics
302
7.6.1 Introduction
302
7.6.2 Orders of Magnitude
7.6.3 The Big-O
and Related Notations
304
310
7.6.4 Keeping the Dominant Term
311
Pointers and Pitfalls
Review Questions
References for Further Study
314
315
8 Sorting
316
317
8.1 Introduction and Notation
319
8.1.1 Sortable Lists
318
212
219
221
230
234
238
8.2 Insertion Sort
320
8.2.1 Ordered Insertion
8.2.2 Sorting by Insertion
8.2.3 Linked Version
8.2.4 Analysis
325
323
320
321
8.3 Selection Sort
329
8.3.1 The Algorithm
8.3.2 Contiguous Implementation
8.3.3 Analysis
8.3.4 Comparisons
329
331
332
330
267
8.4 Shell Sort
333
8.5 Lower Bounds
336
viii
Contents
8.6 Divide-and-Conquer Sorting
339
8.6.1 The Main Ideas
8.6.2 An Example
340
8.7 Mergesort for Linked Lists
8.7.1 The Functions
345
8.7.2 Analysis of Mergesort
344
348
8.8 Quicksort for Contiguous Lists
352
353
356
8.8.1 The Main Function
8.8.2 Partitioning the List
8.8.3 Analysis of Quicksort
8.8.4 Average-Case Analysis of
Quicksort
358
8.8.5 Comparison with Mergesort
352
360
8.9 Heaps and Heapsort
363
8.9.1 Two-Way Trees as Lists
8.9.2 Development of Heapsort
8.9.3 Analysis of Heapsort
8.9.4 Priority Queues
369
368
363
365
8.10 Review: Comparison of Methods
Pointers and Pitfalls
Review Questions
References for Further Study
375
376
377
372
9 Tables and Information
Retrieval
9.1 Introduction:
Breaking the lg n Barrier
380
379
339
9.8 Conclusions:
Comparison of Methods
417
9.9 Application:
418
418
The Life Game Revisited
9.9.1 Choice of Algorithm
9.9.2 Specification of Data Structures
9.9.3 The Life Class
9.9.4 The Life Functions
426
421
421
Pointers and Pitfalls
Review Questions
References for Further Study
427
428
419
10 Binary Trees
10.1 Binary Trees
430
430
10.1.1 Definitions
10.1.2 Traversal of Binary Trees
10.1.3 Linked Implementation
437
444
of Binary Trees
10.2 Binary Search Trees
10.2.1 Ordered Lists
429
432
and Implementations
446
10.2.2 Tree Search
10.2.3 Insertion into a Binary Search
447
Tree
451
10.2.4 Treesort
10.2.5 Removal from a Binary Search
453
Tree
455
9.2 Rectangular Tables
9.3 Tables of Various Shapes
381
9.3.1 Triangular Tables
9.3.2 Jagged Tables
9.3.3 Inverted Tables
385
386
383
383
9.4 Tables: A New Abstract Data Type
9.5 Application: Radix Sort
391
9.5.1 The Idea
392
9.5.2 Implementation
396
9.5.3 Analysis
393
9.6 Hashing
397
9.6.1 Sparse Tables
9.6.2 Choosing a Hash Function
9.6.3 Collision Resolution with Open
397
399
Addressing
401
9.6.4 Collision Resolution by Chaining
9.7 Analysis of Hashing
411
10.3 Building a Binary Search Tree
464
10.3.1 Getting Started
10.3.2 Declarations
and the Main Function
10.3.3 Inserting a Node
10.3.4 Finishing the Task
10.3.5 Evaluation
469
10.3.6 Random Search Trees
466
467
and Optimality
470
463
465
10.4 Height Balance: AVL Trees
473
473
10.4.1 Definition
477
10.4.2 Insertion of a Node
10.4.3 Removal of a Node
484
10.4.4 The Height of an AVL Tree
10.5 Splay Trees:
A Self-Adjusting Data Structure
10.5.1 Introduction
10.5.2 Splaying Steps
10.5.3 Algorithm Development
490
491
485
490
495
388
406
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
