An edition of Fundamentals of data structures in C (1993)

Fundamentals of data structures in C++

by

  • ★★ 2.0 (1 rating)
  • 74 Want to read
  • 9 Currently reading
  • 2 Have read
Cover of: Fundamentals of data structures in C++ by Ellis Horowitz, Ellis Horowitz
Preview
Borrow

My Reading Lists:

Create a new list
Notes
  • ★★ 2.0 (1 rating)
  • 74 Want to read
  • 9 Currently reading
  • 2 Have read
Notes

Check nearby libraries

Buy this book

Last edited by MARC Bot
July 13, 2024 | History
Edit
An edition of Fundamentals of data structures in C (1993)

Fundamentals of data structures in C++

by

  • ★★ 2.0 (1 rating)
  • 74 Want to read
  • 9 Currently reading
  • 2 Have read

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

Publish Date
Publisher
Computer Science Press
Language
English
Pages
653

Check nearby libraries

Buy this book

Previews available in: English

Subjects

C (Computer program language), C [plus plus] (computer program language), C++ (Computer program language), C[plus plus] (Computer program language), Data structures (Computer science), C, Structures de donnees (informatique), C (langage de programmation), Datenstruktur, C plus plus (computer program language)
Edition Availability
Cover of: Fundamentals of data structures in C
Fundamentals of data structures in C
2007, Silicon Press
in English - 2nd ed.
Cover of: Fundamentals of data structures in C++
Fundamentals of data structures in C++
1995, Computer Science Press
in English
Cover of: Fundamentals of data structures in C [plus plus]
Fundamentals of data structures in C [plus plus]
1995, W. H. Freeman
in English
Cover of: Fundamentals of data structures in C
Fundamentals of data structures in C
1993, Computer Science Press
in English

Add another edition?

Book Details

Table of Contents

Preface
Page xv
Chapter 1. Basic Concepts
Page 1
1.1. Overview: System Life Cycle
Page 1
1.2. Object-Oriented Design
Page 4
1.2.1. Algorithmic Decomposition versus OO Decomposition
Page 4
1.2.2. Fundamental Definitions and Concepts of OO Programming
Page 5
1.2.3. Evolution of Programming Languages and History of C++
Page 5
1.3. Data Abstraction and Encapsulation
Page 6
1.4. Basics of C++
Page 11
1.4.1. Program Organization in C++
Page 11
1.4.2. Scope in C++
Page 12
1.4.3. C++ Statements and Operators
Page 13
1.4.4. Data Declarations in C++
Page 14
1.4.5. Comments in C++
Page 15
1.4.6. Input/Output in C++
Page 15
1.4.7. Functions in C++
Page 17
1.4.8. Parameter Passing in C++
Page 18
1.4.9. Function Name Overloading in C++
Page 19
1.4.10. Inline Functions
Page 19
1.4.11. Dynamic Memory Allocation in C++
Page 20
1.5. Algorithm Specification
Page 20
1.5.1. Introduction
Page 20
1.5.2. Recursive Algorithms
Page 25
1.6. Performance Analysis And Measurement
Page 30
1.6.1. Performance Analysis
Page 30
1.6.2. Performance Measurement
Page 51
1.6.3. Generating Test Data
Page 60
1.7. References And Selected Readings
Page 64
Chapter 2. Arrays
Page 66
2.1. Abstract Data Types and the C++ Class
Page 66
2.1.1. An Introduction to the C++ Class
Page 66
2.1.2. Data Abstraction and Encapsulation in C++
Page 67
2.1.3. Declaring Class Objects and Invoking Member Functions
Page 68
2.1.4. Special Class Operations
Page 68
2.1.5. Miscellaneous Topics
Page 73
2.1.6. ADTs and C++ Classes
Page 73
2.2. The Array as an Abstract Data Type
Page 75
2.3. The Polynomial Abstract Data Type
Page 77
2.3.1. Polynomial Representation
Page 80
2.3.2. Polynomial Addition
Page 82
2.3.3. Disadvantages of Representing Polynomials by Arrays
Page 84
2.4. Sparse Matrices
Page 87
2.4.1. Introduction
Page 87
2.4.2. Sparse Matrix Representation
Page 88
2.4.3. Transposing a Matrix
Page 89
2.4.4. Matrix Multiplication
Page 93
2.4.5. Disadvantages of Representing Sparse Matrices by Arrays
Page 98
2.5. Representation of Arrays
Page 100
2.6. The String Abstract Data Type
Page 104
2.6.1. String Pattern Matching: A Simple Algorithm
Page 105
2.6.2. String Pattern Matching: The KMP Algorithm
Page 106
2.7. References and Selected Readings
Page 111
2.8. Additional Exercises
Page 111
Chapter 3. Stacks and Queues
Page 119
3.1. Templates in C++
Page 119
3.1.1. Template Functions
Page 119
3.1.2. Using Templates to Represent Container Classes
Page 121
3.2. The Stack Abstract Data Type
Page 124
3.3. The Queue Abstract Data Type
Page 131
3.4. Subtyping and Inheritance in C++
Page 137
3.5. A Mazing Problem
Page 140
3.6. Evaluation of Expressions
Page 147
3.6.1. Expressions
Page 147
3.6.2. Postfix Notation
Page 148
3.6.3. Infix to Postfix
Page 150
3.7. Multiple Stacks And Queues
Page 154
3.8. Selected Readings And References
Page 158
3.9. Additional Exercises
Page 158
Chapter 4. Linked Lists
Page 161
4.1. Singly Linked Lists
Page 161
4.2. Representing Lists in C++
Page 165
4.2.1. Defining a List Node in C++
Page 165
4.2.2. Designing a List in C++
Page 166
4.2.3. Pointer Manipulation in C++
Page 170
4.2.4. List Manipulation Operations
Page 171
4.3. A Reusable Linked List Class
Page 174
4.3.1. Implementing Linked Lists with Templates
Page 175
4.3.2. Linked List Iterators
Page 176
4.3.3. Linked List Operations
Page 179
4.3.4. Reusing a Class
Page 182
4.4. Circular Lists
Page 183
4.5. Linked Stacks and Queues
Page 186
4.6. Polynomials
Page 190
4.6.1. Polynomial Representation
Page 190
4.6.2. Adding Polynomials
Page 190
4.6.3. Erasing Polynomials
Page 194
4.6.4. Circular List Representation of Polynomials
Page 195
4.6.5. Summary
Page 199
4.7. Equivalence Classes
Page 202
4.8. Sparse Matrices
Page 207
4.8.1. Sparse Matrix Representation
Page 207
4.8.2. Sparse Matrix Input
Page 209
4.8.3. Erasing a Sparse Matrix
Page 213
4.9. Doubly Linked Lists
Page 217
4.10. Generalized Lists
Page 221
4.10.1. Representation of Generalized Lists
Page 221
4.10.2. Recursive Algorithms for Lists
Page 225
4.10.3. Reference Counts, Shared and Recursive Lists
Page 230
4.11. Virtual Functions and Dynamic Binding in C++
Page 237
4.12. Heterogeneous Lists
Page 241
4.13. References and Selected Readings
Page 245
Chapter 5. Trees
Page 246
5.1. Introduction
Page 246
5.1.1. Terminology
Page 246
5.1.2. Representation of Trees
Page 249
5.2. Binary Trees
Page 252
5.2.1. The Abstract Data Type
Page 252
5.2.2. Properties of Binary Trees
Page 255
5.2.3. Binary Tree Representations
Page 257
5.3. Binary Tree Traversal and Tree Iterators
Page 261
5.3.1. Introduction
Page 261
5.3.2. Inorder Traversal
Page 262
5.3.3. Preorder Traversal
Page 263
5.3.4. Postorder Traversal
Page 263
5.3.5. Iterative Inorder Traversal
Page 265
5.3.6. Level-Order Traversal
Page 268
5.3.7. Traversal Without a Stack
Page 269
5.4. Additional Binary Tree Operations
Page 27
5.4.1. Copying Binary Trees
Page 271
5.4.2. Testing Equality
Page 271
5.4.3. The Satisfiability Problem
Page 272
5.5. Threaded Binary Trees
Page 277
5.5.1. Threads
Page 277
5.5.2. Inorder Traversal of a Threaded Binary Tree
Page 278
5.5.3. Inserting a Node into a Threaded Binary Tree
Page 281
5.6. Heaps
Page 283
5.6.1. Priority Queues
Page 283
5.6.2. Definition of a Max Heap
Page 285
5.6.3. Insertion into a Max Heap
Page 286
5.6.4. Deletion from a Max Heap
Page 288
5.7. Binary Search Trees
Page 291
5.7.1. Definition
Page 291
5.7.2. Searching a Binary Search Tree
Page 292
5.7.3. Insertion into a Binary Search Tree
Page 293
5.7.4. Deletion from a Binary Search Tree
Page 294
5.7.5. Joining and Splitting Binary Search Trees
Page 295
5.7.6. Height of a Binary Search Tree
Page 298
5.8. Selection Trees
Page 300
5.8.1. Introduction
Page 300
5.8.2. Winner Trees
Page 300
5.8.3. Loser Trees
Page 301
5.9. Forests
Page 304
5.9.1. Transforming a Forest into a Binary Search Tree
Page 304
5.9.2. Forest Traversals
Page 305
5.10. Set Representation
Page 307
5.10.1. Introduction
Page 307
5.10.2. Union and Find Operations
Page 307
5.10.3. Application to Equivalence Classes
Page 316
5.11. An Object-Oriented System of Tree Data Structures
Page 319
5.12. Counting Binary Trees
Page 321
5.12.1. Distinct Binary Trees
Page 322
5.12.2. Stack Permutations
Page 323
5.12.3. Matrix Multiplication
Page 326
5.12.4. Number of Distinct Binary Trees
Page 327
5.13. References and Selected Readings
Page 328
Chapter 6. Graphs
Page 330
6.1. The Graph Abstract Data Type
Page 330
6.1.1. Introduction
Page 330
6.1.2. Definitions
Page 332
6.1.3. Graph Representations
Page 336
6.2. Elementary Graph Operations
Page 345
6.2.1. Depth First Search
Page 345
6.2.2. Breadth First Search
Page 347
6.2.3. Connected Components
Page 348
6.2.4. Spanning Trees
Page 348
6.2.5. Biconnected Components
Page 350
6.3. Minimum Cost Spanning Trees
Page 356
6.3.1. Kruskal's Algorithm
Page 357
6.3.2. Prim's Algorithm
Page 361
6.3.3. Sollin's Algorithm
Page 361
6.4. Shortest Paths and Transitive Closure
Page 364
6.4.1. Single Source/All Destination: Nonnegative Edge Costs
Page 364
6.4.2. Single Source/All Destination: General Weights
Page 367
6.4.3. All-Pairs Shortest Paths
Page 371
6.4.4. Transitive Closure
Page 373
6.5. Activity Networks
Page 378
6.5.1. Activity on Vertex (AOV) Networks
Page 378
6.5.2. Activity on Edge (AOE) Networks
Page 383
6.6. References and Selected Readings
Page 393
6.7. Additional Exercises
Page 394
Chapter 7. Sorting
Page 397
7.1. Motivation
Page 397
7.2. Insertion Sort
Page 402
7.3. Quick Sort
Page 405
7.4. How Fast Can We Sort?
Page 408
7.5. Merge Sort
Page 410
7.5.1. Merging
Page 410
7.5.2. Iterative Merge Sort
Page 416
7.5.3. Recursive Merge Sort
Page 418
7.6. Heap Sort
Page 423
7.7. Sorting on Several Keys
Page 425
7.8. List and Table Sorts
Page 431
7.9. Summary of Internal Sorting
Page 439
7.10. External Sorting
Page 445
7.10.1. Introduction
Page 445
7.10.2. k-way Merging
Page 448
7.10.3. Buffer Handling for Parallel Operation
Page 450
7.10.4. Run Generation
Page 456
7.10.5. Optimal Merging of Runs
Page 458
7.11. References and Selected Readings
Page 463
Chapter 8. Hashing
Page 464
8.1. The Symbol Table Abstract Data Type
Page 464
8.2. Static Hashing
Page 466
8.2.1. Hash Tables
Page 466
8.2.2. Hashing Functions
Page 468
8.2.3. Overflow Handling
Page 471
8.2.4. Theoretical Evaluation of Overflow Techniques
Page 478
8.3. Dynamic Hashing
Page 482
8.3.1. Motivation for Dynamic Hashing
Page 482
8.3.2. Dynamic Hashing using Directories
Page 483
8.3.3. Analysis of Directory-Based Dynamic Hashing
Page 489
8.3.4. Directoryless Dynamic Hashing
Page 491
8.4. References and Selected Readings
Page 496
Chapter 9. Heap Structures
Page 497
9.1. Min-Max Heaps
Page 497
9.1.1. Definitions
Page 497
9.1.2. Insertion into a Min-Max Heap
Page 499
9.1.3. Deletion of the Min Element
Page 502
9.2. Deaps
Page 507
9.2.1. Definition
Page 50
9.2.2. Insertion into a Deap
Page 508
9.2.3. Deletion of the Min Element
Page 511
9.3. Leftist Trees
Page 515
9.4. Binomial Heaps
Page 522
9.4.1. Cost Amortization
Page 522
9.4.2. Definition of Binomial Heaps
Page 523
9.4.3. Insertion into a Binomial Heap
Page 524
9.4.4. Combining Two Binomial Heaps
Page 524
9.4.5. Deletion of Min Element
Page 525
9.4.6. Analysis
Page 529
9.5. Fibonacci Heaps
Page 531
9.5.1. Definition
Page 531
9.5.2. Deletion from an F-heap
Page 532
9.5.3. Decrease Key
Page 532
9.5.4. Cascading Cut
Page 533
9.5.5. Analysis
Page 534
9.5.6. Application to the Shortest Paths Problem
Page 536
9.6. References and Selected Readings
Page 539
9.7. Additional Exercise
Page 539
Chapter 10. Search Structures
Page 541
10.1. Optimal Binary Search Trees
Page 541
10.2. AVL Trees
Page 551
10.3. 2-3 Trees
Page 567
10.3.1. Definition and Properties
Page 567
10.3.2. Searching a 2-3 Tree
Page 569
10.3.3. Insertion into a 2-3 Tree
Page 569
10.3.4. Deletion from a 2-3 Tree
Page 573
10.4. 2-3-4 Trees
Page 580
10.4.1. Definition and Properties
Page 580
10.4.2. Top-Down Insertion
Page 582
10.4.3. Top-Down Deletion
Page 586
10.5. Red-Black Trees
Page 589
10.5.1. Definition and Properties
Page 589
10.5.2. Searching a Red-Black Tree
Page 592
10.5.3. Top-Down Insertion
Page 592
10.5.4. Bottom-Up Insertion
Page 594
10.5.5. Deletion from a Red-Black Tree
Page 598
10.5.6. Joining and Splitting Red-Black Trees
Page 598
10.6. B-Trees
Page 602
10.6.1. Definition of m-way Search Trees
Page 602
10.6.2. Searching an m-way Search Tree
Page 603
10.6.3. Definition and Properties Of A B-tree
Page 604
10.6.4. Insertion into a B-tree
Page 609
10.6.5. Deletion from a B-tree
Page 611
10.6.6. Variable Size Key Values
Page 614
10.7. Splay Trees
Page 618
10.8. Digital Search Trees
Page 624
10.8.1. Definition
Page 624
10.8.2. Binary Tries
Page 625
10.8.3. Patricia
Page 627
10.9. Tries
Page 630
10.9.1. Definition
Page 630
10.9.2. Searching a Trie
Page 633
10.9.3. Sampling Strategies
Page 635
10.9.4. Insertion into a Trie
Page 636
10.9.5. Deletion from a Trie
Page 637
10.9.6. Node Structure
Page 637
10.10. Differential Files
Page 639
10.10.1. The Concept
Page 639
10.10.2. Bloom Filters
Page 642
10.11. References and Selected Readings
Page 644
Index
Page 646

Edition Notes

Includes bibliographical references and index.

Published in
New York
Other Titles
Data structures C++

Classifications

Dewey Decimal Class
005.7/3
Library of Congress
QA76.73.C153 H667 1995, QA76.73.C153H667

The Physical Object

Pagination
xx, 653 p. :
Number of pages
653

Edition Identifiers

Open Library
OL1121277M
Internet Archive
fundamentalsofda0000horo_a4f1
ISBN 10
0716782928
LCCN
94048034
OCLC/WorldCat
31783181
LibraryThing
580207
Goodreads
71670

Work Identifiers

Work ID
OL2676164W

Source records

Library of Congress MARC record
Internet Archive item record
Better World Books record
Promise Item
ISBNdb
marc_columbia MARC record

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
July 13, 2024 Edited by MARC Bot import existing book
May 25, 2022 Edited by ImportBot import existing book
May 25, 2022 Edited by ImportBot import existing book
September 6, 2018 Edited by ImportBot import new book
December 10, 2009 Created by WorkBot add works page