Preface
1IntroductiontoDataStructures
1-1WHATISTHISBOOKABOUT?2
DataStructuresandAlgorithms5
1-2ABSTRACTVIEWOFDATASTRUCTURES5
Thetime24ADT6
1-3ANADTASACLASS8
TheC++Class8
PrivateandPublicSections9
EncapsulationandInformationHiding9
Thetime24Class9
1-4IMPLEMENTINGC++CLASSES13
Implementationofthetime24Class14
1-5DECLARINGANDUSINGOBJECTS18
RunningaProgram18
1-6IMPLEMENTINGACLASSWITHINLINECODE21
CompilerUseofInlineCode22
1-7APPLICATIONPROGRAMMINGINTERFACE(API)23
RandomNumbers24
TherandomNumberAPI24
Application:TheGameofCraps26
1-8STRINGS28
ThestringClass30
AdditionalStringFunctionsandOperations31
CHAPTERSUMMARY36
CLASSESANDLIBRARIESINTHECHAPTER37
REVIEWEXERCISES38
AnswerstoReviewExercises40
WRITTENEXERCISES42
PROGRAMMINGEXERCISES48
PROGRAMMINGPROJECTS51
2ObjectDesignTechniques
2-1SOFTWAREDESIGN55
RequestandProblemAnalysis56
ProgramDesign57
DesigningtheCalendarClass58
ProgramImplementation62
ImplementingtheCalendarClass62
ProgramTestingandDebugging64
ProgramMaintenance68
2-2HANDLINGRUNTIMEERRORS68
TerminateProgram69
SetaFlag69
C++Exceptions70
2-3OBJECTCOMPOSITION74
ThetimeCardClass75
ImplementingthetimeCardClass77
2-4OPERATOROVERLOADING82
OperatorFunctionsS5
OperatorOverloadingwithFreeFunctions86
OperatorOverloadingwithFriendFunctions87
OverloadingStreamI/OOperators89
MemberFunctionOverloading94
CHAPTERSUMMARY97
CLASSESANDLIBRARIESINTHECHAPTER98
REVIEWEXERCISES99
AnswerstoReviewExercises100
WRITTENEXERCISES102
PROGRAMMINGEXERCISES107
PROGRAMMINGPROJECTS108
3IntroductiontoAlgorithms
3-1SELECTIONSORT115
SelectionSortAlgorithm116
3-2SIMPLESEARCHALGORITHMS120
SequentialSearch120
BinarySearch122
3-3ANALYSISOFALGORITHMS127
System/MemoryPerformanceCriteria128
AlgorithmPerformanceCriteria:RunningTimeAnalysis128
Big-ONotation131
CommonOrdersofMagnitude133
3-4ANALYZINGTHESEARCHALGORITHMS135
BinarySearchRunningTime135
ComparingSearchAlgorithms136
3-5MAKINGALGORITHMSGENERIC139
TemplateSyntax140
RuntimeTemplateExpansion142
Template-BasedSearchingFunctions144
3-6THECONCEPTOFRECURSION146
ImplementingRecursiveFunctions148
HowRecursionWorks149
Application:MultibaseOutput152
3-7PROBLEMSOLVINGWITHRECURSION155
TowerofHanoi155
NumberTheory;TheGreatestCommonDivisor159
Applicationofgcd-RationalNumbers161
EvaluatingRecursion164
CHAPTERSUMMARY168
CLASSESANDLIBRARIESINTHECHAPTER169
REVIEWEXERCISES169
AnswerstoReviewExercises172
WRITTENEXERCISES173
PROGRAMMINGEXERCISES179
PROGRAMMINGPROJECT182
4TheVectorContainer
4-1OVERVIEWOFSTLCONTAINERCLASSES184
4-2TEMPLATECLASSES188
ConstructingaTemplateClass188
DeclaringTemplateClassObjects191
4-3THEVECTORCLASS192
IntroducingtheVectorContainer195
TheVectorAPI200
4-4VECTORAPPLICATIONS202
JoiningVectors203
TheInsertionSort203
CHAPTERSUMMARY208
CLASSESANDLIBRARIESINTHECHAPTER209
REVIEWEXERCISES209
AnswerstoReview,Exercises211
WRITTENEXERCISES211
PROGRAMMINGEXERCISES216
PROGRAMMINGPROJECT217
5PointersandDynamicMemory
5-1C++POINTERS221
DeclaringPointerVariables222
AssigningValuestoPointers222
AccessingDatawithPointers224
ArraysAndPointers225
PointersandClassTypes227
5-2DYNAMICMEMORY229
TheMemoryAllocationOperatornew229
DynamicArrayAllocation231
TheMemoryDeallocationOperatordelete232
5-3CLASSESUSINGDYNAMICMEMORY234
TheClassdynamicClass234
TheDestructor236
5-4ASSIGNMENTANDINITIALIZATION240
AssignmentIssues240
OverloadingtheAssignmentOperator242
ThePointerthis243
InitializationIssues243
CreatingaCopyConstructor244
5-5THEMINIVECTORCLASS247
DesignoftheminiVectorClass248
ReservingMoreCapacity251
TheMINIVectorConstructor,Destructor,andAssignment253
AddingandRemovingElementsfromaMINIVectorObject254
OverloadingtheIndexOperator258
5-6THEMATRIXCLASS260
DescribingtheMatrixContainer261
ImplementingMatrixFunctions265
CHAPTERSUMMARY266
CLASSESANDLIBRARIESINTHECHAPTER267
REVIEWEXERCISES268
AnswerstoReview,Exercises270
WRITTENEXERCISES271
PROGRAMMINGEXERCISES277
PROGRAMMINGPROJECT279
6TheListContainerandIterators
6-1THELISTCONTAINER282
ThelistADT2S4
ThelistAPI286
Application:AListPalindrome288
6-2ITERATORS290
TheIteratorConcept290
ConstantIterators294
TheSequentialSearchofaList296
Application:WordFrequencies298
6-3GENERALLISTINSERTANDERASEOPERATIONS302
OrderedLists305
RemovingDuplicates307
SplicingTwoLists309
6-4CASESTUDY:GRADUATIONLISTS310
ProblemAnalysis310
ProgramDesign310
ProgramImplementation312
CHAPTERSUMMARY315
CLASSESANDLIBRARIESINTHECHAPTER316
REVIEWEXERCISES316
AnswerstoReviewExercises318
WRITTENEXERCISES319
PROGRAMMINGEXERCISES322
PROGRAMMINGPROJECT325
7Stacks
7-1THESTACKADT328
MultibaseOutput332
UncouplingStackElements336
7-2RECURSIVECODEANDTHERUNTIMESTACK339
7-3STACKIMPLEMENTATION342
miniStackClassImplementation345
ImplementationoftheSTLstackClass(Optional)346
7-4POSTFIXEXPRESSIONS347
PostfixEvaluation349
ThepostfixEvalClass350
7-5CASESTUDY:INFIXEXPRESSIONEVALUATION357
InfixExpression.Attributes358
InfixtoPostfixConversion:AlgorithmDesign359
InfixtoPostfixConversion:ObjectDesign364
infix2PostfixClassImplementation366
CHAPTERSUMMARY372
CLASSESINTHECHAPTER373
REVIEWEXERCISES373
AnswerstoReviewExercises375
WRITTENEXERCISES377
PROORAMMINGEXERCISES381
PROGRAMMINGPROJECTS382
8QueuesandPriorityQueues
8-1THEQUEUEADT386
application:SchedulingQueue388
8-2THERADIXSORT390
RadixSortAlgorithm391
8-3IMPLEMENTINGTHEMINIQUEUECLASS395
ImplementationoftheSTLqueueClass(Optional)398
8-4CASESTUDY:TIME-DRIVENSIMULATION399
SimulationDesign400
SimulationImplementation401
8-5ARRAY-BASEDQUEUEIMPLEMENTATION406
DesigningtheBoundedQueue409
ImplementingtheBoundedQueue411
8-6PRIORITYQUEUES412
PriorityQueueADT413
SortingwithaPriorityQueue415
CompanySupportServices417
CHAPTERSUMMARY421
CLASSESANDLIBRARIESINTHECHAPTER422
REVIEWEXERCISES423
AnswerstoReviewExercises425
WRITTENEXERCISES426
PROGRAMMINGEXERCISES430
PROGRAMMINGPROJECT432
9LinkedLists
9-1LINKEDLISTNODES438
ThenodeClass439
AddingandRemovingNodes442
9-2BUILDINGLINICEDLISTS443
DefiningaSinglyLinkedList443
InsertingattheFrontofaLinkedList445
ErasingattheFrontofaLinkedList447
RemovingaTargetNode44S
9-3HANDLINGTHEBACKOFTHELIST452
DesigningaNewLinkedListStructure453
9-4IMPLEMENTINGALINKEDQUEUE455
ThelinkedQueueClass456
ImplementingthelinkedQueueClass457
9-5DOUBLYLINKEDLISTS462
dnodeObjects463
CircularDoublyLinkedLists466
9-6UPDATINGADOUBLYLINKEDLIST468
Theinsert()Function468
Theerase()Function470
9-7THEJOSEPHUSPROBLEM474
9-8THEMINILISTCLASS477
miniListClassPrivateMembers478
miniListClassConstructorsandDestructor479
FunctionsDealingwiththeEndsofaList480
miniListIterators481
TheminiListMemberFunctionsbegin()andend()485
TheGeneralListInsertFunction485
9-9SELECTINGASEOUENCECONTAINER486
CHAPTERSUMMARY487
CLASSESANDLIBRARIESINTHECHAPTER489
REVIEWEXERCISES489
AnswerstoReviewExercises493
WRITTENEXERCISES495
PROGRAMMINGEXERCISES498
PROGRAMMINGPROJECT500
10BinaryTrees
10-1TREESTRUCTURES504
TreeTerminology505
BinaryTrees506
10-2BINARYTREENODES510
BuildingaBinaryTree511
10-3BINARYTREESCANALGORITHMS514
RecursiveTreeTraversals514
IterativeLevel-OrderScan518
10-4USINGTREESCANALGORITHMS522
ComputingtheLeafCount522
ComputingtheDepthsofaTree523
CopyingaBinaryTree526
DeletingTreeNodes.529
DisplayingaBinaryTree.530
10-5BINARYSEARCHTREES532
鄂公网安备 42010302001612号 