# Design, develop and execute a C program to demonstrate how jobs are executed in CPU

using queue. Assume all jobs which are submitted to CPU for execution are stored in a
queue and each job will be executed in first come first serve manner. In this process also
calculate waiting time of a job before being executed by the CPU. An example is
mentioned below.

#include<stdio.h>
#define n 5
void main(){
int queue[n][3],ch=1,front=0,rear=0,i,j=1,x=n, r=0;
int f, wt[n];
printf("Queue using Array");
printf("\n1.Insertion \n2.Deletion \n3.Display \n4.Exit");
while(ch)
{
printf("\nEnter the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(rear==x)
printf("\n Queue is Full");
else
{
printf("\n Enter process id, Burst time and Arrival time \n");
r=rear++;
scanf("%d %d %d",&queue[r][0], &queue[r][1], &queue[r][2]);
}
break;
case 2:
if(front==rear)
{
printf("\n Queue is empty");
}
else
{
f=front++;
printf("\n Executed process ID is %d\n",queue[f][0]);
x++;
if(f==0)
wt[0]=0;
else
wt[f]=wt[f-1]+queue[f-1][1]-queue[f][2];
printf(" WT= %d", wt[f]);
}
break;
case 3:
printf("\n Queue Elements are:\n");
if(front==rear)
printf("\n Queue is Empty");
else
{
printf(" P_Id\tBT\tAT\n");
for(i=front; i<rear; i++)
{
for(j=0;j<3;j++)
printf(" %d\t",queue[i][j]);
printf("\n");
}
break;
case 4:
exit(0);
default:
printf(" Wrong Choice: please see the options");
}} }
}
Output:
Queue using Array
1.Insertion
2.Deletion
3.Display
4.Exit
Enter the Choice:1
Enter process id, Burst time and Arrival time
1271
1045
1250
Enter the Choice:3
Queue Elements are:
P_Id BT AT
1271 1045 1250
Enter the Choice:2
Executed process ID is 1271
WT= 0
Enter the Choice:3
Queue Elements are:

Queue is Empty
Enter the Choice:4
# C program to implement singly linked list.
#include<stdio.h>
#include<stdlib.h>
int c=0;
struct node
{
int data;
struct node *next;
};
struct node *temp,*head=NULL,*newnode,*new1;
void insert()
{
int x;
newnode=(struct node*) malloc(sizeof(struct node));
printf ("\nENTER THE VALUE: ");
scanf ( "%d",&x);
printf("%d",x);
if(head==NULL)
{
newnode->data=x;
head=newnode;
new1= head;
temp=newnode;
}
else
{
newnode->data=x;
temp->next=newnode;
temp=newnode;
newnode->next=NULL;
}
c++;
}
void delet()
{
if(head==0)
{
printf("EMPTY");
}
else
{
printf("\nNO DELETE IS %d\n",head->data);
head=head->next;
new1=head;
c--;
}
}
void display ()
{
printf("\nLINKED LIST\n");
while(new1!=NULL)
{
printf ("%d\n",new1->data);
new1=new1->next;
}
new1=head;
}
void insertF()
{
struct node*newnode;
newnode=(struct node*) malloc(sizeof(struct node));
printf("ENTER THE VALUE: ");
int a;
scanf("%d",&a);
printf("%d\n",a);
newnode->data=a;
newnode->next=head;
new1=head=newnode;
c++;
}

void insertS()
{
if(head==0)
{
printf("EMPTY");
}
else
{
struct node*newnode;
newnode=(struct node*) malloc(sizeof(struct node));
struct node*temp3=head;
printf("\nENTER THE POSITION : ");
int i;
scanf("%d",&i);
printf("%d",i);
int j=1;
for(j=1;j<i-1;j++)
{
temp3=temp3->next;
}
printf("ENTER THE VAL: ");
int a;
scanf("%d",&a);
printf("%d\n",a);
newnode->data=a;
newnode->next=temp3->next;
temp3->next=newnode;
c++;
}
}
void deletel()
{
if(head==0)
{
printf("\nEMPTY\n");
}
else{
struct node*temp4=head;
int i;
for(i=1;i<c-1;i++)
{
temp4=temp4->next;
}
temp4->next=0;
free(temp);
temp=temp4;
new1=head;
c--;
}
}
void delsp()
{
struct node *temp5=head,*temp6=head;
if(head==0)
{
printf("\nEMPTY\n");
}
else {

printf("\nENTER THE POSITION: ");

int pos;
scanf("%d",&pos);
printf ("%d\n",pos);
int i;
for(i=1;i<pos;i++)
{
temp6=temp6->next;
}
for( i=1;i<pos-1;i++)
{
temp5=temp5->next;
}
temp5->next=temp6->next;
c--;
}
}
int ex()
{
printf(" \nI M EXITING ");
return 1;
}
int main()
{
int ch,i=0;
while(i<1)
{
printf("\nMAIN MENU\n\n1.INSERT\n2.DELETE\n3.DISPLAY\n4.INSERT FIRST\n5.INSERT
SPECFIC\n6.DELETE LAST\n7.DELETE SPECIFIC\n8.EXIT\n");
scanf("%d",&ch);
printf("YOUR CHOICE IS: %d",ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
insert();
break;
case 5:
insert();
break;
case 6:
deletel();
break;
case 7:
delsp();
break;
case 8:
i=ex();
break;
}
}
return 0;
}

Output:
MAIN MENU

1.INSERT
2.DELETE
3.DISPLAY
4.INSERT FIRST
5.INSERT SPECFIC
6.DELETE LAST
7.DELETE SPECIFIC
8.EXIT
1
YOUR CHOICE IS: 1
ENTER THE VALUE: 10
10

1
YOUR CHOICE IS: 1
ENTER THE VALUE: 20
20

3
YOUR CHOICE IS: 3
LINKED LIST
10
20

2
YOUR CHOICE IS: 2
NO DELETE IS 10

3
YOUR CHOICE IS: 3
LINKED LIST
20

4
YOUR CHOICE IS: 4
ENTER THE VALUE: 30
30

5
YOUR CHOICE IS: 5
ENTER THE VALUE: 1
1

3
YOUR CHOICE IS: 3
LINKED LIST
20
30
1

6
YOUR CHOICE IS: 6

7
YOUR CHOICE IS: 7
ENTER THE POSITION: 1
1

3
YOUR CHOICE IS: 3
LINKED LIST
20
30

8
YOUR CHOICE IS: 8
I M EXITING
# C program to implement doubly linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Insert at any random
location\n4.Delete from Beginning\n5.Delete from last\n6.Delete the node after the given
data\n7.Search\n8.Show\n9.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
ptr -> next = temp -> next;
temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}

Output:
*********Main Menu*********
Choose one option from the following list ...
===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?

1
Enter Item value10
Node inserted

Enter your choice?

1
Enter Item value20
Node inserted

Enter your choice?

2
Enter value30
node inserted

Enter your choice?

3
Enter the location1
Enter value40
node inserted

Enter your choice?

8
printing values...
20
10
40
30

Enter your choice?

4
node deleted

Enter your choice?

5
node deleted

Enter your choice?

8
printing values...
10
40
0

Enter your choice?

7
Enter item which you want to search?
40
item found at location 2

Enter your choice?

8
printing values...
10
40
0

Enter your choice?

9
# C program to construct binary search tree (BST)

// Binary Search Tree operations in C

#include <stdio.h>

#include <stdlib.h>

struct node {

int key;

struct node *left, *right;

};

// Create a node

struct node *newNode(int item) {

struct node *temp = (struct node *)malloc(sizeof(struct node));

temp->key = item;

temp->left = temp->right = NULL;

return temp;

// Inorder Traversal

void inorder(struct node *root) {

if (root != NULL) {

// Traverse left

inorder(root->left);

// Traverse root

printf("%d -> ", root->key);

// Traverse right

inorder(root->right);
}

// Insert a node

struct node *insert(struct node *node, int key) {

// Return a new node if the tree is empty

if (node == NULL) return newNode(key);

// Traverse to the right place and insert the node

if (key < node->key)

node->left = insert(node->left, key);

else

node->right = insert(node->right, key);

return node;

// Find the inorder successor

struct node *minValueNode(struct node *node) {

struct node *current = node;

// Find the leftmost leaf

while (current && current->left != NULL)

current = current->left;

return current;

// Deleting a node

struct node *deleteNode(struct node *root, int key) {

// Return if the tree is empty

struct node *temp;

if (root == NULL) return root;

// Find the node to be deleted

if (key < root->key)

root->left = deleteNode(root->left, key);

else if (key > root->key)

root->right = deleteNode(root->right, key);

else {

// If the node is with only one child or no child

if (root->left == NULL) {

struct node *temp = root->right;

free(root);

return temp;

} else if (root->right == NULL) {

struct node *temp = root->left;

free(root);

return temp;

// If the node has two children

// struct node

temp = minValueNode(root->right);

// Place the inorder successor in position of the node to be deleted

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);

}
return root;

// Driver code

void main() {

struct node *root = NULL;

clrscr();

root = insert(root, 8);

root = insert(root, 3);

root = insert(root, 1);

root = insert(root, 6);

root = insert(root, 7);

root = insert(root, 10);

root = insert(root, 14);

root = insert(root, 4);

printf("Inorder traversal: ");

inorder(root);

printf("\nAfter deleting 10\n");

root = deleteNode(root, 10);

printf("Inorder traversal: ");

inorder(root);

getch();

Output:
OPERATIONS ---
1 - Insert an element into tree
2 - Delete an element from the tree
3 - Inorder Traversal
4 - Preorder Traversal
5 - Postorder Traversal
6 - Exit
Enter your choice : 1
Enter data of node to be inserted : 10
Enter your choice : 5
10 ->
Enter your choice : 1
Enter data of node to be inserted : 4
Enter your choice : 1
Enter data of node to be inserted : 6
Enter your choice : 1
Enter data of node to be inserted : 8
Enter your choice : 3
4 -> 6 -> 8 -> 10 ->
Enter your choice : 4
10 -> 4 -> 6 -> 8 ->
Enter your choice : 5
8 -> 6 -> 4 -> 10 ->
Enter your choice : 2
Enter the data to be deleted : 4
Enter your choice : 3
6 -> 8 -> 10 ->
Enter your choice :
# C program to implement linear search and binary search.
Program A
#include <stdio.h>
void main()
{
int array[100], search, c, n;
int count=0;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
printf("Enter a number to search\n");
scanf("%d", &search);
for (c = 0; c < n; c++)
{
if (array[c] == search)
{
printf("%d is present at location %d.\n", search, c+1);
count++;
}
}
if (count == 0)
printf("%d isn't present in the array.\n", search);
}

Output:
Enter number of elements in array
5
Enter 5 integer(s)
10 20 30 40 50
Enter a number to search
30
30 is present at location 3.
Program B

#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x, int i)
{
while (l <= r) {
int m = l + (r - l) / 2;
i++;
if (arr[m] == x){
printf("\nTotal iterations: %d\n",i);
return m;
}
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
void main()
{
int arr[100],n,c;
int it=0;
int num, result;
printf("Enter number of elements in array\n");
scanf("%d", &n);
printf("Enter %d integer(s)\n", n);
for (c = 0; c < n; c++)
scanf("%d", &arr[c]);
printf("Enter a number to search\n");
scanf("%d", &num);
result = binarySearch(arr, 0, n - 1, num, it);
(result == -1) ? printf("Element is not present"" in array"):
printf("Element is present at ""index %d",result);
}

Output:
Enter number of elements in array
10
Enter 10 integer(s)
5 10 15 20 25 30 35 40 45 50
Enter a number to search
35
Total iterations: 4
Element is present at index 6
# C program t implement insertion and selection sort.

#include<stdio.h>
#include<stdlib.h>
//function prototypes
void selection(int *,int);
void insertion(int *,int);
int main()
{
int count=0; //size of array
int choice=0,ch=0; //variables used to store user choice
int i=0; //loop variable
int list[100];
clrscr();
printf("Enter no of Elements: ");
scanf("%d",&count);
//filling in the array
for(i=0;i<count;i++)
{
printf("Enter element %d: ",i+1);
scanf("%d",&list[i]);
}
//prints the list
printf("\nNumbers entered: ");
for(i=0;i<count;i++)
printf("%d,",list[i]);
printf("\n");

//Creates Menu for the user

do{
printf("*******Menu:*******\n\n");
printf("1.Inserton sort\n2.Selection Sort\n3.Exit\nYour choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: //performs insertion sort
insertion(list,count);
break;
case 2: //performs selection sort
selection(list,count);
break;
case 3: return 0;
default: printf("Invalid option\nRetry: ");
break;
}
printf("Do you want to continue(press 1 to continue any other number to exit): ");
scanf("%d",&ch);
} while(ch==1);
return 0;
}
void insertion(int *list,int n)
{
int temp;
int i=0,j=0;

for(i=1;i<n;i++)
{
temp=list[i];
j=i-1;
while((j>=0)&&(list[j]>temp))
{
list[j+1]=list[j];
j--;
}
list[j+1]=temp;
}

printf("Sorted list is: ");

for(i=0;i<n;i++)
{
printf("%d,",list[i]);
}

printf("\n");
}
void selection(int *list,int n)
{
int i;
int j,min;
int k;
for(j=0;j<n-1;j++)
{
min=list[j];
k=j;
for(i=j+1;i<n;i++)
{
if(list[i]<min)
{
min=list[i];
k=i;
}
}

list[k]=list[j];
list[j]=min;
}
printf("Sorted list is:");
for(i=0;i<n;i++)
{
printf("%d,",list[i]);
}
printf("\n");
}

Output:
Enter no of Elements: 4

Enter element 1: 5

Enter element 2: 6

Enter element 3: 9

Enter element 4: 7

Numbers entered: 5,6,9,7,

*******Menu:*******

1.Inserton sort

2.Selection Sort

3.Exit

Your choice: 1
Sorted list is: 5,6,7,9,

Do you want to continue(press 1 to continue any other number to exit):

*******Menu:*******

1.Inserton sort

2.Selection Sort

3.Exit

Your choice: 2

Sorted list is:5,6,7,9,

Do you want to continue(press 1 to continue any other number to exit): 1

*******Menu:*******

1.Inserton sort

2.Selection Sort

3.Exit

Your choice: 3