Varsha H Patil

Data Structures Using C++

• Broschiertes Buch

Produktbeschreibung

Data Structures Using C++ is designed to serve as a textbook for undergraduate engineering students of Computer Science and Information Technology as well as postgraduate students of Computer Applications. The book aims to provide a comprehensive coverage of the concepts of Data Structures using C++.

Produktdetails

• Verlag: Oxford University Press, USA
• Seitenzahl: 704
• Erscheinungstermin: 10. Mai 2012
• Englisch
• Abmessung: 243mm x 189mm x 33mm
• Gewicht: 1031g
• ISBN-13: 9780198066231
• ISBN-10: 0198066236
• Artikelnr.: 35275316

Autorenporträt

Varsha H. Patil is currently working as Head of Computer & I.T. Engineering department at Matoshri College of Engineering. She is also serving as the Vice Principal of the same institute. She has more than 18 years of teaching experience. She is a life member of many professional bodies such as ISTE, CSI, IE(I), and IETE. Having published many national and international journals she is also an author of five books in different areas of Computer Science & Engineering.

Inhaltsangabe

* 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