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