Data Structure Using C. Theory and Program

✍ Scribed by Ahmad Talha Siddiqui, Shoeb Ahad Siddiqui

• Publisher: CRC Press
• Year: 2024
• Tongue: English
• Leaves: 428
• Category: Library

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Brief Contents
Table of Contents
1 Introduction to Data Structures
1.1 Introduction
Definition
1.2 Classification of Data Structure
1.3 Operation on Data Structure
1.4 Overview of Various Data Structure
Array
Stack
Queue
Linked List
Tree
Graphs
1.5 Algorithm
1.6 Approach for Algorithm Design
Analysis of Algorithm
Types of Analysis
1.7 Time-Space Trade Off
Time Complexity
Space Complexity
1.8 Asymptotic Notation
Big-Oh Notation
Theta (θ) Notation
1.9 Dynamic Memory Allocation
Memory Allocation Process
Allocating block of Memory
2 Introduction to Array
2.1 Array
Definition
2.2 One-dimensional Array
2.3 Operations on Array
Traversing
Sorting
Searching
Insertion
Deletion
Merging
2.4 Representation of One-dimension in Memory
2.5 Two-dimensional Array
2.6 Implementation of 2-D (Dimension) Array in Memory
Row-Major Implementation
Address of element in Column-Major Implementation
2.7 Sparse Matrices
2.8 Array Representation of a Sparse Matrix
Linked List Representation of a Sparse Matrix
2.9 Advantages and Disadvantage of Arrays
Advantages of Arrays
Disadvantage of Arrays
3 Linked List
3.1 Introduction
3.2 Representation of Liked List in Memory
3.3 Single Linked List
3.4 Operations on a Single Linked List
a. Traversing the Linked List
b. Insert a Node Into the Linked List
c. Deleting a Node Into the Linked List
d. Merging of Two Linked List Into a Single Linked List
e. Searching for An Element in the Linked List
f. Sorting the Node in the Linked List
g. Reverse a Linked List
3.5 Circular Linked List
3.6 Operations in a Circular Linked List
a. Creation of Circular Linked List
b. (i) Insertion of a Node (At Beg)
b. (ii) Insertion of a Node (At End)
c. Deletion from Circular Linked List
3.7 Double Linked List
3.8 Operations in a Double Linked List
1. Traversing a Double Linked List
2. Insertion of a Node in a Double Linked List
3. Deletion of a Node
3.9 Circular Double Linked List
3.10 Operations on Circular Double Linked List
1. Insertion Operation
2. Delete Operation
3.11 Applications of Linked List
Applications of Doubly Linked List Can Be
3.12 Difference Between Linked Lists and Arrays
4 Stack
4.1 Introduction
Definition
4.2 Operations on Stack
Algorithm for PUSH Operation
Algorithm for POP Operation
4.3 Implementation of Stack
4.4 Applications of Stack
Conversion of An Infix Expression to Postfix Expression
Evaluation of Postfix Expression
Evaluation of Prefix Expression
4.5 Recursion
Principles of Recursion
Advantages and Disadvantages of Recursion
Comparison of Iteration and Recursion
Recursion Through Stack
4.6 Tower of Hanoi
5 Queues
5.1 Introduction
5.2 Representation of Queues
Operation on Queue Using Array
Algorithm for Queue Insertion
Algorithm for Queue Deletion
Types of Queue
5.3 Circular Queue
Algorithm Insert An Element in Circular Queue
Algorithm Delete An Element in Circular Queue
5.4 Double Ended Queue (DE-QUEUE)
Types of De-queue
Algorithm to Implement A Double Ended Queue
Algorithm (Insertion)
Algorithm (Deletion)
5.5 Priority Queue
Types of Priority Queues
Representation of the Priority Queue
One way List Representation
Add Operation in Priority Queue
Delete Operation in Priority Queue
5.6 Applications of Queues
5.7 Difference Between Stack and Queue
6 Trees
6.1 Introduction
6.2 Basic Terminology Related to Tree
6.3 Binary Trees
6.4 Terminology Related to Binary Tree
6.5 Properties of Binary Trees
6.6 Types of Binary Trees
Properties
6.7 Representation of a Binary Tree
Declare Structure of Tree Node
6.8 Traversing A Binary Tree
Algorithm for Tree Traversal
Non-Recursive Function for Traversal
6.9 Creation of Binary Tree with the Help of Traversal
Converting Algebraic Expression Into Binary Tree
6.10 Binary Search Tree
6.11 Operations in Binary Search Tree
6.12 Huffman’s Tree
Huffman Algorithm
6.13 Applications of Huffman’s Tree
Huffman Coding
6.14 Threaded Binary Tree
6.15 Traversing in a Threaded Binary Tree
Insertion in a Threaded Binary Tree
Deletion from a Threaded Binary Tree
6.16 AVL Tree
Balance Factor
6.17 Rotations of AVL Tree
6.18 Insertion in An AVL Tree
6.19 Deletion in An AVL Tree
6.20 Red Black Tree
6.21 Insertion a Node in a Red-black Tree
6.22 Deleting a Node from Red-black Tree
6.23 Applications of Red-black Tree
B-Tree and Its Variants
Why do We Need Another Tree Structure?
6.24 Multi-Way Search Trees
Searching a Multi-Way Tree
Insertion in an Multi-Way Search Tree
Deletion in Multi-Way Search Tree
6.25 B Tree
6.26 Insertion in B-Tree
6.27 Deletion in B-Tree
6.28 Application of B-Tree
6.29 B+ Trees
B+ Tree
B+ Tree Structure
Index Set
Sequence Set
Searching Key in a B+ Tree
Insertion Into a B+ Tree
Deletion From a B+ Tree
6.30 Application of Trees
7 Graphs
7.1 Introduction
Definition
Motivation
7.2 Basic Term Related to Graph
Graph Classifications
Kinds of Graphs: Weighted and Unweighted
Kinds of Graphs: Directed and Undirected
Undirected Graphs
Directed Graphs
Subgraph
Degree of a Node
Graphs: Terminology Involving Paths
Cyclic and Acyclic Graphs
Connected and Unconnected Graphs and ConnectedComponents
Trees and Minimum Spanning Trees
Data Structures for Representing Graphs
Adjacency List Representation
Adjacency Matrix Representation
7.3 Representation of Graph
7.4 Matrix Representation
(i) Adjacency Matrix
(ii) Incidence Matrix
(iii) Path Matrix
7.5 Linked List Representation
7.6 Traversing A Graph
1. Breadth First Search Using Queue
2. Depth First Search Using Stack
7.7 Spanning Tree
General Properties of Spanning Tree
Mathematical Properties of Spanning Tree
Application of Spanning Tree
7.8 Minimum Spanning Tree (MST)
Minimum Spanning-Tree Algorithm
7.9 Krukshal’s Algorithm
7.10 Prim’s Algorithm
7.11 Shortest Paths (Dijkstra’s Algorithm)
Dijkstra’s Algorithm
7.12 Warshall’s Algorithm
7.13 Modified Warshall’s Algorithm (Shortest Path)
7.14 Applications of Graph
8 Searching and Sorting
8.1 Introduction
8.2 Linear or Sequential Searching
Drawbacks
8.3 Binary Search
General Idea about Binary Search Algorithm
8.4 Interpolation Search
8.5 Sorting Techniques
Sorting Efficiency
Types of Sorting
8.6 Bubble Sort
Also Called as Sinking Sort
8.7 Insertion Sort
8.8 Selection Sort
Steps
How Selection Sorting Works
8.9 Merge Sort
8.10 Heap Sort
8.11 Quick Sort
8.12 Radix Sort
9 Hashing Techniques
9.1 Introduction
9.2 Hash Tables
9.3 Applications of Hash Tables
9.4 Hashing
9.5 Hash Functions
Characteristics of a Good Hash Function
9.6 Types of Hash Functions
Hash Function for Strings
9.7 Collision Resolution Techniques
9.8 Hashing with Open Addressing
Hashing with Rehashing
More Examples for Hashing Concept
9.9 Hashing with Chains
Searching a Hash Table with Chains
Inserting Into a Hash Table with Chains
Deleting from a Hash Table with Chains
Hashing with Linear Probe
Hashing with Quadratic Probe
Hashing with Double Hashing
9.10 Hashing with Rehashing
Deletion from a Hash Table
9.11 Indexed Search Techniques
Indexed Sequential Search Techniques (ISAM)