DFS LAB PRACTICAL (5,7,8,9)

Practical-5 Program of queue using array

/*Program of queue using array*/
# include<stdio.h>
# define MAX 5

int queue_arr[MAX];
int rear = -1;
int front = -1;

main()
{
int choice;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
insert();
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

insert()
{
int added_item;
if (rear==MAX-1)
printf("Queue Overflow\n");
else
{
if (front==-1)  /*If queue is initially empty */
front=0;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
rear=rear+1;
queue_arr[rear] = added_item ;
}
}/*End of insert()*/

del()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow\n");
return ;
}
else
{
printf("Element deleted from queue is : %d\n", queue_arr[front]);
front=front+1;
}
}/*End of del() */

display()
{
int i;
if (front == -1)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
for(i=front;i<= rear;i++)
printf("%d  ",queue_arr[i]);
printf("\n");
}
}/*End of display() */
---------------------------------------------------------------------------------------------------------

 PRACTICLE 6 - Circular Queue using array

/* Program of circular queue using array*/
# include<stdio.h>
# define MAX 4

int cqueue_arr[MAX];
int front = -1;
int rear = -1;

main()
{
int choice;
clrscr();
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
insert();
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while */
}/*End of main()*/

insert()
{
int added_item;
 // if((front == 0 && rear >= MAX-1) || (front == rear+1))
   // {
     // printf("Queue Overflow \n");
      // return;
       // }
       // if (front == -1)  /*If queue is empty */
       // {
// front = 0;
 // rear = 0;
       // }
       // else
if(rear == MAX-1) /*rear is at last position of queue */
{
rear = 0;
}
else
{
rear = rear+1;
}
if (front == rear)
{
printf("Overflow");
return;
}
printf("Input the element for insertion in queue : ");
scanf("%d", &added_item);
cqueue_arr[rear] = added_item ;
if (front == -1)  /*If queue is empty */
       {
front = 0;
       }
 // rear = 0;
       // }
}/*End of insert()*/

del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",cqueue_arr[front]);
if(front == rear) /* queue has only one element */
{
front = -1;
rear = -1;
}
else
if(front == MAX-1)
front = 0;
else
front = front+1;
}/*End of del() */

display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
}/*End of else */
printf("\n");
}/*End of display() */
------------------------------------------------------------------------------------------------------------

PRACTICLE 7 Singly Link List

#include<iostream.h>
#include<conio.h>
struct SLL
{
int info;
struct SLL *link;
}*first=NULL;
typedef SLL node;
void create_list(int);
void addatbeg(int);
void display();
void del(int);
void addafter(int,int);
void count();
void rev();
void search(int);
void main()
{
int ch,n,m,position,i;
do
{
cout<<"1.Create List\n";
cout<<"2.Add at begining\n";
cout<<"3.Add after \n";
cout<<"4.Delete\n";
cout<<"5.Display\n";
cout<<"6.Count\n";
cout<<"7.Reverse\n";
cout<<"8.Search\n";
cout<<"9.Quit\n";

cout<<"Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1:
cout<<"How many nodes you want : ";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"Enter the element : ";
cin>>m;
create_list(m);
}
break;
case 2:
cout<<"Enter the element : ";
cin>>m;
addatbeg(m);
break;
case 3:
cout<<"Enter the element : ";
cin>>m;
cout<<"Enter the position after which this element is inserted : ";
cin>>position;
addafter(m,position);
break;
case 4:
if(first==NULL)
{
cout<<"List is empty\n";
continue;
}
cout<<"Enter the element for deletion : ";
cin>>m;
del(m);
break;
case 5:
display();
break;
case 6:
count();
break;
case 7:
rev();
break;
case 8:
cout<<"Enter the element to be searched : ";
cin>>m;
search(m);
break;
case 9:
 // exit(0);
default:
cout<<"Wrong choice\n";
}/*End of switch*/
}while(ch<=8);
}/*End of main()*/

void create_list(int data)
{
node *q,*tmp;
tmp= new node;
tmp->info=data;
tmp->link=NULL;

if(first==NULL) /*If list is empty */
first=tmp;
else
{       /*Element inserted at the end */
q=first;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}/*End of create_list()*/

void addatbeg(int data)
{
node *tmp;
tmp=new node;
tmp->info=data;
tmp->link=first;
first=tmp;
}/*End of addatbeg()*/

void addafter(int data,int pos)
{
node *tmp,*q;
int i;
q=first;
for(i=0;i<pos-1;i++)
{
q=q->link;
if(q==NULL)
{
cout<<"There are less than"<<pos<<"elements";
return;
}
}/*End of for*/

tmp=new node;
tmp->link=q->link;
tmp->info=data;
q->link=tmp;
}/*End of addafter()*/

void del(int data)
{
node *tmp,*q,*pred;
if(first->info == data)
{
tmp=first;
first=first->link;
delete(tmp);
return;
}
q=first;
while(q->info!=data)
{
pred=q;
q=q->link;
}
pred->link=q->link;
delete(q);
}

void display()
{
 node *q;
if(first == NULL)
{
cout<<"List is empty\n";
return;
}
q=first;
cout<<"List is :\n";
while(q!=NULL)
{
cout<< q->info;
q=q->link;
}
cout<<endl;
}/*End of display() */

void count()
{
node *q=first;
int cnt=0;
while(q!=NULL)
{
q=q->link;
cnt++;
}
cout<<"Number of elements are "<<cnt;
}

void rev()
{
node *p1,*p2,*p3;
if(first->link==NULL)
return;
p1=first;
p2=p1->link;
p3=p2->link;
p1->link=NULL;
p2->link=p1;
while(p3!=NULL)
{
p1=p2;
p2=p3;
p3=p3->link;
p2->link=p1;
}
first=p2;
}

void search(int data)
{
node *ptr = first;
int pos = 1;
while(ptr!=NULL)
{
if(ptr->info==data)
{
cout<<"Item "<<data<<" found at position" <<pos;
return;
}
ptr = ptr->link;
pos++;
}
if(ptr == NULL)
cout<<"Item "<<data<<" not found in list\n";
}

-----------------------------------------------------------------------------------------------------------

PRACTILE -8 SINGLY CIRCULAR LINK LIST

/* Program of circular linked list*/
# include <stdio.h>
# include <malloc.h>

struct node
{
int info;
struct node *link;
}*last;

main()
{
int choice,n,m,po,i;
last=NULL;
while(1)
{
printf("1.Create List\n");
printf("2.Add at begining\n");
printf("3.Add after \n");
printf("4.Delete\n");
printf("5.Display\n");
printf("6.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("How many nodes you want : ");
scanf("%d",&n);
for(i=0; i < n;i++)
{
printf("Enter the element : ");
scanf("%d",&m);
create_list(m);
}
break;
case 2:
printf("Enter the element : ");
scanf("%d",&m);
addatbeg(m);
break;
case 3:
printf("Enter the element : ");
scanf("%d",&m);
printf("Enter the position after which this element is inserted : ");
scanf("%d",&po);
addafter(m,po);
break;
case 4:
if(last == NULL)
{
printf("List underflow\n");
continue;
}
printf("Enter the number for deletion : ");
scanf("%d",&m);
del(m);
break;
case 5:
display();
break;
case 6:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

create_list(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info = num;

if(last == NULL)
{
last = tmp;
tmp->link = last;
}
else
{
tmp->link = last->link; /*added at the end of list*/
last->link = tmp;
last = tmp;
}
}/*End of create_list()*/

addatbeg(int num)
{
struct node *tmp;
tmp = malloc(sizeof(struct node));
tmp->info = num;
tmp->link = last->link;
last->link = tmp;
}/*End of addatbeg()*/

addafter(int num,int pos)
{

struct node *tmp,*q;
int i;
q = last->link;
for(i=0; i < pos-1; i++)
{
q = q->link;
if(q == last->link)
{
printf("There are less than %d elements\n",pos);
return;
}
}/*End of for*/
tmp = malloc(sizeof(struct node) );
tmp->link = q->link;
tmp->info = num;
q->link = tmp;
if(q==last)    /*Element inserted at the end*/
last=tmp;
}/*End of addafter()*/

del(int num)
{
struct node *tmp,*q;
if( last->link == last && last->info == num)  /*Only one element*/
{
tmp = last;
last = NULL;
free(tmp);
return;
}
q = last->link;
if(q->info == num)
{
tmp = q;
last->link = q->link;
free(tmp);
return;
}
while(q->link != last)
{
if(q->link->info == num)     /*Element deleted in between*/
{
tmp = q->link;
q->link = tmp->link;
free(tmp);
printf("%d deleted\n",num);
return;
}
q = q->link;
}/*End of while*/
if(q->link->info == num)    /*Last element deleted q->link=last*/
{
tmp = q->link;
q->link = last->link;
free(tmp);
last = q;
return;
}
printf("Element %d not found\n",num);
}/*End of del()*/

display()
{
struct node *q;
if(last == NULL)
{
printf("List is empty\n");
return;
}
q = last->link;
printf("List is :\n");
while(q != last)
{
printf("%d ", q->info);
q = q->link;
}
printf("%d\n",last->info);
}/*End of display()*/

----------------------------------------------------------------------------------------------------------

PRACTICLE 9 BINARY TREE

/*Program of insertion and deletion in B tree*/
#include<stdlib.h>
#include<stdio.h>
#define M 5

struct node{
int n; /* n < M No. of keys in node will always less than order of B tree */
int keys[M-1]; /*array of keys*/
struct node *p[M];   /* (n+1 pointers will be in use) */
}*root=NULL;

enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys };

void insert(int key);
void display(struct node *root,int);
void DelNode(int x);
void search(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);

int main()
{
int key;
int choice;
printf("Creation of B tree for node %d\n",M);
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Search\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("Enter the key : ");
scanf("%d",&key);
insert(key);
break;
case 2:
printf("Enter the key : ");
scanf("%d",&key);
DelNode(key);
break;
case 3:
printf("Enter the key : ");
scanf("%d",&key);
search(key);
break;
case 4:
printf("Btree is :\n");
display(root,0);
break;
case 5:
exit(1);
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
return 0;
}/*End of main()*/

void insert(int key)
{
struct node *newnode;
int upKey;
enum KeyStatus value;
value = ins(root, key, &upKey, &newnode);
if (value == Duplicate)
printf("Key already available\n");
if (value == InsertIt)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root->n = 1;
root->keys[0] = upKey;
root->p[0] = uproot;
root->p[1] = newnode;
}/*End of if */
}/*End of insert()*/

enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode)
{
struct node *newPtr, *lastPtr;
int pos, i, n,splitPos;
int newKey, lastKey;
enum KeyStatus value;
if (ptr == NULL)
{
*newnode = NULL;
*upKey = key;
return InsertIt;
}
n = ptr->n;
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
return Duplicate;
value = ins(ptr->p[pos], key, &newKey, &newPtr);
if (value != InsertIt)
return value;
/*If keys in node is less than M-1 where M is order of B tree*/
if (n < M - 1)
{
pos = searchPos(newKey, ptr->keys, n);
/*Shifting the key and pointer right for inserting the new key*/
for (i=n; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
/*Key is inserted at exact location*/
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
++ptr->n; /*incrementing the number of keys in node*/
return Success;
}/*End of if */
/*If keys in nodes are maximum and position of node to be inserted is last*/
if (pos == M - 1)
{
lastKey = newKey;
lastPtr = newPtr;
}
else /*If keys in node are maximum and position of node to be inserted is not last*/
{
lastKey = ptr->keys[M-2];
lastPtr = ptr->p[M-1];
for (i=M-2; i>pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr->keys[pos] = newKey;
ptr->p[pos+1] = newPtr;
}
splitPos = (M - 1)/2;
       (*upKey) = ptr->keys[splitPos];

(*newnode)=malloc(sizeof(struct node));/*Right node after split*/
ptr->n = splitPos; /*No. of keys for left splitted node*/
(*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lastKey;
}
(*newnode)->p[(*newnode)->n] = lastPtr;
return InsertIt;
}/*End of ins()*/

void display(struct node *ptr, int blanks)
{
if (ptr)
{
int i;
for(i=1;i<=blanks;i++)
printf(" ");
for (i=0; i < ptr->n; i++)
printf("%d ",ptr->keys[i]);
printf("\n");
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], blanks+10);
}/*End of if*/
}/*End of display()*/

void search(int key)
{
int pos, i, n;
struct node *ptr = root;
printf("Search path:\n");
while (ptr)
{
n = ptr->n;
for (i=0; i < ptr->n; i++)
printf(" %d",ptr->keys[i]);
printf("\n");
pos = searchPos(key, ptr->keys, n);
if (pos < n && key == ptr->keys[pos])
{
printf("Key %d found in position %d of last dispalyed node\n",key,i);
return;
}
ptr = ptr->p[pos];
}
printf("Key %d is not available\n",key);
}/*End of search()*/

int searchPos(int key, int *key_arr, int n)
{
int pos=0;
while (pos < n && key > key_arr[pos])
pos++;
return pos;
}/*End of searchPos()*/

void DelNode(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf("Key %d is not available\n",key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}/*End of switch*/
}/*End of delnode()*/

enum KeyStatus del(struct node *ptr, int key)
{
int pos, i, pivot, n ,min;
int *key_arr;
enum KeyStatus value;
struct node **p,*lptr,*rptr;

if (ptr == NULL)
return SearchFailure;
/*Assigns values of node*/
n=ptr->n;
key_arr = ptr->keys;
p = ptr->p;
min = (M - 1)/2;/*Minimum number of keys*/

pos = searchPos(key, key_arr, n);
if (p[0] == NULL)
{
if (pos == n || key < key_arr[pos])
return SearchFailure;
/*Shift keys and pointers left*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return  --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}/*End of if */

if (pos < n && key == key_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
while(1)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}/*End of while*/
key_arr[pos] = qp->keys[nkey-1];
qp->keys[nkey - 1] = key;
}/*End of if */
value = del(p[pos], key);
if (value != LessKeys)
return value;

if (pos > 0 && p[pos-1]->n > min)
{
pivot = pos - 1; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pos];
/*Assigns values for right node*/
rptr->p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i--)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = key_arr[pivot];
rptr->p[0] = lptr->p[lptr->n];
key_arr[pivot] = lptr->keys[--lptr->n];
return Success;
}/*End of if */
if (pos<n && p[pos+1]->n > min)
{
pivot = pos; /*pivot for left and right node*/
lptr = p[pivot];
rptr = p[pivot+1];
/*Assigns values for left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
key_arr[pivot] = rptr->keys[0];
lptr->n++;
rptr->n--;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}/*End of for*/
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}/*End of if */

if(pos == n)
pivot = pos-1;
else
pivot = pos;

lptr = p[pivot];
rptr = p[pivot+1];
/*merge right node with left node*/
lptr->keys[lptr->n] = key_arr[pivot];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr); /*Remove right node*/
for (i=pos+1; i < n; i++)
{
key_arr[i-1] = key_arr[i];
p[i] = p[i+1];
}
return  --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}/*End of del()*/