An edition of Data structures, algorithms, and applications in C++ (1998)

Data Structures, Algorithms, And Applications In C++

2 edition

by

  • 8 Want to read
  • 1 Currently reading
Cover of: Data Structures, Algorithms, And Applications In C++ by Sartaj Sahni, Sartaj Sahni
Preview
Borrow

My Reading Lists:

Create a new list
Notes
  • 8 Want to read
  • 1 Currently reading
Notes

Check nearby libraries

Buy this book

Last edited by Drini
September 14, 2025 | History
Edit
An edition of Data structures, algorithms, and applications in C++ (1998)

Data Structures, Algorithms, And Applications In C++

2 edition

by

  • 8 Want to read
  • 1 Currently reading

This edition doesn't have a description yet. Can you add one?

Publish Date
Publisher
Silicon Press
Language
English
Pages
792

Check nearby libraries

Buy this book

Previews available in: English

Subjects

C++ (Computer program language), C (Computer program language), C plus plus (computer program language), Data structures (Computer science), Computer algorithms, Application software, Development
Edition Availability
Cover of: Data Structures, Algorithms, And Applications In C++
Data Structures, Algorithms, And Applications In C++
August 31, 2004, Silicon Press
Paperback in English - 2 edition
Cover of: Data structures, algorithms, and applications in C [plus plus].
Data structures, algorithms, and applications in C [plus plus].
1998, WCB/McGraw-Hill
in English
Cover of: Data structures, algorithms, and applications in C++
Data structures, algorithms, and applications in C++
1998, WCB/McGraw-Hill
in English

Add another edition?

Book Details

Table of Contents

Part I. Preliminaries
1. C++ Review
Page 1
1.1. Introduction
Page 3
1.2. Functions and Parameters
Page 3
1.2.1. Value Parameters
Page 3
1.2.2. Template Functions
Page 1
1.2.3. Reference Parameters
Page 5
1.2.4. Const Reference Parameters
Page 6
1.2.5. Return Values
Page 6
1.2.6. Overloaded Functions
Page 7
1.3. Exceptions
Page 9
1.3.1. Throwing an Exception
Page 9
1.3.2. Handling Exceptions
Page 10
1.4. Dynamic Memory Allocation
Page 12
1.4.1. The operator new
Page 12
1.4.2. One-Dimensional Arrays
Page 13
1.4.3. Exception Handling
Page 13
1.4.4. The operator delete
Page 13
1.4.5. Two-Dimensional Arrays
Page 14
1.5. Your Very Own Data Type
Page 17
1.5.1. The class currency
Page 17
1.5.2. Using a Different Representation
Page 24
1.5.3. Operator Overloading
Page 26
1.5.4. Friends and Protected Class Members
Page 28
1.5.5. Addition of #ifndef, #define, and #endif Statements
Page 30
1.6. The Exception Class illegalParameterValue
Page 33
1.7. Recursion
Page 33
1.7.1. Recursive Mathematical Functions
Page 35
1.7.2. Induction
Page 36
1.7.3. Recursive C++ Functions
Page 37
1.8. The Standard Templates Library
Page 43
1.9. Testing and Debugging
Page 47
1.9.1. What Is Testing?
Page 47
1.9.2. Designing Test Data
Page 50
1.9.3. Debugging
Page 53
1.10. References and Selected Readings
Page 54
2. Performance Analysis
Page 55
2.1. What Is Performance?
Page 57
2.2. Space Complexity
Page 58
2.2.1. Components of Space Complexity
Page 58
2.2.2. Examples
Page 63
2.3. Time Complexity
Page 66
2.3.1. Components of Time Complexity
Page 66
2.3.2. Operation Counts
Page 67
2.3.3. Best, Worst, and Average Operation Counts
Page 73
2.3.4. Step Counts
Page 80
3. Asymptotic Notation
Page 95
3.1. Introduction
Page 96
3.2. Asymptotic Notation
Page 99
3.2.1. Big Oh Notation (O)
Page 99
3.2.2. Omega (Ω) and Theta (Θ) Notations
Page 102
3.3. Asymptotic Mathematics (Optional)
Page 104
3.3.1. Big Oh Notation (O)
Page 104
3.3.2. Omega Notation (Ω)
Page 107
3.3.3. Theta Notation (Θ)
Page 109
3.3.4. Little Oh Notation (o)
Page 111
3.3.5. Properties
Page 111
3.4. Complexity Analysis Examples
Page 114
3.5. Practical Complexities
Page 117
3.6. References and Selected Readings
Page 120
4. Performance Measurement
Page 121
4.1. Introduction
Page 122
4.2. Choosing Instance Size
Page 123
4.3. Developing the Test Data
Page 123
4.4. Setting Up the Experiment
Page 124
4.5. Your Cache and You
Page 131
4.5.1. A Simple Computer Model
Page 131
4.5.2. Effect of Cache Misses on Run Time
Page 132
4.5.3. Matrix Multiplication
Page 133
4.6. References and Selected Readings
Page 136
Part II. Data Structures
5. Linear Lists—Array Representation
Page 137
5.1. Data Objects and Structures
Page 139
5.2. The Linear List Data Structure
Page 140
5.2.1. The Abstract Data Type linearList
Page 141
5.2.2. The Abstract Class LinearList
Page 142
5.3. Array Representation
Page 143
5.3.1. The Representation
Page 143
5.3.2. Changing the Length of a One-Dimensional Array
Page 145
5.3.3. The Class arrayList
Page 146
5.3.4. Iterators in C++
Page 153
5.3.5. An Iterator for arrayList
Page 155
5.4. Vector Representation
Page 161
5.5. Multiple Lists in a Single Array
Page 163
5.6. Performance Measurement
Page 166
5.7. References and Selected Readings
Page 169
6. Linear Lists—Linked Representation
Page 170
6.1. Singly Linked Lists and Chains
Page 172
6.1.1. The Representation
Page 172
6.1.2. The Struct chainNode
Page 174
6.1.3. The Class chain
Page 174
6.1.4. Extensions to the ADT linearList
Page 181
6.1.5. The Class extendedChain
Page 182
6.1.6. Performance Measurement
Page 183
6.2. Circular Lists and Header Nodes
Page 192
6.3. Doubly Linked Lists
Page 195
6.4. Glossary of Linked List Terms
Page 197
6.5. Applications
Page 197
6.5.1. Bin Sort
Page 197
6.5.2. Radix Sort
Page 202
6.5.3. Convex Hull
Page 205
6.5.4. Union-Find Problem
Page 209
7. Arrays and Matrices
Page 222
7.1. Arrays
Page 223
7.1.1. The Abstract Data Type
Page 223
7.1.2. Indexing a C++ Array
Page 224
7.1.3. Row- and Column-Major Mappings
Page 224
7.1.4. Array of Arrays Representation
Page 227
7.1.5. Row-Major and Column-Major Representation
Page 227
7.1.6. Irregular Two-Dimensional Arrays
Page 228
7.2. Matrices
Page 230
7.2.1. Definitions and Operations
Page 230
7.2.2. The Class matrix
Page 233
7.3. Special Matrices
Page 239
7.3.1. Definitions and Applications
Page 239
7.3.2. Diagonal Matrices
Page 242
7.3.3. Tridiagonal Matrix
Page 244
7.3.4. Triangular Matrices
Page 245
7.3.5. Symmetric Matrices
Page 246
7.4. Sparse Matrices
Page 252
7.4.1. Motivation
Page 252
7.4.2. Representation Using a Single Linear List
Page 252
7.4.3. Representation Using Many Linear Lists
Page 258
7.4.4. Performance Measurement
Page 262
8. Stacks
Page 269
8.1. Definition and Applications
Page 271
8.2. The Abstract Data Type
Page 274
8.3. Array Representation
Page 274
8.3.1. Implementation as a Derived Class
Page 274
8.3.2. The Class arrayStack
Page 277
8.3.3. Performance Measurement
Page 277
8.4. Linked Representation
Page 282
8.4.1. The Class derivedLinkedStack
Page 282
8.4.2. The Class linkedStack
Page 282
8.4.3. Performance Measurement
Page 282
8.5. Applications
Page 284
8.5.1. Parenthesis Matching
Page 284
8.5.2. Towers of Hanoi
Page 285
8.5.3. Rearranging Railroad Cars
Page 289
8.5.4. Switch Box Routing
Page 294
8.5.5. Offline Equivalence Class Problem
Page 297
8.5.6. Rat in a Maze
Page 300
8.6. References and Selected Readings
Page 316
9. Queues
Page 317
9.1. Definition and Applications
Page 319
9.2. The Abstract Data Type
Page 320
9.3. Array Representation
Page 322
9.3.1. The Representation
Page 322
9.3.2. The Class arrayQueue
Page 325
9.4. Linked Representation
Page 330
9.5. Applications
Page 333
9.5.1. Railroad Car Rearrangement
Page 333
9.5.2. Wire Routing
Page 336
9.5.3. Image-Component Labeling
Page 341
9.5.4. Machine Shop Simulation
Page 344
9.6. References and Selected Readings
Page 361
10. Skip Lists and Hashing
Page 362
10.1. Dictionaries
Page 364
10.2. The Abstract Data Type
Page 366
10.3. Linear List Representation
Page 367
10.4. Skip List Representation (Optional)
Page 368
10.4.1. The Ideal Case
Page 368
10.4.2. Insertions and Deletions
Page 372
10.4.3. Assigning Levels
Page 373
10.4.4. The Struct skipNode
Page 374
10.4.5. The Class skipList
Page 374
10.4.6. Complexity of skipList Methods
Page 378
10.5. Hash Table Representation
Page 381
10.5.1. Ideal Hashing
Page 381
10.5.2. Hash Functions and Tables
Page 382
10.5.3. Linear Probing
Page 387
10.5.4. Hashing with Chains
Page 394
10.6. An Application—Text Compression
Page 402
10.6.1. LZW Compression
Page 403
10.6.2. Implementation of LZW Compression
Page 403
10.6.3. LZW Decompression
Page 409
10.6.4. Implementation of LZW Decompression
Page 411
10.6.5. Performance Evaluation
Page 413
10.7. References and Selected Readings
Page 116
11. Binary and Other Trees
Page 418
11.1. Trees
Page 420
11.2. Binary Trees
Page 425
11.3. Properties of Binary Trees
Page 426
11.4. Representation of Binary Trees
Page 429
11.4.1. Array-Based Representation
Page 429
11.4.2. Linked Representation
Page 430
11.5. Common Binary Tree Operations
Page 432
11.6. Binary Tree Traversal
Page 432
11.7. The ADT Binary Tree
Page 439
11.8. The Class linkedBinaryTree
Page 439
11.9. Applications
Page 443
11.9.1. Placement of Signal Boosters
Page 443
11.9.2. Union-Find Problem
Page 450
11.10. References and Selected Readings
Page 463
12. Priority Queues
Page 464
12.1. Definition and Applications
Page 466
12.2. The Abstract Data Type
Page 467
12.3. Linear Lists
Page 468
12.4. Heaps
Page 469
12.4.1. Definitions
Page 469
12.4.2. Insertion into a Max Heap
Page 470
12.4.3. Deletion from a Max Heap
Page 471
12.4.4. Max Heap Initialization
Page 472
12.4.5. The Class maxHeap
Page 474
12.4.6. Heaps and the STL
Page 478
12.5. Leftist Trees
Page 479
12.5.1. Height- and Weight-Biased Min and Max Leftist Trees
Page 479
12.5.2. Insertion into a Max HBLT
Page 482
12.5.3. Deletion from a Max HBLT
Page 482
12.5.4. Melding Two Max HBLTs
Page 482
12.5.5. Initialization
Page 485
12.5.6. The Class maxHblt
Page 185
12.6. Applications
Page 491
12.6.1. Heap Sort
Page 491
12.6.2. Machine Scheduling
Page 493
12.6.3. Huffman Codes
Page 497
12.7. References and Selected Readings
Page 504
13. Tournament Trees
Page 505
13.1. Winner Trees and Applications
Page 506
13.2. The ADT Winner Tree
Page 511
13.3. Winner Tree Implementation
Page 511
13.3.1. Representation
Page 511
13.3.2. Initializing a Winner Tree
Page 513
13.3.3. Replaying Matches
Page 514
13.3.4. The Class completeWinnerTree
Page 514
13.4. Loser Trees
Page 515
13.5. Applications
Page 518
13.5.1. Bin Packing Using First Fit
Page 518
13.5.2. Bin Packing Using Next Fit
Page 524
13.6. References and Selected Readings
Page 528
14. Binary Search Trees
Page 529
14.1. Definitions
Page 531
14.1.1. Binary Search Trees
Page 531
14.1.2. Indexed Binary Search Trees
Page 532
14.2. Abstract Data Types
Page 533
14.3. Binary Search Tree Operations and Implementation
Page 535
14.3.1. The Class binarySearchTree
Page 535
14.3.2. Searching
Page 536
14.3.3. Inserting an Element
Page 536
14.3.4. Deleting an Element
Page 536
14.3.5. Height of a Binary Search Tree
Page 540
14.4. Binary Search Trees with Duplicates
Page 544
14.5. Indexed Binary Search Trees
Page 545
14.6. Applications
Page 548
14.6.1. Histogramming
Page 548
14.6.2. Best-Fit Bin Packing
Page 550
14.6.3. Crossing Distribution
Page 553
15. Balanced Search Trees
Page 563
15.1. AVL Trees
Page 566
15.1.1. Definition
Page 566
15.1.2. Height of an AVL Tree
Page 567
15.1.3. Representation of an AVL Tree
Page 567
15.1.4. Searching an AVL Search Tree
Page 567
15.1.5. Inserting into an AVL Search Tree
Page 567
15.1.6. Deletion from an AVL Search Tree
Page 572
15.2. Red-Black Trees
Page 577
15.2.1. Definition
Page 577
15.2.2. Representation of a Red-Black Tree
Page 579
15.2.3. Searching a Red-Black Tree
Page 579
15.2.4. Inserting into a Red-Black Tree
Page 579
15.2.5. Deletion from a Red-Black Tree
Page 584
15.2.6. Implementation Considerations and Complexity
Page 588
15.3. Splay Trees
Page 592
15.3.1. Introduction
Page 592
15.3.2. The Splay Operation
Page 593
15.3.3. Amortized Complexity
Page 595
15.4. B-Trees
Page 598
15.4.1. Indexed Sequential Access Method (ISAM)
Page 598
15.4.2. m-Way Search Trees
Page 599
15.4.3. B-Trees of Order m
Page 602
15.4.4. Height of a B-Tree
Page 603
15.4.5. Searching a B-Tree
Page 604
15.4.6. Inserting into a B-Tree
Page 604
15.4.7. Deletion from a B-Tree
Page 607
15.4.8. Node Structure
Page 612
15.5. References and Selected Readings
Page 614
16. Graphs
Page 615
16.1. Definitions
Page 616
16.2. Applications and More Definitions
Page 617
16.3. Properties
Page 622
16.4. The ADT graph
Page 625
16.5. Representation of Unweighted Graphs
Page 627
16.5.1. Adjacency Matrix
Page 627
16.5.2. Linked Adjacency Lists
Page 629
16.5.3. Array Adjacency Lists
Page 629
16.6. Representation of Weighted Graphs
Page 632
16.7. Class Implementations
Page 634
16.7.1. The Different Classes
Page 634
16.7.2. Adjacency-Matrix Classes
Page 635
16.7.3. An Extension to the Class chain
Page 640
16.7.4. Linked-List Classes
Page 640
16.8. Graph Search Methods
Page 644
16.8.1. Breadth-First Search
Page 644
16.8.2. Implementation of Breadth-First Search
Page 646
16.8.3. Complexity Analysis of graph::bfs
Page 646
16.8.4. Depth-First Search
Page 647
16.8.5. Implementation of Depth-First Search
Page 650
16.8.6. Complexity Analysis of graph::dfs
Page 651
16.9. Applications Revisited
Page 652
16.9.1. Finding a Path
Page 652
16.9.2. Connected Graphs and Components
Page 652
16.9.3. Spanning Trees
Page 655
Part III. Algorithm-Design Methods
17. The Greedy Method
Page 660
17.1. Optimization Problems
Page 662
17.2. The Greedy Method
Page 663
17.3. Applications
Page 668
17.3.1. Container Loading
Page 668
17.3.2. 0/1 Knapsack Problem
Page 669
17.3.3. Topological Sorting
Page 673
17.3.4. Bipartite Cover
Page 678
17.3.5. Single-Source Shortest Paths
Page 682
17.3.6. Minimum-Cost Spanning Trees
Page 687
17.4. References and Selected Readings
Page 703
18. Divide and Conquer
Page 704
18.1. The Method
Page 705
18.2. Applications
Page 715
18.2.1. Defective Chessboard
Page 715
18.2.2. Merge Sort
Page 719
18.2.3. Quick Sort
Page 726
18.2.4. Selection
Page 733
18.2.5. Closest Pair of Points
Page 737
18.3. Solving Recurrence Equations
Page 749
18.4. Lower Bounds on Complexity
Page 751
18.4.1. Lower Bound for the Minmax Problem
Page 752
18.4.2. Lower Bound for Sorting
Page 754
19. Dynamic Programming
Page 757
19.1. The Method
Page 758
19.2. Applications
Page 761
19.2.1. 0/1 Knapsack Problem
Page 761
19.2.2. Matrix Multiplication Chains
Page 766
19.2.3. All-Pairs Shortest Paths
Page 773
19.2.4. Single-Source Shortest Paths with Negative Costs
Page 776
19.2.5. Noncrossing Subset of Nets
Page 784
19.3. References and Selected Readings
Page 792
20. Backtracking (On the Web)
Page 793
20.1. The Method
Page 795
20.2. Applications
Page 802
20.2.1. Container Loading
Page 802
20.2.2. 0/1 Knapsack Problem
Page 809
20.2.3. Max Clique
Page 812
20.2.4. Traveling Salesperson
Page 817
20.2.5. Board Permutation
Page 821
21. Branch and Bound (On the Web)
Page 829
21.1. The Method
Page 830
21.2. Applications
Page 834
21.2.1. Container Loading
Page 834
21.2.2. 0/1 Knapsack Problem
Page 842
21.2.3. Max Clique
Page 844
21.2.4. Traveling Salesperson
Page 848
21.2.5. Board Permutation
Page 853
Index
Page I-1

Classifications

Library of Congress
QA76.73.C153 S25 2005

The Physical Object

Format
Paperback
Number of pages
792
Dimensions
9.1 x 6.1 x 1.8 inches
Weight
2.6 pounds

Edition Identifiers

Open Library
OL8357370M
Internet Archive
datastructuresal0002sahn
ISBN 10
0929306325
ISBN 13
9780929306322
LCCN
2004010933
OCLC/WorldCat
55475078
LibraryThing
1022396
Goodreads
1837076

Work Identifiers

Work ID
OL2706247W

Source records

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON / OPDS | Wikipedia citation
September 14, 2025 Edited by Drini Add TOC from Tocky
August 11, 2024 Edited by MARC Bot import existing book
December 20, 2023 Edited by ImportBot import existing book
July 21, 2023 Edited by ImportBot import existing book
April 29, 2008 Created by an anonymous user Imported from amazon.com record