Fundamentals of data structures in Pascal

Horowitz E., Sartaj S. Fundamentals of data structures in pascal (ed. 4,1994,Computer Science Press )(ISBN 0716782634)(600dpi)(626p) ......Page 3
Copyright ......Page 4
Contents v ......Page 5
PREFACE xiii ......Page 12
1.1 Overview: System Life Cycle 1 ......Page 17
1.2.1 Introduction 4 ......Page 20
1.2.2 Recursive Algorithms 9 ......Page 25
1.3 Data Abstraction 14 ......Page 30
1.4 Performance Analysis And Measurement 17 ......Page 33
1.4.1 Performance Analysis 18 ......Page 34
1.4.2 Performance Measurement 40 ......Page 56
1.4.3 Generating Test Data 51 ......Page 67
1.5 References And Selected Readings 55 ......Page 71
2.1 The Array As An Abstract Data Type 57 ......Page 73
2.2 The Polynomial Abstract Data Type 58 ......Page 74
2.3 Sparse Matrices 67 ......Page 83
2.3.1 Transposing A Matrix 68 ......Page 84
2.3.2 Matrix Multiplication 73 ......Page 89
2.4 Representation Of Arrays 78 ......Page 94
2.5 The String Abstract Data Type 82 ......Page 98
2.7 Additional Exercises 89 ......Page 105
3.1 The Stack Abstract Data Type 97 ......Page 113
3.2 The Queue Abstract Data Type 102 ......Page 118
3.3 A Mazing Problem 108 ......Page 124
3.4.1 Expressions 114 ......Page 130
3.4.2 Postfix Notation 115 ......Page 131
3.4.3 Infix to Postfix 117 ......Page 133
3.5 Multiple Stacks And Queues 121 ......Page 137
3.7 Additional Exercises 125 ......Page 141
4.1 Singly Linked Lists 128 ......Page 144
4.2 Linked Stacks And Queues 138 ......Page 154
4.3.1 Polynomial Representation 141 ......Page 157
4.3.2 Adding Polynomials 142 ......Page 158
4.3.3 Erasing Polynomials 146 ......Page 162
4.3.4 Circularly List Representation Of Polynomials 147 ......Page 163
4.3.5 Summary 150 ......Page 166
4.4.1 Operations For Chains 152 ......Page 168
4.4.2 Operations For Circular Lists 153 ......Page 169
4.5 Equivalence Relations 155 ......Page 171
4.6.1 Sparse Matrix Representation 160 ......Page 178
4.6.2 Sparse Matrix Input 163 ......Page 179
4.6.3 Erasing A Sparse Matrix 165 ......Page 181
4.7 Doubly Linked Lists 168 ......Page 184
4.8 Dynamic Storage Management 172 ......Page 188
4.9.1 Representation Of Generalized Lists 188 ......Page 204
4.9.2 Recursive Algorithms For Lists 192 ......Page 208
4.9.3 Reference Counts, Shared And Recursive Lists 195 ......Page 211
4.10.2 Marking 203 ......Page 219
4.10.3 Storage Compaction 212 ......Page 228
4.11 References And Selected Readings 217 ......Page 233
5.1.1 Terminology 218 ......Page 234
5.1.2 Representation Of Trees 221 ......Page 237
5.2.1 The Abstract Data Type 224 ......Page 240
5.2.2 Properties Of Binary Trees 227 ......Page 243
5.2.3 Binary Tree Representations 229 ......Page 245
5.3.2 Inorder Traversal 233 ......Page 249
5.3.3 Preorder Traversal 234 ......Page 250
5.3.4 Postorder Traversal 235 ......Page 251
5.3.5 Iterative Inorder Traversal 236 ......Page 252
5.3.6 Level-Order Traversal 238 ......Page 254
5.3.7 Traversal Without A Stack 239 ......Page 255
5.4.1 Copying Binary Trees 241 ......Page 257
5.4.3 The Satisfiability Problem 242 ......Page 258
5.5.1 Threads 246 ......Page 262
5.5.2 Inorder Traversal Of A Threaded Binary Tree 248 ......Page 264
5.5.3 Inserting A Node Into A Threaded Binary Tree 249 ......Page 265
5.6.1 Definitions 252 ......Page 268
5.6.2 Priority Queues 253 ......Page 269
5.6.3 Insertion Into A Max Heap 255 ......Page 271
5.6.4 Deletion From A Max Heap 257 ......Page 273
7.1 Motivation 359 ......Page 375
5.7.1 Definition 259 ......Page 275
5.7.2 Searching A Binary Search Tree 260 ......Page 276
5.7.3 Inserting Into A Binary Search Tree 261 ......Page 277
5.7.4 Deletion From A Binary Search Tree 263 ......Page 279
5.7.5 Joining And Splitting Binary Search Trees 264 ......Page 280
5.7.6 Height Of A Binary Search Tree 267 ......Page 283
5.8.2 Winner Trees 268 ......Page 284
5.8.3 Looser Trees 270 ......Page 286
5.9 Forests 272 ......Page 288
5.9.2 Forest Traversals 273 ......Page 289
5.10.1 Introduction 275 ......Page 291
5.10.2 Union And Find Operations 276 ......Page 292
5.10.3 Application To Equivalence Classes 284 ......Page 300
5.11.1 Distinct Binary Trees 287 ......Page 303
5.11.2 Stack Permutations 288 ......Page 304
5.11.3 Matrix Multiplication 289 ......Page 305
5.11.4 Number Of Distinct B inary Trees 291 ......Page 307
5.12 References And Selected Readings 292 ......Page 308
6.1.1 Introduction 293 ......Page 309
6.1.2 Definitions 295 ......Page 311
6.1.3 Graph Representations 299 ......Page 315
6.2.1 Depth First Search 307 ......Page 323
6.2.2 Breadth First Search 308 ......Page 324
6.2.3 Connected Components 310 ......Page 326
6.2.4 Spanning Trees 311 ......Page 327
6.2.5 Biconnected Components 313 ......Page 329
6.3 Minimum Cost Spanning Trees 318 ......Page 334
6.3.1 Kruskal’s Algorithm 319 ......Page 335
6.3.2 Prim’s Algorithm 322 ......Page 338
6.3.3 Sollin’s Algorithm 323 ......Page 339
6.4 Shortest Paths And Transitive Closure 325 ......Page 341
6.4.1 Single Source/All Destination: Nonnegative Edge Costs 326 ......Page 342
6.4.2 Single Source/All Destination: General Weights 329 ......Page 345
6.4.3 All-Pairs Shortest Paths 333 ......Page 349
6.4.4 Transitive Closure 335 ......Page 351
6.5.1 Activity On Vertex (AOV) Networks 340 ......Page 356
6.5.2 Activity On Edge (AOE) Networks 345 ......Page 361
6.6 References And Selected Readings 355 ......Page 371
6.7 Additional Exercises 356 ......Page 372
7.2 Insertion Sort 363 ......Page 379
7.3 Quick Sort 366 ......Page 382
7.4 How Fast Can We Sort? 370 ......Page 386
7.5.1 Merging 372 ......Page 388
7.5.2 Iterative Merge Sort 377 ......Page 393
7.5.3 Recursive Merge Sort 379 ......Page 395
7.6 Heap Sort 384 ......Page 400
7.7 Sorting On Several Keys 386 ......Page 402
7.8 List And Table Sorts 392 ......Page 408
7.9 Summary Of Internal Sorting 401 ......Page 417
7.10.1 Introduction 405 ......Page 421
7.10.2 k-way Merging 409 ......Page 425
7.10.3 Buffer Handling For Parallel Operation 410 ......Page 426
7.10.4 Run Generation 417 ......Page 433
7.10.5 Optimal Merging Of Runs 419 ......Page 435
7.11 References And Selected Readings 424 ......Page 440
8.1 The Symbol Table Abstract Data Type 425 ......Page 441
8.2.1 Hash Tables 427 ......Page 443
8.2.2 Hashing Functions 429 ......Page 445
8.2.3 Overflow Handling 432 ......Page 448
8.2.4 Theoretical Evaluation Of Overflow Techniques 438 ......Page 454
8.3.1 Motivation For Dynamic Hashing 442 ......Page 458
8.3.2 Dynamic Hashing Using Directories 443 ......Page 459
8.3.3 Analysis Of Directory-Based Dynamic Hashing 449 ......Page 465
8.3.4 Directoryless Dynamic Hashing 452 ......Page 468
8.4 References And Selected Readings 456 ......Page 472
9.1.1 Definitions 458 ......Page 474
9.1.2 Insertion Into A Min-Max Heap 459 ......Page 475
9.1.3 Deletion Of The Min Element 462 ......Page 478
9.2.1 Definition 466 ......Page 482
9.2.2 Insertion Into A Deap 467 ......Page 483
9.2.3 Deletion Of The Min Element 470 ......Page 486
9.3 Leftist Trees 473 ......Page 489
9.4.1 Cost Amortization 480 ......Page 496
9.4.2 Definition Of Binomial Heaps 481 ......Page 497
9.4.5 Deletion Of Min Element 483 ......Page 499
9.4.6 Analysis 485 ......Page 501
9.5.1 Definition 488 ......Page 504
9.5.2 Deletion From An F-heap 489 ......Page 505
9.5.4 Cascading Cut 490 ......Page 506
9.5.5 Analysis 491 ......Page 507
9.5.6 Application To The Shortest Paths Problem 494 ......Page 510
9.6 References And Selected Readings 496 ......Page 512
10.1 Optimal Binary Search Trees 497 ......Page 513
10.2 AVL Trees 507 ......Page 523
10.3 2-3 Trees 523 ......Page 539
10.3.1 Definition And Properties 523 ......Page 53
10.3.2 Searching A 2-3 Tree 524 ......Page 540
10.3.3 Insertion Into A 2-3 Tree 525 ......Page 541
10.3.4 Deletion From A 2-3 Tree 528 ......Page 544
10.4.1 Definition And Properties 536 ......Page 552
10.4.2 Top-Down Insertion 538 ......Page 554
10.4.3 Top-Down Deletion 541 ......Page 557
10.5.1 Definition And Properties 545 ......Page 561
10.5.3 Top-Down Insertion 548 ......Page 564
10.5.4 Bottom-Up Insertion 550 ......Page 566
10.5.6 Joining And Splitting Red-Black Trees 554 ......Page 570
10.6.1 Definition Of m-way Search Trees 558 ......Page 574
10.6.2 Searching An m-way Search Tree 560 ......Page 576
10.6.3 Definition And Properties Of A B-tree 561 ......Page 577
10.6.4 Insertion Into A B-tree 563 ......Page 579
10.6.5 Deletion From A B-tree 567 ......Page 583
10.6.6 Variable Size Key Values 570 ......Page 586
10.7 Splay Trees 574 ......Page 590
10.8.1 \tDefinition 580 ......Page 596
10.8.2 Binary Tries 581 ......Page 597
10.8.3 Patricia 582 ......Page 598
10.9.1 Definition 587 ......Page 603
10.9.2 Searching A Trie 589 ......Page 605
10.9.3 Sampling Strategies 591 ......Page 607
10.9.4 Insertion Into A Trie 592 ......Page 608
10.9.5 Deletion From A Trie 593 ......Page 609
10.9.6 Node Structure 594 ......Page 610
10.10.1 The Concept 596 ......Page 612
10.10.2 Bloom Filters 598 ......Page 614
10.11 References And Selected Readings 600 ......Page 616
INDEX 603 ......Page 619
cover......Page 1