Data Structures LAB PROGRAMS FOR BCA 2nd 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(x
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++];
}
}
No comments:
Post a Comment