內 容 簡 介
本書是最優秀的C++入門教材，深受師生歡迎。作者結合自己多年的教學經驗，根據教學大綱精心設計并編寫了書中內容。與此同時，本書還采用了很多便于讀者鞏固所學知識的教學特征，比如各章開始處的小節總覽，書中隨處可見的總結框、編程提示和編程陷阱，各章結尾處的小結、習題和編程項目等。這些非常適合初學者掌握重要的編程概念。
全書共18章，8個附錄。在講解C++基礎知識之后，直接引導學生深入函數、I/O流、類、控制流程、命名空間、數組、字符串、指針和動態數組、遞歸、模板、指針和鏈表、派生類、異常以及標準模板庫。
Original edition, entitled PROBLEM SOLVING WITH C++, 8E, 9780132162739 by SAVITCH,
WALTER, published by Pearson Education, Inc, publishing as Addison-Wesley, Copyright © 2012 Pearson Education, Inc..
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc.
China edition published by PEARSON EDUCATION ASIA LTD., and TSINGHUA UNIVERSITY PRESS LIMITED Copyright © 2014.
This edition is manufactured in the People’s Republic of China, and is authorized for sale and distribution in the People’s Republic of China exclusively (except Taiwan, Hong Kong SAR and Macau SAR).
本書影印版由Pearson Education授權給清華大學出版社在中國境內(不包括中國臺灣、香港特別行政區和澳門特別行政區)出版發行。
北京市版權局著作權合同登記號 圖字：01-2014-7917
前 言
本書適合C++程序設計和計算機科學入門課程使用。閱讀本書不要求讀者有任何編程經驗，也不要求掌握除了中學代數之外的其他任何數學知識。
本書前幾版的讀者請閱讀關于第8版修訂內容的小節，前言的其余內容可略過。新讀者請閱讀前言的全部內容以把握本書脈絡。
第8版修訂內容
第8版采用和第7版相同的編程體例。第7版全部內容予以保留，但進行了以下改進。
第10章不再使用流類(比如ifstream和ofstream)介紹繼承概念，而是，使用那一章更簡單的銀行賬戶例子來介紹。
額外添加了有關作用域、參數傳遞、隨機數生成、動態數組的內容，有幾章的幻燈片進行了重新制作。
新增25個編程項目，合并到每章末尾現有的項目中。
本書配套網站添加了15個新的視頻講解，總數達54個。這些視頻講解輔導學生解題和寫程序，有助于鞏固對關鍵編程概念的掌握。如果書中某個主題有對應的視頻講解，就會出現一行特殊的注釋(視頻講解……)。
用過第7版的教師可以沿用以前的教案，幾乎不需要進行任何改動。
主題可以靈活排序
本書允許教師自由地重新安排教學順序。為了演示這一靈活性，下面推薦了兩種方式來排列主題順序。采用任何一種方式閱讀本書，都不會影響學習的連貫性。為了在重新排序時確保這種連貫性，可能需要移動個別小節而不是全章。但是，只有較大的、位置便利的小節才需要移動。為了幫助您根據需要自定義一個教學/閱讀順序，圖P.1展示了一幅依賴圖。另外，每章都有“預備知識”小節，解釋了學習那一章的每一節之前需要掌握哪些內容。
重新排序1：提前學習類
為了有效地設計類，學生需要掌握一些基本的工具，比如控制結構和函數定義。這些基礎知識在第1章～第6章介紹。完成第6章的學習后，學生就可以開始編寫自己的類了。為了提前學習類的知識，可以像下面這樣重新安排各章的順序。
基礎知識 第1章、第2章、第3章、第4章、第5章和第6章。這6章全面介紹控制結構、函數定義和基本文件I/O。第3章介紹幾種額外的控制結構，如果希望盡早學習類，可以考慮推遲這一章的學習。
類和命名空間 第10章、第11章的11.1節和11.2節、第12章。這些章節全面介紹了如何定義類、友元、重載操作符和命名空間。
數組、字符串和向量 第7章和第8章。
指針和動態數組 第9章。
類中的數組 第11章的11.3節和11.4節。
繼承 第15章。
遞歸 第14章(也可以推遲到稍晚的時候學習)。
指針和鏈表 第13章。
可能還要用到以下各章的部分內容。
異常處理 第16章。
模板 第17章。
標準模板庫 第18章。
重新排序2：略微延后類的學習
在“重新排序2”中，將先學完所有控制結構，再學習有關數組的基本知識，之后才開始學習類。雖然對類的接觸要比“重新排序1”晚，但還是比本書的默認順序略微提前一些。
基礎知識 第1章、第2章、第3章、第4章、第5章和第6章。這6章全面介紹了控制結構、函數定義和基本文件I/O。
數組和字符串 第7章、第8章的8.1節和8.2節。
類和命名空間 第10章、第11章的11.1節、11.2節和第12章。這些章節全面介紹了如何定義類、友元、重載操作符和命名空間。
指針和動態數組 第9章。
類中的數組 第11章的11.3節和11.4節。
繼承 第15章。
遞歸 第14章(也可以推遲到稍晚的時候學習)。
向量 8.3節。
指針和鏈表 第13章。
可能還要用到以下各章的部分內容。
異常處理 第16章。
模板 第17章。
標準模板庫 第18章。
面向學生的易用性
一本書必須按恰當的順序來講解恰當的主題，這是最起碼的要求。另外，在老師和其他有經驗的程序員看來，書中的內容必須清晰而又正確，這是另一個最起碼的要求。但是，是不是符合這兩項要求的書都是好書呢？答案是否定的。書中的內容必須采取有利于初學者使用的方式來編排。在這本入門教科書中，我盡力讓學生覺得清楚和友好。本書以前版本的大量學生反饋證明，這種寫作風格確實使內容更清晰，能使學生充分享受到學習的樂趣。
ANSI/ISO C++標準
本書完全兼容于符合最新ANSI/ISO C++標準的編譯器。
高級主題
許多“高級主題”都成為標準CS1課程的一部分。即使它們不是課程的一部分，也最好以補充材料的形式在書中提供。本書提供了大量高級主題，它們既可集成到一門課程中，也可作為自學主題。本書全面講述了C++模板、繼承(包括虛函數)、異常處理和STL(Standard Template Library，標準模板庫)。雖然本書使用了庫，而且教給學生庫的重要性，但不要求任何非標準庫。本書只使用所有C++實現都附帶的庫。
依賴圖
依賴圖展示了各個章節可能的排序方式。連接兩個框的實線表明上部的框必須先于下部的框完成。只要符合這個條件，采用任何閱讀順序都無損連貫性。如果一個框中包含小節編號，表明該框只代表那些小節，不代表全章。
小結框
每個要點都用一個有底紋的方框來小結。這些“小結框”散布于每一章。
自測題
每章都在重要位置提供大量自測題。每章末尾都有所有自測題的完整答案。
視頻講解
視頻講解(Video Note)是Pearson新推出的可視工具，目的是向學生講解關鍵的編程概念和技術。這些短視頻演示了從設計到編碼來解決問題的過程。視頻講解使學生能方便地自學自己感興趣的主題，允許選擇、播放、倒退、快進和暫停等。每當看到“ 視頻講解……”，都表明當前主題有一段對應的視頻講解。請自行上網觀看視頻，網址是http://media.pearsoncmg.com/aw/aw_savitch_cpp_8/videonotes/vn.html。注意，由于是英文視頻，所以為了方便索引，書中保留了這些視頻的英文名稱。
支持材料
部分支持材料是本書所有讀者都能使用的。另一部分僅供有資格的教師使用。
適于本書所有讀者的支持材料
本書源代碼
PowerPoint幻燈片
視頻講解
為了獲取這些材料，請訪問本書譯者博客(transbot.blog.163.com)。
適于有資格的教師的資源
選用本書作為教材的教師，可致函編輯信箱wenkaiqi@gmail.com了解詳情。
教師資源指南(Instructor’s Resource Guide)：包括每一章的教學要點、課堂測驗/答案和大量編程項目的答案。
Test Bank和Test Generator：用于生成試卷。
PowerPoint幻燈片：包括本書的程序和插圖。
Lab Manual(實驗手冊)。
致謝
在準備本書素材期間，很多個人和團體提供了大量建議和幫助，并和我進行了廣泛而深入的探討。本書第1版大部分內容是我在科羅拉多大學(波德分校)計算機系擔任客座教授時寫就的。其余內容和后續版本則是在加州大學(圣地亞哥分校)計算機科學與工程系完成的。非常感謝這兩所學校為本書寫作和教學所提供的良好氛圍。
特別感謝向這一版和之前各版提供意見或者編程項目的個人，以下人名按字母排序：Joseph Allen，Noah Aydin，Claire Bono,Richard Borie，Andrew Burt，Edward Carr，Karla Chaveau，Wei Lian Chen,Joel Cohen，Doug Cosman，Charles Dowling，Scot Drysdale，Joe Faletti，Alex Feldman，Sheila Foster，Paulo Franca，Len Garrett，Jerrold Grossman，Eitan M. Gurari，Andrew Haas，Dennis Heckman，Bob Holloway，Nisar Hundewale，Matt Johnson，Bruce Johnston，Larry Johnson，Thomas Judson，Huzefa Kagdi，Paul J. Kaiser，Michael Keenan，Brian R. King，Paul Kube，Gilliean Lee，Barney MacCabe，Steve Mahaney，Michael Main，Walter A. Manrique，Anne Marchant，John Marsaglia，Nat Martin，Cynthia Martincic，Bob Matthews，Jesse Morehouse，Ethan Munson，Donald Needham，Dung Nguyen，Joseph D. Oldham，Jennifer Perkins，Jeff Roach，Carol Roberts，Ken Rockwood，John Russo，Amber Settle，Naomi Shapiro，Susanne Sherba，Michal Sramka，James Stepleton，Scott Strong，David Teague，Jeffrey Watson，Jerry Weltman，John J. Westman和Linda F. Wilson。
還要感謝用過本書前幾版的許多老師，他們的建議相當有價值。最后感謝Kenrick Mock幫我實現了這一版的全部修訂。他的工作令我和編輯激賞！
目 錄
Brief Contents
Table of Location of VideoNotes
Inside front cover and inside back cover
Chapter 1 1Introduction to Computers and C++ Programming 1
Chapter 2 2C++ Basics 39
Chapter 3 3More Flow of Control 109
Chapter 4 4Procedural Abstraction and Functions That Return a Value 177
Chapter 5 5Functions for All Subtasks 247
Chapter 6 6I/O Streams as an Introduction to Objects and Classes 301
Chapter 7 7Arrays 373
Chapter 8 8Strings and Vectors 441
Chapter 9 9Pointers and Dynamic Arrays 493
Chapter 10 0Defining Classes 525
Chapter 11 Friends, Overloaded Operators, and Arrays in Classes 601
Chapter 12 Separate Compilation and Namespaces 685
Chapter 13 Pointers and Linked Lists 721
Chapter 14 Recursion 769
Chapter 15 Inheritance 811
Chapter 16 Exception Handling 867
Chapter 17 Templates 899
Chapter 18 Standard Template Library 931
Appendices
1 C++ Keywords 987
2 Precedence of Operators 988
3 The ASCII Character Set 990
4 Some Library Functions 991
5 Inline Functions 998
6 Overloading the Array Index Square Brackets 999
7 The this Pointer 1001
8 Overloading Operators as Member Operators 1004
Table of Location of VideoNotes
Inside front cover and inside back cover
Chapter 1 1Introduction to Computers and C++ Programming 1
1.1 COMPuTER SYSTEMS 2
Hardware 2
Software 7
High-Level Languages 8
Compilers 9
History Note 12
1.2 PROgRAMMINg AND PROBLEM-SOLVINg 12
Algorithms 12
Program Design 15
Object-Oriented Programming 16
The Software Life Cycle 17
1.3 INTRODuCTION TO C++ 18
Origins of the C++ Language 18
A Sample C++ Program 19
Pitfall: Using the Wrong Slash in \n 23
Programming Tip: Input and Output Syntax 23
Layout of a Simple C++ Program 24
Pitfall: Putting a Space Before the include File Name 26
Compiling and Running a C++ Program 26
Programming Tip: Getting Your Program to Run 27
1.4 TESTINg AND DEBuggINg 29
Kinds of Program Errors 30
Pitfall: Assuming Your Program Is Correct 31
Chapter Summary 31
1Answers to Self-Test Exercises 32
2Programming Projects 35
Chapter 2 C++ Basics 39
2.1 VARIABLES AND ASSIgNMENTS 40
Variables 40
0Names: Identifiers 42
2Variable Declarations 44
4Assignment Statements 45
5Pitfall: Uninitialized Variables 47
7Programming Tip: Use Meaningful Names 49
2.2 INPuT AND OuTPuT 50
Output Using cout 50
Include Directives and Namespaces 52
Escape Sequences 53
Programming Tip: End Each Program with a \n or endl 54
Formatting for Numbers with a Decimal Point 55 Input Using cin 56
Designing Input and Output 58
Programming Tip: Line Breaks in I/O 58
2.3 DATA TYPES AND ExPRESSIONS 60
The Types int and double 60
0Other Number Types 62
2The Type char 63
3The Type bool 64
4Introduction to the Class string 65
5Type Compatibilities 66
6Arithmetic Operators and Expressions 68
8Pitfall: Whole Numbers in Division 71
1More Assignment Statements 73
2.4 SIMPLE FLOw OF CONTROL 73
A Simple Branching Mechanism 74
4Pitfall: Strings of Inequalities 79
9Pitfall: Using = in place of == 80
0Compound Statements 81
1Simple Loop Mechanisms 83
Increment and Decrement Operators 86
Programming Example: Charge Card Balance 88
Pitfall: Infinite Loops 89
2.5 PROgRAM STYLE 92
Indenting 92 Comments 92 Naming Constants 94
Chapter Summary 97 Answers to Self-Test Exercises 97
Programming Projects 102
Chapter 3 More Flow of Control 109
3.1 uSINg BOOLEAN ExPRESSIONS 110
Evaluating Boolean Expressions 110
Pitfall: Boolean Expressions Convert to int Values 114
Enumeration Types (Optional) 117
3.2 MuLTIwAY BRANCHES 118
Nested Statements 118
Programming Tip: Use Braces in Nested Statements 119
Multiway if-else Statements 121
Programming Example: State Income Tax 123
The switch Statement 126
Pitfall: Forgetting a break in a switch Statement 130
Using switch Statements for Menus 131
Blocks 133
Pitfall: Inadvertent Local Variables 136
3.3 MORE ABOuT C++ LOOP STATEMENTS 137
The while Statements Reviewed 137
Increment and Decrement Operators Revisited 139
The for Statement 142
Pitfall: Extra Semicolon in a for Statement 147
What Kind of Loop to Use 148
Pitfall: Uninitialized Variables and Infinite Loops 150
The break Statement 151 Pitfall: The break Statement in Nested Loops 152
7387_Savitch_FM_ppi-xxx.indd 18 2/2/11 5:45 PM
contents xix
3.4 DESIgNINg LOOPS 153
Loops for Sums and Products 153 Ending a Loop 155 Nested Loops 158 Debugging Loops 160
Chapter Summary 163 Answers to Self-Test Exercises 164 Programming Projects 170
Chapter 4 4Procedural Abstraction and Functions That Return a Value 177
4.1 TOP-DOwN DESIgN 178
4.2 PREDEFINED FuNCTIONS 179
Using Predefined Functions 179 Random Number Generation 184 Type Casting 186 Older Form of Type Casting 188 Pitfall: Integer Division Drops the Fractional Part 188
4.3 PROgRAMMER-DEFINED FuNCTIONS 189
Function Definitions 189 Functions That Return a Boolean Value 195 Alternate Form for Function Declarations 195 Pitfall: Arguments in the Wrong Order 196 Function Definition–Syntax Summary 197 More About Placement of Function Definitions 198 Programming Tip: Use Function Calls in Branching Statements 199
4.4 PROCEDuRAL ABSTRACTION 200
The Black-Box Analogy 200 Programming Tip: Choosing Formal Parameter Names 203 Programming Tip: Nested Loops 204 Case Study: Buying Pizza 207 Programming Tip: Use Pseudocode 213
4.5 SCOPE AND LOCAL VARIABLES 214
The Small Program Analogy 214 Programming Example: Experimental Pea Patch 217
Global Constants and Global Variables 217 Call-by-Value Formal Parameters Are Local Variables 220 Block Scope 222 Namespaces Revisited 223 Programming Example: The Factorial Function 226
4.6 OVERLOADINg FuNCTION NAMES 228
Introduction to Overloading 228 Programming Example: Revised Pizza-Buying Program 231 Automatic Type Conversion 234 Chapter Summary 236 Answers to Self-Test Exercises 236 Programming Projects 241
Chapter 5 Functions for All Subtasks 247
5.1 void FuNCTIONS 248
Definitions of void Functions 248 Programming Example: Converting Temperatures 251 return Statements in void Functions 251
5.2 CALL-BY-REFERENCE PARAMETERS 255
A First View of Call-by-Reference 255 Call-by-Reference in Detail 258 Programming Example: The swap_values Function 263 Mixed Parameter Lists 264 Programming Tip: What Kind of Parameter to Use 265 Pitfall: Inadvertent Local Variables 266
5.3 uSINg PROCEDuRAL ABSTRACTION 269
Functions Calling Functions 269 Preconditions and Postconditions 271 Case Study: Supermarket Pricing 272
5.4 TESTINg AND DEBuggINg FuNCTIONS 277
Stubs and Drivers 278
5.5 gENERAL DEBuggINg TECHNIquES 283
Keep an Open Mind 283 Check Common Errors 283 Localize the Error 284 The assert Macro 286 2/2/11 5:45 PM
Chapter Summary 288
8Answers to Self-Test Exercises 289
9Programming Projects 292
Chapter 6 6I/O Streams as an Introduction to Objects and Classes 301
6.1 STREAMS AND BASIC FILE I/O 302
Why Use Files for I/O? 303
3File I/O 304
4Introduction to Classes and Objects 308
8Programming Tip: Check Whether a File Was Opened
d Successfully 310
0Techniques for File I/O 312
2Appending to a File (Optional) 316
6File Names as Input (Optional) 317
6.2 TOOLS FOR STREAM I/O 319
Formatting Output with Stream Functions 319
9Manipulators 325
5Streams as Arguments to Functions 328
8Programming Tip: Checking for the End of a File 328
8A Note on Namespaces 331
1Programming Example: Cleaning Up a File Format 332
6.3 CHARACTER I/O 334
The Member Functions get and put 334
4The putback Member Function (Optional) 338
8Programming Example: Checking Input 339
9Pitfall: Unexpected '\n' in Input 341
1Programming Example: Another new_line Function 343
3Default Arguments for Functions (Optional) 344
4The eof Member Function 349
9Programming Example: Editing a Text File 351
1Predefined Character Functions 352
2Pitfall: toupper and tolower Return Values 354
Chapter Summary 356
6Answers to Self-Test Exercises 357
7Programming Projects 364
Chapter 7 Arrays 373
7.1 INTRODuCTION TO ARRAYS 374
Declaring and Referencing Arrays 374 Programming Tip: Use for Loops with Arrays 376 Pitfall: Array Indexes Always Start with Zero 376 Programming Tip: Use a Defined Constant for the Size of an Array 376 Arrays in Memory 378 Pitfall: Array Index Out of Range 379 Initializing Arrays 381
7.2 ARRAYS IN FuNCTIONS 383
Indexed Variables as Function Arguments 383 Entire Arrays as Function Arguments 385 The const Parameter Modifier 388 Pitfall: Inconsistent Use of const Parameters 391 Functions That Return an Array 391 Case Study: Production Graph 392
7.3 PROgRAMMINg wITH ARRAYS 405
Partially Filled Arrays 405 Programming Tip: Do Not Skimp on Formal Parameters 408 Programming Example: Searching an Array 408 Programming Example: Sorting an Array 411
7.4 MuLTIDIMENSIONAL ARRAYS 415
Multidimensional Array Basics 416 Multidimensional Array Parameters 416 Programming Example: Two-Dimensional Grading Program 418 Pitfall: Using Commas Between Array Indexes 422
Chapter Summary 423 Answers to Self-Test Exercises 424 Programming Projects 428
Chapter 8 Strings and Vectors 441
8.1 AN ARRAY TYPE FOR STRINgS 443
C-String Values and C-String Variables 443 Pitfall: Using = and == with C Strings 446 2/2/11 5:45 PM
contents xxiii
Other Functions in <cstring> 448
8C-String Input and Output 453
3C-String-to-Number Conversions and Robust Input 455
8.2 THE STANDARD string CLASS 461
Introduction to the Standard Class string 461
1I/O with the Class string 464
4Programming Tip: More Versions of getline 467
7Pitfall: Mixing cin >> variable; and getline 468
8String Processing with the Class string 469
9Programming Example: Palindrome Testing 473
3Converting Between string Objects and C Strings 476
8.3 VECTORS 477
Vector Basics 477 Pitfall: Using Square Brackets Beyond the Vector Size 480 Programming Tip: Vector Assignment Is Well Behaved 481 Efficiency Issues 481
Chapter Summary 483
3Answers to Self-Test Exercises 484
4Programming Projects 486
Chapter 9 Pointers and Dynamic Arrays 493
9.1 POINTERS 494
Pointer Variables 495
5Basic Memory Management 502
2Pitfall: Dangling Pointers 503
3Static Variables and Automatic Variables 504
4Programming Tip: Define Pointer Types 504
9.2 DYNAMIC ARRAYS 507
Array Variables and Pointer Variables 507
7Creating and Using Dynamic Arrays 508
8Pointer Arithmetic (Optional) 514
4Multidimensional Dynamic Arrays (Optional) 516
Chapter Summary 518
8Answers to Self-Test Exercises 518
8Programming Projects 519
Chapter 10 0Defining Classes 525
10.1 STRuCTuRES 526
Structures for Diverse Data 526
Pitfall: Forgetting a Semicolon in a Structure Definition 531
Structures as Function Arguments 532
Programming Tip: Use Hierarchical Structures 533
Initializing Structures 535
10.2 CLASSES 538
Defining Classes and Member Functions 538 Public and Private Members 543 Programming Tip: Make All Member Variables Private 551 Programming Tip: Define Accessor and Mutator Functions 551 Programming Tip: Use the Assignment Operator with Objects 553 Programming Example: BankAccount Class—Version 1 554 Summary of Some Properties of Classes 558 Constructors for Initialization 560 Programming Tip: Always Include a Default Constructor 568 Pitfall: Constructors with No Arguments 569
10.3 ABSTRACT DATA TYPES 571
Classes to Produce Abstract Data Types 572 Programming Example: Alternative Implementation of a Class 576
10.4 INTRODuCTION TO INHERITANCE 581
Derived Classes 582 Defining Derived Classes 583
Chapter Summary 587 Answers to Self-Test Exercises 588 Programming Projects 594
Chapter 11 1Friends, Overloaded Operators, and Arrays in Classes 601
11.1 FRIEND FuNCTIONS 602
Programming Example: An Equality Function 602 Friend Functions 606 Programming Tip: Define Both Accessor Functions and Friend Functions 608 2/2/11 5:45 PM
contents xxv
Programming Tip: Use Both Member and Nonmember Functions 610 Programming Example: Money Class (Version 1) 610 Implementation of digit_to_int (Optional) 617 Pitfall: Leading Zeros in Number Constants 618 The const Parameter Modifier 620 Pitfall: Inconsistent Use of const 621
11.2 OVERLOADINg OPERATORS 625
Overloading Operators 626
6Constructors for Automatic Type Conversion 629
9Overloading Unary Operators 631
1Overloading >> and << 632
11.3 ARRAYS AND CLASSES 642
Arrays of Classes 642 Arrays as Class Members 646 Programming Example: A Class for a Partially Filled Array 647
11.4 CLASSES AND DYNAMIC ARRAYS 649
Programming Example: A String Variable Class 650
0Destructors 653
3Pitfall: Pointers as Call-by-Value Parameters 656
6Copy Constructors 657
7Overloading the Assignment Operator 662
Chapter Summary 665
5Answers to Self-Test Exercises 665
5Programming Projects 675
Chapter 12 Separate Compilation and Namespaces 685
12.1 SEPARATE COMPILATION 686
ADTs Reviewed 687 Case Study: DigitalTime —A Class Compiled Separately 688 Using #ifndef 697 Programming Tip: Defining Other Libraries 700
12.2 NAMESPACES 701
Namespaces and using Directives 701
1Creating a Namespace 703
3Qualifying Names 706
6A Subtle Point About Namespaces (Optional) 707
Unnamed Namespaces 708 Programming Tip: Choosing a Name for a Namespace 713 Pitfall: Confusing the Global Namespace and the Unnamed Namespace 714
Chapter Summary 715 Answers to Self-Test Exercises 716 Programming Projects 718
Chapter 13 Pointers and Linked Lists 721
13.1 NODES AND LINKED LISTS 722
Nodes 722 Linked Lists 728 Inserting a Node at the Head of a List 729 Pitfall: Losing Nodes 732 Searching a Linked List 733 Pointers as Iterators 735 Inserting and Removing Nodes Inside a List 737 Pitfall: Using the Assignment Operator with Dynamic Data Structures 740 Variations on Linked Lists 741 Linked Lists of Classes 744
13.2 STACKS AND quEuES 747
Stacks 747 Programming Example: A Stack Class 748 Queues 753 Programming Example: A Queue Class 754
Chapter Summary 758 Answers to Self-Test Exercises 758 Programming Projects 761
Chapter 14 Recursion 769
14.1 RECuRSIVE FuNCTIONS FOR TASKS 771
Case Study: Vertical Numbers 771 A Closer Look at Recursion 777 Pitfall: Infinite Recursion 779 2/2/11 5:45 PM
contents xxvii
Stacks for Recursion 780
0Pitfall: Stack Overflow 782
2Recursion Versus Iteration 782
14.2 RECuRSIVE FuNCTIONS FOR VALuES 784
General Form for a Recursive Function That Returns a Value 784 Programming Example: Another Powers Function 784
14.3 THINKINg RECuRSIVELY 789
Recursive Design Techniques 789 Case Study: Binary Search—An Example of Recursive Thinking 790 Programming Example: A Recursive Member Function 798
Chapter Summary 802
2Answers to Self-Test Exercises 802
2Programming Projects 807
Chapter 15 Inheritance 811
15.1 INHERITANCE BASICS 812
Derived Classes 813 Constructors in Derived Classes 821 Pitfall: Use of Private Member Variables from the Base Class 824 Pitfall: Private Member Functions Are Effectively Not Inherited 826 The protected Qualifier 826 Redefinition of Member Functions 829 Redefining Versus Overloading 832 Access to a Redefined Base Function 834
15.2 INHERITANCE DETAILS 835
Functions That Are Not Inherited 835
5Assignment Operators and Copy Constructors in Derived
d Classes 836
6Destructors in Derived Classes 837
15.3 POLYMORPHISM 838
Late Binding 839
9Virtual Functions in C++ 840
0Virtual Functions and Extended Type Compatibility 845
5Pitfall: The Slicing Problem 849
9Pitfall: Not Using Virtual Member Functions 850
Pitfall: Attempting to Compile Class Definitions Without Definitions for Every Virtual Member Function 851 Programming Tip: Make Destructors Virtual 851
Chapter Summary 853 Answers to Self-Test Exercises 853 Programming Projects 857
Chapter 16 Exception Handling 867
16.1 1ExCEPTION-HANDLINg BASICS 869
A Toy Example of Exception Handling 869 Defining Your Own Exception Classes 878 Multiple Throws and Catches 878 Pitfall: Catch the More Specific Exception First 882 Programming Tip: Exception Classes Can Be Trivial 883 Throwing an Exception in a Function 883 Exception Specification 885 Pitfall: Exception Specification in Derived Classes 887
16.2 2PROgRAMMINg TECHNIquES FOR ExCEPTION HANDLINg 888
When to Throw an Exception 888 Pitfall: Uncaught Exceptions 890 Pitfall: Nested try-catch Blocks 890 Pitfall: Overuse of Exceptions 890 Exception Class Hierarchies 891 Testing for Available Memory 891 Rethrowing an Exception 892
Chapter Summary 892 Answers to Self-Test Exercises 892 Programming Projects 894
Chapter 17 Templates 899
17.1 1TEMPLATES FOR ALgORITHM ABSTRACTION 900
Templates for Functions 901 Pitfall: Compiler Complications 905 Programming Example: A Generic Sorting Function 907
Programming Tip: How to Define Templates 911
1Pitfall: Using a Template with an Inappropriate Type 912
17.2 TEMPLATES FOR DATA ABSTRACTION 913
Syntax for Class Templates 913
3Programming Example: An Array Class 916
Chapter Summary 922
2Answers to Self-Test Exercises 922
2Programming Projects 925
Chapter 18 Standard Template Library 931
18.1 ITERATORS 933
using Declarations 933
3Iterator Basics 934
4Pitfall: Compiler Problems 938
8Kinds of Iterators 940
0Constant and Mutable Iterators 944
4Reverse Iterators 945
5Other Kinds of Iterators 946
18.2 CONTAINERS 947
Sequential Containers 948
8Pitfall: Iterators and Removing Elements 952
2Programming Tip: Type Definitions in Containers 953
3Container Adapters stack and queue 953
3Associative Containers set and map 957
7Efficiency 964
18.3 gENERIC ALgORITHMS 965
Running Times and Big-O Notation 965
5Container Access Running Times 970
0Nonmodifying Sequence Algorithms 971
1Container Modifying Algorithms 975
5Set Algorithms 977
7Sorting Algorithms 978
Chapter Summary 979
9Answers to Self-Test Exercises 979
9Programming Projects 981
1 C++ Keywords 987
2 Precedence of Operators 988
3 The ASCII Character Set 990
4 Some Library Functions 991
5 Inline Functions 998
6 Overloading the Array Index Square Brackets 999
7 The this Pointer 1001
8 Overloading Operators as Member Operators 1004
INDEx 1006
