LECTURE NOTES ON
DATA STRUCTURES USING C
Revision 4.0
1 December, 2014
L. V. NARASIMHA PRASAD
Professor
Department of Computer Science and Engineering
E. KRISHNA RAO PATRO
Associate Professor
Department of Computer Science and Engineering
INSTITUTE OF AERONAUTICAL ENGINEERING
DUNDIGAL – 500 043, HYDERABAD
2014-2015
, CONTENTS
CHAPTER 1 BASIC CONCEPTS
1.1 Introduction to Data Structures
1.2 Data structures: organizations of data
1.3. Abstract Data Type (ADT)
1.4. Selecting a data structure to match the operation
1.5. Algorithm
1.6. Practical Algorithm design issues
1.7. Performance of a program
1.8. Classification of Algorithms
1.9. Complexity of Algorithms
1.10. Rate of Growth
1.11. Analyzing Algorithms
Exercises
Multiple Choice Questions
CHAPTER 2 RECURSION
2.1. Introduction to Recursion
2.2. Differences between recursion and iteration
2.3. Factorial of a given number
2.4. The Towers of Hanoi
2.5. Fibonacci Sequence Problem
2.6. Program using recursion to calculate the NCR of a given number
2.7. Program to calculate the least common multiple of a given number
2.8. Program to calculate the greatest common divisor
Exercises
Multiple Choice Questions
CHAPTER 3 LINKED LISTS
3.1. Linked List Concepts
3.2. Types of Linked Lists
3.3. Single Linked List
3.3.1. Source Code for the Implementation of Single Linked List
3.4. Using a header node
3.5. Array based linked lists
3.6. Double Linked List
3.6.1. A Complete Source Code for the Implementation of Double Linked List
3.7. Circular Single Linked List
3.7.1. Source Code for Circular Single Linked List
3.8. Circular Double Linked List
3.8.1. Source Code for Circular Double Linked List
3.9. Comparison of Linked List Variations
3.10. Polynomials
3.10.1. Source code for polynomial creation with help of linked list
3.10.2. Addition of Polynomials
3.10.3. Source code for polynomial addition with help of linked list:
Exercise
Multiple Choice Questions
I
,CHAPTER 4 STACK AND QUEUE
4.1. Stack
4.1.1. Representation of Stack
4.1.2. Program to demonstrate a stack, using array
4.1.3. Program to demonstrate a stack, using linked list
4.2. Algebraic Expressions
4.3. Converting expressions using Stack
4.3.1. Conversion from infix to postfix
4.3.2. Program to convert an infix to postfix expression
4.3.3. Conversion from infix to prefix
4.3.4. Program to convert an infix to prefix expression
4.3.5. Conversion from postfix to infix
4.3.6. Program to convert postfix to infix expression
4.3.7. Conversion from postfix to prefix
4.3.8. Program to convert postfix to prefix expression
4.3.9. Conversion from prefix to infix
4.3.10. Program to convert prefix to infix expression
4.3.11. Conversion from prefix to postfix
4.3.12. Program to convert prefix to postfix expression
4.4. Evaluation of postfix expression
4.5. Applications of stacks
4.6. Queue
4.6.1. Representation of Queue
4.6.2. Program to demonstrate a Queue using array
4.6.3. Program to demonstrate a Queue using linked list
4.7. Applications of Queue
4.8. Circular Queue
4.8.1. Representation of Circular Queue
4.9. Deque
4.10. Priority Queue
Exercises
Multiple Choice Questions
CHAPTER 5 BINARY TREES
5.1. Trees
5.2. Binary Tree
5.3. Binary Tree Traversal Techniques
5.3.1. Recursive Traversal Algorithms
5.3.2. Building Binary Tree from Traversal Pairs
5.3.3. Binary Tree Creation and Traversal Using Arrays
5.3.4. Binary Tree Creation and Traversal Using Pointers
5.3.5. Non Recursive Traversal Algorithms
5.4. Expression Trees
5.4.1. Converting expressions with expression trees
5.5. Threaded Binary Tree
5.6. Binary Search Tree
5.7. General Trees (m-ary tree)
5.7.1. Converting a m-ary tree (general tree) to a binary tree
5.8. Search and Traversal Techniques for m-ary trees
5.8.1. Depth first search
5.8.2. Breadth first search
5.9. Sparse Matrices
Exercises
Multiple Choice Questions
II
, CHAPTER 6 GRAPHS
6.1. Introduction to Graphs
6.2. Representation of Graphs
6.3. Minimum Spanning Tree
6.3.1. Kruskal’s Algorithm
6.3.2. Prim’s Algorithm
6.4. Reachability Matrix
6.5. Traversing a Graph
6.5.1. Breadth first search and traversal
6.5.2. Depth first search and traversal
Exercises
Multiple Choice Questions
CHAPTER 7 SEARCHING AND SORTING
7.1. Linear Search
7.1.1. A non-recursive program for Linear Search
7.1.1. A Recursive program for linear search
7.2. Binary Search
7.1.2. A non-recursive program for binary search
7.1.3. A recursive program for binary search
7.3. Bubble Sort
7.3.1. Program for Bubble Sort
7.4. Selection Sort
7.4.1 Non-recursive Program for selection sort
7.4.2. Recursive Program for selection sort
7.5. Quick Sort
7.5.1. Recursive program for Quick Sort
7.6. Priority Queue and Heap and Heap Sort
7.6.2. Max and Min Heap data structures
7.6.2. Representation of Heap Tree
7.6.3. Operations on heap tree
7.6.4. Merging two heap trees
7.6.5. Application of heap tree
7.7. Heap Sort
7.7.1. Program for Heap Sort
7.8. Priority queue implementation using heap tree
Exercises
Multiple Choice Questions
References and Selected Readings
Index
III
DATA STRUCTURES USING C
Revision 4.0
1 December, 2014
L. V. NARASIMHA PRASAD
Professor
Department of Computer Science and Engineering
E. KRISHNA RAO PATRO
Associate Professor
Department of Computer Science and Engineering
INSTITUTE OF AERONAUTICAL ENGINEERING
DUNDIGAL – 500 043, HYDERABAD
2014-2015
, CONTENTS
CHAPTER 1 BASIC CONCEPTS
1.1 Introduction to Data Structures
1.2 Data structures: organizations of data
1.3. Abstract Data Type (ADT)
1.4. Selecting a data structure to match the operation
1.5. Algorithm
1.6. Practical Algorithm design issues
1.7. Performance of a program
1.8. Classification of Algorithms
1.9. Complexity of Algorithms
1.10. Rate of Growth
1.11. Analyzing Algorithms
Exercises
Multiple Choice Questions
CHAPTER 2 RECURSION
2.1. Introduction to Recursion
2.2. Differences between recursion and iteration
2.3. Factorial of a given number
2.4. The Towers of Hanoi
2.5. Fibonacci Sequence Problem
2.6. Program using recursion to calculate the NCR of a given number
2.7. Program to calculate the least common multiple of a given number
2.8. Program to calculate the greatest common divisor
Exercises
Multiple Choice Questions
CHAPTER 3 LINKED LISTS
3.1. Linked List Concepts
3.2. Types of Linked Lists
3.3. Single Linked List
3.3.1. Source Code for the Implementation of Single Linked List
3.4. Using a header node
3.5. Array based linked lists
3.6. Double Linked List
3.6.1. A Complete Source Code for the Implementation of Double Linked List
3.7. Circular Single Linked List
3.7.1. Source Code for Circular Single Linked List
3.8. Circular Double Linked List
3.8.1. Source Code for Circular Double Linked List
3.9. Comparison of Linked List Variations
3.10. Polynomials
3.10.1. Source code for polynomial creation with help of linked list
3.10.2. Addition of Polynomials
3.10.3. Source code for polynomial addition with help of linked list:
Exercise
Multiple Choice Questions
I
,CHAPTER 4 STACK AND QUEUE
4.1. Stack
4.1.1. Representation of Stack
4.1.2. Program to demonstrate a stack, using array
4.1.3. Program to demonstrate a stack, using linked list
4.2. Algebraic Expressions
4.3. Converting expressions using Stack
4.3.1. Conversion from infix to postfix
4.3.2. Program to convert an infix to postfix expression
4.3.3. Conversion from infix to prefix
4.3.4. Program to convert an infix to prefix expression
4.3.5. Conversion from postfix to infix
4.3.6. Program to convert postfix to infix expression
4.3.7. Conversion from postfix to prefix
4.3.8. Program to convert postfix to prefix expression
4.3.9. Conversion from prefix to infix
4.3.10. Program to convert prefix to infix expression
4.3.11. Conversion from prefix to postfix
4.3.12. Program to convert prefix to postfix expression
4.4. Evaluation of postfix expression
4.5. Applications of stacks
4.6. Queue
4.6.1. Representation of Queue
4.6.2. Program to demonstrate a Queue using array
4.6.3. Program to demonstrate a Queue using linked list
4.7. Applications of Queue
4.8. Circular Queue
4.8.1. Representation of Circular Queue
4.9. Deque
4.10. Priority Queue
Exercises
Multiple Choice Questions
CHAPTER 5 BINARY TREES
5.1. Trees
5.2. Binary Tree
5.3. Binary Tree Traversal Techniques
5.3.1. Recursive Traversal Algorithms
5.3.2. Building Binary Tree from Traversal Pairs
5.3.3. Binary Tree Creation and Traversal Using Arrays
5.3.4. Binary Tree Creation and Traversal Using Pointers
5.3.5. Non Recursive Traversal Algorithms
5.4. Expression Trees
5.4.1. Converting expressions with expression trees
5.5. Threaded Binary Tree
5.6. Binary Search Tree
5.7. General Trees (m-ary tree)
5.7.1. Converting a m-ary tree (general tree) to a binary tree
5.8. Search and Traversal Techniques for m-ary trees
5.8.1. Depth first search
5.8.2. Breadth first search
5.9. Sparse Matrices
Exercises
Multiple Choice Questions
II
, CHAPTER 6 GRAPHS
6.1. Introduction to Graphs
6.2. Representation of Graphs
6.3. Minimum Spanning Tree
6.3.1. Kruskal’s Algorithm
6.3.2. Prim’s Algorithm
6.4. Reachability Matrix
6.5. Traversing a Graph
6.5.1. Breadth first search and traversal
6.5.2. Depth first search and traversal
Exercises
Multiple Choice Questions
CHAPTER 7 SEARCHING AND SORTING
7.1. Linear Search
7.1.1. A non-recursive program for Linear Search
7.1.1. A Recursive program for linear search
7.2. Binary Search
7.1.2. A non-recursive program for binary search
7.1.3. A recursive program for binary search
7.3. Bubble Sort
7.3.1. Program for Bubble Sort
7.4. Selection Sort
7.4.1 Non-recursive Program for selection sort
7.4.2. Recursive Program for selection sort
7.5. Quick Sort
7.5.1. Recursive program for Quick Sort
7.6. Priority Queue and Heap and Heap Sort
7.6.2. Max and Min Heap data structures
7.6.2. Representation of Heap Tree
7.6.3. Operations on heap tree
7.6.4. Merging two heap trees
7.6.5. Application of heap tree
7.7. Heap Sort
7.7.1. Program for Heap Sort
7.8. Priority queue implementation using heap tree
Exercises
Multiple Choice Questions
References and Selected Readings
Index
III
