14339cam a22004214a 45000030004000000050017000040080041000210200018000620400009000800820020000891000021001091000017001301000025001472450098001722500012002702600058002823000018003403000011003583360026003693370028003953380027004235051186900450520109312319650002213412650003413434650002613468650002613494650002613520650003913546700001913585700002713604856008313631906004513714942000713759942001113766999001713777952012313794OSt20260817055930.0070327s2008 njua 000 0 eng  a9780929306407 cAKCL00a005.133bHOR-F21 aHorowitz, Ellis.1 aSartaj Sahni1 aSusan Anderson-Freed10aFundamentals of Data Structures in C++ /cEllis Horowitz, Sartaj Sahni, Susan Anderson-Freed. a2nd ed. aHyerabad:bUniversity Press (India) Pvt. Ltd. c2008. aXXI, 694 p. : c23 cm. atextbtxt2rdacontent aunmediatedbn2rdamedia avolumebnc2rdacarrier aCHAPTER 1 BASIC CONCEPTS 1.1 Overview: System Life Cycle 1.2 Object-Oriented Design 1.2.1 Algorithmic Decomposition versus 00 Decomposition 1.2.2 Fundamental Definitions and Concepts of 00 Programming 1.2.3 Evolution of Programming Languages and History of C++ 1.3 Data Abstraction and Encapsulation 1.4 Basics of C++ 1.4.1 Program Organization in C++ 1.4.2 Scope in C++ 1.4.3 C++ Statements and Operators 1.4.4 Data Declarations in C++ 1.4.5 Comments in C++ 1.4.6 Input/Output in C++ 1.4.7 Functions in C++ 1.4.8 Parameter Passing in C++ 1.4..9 Function Name Overloading in C++ 1.4.10 Inline Functions 1.4.11Dynamic Memory Allocation in C++ 1.4.12 Exceptions 1.5 Algorithm Speci fication 1.5.1 Introduction 1.5.2 Recursive Algorithms 1.6 The Standard Template Library 1.7 Performance Analysis And Measurement 1.7.1 Performance Analysis 1.7.2 Performance Measurement 1.7.3 Generating Test Data 1.8 References And Selected Readings CHAPTER 2 ARRAYS 2.1 Abstract Data Types and the C++ Class 2.1.1 An Introduction to the C++ Class 2.1.2 Data Abstraction and Encapsulation in C++ 2.1.3 Declaring Class Objects and Invoking Member Functions 2.1.4 Special Class Operations 2.1.5 Miscellaneous Topics 2.1.6 ADTs and C++ Classes 2.2 The Array as an Abstract Data Type 2.3 The Polynomial Abstract Data Type 2.3.1 Polynomial Representation 2.3.2 Polynomial Addition 2.4 Sparse Matrices 2.4.1 Introduction 2.4.2 Sparse Matrix Representation 2.4.3 Transposing a Matrix 2.4.4 Matrix Multiplication 2.5 Representation of Arrays 2.6 The String Abstract Data Type 2.6.1 String Pattern Matching: A Simple Algorithm 2.6.2 String Pattern Matching: The KMP Algorithm 2.7 References and Selected Readings 2.8 Additional Exercises CHAPTER 3 STACKS AND QUEUES 3.1 Templates in C++ 3.1.1 Template Functions 3.1.2 Using Templates to Represent Container Classes 3.2 The Stack Abstract Data Type 3.3 The Queue Abstract Data Type 3.4 Subtyping and Inheritance in C++ 3.5 A Mazing Problem 3.6 Evaluation of Expressions 3.6.1 Expressions 3.6.2 Postfix Notation 3.6.3 Infix to Postfix 3.7 Additional Exercises CHAPTER 4 LINKED LISTS 4.1 Singly Linked Lists and Chains 4.2 Representing Chains in C++ 4.2.1 Defining a Node in C++ 4.2.2 Designing a Chain Class in C++ 4.2.3 Pointer Manipulation in C++ 4.2.4 Chain Manipulation Operations 4.3 The Template Class Chain 4.3.1 Implementing Chains with Templates 4.3.2 Chain Iterators 4.3.3 Chain Operations 4.3.4 Reusing a Class 4.4 Circular Lists 4.5 Available Space Lists 4.6 Linked Stacks and Queues 4.7 Polynomials 4.7.1 Polynomial Representation 4.7.2 Adding Polynomials 4.7.3 Circular List Representation of Polynomials 4.8 Equivalence Classes 4.9 Sparse Matrices 4.9.1 Sparse Matrix Representation 4.9.2 Sparse Matrix Input 4.9.3 Deleting a Sparse Matrix 4.10 Doubly Linked Lists 4.11 Generalized Lists 4.11.1 Representation of Generalized Lists 4.11.2 Recursive Algorithms for Lists 4.11.3 Reference Counts, Shared and Recursive Lists CHAPTER 5 TREES 5.1 Introduction 5.1.1 Terminology 5.1.2 Representation of Trees 5.2 Binary Trees 5.2.1 The Abstract Data Type 5.2.2 Properties of Binary Trees 5.2.3 Binary Tree Representations 5.3 Binary Tree Traversal and Tree Iterators 5.3.1 Introduction 5.3.2 Inorder Traversal 5.3.3 Preorder Traversal 5.3.4 Postorder Traversal 5.3.5 Iterative Inorder Traversal 5.3.6 Level-Order Traversal 5.3.7 Traversal Without a Stack 5.4 Additional Binary Tree Operations 5.4.1Copying Binary Trees 5.4.2 Testing Equality 5.4.3 The Satisfiability Problem 5.5 Threaded Binary Trees 5.5.1 Threads 5.5.2 Inorder Traversal of a Threaded Binary Tree 5.5.3 Inserting a Node into a Threaded Binary Tree 5.6 Heaps 5.6.1 Priority Queues 5.6.2 Definition of a Max Heap 5.6.3 Insertion into a Max Heap 5.6.4 Deletion from a Max Heap 5.7 Binary Search Trees 5.7.1 Definition 5.7.2 Searching a Binary Search Tree 5.7.3 Insertion into a Binary Search Tree 5.7.4 Deletion from a Binary Search Tree 5.7.5 Joining and Splitting Binary Search Trees 5.7.6 Height of a Binary Search Tree 5.8 Selection Trees 5.8.1 Introduction 5.8.2 Winner Trees 5.8.3 Loser Trees 5.9 Forests 5.9.1 Transforming a Forest into a Binary Tree 5.9.2 Forest Traversals 5.10 Representation of Disjoint Sets 5.10.1 Introduction 5.10.2 Union and Find Operations 5.10.3 Application to Equivalence Classes 5.11 Counting Binary Trees 5.11.1 Distinct Binary Trees 5.11.2 Stack Permutations 5.11.3 Matrix Multiplication 5.1l.4 Number of Distinct Binary Trees 5.12 References and Selected Readings CHAPTER 6 GRAPHS 6.1 The Graph Abstract Data Type 6.1.1 Introduction 6.1.2 Definitions 6.1.3 Graph Representations 6.2 Elementary Graph Operations 6.2.1 Depth First Search 6.2.2 Breadth First Search 6.2.3 Connected Components 6.2.4 Spanning Trees 6.2.5 Biconnected Components 6.3 Minimum Cost Spanning Trees 6.3.1 Kruska1 s Algorithm 6.3.2 Prim s Algorithm 6.3.3 SoUin s Algorithm 6.4 Shortest Paths and Transitive Closure 6.4.1 Single Source/All Destination: Nonnegative Edge Costs 6.4.2 Single Source/All Destination: General Weights 6.4.3 All-Pairs Shortest Paths 6.4.4 Transitive Closure 6.5 Activity Networks 6.5.1 Activity on Vertex (AOV) Networks 6.5.2 Activity on Edge (AOE) Networks 6.6 References and Selected Readings 6.7 Additional Exercises CHAPTER 7 SORTING 7.1 Motivation 7.2 Insertion Sort 7.3 Quick Sort 7.4 How Fast Can We Sort? 7.5 Merge Sort 7.5.1 Merging 7.5.2 Iterative Merge Sort 7.5.3 Recursive Merge Sort 7.6 Heap Sort 7.7 Sorti ng on Several Keys 7.8 List and Table Sorts 7.9 Summary oflnternal Sorting 7.10 External Sorting 7.10.1 Introduction 7.10.2 k-way Merging 7.10.3 Butter Handling for Parallel Operation 7.10.4 Run Generation 7.10.5 Optimal Merging of Runs 7. 11 References and Selected Readings CHAPTER 8 HASHING 8.1 Introduction 8.2 Static Hashing 8.2.1 Hash Tables 8.2.2 Hash Functions 8.2.3 Secure Hash Functions 8.2.4 Overflow Handling 8.2.5 Theoretical Evaluation of Overflow Techniques 8.3 Dynamic Hashing 8.3.1 Motivation for Dynamic Hashing 8.3.2 Dynamic Hashing using Directories 8.3.3 Directoryless Dynamic Hashing 8.4 Bloom Filters 8.4.1 An Application -- Differential Files 8.4.2 Bloom Filter Design 8.5 References and selected Readings CHAPTER 9 PRIORITY QUEUES 9.1 Single- and Double-Ended Priority Queues 9.2 Leftist Trees 9.2.1 Height-Biased Leftist Trees 9.2.2 Weight-Biased Leftist Trees 9.3 Binomial Heaps 9.3.1 Cost Amortization 9.3.2 Definition of Binomial Heaps 9.3.3 Insertion into a Binomial Heap 9.3.4 Melding Two Binomial Heaps 9.3.5 Deletion of Min Element 9.3.6 Analysis 9.4 Fibonacci Heaps 9.4.1 Definition 9.4.2 Deletion from an F-heap 9.4.3 Decrease Key 9.4.4 Cascading Cut 9.4.5 Analysis 9.4.6 Application to The Shortest Paths Problem 9.5 Pairing Heaps 9.5.1 Definition 9.5.2 Meld and Insert 9.5.3 Decrease Key 9.5.4 Delete Min 9.5.5 Arbitrary Delete 9.5.6 Implementation Considerations 9.5.7 Complexity 9.6 Symmetric Min-Max Heaps 9.6.1 Definition and Properties 9.6.2 SMMH Representation 9.6.3 Inserting into an SMMH 9.6.4 Deleting from an SMMH 9.7 Interval Heaps 9.7.1 Definition and Properties 9.7.2 Inserting into an Interval Heap 9.7.3 Deleting the Min Element 9.7.4 Initializing an Interval Heap 9.7.5 Complexity of Interval Heap Operations 9.7.6 The Complemenary Range Search Problem 9.8 References and Selected Readings CHAPTER 10 EFFICIENT BINARY SEARCH TREES 10.1 Optimal Binary Search Trees 10.2 AVL Trees 10.3 Red-Black Trees 10.3.1 Definition 10.3.2 Representastion of a Red-Black Tree 10.3.3 Searching a Red-Black Tree 10.3.4 Inserting into a Red-Black Tree 10.3.5 Deletion from a Red-Black Tree 10.3.6 Joining Red-Black Trees 10.3.7 Splitting a Red-Black Tree 10.4 Splay Trees 10.4.1 Bottom-Up Splay Trees 10.4.2 Top-Down Splay Trees 10.5 References and Selected Readings CHAPTER 11 MULTIWAY SEARCH TREES 11.1 m-way Search Trees 11.1.1 Definition and Properties 11.1.2 Searching an m-way Search Tree 11.2 B- Trees 11.2.1 Definition and Properties 11.2.2 Number of Elements in a B- Tree 11.2.3 Insertion into a B-tree 11.2.4 Deletion from a B-tree 11.3 B+-Trees 11.3.1 Definition 11.3.2 Searching a B+-Tree 11.3.3 Insertion into a B+-Tree 11.3.4 Deletion from a B+-Tree 11.4 References and Selected Readings CHAPTER 12 DIGITAL SEARCH STRUCTURES 12.1 Digital Search Trees 12.1.1 Defintiion 12.1.2 Search, Insert and Delete 12.2 Binary Tries and Patricia 12.2.1 Binary Tries 12.2.2 Compressed Binary Tries 12.2.3 Patricia 12.3 Multiway Tries 12.3.1 Definition 12.3.2 Searching a Trie 12.3.3 Sampling Strategies 12.3.4 Insertion into a Trie 12.3.5 Deletion from a Trie 12.3.6 Keys with Different Length 12.3.7 Height of a Trie 12.3.8 Space Required and Alternative Node Structures 12.3.9 Prefix Search and Applications 12.3.10 Compressed Tries 12.3.11 Compressed Tries with Skip Fields 12.3.12 Compressed Tries with Labeled Edges 12.3.13 Space Required by a Compressed Trie 12.4 Suffix. Trees 12.4.1 Have You Seen this String? 12.4.2 The Suffix. Tree Data Structure 12.4.3 Let's Find That Substring (Searching a Suffix Tree) 12.4.4 Other Nifty Things You Can Do with a Suffix Tree 12.5 Tries and Internet Packet Forwarding 12.5.1 IP Routing 12.5.2 I-Bit Tries 12.5.3 Fixed-Stride Tries 12.5.4 Variable-Stride Tries 12.6 References and Selected Readings INDEX aThis new edition provides a comprehensive and technically rigorous introduction to data structures such as arrays, stacks, queues, linked lists, trees and graphs and techniques such as sorting hashing that form the basis of all software. In addition, this text presents advanced or specialized data structures such as priority queues, efficient binary search trees, multiway search trees and digital search structures. The book has been updated to include the latest features of the C++ language. Features such as exceptions and templates are now incorporated throughout the text along with limited exposure to STL. Treatment of queues, iterators and dynamic hashing has been improved. The book now discusses topics such as secure hashing algorithms, weightbiased leftist trees, pairing heaps, symmetric min–max heaps, interval heaps, top-down splay trees, B+ trees and suffix trees. Red–black trees have been made more accessible. The section on multiway tries has been significantly expanded and discusses several trie variations and their application to Internet packet forwarding. 0aComputer Science  0aC (Computer program language) 0aComputer Programming  0aSoftware Development  0aProgramming Languages 0aData structures (Computer science)1 aSahni, Sartaj.1 aAnderson-Freed, Susan.413Table of contents onlyuhttp://www.loc.gov/catdir/toc/ecip0714/2007012974.html a7bcbccorignewd1eecipf20gy-gencatlg cBK 2ddcn0 c45037d45037 00102ddc4070aAKCLbAKCLd2026-08-17g975.00l0o005.133 HOR=F2p69325r2026-08-17 06:00:12v975.00w2026-08-17yBK