Applied Data Structures with C++

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9780763725624 | 0763725625
Cover: Paperback
Copyright: 3/1/2004

Rent

(Recommended)

$127.88

Term

Due

Price

Semester

Dec 12

$142.10

Quarter

Sep 5

$134.99

Short Term

Aug 13

$127.88

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping bag.
Buy New

Usually Ships in 3-5 Business Days

$181.93

Designed for use in either a one- or two-semester advanced data structures course, Applied Data Structures with C++ covers all of the fundamental structures and data types and features implementations presented in C++. Using clear explanations and efficient examples, The book presents a comprehensive overview of main memory and file-based structures, with an emphasis on files and persistent structures. Additional coverage of object-oriented design, persistence, recursion, and databases as large-scale file structures supplements the standard approach to fundamental topics. Material can be adapted flexibly according To The focus or length of the course, with suggestions for use in one- and two-semester formats from the author. Topics in Advanced Data Structures and Databases include: Programming with Objects Lists and Strings Sets: Set ADT, implementation, Sets in STL Stacks and Queues Maps: Hash Tables Binary Trees, Tries, and Ternary Trees Graphs Hardware foundations of persistent objects Files and Objects Sorting Maps: Hash files Static Indexes Dynamic Indexes Secondary Key retrievals File structure selection, files and databases, object databases

Part I Transient Objects

(344)

Chapter 1 Programming with Objects

(32)

1.1 Introduction

(1)

1.2 Object-Oriented Design

(5)

1.3 Templates and the Standard Template Library

(8)

1.3.1 Templates

(7)

1.3.2 The Standard Template Library

(1)

1.4 Objects and Secondary Memory

(1)

1.5 Recursion

(4)

1.5.1 Examples of Recursion

(2)

1.5.2 Iteration or Recursion?

(1)

1.6 Measures of Complexity

(11)

1.6.1 Big-O and Related Analyses

(5)

1.6.2 Complexity of Problems

(2)

Chapter Summary

(1)

Exercises

(1)

Problems

(1)

References

(1)

Notes

(2)

Chapter 2 Lists and Strings

(54)

2.1 Introduction

(1)

2.2 Basic List Operations

(1)

2.3 List Implementations

(23)

2.3.1 Arrays

(3)

2.3.2 Single-Linked Lists

(14)

2.3.3 Skip Lists

(3)

2.3.4 Double-Linked Lists

(3)

2.4 Lists and the STL

(3)

2.5 General Lists

(4)

2.6 List Applications

(5)

2.6.1 Memo Functions

(2)

2.6.2 Multilength Arithmetic

(1)

2.6.3 Polynomials

(1)

2.6.4 Sparse Vectors and Matrices

(1)

2.7 Basic String Operations

(1)

2.8 String Implementation

(4)

2.8.1 C-Style Strings

(1)

2.8.2 The String.h Header File

(2)

2.8.3 Strings and the STL

(1)

2.9 String Applications

(11)

2.9.1 Word Frequencies

(2)

2.9.2 String Searching

(4)

Chapter Summary

(1)

Exercises

(2)

Problems

(2)

References

(1)

Notes

(2)

Chapter 3 Sets

(36)

3.1 Introduction

(1)

3.2 Basic Set Operations

(2)

3.2.1 Class Definition

(1)

3.2.2 Set-Set Operators

(1)

3.3 Implementation of Sets

(19)

3.3.1 Linked List

(7)

3.3.2 Bit Map

(12)

3.4 Sets in the STL

111

(2)

3.5 Applications of Sets

113

(10)

3.5.1 Factorization

113

(2)

3.5.2 Processing Lottery Tickets

115

(3)

Chapter Summary

118

(1)

Exercises

118

(3)

Problems

121

(2)

References

123

(1)

Notes

123

(2)

Chapter 4 Stacks and Queues

125

(48)

4.1 Introduction

125

(1)

4.2 Stacks

126

(19)

4.2.1 Basic Stack Operations

126

(2)

4.2.2 Stack Implementations

128

(2)

4.2.3 Stack Applications

130

(15)

4.3 Queues

145

(11)

4.3.1 Basic Queue Operations

145

(1)

4.3.2 Queue Implementations

146

(2)

4.3.3 Queue Applications

148

(8)

4.4 Priority Queues

156

(7)

4.4.1 Priority Queue Implementation

157

(1)

4.4.2 Priority Queue Applications

157

(6)

4.5 Stacks, Queues, and the STL

163

(8)

4.5.1 Stacks

163

(1)

4.5.2 Queues

164

(2)

Chapter Summary

166

(1)

Exercises

166

(3)

Problems

169

(2)

Notes

171

(2)

Chapter 5 Maps: Hash Tables

173

(50)

5.1 Introduction

173

(4)

5.1.1 Primary Key

174

(1)

5.1.2 Overview of Hashing

174

(1)

5.1.3 Example of a Simple Hash Table

175

(2)

5.2 Bucket Size

177

(1)

5.3 Packing Density

178

(1)

5.4 Hash Function

178

(6)

5.4.1 Example Hash Function

179

(1)

5.4.2 A General Hash Function

179

(3)

5.4.3 A Hash Function for Strings

182

(2)

5.5 Overflow Resolution

184

(10)

5.5.1 Open Addressing

184

(8)

5.5.2 Closed Addressing (Chaining)

192

(2)

5.6 Hash Table Implementations

194

(11)

5.6.1 map_hash_bounded

195

(5)

5.6.2 map_hash_unbounded

200

(5)

5.7 Applications

205

(14)

5.7.1 A Spelling Checker

205

(4)

5.7.2 A Password Manager

209

(5)

Chapter Summary

214

(1)

Exercises

214

(3)

Problems

217

(1)

References

218

(1)

Notes

219

(4)

Chapter 6 Maps: Binary Trees, Tries, and Ternary Trees

223

(82)

6.1 Introduction

223

(6)

6.1.1 Overview of Trees

224

(1)

6.1.2 Binary Trees

225

(4)

6.2 Binary Search Trees

229

(12)

6.2.1 Implementation: map_bst Class

230

(5)

6.2.2 Random Trees

235

(2)

6.2.3 Deletions from a Binary Search Tree

237

(2)

6.2.4 Worst-Case Behavior

239

(2)

6.3 AVL Trees

241

(12)

6.3.1 Insertion into an AVL Tree

242

(6)

6.3.2 Implementation

248

(1)

6.3.3 Deletion from an AVL Tree

248

(3)

6.3.4 Bounds on an AVL Tree

251

(2)

6.4 Tries

253

(19)

6.4.1 The Variants

253

(12)

6.4.2 Map Implementation

265

(4)

6.4.3 Trie Algorithms

269

(3)

6.5 Ternary Trees

272

(7)

6.5.1 Example Ternary Tree

273

(3)

6.5.2 Implementation

276

(1)

6.5.3 Comparison with Hash Tables and Binary Trees

277

(1)

6.5.4 Partial-Match Searches

277

(2)

6.6 Binary Tree Applications

279

(24)

6.6.1 Expression Trees

279

(12)

6.6.2 Huffman Codes

291

(5)

Chapter Summary

296

(1)

Exercises

297

(2)

Problems

299

(4)

References

303

(1)

Notes

303

(2)

Chapter 7 Graphs

305

(40)

7.1 Introduction

305

(6)

7.1.1 Terminology

305

(2)

7.1.2 Graphical Representations

307

(4)

7.2 Basic Graph Operations

311

(1)

7.3 Graph Implementation

312

(3)

7.3.1 Sets

312

(1)

7.3.2 Adjacency Matrix

312

(2)

7.3.3 Linked Storage

314

(1)

7.4 Graph Algorithms

315

(16)

7.4.1 Finding a Path

315

(4)

7.4.2 Identifying the Path

319

(3)

7.4.3 Graph-Traversal Problem Solvers

322

(1)

7.4.4 Transitive Closure

322

(2)

7.4.5 Shortest Path

324

(3)

7.4.6 Spanning Tree

327

(4)

7.5 Activity Networks

331

(4)

7.5.1 Activity on Vertex

331

(2)

7.5.2 Activity on Edge

333

(2)

7.6 The Seven Bridges of Konigsburg

335

(3)

7.6.1 Konigsburg Today

337

(1)

7.6.2 Applications of Eulerian Paths and Cycles

337

(1)

7.6.3 Hamiltonian Paths and Cycles

338

(1)

7.7 Planar Graphs

338

(1)

Chapter Summary

339

(1)

Exercises

339

(3)

Problems

342

(1)

References

343

(1)

Notes

344

(1)

Part II Persistent Objects

345

(286)

Chapter 8 Hardware Foundations of Persistent Objects

347

(32)

8.1 Introduction

347

(1)

8.2 Memory Reliability

347

(6)

8.2.1 Simple Parity

348

(1)

8.2.2 Hamming Codes

349

(4)

8.2.3 Block Check Data

353

(1)

8.3 Disks, RAID, and Cache Memories

353

(16)

8.3.1 Disk Fundamentals

354

(3)

8.3.2 Read/Write Operations

357

(1)

8.3.3 RAID

358

(8)

8.3.4 Cache Memories

366

(3)

8.4 File Systems

369

(8)

8.4.1 Properties of a File System

369

(1)

8.4.2 Mapping Files to Disks

369

(3)

8.4.3 Hierarchical File Systems

372

(1)

Chapter Summary

373

(1)

Exercises

373

(3)

Problems

376

(1)

References

377

(1)

Notes

377

(2)

Chapter 9 Files and Objects

379

(28)

9.1 Introduction

379

(1)

9.2 Programming Language Interface

379

(13)

9.2.1 File Streams

379

(1)

9.2.2 Attaching and Detaching Files

380

(3)

9.2.3 Text Files and Binary Files

383

(2)

9.2.4 Serial Access and Direct Access

385

(7)

9.3 File Objects

392

(6)

9.3.1 Overview of Requirements

393

(1)

9.3.2 File Mode

393

(1)

9.3.3 BinaryFile Class Definition

393

(2)

9.3.4 Use of the BinaryFile Class

395

(3)

9.4 Saving Transient Objects

398

(5)

9.4.1 Overview

398

(1)

9.4.2 Implementation

398

(5)

Chapter Summary

403

(1)

Exercises

403

(1)

Problems

404

(1)

Notes

405

(2)

Chapter 10 Sorting

407

(40)

10.1 Introduction

407

(1)

10.2 Internal Sorting

408

(1)

10.2.1 Selection Sort

408

(1)

10.2.2 Heapsort

409

(1)

10.2.3 Mergesort

414

(1)

10.2.4 Quicksort

415

(1)

10.2.5 Comparison of Internal Sorting Algorithms

417

(1)

10.2.6 Stable Sorting Algorithms

418

(1)

10.3 External Sorting

419

(1)

10.3.1 Overview

419

(1)

10.3.2 Generating Sorted Partitions

421

(1)

10.3.3 Distribution and Merging

430

(1)

10.3.4 Comparison of Distribution and Merging Strategies

442

(1)

Chapter Summary

442

(1)

Exercises

443

(2)

Problems

445

(1)

References

446

(1)

Notes

446

(1)

Chapter 11 Maps: Hash Files

447

(68)

11.1 Introduction

447

(1)

11.2 Hash Files

448

(1)

11.2.1 Bucket Size

448

(1)

11.2.2 Packing Density

448

(1)

11.2.3 Hash Function

450

(1)

11.2.4 Overflows

451

(1)

11.2.5 Main Memory Enhancements to Hash Files

451

(1)

11.3 Table-Assisted Hashing

452

(1)

11.3.1 Insertions, Retrievals, and Deletions

454

(1)

11.3.2 Implementation: map_tah Class

458

(1)

11.3.3 Periodic Maintenance

467

(1)

11.4 Fixed-Length Versus Extensible Files

467

(1)

11.5 Dynamic Hashing

468

(1)

11.5.1 Insertions, Retrievals, and Deletions

468

(1)

11.5.2 Bitstring Function B

476

(1)

11.5.3 Implementation: map_dynamich Class

478

(1)

11.5.4 Saving and Restoring the Index

485

(1)

11.5.5 Storage Utilization

490

(1)

11.6 Extendible Hashing

490

(1)

11.6.1 Retrievals, Insertions, and Deletions

491

(1)

11.6.2 Implementation: map_exth Class

496

(10)

Chapter Summary

506

(1)

Exercises

506

(5)

Problems

511

(1)

References

512

(1)

Notes

512

(3)

Chapter 12 Maps: File-Based Trees

515

(54)

12.1 Introduction

515

(2)

12.2 Static Indexes

517

(1)

12.2.1 ISAM

517

(1)

12.2.2 Periodic Maintenance

523

(1)

12.3 Dynamic Indexes

523

(1)

12.3.1 VSAM

524

(1)

12.3.2 B-Trees

528

(1)

12.3.3 Variations on the B-Tree

552

(1)

12.3.4 B*-Trees

553

(1)

12.3.5 B+-Trees

557

(5)

12.4 Comparison of Static and Dynamic Indexes

562

(1)

Chapter Summary

563

(1)

Exercises

563

(3)

Problems

566

(1)

References

566

(1)

Notes

567

(2)

Chapter 13 Multimaps: Secondary Key Retrievals

569

(44)

13.1 Introduction

569

(1)

13.1.1 Indexed Versus Brute-force Searches

570

(1)

13.1.2 The World Wide Web

570

(1)

13.2 Inverted Files

571

(1)

13.2.1 Implementation of Indexes

573

(1)

13.2.2 Index Maintenance

578

(1)

13.2.3 Simple Query Processing

580

(1)

13.2.4 Application of Inverted Files

581

(1)

13.2.5 Weaknesses of Inverted Files

584

(1)

13.3 Grid Files

585

(1)

13.3.1 The Grid File Concept

586

(1)

13.3.2 Insertions and Deletions

589

(1)

13.3.3 Grid File Implementation

594

(1)

13.3.4 Data Declustering

604

(3)

Chapter Summary

607

(1)

Exercises

608

(2)

Problems

610

(1)

References

610

(1)

Notes

611

(2)

Chapter 14 Persistent Structures and Databases

613

(18)

14.1 Introduction

613

(1)

14.2 Selection of Persistent Structure

613

(1)

14.2.1 Summary of Structures

614

(1)

14.2.2 Factors in Structure Selection

615

(1)

14.2.3 A Selection Methodology

617

(2)

14.3 Comparison of Files and Databases

619

(1)

14.3.1 Advantages of Using Integrated Files

620

(1)

14.3.2 Disadvantages of Using Integrated Files

620

(1)

14.3.3 Data Independence

620

(1)

14.3.4 Database Models

621

(5)

14.4 Object Databases

626

(1)

14.4.1 Weaknesses of the Relational Model

626

(1)

14.4.2 Alternatives to the Relational Model

626

(1)

14.4.3 Object Database Management Systems

627

(1)

Chapter Summary

627

(1)

Exercises

628

(1)

Problems

629

(1)

References

629

(1)

Notes

630

(1)

Appendix A Random Numbers and Data Generation

631

(8)

A.1 Single-Seed PNG

631

(1)

A.2 Multiseed PNG

632

(1)

A.3 Example Applications of Single-Seed PNG

633

(4)

A.3.1 Example 1: A Uniform Distribution

633

(1)

A.3.2 Example 2: Unique Integers

634

(1)

A.3.3 Example 3: Nonuniform Distribution

635

(1)

A.3.4 Example 4: Matching a Distribution

636

(1)

References

637

(2)

Appendix B Data Normalization

639

(16)

B.1 Introduction

639

(1)

B.1.1 Update Anomalies

639

(1)

B.1.2 Running Example

640

(1)

B.2 First Normal Form (1NF)

640

(1)

B.3 Functional Dependencies

641

(1)

B.4 Second Normal Form (2NF)

642

(1)

B.5 Third Normal Form (3NF)

643

(1)

B.6 Boyce_Codd Normal Form

644

(1)

B.7 Fourth Normal Form (4NF)

645

(1)

B.8 Fifth Normal Form (5NF)

646

(3)

Summary

649

(1)

Exercises

649

(4)

Notes

653

(2)

Appendix C Test of File Object

655

(8)

Glossary

663

(12)

Index

675

Please wait while the item is added to your bag...

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Applied Data Structures with C++

Summary

Table of Contents

Supplemental Materials

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Applied Data Structures with C++

Summary

Table of Contents

Supplemental Materials

Digital License