Data Structures and Algorithms Using C++

Data Structures and Algorithms Using C++ helps students to master data structures, their algorithms and the analysis of complexities of these algorithms. Each chapter includes an Abstract Data Type (ADT) and applications along with a detailed explanation of the topics. This book meets the requiremen...

Descripción completa

Detalles Bibliográficos
Autor principal:	Akepogu, Ananda Rao (-)
Otros Autores:	Palagiri, Radhika Raju
Formato:	Libro electrónico
Idioma:	Inglés
Publicado:	: Pearson India 1900.
Edición:	[First edition]
Materias:	Data structures (Computer science) Algorithms. C++ (Computer program language) Computer algorithms.
Ver en Biblioteca Universitat Ramon Llull:	https://discovery.url.edu/permalink/34CSUC_URL/1im36ta/alma991009820411306719

Tabla de Contenidos:

Cover
Data Structures and Algorithms Using C++
Copyright
Contents
About the Authors
Preface
Acknowledgements
Chapter 1 Introduction to C++
1.1 Introduction
1.2 Class Overview
1.2.1 Class
1.2.2 Objects
1.2.3 Class Members
1.3 I/O Streams
1.4 Access Control
1.5 Class Scope
1.6 Static Class Members
1.6.1 Static Member Variables
1.6.2 Static Member Function
1.6.3 Static Object
1.7 Functions
1.7.1 Parameter Passing Methods
1.7.2 Inline Functions
1.7.3 The friend Function
1.7.4 Function Overloading
1.8 The this Pointer
1.9 Dynamic Memory Allocation and Deallocation
1.9.1 The new Operator
1.9.2 The delete Operator
1.10 Exception Handling
Summary
Exercises
Chapter 2 Object Oriented Concepts
2.1 Goals and Principles
2.1.1 Object Oriented Design Goals
2.1.2 Object Oriented Design Principles
2.2 Constructors and Destructors
2.2.1 Constructors
2.2.2 Constructor Overloading
2.2.3 Destructors
2.3 Operator Overloading
2.3.1 Overloading the Plus (+) Operator
2.3.2 Overloading the Minus (-) Operator
2.3.3 Overloading Unary Operators
2.3.4 Postfix Form of Overloading the Unary Operator ++
2.3.5 Prefix Form of Overloading the Unary Operator
2.3.6 Postfix Form of Overloading the Unary Operator
2.4 Inheritance
2.4.1 Base Class Access Control
2.4.2 Types of Inheritance
2.4.3 Reasons for the Usage of Inheritance
2.4.4 Advantages
2.4.5 Disadvantages
2.4.6 Delegation
2.5 Polymorphism
2.5.1 Virtual Functions
2.5.2 Pure Virtual Functions
2.6 Abstract Classes
2.7 Generic Programming with Templates
2.7.1 Function Templates
2.7.2 Class Templates
2.8 Recursion
Summary
Exercises
Chapter 3 Algorithms
3.1 Introduction
3.2 Basic Notations
3.2.1 Pseudo Code.
3.3 Types of Algorithms
3.3.1 Brute Force Algorithms
3.3.2 Divide and Conquer Algorithms
3.3.3 Dynamic Programming Algorithms
3.3.4 Greedy Algorithms
3.3.5 Branch and Bound Algorithms
3.3.6 Recursive Algorithms
3.3.7 Back Tracking Algorithms
3.3.8 Randomized Algorithms
3.3.9 Hill Climbing Algorithms
3.4 Performance Analysis
3.4.1 Properties of the Best Algorithms
3.5 Space Complexity
3.5.1 Instruction Space
3.5.2 Text Section of a Program
3.5.3 Data Space
3.5.4 Stack Space
3.5.5 Calculating the Instruction Space
3.5.6 Calculating the Data Space
3.5.7 Size of Data Section
3.5.8 Size of Rodata Section
3.5.9 Size of bss Section
3.6 Apriori Analysis
3.7 Asymptotic Notation
3.7.1 Big oh Notation (O)
3.7.2 Omega Notation (Ω)
3.7.3 Theta Notation (θ)
3.7.4 Little oh Notation(o)
3.8 Time Complexity
3.8.1 Time Complexity Analysis of Bubble Sort
3.8.2 Time Complexity Analysis of Selection Sort
3.9 Worst Case, Average Case and Best Case Complexity
3.9.1 Worst Case
3.9.2 Average Case
3.9.3 Best Case
Summary
Exercises
Chapter 4 Arrays
4.1 Introduction
4.1.1 Array
4.2 Array Types
4.2.1 Single-dimensional Array
4.2.2 Multi-dimensional Array
4.2.3 N-dimensional Array
4.3 Array Representation
4.4 Initializing Arrays
4.5 Accessing Values of an Array
4.6 Array Operations
4.6.1 Traversing
4.6.2 Insertion
4.6.3 Deletion
4.6.4 Sorting
4.6.5 Searching
4.7 Arrays as Parameters
4.8 Character Sequences
4.9 Applications
Summary
Exercises
Chapter 5 Linked List
5.1 Introduction
5.2 Representation of Linked List in Memory
5.2.1 Static Representation
5.2.2 Dynamic Representation
5.3 Singly Linked List
5.3.1 Operations
5.4 Circular Linked List
5.4.1 Merging of Two Circular Lists.
5.5 Doubly Linked Lists
5.5.1 Representation of Doubly Linked List
5.5.2 Operations
5.6 Comparison of Various Linked Lists
5.6.1 Linked Lists Versus Arrays
5.7 Applications
5.7.1 Polynomial Manipulation
Summary
Exercises
Chapter 6 Stacks
6.1 Definition
6.2 Representation of a Stack
6.2.1 Array Representation of a Stack
6.2.2 Linked Representation of a Stack
6.3 Operations on Stack
6.3.1 Array Implementation of a Stack
6.3.2 Linked Implementation of a Stack
6.4 Applications of Stacks
6.4.1 Expression Evaluation
6.4.2 Postfix Evaluation
6.4.3 Recursion
6.4.4 Balancing of the Matching Parenthesis
Summary
Excercises
Chapter 7 Queues
7.1 Introduction
7.2 Representation of a Queue
7.2.1 Array Representation
7.2.2 Linked Representation
7.3 Operations on a Queue
7.3.1 Enqueue and Deque Using Arrays
7.3.2 Enqueue and Deque Using Linked List
7.4 Circular Queues
7.4.1 Operations on Circular Queue
7.5 Deque
7.5.1 Operations on a Deque
7.6 Applications of Queues
7.6.1 Simulation of Time-sharing System
7.6.2 Queue ADT
Summary
Exercises
Chapter 8 Dictionaries
8.1 Dictionaries
8.2 Linear List Representation
8.3 Skip Lists Representation
8.3.1 Operations
8.3.2 Searching
8.3.3 Insertion
8.3.4 Deletion
8.4 Hash Table
8.4.1 Hash Functions
8.5 Collisions
8.5.1 Separate Chaining
8.5.2 Open Addressing
8.6 Comparison of Chaining and Open Addressing
8.7 Applications
8.8 Dictionary ADT
Summary
Exercises
Chapter 9 Trees and Binary Trees
9.1 Introduction
9.2 Terminologies
9.3 Representation of a Tree
9.4 Binary Trees
9.5 Representation of Binary Trees
9.5.1 Array Representation of a Binary Tree
9.5.2 Linked Representation of Binary Trees
9.6 Binary Tree Operations.
9.7 Binary Tree Traversals
9.7.1 Inorder Traversal (LVR)
9.7.2 Preorder Traversal (VLR)
9.7.3 Postorder Traversal (LRV)
9.7.4 Level-order Traversal
9.8 Conversion of a Tree into a Binary Tree
9.9 Threaded Binary Trees
9.9.1 Linked Representation of a Threaded Binary Tree
9.10 Applications of Binary Trees
9.10.1 Traversal of an Expression Tree
9.10.2 Operations on Expression Trees
9.11 ADT of Binary Tree
Summary
Exercises
Chapter 10 Graphs
10.1 Introduction
10.2 Basic Terminology
10.3 Representation of Graphs
10.3.1 Sequential Representation of Graphs
10.3.2 Linked Representation of Graphs
10.4 Operations on Graphs
10.5 Graph Traversals
10.5.1 Breadth First Traversal
10.5.2 Depth First Traversal
10.6 Applications
10.7 Graph ADT
Summary
Exercises
Chapter 11 Priority Queues
11.1 Introduction
11.2 Priority Queue ADT
11.3 Priority Queue Implementation Using Heaps
11.3.1 Priority Queue Interface
11.3.2 Min Heap-Insertion
11.3.3 Min Heap-Deletion
11.3.4 Max Heap-Insertion
11.3.5 Max Heap-Deletion
11.4 Applications
11.4.1 Job Scheduling
11.5 External Sorting
11.5.1 Polyphase Merge
11.5.2 Multiway Merge
Summary
Exercises
Chapter 12 Binary Search Trees and AVL Trees
12.1 Binary Search Trees
12.2 Representation of a Binary Search Tree
12.3 Operations on Binary Search Trees
12.3.1 Searching
12.3.2 Insertion
12.3.3 Deletion
12.3.4 Disadvantages of Binary Search Tree
12.4 AVL Trees
12.5 Operation of AVL Search Trees
12.5.1 Searching
12.5.2 Insertion
12.5.3 Deletion
12.6 Applications
Summary
Exercises
Chapter 13 Multiway Trees and B Trees
13.1 Introduction
13.2 Representation of a Node Structure
13.3 Operations on m-Way Search Trees
13.3.1 Searching
13.3.2 Insertion.
13.3.3 Deletion
13.3.4 Drawbacks of m-Way Search Trees
13.4 B Trees
13.5 Operations on B Trees
13.5.1 Searching
13.5.2 Insertion
13.5.3 Deletion
13.6 Height of B Trees
13.7 Variations of B Tree
13.7.1 B* Tree
13.7.2 B+ Tree
13.8 Applications
13.8.1 Databases
Summary
Exercises
Chapter 14 Red-Black Trees and Splay Trees
14.1 Introduction
14.2 Representation of a Red-Black Tree
14.3 Operations
14.3.1 Searching
14.3.2 Insertion
14.3.3 Deletion
14.4 Splay Trees
14.4.1 Splay Rotations
14.4.2 Amortized Analysis
14.5 Applications
Summary
Exercises
Chapter 15 Pattern Matching and Tries
15.1 Introduction
15.2 Terminology
15.3 Pattern Matching Algorithms
15.3.1 Fixed Pattern Matching Algorithms
15.3.2 Regular Expression Pattern Matching
15.4 Fixed Pattern Matching Algorithms
15.4.1 Brute Force Pattern Matching Algorithm
15.4.2 Th e Boyer-Moore Algorithm
15.4.3 Knuth-Morris-Pratt Algorithm (KMP)
15.5 Applications of Pattern Matching Algorithms
15.6 Tries
15.6.1 Standard Tries
15.6.2 Compressed Tries
15.6.3 Suffix Tries
15.7 Applications of Tries
Summary
Exercises
Chapter 16 Sorting and Searching
16.1 Sorting
16.1.1 Bubble Sort
16.1.2 Insertion Sort
16.1.3 Selection Sort
16.1.4 Quick Sort
16.1.5 Merge Sort
16.1.6 Shell Sort
16.1.7 Radix Sort
16.1.8 Heap Sort
16.2 Searching
16.2.1 Linear Search or Sequential Search
16.2.2 Binary Search
16.2.3 Fibonacci Search
Summary
Exercises
Index.

Data Structures and Algorithms Using C++

Ejemplares similares