Practical NO: 01.

Array element add/delete operation

Flow chart to delete array element:

Delete Algorithm:
Let A [Max] is an array and size specifies length of array.
1. Accept the location into loc where element to be deleted.
2. Repeat for i=loc+l to size-l.
3. Set a[i-1]=a[i].
4. Set size=size-1.

Flow chart to add array element:

Insert Algorithm : -
Let A [Max] is an array and size specifies length of an array.
 1. Accept the item to be inserted into element.
2. Accept the location into loc where element to be inserted.
3. Repeat for i=size-l down to loc.
4. Set a[i+l]=a[i].
5. Set size=size+1.
6. Set a[oc]=element.

Program : Menu driven program for array to create, insert, delete and
display elements in array.

#include <stdio.h>
#include <process.h>
#define MAX 100 //l(maximum number of elements that can be stored
int num=0,a[MAX];
void create();
void insert();
void delete();
void display();
int main()
{
int ch;
setbuf(stdout, NULL) ; / /Turn off buffering of stdout
Printf ( “*** Array Menu ***” );
printf ( " \n1.Create \n 2.Insert \n 3.Delete \n 4.Display \n 5.Exit " );
while(1) //infinite loop
{

printf("\n Enter yourchoice(1.Cneate2.Insert3.De1ete4.Display5.Exit):\n");

scanf( "%d" &ch);
switch ( ch )
{
case 1: create( );
break;
case 2: Insert( );
break;
case 3: delete( );
break;
case 4: display( );
break;
case 5: exit(0);
default: printf("\n Wrong Choice!! ");
}}
return 0;
}
void create( )
{
int i;
pnintf( "Enter the value of n: \n" );
scanf( "%d", &num);
printf( "Enter n elements: \n" );
for (i = 0; i < num; i++)
scanf("%d", &a[i]);
}
void insert( )
{
int i,element,index;
printf("Enter the element to be inserted :\n")j
scanf("%d",&element);
printf("Enter the index after which element to be inserted:\n");
scanf("%d", &index);
// Make space at the specified location
for (i = num-l; i >= index; i--)
{
a[i+1] = a[i];
}
num++; // No of elements increased by 1
a[index] = element;
}

void delete( )
{
int i,index;
printf("Enter index of the element to be deleted :\n");
scanf("%d", &index);
for (i = index+1; i <= num-l; i++)
{
a[i-1] = a[i];
}
num--; // No of elements reduced by 1
}

void display()
{
int i;
printf ( *** Elements in Array***\n" );
for(i=0; i<num; i++)
printf("%d "a[i] );
}

Practical No: 02.

Linear Search.
Linear Search Algorithm:

- Let Array[Max] is array , N is size of array and item is an element to be

searched.
- Repeat for i=0 to N-1.
If Array[i]==item.
print index and return from loop.
- if i==N.
Print "element not found".
Program for linear search.

#include <stdio.h>
#include <conio.h>
int main()
{
int a[100], find, i, n;
setbuf(stdout, NULL); / /Turn off buffering of stdout
printf("Enter the size of array: \n");
scanf("%d", &n);
printf("Enter n elements: \n");
for (i = 0 i < n; i++)
scanf("%d", &a[i]);
printf("Enter value to be search \n “);
scanf("%d", &find);
for (i = 0; i < n; i++)
{
if (a[i] == find) /* if the key element is found */
{
printf("Element found at index %d= \n”,i);
break;
}
}
if (i == n)
printf("Element Not found in Array”);
return 0;
}
Advantages of Linear Search:

1. It is a very simple method.

2. Efficient for only small list.
3. Better to use for unsorted data.
4. It does not require the data to be ordered.
5. It does not require any additional data structure other than array.
6. Suitable for storage structure, which do not support direct access to data.

Disadvantages of Linear Search:

1. If number of elements in Array is very high, this method is very inefficient and slow.

Practical No: 03.

Binary Search.
Binary Search Algorithm:

- Let Array[Max] is array , N is size of array and item is an element to be

searched.

1. Set first=0, Last=n, mid=(first+last)/2

2. Repeat step 3 and 4 while first<=last and Array[mid]!=item
3. If item > Array[mid] then
set first=mid+1
EIse if item==Arraylmid] then
print "item found"
Else set Last=mid-1
4. Set mid=(first + last)/2
5. If first>last then print item not found.
Program for Binary search.

#include <stdio.h>
#include <conio.h>
int main()
{
int first, last, middle, n, i, find, a[100];
printf(“Enter the size of array: \n”);
scanf (“%d”,&n);
printf("Enter n elements in Ascending order: \n”);
for (i = 0; i < n; i++)
scanf(“%d"&a[i]);
printf (“Enten value to be seanch : \n”);
scanf (“%d", &find);
first = 0;
last=n-1;
middle = (first+last)/2;
while (first <= last)
{
if (a[middle] < find)
first= middle+1;
else if (a[middle] == find)
{
printf(,,Element found at index Xd.\n,,,middle);
break;
}
else
last= middle-1;
middle = (first + last)/2;
}
if (first > tast)
pnintf (“Element Not found in the list.”);
return 0;
}
Output:
Enter the size of array: 5
Enter n elements in Ascending order: 1 4 7 9 11
Enter value to be search: 7
Element found at index 2

Advantages of Binary Search :

1. Binary search is suitable for sorted data.

2. It is efficient for large list.
3. It is suitable for storage structures that support direct access.

Disadvantages of Binary Search : -

1. It is not suitable for unsorted data.
2. Binary search is inefficient for small lists.
 Practical No: 04.
Bubble Sort.

- Bubble Sort Algorithm:

- Let Array[Max] is array, N is size of array.

1. Repeat for pass=1to N-L.

2. Repeat for j=0 to N-pass-1.
3. If array[j]> array [j+1].
Interchange a[j] with a[j+1].
4. Print sorted Array.

Program for bubble sort: -

#include <stdio.h>
int main(void)
{
int a[50], n, pass, i,j, temp = 0;
printf("Enter the value of n:\n");
scanf("%d", &n);
printf("Enter n elements: \n");
for (i = 0; i < n; i++)
{
scanf("%d", &aIi]);
}
//computation of bubble sort
for (pass = 1; pass <= n-1; pass++)
{
for (j=0; j<n-pass; j++)
{
if (a[j] > a[j+1]
 {
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
printf("The sorted array after Bubble sort is:\n")j
for (i * 0j i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
Output:
Enter the value of n:6
Enter n elements:75 16 80 10 18 6
The sorted array after Bubble sort is:6 l0 16 18 75 80

Practical No: 05.

Selection Sort.

Selection Sort Algorithm:

1. Let Array[Max] is integer array, N is size of array.
2. Repeat for i= 0 to N-2.
3. Set min =Array[i] and loc=i.
4. Repeat for j= i+1 to N-1.
5. IF MIN>Array[j]then.
6. set MIN= [j] and loc= j;
7. Interchange Array [i] with Array[loc]

Program for selection sort : -

#include <stdio.h>
#include <stdlib.h>
int maino
{
int i, j, n, loc,temp,min, a[30];
printf("Enter the size of array:\n");
scanf( "%d" , &n) ;
printf("Enter n elements : \n") j
for(i=0; i<n; i++)
{
scanf( "%d", &a [i] );
}

for(i=0; i<n-1; i++) //computation of selection sort

{
min=a[i];
loc=i;
for(j=i+1;j<n; j++)
{
if(min>a[j])
{
min=a[j];
loc=j;
 }
}
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
printf("The sorted array after Selection sort “);
for(i=0; i<n; i++)
{
printf("%d " a[i]);
}
return 0;
}
Output:
Enter the size of array: 5
Enter n elements: 5 7 1 4 2
The sorted array after Selection sort is: 1 2 4 5 7

Flow Chart : -

Practical No: 06.

Insertion Sort.
 Insertion Sort Algorithm:
Let Array[Max] is integer array, N is size of array.
Repeat for i=1to N-1.
Set temp=Array[i] and j=i-1.
While j>=0 and Array[j]>temp do.
Array[j+1]=Array[j].
 j=j-7.
Array[j+1]=temp.

Flow Chart : -

Program for insertion sort : -

#include <stdio.h>
#include <stdlib.h>
int main()
{
int i,j,n,temp,a[30];
printf("Enter the size of array:\n,,);
scanf( "%d ", &n);
printf("Enter n elements: \n");
for(i=0; i<n; i++)
{
scanf( "%d ", &a [i] ) ;
}
//computation of insertion sort
for(i=1; i<=n-1; i++)
{
temp=a[i];
j=i-1;
while( (temp <a [j])&&(j >=0))
{
a[j+1]=a[j]; / /moves element forward
j=j -1;
}
a[j+1]=temp; //insert element in proper place
}
printf("The sorted array after Insertion sort is:\n");
for(i=0; i<n; i++)
{
printf("%d ",a[i] );
}
return 0;
}
Output:
Enter the size of array: 5
Enter n elements: 10 1 7 3 9
The sorted array after Insertion sort is: 1 3 7 9 10.

Comparison between sorting algorithms : -

Algorithm Best Average Worst Time Worst Space Stability

Time Time Complexity Complexity
Complexi Complexit
ty y
Bubble Sort O(n) O(n2) O(n2) O(1) Yes
Selection Sort O(n2) O(n2) O(n2) O(1) No
Insertion Sort O(n) O(n2) O(n2) O(1) yes
Quick Sort O(log n) O(log n) O(n2) O(log n) No
Merge Sort O(log n) O(log n) O(log n) O(n) yes

Practical No: 07.

Push and Pop operation on Stack.

PUSH: The process of adding a new element to the top of stack is called push operation. After every push operation the
top is incremented by one.

Algorithm :
PUSH (stack, TOP, size, item)
Step 1: Check for stack overflow,
If TOP > size
message "stack overflow”
return
Step 2: Set the position of TOP pointer
 Set TOP = TOP + 1
Step 3: Apply insertion
stack [TOP] = item
Step 4: Exit
1. POP: The process of deleting an element from the top of stack is called pop operation. After every POP
operation the top pointer of the stack is decremented by one.

Algorithm:
POP (Stack, TOP, size, item)
Step 1: Check underflow condition,
If TOP = -1 then
message "underflow”
exit
Step 2: Delete the TOP element.
Set item = Stack [TOP].
Step 3: Set the value of TOP
Set TOP = TOP - 1
Step 4: Return.

Program for stack push and pop operation using array : -

#include <stdio.h>
#include <stdlib.h>
#include<process. h>
#define MAX 5 //Maximun number of elements that can be stored
int top=-1,stack[MAX];
void push();
void pop();
void display();
int main()
{
int ch;
printf("\n *** Stack Menu ***”);
printf (" \n1 . Push\n2 . Pop\n3. Display\n4. Exit" );
while(1) //infinite loop
{
printf ("\n Enter your choice(1-4) : ");
scanf( "%d", &ch );

switch ( ch )
{
case 1; push();
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
default: printf(“\n Wrong Choice!!”);
}

}
return 0;
}

void push( )
{
int val;
if(top== MAX-1);
printf( "\n Stack is full ! !'” );
else
{
printf ( "\n Enter element to push :”);
scanf( "%d ", &val ); I
top= top+1;
stack[top ] = val;
}
}
void pop( )
{
if(toP ==-1);
printf( "\n Stack is Empty ! “);
else
{
printf("\n Deleted element is %d", stack[top]); //delete top element
top= top-1;
}
}

void display()
{
int i;
if(top==-1);
 printf("\n Stack is Empty!!”);
else
{
printf( " \n** Elements in Stack**. \n” );
for(i=top; i>=0; i- - )
printf( "%d\n", stack[i]);
}
Output:
*** Stack Menu *x*
1.Push
2.Pop
3.Display
4.Exit
Enter your choice(1-4) :1
Enter element to push:10
Enter your choice(1-a):1
Enter element to push:20
Enter your choice(1-4) :1
Enter element to push:30
Enter your choice(1-4):3
*** Elements in stack***.
30
20
10
Enter your choice(1-4) :2
Deleted element is 30
Enter your choice(1-4):3
*** Elements in stack***.
20
10
Practical No: 08.
Insert and Delete operation on Queue using array.

Enqueue /insertion or addition of element in queue.

Algorithm:
Let queue [Max] is an array for implementation of queue. Let front and queue initialize to -1.
1 if rear=MAX-l then //[check queue is overflow]
2. print queue is overflow
3. else
4. if front = -1 then set front to 0
5. set rear = rear + l
6. Set Queue[Rear] = Item //Insert element at rear position of queue.

Dequeue /deletion or removal of element from a queue.

Dequeue Algorithm:
Let queue [Max] is an array for implementation of queue. Let front and queue initialize to -1.
1. If front = -1 then //[check queue is underflow]
2. Print queue is underflow
3. Else
4. Set value = Queue [front] //Delete the element which is at the front of queue
5. Set front = front +1
6. If front > rear then set both front and rear to -1
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();

int queue[SIZE], front = -1, rear = -1;

void main()
{
int value, choice;
clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",queue[i]);
}
}
 Practical No: 09.
Insert and Delete operation on Circular Queue using array.

Circular Queue Representation Using Array : -

Menu driven code for circular queue, (enqueue and dequeue).

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 5
Int queue[MAX],front=-l,rear=-l;
void enqueue();
void dequeue();
void display();
int main()
{
int ch;
setbuf(stdout, NULL); //turn off buffering of stdout
printf("\n*** Circular Queue Menu ***");
printf("\nl.Insertion \n2.Deletion \n3.Display \n4.Exit");
while(l)
{
printf("\nEnter the Choice(l-4):" ) ;
scanf("%d",&ch);
switch(ch)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
 case 4:
exit(0);
default:
printf("\nWrong Choice!!");
}
}
return 0;
}
void enqueue()
{
if((front == rear + 1) || (front == 0 && rear == MAX-1))
printf("\n Queue is Full!!");

else
{
if(front = = -1)
front=0;

rear=(rear+l)%MAX;
printf("\n Enter element to Insert:");
scanf("%d",&queue[rear]);
}
printf("\nAfter Insertion position of Front=%d and Rear=%d", front, rear);
}

void dequeue()

if(front= =-l)
printf("\n Queue is Empty!!");
else
{

printf("\n Deleted Element is %d",queue[front]);

if (front = = rear)
{
front = -1;
rear = -1;
}
else
front=(front +1)%MAX;
}
printf("\n After Deletion position of Front=%d and Rear=%d ",front, rear);
}
void display()
{
int i;
if(rear = = -l)
printf("\n Queue is Empty!!");
else
{
 printf("\n**** Elements in Queue*****.\n"); for(i=front;
i!= rear; i=(i+l)%MAX)
printf("%d ", queue[i]);
printf("%d ", queue[i]);
}
}
Sr.: Stack Queue
1. A stack is a linear structure in which element A queue is a linear structure in which
may be added or deleted one end only called insertion takes place at one end called rear
the TOP. and deletion takes place at other end called
front.
2. Stack is LIFO (Last-In-First-Out). Queue is FIFO (First-In-First-Out).
3. Stack has a pointer variable TOP for Queue has two pointer variables front and
operations. rear for operations.
4. Top moves in both directions. Hence, vacant Front and rear move in one direction only.
positions are reused.
5 The elements are popped in the reverse order The elements are removed in the same order
in which they were pushed. in which they were added.
6. In computer system stack is used for In computer system queue is used for time
procedure calls or for interrupt handling. sharing system.
7. Operations on the stack are PUSH and POP. Operations on the queue are ENQUEUE and
DEQUEUE.
8. Stacks are visualized as vertical collections. Queues are visualized as horizontal
collections.
9. For examples: Stack of dishes, disks etc. For examples: People waiting in line at banks
and bus stops.

Practical No: 10.

Operation on Single Linked List.
Flow chart to insert node:
Algorithm to insert a node at start : -
1. Create New Node
2. Fill Data into “Data Field“
3. Make it’s “Pointer” or “Next Field” as NULL
4. Attach This newly Created node to Start
5. Make newnode as Starting node

Program to insert node at start:

void insert_at_beg()
{
struct node *new_node,*current;
new_node=(struct node *)malloc(sizeof(struct node));
if(new_node == NULL)
printf("nFailed to Allocate Memory");
printf("nEnter the data : ");
scanf("%d",&new_node->data);
new_node->next=NULL;

if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{
new_node->next=start;
start=new_node;
}
}

Algorithm to delete last node :

1. Traverse upto last
2. Declare one temp node and assign last node to temp
3. Move the last node to its previous nodeand make its pointer as NULL
4. Delete the temp node using free() function.

Program to delete last node:

void LastNodeDeletion()
{
struct node *Last, *preNode;
if(stnode == NULL)
{
printf(" There is no element in the list.");
}
else
{
Last = stnode;
preNode = stnode;
/* Traverse to the last node of the list*/
while(Last->nextptr != NULL)
{
preNode = Last;
Last = Last->nextptr;
 }
if(Last == stnode)
{
stnode = NULL;
}
else
{
/* Disconnects the link of second last node with last node */
preNode->nextptr = NULL;
}

/* Delete the last node */

free(Last);
}
}

Flow chart to delete node:

Practical No: 11.

Operation on Circular Linked List.

Create
First check the status of last pointer, if it is NULL means, we are inserting first node in the list and that new node (tmp)
will be the Iast node in the list as shown in Fig
void create()
{
struct node *tmp;
printf("Enter element”);
scanf("%d", &data);
tmp=malloc(sizeof(struct node));
tmp->info=data;
if(last==NULL)
{
last=tmp;
tmp->link=last;
}
}

Inserting Nodes at beginning in Circular Linked list : -

 Let tmp is the node which we want to insert at beginning of iist. Store the address of (Last->link) in the
tmp->link. And update first node(last->link) as shown in Fig above.
 C code is given below:

struct node *tmp;

printf("Enter element :\n");
scanf("%d", &data);
tmp=malloc(sizeof(struct node));
tmp->info=data;
tmp->link=last->link;
last->link=tmp;
display();

Deleting a node from the End :

void del_at_end()
{
struct node *q;
q=last->link;
if(last==NULL)
{
printf("List is empty");
}
if(last->link==last) //single node in the list
{
last=NULL;
free(last);
printf("List is empty!!");
return;
}
while(q->link!=last)//traverse upto Last pointer
{
q=q->link;
}
q->link=last->link;
free(last);
last=q;
printf("Last element deleted!!\n");
display();
return;
}

Practical No: 12.

Traversing on Binary Search Tree.

Algorithm for Inorder Traversal of Binary Search Tree:

Step 1 : Repeat step 2 to 4
Step 2 : while tree! =NULL.
Step 3 : INORDER (TREE->LEFT)
Step 4 : Write "Tree ->Data"
Step 5: INORDER (Tree->Right)
[END of while]
Step 6 : END

Algorithm for Preorder Traversal of Binary Search Tree:

Step 1 : Repeat step 2 to 4
Step 2 : while tree!=NULL.
Step 3 : Write "Tree ->Data"
Step 4 : Preorder (Tree->Left)
Step 5 : Preorder (Tree->Right)
[END of while]
Step 6 : END.

Algorithm for Postorder Traversal of Binary Search Tree:

Step 1 : Repeat step 2 to 4

Step 2: while tree! = NULL.
Step 3: POSTORDER (TREE->LEFT)
Step 4 : POSTORDER (Tree->Right)
Step 5 : Write "Tree ->Data"
[END of while]
Step 6: END.

Program : Menu driven program for binary search tree creation and tree traversing. [Recursive]

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node
{
int data;
struct node *right;
struct node *left;
};

struct node *Create(struct node *, int);

void Inorder(struct node *);
void Preorder(struct node *);
void Postorder(struct node *);
int main()
{
struct node *root = NULL;
setbuf(stdout, NULL);
int choice, item, n, i;
printf("\n*** Binary Search Tree ***\n");
printf("\nl. Creation of BST");
printf("\n2. Traverse in Inorder");
printf("\n3. Traverse in Preorder");
printf("\n4. Traverse in Postorder");
printf("\n5. Exit\n");
while(l)
{
printf("\nEnter Your Choice :(1.Create 2.Inorder 3.Preorder 4.Postorder
5.Exit)\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
root = NULL;
printf("Enter number of nodes:\n");
scanf("%d",&n);
for(i = 1; i <= n; i++)
{
printf("\n Enter data for node %d : ", i);
scanf("%d", &item);
root = Create(root,item);
}
break;
case 2:
Inorder(root);
break;
case 3:
Preorder(root);
Break;
case 4:
Postorder(root);
break;
case 5:
exit(0);
default:
printf("Wrong Choice !!\n");
}
}
return 0;
}
struct node *Create(struct node *root, int item)
{
if(root == NULL)
{
 root = (struct node *)malloc(sizeof(struct node));
root->left = root->right = NULL;
root->data = item;
return root;
}
else
{
if(item < root->data )
root->left = Create(root->left,item); //recursive function call
elseif(item > root->data )
root->right = Create(root->right,item);
else
printf(" Duplicate Element is Not Allowed !!!");
return(root);
}
}
void Inorder(struct node *root)
{
if( root != NULL)
{
Inorder(root->left); //recursive function call
printf("%d ",root->data);
Inorder(root->right);
}
}
void Preorder(struct node *root)
{
if( root != NULL)
{
printf("%d ",root->data);
Preorder(root->left);//recursive function call
Preorder(root->right);
}
}
void Postorder(struct node *root)
{
if( root != NULL)
{
Postorder(root->left);//recursive function call
Postorder(root->right);
printf("%d ",root->data);
}
}