c plus plus handout

所需积分/C币:1 2012-02-09 04:32:04 17.73MB PDF
收藏 收藏
举报

这是学习的好书, 大家下载学学 c jiajia
If you purchased this book within the United States or Canada ou should be aware that it has been wrongfully imported without the approval of the publisher or the Author Project Editor: Katherine Harutumian herd lnc Conposition: Shepherd. Inc. Cover design: Diana co Cover Photo: Mike Shepherd/PhotonIc 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 designations hay been printed in nitial caps or in atl cal The programs and the applications presented in this bex)k have been included for their instructIonal value. They have been tested with care but are not guaranteed tor any particular purposc. Neither the publisher or the aurthur offers any warranties or representations. nor do they accept any liabilities with respect to the programs or applications pearsonOCopyright 2003 Pearson Elucation International Upper Saddle River. N.J. 04758 cOpyright 2002 by Addison Wesley Longman. In .I rights reserved. No part of this publication may be reproduced, stored in a database or retrieval system. Im or by 1s. clectronic, mechanical, photocopyIng. recording, or any other media embodiments now known or hereafter to become known. without the prior written permission of the publisher, Printed in the United States of America sBN:0321205006 10987654321 Contents Part 1: Objects and C++ Chapter 1 Arrays, Pointers, and structures 3 What Are Pointers, Arrays, and Structures? 3 1, 2 Arrays and Strings 4 1.2.1 First-Class Versus Second-Class Objects 4 1. 2.2 USing the vector 6 1. 2. 3 Resizing a vector 7 1.2.4 push back: size and capacity lI 2.5 Parameter-Passing Mechanisms 11 2.6 Primitive Arrays of Constants 13 1. 2. 7 Multidimensional Arrays 14 1. 2.8 The Standard Library string Type 14 1.3 Pointer Syntax in C++ I5 1. 4 Dynamic Memory management 20 1.4.1 The new Operator 21 1.4.2 Garbage Collection and delete 21 3 Stale Pointers Double deletion, and More 22 1.5 Reference variables 24 1. 6 Structures 26 1. 6.1 Pointers to structures 28 1. 6.2 Exogenous Versus Indigenous data and Shallow Versus deep C 1. 6.3 Noncontiguous Lists: Linked Lists 30 Summary 32 Objects of the game 32 Common errors 34 On the internet 35 Exercises 35 References 3 8 Contents Chapter 2 objects and classes 41 2.1 What Is object-Oriented Programming? 41 2.2 Basic class Syntax 43 Class members 43 2.2.2 Extra Constructor Syntax and Accessors 45 2.2.3 Separation of Interface and Implementation 48 2. 2. 4 The big Three: Destructor. Copy Constructor, and peat。x=51 2.2.5 Default Constructor 57 2.3 Additional C++ Class Features 57 Initialization Versus Assignment in the Constructor Revisited 6l 2.3.2 Type Conversions 63 2.3.3 Operator Overloading 64 2.3.4 Input and Output and friends 67 2.4 Some Common idioms 68 2.4. Avoiding friend 2.4.2 Static Class Members 71 2.4.3 The enum Trick for Integer Class Constants 71 2.5 Exceptions 72 2.6 A string Class 73 2.7 Recap: What Gets Called and What Are the defaults? 82 8 Composition 84 Summary 85 Objects of the game 85 Common errors 87 On the internet 89 Exercises 90 References 96 Chapter3 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.4.1 A Memorycell Template 103 3.4.2 Implementing the vector Class Template 108 3.5 Templates of Templates: A matrix Class 108 The Data Members. Constructor and Basic Accessors 11 1 3.5.2。 perator[】112 3.5.3 Destructor, Copy Assignment, and Copy Constructor 1 12 Conte 6 Fancy Templates 1 12 I Multiple Template Parameters [12 3.6. 2 Default Template Parameters 113 The Reserved Word typename 113 3.7 Bugs Associated with Templates 114 3.7.1 Bad Error Messages and Inconsistent Rules 114 3.7.2 Template-Matching Algorithms 114 3.7.3 Nested Classes in a Template 1|4 3.7.4 Static Members in Class Templates 115 Summary 115 Objects of the game 115 Common errors [15 On the internet 116 Exercises |17 Chapter 4 Inheritance 119 4.1 What Is Inheritance? 119 4.2 Inheritance Basics 123 4.2. Visibility rules 124 4.2.2 The Cons tructor and Base Class initialization 125 4.2.3 Adding Members 126 4.2.4 Overriding a Method 128 4 Static and Dynamic Binding 129 4.2.6 The Default Constructor, Copy Constructor, Copy Assignment Operator, and Destructor 131 4.2.7 Constructors and Destructors Virtual or not virtual? 132 4. 2. 8 Abstract Methods and classes 133 4.3 Example: Expanding the Shape Class 136 4.4 Tricky c++ Details 142 4.4.1 Static Binding of parameters 42 4.4.2 Default Parameters 143 4.4. 3 Derived Class Methods hide Base Class methods 144 4.4.4 Compatible Return Types for Overridden Methods 145 4. 4.5 Private Inheritance 146 4.4.6 Friends 146 4.4.7 Call by value and polymorphism Do Not mix 146 4.5 Multiple Inherit 147 S ummar l49 Objects of the game |49 Common errors 150 On the internet 152 Exercises 152 References 154 Chapter 5 Design Patterns 155 5.1 What Is a pal 2 The Functor(Functie 5.3 Adapters and W apper for Pointers 162 5.3.2 A Constant Rcfcrcnce Wrapper I 5.3.3 Adaptcrs: Changing an Interface 16y 5. Iterators 170 5.4.3 Inheritance- Based Iterators and Factories 174 184 Comon er Referent Part 11: Algorithms and Building block Chapter 6 Algorithm Analysis 1 6.3 The Maximum Contiguous Subsequence Sum Problen 199 3.1 The Obvious O(N) Algorithm 2(0) 6.3. 63. 3 A Linear algorithm 204 h 4 Greneral Big-Oh Rules 206 6.5 The Logarithm 211 6. 6 Static Searching Problem 214 6.6.1 Sequential Search 214 Interpolation Search 21 hecking an Algorithm Analysis 219 6.8 Limitations of bi Contentsⅶ Objects of the Game 221 Cormon errors 222 On the Internet 223 Reterences 228 Chapter 7 The Standard Template Library 231 7.1ln 7.2 Stacks and Queues 233 7. 2.2 Stacks and Computer Languages 235 7.3 Containers and Iterators 237 7.3.1 Containers 238 7.3.2 The iterator 238 7. STL algorithms s240 7.4.1 STL Function Objects 240 7.4.2 Binary Search 243 7.4.3 Sorting 244 7.5 Implementation of vector with an Iterator 245 7.6 Sequences and Linked Lists 247 7.6.1 The list class 24 7.6.2 Stacks and Queues 7.7 Sets 249 7.8 Maps 7.9 Pricrity Queu On the internet 259 Exercises 260 References 264 chapter 8 Recursion 265 8. 1 what Is Recursion: 265 8.2 Background: Proofs by MaLhernalical Induction 267 8.3 Basic recursion 269 8. 3.1 Printing numb 8.3.2 Why It Works 27 4 iii Contents 83, 3 How lt works 275 8. 3.4 Too Much Recursion Can Be dangerous 276 8.3.5 Preview of trees 278 83.6 Additional Examples 279 8.4 Numerical Applications 284 8.4. Modular arithmetic 285 8.4.2 Modular exponentiation 285 8.4.3 Greatest Common Divisor and multiplicative invers 287 8.4.4 The RsA Cryptosystem 289 8.5 Divide-and-Conquer Algorithms 292 8.5.1 The Maximum Contiguous subsequence Sum Problem 293 8.5.2 Analysis of a Basic Divide-and-Conquer Recurrence 297 8.5.3 A General Upper Bound for Di Conquer Running Times 301 8.6 Dynamic Programming 303 8.7 Backtracking 308 Summary 310 Objects of the Game 312 C 313 On the internet 314 Er xercises 14 References 319 Chapter 9 Sorting Algorithms 321 9. 1 Why Is Sorting Important? 322 9.2 Preliminaries 323 9.3 Analysis of the Insertion Sort and Other Simple Sorts 324 9.4 Shellsort 326 4. Performance of shellsort 328 9.5 Mergesort 330 9.5.1 Linear-Time Merging of Sorted Arrays 330 9.5.2 The Mergesort Algorithm 332 9.6 Quicksort 334 6 The Quicksort Algorithm 33.5 9.6.2 Analysis of Quicksort 337 9.6.3 Picking the Pivot 340 9.6. 4 A Partitioning Strategy 342 9.6. 5 Keys equal to the pi 344 9.6.6 Median-of-Three partitioning 345 9.6.7 Small arrays 346 9.6.8 C++ Quicksort routine 346 Contents Quickselect 348 9. 8 A Lower Bound for Sorting 349 9.9 Indirect sorting 352 Using Pointers to Reduce Comparable Copies to 2N 352 9.9.2 Avoiding the Extra Array 353 Summary 355 Objects of the Game 356 Common Errors 357 On the internet 357 Exercises 358 References 363 Chapter 10 Randomization 365 10. Why do we Need random Numbers? 365 10.2 Random Number Generators 366 10.3 Nonuniform random numbers 371 10. 4 Generating a random permutation 373 10.5 Randomized algorithms 375 10.6 Randomized primality Testing 378 Su 380 Objects of the Game 382 Common errors 383 On the Internet 383 Exercises 383 References 386 Part applications Chapter 11 Fun and games 389 11. 1 Word Search Puzzles 389 1. I I Theory 390 1.1.2 C++Implementation 3 91 11. 2 The game of Tic-Tac-Toe 395 11. 2. 1 Alpha-Beta Pruning 397 1. 2.2 Transposition Tables 398 1.2.3 Computer Chess 404 Summary 405 Objects of the Game 405

...展开详情
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐