Librería Portfolio

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 all the topics related to data structures.

The book begins with a discussion on the fundamentals of data structures and algorithms, and moves on to the concepts of linear data structures, stacks, recursion, queues, and searching and sorting. All the elements of data structures, such as linked lists, trees, graphs, hashing, heaps, and indexing, are covered in separate chapters in detail. The chapter on files explains file management and organization using C++ and the chapter on the standard template library provides detailed coverage of entities such as containers and iterators. A chapter on algorithm analysis and design is provided towards the end that discusses the various algorithmic strategies required to solve a problem effectively and efficiently.

Written in a simple manner with strong pedagogy including numerous multiple choice and review questions, the book also provides programming problems at the end of every chapter.



Table of Contents

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