Table of contents for Data structures using C++ / Varsha H. Patil.


Bibliographic record and links to related information available from the Library of Congress catalog


Information from electronic data provided by the publisher. May be incomplete or contain other coding.


Counter

1 Fundamental Concepts 1
1.1 Introduction to Programming 1
1.2 Object-oriented Programming 3
1.3 Introduction to Data Structures 3
1.3.1 Data 4
1.3.2 Data type 4
1.3.3 Data object 5
1.3.4 Data structure 5
1.3.5 Abstract data type 6
1.4 Types of Data Structures 9
1.4.1 Primitive and non-primitive data structures 9
1.4.2 Linear and non-linear data structures 9
1.4.3 Static and dynamic data structures 10
1.4.4 Persistent and ephemeral data structures 10
1.4.5 Sequential access and direct access data structures 11
1.5 Introduction to Algorithms 11
1.5.1 Characteristics of algorithms 12
1.5.2 Algorithmics 13
1.5.3 Algorithm design tools: Pseudocode and fl owchart 13
1.6 Pseudocode 14
1.6.1 Pseudocode notations 14
1.6.2 Algorithm header 14
1.6.3 Purpose 15
1.6.4 Condition and return statements 15
1.6.5 Statement numbers 16
1.6.6 Variables 16
1.6.7 Statement constructs 17
1.6.8 Subalgorithms 18
1.7 Relationship among data, data structures, and algorithms 20
1.8 Implementation of data structures 21
1.9 Flowcharts 22
1.10 Analysis of Algorithms 22
1.10.1 Complexity of algorithms 22
1.10.2 Space complexity 23
1.10.3 Time complexity 24
1.10.4 Computing time complexity of an algorithm 24
1.10.5 Big-O notation 25
1.11 From Problem to Program 26
1.12 Software Engineering 27
1.12.1 Analysis phase 27
1.12.2 Design phase 28
1.12.3 Implementation phase 28
1.12.4 Testing phase 29
1.12.5 Verifi cation 29
2 Linear Data Structure Using Arrays 34
2.1 Sequential Organization 34
2.2 Linear Data Structure Using Sequential Organization: Arrays 35
2.3 Array as an Abstract Data Type 37
2.4 Memory Representation and Address Calculation 39
2.5 The Class Array 41
2.5.1 Inserting an element into an array 43
2.5.2 Deleting an element 45
2.6 Arrays Using Template 47
2.7 Multidimensional Arrays 48
2.7.1 Two-dimensional arrays 48
2.7.2 n-dimensional arrays 53
2.8 Concept of Ordered List 58
2.9 Single Variable Polynomial 59
2.9.1 Representation using arrays 59
2.9.2 Polynomial as array of structure 61
2.9.3 Polynomial evaluation 62
2.9.4 Polynomial addition 63
2.9.5 Polynomial multiplication 67
2.10 Array for Frequency Count 70
2.11 Sparse Matrix 71
2.11.1 Sparse matrix representation 73
2.11.2 Sparse matrix addition 74
2.11.3 Transpose of sparse matrix 78
2.12 String Manipulation Using Array 85
2.13 Pros and Cons of Arrays 90
2.13.1 Characteristics 90
2.13.2 Advantages 90
2.13.3 Disadvantages 91
2.13.4 Applications of arrays 91
3 Stacks 96
3.1 Concept of Stacks and Queues 96
3.2 Stacks 97
3.2.1 Primitive operations 98
3.3 Stack Abstract Data Type 101
3.4 Representation of Stacks Using Sequential Organization (Arrays) 102
3.4.1 Create 104
3.4.2 Empty 104
3.4.3 GetTop 104
3.4.4 Push 105
3.4.5 Pop 105
3.5 Stacks Using Template 107
3.6 Multiple Stacks 109
3.7 Applications of Stack 112
3.8 Expression Evaluation and Conversion 112
3.8.1 Polish notation and expression conversion 114
3.8.2 Need for prefi x and postfi x expressions 115
3.8.3 Postfi x expression evaluation 115
3.9 Processing of Function Calls 139
3.10 Reversing a String with a Stack 141
3.11 Checking Correctness of Well-formed Parentheses 142
3.12 Recursion 143
3.13 Parsing Computer Programs 144
3.14 Backtracking Algorithms 144
3.15 Converting Decimal Numbers to Binary 144
4 Recursion 151
4.1 Introduction 151
4.2 Recurrence 154
4.3 Use of Stack in Recursion 155
4.4 Variants of Recursion 156
4.4.1 Direct recursion 157
4.4.2 Indirect recursion 157
4.4.3 Tail recursion 158
4.4.4 Linear recursion 159
4.4.5 Tree recursion 159
4.5 Execution of Recursive Calls 160
4.6 Recursive Functions 161
4.6.1 Writing recursive code 163
4.6.2 Tower of hanoi: An example of recursion 163
4.6.3 Checking for correctness 165
4.6.4 Things to remember 166
4.7 Iteration Versus Recursion 166
4.7.1 Demerits of recursive algorithms 166
4.7.2 Demerits of iterative methods 167
4.8 Simulating Recursion Using Stack (Eliminating Recursion) 167
4.9 Applications of Recursion 168
5 Queues 174
5.1 Concept of Queues 174
5.2 Queue as Abstract Data Type 175
5.3 Realization of Queues Using Arrays 176
5.4 Circular Queue 182
5.4.1 Advantages of using circular queues 186
5.5 Multi-queues 186
5.6 Deque 187
5.7 Priority Queue 188
5.7.1 Array implementation of priority queue 191
5.8 Applications of Queues 191
5.8.1 Josephus problem 192
5.8.2 Job scheduling 193
5.8.3 Simulation 194
5.9 Queues Using Templates 195
6 Linked Lists 202
6.1 Introduction 202
6.2 Linked List 203
6.2.1 Comparison of sequential and linked organizations 206
6.2.2 Linked list terminology 207
6.2.3 Primitive operations 208
6.3 Realization of Linked Lists 208
6.3.1 Realization of linked list using arrays 209
6.3.2 Linked list using dynamic memory management 210
6.4 Dynamic Memory Management 211
6.4.1 Dynamic memory management in C++ with new and
delete operators 212
6.5 Linked List Abstract Data Type 214
6.5.1 Data structure of node 216
6.5.2 Insertion of a node 219
6.5.3 Linked list traversal 225
6.5.4 Deletion of a node 228
6.6 Linked List Variants 231
6.6.1 Head pointer and header node 231
6.6.2 Types of linked list 232
6.6.3 Linear and circular linked lists 233
6.7 Doubly Linked List 234
6.7.1 Creation of doubly linked list 235
6.7.2 Deletion of a node from a doubly linked list 238
6.7.3 Insertion of a node in a doubly linked list 241
6.7.4 Traversal of DLL 243
6.8 Circular Linked List 244
6.8.1 Singly circular linked list 245
6.8.2 Circular linked list with header node 246
6.8.3 Doubly circular linked list 247
6.9 Polynomial Manipulations 248
6.9.1 Polynomial evaluation 250
6.9.2 Polynomial addition 251
6.9.3 Multiplication of two polynomials 254
6.10 Representation of Sparse Matrix Using Linked List 257
6.11 Linked Stack 259
6.11.1 Class for linked stack 259
6.11.2 Operations on linked stack 261
6.12 Linked Queue 263
6.12.1 Erasing a linked queue 267
6.13 Generalized Linked List 267
6.13.1 Defi nition 268
6.13.2 Applications 269
6.13.3 Representation of polynomials using generalized linked list 272
6.13.4 Representation of sets using generalized linked list 277
6.14 More on Linked Lists 279
6.14.1 Copying a linked list 279
16.4.2 Computing the length of a linked list 280
6.14.3 Reversing singly linked list without temporary storage 281
6.14.4 Concatenating two linked lists 282
6.14.5 Erasing the linked list 282
6.15 Application of Linked List-Garbage Collection 283
7 Trees 289
7.1 Introduction 289
7.1.1 Basic terminology 290
7.1.2 General trees 295
7.1.3 Representation of a general tree 298
7.2 Types of Trees 299
7.3 Binary Tree 302
7.3.1 Properties of a binary tree 303
7.4 Binary Tree Abstract Data Type 306
7.5 Realization of a Binary Tree 308
7.5.1 Array implementation of binary trees 308
7.5.2 Linked implementation of binary trees 311
7.6 Insertion of a Node in Binary Tree 315
7.7 Binary Tree Traversal 316
7.7.1 Preorder traversal 317
7.7.2 Inorder traversal 318
7.7.3 Postorder traversal 319
7.7.4 Non-recursive implementation of traversals 320
7.7.5 Formation of binary tree from its traversals 326
7.7.6 Breadth- and depth-fi rst traversals 330
7.8 Other Tree Operations 333
7.8.1 Counting nodes 333
7.8.2 Counting leaf nodes 333
7.8.3 Computing height of binary tree 333
7.8.4 Getting mirror, replica, or tree interchange of binary tree 334
7.8.5 Copying binary tree 334
7.8.6 Equality test 334
7.9 Conversion of General Tree to Binary Tree 335
7.10 Binary Search Tree 339
7.10.1 Inserting a node 341
7.10.2 Searching for a key 346
7.10.3 Deleting a node 348
7.10.4 Binary tree and binary search tree 354
7.11 Threaded Binary Tree 355
7.11.1 Threading a binary tree 358
7.11.2 Right-threaded binary tree 364
7.11.3 Inorder traversal 364
7.11.4 Preorder traversal 366
7.11.5 Insert to right of a node 366
7.11.6 Deleting a node 368
7.11.7 Pros and cons 368
7.12 Applications of Binary Trees 369
7.12.1 Expression tree 369
7.12.2 Decision tree 373
7.12.3 Huffman's coding 375
7.12.4 Game trees 378
8 Graphs 388
8.1 Introduction 388
8.2 Graph Abstract Data Type 389
8.3 Representation of Graphs 391
8.3.1 Adjacency matrix 391
8.3.2 Adjacency list 394
8.3.3 Adjacency multilist 399
8.3.4 Inverse adjacency list 400
8.3.5 Comparison of sequential and linked representations 401
8.4 Graph Traversal 401
8.4.1 Depth-fi rst search 401
8.4.2 Breadth-fi rst search 408
8.5 Spanning Tree 412
8.5.1 Connected components 413
8.5.2 Prim's algorithm 413
8.5.3 Kruskal's algorithm 418
8.5.4 Biconnected components 423
8.5.5 Disjoint set operations 424
8.6 Shortest Path Algorithm 424
9 Searching and Sorting 438
9.1 Searching 438
9.2 Search Techniques 439
9.2.1 Sequential search 439
9.2.2 Binary search 444
9.2.3 Fibonacci search 447
9.2.4 Indexed sequential search 450
9.2.5 Hashed search 454
9.3 Sorting 455
9.3.1 Types of sorting 455
9.3.2 General sort concepts 457
9.3.3 Bubble sort 458
9.3.4 Insertion sort 462
9.3.5 Selection sort 466
9.3.6 Quick sort 469
9.3.7 Heap sort 474
9.3.8 Shell sort 478
9.3.9 Bucket sort 479
9.3.10 Radix sort 481
9.3.11 File sort 483
9.3.12 Merge sort 484
9.4 Multiway Merge and Polyphase Merge 487
9.4.1 Comparison of ordinary merge sort and polyphase sort 487
9.5 Comparison of All Sorting Methods 489
10 Search Trees 498
10.1 Symbol Table 498
10.1.1 Representation of symbol table 499
10.2 Optimal Binary Search Tree 500
10.3 AVL Tree (Height-balanced Tree) 519
10.3.1 Implementation of AVL technique 528
10.3.2 Insertions and deletions in AVL tree 533
11 Hashing 547
11.1 Introduction 547
11.2 Key Terms and Issues 549
11.3 Hash Functions 551
11.3.1 Good hash function 552
11.3.2 Division method 552
11.3.3 Multiplication method 552
11.3.4 Extraction method 553
11.3.5 Mid-square hashing 554
11.3.6 Folding technique 554
11.3.7 Rotation 555
11.3.8 Universal hashing 555
11.4 Collision Resolution Strategies 555
11.4.1 Open addressing 556
11.4.2 Chaining 566
11.5 Hash Table Overfl ow 569
11.5.1 Open addressing for overfl ow handling 570
11.5.2 Overfl ow handling by chaining 570
11.6 Extendible Hashing 571
11.7 Dictionary 573
11.8 Skip List 573
11.9 Comparison of Hashing and Skip Lists 574
12 Heaps 578
12.1 Basic Concepts 578
12.1.1 Min-heap and max-heap 579
12.2 Implementation of Heap 581
12.3 Heap as Abstract Data Type 582
12.3.1 Operations on heaps 583
DETAILED CONTENTS ix
DSUC Detailed Contents V2 November 18, 2011 5:59 PM Page ix
12.4 Heap Applications 594
12.5 Heap Sort 595
12.6 Binomial Trees and Heaps 601
12.6.1 Binomial trees 601
12.6.2 Binomial heap 602
12.6.3 Representation of binomial heap 603
12.6.4 Operations on binomial heaps 604
12.7 Fibonacci Heap 604
12.7.1 Representation of Fibonacci heap 604
12.7.2 Operations on Fibonacci heaps 606
13 Indexing and Multiway Trees 612
13.1 Introduction 612
13.2 Indexing 613
13.2.1 Indexing techniques 614
13.3 Types of Search Trees 616
13.3.1 Multiway search tree 616
13.3.2 B-tree 617
13.3.3 B+ tree 647
13.3.4 Trie tree 651
13.3.5 Splay tree 653
13.3.6 Red-black tree 654
13.3.7 K-dimensional tree 656
13.3.8 AA Tree 657
14 Files 662
14.1 Introduction 662
14.2 External Storage Devices 663
14.2.1 Magnetic tape 664
14.2.2 Magnetic drum 664
14.2.3 Magnetic disk 664
14.3 File Organization 665
14.3.1 Schemes of fi le organization 665
14.3.2 Factors affecting fi le organization 666
14.3.3 Factors involved in selecting fi le organization 666
14.4 Files Using C++ 667
14.4.1 File I/O classes 667
14.4.2 Primitive functions 667
14.4.3 Binary and text fi les 672
14.5 Sequential File Organization 675
14.5.1 Primitive operations 676
14.5.2 Advantages 679
14.5.3 Drawbacks 679
14.6 Direct Access File Organization 679
14.6.1 Primitive operations 680
14.7 Indexed Sequential File Organization 686
14.7.1 Types of indices 686
14.7.2 Structure of indexed sequential fi le 687
14.7.3 Characteristics of indexed sequential fi le 688
14.8 Linked Organization 693
14.8.1 Multilist fi les 693
14.8.2 Coral rings 695
14.8.3 Inverted fi les 695
14.8.4 Cellular partitions 696
15 Standard Template Library 703
15.1 Abstract Data Type 703
15.1.1 Abstract data type and data structures 704
15.1.2 Creating abstract data types 704
15.1.3 Stack abstract data type 705
15.2 Survey of Programming Techniques 706
15.3 Standard Template Library 718
15.3.1 Containers 718
15.3.2 Algorithms 730
15.3.3 Iterators 733
15.3.4 Function Objects 737
16 Algorithm Analysis and Design 741
16.1 Introduction 741
16.1.1 Algorithm analysis 742
16.1.2 Asymptotic notations ( , q, O) 742
16.2 Divide-and-Conquer 743
16.2.1 Unique characteristics and use 743
16.2.2 General method 744
16.2.3 Binary search 745
16.2.4 Merge sort 747
16.2.5 Quick sort 750
16.2.6 Strassen's algorithm for matrix multiplication 756
16.3 Greedy Method 758
16.3.1 General greedy method 758
16.3.2 Knapsack problem 759
16.4 Dynamic Programming 762
16.4.1 The General method 762
16.4.2 Elements of dynamic programming 763
16.4.3 Principle of optimality 764
16.4.4 Limitations of dynamic programming 765
16.4.5 Knapsack problem 766
16.5 Pattern Matching 770
16.5.1 Brute-force approach 771
16.5.2 Boyer-Moore algorithm 774
16.5.3 Knuth-Morris-Pratt algorithm 775
16.6 Tries 781
16.6.1 Standard tries 782
16.6.2 Compressed tries 783
16.6.3 Suffi x tries 783
Appendix 788
Index 827



Library of Congress subject headings for this publication:
C++ (Computer program language)
Data structures (Computer science)
C++ (Computer program language) -- fast
Data structures (Computer science) -- fast