第1页 / 共976页
第2页 / 共976页
第3页 / 共976页
第4页 / 共976页
第5页 / 共976页
第6页 / 共976页
第7页 / 共976页
第8页 / 共976页
Algorithms Data Structures and Problem Solving with C++.pdf
Book Cover
Contents
Preface
Part I: Objects & C++
Chapter 1: Arrays, Pointers & Structures
1.1 What are Pointers, Arrays & Structures?
1.2 Arrays & Strings
1.2.1 First-Class Versus Second-Class Objects
1.2.2 Using the vector
1.2.3 Resizing a vector
1.2.4 push_back, size & capacity
1.2.5 Parameter-Passing Mechanisms
1.2.6 Primitive Arrays of Constants
1.2.7 Multidimensional Arrays
1.2.8 The Standard Library string Type
1.3 Pointer Syntax in C++
1.4 Dynamic Memory Management
1.4.1 The new Operator
1.4.2 Garbage Collection & delete
1.4.3 Stale Pointers, Double Deletion, and More
1.5 Reference Variables
1.6 Structures
1.6.1 Pointers to Structures
1.6.2 Exogenous Versus Indigenous Data and Shallow Versus Deep Copying
1.6.3 Noncontigious Lists: Linked Lists
Summary, Exercises etc
Objects of the Game
Common Errors
On the Internet
Exercises
References
Chapter 2: Objects & Classes
2.1 What is Object Oriented Programming?
2.2 Basic class Syntax
2.2.1 Class Members
2.2.2 Extra Constructor Syntax and Accessors
2.2.3 Separation of Interface and Implementation
2.2.4 The Big Three: Destructor, Copy Constructor, andoperator=
2.2.5 Default Constructor
2.3 Additional C++ Class Features
2.3.1 Initialization Versus Assignment in the ConstructorRevisited
2.3.2 Type Conversions
2.3.3 Operator Overloading
2.3.4 Input and Output and Friends
2.4 Some Common Idioms
2.4.1 Avoiding Friends
2.4.2 Static Class Members
2.4.3 The enum Trick for Integer Class Constants
2.5 Exceptions
2.6 A string Class
2.7 Recap: What Gets Called and What Are the Defaults?
2.8 Composotion
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
Chapter 3: Templates
3.1 What Is a Template?
3.2 Function Templates
3.3 A Sorting Function Template
3.4 Class Templates
3.4.1 A MemoryCell Template
3.4.2 Implementing the vector Class Template
3.5 Templates of Templates: A matrix Class
3.5.1 The Data Members, Constructor. and Basic Accessors
3.5.2 operator [ ]
3.5.3 Destructor, Copy Assignment, and Copy Constructor
3.6 Fancy Templates
3.6.1 Multiple Template Parameters
3.6.2 Default Template Parameters
3.6.3 The Reserved Word typename
3.7 Bugs Associated with Templates
3.7.1 Bad Error Messages and Inconsistent Rules
3.7.2 Template-Matching Algorithms
3.7.3 Nested Classes in a Template
3.7.4 Static Members in Class Templates
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
Chapter 4: Inheritance
Chapter 5: Design Patterns
Part II: Algorithms & Building Blocks
Chapter 6: Algorithm Analysis
Chapter 7: The Standard Template Library
Chapter 8: Recursion
Chapter 9: Sorting Algorithms
Chapter 10: Randomization
Part III: Applications
Chapter 11: Fun & Games
Chapter 12: Stacks & Compilers
Chapter 13: Utilities
Chapter 14: Simulation
Chapter 15: Graphs & Paths
Part IV: Implementations
Chapter 16: Stacks & Queues
Chapter 17: Linked Lists
Chapter 18: Trees
Chapter 19: Binary Search Trees
Chapter 20: Hash Tables
Chapter 21: A Priority Queue: The Binary Heap
Part V: Advanced Data Structures
Chapter 22: Splay Trees
Chapter 23: Merging Priority Queues
Chapter 24: The Disjoint Set Class
Appendices
Appendix A: Miscellaneous C++ Details
Appendix B: Operators
Appendix C: Some Library Routines
Appendix D: Primitive Arrays in C++
Index
Back Cover
DATA STRUCTURES AND
PROBLEM SOLVING USING C++
Second Edition
MARK ALLEN WElSS
Florida International U n i v e r s i ~
Pearson Education International Inc., Upper Saddle River, N.J. 07458
If you purchased this book within the United States or Canada
you should be aware that it has been wrongfully imported
without the approval of the Publisher or the Author.
Acquisitions Editor: Susan Hartman
Project Editor: Katherine Harutunian
Production Management: Shepherd, lnc.
Composition: Shepherd. Inc.
Cover Design: Diana Coe
Cover Photo: O Mike ShepherdPhotonica
Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks.
Where those designations appear in this book, and the publisher was aware of a trademark claim. the des~gnations have
been printed in ~nitial caps or in all caps.
The programs and the applications presented In this book have been included for their instruct~onal value. They have
been tested with care but are not guaranteed for any particular purpose. Neither the publisher or the author offers any
warranties or representations. nor do they accept any liabilities with respect to the programs or applications.
@Copyright 2003 Pearson Education International
Upper Saddle River. N.J. 04758
@Copyright 2002 by Addison Wesley Longman, Inc.
All rights reserved. No part of this publication may be reproduced. stored In a database or retrieval system.
or transmitted in any form or by any means. electronic, mechanical, photocopying, recording. or any other
media embodiments now known or hereafter to become known. without the prior written permis5lon of the
publisher. Printed in the United States of Amenca.
ISBN: 0321 205006
1 0 9 8 7 6 5 4 3 2 1
I Contents
Part I: Objects and C++
Arrays, Pointers, and Structures 3
Chapter 1
I . I What Are Pointers, Arrays, and Structures? 3
1.2 Arrays and Strings 4
First-Class Versus Second-Class Objects 4
1.2.1
1.2.2 Using the vector 6
1.2.3
Resizing a vector 7
1.2.4
gush-back:sizeandcapacity 1 1
Parameter-Passing Mechanisms
1.2.5
1.2.6
Primitive Arrays of Constants 13
1.2.7 Multidimensional Arrays 14
1.2.8
Pointer Syntax in C++ 15
TheStandardLibrarystringType 14
1 1
1.3
1.4 Dynamic Memory Management 20
1.4.1
I .4.2
1.4.3
The new Operator 2 1
Garbage Collection and delete 21
Stale Pointers, Double Deletion, and More 22
1.5 Reference Variables 24
1.6
Structures 26
1.6.1
1.6.2
Pointers to Structures 28
Exogenous Versus Indigenous Data and Shallow Versus Deep
Copying 29
1.6.3 Noncontiguous Lists: Linked Lists 30
32
32
Summary
Objects of the Game
34
Common Errors
On the Internet
35
Exercises
35
References
38
Objects and Classes 41
Chapter 2
2.1 What Is Object-Oriented Programming? 4 1
2.2 Basic class Syntax 43
2.2.1
2.2.2
2.2.3
2.2.4
2.2.5
Class Members 43
Extra Constructor Syntax and Accessors 45
Separation of Interface and Implementation 48
The Big Three: Destructor, Copy Constructor, and
operator= 51
Default Constructor 57
2.3 Additional C++ Class Features 57
2.3.1
Initialization Versus Assignment in the Constructor
Revisited 61
Type Conversions 63
Operator Overloading 64
Input and Output and Friends 67
Avoiding Friends 70
Static Class Members 7 I
The enum Trick for Integer Class Constants 71
2.4
2.3.2
2.3.3
2.3.4
Some Common Idioms 68
2.4.1
2.4.2
2.4.3
Exceptions 72
2.5
2.6 A string Class 73
2.7
2.8
Summary
Objects of the Game
87
Common Errors
On the Internet
89
Exercises
90
References
96
85
85
Recap: What Gets Called and What Are the Defaults? 82
Composition 84
Chapter 3
Templates 97
3.1 What Is a Template? 97
3.2
Function Templates 98
3.3 A Sorting Function Template 100
3.4 Class Templates 103
3.5
Implementing the vector Class Template 108
3.4.1 A MemoryCell Template 103
3.4.2
Templates of Templates: A matrix Class 108
3.5.1
3.5.2
3.5.3
The Data Members, Constructor. and Basic Accessors
operator [ I
Destructor, Copy Assignment, and Copy Constructor 112
112
1 1 1
--
Contents
3.6
3.7
1 12
1 12
1 13
Fancy Templates
3.6.1 Multiple Template Parameters
Default Template Parameters
3.6.2
The Reserved Word typename 1 13
3.6.3
Bugs Associated with Templates
3.7.1
3.7.2
3.7.3
3.7.4
Bad Error Messages and Inconsistent Rules
Template-Matching Algorithms
Nested Classes in a Template 114
Static Members in Class Templates
1 14
1 14
1 15
1 15
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
1 17
1 15
1 16
1 15
Inheritance 119
Chapter 4
4. I What Is Inheritance?
4.2
1 19
1 14
125
Visibility Rules 124
The Constructor and Base Class Initialization
Adding Members 126
Inheritance Basics 123
4.2.1
4.2.2
4.2.3
4.2.4 Overriding a Method 128
4.2.5
4.2.6
Static and Dynamic Binding 129
The Default Constructor, Copy Constructor, Copy Assignment
Operator, and Destructor 13 1
Constructors and Destructors: Virtual or Not Virtual? 132
Static Binding of Parameters 142
4.2.7
4.2.8 Abstract Methods and Classes 133
Example: Expanding the Shape Class 136
Tricky C++ Details 142
4.4.1
4.4.2 Default Parameters 143
4.4.3 Derived Class Methods Hide Base Class Methods 144
Compatible Return Types for Overridden Methods 145
4.4.4
4.4.5
Private Inheritance 146
Friends 146
4.4.6
Call by Value and Polymorphism Do Not Mix 146
4.4.7
4.3
4.4
149
4.5 Multiple Inheritance 147
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
R e f e r e n c e s 154 - - - - - - - - - - - - - -
150
152
152
149
- - -
Design Patterns 155
Chapter 5
5.1 What Is a Pattern'? 155
5.2
5.3 Adapters and Wrappers 162
The Functor (Function Objects) 156
5.4
5.3.1 Wrapper for Pointers 162
5.3.2
A Constant Reference Wrapper 168
5.3.3 Adapters: Changing an Interface 169
lterators 170
5.4.1
5.4.2
5.4.3
Iterator Design 1 17 1
Iterator Design 2 174
Inheritance-Based Iterators and Factories 174
184
5.5 Composite (Pair) 179
5.6 Observer 179
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
186
References 190
185
186
184
Part ZI: Algorithms and Building Blocks
Algorithm Analysis 193
Chapter 6
6.1 What Is Algorithm Analysis? 193
6.2
6.3
Examples of Algorithm Running Times 198
The Maximum Contiguous Subsequence Sum Problem 199
6.3.1
The Obvious O(N3) Algorithm 200
6.3.2 An Improved O(N2) Algorithm 203
6.3.3 A Linear Algorithm 204
6.4 General Big-Oh Rules 206
6.5
6.6
The Logarithm 2 1 1
Static Searching Problem 21 4
6.6.1
6.6.2
6.6.3
Sequential Search 2 14
Binary Search 215
Interpolation Search 217
6.7 Checking an Algorithm Analysis 2 19
6.8 Limitations of Big-Oh Analysis 220
Contents
Summary 221
Objects of the Game 22 1
Common Errors
222
On the Internet 223
Exercises 223
References 228
The Standard Template Library 231
Chapter 7
7.1
7.2
Introduction 232
Stacks and Queues 233
7.2.1
7.2.2
7.2.3 Queues 236
7.3 Containers and Iterators 237
Stacks 233
Stacks and Computer Languages 235
7.4
7.5
7.6
Containers 238
The i t e r a t o r 238
STL Function Objects 240
Binary Search 243
Sorting 244
7.3.1
7.3.2
STL Algorithms 240
7.4.1
7.4.2
7.4.3
Implementation of vector with an Iterator 245
Sequences and Linked Lists 247
7.6.1
7.6.2
7.7
Sets 249
7.8 Maps 251
7.9
Summary 257
Objects of the Game 257
Common Errors 259
On the Internet 259
Exercises 260
References 264
T h e l i s t c l a s s 247
Stacks and Queues 249
Priority Queues 253
Recursion 265
Chapter 8
8.1 What Is Recursion? 265
8.2 Background: Proofs by Mathematical Induction 267
8.3 Basic Recursion 269
8.3.1
8.3.2 Why It Works 274
Printing Numbers in Any Base 27 1
8.3.3 How It Works 275
8.3.4
8.3.5
8.3.6 Additional Examples 279
Too Much Recursion Can Be Dangerous 276
Preview of Trees 278
8.4 Numerical Applications 284
8.4.1 Modular Arithmetic 285
8.4.2 Modular Exponentiation 285
8.4.3
8.4.4
Greatest Common Divisor and Multiplicative Inverses 287
The RSA Cryptosystem 289
8.5 Divide-and-Conquer Algorithms 292
The Maximum Contiguous Subsequence Sum Problem 293
8.5.1
8.5.2 Analysis of a Basic Divide-and-Conquer Recurrence 297
8.5.3 A General Upper Bound for Divide-and-Conquer Running
Times 301
3 10
8.6 Dynamic Programming 303
8.7 Backtracking 308
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References
3 14
3 19
3 13
3 14
3 12
Sorting Algorithms 321
Chapter 9
9.1 Why Is Sorting Important? 322
9.2
9.3 Analysis of the Insertion Sort and Other Simple Sorts 324
9.4
Preliminaries 323
Shellsort 326
9.4.1
Performance of Shellsort 328
9.5 Mergesort 330
9.5.1
9.5.2
Linear-Time Merging of Sorted Arrays 330
The Mergesort Algorithm 332
9.6 Quicksort 334
The Quicksort Algorithm 335
Analysis of Quicksort 337
Picking the Pivot 340
A Partitioning Strategy 342
Keys Equal to the Pivot 344
9.6.1
9.6.2
9.6.3
9.6.4
9.6.5
9.6.6 Median-of-Three Partitioning 345
9.6.7
9.6.8
Small Arrays 346
C++ Quicksort Routine 346
相关推荐
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
