Vor Ort
Merkzettel Warenkorb
Produktbild: Data Structures Using C++

Data Structures Using C++

44,99 €

inkl. gesetzl. MwSt., Versandkostenfrei

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

10.05.2012

Verlag

Oxford University Press, USA

Seitenzahl

704

Maße (L/B/H)

24,3/18,9/3,3 cm

Gewicht

1031 g

Sprache

Englisch

ISBN

978-0-19-806623-1

Beschreibung

Produktdetails

Einband

Taschenbuch

Erscheinungsdatum

10.05.2012

Verlag

Oxford University Press, USA

Seitenzahl

704

Maße (L/B/H)

24,3/18,9/3,3 cm

Gewicht

1031 g

Sprache

Englisch

ISBN

978-0-19-806623-1

Herstelleradresse

Libri GmbH
Europaallee 1
36244 Bad Hersfeld
DE

Email: gpsr@libri.de

Noch keine Bewertungen vorhanden

Verfassen Sie die erste Bewertung zu diesem Artikel

Helfen Sie anderen Kundinnen und Kunden durch Ihre Meinung.

Kundinnen und Kunden meinen

Bewertungen (0)
  • Produktbild: Data Structures Using C++

    • 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