CS 1212 DATA STRUCTURES AND ALGORITHMS LABORATORY 0 0 3 100
AIM
To implement Quene, stack, linked lists and to implement search, sort and traversal
technique.
1. Queue implementation using arrays.
2. Stack implementation-using arrays.
3. Singly, doubly and circular liked list implementation and all possible operations on lists.
4. Queue and Stack implementation using linked list
5. Binary search tree implementation using linked list and
possible operations on binary
search trees.
6. In-order, preorder and post order traversals.
7. Quick sort implementation and its efficiency calculation.
8. Binary Search implementation.
9. Graph implementation using arrays and list structure.
10. Depth first and Breadth first traversal in graphs.
P = 45 Total = 45
Detailed Syllabus
1. Queue implementation using arrays
Aim
To implement queue using arrays.
Objective
To represent queue using an array and to perform insert and delete operations in
the queue.
Exercises
1. Declare an array Q of size N.
2. Assign F and R to be the front and rear pointers of the queue and assign 0 to F and R.
3. Get the new element Y to be inserted in to the queue
4. If R is less than N, insert Y at the end, by incrementing R by 1. Otherwise display
queue is full.
5. If F is zero then assign F to be 1.
6. To delete an element check whether F is greater than zero, then delete an element
pointed by F, otherwise display queue is empty.
7. If F and R are equal the set F = R=0;otherwise F=F+1;
8. Display the queue Q from F to R.
Software Requirements
Turbo C - 30 nodes
Hardware Requirements
PC (preferably P-IV) - 30 nos.
2. Stack implementation using arrays.
Aim
To implement stack using arrays
Objective
To represent stack using an array and to perform push and pop operations in the stack.
Exercises
1. Declare an array S of size N.
2. Assign TOP as a pointer to denote the top element in the stack
3. Get the new element Y to be added in to the stack.
4. If TOP is greater than or equal to N then display stack over flow; otherwise set
TOP=TOP+1.
5. Set S[TOP] = Y.
6. To delete top element from the stack check if TOP =0,the display stack underflow, otherwise decrement TOP by one, and display S [TOP+1].
7. Display the stack S from 1 to TOP.
Software Requirements
Turbo C - 30 nodes
Hardware Requirements
PC - 30 nos.
3. Singly, Doubly and Circular linked list implementation and all possible operations on lists
Aim
To implement singly, doubly and circular linked list and performing insert, delete and search operations.
Objective
To represent singly, doubly and circular linked list and to perform operations like
insertion, deletion and search.
Exercises
SINGLY LINKED LIST:
1. Set a node to contain INFO and LINK fields.
2. Allot memory dynamically for a node and declare it as a header H.
3. To create a singly linked lists get the element N and allot memory for a node S1.
4. Set S1->INFO=N; and S1->LINK=NULL.
5. Repeat the above two steps for all the elements.
6. A node can be inserted at the front, in the middle or at the end of the list.
7. To insert a node X at the front check whether the list is empty, if not set
X->LINK=H->LINK and H->LINK=X.
8. To insert a node X at the end travel till the end of the list and assign the last node’s LINK value to X.
9. To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->LINK=Y->LINK and Y->LINK=X
10. A node can be deleted at the front, in the middle or at the end of the list.
11. To delete a node X at the front set H->LINK=H->LINK->LINK.
12. To delete a node X at the end travel the list till the end and assign the previous to last node’s LINK value to be NULL.
13. To delete a node X after the specified node Y, travel the list till the node Y is reached Set Y->LINK= Y->LINK->LINK.
14. To search an element E traverse the list until E is found.
DOUBLY LINKED LIST:
1. Set a node to contain INFO and RLINK and LLINK fields.
2. Allot memory dynamically for a node and declare it as a header H.
3. To create a doubly linked list get the element N and allot memory for a node S1.
4. Set S1->INFO=N; and S1->RLINK=NULL, S1->LLINK=H.
5. Repeat the above two steps for all the elements.
6. A node can be inserted at the front, in the middle or at the end of the list.
7. To insert a node X at the front check whether the list is empty, if not set
X->RLINK=H->RLINK and H->RLINK=X.
8. To insert a node X at the end travel till the end of the list and assign the last node’s RLINK value to X and set X->LLINK=last node’s RLINK.
9. To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->RLINK=Y->RLINK , Y->RLINK=X,X->LLINK=Y and X->RLINK->LLINK=X
10. A node can be deleted at the front, in the middle or at the end of the list.
11. To delete a node X at the front set X->RLINK->LLINK=H,H->RLINK->RLINK= X.
12. To delete a node X at the end travel the list till the end and assign the previous to last node’s RLINK value to be NULL.
13. To delete a node X after the specified node Y, travel the list till the node Y is reached Set X->RLINK->LLINK=Y, Y->RLINK= X->RLINK.
14. To search an element E traverse the list until E is found.
CIRCULAR LINKED LIST
1. Set a node to contain INFO and LINK fields.
2. Allot memory dynamically for a node and declare it as a header H.
3. To create a singly linked lists get the element N and allot memory for a node S1.
4. Set S1->INFO=N; and S1->LINK=H.
5. Repeat the above two steps for all the elements.
6. A node can be inserted at the front, in the middle or at the end of the list.
7. To insert a node X at the front check whether the list is empty, if not set
X->LINK=H->LINK and H->LINK=X.
8. To insert a node X at the end travel till the end of the list and assign the last node’s LINK value to X and X->LINK=H.
9. To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->LINK=Y->LINK and Y->LINK=X
10. A node can be deleted at the front, in the middle or at the end of the list.
11. To delete a node X at the front set H->LINK=H->LINK->LINK.
12. To delete a node X at the end travel the list till the end and assign the previous to last node’s LINK value to be H.
13. To delete a node X after the specified node Y, travel the list till the node Y is reached Set Y->LINK= Y->LINK->LINK.
14. To search an element E traverse the list until E is found.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
4. Queue and Stack implementation using linked list
Aim
To implement queue and stack using linked list.
Objective
To represent queue and stack operations using linear linked list.
Exercises
STACK
1. Create a singly linked list.
2. To PUSH a node X travel the list until the end is reached. Assign last node’s LINK to X.
3. To POP a node X delete the last node and set the previous to last node’s LINK to NULL.
4. To display the stack contents traverse the list from the header till the last node.
QUEUE
1. Create a singly linked list.
2. Set first node as F and last node as R.
3. To insert a node X set R->LINK=X;
4. To delete a node X check whether the list is empty, if not set F=F->LINK;
5. To display the queue contents traverse the list from F to R.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
5. In-order, Pre-order and Post-order Traversals
Aim
To perform In-order, Preorder and Post order traversals in Binary Search Tree
Objective
To perform traversals in binary search tree using In-order, Preorder and Post-order techniques.
Exercises
1. Create the binary search tree
2. To perform in-order traversals
a. process the left sub tree
b. process the root
c. process the right sub-tree
3. To perform preorder traversal
a. process the root node
b. process the left
c. process the right
4. To perform post-order traversal
a. process the left node
b. process the right node.
c. process the root node.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
6. Binary search tree implementation using linked list and possible operations on binary search trees
Aim
To implement binary search tree using linked list and possible operations on binary search trees.
Objective
To represent binary search tree using linked list and to implement operations like insertion, deletion and search operations
Exercises
1. Create the memory space for the root node and initialize the value to zero.
2. Read the value.
3. If the value is less than the root value ,it is assigned as the left child of the root.
Else if new value is greater than the root value, it is assigned as the right child
of the root. Else if there is no value in the root, the new value is assigned as the
root.
4. The step(2) and (3) is repeated to insert the ‘n’ number of values.
Search operation
1. Read the value to be searched.
2. Check whether the root is not null.
3. If the value to be searched is less than the root, consider the left sub-tree for searching the particular element else if the value is greater than the root consider the right sub - tree to search the particular element else if the value is equal then return the value that is the value which was searched.
Insertion
1. Read the value to be inserted
2. First perform the search operation to check whether the key values is different from those existing element
3. If the search is unsuccessful, then the key is inserted at the point the search is
terminated.
Deletion
1. Read the key value to be deleted
2. First perform search operation to get that particular key element
3. If it is, check whether
(a) it is leaf node,
(b) or it has only one sub-tree
(c) or it has exactly 2 sub-trees
4. If the key value is the leaf-node, assign null value to that node ,else if the key contains only one sub-tree either left (or)right sub-tree, if the key is root, it is discarded and the root its single sub-tree becomes the new search tree root. Else if the key is the child node , then we change the pointer from the root of key to the child of the key.
5. If the key contain both left and right sub-tree replace the key with either largest
element is the left sub-tree or smallest element is the right sub-tree.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
7. Quick sort implementation and it’s efficiency calculation
Aim
To implement quick sort and calculate it’s efficiency
Objective
To arrange the elements using fastest sorting technique quick sort and the time taken to sort the elements.
Exercises
1. Get N elements which are to be sorted, and store it in the array A.
2. Select the element from A[0 ] to A[N-1] for middle. This element is the pivot.
3. Partition the remaining elements into the segments left and right so that no elements in left has a key larger than that of the pivot and no elements in right has a key smaller than that of the pivot.
4. Sort left using quick sort recursively.
5. Sort right using quick sort recursively.
6. Display the sorted array A.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
8. Binary Search implementation
Aim
To implement binary search technique.
Objective
To perform sorting using binary search technique.
Exercises
1. Get N elements and store the elements in the array K in ascending order.
2. Get the element to be searched X.
3. Initialize LOW=1,HIGH=N;
4. Until LOW<= HIGH check whether X K[MIDDLE] ,if so LOW=MIDDLE+1,otherwise Display UNSUCCESSFUL SEARCH
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
9. Graph implementation using arrays and list structure
Aim
Graph implementation using arrays and linear linked list.
Objective
To represent Graph using arrays and linked list
Exercises
1. Construct adjacency matrix, such that it has value one if there exists direct path between two vertices and otherwise zero.
2. For linked representation of graph an array H of head nodes each contains one pointer field INFO.
3. If there exists a direct path between ith head node H[I] and the node X , then
H[I]->INFO=X.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
10. Depth first and Depth first traversal in Graph
Aim
To implement depth first and Breadth first traversal in graphs.
Objective
Depth first and Breadth first traversal implementation in graphs .
Exercises
1. Construct a graph.
2. To traverse a graph in breadth first technique ,label vertex v as reached.
3. Initialize Q to be a queue with only v in it.
4. While Q is not empty, do the following steps
5. Delete a vertex W from the queue
6. Let u be a vertex adjacent from w.
7. While u, if u has not been labeled then add u to the queue label u as reached.
8. Set u = next vertex, that is adjacent from w
9. To traverse a graph in DFS label vertex v as reached.
10. While u is adjacent to v, if u is not reached call DFS recursively
11. Set u as next adjacent vertex of v. Repeat from step 9 till all the nodes are visited.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
AIM
To implement Quene, stack, linked lists and to implement search, sort and traversal
technique.
1. Queue implementation using arrays.
2. Stack implementation-using arrays.
3. Singly, doubly and circular liked list implementation and all possible operations on lists.
4. Queue and Stack implementation using linked list
5. Binary search tree implementation using linked list and
possible operations on binary
search trees.
6. In-order, preorder and post order traversals.
7. Quick sort implementation and its efficiency calculation.
8. Binary Search implementation.
9. Graph implementation using arrays and list structure.
10. Depth first and Breadth first traversal in graphs.
P = 45 Total = 45
Detailed Syllabus
1. Queue implementation using arrays
Aim
To implement queue using arrays.
Objective
To represent queue using an array and to perform insert and delete operations in
the queue.
Exercises
1. Declare an array Q of size N.
2. Assign F and R to be the front and rear pointers of the queue and assign 0 to F and R.
3. Get the new element Y to be inserted in to the queue
4. If R is less than N, insert Y at the end, by incrementing R by 1. Otherwise display
queue is full.
5. If F is zero then assign F to be 1.
6. To delete an element check whether F is greater than zero, then delete an element
pointed by F, otherwise display queue is empty.
7. If F and R are equal the set F = R=0;otherwise F=F+1;
8. Display the queue Q from F to R.
Software Requirements
Turbo C - 30 nodes
Hardware Requirements
PC (preferably P-IV) - 30 nos.
2. Stack implementation using arrays.
Aim
To implement stack using arrays
Objective
To represent stack using an array and to perform push and pop operations in the stack.
Exercises
1. Declare an array S of size N.
2. Assign TOP as a pointer to denote the top element in the stack
3. Get the new element Y to be added in to the stack.
4. If TOP is greater than or equal to N then display stack over flow; otherwise set
TOP=TOP+1.
5. Set S[TOP] = Y.
6. To delete top element from the stack check if TOP =0,the display stack underflow, otherwise decrement TOP by one, and display S [TOP+1].
7. Display the stack S from 1 to TOP.
Software Requirements
Turbo C - 30 nodes
Hardware Requirements
PC - 30 nos.
3. Singly, Doubly and Circular linked list implementation and all possible operations on lists
Aim
To implement singly, doubly and circular linked list and performing insert, delete and search operations.
Objective
To represent singly, doubly and circular linked list and to perform operations like
insertion, deletion and search.
Exercises
SINGLY LINKED LIST:
1. Set a node to contain INFO and LINK fields.
2. Allot memory dynamically for a node and declare it as a header H.
3. To create a singly linked lists get the element N and allot memory for a node S1.
4. Set S1->INFO=N; and S1->LINK=NULL.
5. Repeat the above two steps for all the elements.
6. A node can be inserted at the front, in the middle or at the end of the list.
7. To insert a node X at the front check whether the list is empty, if not set
X->LINK=H->LINK and H->LINK=X.
8. To insert a node X at the end travel till the end of the list and assign the last node’s LINK value to X.
9. To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->LINK=Y->LINK and Y->LINK=X
10. A node can be deleted at the front, in the middle or at the end of the list.
11. To delete a node X at the front set H->LINK=H->LINK->LINK.
12. To delete a node X at the end travel the list till the end and assign the previous to last node’s LINK value to be NULL.
13. To delete a node X after the specified node Y, travel the list till the node Y is reached Set Y->LINK= Y->LINK->LINK.
14. To search an element E traverse the list until E is found.
DOUBLY LINKED LIST:
1. Set a node to contain INFO and RLINK and LLINK fields.
2. Allot memory dynamically for a node and declare it as a header H.
3. To create a doubly linked list get the element N and allot memory for a node S1.
4. Set S1->INFO=N; and S1->RLINK=NULL, S1->LLINK=H.
5. Repeat the above two steps for all the elements.
6. A node can be inserted at the front, in the middle or at the end of the list.
7. To insert a node X at the front check whether the list is empty, if not set
X->RLINK=H->RLINK and H->RLINK=X.
8. To insert a node X at the end travel till the end of the list and assign the last node’s RLINK value to X and set X->LLINK=last node’s RLINK.
9. To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->RLINK=Y->RLINK , Y->RLINK=X,X->LLINK=Y and X->RLINK->LLINK=X
10. A node can be deleted at the front, in the middle or at the end of the list.
11. To delete a node X at the front set X->RLINK->LLINK=H,H->RLINK->RLINK= X.
12. To delete a node X at the end travel the list till the end and assign the previous to last node’s RLINK value to be NULL.
13. To delete a node X after the specified node Y, travel the list till the node Y is reached Set X->RLINK->LLINK=Y, Y->RLINK= X->RLINK.
14. To search an element E traverse the list until E is found.
CIRCULAR LINKED LIST
1. Set a node to contain INFO and LINK fields.
2. Allot memory dynamically for a node and declare it as a header H.
3. To create a singly linked lists get the element N and allot memory for a node S1.
4. Set S1->INFO=N; and S1->LINK=H.
5. Repeat the above two steps for all the elements.
6. A node can be inserted at the front, in the middle or at the end of the list.
7. To insert a node X at the front check whether the list is empty, if not set
X->LINK=H->LINK and H->LINK=X.
8. To insert a node X at the end travel till the end of the list and assign the last node’s LINK value to X and X->LINK=H.
9. To insert a node X after the specified node Y, travel the list till the node Y is reached. Set X->LINK=Y->LINK and Y->LINK=X
10. A node can be deleted at the front, in the middle or at the end of the list.
11. To delete a node X at the front set H->LINK=H->LINK->LINK.
12. To delete a node X at the end travel the list till the end and assign the previous to last node’s LINK value to be H.
13. To delete a node X after the specified node Y, travel the list till the node Y is reached Set Y->LINK= Y->LINK->LINK.
14. To search an element E traverse the list until E is found.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
4. Queue and Stack implementation using linked list
Aim
To implement queue and stack using linked list.
Objective
To represent queue and stack operations using linear linked list.
Exercises
STACK
1. Create a singly linked list.
2. To PUSH a node X travel the list until the end is reached. Assign last node’s LINK to X.
3. To POP a node X delete the last node and set the previous to last node’s LINK to NULL.
4. To display the stack contents traverse the list from the header till the last node.
QUEUE
1. Create a singly linked list.
2. Set first node as F and last node as R.
3. To insert a node X set R->LINK=X;
4. To delete a node X check whether the list is empty, if not set F=F->LINK;
5. To display the queue contents traverse the list from F to R.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
5. In-order, Pre-order and Post-order Traversals
Aim
To perform In-order, Preorder and Post order traversals in Binary Search Tree
Objective
To perform traversals in binary search tree using In-order, Preorder and Post-order techniques.
Exercises
1. Create the binary search tree
2. To perform in-order traversals
a. process the left sub tree
b. process the root
c. process the right sub-tree
3. To perform preorder traversal
a. process the root node
b. process the left
c. process the right
4. To perform post-order traversal
a. process the left node
b. process the right node.
c. process the root node.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
6. Binary search tree implementation using linked list and possible operations on binary search trees
Aim
To implement binary search tree using linked list and possible operations on binary search trees.
Objective
To represent binary search tree using linked list and to implement operations like insertion, deletion and search operations
Exercises
1. Create the memory space for the root node and initialize the value to zero.
2. Read the value.
3. If the value is less than the root value ,it is assigned as the left child of the root.
Else if new value is greater than the root value, it is assigned as the right child
of the root. Else if there is no value in the root, the new value is assigned as the
root.
4. The step(2) and (3) is repeated to insert the ‘n’ number of values.
Search operation
1. Read the value to be searched.
2. Check whether the root is not null.
3. If the value to be searched is less than the root, consider the left sub-tree for searching the particular element else if the value is greater than the root consider the right sub - tree to search the particular element else if the value is equal then return the value that is the value which was searched.
Insertion
1. Read the value to be inserted
2. First perform the search operation to check whether the key values is different from those existing element
3. If the search is unsuccessful, then the key is inserted at the point the search is
terminated.
Deletion
1. Read the key value to be deleted
2. First perform search operation to get that particular key element
3. If it is, check whether
(a) it is leaf node,
(b) or it has only one sub-tree
(c) or it has exactly 2 sub-trees
4. If the key value is the leaf-node, assign null value to that node ,else if the key contains only one sub-tree either left (or)right sub-tree, if the key is root, it is discarded and the root its single sub-tree becomes the new search tree root. Else if the key is the child node , then we change the pointer from the root of key to the child of the key.
5. If the key contain both left and right sub-tree replace the key with either largest
element is the left sub-tree or smallest element is the right sub-tree.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
7. Quick sort implementation and it’s efficiency calculation
Aim
To implement quick sort and calculate it’s efficiency
Objective
To arrange the elements using fastest sorting technique quick sort and the time taken to sort the elements.
Exercises
1. Get N elements which are to be sorted, and store it in the array A.
2. Select the element from A[0 ] to A[N-1] for middle. This element is the pivot.
3. Partition the remaining elements into the segments left and right so that no elements in left has a key larger than that of the pivot and no elements in right has a key smaller than that of the pivot.
4. Sort left using quick sort recursively.
5. Sort right using quick sort recursively.
6. Display the sorted array A.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
8. Binary Search implementation
Aim
To implement binary search technique.
Objective
To perform sorting using binary search technique.
Exercises
1. Get N elements and store the elements in the array K in ascending order.
2. Get the element to be searched X.
3. Initialize LOW=1,HIGH=N;
4. Until LOW<= HIGH check whether X
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
9. Graph implementation using arrays and list structure
Aim
Graph implementation using arrays and linear linked list.
Objective
To represent Graph using arrays and linked list
Exercises
1. Construct adjacency matrix, such that it has value one if there exists direct path between two vertices and otherwise zero.
2. For linked representation of graph an array H of head nodes each contains one pointer field INFO.
3. If there exists a direct path between ith head node H[I] and the node X , then
H[I]->INFO=X.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
10. Depth first and Depth first traversal in Graph
Aim
To implement depth first and Breadth first traversal in graphs.
Objective
Depth first and Breadth first traversal implementation in graphs .
Exercises
1. Construct a graph.
2. To traverse a graph in breadth first technique ,label vertex v as reached.
3. Initialize Q to be a queue with only v in it.
4. While Q is not empty, do the following steps
5. Delete a vertex W from the queue
6. Let u be a vertex adjacent from w.
7. While u, if u has not been labeled then add u to the queue label u as reached.
8. Set u = next vertex, that is adjacent from w
9. To traverse a graph in DFS label vertex v as reached.
10. While u is adjacent to v, if u is not reached call DFS recursively
11. Set u as next adjacent vertex of v. Repeat from step 9 till all the nodes are visited.
Software Requirements
Turbo C - 30 nodes.
Hardware Requirements
PC - 30 nos.
EmoticonEmoticon