CS306ES: DATA STRUCTURES THROUGH C++ LAB
B.Tech. II Year I Sem. L T P C
0 0 3 2

Course Objectives:

• To write and execute programs in C++ to solve problems using data structures such as arrays, linked lists, stacks, queues, trees, graphs, hash tables and search trees.
• To learn to write C++programs to implement various sorting and searching algorithms

Course Outcomes:

• Able to identify the appropriate data structures and algorithms for solving real world problems.
• Able to implement various kinds of searching and sorting techniques.
• Able to implement data structures such as stacks, queues, Search trees, and hash tables to solve various computing problems.

1. Write a C++ program that uses functions to perform the following:
   1. Create a singly linked list of integers.
   2. Delete a given integer from the above linked list.
   3. Display the contents of the above list after deletion.
2. Write a template based C++ program that uses functions to perform the following:
   1. Create a doubly linked list of elements.
   2. Delete a given element from the above doubly linked list.
   3. Display the contents of the above list after deletion.
3. Write a C++ program that uses stack operations to convert a given infix expression into its postfix equivalent, Implement the stack using an array.
4. Write a C++ program to implement a double ended queue ADT using an array, using a doubly linked list.
5. Write a C++ program that uses functions to perform the following:
   1. Create a binary search tree of characters.
   2. Traverse the above Binary search tree recursively in preorder, in order and post order,
6. 6. Write a C++ program that uses function templates to perform the following:
   1. Search for a key element in a list of elements using linear search.
   2. Search for a key element in a list of sorted elements using binary search.
7. Write a C++ program that implements Insertion sort algorithm to arrange a list of integers in ascending order.
8. Write a template based C++ program that implements selection sort algorithm to arrange a list of elements in descending order.
9. Write a template based C++ program that implements Quick sort algorithm to arrange a list of elements in ascending order.
10. Write a C++ program that implements Heap sort algorithm for sorting a list of integers in ascending order.
11. Write a C++ program that implements Merge sort algorithm for sorting a list of integers in ascending order
12. Write a C++ program to implement all the functions of a dictionary (ADT) using hashing.
13. Write a C++ program that implements Radix sort algorithm for sorting a list of integers in ascending order
14. Write a C++ program that uses functions to perform the following:
    1. Create a binary search tree of integers.
    2. Traverse the above Binary search tree non recursively in inorder.
15. 15. Write a C++ program that uses functions to perform the following:
    1. Create a binary search tree of integers.
    2. Search for an integer key in the above binary search tree non recursively.
    3. Search for an integer key in the above binary search tree recursively.

REFERENCE BOOKS

1. Data Structures using C++, D. S. Malik, 2nd edition, Cengage learning.
2. Data Structures using C++, V. Patil, Oxford University Press.
3. Fundamentals of Data structures in C++, 2nd edition, E. Horowitz, S. Sahni and D. Mehta, Universities Press.
4. C++ Plus Data Structures, 4th edition, Nell Dale, Jones and Bartlett student edition.