数据结构C++语言描述：应用标准模板库（STL）

作　者：	William Ford William Topp
出版社：	清华大学出版社
丛编项：	应用标准模板库
版权说明：	本书为公共版权或经版权方授权，请支持正版图书
标　签：	数据结构

ISBN	出版时间	包装	开本	页数	字数
未知	暂无	暂无	未知	0	暂无

作者简介

暂缺《数据结构C++语言描述：应用标准模板库（STL）》作者简介

内容简介

本书是Ford和Topp两教授1996年所著“Data Structures with C++”的第2版，但在本书中应用了STL（标准模板库）。STL是ANSI C++1998中正式规定的，对常用的数据结构都进行了规范化并纳入其中。程序设计人员可以直接使用进行数据设计。本书的主要特点是：1.在全书中使用了STL容器类；2.对于每一容器类都提供了应用程序界面（API），可直接用于解决问题；3.作为现代数据结构核心的游标类，书中都进行了只管而精细的介绍；4.书中以同样细腻的风格介绍了诸如红黑树、散列表、堆、图等更为复杂的数据结构；5.作为数据结构的应用，作者提供了许多有关递归和继承的开发经验；6.每章都有学习目标和小结，许多完整的程序都给出运行结果，还提供了事例学习和复习题，每章的练习都给出了解答，还有大量的程序设计练习和程序设计项目实验。本书不仅可用作计算机专业本科生和研究生的教材，也可作为计算机专业人员自学数据结构的参考书。

图书目录

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