Pg.
|1
DATA STRUCTURES – PRACTICAL GUIDE
INTRODUCTION TO DATA STRUCTURES LAB
Data structure is structuring and organizing data in efficient
manner so that it can be accessed and modified easily. It determines the logical linkages
between data elements and affects the physical processing of data.
Algorithms presented in this manual are in a form which is machine and language
independent. The prerequisite for this course is a course in programming with experience
using elementary features of C.
List of Practical
1. To implement traversal, insertion, deletion in a linear array.
2. To implement Stacks using arrays.
3. To implement Linear and Circular Queue using arrays.
4. To Implement Singly Linked List.
5. To Implement Doubly Linked List.
6. To Implement Circular Linked List.
7. To Implement Stacks using linked list.
8. To Implement Queues using linked list.
TREE:
9. To Implement Binary Search Tree.
10. To Implement Tree Traversal.
SEARCHING:
11. To Implement Sequential Search.
12. To Implement Binary Search.
SORTINGS:
13. To Implement Insertion sort.
14. To Implement Exchange sort.
15. To Implement Selection sort.
16. To Implement Quick sort.
17. To Implement Shell sort.
18. To Implement Merge sort.
GRAPH:
19.Study of Dijkstra’s Algorithm.
20.Study of Floyd Warshall’s Algorithm.
FORMAT OF THE LAB RECORDS TO BE PREPARED BY THE
STUDENTS
The students are required to maintain the lab records as per the instructions:
The following shall form the basis for practical reporting format for students:
Pg. |2
I. Date
II. Aim
III. Algorithm Or The Procedure to be followed.
IV. Program
V. Output
VI. Viva questions after each section of programs.
MARKING SCHEME
Total Marks: 40
Division of 40 marks is as follows:
1. Regularity: 25
i. Performing program in each turn of the lab [10mks]
ii. Attendance to the lab. class [10mks]
iii. Neat records/sketches [5mks]
2. Viva Voice: 10
3. Presentation: 5
NOTE: For the regularity, marks are awarded to the student out of 10 for each
experiment performed in the lab and at the end the average marks are given out of 25.
LIST OF COURSES
The programs to be done in Data Structures are divided in five sections.
The first section has the programs related to arrays and linked list which are the simplest
data structures. Stacks and queues are to be implemented using arrays as well as linked
list.
The second section includes the programs related to trees. In computer science, a tree is a
widely-used data structure that emulates a tree structure with a set of linked nodes. It is a
special case of a graph. Each node has zero or more child nodes, which are below it in the
tree (by convention, trees grow down, not up as they do in nature). A node that has a child
is called the child's parent node (or ancestor node, or superior). A node has at most one
parent .The topmost node in a tree is called the root node. Being the topmost node, the root
node will not have parents. It is the node at which all operations on the tree begin.
The third section includes the programs of searching. In computer science, a search
algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a
solution to the problem, usually after evaluating a number of possible solutions.
The fourth section has programs on sorting .A sorting algorithm is an algorithm that puts
elements of a list in a certain order. The most used orders are numerical order and
lexicographical order.
Pg. |3
SECTION I
ARRAYS, STACK, QUEUE AND LINKED LIST
DATE: …………………………………………….
TITLE: PROCESSING LINEAR ARRAY: TRAVERSE, INSERTION & DELETION
AIM: TRAVERSAL – The algorithm seeks to process each item in the array list.
ALGORITHM OR PROCEDURE
This algorithm traverses a linear array LA with lower bound LB and upper bound UB.It
traverses LA applying an operation PROCESS to each element of LA.
Step1. Repeat for K = LB to UB
Apply PROCESS to LA[K].
{End of loop}.
Step2. Exit
PROGRAM
Write a program to implement the above procedure, e.g. display array values 1, 2, 3, … 8
OUTPUT:
QUESTIONS:
Pg. |4
1. What control structure is used in the program to traverse an array?
_______________________________________________________________
2. What is the difference between an array and a stack structure?
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
INSERTION:
Here LA is a liner array with N elements and K is a positive integer such that K<=N. This
algorithm inserts an element ITEM into the Kth position in LA.
Step1. Set J := N [Initialize counter]
Step2. Repeat Steps 3 and 4 while J>=K.
Step3. Set LA[J+1] := LA[J]. [Move Jth element downward]
Step4. Set J := J-1. [Decrease counter.]
[End of step 2 loop.]
Step5. Set LA[K] := ITEM. [Insert element.]
Step6. Set N := N+1. [Reset N.]
Step7. EXIT.
PROGRAM:
#include <stdio.h>
int main(){
int array[100], position, c, n, value;
printf(“Enter number of elements in array\n”);
scanf(“%dd”, &n);
printf(“Enter %d elements\n”, n);
for (c=0; c<n; c++)
scanf(“%d”, &array[c]);
printf(“ Enter the position to insert an element\n”);
scanf(“%d”, &position)l
printf(“Enter the value to insert\n”);
scanf(“%d”, &value);
for(c=n-1; c>=position-1; c--)
array[c+1] = array[c];
array[position-1] = value;
printf(“Resultant array is \n”);
for (c=0; c<=n; c++)
printf(“%d\n”, array[c];
return 0;
}
Pg. |5
OUTPUT: Copy down the programs output.
QUESTIONS:
1. Explain the meaning of the following statements from the program above:
a) Printf: _________________________________________________________
b) Scanf: _________________________________________________________
c) “%d” ___________________________________________________________
d) “…\n” __________________________________________________________
2. What is the language used to encode the program above? ____________________
3. What is the array size declared in the program above? _______________________
4. What is an array index and the format of array index?
___________________________________________________________________
___________________________________________________________________
5. What happens when an element is inserted in an array, what is the resultant number
of elements in the array?
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
DELETION FROM A LINEAR ARRAY
AIM: Here LA is a linear array with N elements and k is a positive integer such that K<=N.
This
algorithm deletes the Kth element from LA.
PROCEDURE OR ALGORITHM
Step1. Set ITEM := LA[K].
Step2. Repeat for J = K to N-1:
Set LA[J] := LA[J+1]. [Move J+1st element upward.]
[End of Loop]
Step3. Set N := N-1; [Reset the number N of elements in LA.]
Step4. Exit
PROGRAM
Develop a program to implement the deletion algorithm above
OUTPUT
Pg. |6
QUESTIONS
1. What happens when an element is DELETED in an array, what is the resultant
number of elements in the array?
___________________________________________________________________
___________________________________________________________________
___________________________________________________________________
2. Mention the control structures used in the program.
___________________________________________________________________
___________________________________________________________________
STACKS AND QUEUES
Introduction
A stack is a data structure based on the principle of Last In First Out (LIFO). Stacks are
used extensively at every level of a modern computer system. For example, a modern PC
uses stacks at the architecture level, which are used in the basic design of an operating
system for interrupt handling and operating system function calls.
A collection of items in which only the earliest added item may be accessed is called
QUEUE. Basic operations are add (to the tail) or enqueue and delete (from the head) or
dequeue. Delete returns the item removed. Queue is also known as "first-in, first-out" or
FIFO data structures.
ALGORITHM FOR IMPLEMENTATION OF STACK
DATE: …………………………………
TITLE: PUSH OPERATION
AIM: TOS is top of the stack, the algorithm seek to add element to the top of stack if it is not
filled up.
ALGORITHM
Step1: [Check for stack overflow]
If TOS>=Size-1
Output” Stack Overflow” and exit
Step2: [Increment the pointer value by one]
TOS = TOS+1
Step3: [Perform Insertion]
S[TOS] = Value
Step4: Exit
Pg. |7
PROGRAM
Write a function to illustrate how to push item to stack:
void push(){
int top = -1, stack[MAX];
int val;
if(top= = MAX-1){
printf(“nStack is full!”);
}
else {
printf(“\n Enter element to push:”);
scanf(“%d”, &val);
top = top +1;
stack[top] = val;
}
}
OUTPUT:
Write down the output from the output screen.
QUESTIONS
1. What is the key function of a push command?
___________________________________________________________________
___________________________________________________________________
2. Which programming language is used to implement the stack (push) above
___________________________________________________________________
3. What does the PUSH operation always check before its operation is performed at
least once?
___________________________________________________________________
___________________________________________________________________
Pg. |8
TITLE: POP OPERATION
AIM: The operation removes an item earlier inserted on the stack data structure. It first
checks to see whether or not, the stack is empty.
ALGORITHM
Step1: [Check whether the stack is empty]
If TOS= 0
Output” Stack Underflow” and exit
Step2: [Remove the TOS information]
Value = S[TOS]
TOS = TOS-1
Step3: [Return the former information of the stack]
Return (Value)
PROGRAM
Write a function to demonstrate the POP operation
OUTPUT
QUESTION
1. What does the POP operation do?
___________________________________________________________________
2. What is the condition for the operation to execute at least once?
___________________________________________________________________
___________________________________________________________________
3. What can cause early exit in the algorithm?
___________________________________________________________________
___________________________________________________________________
Pg. |9
ALGORITHM FOR IMPLEMENTATION OF QUEUE
INSERTION IN A QUEUE
Step1: [Check overflow condition]
If Rear>=Size-1
Output” Overflow” and return
Step2: [Increment Rear pointer]
Rear = Rear+1
Step3: [Insert an element]
Q [Rear] = Value
Step4: [Set the Front pointer]
If Front = -1
Front = 0
Step5: Return
DELETION FROM A QUEUE
Step1: [Check underflow condition]
If Front = -1
Output ”Underflow” and return
Step2: [Remove an element]
Value = Q[Front]
Step3: [Check for Empty queue]
If Front = Rear
Front = -1
Rear = -1
Else
Front = Front + 1
Step4: Return (Value)
