Code on Dynamic Memory Allocation

/*Example program for reallocation*/
#include< stdio.h >
#include< stdlib.h >
define NULL 0
main()
{
char *buffer;
/*Allocating memory*/
if((buffer=(char *) malloc(10))==NULL)
{
printf(“Malloc failed\n”);
exit(1);
}
printf(“Buffer of size %d created \n,_msize(buffer));
strcpy(buffer,”Bangalore”);
printf(“\nBuffer contains:%s\n”,buffer);
/*Reallocation*/
if((buffer=(char *)realloc(buffer,15))==NULL)
{
printf(“Reallocation failed\n”);
exit(1);
}
printf(“\nBuffer size modified.\n”);
printf(“\nBuffer still contains: %s\n”,buffer);
strcpy(buffer,”Mysore”);
printf(“\nBuffer now contains:%s\n”,buffer);
/*freeing memory*/
free(buffer);
}

DYNAMIC MEOMORY ALLOCATION

C Programming - Dynamic Memory allocation

1. Dynamic Memory Allocation,
2. Dynamic Memory Allocation.
3. Memory Allocations Process,
4. Allocating a block of memory,
5. Allocating multiple blocks of memory,
6. Releasing the used.
7. Alter the size of allocated memory.

In programming we may come across situations where we may have to deal with data, which is dynamic in nature. The number of data items may change during the executions of a program. The number of customers in a queue can increase or decrease during the process at any time. When the list grows we need to allocate more memory space to accommodate additional data items. Such situations can be handled move easily by using dynamic techniques. Dynamic data items at run time, thus optimizing file usage of storage space.

1.Dynamic memory allocation:

The process of allocating memory at run time is known as dynamic memory allocation. Although c does not inherently have this facility there are four library routines which allow this function.

Many languages permit a programmer to specify an array size at run time. Such languages have the ability to calculate and assign during executions, the memory space required by the variables in the program. But c inherently does not have this facility but supports with memory management functions, which can be used to allocate and free memory during the program execution. The following functions are used in c for purpose of memory management.

Functions


2. Memory allocations process:
According to the conceptual view the program instructions and global and static variable in a permanent storage area and local area variables are stored in stacks. The memory space that is located between these two regions in available for dynamic allocation during the execution of the program. The free memory region is called the heap. The size of heap keeps changing when program is executed due to creation and death of variables that are local for functions and blocks. Therefore it is possible to encounter memory overflow during dynamic allocation process. In such situations, the memory allocation functions mentioned above will return a null pointer.

3. Allocating a block of memory:
A block mf memory may be allocated using the function malloc. The malloc function reserves a block of memory of specified size and returns a pointer of type void. This means that we can assign it to any type of pointer. It takes the following form:

ptr=(cast-type*)malloc(byte-size);

ptr is a pointer of type cast-type the malloc returns a pointer (of cast type) to an area of memory with size byte-size.

Example:

x=(int*)malloc(100*sizeof(int));

On successful execution of this statement a memory equivalent to 100 times the area of int bytes is reserved and the address of the first byte of memory allocated is assigned to the pointer x of type int

4.Allocating multiple blocks of memory:
Calloc is another memory allocation function that is normally used to request multiple blocks of storage each of the same size and then sets all bytes to zero. The general form of calloc is:

ptr=(cast-type*) calloc(n,elem-size);

The above statement allocates contiguous space for n blocks each size of elements size bytes. All bytes are initialized to zero and a pointer to the first byte of the allocated region is returned. If there is not enough space a null pointer is returned.

5. Releasing the used space:
Compile time storage of a variable is allocated and released by the system in accordance with its storage class. With the dynamic runtime allocation, it is our responsibility to release the space when it is not required. The release of storage space becomes important when the storage is limited. When we no longer need the data we stored in a block of memory and we do not intend to use that block for storing any other information, we may release that block of memory for future use, using the free function.

free(ptr);

ptr is a pointer that has been created by using malloc or calloc.

6. To alter the size of allocated memory:
The memory allocated by using calloc or malloc might be insufficient or excess sometimes in both the situations we can change the memory size already allocated with the help of the function realloc. This process is called reallocation of memory. The general statement of reallocation of memory is :

REFER BLOGS FOR ALL SUBJECTS

http://jayashree-ds.blogspot.com/
http://jayashree-webprogramming.blogspot.com/
http://jayashree-sqlplsql.blogspot.com/
http://jayashree-dbms.blogspot.com/
http://cprogramming-jayashree.blogspot.com/
http://bca-3sem-vb.blogspot.com/
http://bca-3sem-se.blogspot.com/
http://bca-3sem-cpp.blogspot.com/

lAB PROGRAMS "PART A" And "PART B"

Data Structures LAB PROGRAMS FOR BCA 2^nd SEM

Part A:

1)//P1 Use a recursive function to find GCD of two numbers.

#include

int main()

{

int n1,n2,gcd;

printf("\nEnter two numbers: ");

scanf("%d %d",&n1,&n2);

gcd=findgcd(n1,n2);

printf("\nGCD of %d and %d is: %d",n1,n2,gcd);

return 0;

}

int findgcd(int x,int y)

{

while(x!=y)

{

if(x>y)

return findgcd(x-y,y);

else

return findgcd(x,y-x);

}

return x;

}

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

2)//P2 Use a recursive function to find Fibonacci series.

#include

#include

int y;

fib(int n)

{

      if(n==1 || n==0)

      return n;

      y=fib(n-1)+fib(n-2);

      return y;

}

main()

{

int a,r;

clrscr();

printf("Enter any number : ");

scanf("%d",&a);

r=fib(a);

printf("The no. at position %d is %d",a,r);

getch();

return 0;

}

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

3)//P3.Use pointers to find the length of a string and to concatinate the string

#include

#include

void stcat(char *str1, char *str2);

int stlen(char *str);

void main()

{

char *str1, *str2,*str;

int i=0;

clrscr();

printf("\n\n\t ENTER ANY STRING...: ");

gets(str);

i=stlen(str);

printf("\n\n\t THE LENGHT OF THE STRING...:%d",i);

printf("\n\n\t ENTER THE FIRST STRING...: ");

gets(str1);

printf("\n\n\t ENTER THE FIRST STRING...: ");

gets(str2);

stcat(str1,str2);

printf("\n\t THE CONCATENATED STRING IS...: ");

puts(str1);

getch();

}

void stcat (char *str1, char *str2)

{

int i = 0,len = 0;

while(*(str1+len)!='\0')

len++;

while(*(str2+i)!='\0')

{

*(str1+len) = *(str2+i);

i++;

len++;

}

*(str1+len) = '\0';

}

int stlen(char *str)

{

int i=0;

while(*(str+i)!='\0')

{

i++;

}

return i;

}

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

4)//P4.Use pointers to copy a string and to extract a substring from a given string.

#include

#include

#include

void mystrcpy (char* dest, char* src)

{

while ((*dest++ = *src++) != '\0');

}

void extract(char *,char *,char *,int,int);

void main()

{

char s[50]="working with strings is fun";

char t[50];

char d[50];

int pos,len;

char *dest,*src;

printf("\nEnter strings");

scanf("%s",src);

mystrcpy(dest,src);

printf("\nString is=%s",dest);

printf("enter the position and length to be extracted= ");

scanf("%d%d",&pos,&len);

printf("\n\n");

extract(s,t,d,pos,len);

puts(d);

getch();

}

void extract(char *s,char *t,char *d,int pos,int len)

{

s=s+(pos-1);

t=s+len;

while(s!=t)

{

*d=*s;

s++;

d++;

}

*d='\0';

}

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

5)//P5 Tower of honaai

#include

#include

void tower_of_hanoi(int n, char LEFT, char RIGHT, char CENTER)

{

if(n>0)

{

tower_of_hanoi(n-1, LEFT, CENTER, RIGHT);

printf("\n\tMove disk %d from %c to %c", n, LEFT, RIGHT);

tower_of_hanoi(n-1, CENTER, RIGHT, LEFT);

}

}

void main()

{

int n;

printf("\nEnter no. of disks: ");

scanf("%d",&n);

clrscr();

printf("\nSOLUTION \n\t (L=Left,R=Right,C=Ceter)\n");

tower_of_hanoi(n,'L','R','C');

}

6)//P6. C program to insert an integer into a given position in an array

#include

#include

void main()

{

int x[10];

int i, j, n, m, temp, key, pos;

clrscr();

printf("Enter how many elements\n");

scanf("%d", &n);

printf("Enter the elements\n");

for(i=0; i

{

scanf("%d", &x[i]);

}

printf("Input array elements are\n");

for(i=0; i

{

printf("%d\n", x[i]);

}

for(i=0; i<>

{

for(j=i+1; j

{

if (x[i] > x[j])

{

temp = x[i];

x[i] = x[j];

x[j] = temp;

}

}

}

printf("Sorted list is\n");

for(i=0; i

{

printf("%d\n", x[i]);

}

printf("Enter the element to be inserted\n");

scanf("%d",&key);

for(i=0; i

{

if ( key <>

{

pos = i;

break;

}

}

m = n - pos + 1 ;

for(i=0; i<= m ; i++)

{

x[n-i+2] = x[n-i+1] ;

}

x[pos] = key;

printf("Final list is\n");

for(i=0; i

{

printf("%d\n", x[i]);

}

getch();

} /* End of main() */

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

7)//P7. C program to delete an array element from the given position

#include

int rem(int a[],int pLen,int pos)

{

int count;

for (count = pos;count <>

{

a[count] = a[count+1];

}

return a[count];

}

void main()

{

int arr[10],pos;// = {1,2,3,4,5,6,7,8,9,10};

int count2,n;

printf("Enter n value");

scanf("%d",&n);

printf("enter array elements");

for(count2=0;count2

scanf("%d",&arr[count2]);

printf("Enter positon to be delete");

scanf("%d",&pos);

rem(arr,n,pos);

for (count2 = 0;count2 <>

{

printf(" %d ",arr[count2]);

}

getch();

}

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

//P8 PROGRAM IMPLEMENTATION OF SINGLE LINKED LIST */

#include"stdio.h"

//#define NULL 0

/* STRUCTURE CONTANING A DATA PART AND A LINK PART */

struct node

{

int data;

struct node *next;

}*p;

// P IS A GLOBAL POINTER CONTAINS THE ADRESS OF THE FIRST NODE IN LIST

/*THIS FUNCTION DELETES A NODE */

void delnode(int num)

{

struct node *temp, *m;

temp=p;

while(temp!=NULL)

{

if(temp->data==num)

{

if(temp==p)

{

p=temp->next;

free(temp);

return;

}

else

{

m->next=temp->next;

free(temp);

return;

}

}

else

{

m=temp;

temp= temp->next;

}

}

printf(" \n ELEMENT %d NOT FOUND ", num);

}/*THIS FUNCTION ADDS A NODE AT THE LAST OF LINKED LIST */

void append( int num )

{

struct node *temp,*r;

/* CREATING A NODE AND ASSIGNING A VALUE TO IT */

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

temp->data=num;

r=(struct node *)p;

if (p == NULL) /* IF LIST IS EMPTY CREATE FIRST NODE */

{

p=temp;

p->next =NULL;

}

else

{ /* GO TO LAST AND ADD*/

while( r->next != NULL)

r=r->next;

r->next =temp;

r=temp;

r->next=NULL;

}

}/* ADD A NEW NODE AT BEGINNING */

void addbeg( int num )

{

/* CREATING A NODE AND INSERTING VALUE TO IT */

struct node *temp;

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

temp->data=num;

/* IF LIST IS NULL ADD AT BEGINNING */

if ( p== NULL)

{

p=temp;

p->next=NULL;

}

else

{

temp->next=p;

p=temp;

}

}

/* ADD A NEW NODE AFTER A SPECIFIED NO OF NODES */

void addafter(int num, int loc)

{

int i;

struct node *temp,*t,*r;

r=p; /* here r stores the first location */

if(loc > count()+1 || loc <= 0)

{

printf(" \n insertion is not possible : ");

return;

}

if (loc == 1)/* if list is null then add at beginning */

{

addbeg(num);

return;

}

else

{

for(i=1;i

{

t=r; /* t will be holding previous value */

r=r->next;

}

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

temp->data=num;

t->next=temp;

t=temp;

t->next=r;

return;

}

}/* THIS FUNCTION DISPLAYS THE CONTENTS OF THE LINKED LIST */

void display(struct node *r)

{

r=p;

if(r==NULL)

{

printf("\n\n NO ELEMENT IN THE LIST :");

return;

}

/* traverse the entire linked list */

while(r!=NULL)

{

printf(" -> %d ",r->data);

r=r->next;

}

printf(" ");

}

//THIS FUNCTION COUNTS THE NUMBER OF ELEMENTS IN THE LIST

int count()

{

struct node *n;

int c=0;

n=p;

while(n!=NULL)

{

n=n->next;

c++;

}

return(c);

}

//THIS FUNCTION REVERSES A LINKED LIST

void reverse(struct node *q)

{

struct node *m, *n,*l,*s;

m=q;

n=NULL;

while(m!=NULL)

{

s=n;

n=m;

m=m->next;

n->next=s;

}

p=n;

}

/* THIS IS THE MAIN PROGRAM */

void main()

{

int i;

clrscr();

p=NULL;

while(1) /* this is an indefinite loop */

{

printf("\n\n 1.INSERT A NUMBER AT BEGINNING;");

printf("\n\n 2.INSERT A NUMBER AT LAST:");

printf("\n\n 3.INSERT A NUMBER AT A PARTICULAR LOCATION INlIST:");

printf("\n\n 4.PRINT THE ELEMENTS IN THE LIST : ");

printf("\n\n 5.PRINT THE NUMBER OF ELEMENTS IN THE LIST ");

printf("\n\n 6.DELETE A NODE IN THE LINKED LIST ");

printf("\n\n 7.REVERSE A LINKED LIST :");

printf("\n\n 8.GET OUT OF LINKED LIST (BYEE BYEE):");

printf("\n\n PLEASE, ENTER THE NUMBER:");

scanf("%d",&i); /* ENTER A VALUE FOR SWITCH */

switch(i)

{

case 1:

{

int num;

printf("\n\n PLEASE ENTER THE NUMBER : ");

scanf("%d",&num);

addbeg(num);

break;

}

case 2:

{

int num;

printf("\n\n PLEASE ENTER THE NUMBER : ");

scanf("%d",&num);

append(num);

break;

}

case 3:

{

int num, loc,k;

printf("\n\n PLEASE ENTER THE NUMBER : ");

scanf("%d",&num);

printf("\n\nPLEASE ENTER THE LOCATION NUMBER : ");

scanf("%d",&loc);

addafter(num,loc);

break;

}

case 4:

{

struct node *n;

printf("\n\n THE ELEMENTS IN THE LIST ARE : ");

display(n);

break;

}

case 5:

{

struct node *n;

display(n);

printf("\n\n TOTAL NO OF ELEMENTS IN THE LSIT ARE %d: ",count());

break;

}

case 6:

{

int num;

printf("\n\n PLEASE ENTER A NUMBER FROM THE LIST : ");

scanf("%d",&num);

delnode(num);

break;

}

case 7:

{

reverse(p);

display(p);

break;

}

case 8:

{

exit();

}

}/* end if switch */

}/* end of while */

}/* end of main */

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

//P9 Write a program to sort N Numbers using insertion sort

#include

#include

void insertion(int a[],int n)

{

int i,j,x,k;

for(i=1;i<=n-1;i++)

{

j=i;

x=a[i];

while(a[j-1]>x && j>0)

{

a[j]=a[j-1];

j=j-1;

}

a[j]=x;

printf("\n\n The array after pass no.%d: ",i);

for(k=0;k<=n-1;k++)

printf("%4d",a[k]);

}//end for.

} //end function.

void main()

{

int a[1000],n,i;

clrscr();

printf("\n\nEnter an integer value for total no.s of elements to be sorted: ");

scanf("%3d",&n);

for(i=0;i<=n-1;i++)

{

printf("\n\nEnter an integer value for element no.%d: ",i+1);

scanf("%4d",&a[i]);

}

insertion(a,n);

printf("\n\n\nFinally sorted array is : ");

for(i=0;i<=n-1;i++)

printf("%4d",a[i]);

}//end program.

//P10 Write a program to sort N numbers using selection sort.

#include

#include

#define MAXSIZE 500

void selection(int elements[], int maxsize);

int elements[MAXSIZE],maxsize;

void main()

{

int i;

clrscr();

printf("\nHow many elements you want to sort: ");

scanf("%d",&maxsize);

printf("\nEnter the values one by one: ");

for (i = 0; i <>

{

printf ("\nEnter element %i :",i);

scanf("%d",&elements[i]);

}

printf("\nArray before sorting:\n");

for (i = 0; i <>

printf("[%i], ",elements[i]);

printf ("\n");

selection(elements, maxsize);

printf("\nArray after sorting:\n");

for (i = 0; i <>

printf("[%i], ", elements[i]);

getch();

}

void selection(int elements[], int array_size)

{

int i, j, k;

int min, temp;

for (i = 0; i <>

{

min = i;

for (j = i+1; j <>

{

if (elements[j] <>

min = j;

}

temp = elements[i];

elements[i] = elements[min];

elements[min] = temp;

}

}

PART B:

/P1 & P2 PROGRAM IMPLEMENTATION OF SINGLE LINKED LIST inserting node and deleting node. */

#include"stdio.h"

//#define NULL 0

/* STRUCTURE CONTANING A DATA PART AND A LINK PART */

struct node

{

int data;

struct node *next;

}*p;

// P IS A GLOBAL POINTER CONTAINS THE ADRESS OF THE FIRST NODE IN LIST

/*THIS FUNCTION DELETES A NODE */

void delnode(int num)

{

struct node *temp, *m;

temp=p;

while(temp!=NULL)

{

if(temp->data==num)

{

if(temp==p)

{

p=temp->next;

free(temp);

return;

}

else

{

m->next=temp->next;

free(temp);

return;

}

}

else

{

m=temp;

temp= temp->next;

}

}

printf(" \n ELEMENT %d NOT FOUND ", num);

}/*THIS FUNCTION ADDS A NODE AT THE LAST OF LINKED LIST */

void append( int num )

{

struct node *temp,*r;

/* CREATING A NODE AND ASSIGNING A VALUE TO IT */

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

temp->data=num;

r=(struct node *)p;

if (p == NULL) /* IF LIST IS EMPTY CREATE FIRST NODE */

{

p=temp;

p->next =NULL;

}

else

{ /* GO TO LAST AND ADD*/

while( r->next != NULL)

r=r->next;

r->next =temp;

r=temp;

r->next=NULL;

}

}/* ADD A NEW NODE AT BEGINNING */

void addbeg( int num )

{

/* CREATING A NODE AND INSERTING VALUE TO IT */

struct node *temp;

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

temp->data=num;

/* IF LIST IS NULL ADD AT BEGINNING */

if ( p== NULL)

{

p=temp;

p->next=NULL;

}

else

{

temp->next=p;

p=temp;

}

}

/* ADD A NEW NODE AFTER A SPECIFIED NO OF NODES */

void addafter(int num, int loc)

{

int i;

struct node *temp,*t,*r;

r=p; /* here r stores the first location */

if(loc > count()+1 || loc <= 0)

{

printf(" \n insertion is not possible : ");

return;

}

if (loc == 1)/* if list is null then add at beginning */

{

addbeg(num);

return;

}

else

{

for(i=1;i

{

t=r; /* t will be holding previous value */

r=r->next;

}

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

temp->data=num;

t->next=temp;

t=temp;

t->next=r;

return;

}

}/* THIS FUNCTION DISPLAYS THE CONTENTS OF THE LINKED LIST */

void display(struct node *r)

{

r=p;

if(r==NULL)

{

printf("\n\n NO ELEMENT IN THE LIST :");

return;

}

/* traverse the entire linked list */

while(r!=NULL)

{

printf(" -> %d ",r->data);

r=r->next;

}

printf(" ");

}

//THIS FUNCTION COUNTS THE NUMBER OF ELEMENTS IN THE LIST

int count()

{

struct node *n;

int c=0;

n=p;

while(n!=NULL)

{

n=n->next;

c++;

}

return(c);

}

//THIS FUNCTION REVERSES A LINKED LIST

void reverse(struct node *q)

{

struct node *m, *n,*l,*s;

m=q;

n=NULL;

while(m!=NULL)

{

s=n;

n=m;

m=m->next;

n->next=s;

}

p=n;

}

/* THIS IS THE MAIN PROGRAM */

void main()

{

int i;

clrscr();

p=NULL;

while(1) /* this is an indefinite loop */

{

printf("\n\n 1.INSERT A NUMBER AT BEGINNING;");

printf("\n\n 2.INSERT A NUMBER AT LAST:");

printf("\n\n 3.INSERT A NUMBER AT A PARTICULAR LOCATION INlIST:");

printf("\n\n 4.PRINT THE ELEMENTS IN THE LIST : ");

printf("\n\n 5.PRINT THE NUMBER OF ELEMENTS IN THE LIST ");

printf("\n\n 6.DELETE A NODE IN THE LINKED LIST ");

printf("\n\n 7.REVERSE A LINKED LIST :");

printf("\n\n 8.GET OUT OF LINKED LIST (BYEE BYEE):");

printf("\n\n PLEASE, ENTER THE NUMBER:");

scanf("%d",&i); /* ENTER A VALUE FOR SWITCH */

switch(i)

{

case 1:

{

int num;

printf("\n\n PLEASE ENTER THE NUMBER : ");

scanf("%d",&num);

addbeg(num);

break;

}

case 2:

{

int num;

printf("\n\n PLEASE ENTER THE NUMBER : ");

scanf("%d",&num);

append(num);

break;

}

case 3:

{

int num, loc,k;

printf("\n\n PLEASE ENTER THE NUMBER : ");

scanf("%d",&num);

printf("\n\nPLEASE ENTER THE LOCATION NUMBER : ");

scanf("%d",&loc);

addafter(num,loc);

break;

}

case 4:

{

struct node *n;

printf("\n\n THE ELEMENTS IN THE LIST ARE : ");

display(n);

break;

}

case 5:

{

struct node *n;

display(n);

printf("\n\n TOTAL NO OF ELEMENTS IN THE LSIT ARE %d : ",count());

break;

}

case 6:

{

int num;

printf("\n\n PLEASE ENTER A NUMBER FROM THE LIST : ");

scanf("%d",&num);

delnode(num);

break;

}

case 7:

{

reverse(p);

display(p);

break;

}

case 8:

{

exit();

}

}/* end if switch */

}/* end of while */

}/* end of main */

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

//P3 Pointer implementation of stacks.

#include

#include

struct node

{

int data;

struct node* next;

};

void init(struct node* s)

{

s = NULL;

}

struct node* push(struct node* s,int data)

{

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

if(tmp == NULL)

{

// no memory available

exit(0);

}

tmp->data = data;

tmp->next = s;

s = tmp;

return s;

}

struct node* pop(struct node *s,int *element)

{

struct node* tmp = s;

*element = s->data;

s = s->next;

free(tmp);

return s;

}

int empty(struct node* s)

{

return s == NULL ? 1 : 0;

}

void main()

{

struct node* head = NULL;

int size,element,counter = 0;

/*stack size is dynamic andspecified at runtime*/

printf("Enter stack size:");

scanf("%d",&size);

printf("Push elements to stack\n");

init(head);

while(counter <>

{

getchar();

element = rand();

printf("push element %d into stack\n",element);

head = push(head,element);

counter++;

}

printf("Pop elements from stack\n");

while(0 == empty(head))

{

head = pop(head,&element);

printf("pop element %d from stack\n",element);

getchar();

}

getchar();

}

//P4 Pointer implementations with queues

#define true 1

#define false 0

#include

#include

#include

struct q_point

{

int ele;

struct q_point* n;

};

struct q_point *f_ptr = NULL;

int e_que(void);

void add_ele(int);

int rem_ele(void);

void show_ele();

/*main function*/

void main()

{

int ele,choice,j;

while(1)

{

clrscr();

printf("\n\n****IMPLEMENTATION OF QUEUE USING POINTERS****\n");

printf("==============================================");

printf("\n\t\t MENU\n");

printf("==============================================");

printf("\n\t[1] To insert an element");

printf("\n\t[2] To remove an element");

printf("\n\t[3] To display all the elements");

printf("\n\t[4] Exit");

printf("\n\n\tEnter your choice:");

scanf("%d", &choice);

switch(choice)

{

case 1:

{

printf("\n\tElement to be inserted:");

scanf("%d",&ele);

add_ele(ele);

getch();

break;

}

case 2:

{

if(!e_que())

{

j=rem_ele();

printf("\n\t%d is removed from the queue",j);

getch();

}

else

{

printf("\n\tQueue is Empty.");

getch();

}

break;

}

case 3:

show_ele();

getch();

break;

case 4:

exit(1);

break;

default:

printf("\n\tInvalid choice.");

getch();

break;

}

}

}

/* Function to check if the queue is empty*/

int e_que(void)

{

if(f_ptr==NULL)

return true;

return false;

}

/* Function to add an element to the queue*/

void add_ele(int ele)

{

struct q_point *queue = (struct q_point*)malloc(sizeof(struct q_point));

queue->ele = ele;

queue->n = NULL;

if(f_ptr==NULL)

f_ptr = queue;

else

{

struct q_point* ptr;

ptr = f_ptr;

for(ptr=f_ptr ;ptr->n!=NULL; ptr=ptr->n);

ptr->n = queue;

}

}

/* Function to remove an element from the queue*/

int rem_ele()

{

struct q_point* queue=NULL;

if(e_que()==false)

{

int j = f_ptr->ele;

queue=f_ptr;

f_ptr = f_ptr->n;

free (queue);

return j;

}

else

{

printf("\n\tQueue is empty.");

return -9999;

}

}

/* Function to display the queue*/

void show_ele()

{

struct q_point *ptr=NULL;

ptr=f_ptr;

if(e_que())

{

printf("\n\tQUEUE is Empty.");

return;

}

else

{

printf("\n\tElements present in Queue are:\n\t");

while(ptr!=NULL)

{

printf("%d\t",ptr->ele);

ptr=ptr->n;

}

}

}

//P5 Creatingg binary search tree Nd traversing it using in order,preorder and post order

#include

#include

#include

struct searchtree

{

int element; struct searchtree *left,*right;

}*root;

typedef struct searchtree *node;

typedef int ElementType;

node insert(ElementType, node);

node delet(ElementType, node);

void makeempty();

node findmin(node);

node findmax(node);

node find(ElementType, node);

void display(node, int);

void main()

{

int ch;

ElementType a;

node temp;

makeempty();

while(1)

{

printf("\n1. Insert\n2. Delete\n3. Find min\n4. Find max\n5. Find\n6. Display\n7. Exit\nEnter Your Choice : ");

scanf("%d",&ch);

switch(ch)

{

case 1:

printf("Enter an element : ");

scanf("%d", &a);

root = insert(a, root);

break;

case 2:

printf("\nEnter the element to delete : ");

scanf("%d",&a);

root = delet(a, root);

break;

case 3:

printf("\nEnter the element to search : ");

scanf("%d",&a);

temp = find(a, root);

if (temp != NULL)

printf("Element found");

else

printf("Element not found");

break;

case 4:

temp = findmin(root);

if(temp==NULL)

printf("\nEmpty tree");

else

printf("\nMinimum element : %d", temp->element);

break;

case 5:

temp = findmax(root);

if(temp==NULL)

printf("\nEmpty tree");

else

printf("\nMaximum element : %d", temp->element);

break;

case 6:

if(root==NULL)

printf("\nEmpty tree");

else

display(root, 1);

break;

case 7: exit(0);

default:printf("Invalid Choice");

}

}

}

node insert(ElementType x,node t)

{

if(t==NULL)

{

t = (node)malloc(sizeof(node));

t->element = x;

t->left = t->right = NULL;

}

else

{

if(x <>element)

t->left = insert(x, t->left);

else if(x > t->element)

t->right = insert(x, t->right);

}

return t;

}

node delet(ElementType x,node t)

{

node temp;

if(t == NULL)

printf("\nElement not found");

else

{

if(x <>element)

t->left = delet(x, t->left);

else if(x > t->element)

t->right = delet(x, t->right);

else

{

if(t->left && t->right)

{

temp = findmin(t->right);

t->element = temp->element;

t->right = delet(t->element,t->right);

}

else if(t->left == NULL)

t=t->right;

else

t=t->left;

}

}

return t;

}

void makeempty()

{

root = NULL;

}

node findmin(node temp)

{

if(temp == NULL || temp->left == NULL)

return temp;

return findmin(temp->left);

}

node findmax(node temp)

{

if(temp==NULL || temp->right==NULL)

return temp;

return findmin(temp->right);

}

node find(ElementType x, node t)

{

if(t==NULL)

return NULL;

if(xelement)

return find(x,t->left);

if(x>t->element)

return find(x,t->right);

return t;

}

void display(node t,int level)

{

int i;

if(t)

{

display(t->right, level+1);

printf("\n");

for(i=0;i

printf(" ");

printf("%d", t->element);

display(t->left, level+1);

}

}

//P6 Sort N numbers using merge sort

//PART-B P6 Sort numbers using Merge Sort.

#include

#include

#define MAX_ARY 10

void merge_sort(int x[], int end, int start);

int main(void)

{

int ary[MAX_ARY];

int j = 0;

printf("\n\nEnter the elements to be sorted: \n");

for(j=0;j scanf("%d",&ary[j]);

/* array before mergesort */

printf("Before :");

for(j = 0; j <>

printf(" %d", ary[j]);

printf("\n");

merge_sort(ary, 0, MAX_ARY - 1);

/* array after mergesort */

printf("After Merge Sort :");

for(j = 0; j <>

printf(" %d", ary[j]);

printf("\n");

getch();

}

/* Method to implement Merge Sort*/

void merge_sort(int x[], int end, int start)

{

int j = 0;

const int size = start - end + 1;

int mid = 0;

int mrg1 = 0;

int mrg2 = 0;

int executing[MAX_ARY];

if(end == start)

return;

mid = (end + start) / 2;

merge_sort(x, end, mid);

merge_sort(x, mid + 1, start);

for(j = 0; j <>

executing[j] = x[end + j];

mrg1 = 0;

mrg2 = mid - end + 1;

for(j = 0; j <>

{

if(mrg2 <= start - end)

if(mrg1 <= mid - end)

if(executing[mrg1] > executing[mrg2])

x[j + end] = executing[mrg2++];

else

x[j + end] = executing[mrg1++];

else

x[j + end] = executing[mrg2++];

else

x[j + end] = executing[mrg1++];

}

}