c-programming-using-pointers

EX NO: IMPLEMENTATION OF RECURSIVE ALGORITHM
DATE: USING POINTER

AIM:
To write a C-Program to implement a recursive algorithm using pointers

ALGORITHM:

STEP 1: Start the program
STEP 2: Declare the variable, *no, factorial, sum, p, i, and the function fact(int p),
sum(int p), fib(int p)

sy
STEP 3: Read the value of no.
STEP 4: Call the function fact(*no), sum(*no)

ea
STEP 5: Using a for loop call the function fib(int p) and display the Fibonacci series &
also display factorial & summation.
STEP 6: Stop the program

e
FUNCTION FIB (int p)

ad
STEP 1: Check whether the value of n is equal to ‘0’ if so return ‘0’
STEP 2: Else check whether (p>=1 && p<=2), if so return the value ‘1’
m
STEP 3: Else return ( fib(p-1)+ fib(p-2))

FUNCTION FACT (int p)
g
in

STEP 1: Check whether (p==0), if so return ‘1’.
STEP 2: Else return (p*fact(p-1))
m

FUNCTION SUM (int p)
am

STEP 1: Check whether p==0, if so return ‘0’
STEP 2: Else return (p+sum(p-1))
o gr
Pr

PROGRAM:

#include<stdio.h>
#include<conio.h>
void main()
{
int i,p, *no,factorial,summ;
int fact(int p);
int sum(int p);
int fib(int p);
clrscr();

sy
printf("n Enter The Number:");
scanf("%d",no);

ea
printf("n The Fibonnacci series: n");
for(i=0;i<*no;i++)
printf("%dn",fib(i));
factorial=fact(*no);

e
printf("n The factorial of %d: %dn", *no,factorial);

ad
summ=sum(*no);printf("nThe summation of %d: %dn", *no,summ);
getch();
}
m
int fib(int p)
{
if(p==0)
g

return(0);
in

if(p>=1&&p<=2)
return(1);
m

else
return(fib(p-1)+fib(p-2));
am

}
int fact(int p)
{
gr

if(p==0)
return(1);
else
o

return(p*fact(p-1));
Pr

}
int sum(int p)
{
if(p==0)
return(0);
else
return(p+sum(p-1));
}

OUTPUT:

Enter the Number: 5

The Fibonacci series:
0
1
1
2
3

sy
The factorial of 5: 120
The summation of 5: 15

ea
e
ad
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

RESULT:

Thus the C-Program was written to implement a recursive algorithm using pointers and the
output was verified

`EX.NO: IMPLEMENTATION OF BUBBLE SORT
DATE:

AIM: To write a C-Program to implement bubble sort using pointers and functions

ALGORITHM:

STEP 2: Read the value of n
STEP 3: Set a for loop to read the elements of array
for(i=0;i<n;i++)

sy
STEP 4: Call the function bubblesort(a,n)
STEP 5: Print the sorted array a

ea

FUNCTION BUBBBLESORT (int *b[], int n)

e
ad
STEP 1: Declare the local variable.
STEP 2: Set a for loop
for(i=0;i<n;i++)
m
STEP 3: Nest another for loop
for(j=1;j<n;j++)
STEP 4: Check the condition
g

b[i]>b[j]
in

STEP 5: If so swap the two values using temporary variable t as
t=a[i]
m

b[i]=b[j]
b[j]=t
am

STEP 6: Else go back to step3.
o gr
Pr

PROGRAM:

#include<stdio.h>
#include<conio.h>
void bubblesort(int*[],int);
void main()
{
int i,n,a[100];
clrscr();
printf("n Enter the number of elements:");
scanf("%d",&n);

sy
printf("n Enter the array elements");
for(i=0;i<n;i++)

ea
scanf("%d",&a[i]);
printf("nUNSORTED ARRAY ELEMENTS");
for(i=0;i<n;i++)
printf("t%d",a[i]);

e
bubblesort(a,n);

ad
printf("nSORTED ARRAY");
for(i=0;i<n;i++)
printf("t%d",*(a+i));
m
getch();
}
void bubblesort(int* b[],int n)
g

{
in

int i,j,t;
for(i=0;i<n;i++)
m

{
for(j=i+1;j<n;j++)
am

{
if(b[i]>b[j])
{
gr

t=b[i];
b[i]=b[j];
b[j]=t;
o

}
Pr

}
}
}

OUTPUT:

Enter the number of elements:6

Enter the array elements 34
32
12
456
43

sy
56

ea
UNSORTED ARRAY ELEMENTS 34 32 12 456 43 56

SORTED ARRAY 12 32 34 43 56 456

e
ad
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

RESULT:

Thus the C-Program was written to implement bubble sort using pointers and functions
and the output was verified successfully.

EX.NO: IMPLEMENTATION OF SELECTION SORT
DATE:

AIM: To write a C-Program to implement selection sort using pointers and functions

ALGORITHM:

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

sy
STEP 4: Call the function sel(a,0,n-1)

ea

FUNCTION SEL (int *x, int start, int stop )

e
ad
STEP 2: Assign
begin =start and small=begin and check if
m
start < stop
STEP 3: If so then set a for loop
for(i=begin+1;i<=stop;i++)
g

STEP 4: Check the condition
in

x[i]<x[small]
STEP 6: If so then assign the value of i to small
m

Small=i
STEP 7: Then swap the values of x[begin] and x[small] using temp
am

temp=x[begin]
x[begin]=x[small]
x[small]=temp
gr

STEP 8: Call another function sel(x,start+1,stop)
o
Pr

PROGRAM:

#include<stdio.h>
#include<conio.h>
void sel(int *[],int,int);
int main()
{
int a[100],i,n;
clrscr();
printf("nEnter The number Of elements:");
scanf("%d",&n);

sy
printf("nEnter the array elements one by onen");
for(i=0;i<n;i++)
{

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

e
for(i=0;i<n;i++)

ad
printf("t%d",a[i]);
sel(a,0,n-1);
printf("SORTED ARRAY:n");
m
for(i=0;i<n;i++)
{
printf("t %d",a[i]);
g

}
in

getch();
return(0);
m

}
am

void sel(int *x[], int start, int stop)
{
int begin=start;
int small=begin;
gr

int temp,i;
if(start<stop)
o

{
Pr

for(i=begin+1;i<=stop;i++)
{
if(x[i]<x[small])
small=i;
}
temp=x[begin];
x[begin]=x[small];
x[small]=temp;
sel(x,start+1,stop);
}
}

OUTPUT:


Enter the array elements one by one 23
45
89
98
09

sy
65

ea

SORTED ARRAY 09 23 45 65 89 98

e
ad
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

RESULT:

Thus the C-Program was written to implement selection sort using pointers and functions

EX.NO: IMPLEMENTATION OF MERGE SORT
DATE:

AIM: To write a C-Program to implement merge sort using divide and conquer strategy

ALGORITHM:

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

sy
STEP 4: Call the function split(a,0,n-1)

ea

FUNCTION MERGE_SORT (int *a, int low, int high)

e

ad
STEP 2: If low is less than high then assign the mean value of low
and high to mid
mid =(low+high)/2
m
STEP 3: Call the function merge_sort(a,low,mid)
STEP 4: Call the another function merge_sort(a,mid+1,high)
STEP 5: Call the function combine(a,low,mid,high)
g
in

FUNCTION SPLIT(int *c, int first, int last)
m

STEP 1: Declare the local variables
STEP 2: Set the while loop till the condition i<=mid && j<=high is failed
am

STEP 3: Check whether a[i]<a[j]
STEP 4: If so the assign the value of a[j] to temp[k] and increment j and k
temp[k]=a[i]
gr

j++ k++
STEP 5: Else assign a[j] to temp[k] and then increment j and k
temp[k]=a[j] & j++ k++
o

STEP 6: Set another while loop till i is less than mid
Pr

STEP 7: Assign the value of a[i] to temp[k]
temp[k]=a[i] & j++ k++
STEP 8: Set another while loop till j is greater than mid
STEP 9: Assign the value of a[j] to temp[k]
temp[k]=a[j]
j++ k++
STEP 10: Construct a for loop for k
for(k=low; k<=high; k++)
STEP 11: Assign the value of temp[k] to a[k]
a[k]=temp[k]

PROGRAM:

#include<stdio.h>
#include<conio.h>
void split(int *,int,int);
void merge(int *,int,int,int,int);
int a[25],b[25];
void main()
{
int i,n;
clrscr();

sy
printf("Enter the limit");
scanf("%d",&n);

ea
printf("n Enter the elements");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);

e
}

ad
split(a,0,n-1);
printf("n The sorted list is:");
for(i=0;i<n;i++)
m
printf("n %d",a[i]);
getch();
}
g

void split(int *c,int first,int last)
in

{
int mid;
m

if(first<last)
{
am

mid=(first+last)/2;
split(c,first,mid);
split(c,mid+1,last);
gr

merge(c,first,mid,mid+1,last);
}
}
o

void merge(int *a,int f1,int l1,int f2,intl2)
Pr

{
int i,j,k=0;
i=f1;
j=f2;
while(i<=l1&&j<=l2)
{
if(a[i]<a[j])
b[k]=a[i++];
else
b[k]=a[j++];

k++;
}
while(i<=l1)
b[k++]=a[i++];
while(j<=l2)
i=f1;
j=0;
while(i<=l2&&j<k)
a[i++]=b[j++]
}

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

OUTPUT:


45
89
98
09
65

sy

ea
SORTED ARRAY 09 23 45 65 89 98

e
ad
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr

RESULT:
Pr

Thus the C-Program was written to implement merge sort using pointers and functions

EX.NO: IMPLEMENTATION OF BINARY SEARCH WITH RECURSION
DATE:

AIM: To write a C-Program to implement binary search using recursive functions

ALGORITHM:

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

sy
for(j=i+1;j<n;j++)

ea
STEP 6: Check the condition a[i]>a[j]
t=a[i]
a[i]=a[j]

e
a[j]=t

ad
STEP 8: Else go back to step 6.
STEP 9: Set a for loop to print the value of array a
For(i=0;i<n;i++)
m
STEP 10: Read the search key as k
STEP 11: Assign low=0 and high=n-1
STEP 12: Call the function binsearch(a,k,low,high)
g

STEP 13: Check if ans is not equal to1 if so print the position b+i
in

Else print that element is not found
m

FUNCTION BINARY SEARCH (int *x[ ], int x, int low, int high)
am

STEP 1: Set a while loop till low is greater than high
STEP 2: Assign mean value of low and high to mid
gr

mid=(high+low)/2
STEP 3: Assign the value of x[mid] to p
p=x[mid]
o

STEP 4: Check if x<p if so assign
Pr

high=mid-1
STEP 5: Else check whether x>p if so then assign
low=mid+1
STEP 6: Else check whether x= =p, if so return mid
STEP 7: Else return -1

PROGRAM:

#include<stdio.h>
#include<conio.h>
binarysearch(int *[],int,int,int);
void main()
{
int i,j,k,t,low,high,n,a[50],ans;
clrscr();
printf("n enter the N:");
scanf("%d",&n);
printf("n enter the array element one by onen");
for(i=0;i<n;i++)

sy
scanf("%d",&a[i]);
printf("n sorted array n");

ea
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(a[i]>a[j])
{

e
t=a[i];

ad
a[i]=a[j];
a[j]=t;
}
m
for(i=0;i<n;i++)
printf("t a[%d]=%dn",i,a[i]);
printf("t enter the element to search:");
g

scanf("%d",&k);
in

low=0;
high=n-1;
m

ans=binarysearch(a,k,low,high);
if(ans!=-1)
am

printf("nthe number %d is present in the list at location %d",k,ans);
else
printf(" the number is not present in the list");
gr

getch();
}
int binarysearch(int *a[],int x,int low,int high)
o

{
Pr

int mid,p;
if(low>high)
return-1;
mid=(low+high)/2;
p=a[mid];
if(x==p)
return(mid);
else
if(x<p)
return binarysearch(a,x,low,mid-1);

else
return binarysearch(a,x,mid+1,high);
}

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

OUTPUT:


45
89
98
09
65

sy
SORTED ARRAY 09 23 45 65 89 98

ea
Enter the element to search 23

The number 23 is present in the list at location 2

e
ad
Enter the element to search 50

The number is not present in the list
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr

RESULT:
Pr

Thus the C-Program was written to implement binary search using recursive functions

EX.NO: IMPLEMENTATION OF BINARY SEARCH WITHOUT RECURSION
DATE:

AIM: To write a C-Program to implement binary search using non-recursive functions

ALGORITHM:

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

sy
for(j=i+1;j<n;j++)

ea
STEP 6: Check the condition a[i]>a[j]
t=a[i]
a[i]=a[j]

e
a[j]=t

ad
STEP 8: Else go back to step 6.
STEP 9: Set a for loop to print the value of array a
for(i=0;i<n;i++)
m
STEP 10: Read the search key as k
STEP 11: Assign low=0 and high=n-1
STEP 12: Call the function binsearch(a,k,low,high)
g

STEP 13: Check if ans is not equal to1 if so print the position b+i
in

Else print that element is not found
m

FUNCTION BINARY SEARCH (int *a[ ], int x, int low, int high)
am

STEP 1: Check if low>high if so return -1
STEP 2: Else assign mean value of low and high to mid
gr

mid=(high+low)/2
STEP 3: Assign the value of a[mid] to p
p=a[mid]
o

STEP 4: Check if x= =p if so then return mid
Pr

STEP 5: Else check whether x<p if so then return
binsearch(a,x,low,mid-1)
STEP 6: Else return
binsearch(a,x,mid+1,high)

PROGRAM:

#include<stdio.h>
#include<conio.h>
binarysearch(int *[],int,int);
void main()
{
int i,j,n,a[10],t,k,b;
clrscr();
printf(" ENTER THE NUMBERn ");
scanf("%d",&n);
printf("Enter array elementsn");
for(i=0;i<n;i++)

sy
scanf("%d",&a[i]);
printf("The sorted the arrayn");

ea
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(a[i]>a[j])
{

e
t=a[i];

ad
a[i]=a[j];
a[j]=t;
}
m
for(i=0;i<n;i++)
printf("%d",a[i]);
printf("nEnter the search elementn");
g

scanf("%d",&k);
in

b=binarysearch(&a,n,k);
if(b!=-1)
m

printf("position:%d",b);
else
am

printf("search element not foundn");
getch();
}
gr

binarysearch(int *a[],int n,int k)
{
int mid,low,high,p;
o

low=0;
Pr

high=n-1;
while(low<=high)
{
mid=(low+high)/2;
p=a[mid];
if(p>k)
high=mid-1;
else if(p<k)
low=mid+1;
else if(k==p)

return mid;
}
return-1;
}

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

OUTPUT:

sy
ea
e
ad
m
g
in
m
am
o gr

RESULT:
Pr

Thus the C-Program was written to implement binary search without using recursive functions and
the output was verified successfully.

EX.NO: IMPLEMENTATION OF QUICK SORT
DATE:

AIM: To write a C-Program to implement quick sort using pointers and functions

ALGORITHM:

STEP 2: Assign the pointer array *a[100] as global, read the value of n
for(i=0;i<n;i++)
STEP 4: Call the function sort(0,n-1)

sy

ea
FUNCTION SORT (int first, int last )


e
STEP 2: Check if first is less than last

ad
first < last
STEP 3: If so then assign the following
pivot=a[first]
m
i=first
j=last
STEP 4: Assign a while loop till the condition
g

i<j
in

STEP 5: Assign a while loop to increment i till
a[i]<pivot and i< last
m

STEP 6: Assign a while loop to decrement j till
a[j] > pivot and j > first
am

STEP 7: Check whether i is than j if so then swap the values of a[i] and a[j]
temp=a[i]
a[j]=a[j]
gr

a[j]=temp
STEP 8: Then swap the values of a[j] and a[first]
temp=a[j]
o

a[j]=a[first]
Pr

a[first]=temp
STEP 9: Call another functions sort(first, j-1) and sort(j+1, last)

PROGRAM:

#include<stdio.h>
#include<conio.h>
int *a[50],n,i;
void sort(int,int);
void main()
{
clrscr();
printf("Enter the No of Elements:");
scanf("%d",&n);
printf("Enter The Elements;");
for(i=0;i<n;i++)

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

ea
for(i=0;i<n;i++)
printf("t%d",a[i]);
sort(0,n-1);
printf("nSORTED ARRAY");

e
for(i=0;i<n;i++)

ad
printf("%d",a[i]);
getch();
}
m
void sort(int first,int last)
{
int *temp,*pivot,i,j;
g

if(first<last)
in

{
pivot=a[first];
m

i=first;
j=last;
am

while(i<j)
{
while((a[i]<=pivot)&&(i<last))
gr

i++;
while((a[j]>=pivot)&&(j>first))
j--;
o

if(i<j)
Pr

{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[first];
a[first]=a[j];
a[j]=temp;
sort(first,j-1);

sort(j+1,last);
}
}

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

OUTPUT:


Enter the array elements one by one 23
45
89
98
09
65

sy

ea
SORTED ARRAY 09 23 45 65 89 98

e
ad
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr

RESULT:
Pr

Thus the C-Program was written to implement quick sort using functions and pointers and the output
was verified successfully.

EX.NO: IMPLEMENTATION OF INSERTION SORT
DATE:

AIM: To write a C-Program to implement insertion sort using pointers and functions

ALGORITHM:

for(i=0;i<n;i++)
STEP 4: Call the function ins_sort(a,n)

sy

ea
FUNCTION INS_SORT (int *b[], int k )


e
STEP 2: Set a for loop for p

ad
for(p=1;p<k;p++)
STEP 3: Assign the value of b[p] to temp
temp=b[p]
m
STEP 4: Set a nested for loop for j
for(j=p;j>0&&b[j-1]>temp;j--)
STEP 5: Assign the value of b[j-1] to b[j] and temp to b[j]
g

b[j]=b[j-1];
in

b[j]=temp;
m

STEP 6: Assign a while loop to decrement j till
a[j] > pivot and j > first
am

STEP 7: Check whether i is than j if so then swap the values of a[i] and a[j]
temp=a[i]
a[j]=a[j]
gr

a[j]=temp
STEP 8: Then swap the values of a[j] and a[first]
temp=a[j]
o

a[j]=a[first]
Pr

a[first]=temp
STEP 9: Call another functions sort(first, j-1) and sort(j+1, last)

PROGRAM:

#include<stdio.h>
#include<conio.h>
void ins_sort(int *a[], int n);
void main()
{
int i,n,*a[50];
clrscr();
printf("Enter the number of Elements");
scanf("%d",&n);
printf("nEnter the array elements n");
for(i=0;i<n;i++)

sy
scanf("%d",&a[i]);
printf("UNSORTED ARRAY:n");

ea
for(i=0;i<n;i++)
printf("t%d",a[i]);
ins_sort(a,n);
printf("SORTED ARRAY:n");

e
for(i=0;i<n;i++)

ad
printf("t%d",a[i]);
getch();
}
m
void ins_sort(int *b[], int k)
{
int j,p,*temp;
g

for(p=1;p<k;p++)
in

{
temp=b[p];
m

for(j=p;j>0&&b[j-1]>temp;j--)
b[j]=b[j-1];
am

b[j]=temp;
}
o gr
Pr

OUTPUT:

sy
ea
e
ad
m
g
in
m
am
o gr

RESULT:
Pr

Thus the C-Program was written to implement insertion sort using pointers and functions

EX.NO: IMPLEMENTATION OF 8 QUEEN PROBLEMS
DATE:

AIM: To write a C-Program to implement a 8 queen program using functions

ALGORITHM:

STEP 1: Define the functions that are to be used
STEP 2: Assign a constant value of 8 to QUEENNO
STEP 3: Call the function placequeen(0,x)
STEP 4: Print the message “end”

sy
FUNCTION VOID PLACEQUEEN(int k, int *x)

ea
STEP 1: Declare local variables
STEP 2: Set a for loop for i
for(i=0;i<8;i++)
STEP 3: Check for result of function canbeplaced(k,i,x)

e
STEP 4: If it is 1 then assign the value of i to x[k]

ad
x[k]=i;
STEP 5: Check if k is equal to 7 if show call the function showboard(x)
STEP 6: Read the value of ch from the user
m
STEP 7: If the value is equal to n or N then exit
STEP 8: Check whether k is less than 7 if so then call the function placequeen(k+1,x)
g
in

FUNCTION INT CANBEPLACED(int k, int i, int *x)
m

STEP 2: Set a for loop for j
am

for(j=0;j<k;j++)
STEP 3: Check for the following condition
if((abs(j-k)==abs(x[j]-i)||(x[j]==i)))
gr

STEP 4: If its true return 0 else return 1

FUNCTION VOID SHOWBOARD(int *x)
o
Pr

STEP 2: Set all the display style in printf function
STEP 3: Set a for loop for i to print 1,2,..8 vertically and horizontally
for(i=0;i<8;i++)
STEP 4: Set another for loop for j and check whether j is equal to x[i]
for(j=0;j<8;j++)
STEP 5: If so then print Q else print -

PROGRAM:

#include<stdio.h>
#include<conio.h>
#define QUEENNO 8
void placequeen(int,int*);
int canbeplaced(int,int,int*);
void showboard(int*);
void main()
{
int x[QUEENNO],i;
clrscr();
printf("the 8 queens problem");

sy
placequeen(0,x);
printf("end");

ea
getch();
}
void placequeen(int k,int *x)
{

e
int i,j;

ad
char ch;
for(i=0;i<8;i++)
{
m
if(canbeplaced(k,i,x))
{
x[k]=i;
g

if(k==7)
in

{
showboard(x);
m

printf("want to see more?[n->stop, any-> continue]:");
scanf("%c",&ch);
am

if(ch=='n' || ch=='N')
exit(0);
}
gr

if(k<7)
placequeen(k+1,x);
}
o

}
Pr

}
int canbeplaced(int k,int i,int *x)
{
int j;
for(j=0;j<k;j++)
{
if((abs(j-k)==abs(x[j]-i))||(x[j]==i)))
return 0;
}
return 1;

}
void showboard(int *x)
{
int i,j;
printf("n----------------------------------------------n");
printf(" ");
for(i=0;i<8;i++)
{
printf("%d",(i+1));
printf(" ");
}

sy
for(i=0;i<8;i++)
{

ea
printf("nn%d",(i+1));
for(j=0;j<8;j++)
{
if(j==x[i])

e
printf("Q");

ad
else
printf("-");
printf(" ");
m
}
printf("");
}
g

printf("n----------------------------------------------");
in

}
m
am
o gr
Pr

OUTPUT:

The 8 queens’ problem

------------------
1 2 3 4 5 6 7 8
1 Q - - - - - - -
2 - - Q - - - - -
3 - - - - Q - - -
4 - - - - - - Q -
5 – Q - - - - - -

sy
6 - - - Q - - - -
7 - - - - - Q - -
8 - - - - - - - Q

ea
------------------ want to see more?[n->stop, any-> continue]: n

e
ad
m
g
in
m
am
gro
Pr

sy
ea
e
ad
m
g
in
m
am
o gr

RESULT:
Pr

Thus the C-Program was written to implement an 8 queen program using functions

EX.NO: IMPLEMENTATION OF MINIMUM SPANNING TREE

DATE:

AIM: To write the C-Program to implement minimum spanning tree using structures, pointers and
functions

ALGORITHM:

STEP 2: Assign MAX a constant value of 20
STEP 3: Declare a structure edge with structure variable *front
STEP 4: Define the functions and variables required in the program globally

sy
STEP 5: Call the function create_graph() inside the main function
STEP 6: Call the function make_tree()

ea
STEP 7: Set a for loop using i
for(i=1;i<=count;i++)
STEP 8: Print the values of tree[i].u and tree[i].v

e
ad
FUNCTION OF CREATE_GRAPH ( )

m
STEP 2: Read the number of nodes n
STEP 3: Calculate the value of max_edge as
max_edge=n*(n-1)/2
g

STEP 4: Set a for loop using i
in

for(i=0;i<=max_edge;i++)
STEP 5: Read the values of origin and destin
m

STEP 6: Check whether origin and destin are equal to 0
STEP 7: If so exit the loop using break statement
am

STEP 8: Read the weight of the current edge wt
STEP 9: Check the following condition
if(origin>n||destin>n||origin<=0||destin <=0)
gr

STEP 10: If any of the condition is true, print “invalid edge!” and decrement the value of i by 1
STEP 11: Else call the function insert_pque(origin,destin,wt)
STEP 12:Check whether i is less than n-1, if so then exit with an error message
o
Pr

FUNCTION OF MAKE_TREE ( )

STEP 2: Initialize the variable tmp,node1,node2
STEP 3: Assign the values for node1, node2
STEP 4: Calculate and print the values of root_n1 and root_n2.
STEP 5: If the two roots are not equal, call the function inset_tree
STEP 6: Assign the value of root_n1 to father[root_n2]

FUNCTION OF INSERT_TREE (int i, int j, int wt )

STEP 2: Increment the value of count
STEP 3: Assign values to tree[count].u, tree[count].v, tree[count].weight.

FUNCTION OF INSERT_PQUE (int i, int j, int wt )

STEP 2: Allocate the memory space of size, struct edge for tmp

sy
STEP 3: Assign values to tmp->u, tmp->v, tmp->weight.
STEP 4: Check for the following condition.

ea
if(front==NULL||tmp->weight<front->weight)
STEP 5: If any of the conditions are true assign the value of front to tmp->link and assign tmp to
front
STEP 6: else set a while loop and declare following

e
q=q->link;

ad
tmp->link=q->link;
q->link=tmp;
if(q->link==NULL)
m
tmp->link=NULL;
g

FUNCTION OF STRUCT EDGE *DEL_PQUE( )
in

STEP 1: Declare the local variable
m

STEP 2: Assign the value of front to temp
STEP 3: print the values of processed edge and return the value of tmp
am
o gr
Pr

PROGRAM:

#include<stdio.h>
#include<conio.h>
#define MAX 20
struct edge
{
int u;
int v;

sy
int weight;
struct edge *link;

ea
}
*front=NULL;
int father[MAX];
struct edge tree[MAX];

e
int n;

ad
int wt_tree=0;
int count=0;
void make_tree();
m
void insert_tree(int i, int j, int wt);
void insert_pque(int i, int j, int wt);
struct edge *del_pque();
g

void main()
in

{
int i;
m

create_graph();
make_tree();
am

clrscr();
printf("edge to be included in spanning tree are:n");
for(i=1;i<=count;i++)
gr

{
printf("%d->",tree[i].u);
printf("%dn",tree[i].v);
o

}
Pr

printf("weight of this minimum spanning tree is: %dn",wt_tree);
getch();
}
create_graph()
{
int i,wt,max_edge,origin,destin;
printf("enter no. of nodes");
scanf("%d",&n);
max_edge=n*(n-1)/2;
for(i=0;i<=max_edge;i++)

{
printf("enter edge %d(0 0 to quit):",i);
scanf("%d%d",&origin,&destin);
if((origin==0)&&(destin==0))
break;
printf("enter weight for this ecge");
scanf("%d",&wt);
if(origin>n||destin>n||origin<=0||destin <=0)
{
printf("invalid edge!");
i--;

sy
}
else insert_pque(origin,destin,wt);

ea
}
if(i<n-1)
{
printf("spanning tree is not possible");

e
exit(1);

ad
}
return 0;
}
m
void make_tree()
{
struct edge *tmp;
g

int node1,node2,root_n1,root_n2;
in

while(count<n-1)
{
m

tmp=del_pque();
node1=tmp->u;
am

node2=tmp->v;
printf("n1=%d",node1);
printf("n2=%d",node2);
gr

while(node1>0)
{
root_n1=node1;
o

node1=father[node1];
Pr

}
while(node2>0)
{
root_n2=node2;
node2=father[node2];
}
printf("rootn1=%dn",root_n1);
printf("rootn2=%dn",root_n2);
if(root_n1!=root_n2)
{

insert_tree(tmp->u,tmp->v,tmp->weight);
wt_tree=wt_tree+tmp->weight;
father[root_n2]=root_n1;
}
}
}
void insert_tree(int i, int j, int wt)
{
printf("This Edge inserted in the spanning treen");
count++;
tree[count].u=i;

sy
tree[count].v=j;
tree[count].weight=wt;

ea
}
void insert_pque(int i, int j, int wt)
{
struct edge *tmp, *q;

e
tmp=(struct edge *)malloc(sizeof(struct edge));

ad
tmp->u=i;
tmp->v=j;
tmp->weight=wt;
m
if(front==NULL||tmp->weight<front->weight)
{
tmp->link=front;
g

front=tmp;
in

}
else
m

{
q=front;
am

while(q->link!=NULL&&q->link->weight<=tmp->weight)
q=q->link;
tmp->link=q->link;
gr

q->link=tmp;
if(q->link==NULL)
tmp->link=NULL;
o

}
Pr

}
struct edge *del_pque()
{
struct edge *tmp;
tmp=front;
printf("Edge Processed is %d->%d%dn",tmp->u,tmp->v,tmp->weight);
front=front->link;return tmp;
}

OUTPUT:

NUMBER OF NODES: 3
Enter the Edge 1:2 2
Enter the weight: 1
Enter the weight: 2
Enter the weight: 5

THE MINIMUM SPANNING TREE WEIGHT IS 7

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

sy
ea
e
ad
m
g
in
m
am
o gr
Pr

RESULT:

Thus the C-Program was written to implement minimum spanning tree using structures, pointers and
functions and the output was verified successfully.

c-programming-using-pointers

Recommended

More Related Content

What's hot (20)

Viewers also liked (12)

Similar to c-programming-using-pointers (20)

More from Sushil Mishra (14)

c-programming-using-pointers