Fundamentals of Data Structures in C:/ Ellis Horowitz, Sartaj Sahni & Susan Anderson-Freed
Material type:
TextPublication details: Hyderabad: Universities Press, 2023.Edition: 2nd edDescription: xvii, 617p. : ill. ; Softbound, 17.5*23.5 cmISBN: - 978-81-7371-605-8
- 23 005.133 HOR
| Item type | Current library | Collection | Call number | Copy number | Status | Barcode | |
|---|---|---|---|---|---|---|---|
Books
|
Tetso College Library Computer Science | Non-fiction | 005.133 HOR (Browse shelf(Opens below)) | 1 | Available | 15128 | |
|
Books
|
Tetso College Library Computer Science | Non-fiction | 005.133 HOR (Browse shelf(Opens below)) | 2 | Available | 15129 | |
|
Books
|
Tetso College Library Computer Science | Non-fiction | 005.133 HOR (Browse shelf(Opens below)) | 3 | Available | 15130 |
CHAPTER 1 BASIC CONCEPTS.................................... 1
1.1 Overview: System Life Cycle........................... 1
1.2 Algorithm Specification............................... 4
1.2.1 Introduction................................... 4
1.2.2 Recursive Algorithms........................... 10
1.3 Data Abstraction...................................... 14
1.4 Performance Analysis.................................. 18
1.4.1 Space Complexity............................... 19
1.4.2 Time Complexity................................ 21
1.4.3 Asymptotic Notation............................ 30
1.4.4 Comparing Time Complexities.................... 37
1.5 Performance Measurement............................... 40
1.6 References and Selected Readings...................... 46
CHAPTER 2 ARRAYS AND STRUCTURES........................... 47
2.1 The Array as an Abstract Data Type.................... 47
2.2 The Polynomial Abstract Data Type..................... 51
2.3 The Sparse Matrix Abstract Data Type.................. 59
2.3.1 Introduction................................... 59
2.3.2 Transposing a Matrix........................... 61
2.3.3 Matrix Multiplication......................... 65
2.4 The Representation of Multidimensional Arrays......... 71
2.5 The String Abstract Data Type......................... 75
2.5.1 Introduction................................... 75
2.5.2 Pattern Matching............................... 80
2.6 Structures and Unions................................. 86
2.6.0 Structures.................................... 86
2.6.1 Unions........................................ 89
2.6.1 Internal Implementation of Structures 90
2.6.1 Self-Referential Structures................... 90
2.7 References and Selected Readings...................... 92
2.8 Additional Exercises.................................. 92
CHAPTER 3 STACKS AND QUEUES............................... 99
3.1 The Stack Abstract Data Type.......................... 99
3.2 The Queue Abstract Data Type.......................... 103
3.3 A Mazing Problem...................................... 110
3.4 Evaluation of Expressions............................. 116
3.4.1 Introduction................................... 116
3.4.2 Evaluatng Postfix Expressions.................. 117
3.4.3 Infix to Postfix............................... 120
3.5 Multiple Stacks and Queues............................ 127
3.6 Selected Readings and References...................... 130
3.7 Additional Exercises.................................. 131
CHAPTER 4 LINKED LISTS.................................... 134
4.1 Pointers.............................................. 134
4.1.1 Pointer Can Be Dangerous....................... 136
4.1.2 Using Dynamically Allocated Storage............ 137
4.2 Singly Linked Lists................................... 138
4.3 Dynamically Linked Stacks and Queues.................. 146
4.4 Polynomials........................................... 150
4.4.1 Representing Polynomials as Singly Linked Lists 150
4.4.2 Adding Polynomials............................. 151
4.4.3 Erasing Polynomials............................ 155
4.4.4 Polynomials as Circularly Linked Lists......... 156
4.4.5 Summary........................................ 161
4.5 Additional List Operations............................ 162
4.5.1 Operations for Singly Linked Lists............. 162
4.5.2 Operations for Doubly Linked Lists............. 164
4.6 Equivalence Relations................................. 165
4.7 Sparse Matrices....................................... 171
4.8 Doubly Linked Lists................................... 179
4.9 References and Selected Readings...................... 182
4.10 Additional Exercises.................................. 183
CHAPTER 5 TREES........................................... 186
5.1 Introduction.......................................... 186
5.1.1 Terminology.................................... 186
5.1.2 Representation of Trees........................ 189
5.2 Binary Trees.......................................... 191
5.2.1 The Abstract Data Type......................... 191
5.2.2 Properties of Binary Trees..................... 193
5.2.3 Binary Tree Representations.................... 196
5.3 Binary Tree Traversals................................ 200
5.4 Additional Binary Tree Operations..................... 206
5.5 Threaded Binary Trees................................. 212
5.6 Heaps................................................. 218
5.6.1 The Heap Abstract Data Type.................... 219
5.6.2 Priority Queues................................ 220
5.6.3 Insertion into a max heap...................... 222
5.6.4 Deletion from a max heap....................... 223
5.7 Binary Search Trees................................... 227
5.7.1 Introduction................................... 227
5.7.2 Searching a Binary Search Tree................. 228
5.7.3 Inserting an Element into a Binary Search Tree 229
5.7.4 Deleting an Element from a Binary Search Tree 230
5.7.5 Height of a Binary Search Tree................. 232
5.8 Forests............................................... 234
5.8.1 Transforming a Forest into a Binary Search Tree 234
5.8.2 Forest Traversals.............................. 235
5.9 Set Representation.................................... 236
5.9.1 Union and Find Operations...................... 237
5.9.2 Equivalence Relations.......................... 245
5.10 Counting Binary Trees................................. 245
5.11 References and Selected Readings...................... 252
5.12 Additional Exercises.................................. 252
CHAPTER 6 GRAPHS.......................................... 255
6.1 The Graph Abstract Data Type.......................... 255
6.1.1 Introduction................................... 255
6.1.2 Definitions.................................... 257
6.1.3 Graph Representations.......................... 262
6.2 Elementary Graph Operations........................... 270
6.2.1 Depth First Search............................. 270
6.2.2 Breadth First Search........................... 271
6.2.3 Connected Components........................... 273
6.2.4 Spanning Trees 274
6.2.4 Biconnected Components, Articulation Points 274
6.3 Minimum Cost Spanning Trees........................... 280
6.4 Shortest Paths and Transitive Closure................. 289
6.4.1 Single Source All Destination.................. 290
6.4.2 All Pairs Shortest Paths....................... 292
6.4.3 Transitive Closure............................. 296
6.5 Activity Networks..................................... 300
6.5.1 Activity on Vertex (AOV) Networks.............. 300
6.5.2 Activity on Edge (AOE) Networks................ 306
6.6 References and Selected Readings...................... 314
6.7 Additional Exercises.................................. 315
CHAPTER 7 SORTING......................................... 317
7.1 Searching and List Verification....................... 317
7.1.1 Introduction................................... 317
7.1.2 Sequential Search.............................. 336
7.1.3 Binary Search.................................. 336
7.1.4 List Verification.............................. 336
7.2 Definitions........................................... 408
7.3 Insertion Sort........................................ 408
7.4 Quick Sort............................................ 410
7.5 Optimal Sorting Time.................................. 414
7.6 Merge Sort............................................ 416
7.6.1 Introduction................................... 336
7.6.2 Iterative Merge Sort........................... 336
7.6.3 Recursive Merge Sort........................... 336
7.7 Heap Sort............................................. 424
7.8 Radix Sort............................................ 426
7.9 List and Table Sorts.................................. 432
7.10 External Sorts........................................ 416
7.10.1 Run Generation................................. 336
7.10.2 External Merge Sort............................ 336
7.11 Summary............................................... 446
7.12 References and Selected Readings...................... 446
7.13 Additional Exercises.................................. 446
CHAPTER 8 HASHING......................................... 493
8.1 Symbol Tables......................................... 493
8.2 Static Hashing........................................ 495
8.2.1 Hash Tables.................................... 495
8.2.2 Hashing Functions.............................. 497
8.2.3 Linear Open Addressing......................... 501
8.2.4 Chaining....................................... 508
8.2.5 Theoretical Evaluation of Overflow Techniques 508
8.3 Dynamic Hashing....................................... 509
8.3.1 Dynamic Hashing Using Directories.............. 509
8.3.2 Analysis of Directory Dynamic Hashing.......... 510
8.3.3 Directoryless Dynamic Hashing.................. 519
8.4 References and Selected Readings...................... 523
CHAPTER 9 HEAP STRUCTURES................................. 528
9.1 Min-Max Heaps......................................... 528
9.2 Deaps................................................. 534
9.3 Leftist Trees......................................... 541
9.4 Fibonacci Heaps....................................... 547
9.5 References and Selected Readings...................... 631
CHAPTER 10 SEARCH STRUCTURES.............................. 528
10.1 Optimal Binary Search Trees........................... 566
10.2 AVL Trees............................................. 572
10.3 2-3 Trees............................................. 591
10.4 2-3-4 Trees........................................... 599
10.5 Red-Black Trees....................................... 611
10.6 Splay Trees........................................... 618
10.7 Digital Search Trees.................................. 625
10.8 B-Trees............................................... 660
10.9 Tries................................................. 680
10.10 Differential Files.................................... 698
10.11 References and Selected Readings...................... 631
INDEX....................................................... 575
There are no comments on this title.