Syllabus Of Data Structures Using C

Introduction to Data structures:
Definition, Classification of data structures : primitive and non primitive. Operations on data structures.

Dynamic memory allocation and pointers:
Definition Accessing the address of a variable, Declaring and initializing pointers. Accessing a variable through its pointer. Meaning of static and dynamic memory allocation. Memory allocation functions : malloc, calloc, free and realloc.

Recursion:
Definition, Recursion in C, Writing Recursive programs – Binomial coefficient, Fibonacci, GCD.

Searching and Sorting Search:
Basic Search Techniques : Search algorithm searching techniques : sequential search, Binary search – Iterative and Recursive methods. Comparison between sequential and binary search.

Sort- General Background: Definition, different types: Bubble sort, Selection sort, Merge sort, Insertion sort, Quick sort

Stack – Definition, Array representation of stack, Operations on stack: Infix, prefix and postfix notations Conversion of an arithmetic expression from Infix to postfix. Applications of staks.

Queue - Definition, Array representation of queue, Types of queue: Simple queue, circular queue, double ended queue (deque) priority queue, operations on all types of Queues

Linked list – Definition, Components of linked list, Representation of linked list, Advantages and Disadvantages of linked list. Types of linked list : Singly linked list, Doubly linked list, Circular linked list and circular doubly linked list. Operations on singly linked list : creation, insertion, deletion, search and display.

Tree - Definition : Tree, Binary tree, Complete binary tree, Binary search tree, Heap Tree terminology : Root, Node, Degree of a node and tree, Terminal nodes, Nonterminal nodes, Siblings, Level, Edge, Path, depth, Parent node, ancestors of a node. Binary tree : Array representation of tree, Creation of binary tree. Traversal of Binary Tree : Preorder, Inorder and postorder.

Lab Programs

•  Write a C program to search for an element in an array using Binary search
•  Write a C program to sort a list of N elements using Bubble sort Technique
•  Write a C program to demonstrate the working of stack of size N using an array. The elements of the stack may assume to be of type integer or real, the operations to be supported are 1. PUSH 2. POP 3. DISPLAY. The program should print appropriate messages for STACK overflow, Under flow and empty, use separatefunctions to detect these cases
•  Write a C program to simulate the working of an ordinary Queue using an array. Provide the operations QINSERT, QDELETE and QDISPLAY. Check the Queue status for empty and full.
•  Write a C program to simulate the working of an Circular Queue using an array. Provide the operations CQINSERT, CQDELETE and CQDISPLAY. Check the Circular Queue status for empty and full.
•  Using dynamic variables and pointers Write a C program to construct a singly linked list consisting of the following information in each node; Roll – No (Integer), Name (Character string). The operations to be supported are :

1.  LINSERT Inserting a node in the front of the list
2.  LDELETE Deleting the node based on Roll – No
3.  LSEARCH Searching a node based on Roll-No
4.  LDISPLAY Displaying all the nodes in the list

•  Write a C program to sort a list of N elements using Merge sort Algorithm
•  Using Dynamic variables and pointers construct Binary search tree of integers, Write C functions to do the following:

1.  Given a KEY, Perform a search in Binary search tree. If it is found display Key found else insert the key in the Binary search tree.
2.  While constructing the Binary search tree do not add any duplicate
3.  Display the tree using any of the traversal method

•  Write a C program to sort a list of N elements of integer type using heap sort Algorithm
•  Write a C program to simulate the working of Towers of Hanoi problem for N disks, print the total number of Moves taken by the program.
•  Write a C program to sort a list of N elements of integer type using quick sort Algorithm
•  Write a C program to find ncr using recursion
•  Write a C program to convert and print a given valid fully parenthesized in fix arithmetic expression to post fix expression, the expression consists of single character (letter or digit) as operands and +, -, * , / as operators, assume that only binary operators are allowed in the expression
•  Write a C program to search for an element using sequential search
•  Write a C program to create file for N students, it should contain Roll-No, Name and Marks in two subjects. Using the above created file, create an out put file which contains Roll-No, Name, Marks in subjects, Total and Average.