Data Structures using C: A Practical Approach for Beginners

Length: 346 pages
Edition: 1
Language: English
Publisher: Chapman and Hall/CRC
Publication Date: 2021-11-09
ISBN-10: 0367616319
ISBN-13: 9780367616311
Sales Rank: #0 (See Top 100 Books)

The data structure is a set of specially organized data elements and functions, which are defined to store, retrieve, remove and search for individual data elements. Data Structures using C: A Practical Approach for Beginners covers all issues related to the amount of storage needed, the amount of time required to process the data, data representation of the primary memory and operations carried out with such data. Data Structures using C: Practical Approach for Beginners book will help students learn data structure and algorithms in a focused way.

Resolves linear and nonlinear data structures in C language using the algorithm, diagrammatically and its time and space complexity analysis
Covers interview questions and MCQs on all topics of campus readiness
Identifies possible solutions to each problem
Includes real-life and computational applications of linear and nonlinear data structures

This book is primarily aimed at undergraduates and graduates of computer science and information technology. Students of all engineering disciplines will also find this book useful.

Cover
Half Title
Title Page
Copyright Page
Table of Contents
Preface
Authors
1 Fundamental Principles of Algorithm and Recursion
	1.1 Algorithm, Its Pseudo-Code Representation and FlowChart
		1.1.1 Algorithm Definition
		1.1.2 Pseudo-Code Representation
		1.1.3 Flowchart
	1.2 Abstract Data Type
		1.2.1 List ADT
		1.2.2 Stack ADT
		1.2.3 Queue ADT
	1.3 Data Structure
		1.3.1 Definition
		1.3.2 Types of Data Structures or Their Classification
		1.3.3 Difference in Abstract Data Types and Data Structures
	1.4 Algorithm Efficiency or Performance Analysis of an Algorithm
		1.4.1 Space Complexity
			1.4.1.1 Components of Program Space
		1.4.2 Time Complexity
	1.5 Recursion and Design of Recursive Algorithms with Appropriate Examples
		1.5.1 Example 1: Implementing a Factorial Program Using Non-recursive Functions
		1.5.2 Example 2: Implementing a Factorial Program Using Recursive Functions
		1.5.3 Example 3: Implementing a Program That Displays the Sum of Digits in a Number Using Non-recursive Functions
		1.5.4 Example 4: Implementing a Program That Displays the Sum of Digits in a Number Using Recursive Functions
		1.5.5 Example 5: Implementation of the Sum of n First Natural Numbers by Means of Non-recursive Functions
		1.5.6 Example 6: Implementation of the Sum of n First Natural Numbers by Means of Recursive Functions
		1.5.7 Example 7: Implementation of the Prime Number Program Using Non-recursive Functions
		1.5.8 Example 8: Implementation of the Prime Number Program Using Recursive Functions
		1.5.9 Example 9: Implementation of the Reverse Number Program Using Non-recursive Functions
		1.5.10 Example 10: Implementation of the Reverse Number Program Using Recursive Functions
	1.6 Interview Questions
	1.7 Multiple Choice Questions
2 Sequential Representation of Linear Data Structures
	2.1 Distinction between Linear Data Structure and Nonlinear Data Structure
	2.2 Operations on Stack
		2.2.1 Primitive Operations on Stack
		2.2.2 Algorithm for Push and Pop Function
		2.2.3 A C Program for Stack Implementation Using the Array
	2.3 Applications of Stack
		2.3.1 Expression Evaluation
		2.3.2 Expression Conversion
		2.3.3 Backtracking
		2.3.4 Function Call and Function Return Process
		2.3.5 Recursive Functions
		2.3.6 Depth First Search (DFS)
		2.3.7 Undo Mechanism in Text Editors
		2.3.8 Reverse the String
		2.3.9 Towers of Hanoi Problems
		2.3.10 Parsing or Syntax Analysis
	2.4 Implementing Stack Applications
		2.4.1 Implementation of Post-Fix to Infix Conversion Using Stack
		2.4.2 Implementation of the Tower of Hanoi Puzzle Using Recursion
			2.4.2.1 Recursive Algorithm of the Tower of Hanoi Puzzle
			2.4.2.2 Program of Tower of Hanoi Puzzle Using Recursion
	2.5 Queue
		2.5.1 Linear Queue
			2.5.1.1 Representation and Operations on Linear Queue Using Arrays
			2.5.1.2 Implementation of Linear Queue Using Arrays
		2.5.2 Circular Queue
			2.5.2.1 Representation and Operations on Circular Queue Using Arrays
			2.5.2.2 Implementation of Circular Queue Using Arrays
		2.5.3 Priority Queue
			2.5.3.1 Types of Priority Queues
			2.5.3.2 Implementing Ascending Order Priority Queue Using Arrays
		2.5.4 Double-ended Queue
			2.5.4.1 Representation of Double End Queue
			2.5.4.2 Operations Performed on the Double-Ended Queue
			2.5.4.3 Implementing Double Ended Queue Using Arrays
	2.6 Applications of the Queue Data Structure
	2.7 Differences between Stack and Queue Data Structure
	2.8 Interview Questions
	2.9 Multiple Choice Questions
3 Void Pointer and Dynamic Memory Management
	3.1 Void Pointer
		3.1.1 Why Void Pointer Is Useful?
		3.1.2 Program: Assign Float or Int Type Variables to Void Pointer and Typecasting When Dereferencing of Void Pointer to Its Particular Data Type
		3.1.3 Program: Address Void Pointer Assigned to Float or Int Pointer Type Variable and Dereferencing of Void Pointer
		3.1.4 Important Point
	3.2 Pointer and Structure Data Type
		3.2.1 Program: Implement a Program That Can Access Structure’s Value Type Data Members by Using Structure’s Pointer Type of Variable
		3.2.2 Program: Implement a Program That Can Access Structure’s Pointer Type of Data Members by Using Structure’s Pointer Type of Variable
		3.2.3 Program: Structure’s Pointer Variable Incrementation
	3.3 Dynamic Memory Allocation
		3.3.1 Allocating a Block of Memory: malloc () Function
		3.3.2 Allocation of Multiple Block of Memory: calloc () Function
		3.3.3 Releasing the Used Space Using free () Function
		3.3.4 The realloc () Function
	3.4 Memory Leakage
		3.4.1 Program: To Demonstrate a Function with Memory Leak
		3.4.2 Program: To Demonstrate a Function without Memory Leak
	3.5 Dangling Pointer
		3.5.1 Deallocating a Memory Pointed by Pointer Causes Dangling Pointer
		3.5.2 Function Call
		3.5.3 When Local Variable Goes Out of Scope or Lifetime Is Over
	3.6 Interview Questions
	3.7 Multiple Choice Questions
4 Linked Representation of Linear Data Structures
	4.1 Limitations of Static Memory Allocation and Advantages of Dynamic Memory Management
		4.1.1 Introduction
		4.1.2 Major Limitations of Static Memory Allocation
		4.1.3 Major Advantages of Dynamic Memory Allocation
	4.2 Concept of the Linked List
		4.2.1 Introduction
		4.2.2 Singly Linked List Representation Using C Language
		4.2.3 Operations on the Linked List
		4.2.4 Program: Implementation of Static Linked List Containing Three Nodes and Displaying Values on Those Nodes
	4.3 Types of Linked List
		4.3.1 Singly Linear Linked List
		4.3.2 Singly Circular Linked List
		4.3.3 Doubly Linear Linked List
		4.3.4 Doubly Circular Linked list
	4.4 Singly Linear Linked List
		4.4.1 Algorithm for Singly Linear Linked List
			4.4.1.1 Algorithm: Insert a Node at the Last of Singly Linear Linked List
			4.4.1.2 Algorithm: Delete a Node from the Singly Linear Linked List
			4.4.1.3 Algorithm: Display Elements into Linked List
		4.4.2 Program: Implementation of Singly Linear Linked List
	4.5 Singly Circular Linked List
		4.5.1 Algorithm for Singly Circular Linked List
			4.5.1.1 Creation of Singly Circular Linked List
			4.5.1.2 Display Elements in Circular Linked List
			4.5.1.3 Delete Element in Circular Linked List
		4.5.2 Program: Implementation of Singly Circular Linked List
	4.6 Doubly Linear Linked List (DLLL)
		4.6.1 Algorithm for Doubly Linear Linked List
			4.6.1.1 Creation of Doubly Linear Linked List
			4.6.1.2 Delete an Element from Doubly Linear Linked List
		4.6.2 Program: Implementation of Doubly Linear Linked List
		4.6.3 Insert New Node at the Start of Doubly Linear Linked List
		4.6.4 Insert New Node at Last Position of Doubly Linked List
		4.6.5 Insert New Node at the Specified Position in Doubly Linear Linked List
	4.7 Doubly Circular Linked List
		4.7.1 Program: Implementation of Doubly Circular Linked List
	4.8 Stack Implementation Using Linked List
		4.8.1 Representation of Stack Using Linked List
		4.8.2 Program: Stack Implementation Using Linked List
	4.9 Linear Queue Implementation Using Linked List
		4.9.1 Representation of Queue Using Linked List
		4.9.2 Program: Linear Queue Implementation Using Linked List
	4.10 Circular Queue Implementation Using Linked List
		4.10.1 Operations on Circular Queue
		4.10.2 Program: Circular Queue Implementation Using Linked List
	4.11 Interview Questions
	4.12 Multiple Choice Questions
5 Nonlinear Data Structures: Trees
	5.1 Basic Concept and Tree Terminology
		5.1.1 Basic Concept
		5.1.2 Tree Terminology
	5.2 Data Structure for Binary Trees
		5.2.1 Binary Tree Definition with Example
		5.2.2 Types of Binary Tree
		5.2.3 Binary Tree Representation
			5.2.3.1 Sequential Representation or Array Representation
			5.2.3.2 Linked List Representation
		5.2.4 Operations on Binary Tree
		5.2.5 Binary Tree Traversals
			5.2.5.1 Breadth First Traversal or Level Order Traversal
			5.2.5.2 Depth First Traversal
		5.2.6 Simple Binary Tree Implementation
	5.3 Algorithms for Tree Traversals
		5.3.1 Recursive Algorithm for In-order Traversal
		5.3.2 Recursive Algorithm for Preorder Traversal
		5.3.3 Recursive Algorithm for Postorder Traversal
	5.4 Construct a Binary Tree from Given Traversing Methods
		5.4.1 Construct a Binary Tree from Given In-order and Preorder Traversing
		5.4.2 Construct a Binary Tree from Given In-order and Post-order Traversing
		5.4.3 Construct a Strictly or Full Binary Tree from Given Preorder and Post-order Traversing
	5.5 Binary Search Trees
		5.5.1 Basic Concepts of BSTs
		5.5.2 Operations on BSTs
			5.5.2.1 Insertion of Node in the BST
			5.5.2.2 Deletion of Node in the BST
			5.5.2.3 Searching for a Particular Node in BSTs
	5.6 BST Algorithms
		5.6.1 Create BST Algorithm
		5.6.2 Insert New Node in BST Algorithm
		5.6.3 Search Node in BST Algorithm
		5.6.4 Delete Any Node from BST Algorithm
		5.6.5 In-order Traversing of BST Algorithm
	5.7 Applications of Binary Tree and BST
	5.8 Heaps
		5.8.1 Basic of Heap data Structure
		5.8.2 Definition of Max Heap
		5.8.3 Operations Performed on Max Heap
			5.8.3.1 Insertion Operation in Max Heap
			5.8.3.2 Deletion Operation in Max Heap
			5.8.3.3 Finding Maximum Value in Max Heap
		5.8.4 Applications of Heaps
	5.9 AVL Tree
		5.9.1 Introduction of AVL Tree
		5.9.2 Definition
		5.9.3 AVL Tree Rotations
		5.9.4 Operations on an AVL Tree
			5.9.4.1 Search Operation in AVL Tree
			5.9.4.2 Insertion Operation in AVL Tree
			5.9.4.3 Deletion Operation in AVL Tree
		5.9.5 Advantages
		5.9.6 Disadvantages
	5.10 B Trees
		5.10.1 Introduction of B Tree
		5.10.2 B-Tree of Order mHas the Following Properties
		5.10.3 Operations on a B-Tree
			5.10.3.1 B-Tree Insertion
			5.10.3.2 B-Tree Deletion
			5.10.3.3 Search Operation in B-Tree
		5.10.4 Uses of B-tree
	5.11 B+ Trees
		5.11.1 Introduction of B+ Tree
		5.11.2 B+ Tree of Order mHas the Following Properties
		5.11.3 Operations on a B+ Tree
			5.11.3.1 B+ Tree Insertion
			5.11.3.2 B+ Tree Deletion
			5.11.3.3 Search Operation in B+ Tree
		5.11.4 Uses of B+ Tree
	5.12 Interview Questions
	5.13 Multiple Choice Questions
6 Nonlinear Data Structures: Graph
	6.1 Concepts and Terminology of Graph
		6.1.1 Introduction to Graph
		6.1.2 Definition of Graph
		6.1.3 Types of Graph
			6.1.3.1 Directed, Undirected and Mixed Graph
			6.1.3.2 Null Graph
			6.1.3.3 Complete Graph
			6.1.3.4 Strongly Connected Graph
			6.1.3.5 Unilaterally Connected and Weakly Connected Digraph
			6.1.3.6 Simple Graph
			6.1.3.7 Multigraph
			6.1.3.8 Cyclic Graph
			6.1.3.9 Acyclic Graph or Non-cyclic Graph
			6.1.3.10 Bipartite Graph
			6.1.3.11 Complete Bipartite Graph
	6.2 Representation of Graph Using Adjacency Matrix and Adjacency List
		6.2.1 Adjacency Matrix Representation
			6.2.1.1 Definition of Adjacency Matrix
			6.2.1.2 Example of Adjacency Matrix
			6.2.1.3 Algorithm of Creating or Representing Graph Using Adjacency Matrix
		6.2.2 Adjacency List Representation
			6.2.2.1 Basics of Adjacency List Representation
			6.2.2.2 Example of Adjacency List Representation for Directed Graph
			6.2.2.3 Example of Adjacency List Representation for Weighted Graph
	6.3 Graph traversal Techniques (Breadth First Search and Depth First Search)
		6.3.1 BFS Traversal of a Graph
			6.3.1.1 Basics of BFS
			6.3.1.2 Algorithm of BFS Traversal of a Graph
			6.3.1.3 Example of BFS
			6.3.1.4 Implementation of Graph Traversing Using the BFS Technique
			6.3.1.5 Time Complexity of BFS
			6.3.1.6 Advantages of BFS
			6.3.1.7 Disadvantages of BFS
			6.3.1.8 Applications of BFS
		6.3.2. DFS Traversal of a Graph
			6.3.2.1 Basics of DFS
			6.3.2.2 Non-recursive DFS Algorithm
			6.3.2.3 Recursive DFS Algorithm
			6.3.2.4 Explanation of Logic for Depth First Traversal (DFS)
			6.3.2.5 Implementation of Graph Traversing Using the DFS Technique
			6.3.2.6 Time Complexity of DFS
			6.3.2.7 Advantages of DFS
			6.3.2.8 Disadvantages of DFS
			6.3.2.9 Applications of DFS
	6.4 Applications of Graph as Shortest Path Algorithm and Minimum Spanning Tree
		6.4.1 Shortest Path Algorithm
			6.4.1.1 Dijkstra’s Algorithm for Shortest Path
			6.4.1.2 Dijkstra’s Algorithm
			6.4.1.3 Time Complexity
			6.4.1.4 Example Showing Working of Dijkstra’s Algorithm
		6.4.2 Minimum Spanning Tree
			6.4.2.1 Basic Concept of Spanning Tree and Minimum Spanning Tree
			6.4.2.2 Properties Spanning Tree
			6.4.2.3 Example of Spanning Tree
			6.4.2.4 Prime’s Algorithm
			6.4.2.5 Kruskal’s Algorithm
	6.5 Interview Questions
	6.6 Multiple Choice Questions
7 Searching and Sorting Techniques
	7.1 Need of Searching and Sorting
		7.1.1 Need of Searching
		7.1.2 Need for Sorting
	7.2 Sequential Search or Linear Search
		7.2.1 Linear Search or Sequential Search Basics
		7.2.2 Efficiency of Linear Search
		7.2.3 Algorithm of Linear Search
		7.2.4 Program of Linear Search
		7.2.5 Advantages of Linear Search
		7.2.6 Disadvantages of Linear Search
	7.3 Binary Search
		7.3.1 Binary Search Basics
		7.3.2 Binary Search Algorithm
		7.3.3 Example of Binary Search
		7.3.4 Program of Binary Search
		7.3.5 Analysis of Binary Search or Time Complexity of Binary Search
		7.3.6 Advantages of Binary Search
		7.3.7 Disadvantages of Binary Search
	7.4 Analysis of Searching Techniques for Best, Average and Worst Case
	7.5 Hashing Techniques
		7.5.1 Basic Concept of Hashing and Hash Table
		7.5.2 Example of Hashing
		7.5.3 Collision in Hash Function
		7.5.4 Rules for Choosing Good Hash Function
	7.6 Types of Hash Functions
		7.6.1 Mid-Square Method
		7.6.2 Division or Modulus Method
		7.6.3 The Folding Method
		7.6.4 Digit Analysis
	7.7 Collision Resolution Techniques
		7.7.1 Linear Probing
		7.7.2 Chaining without Replacement
		7.7.3 Chaining with Replacement
	7.8 Open and Closed Hashing
		7.8.1 Closed Hashing or Open Addressing
		7.8.2 Open Hashing or Closed Addressing
	7.9 Sorting
		7.9.1 Bubble Sort
			7.9.1.1 Introduction to Bubble Sort
			7.9.1.2 Algorithm of Bubble Sort
			7.9.1.3 Example of Bubble Sort
			7.9.1.4 Program of Bubble Sort
			7.9.1.5 Analysis of Bubble Sort
			7.9.1.6 Advantages of Bubble Sort
			7.9.1.7 Disadvantages of Bubble Sort
		7.9.2 Selection Sort
			7.9.2.1 Introduction to Selection Sort
			7.9.2.2 Example of Selection Sort
			7.9.2.3 Program of Selection Sort
			7.9.2.4 Analysis of Selection Sort
			7.9.2.5 Advantages of Selection Sort
			7.9.2.6 Disadvantages of Selection Sort
		7.9.3 Insertion Sort
			7.9.3.1 Introduction to Insertion Sort
			7.9.3.2 Example of Insertion Sort
			7.9.3.3 Program of Insertion Sort
			7.9.3.4 Analysis of Insertion Sort
			7.9.3.5 Insertion Sort: Real-Time Example
			7.9.3.6 Advantages of Insertion Sort
			7.9.3.7 Disadvantages of Insertion Sort
		7.9.4 Quick Sort
			7.9.4.1 Introduction to Quick Sort
			7.9.4.2 Algorithm of Quick Sort
			7.9.4.3 Example of Quick Sort
			7.9.4.4 Program of Quick Sort
			7.9.4.5 Analysis of Quick Sort
			7.9.4.6 Advantages of Quick Sort
			7.9.4.7 Disadvantages of Quick Sort
		7.9.5 Merge Sort
			7.9.5.1 Introduction to Merge Sort
			7.9.5.2 Algorithm of Merge Sort
			7.9.5.3 Example of Merge Sort
			7.9.5.4 Program of Merge Sort
			7.9.5.5 Analysis of Merge Sort
			7.9.5.6 Advantages of Merge Sort
			7.9.5.7 Disadvantages of Merge Sort
			7.9.5.8 Applications of Merge Sort
		7.9.6 Heap Sort
			7.9.6.1 Introduction to Heap Sort
			7.9.6.2 Examples of Heap
			7.9.6.3 Creating a Heap
			7.9.6.4 Processing a Heap
			7.9.6.5 Program of Heap Sort
			7.9.6.6 Analysis of Heap Sort
			7.9.6.7 Advantages of Heap Sort
			7.9.6.8 Disadvantages of Heap Sort
	7.10 Interview Questions
	7.11 Multiple Choice Questions
	References
Index