Mca Ds Lab Manual

DATA STRUCTURES LAB I MCA II SEMESTER
EXERCISE 1
Write recursive program which computes the nth fibonacci number,for appropriate values
of n.
#include<stdio.h>
int fib(int);
main()
{
int x,i;
printf("enter up to series\n");
scanf("%d",&x);
for (i=0;i<x;i++)
printf("%d",fib(i));
}
int fib(int num)
{
if (num==0||num==1)
return num;
return fib(num-1)+fib(num-2);
}
input:
enter up to series
4
output:
0 1 1 2
VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 1

EXERCISE 2:
Write recursive program for the following
(A)write recursive and nonrecursive c program for calculation of factorial of an integer
RECURSIVE PROGRAM:
#include<stdio.h>
int factorial(int);
main()
{
int n,fact;
printf("enter number n");
scanf("%d",&n);
fact=factorial(n);
printf("factorial is %d",fact);
}
int factorial(int x)
{
int result;
if(x==1)
return 1;
else
{
result=x*factorial(x-1);
return result;
}
}
Input:
enter number n 5
output:
factorial is 120.
NON-RECURSIVE PROGRAM:
#include<stdio.h>
int factorial(int);
main()
{
int n,k;

printf("enter n value");
scanf("%d",&n);
k=factorial(n);
printf("factorial is %d",k);
}
int factorial(int x)
{
int i,result=1;
for(i=x;i>0;i--)
result=i*result;
return result;
}
Input:
enter n value 4
Output:
factorial is 24.
(B) Write recursive and non recursive C program for calculation of GCD(n,m)
RECURSIVE PROGRAM:
#include<stdio.h>
int gcd(int a,int b);
main()
{
int result,m,n;
printf("enter m,n values");
scanf("%d%d",&m,&n);
result=gcd(m,n);
printf("gcd of %d and %d is %d",m,n,result);
}
int gcd(int a,int b)

{
if(b==0)
return a;
if (a==0)

return b;
return gcd(b,a%b);
}
input:
enter m,n values 11 14
output:
gcd of 11 and 14 is 1.
#include<stdio.h>
int gcd(int,int);
main()
{
int a,b,r;
printf("enter any twonumbers");
scanf("%d%d",&a,&b);
r=gcd(a,b);
printf("gcd of twonumbers is%d",r);
}
int gcd(int a,int b)
{
int i,n;
if(a>b)
n=b;
else
n=a;
for(i=n;i>0;i--)
{
if(a%i==0&&b%i==0)
{
return i;
break;
}
}
}

Input:
enter any two numbers 5 45
Output:
gcd of two numbers is 5.
(C) Write recursive and non recursive program for towers of hanoi :ndisks are to be
transferred from peg s to peg d with peg i as the intermediate peg.
RECURSIVE PROGRAM
#include<stdio.h>
void towers(int,char,char,char);
main()
{
int n;
char a,b,c;
printf("enter no.of disks");
scanf("%d",&n);
printf("movements are \n");
towers(n,'a','c','b');
}
void towers(int n,char source,char dest,char aux)
{
if(n==1)
printf("move disk %c to %c\n",source,dest);
else
{
towers(n-1,source,aux,dest);
printf("move disk %c to %c\n",source,dest);
towers(n-1,aux,dest,source);
}}
Input:
Sequence of Disk Moves
enter no of disks 2
output:
move disk a to b

move disk a to c
move disk b to c
NON RECURSIVE PROGRAM

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <math.h>
struct Stack_Structure
{
int top;
int *array;
int max;
};
struct Stack_Structure* createStack(int max)

{
struct Stack_Structure* stack_object = (struct Stack_Structure*)malloc(sizeof(struct
Stack_Structure));
stack_object -> max = max;
stack_object -> top = -1;
stack_object -> array = (int*)malloc(stack_object -> max*sizeof(int));
return stack_object;
}
int isEmpty(struct Stack_Structure* stack_object)

{
return (stack_object->top == -1);
}
int isFull(struct Stack_Structure* stack_object)

{
return (stack_object->top == stack_object->max - 1);
}

void display_shift(char fromTower, char toTower, int disk)

{
printf("Move Disk %d from \'%c\' to \'%c\'\n", disk, fromTower, toTower);
}
void add_element(struct Stack_Structure *stack_object, int item)

{
if(isFull(stack_object))
{
return;
}
stack_object -> array[++stack_object -> top] = item;
}
int remove_element(struct Stack_Structure* stack_object)

{
if(isEmpty(stack_object))
{
return INT_MIN;
}
return stack_object -> array[stack_object -> top--];
}
void shift_Disks(struct Stack_Structure *source_tower, struct Stack_Structure

*destination_tower, char source, char destination)
{
int tower1 = remove_element(source_tower);
int tower2 = remove_element(destination_tower);
if(tower1 == INT_MIN)
if(tower1 == INT_MIN)
{
add_element(source_tower, tower2);
display_shift(destination, source, tower2);
}
else if(tower2 == INT_MIN)
{
add_element(destination_tower, tower1);
display_shift(source, destination, tower1);

}
else if(tower1 > tower2)
{
display_shift(destination, source, tower2);
}
else
{
display_shift(source, destination, tower1);
}
}
void tower_of_hanoi(int limit, struct Stack_Structure *source_tower, struct Stack_Structure

*temporary_tower, struct Stack_Structure *destination_tower)
{
int count, shift;
char destination = 'D', source = 'S', temporary = 'A';
if(limit % 2 == 0)
{
char x = destination;
destination = temporary;
temporary = x;
}
shift = pow(2, limit) - 1;
for (count = limit; count >= 1; count--)
{
add_element(source_tower, count);
}
for (count = 1; count <= shift; count++)
{
if (count%3 == 1)
{
shift_Disks(source_tower, destination_tower, source, destination);
}
else if (count%3 == 2)

{
shift_Disks(source_tower, temporary_tower, source, temporary);
}
else if(count%3 == 0)
{
shift_Disks(temporary_tower, destination_tower, temporary, destination);
}
}
}
int main()
{
int limit;
struct Stack_Structure *source_tower, *destination_tower, *temporary_tower;
printf("\nEnter The Number of Disks:\t");
scanf("%d", &limit);
printf("\nSequence of Disk Moves:\n\n");
source_tower = createStack(limit);
temporary_tower = createStack(limit);
destination_tower = createStack(limit);
tower_of_hanoi(limit, source_tower, temporary_tower, destination_tower);
printf("\n");
return 0;
printf("\nEnter The Number of Disks:\t");
scanf("%d", &limit);
printf("\nSequence of Disk Moves:\n\n");
source_tower = createStack(limit);
temporary_tower = createStack(limit);
destination_tower = createStack(limit);
tower_of_hanoi(limit, source_tower, temporary_tower, destination_tower);
printf("\n");
return 0;
}

OUTPUT :
Enter The Number of Disks: 3
Sequence of Disk Moves:
Move Disk 1 from 'S' to 'D'

Move Disk 2 from 'S' to 'A'
Move Disk 1 from 'D' to 'A'
Move Disk 3 from 'S' to 'D'
Move Disk 1 from 'A' to 'S'
Move Disk 2 from 'A' to 'D'
Move Disk 1 from S to D

EXERCISE 3:
(A) Write c program that use both recursive and non-recursive functions to perform linear search
for a key value in a given list
RECURSIVE PROGRAM:
#include<stdio.h>
int lsr(int a[ ],int,int);
main()
{
int a[10],i,result,n,key;
printf("enter array size");
scanf("%d",&n);
printf("enter array elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("elements in array are\n");
for(i=0;i<n;i++)
printf("\t%d",a[i]);
printf("enter search element");
scanf("%d",&key);
result=lsr(a,n,key);
if(result==1)
printf("\nelement found");
else
printf("\nelement not found");
}
int lsr(int a[10],int n,int key)
{
int c;
if(n<0)
{
c=-1;
return c;
}
else if (a[n]==key)
{

c=1;
printf("element is found at %d position",n);
return c;
}
else
lsr(a,n-1,key);
}
Input:
enter array size 3
enter array elements 1 4 5
elements in array are 1 4 5
enter search element 1
Output:
element is found at 0 position

element found
#include<stdio.h>
main()
{
int a[10],i,n,key;
printf("enter no.of elements\n");
scanf("%d",&n);
printf("enter elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter key\n");
scanf("%d",&key);
for(i=0;i<n;i++)
{
if(key==a[i])

break;
}
if(i==n)
printf("\n key not found");
else
printf("key found at %d position\n",i+1);
}
input:
enter no of elements 4
enter elements 3 4 7 9
enter key 4
output:
key found at 2 position
(B) Write c program that use both recursive and non-recursive functions to perform
binary search for a key value in a given list
RECURSIVE PROGRAM:
#include<stdio.h>
int binary(int a[],int,int,int,int);
main()
{
int a[10],i,n,m,c,l,u;
printf("enter no. of elements");
scanf("%d",&n);
printf("enter the elements of an array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter the number to be search");
scanf("%d",&m);
l=0,u=n-1;
c=binary(a,n,m,l,u);
if(c==1)
printf("number found");

else
printf("number not found");
}
int binary(int a[],int n,int m,int l,int u)
{
int mid,c=0;
if(l<=u)
{
mid=(l+u)/2;
//printf("%d",mid);
if(m==a[mid])
{
c=1;
printf("element found at position is %d",mid+1);
return c;
}
else if (m<a[mid])
return binary(a,n,m,l,mid-1);
else
return binary(a,n,m,mid+1,u);
}
}
input:
enter no of elements 3
enter the elements of an array 4 7 9
enter the number to be search 7
output:
element found at position is 2
number found
#include<stdio.h>

int bs(int a[],int,int);

main()
{
int a[10],n,i,result,key,mid;
scanf("%d",&n);
printf("enter the elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter search element");
scanf("%d",&key);
mid=bs(a,n,key);
if(mid>=0)
printf("element is found at %d position",mid);
if(mid==-1)
printf("element not found");
}
int bs(int a[10],int n,int key)
{
int low,mid,high;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(key==a[mid])
return mid;
else if(key<a[mid])
high=mid-1;
else
low=mid+1;
}
return -1;}
input:
enter array size 4
enter the elements 2 4 6 8
enter search element 5

output:
element not found.
(C) erite a c program that use both recursive and non recursivefunctions to perform
Fibonacci search for a key value in a given list
Recursive program
#include<stdio.h>
void main()
{
int n,a[50],i,key,loc,p,q,r,m,fk;
printf("\nenter number elements to be entered");
scanf("%d",&n);
printf("enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("enter the key element");
scanf("%d",&key);
fk=fib(n+1);
p=fib(fk);
q=fib(p);
r=fib(q) ;
m=(n+1)-(p+q);
if(key>a[p])
p=p+m;
loc=rfibsearch(a,n,p,q,r,key);
if(loc==0)
printf("key is not found");
else
printf("%d is found at location %d",key,loc);
}
int fib(int m)
{
int a,b,c;
a=0;
b=1;

c=a+b;
while(c<m)
{
a=b;
b=c;
c=a+b;
}
return b;
}
int rfibsearch(int a[],int n,int p,int q,int r,int key)
{
int t;
if(p<1||p>n)
return 0;
else if(key==a[p])
return p;
else if(key<a[p])
{
if(r==0)
return 0;
else
{
P=p-r
t=q;
q=r;
r=t-r;
return rfibsearch(a,n,p,q,r,key);
}
}
else
{
if(q==1)
return 0;
else
{
p=p+r;
q=q-r;
r=r-q;

return rfibsearch(a,n,p,q,r,key);
}
}
}
Non recursive program
#include <stdio.h>
//Utility function to find minimum of two elements

int min(int x, int y) { return (x<=y)? x : y; }
/* Returns index of x if present, else returns -1 */
int fibMonaccianSearch(int arr[], int x, int n)
{
/* Initialize fibonacci numbers */
int fibMMm2 = 0; // (m-2)'th Fibonacci No.
int fibMMm1 = 1; // (m-1)'th Fibonacci No.
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci
/* fibM is going to store the smallest Fibonacci

Number greater than or equal to n */
while (fibM < n)
{
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}
// Marks the eliminated range from front

int offset = -1;
/* while there are elements to be inspected. Note that

we compare arr[fibMm2] with x. When fibM becomes 1,
fibMm2 becomes 0 */
while (fibM > 1)
{
// Check if fibMm2 is a valid location
int i = min(offset+fibMMm2, n-1);
/* If x is greater than the value at index fibMm2,

cut the subarray array from offset to i */

if (arr[i] < x)
{
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
}
/* If x is greater than the value at index fibMm2,

cut the subarray after i+1 */
else if (arr[i] > x)
{
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
}
/* element found. return index */
else return i;
}
/* comparing the last element with x */
if(fibMMm1 && arr[offset+1]==x)return offset+1;
//element not found. return -1
return -1;
}
/* driver function */
int main(void)
{
int x,i,arr[10],n;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (i = 0; i < n; i++)

scanf("%d", &arr[i]);
printf("enter an element to search\n");
scanf("%d",&x);

printf("Found at index: %d",

fibMonaccianSearch(arr, x, n));
return 0;
}

EXERCISE:4
(A) Write c program that implement bubblesort,to sort a given list of integers in ascending order
#include<stdio.h>
void bubblesort(int a[10],int n);
main()
{
int a[10],i,n;
scanf("%d",&n);
printf("enter array elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
bubblesort(a,n);
}
void bubblesort(int a[10],int n)
{
int i,j,temp;
for(i=1;i<=n-1;i++)
{
for(j=0;j<=n-2;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("sorted array is:");
for(i=0;i<n;i++)
printf("\t%d",a[i]);
}
input:
enter array size 4

enter array elements 3 4 6 2
output:
sorted array is : 2 3 4 6
(B) Write c program that implement quick sort ,to sort a given list of integers in ascending order
#include<stdio.h>
void quicksort(int a[],int,int,int);
int partition(int a[],int,int);
main()
{
int a[10],n,i;
printf("enter size");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1,n);
}
void quicksort(int a[10],int l,int h,int n)
{
int j,i,p,q,temp;
if(l<h)
{
j=partition(a,l,h);
p=1;
q=n-1;
if(q>p)
{
if(q<j)
{
temp=a[p];
a[p]=a[q];
a[q]=temp;
p++;
}
else
q--;

}
else
{
temp=a[q];
a[q]=j;
j=a[q];
}
}
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
int partition(int a[10],int l,int h)
{
int pivot,t,i,j;
pivot=a[l];
i=l+1;
j=h;
while(i<=j)
{
while(pivot>a[i]&&i<=h)
i=i+1;
while(pivot<a[j]&&j>=l)
j=j-1;
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
a[l]=a[j];
a[j]=pivot;
return j;
}

Input:
enter size 4
output:
sorted array is: 2 4 6 8
(C) Write c program that implement insertion sort ,to sort a given list of integers in ascending
order
#include<stdio.h>
void insertionsort(int a[10],int n)
{
int i,k,j;
for(i=1;i<=n-1;i++)
{
k=a[i];
j=i-1;
while(k<a[j]&&j>=0)
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=k;
}
for(i=0;i<n;i++)
}
main()
{
int a[10],i,n;
scanf("%d",&n);

for(i=0;i<n;i++)
scanf("%d",&a[i]);
insertionsort(a,n);
}
input:
enter size 4
output:
sorted array is: 2 3 5 9

EXERCISE 5:
(A) Write c program that implement heap sort ,to sort a given list of integers in ascending
order
#include<stdio.h>
void heapify(int a[],int n)
{
int i,j,t;
for( i=n;i>=n/2;i--)
{
j=i;
while(a[j]>a[j/2] && j>=1)
{
t=a[j];
a[j]=a[j/2];
a[j/2]=t;
j=(j/2)+1;
}
}
}
void heapsort(int a[],int n)
{
int t;
while(n>1)
{
heapify(a,n);
t=a[n];
a[n]=a[1];
a[1]=t;
n=n-1;
}
}
void main()
{
int a[100],i,n;

scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("sorted array");
for(i=1;i<=n;i++)
}
input:
enter size 4
output:
sorted array 2 3 4 7
(B) Write c program that implement radixsort,to sort a given list of integers in ascending
order
#include<stdio.h>
// Function to find largest element
int largest(int a[], int n)
{
int large = a[0], i;
for(i = 1; i < n; i++)
{
if(large < a[i])
large = a[i];
}
return large;
}
// Function to perform sorting
void RadixSort(int a[],int n)
{
int bucket[10][10], bucket_count[10];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;

large = largest(a, n);

printf("The large element %d\n",large);
while(large > 0)
{
NOP++;
large/=10;
}
for(pass = 0; pass < NOP; pass++)
{
for(i = 0; i < 10; i++)
{
bucket_count[i] = 0;
}
for(i = 0; i < n; i++)
{
remainder = (a[i] / divisor) % 10;
bucket[remainder][bucket_count[remainder]] = a[i];
bucket_count[remainder] += 1;
}
i = 0;
for(k = 0; k < 10; k++)
{
for(j = 0; j < bucket_count[k]; j++)
{
a[i] = bucket[k][j];
i++;
}
}
divisor *= 10;
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
}
}
//program starts here
int main()
{
int i, n, a[10];

printf("Enter the number of elements :: ");

scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
RadixSort(a,n);
printf("The sorted elements are :: ");
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
Output:
Enter the number of elements :: 5
Enter the elements :: 2
4
23
100
35
The large element 100
100 2 23 4 35
100 2 4 23 35
2 4 23 35 100
The sorted elements are :: 2 4 23 35 100
(C) Write c program that implement merge sort ,to sort a given list of integers in ascending order
#include<stdio.h>
void merge(int a[],int,int,int);
void ms(int a[10],int l,int h)
{
int m;
if(l<h)
{
m=(l+h)/2;
ms(a,l,m);
ms(a,m+1,h);

merge(a,l,m,h);
}
}
void merge(int a[10],int l,int m,int h)
{
int i,j,k,b[100];
i=l;
j=m+1;
k=l;
while(i<=m && j<=h)
{
if(a[i]<a[j])
{
b[k]=a[i];
k++;
i++;
}
else
{
b[k]=a[j];
k++;
j++;
}
}
while(i<=m)
{
b[k]=a[i];
k++;
i++;
}
while(j<=h)
{
b[k]=a[j];
k++;
j++;
}
for(k=l;k<=h;k++)
a[k]=b[k];

}
void main()
{
int a[10],i,n;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
ms(a,0,n-1);
printf("sorted array");
for(i=0;i<n;i++)
}
input:
enter size 4
output:
sorted array 1 3 4 6

EXERCISE 6:
(A) Write c program that implement stack(its operations)using arays.
#include<stdio.h>
#define MAX 10
void insert();
void delete();
void display();
int stack[MAX],top=-1;
int main()
{
int option;
printf("\n program on stack");
do
{
printf("\n\n1.insert an element");
printf("\n2.delete an element");
printf("\n 3.display stack");
printf("\n4.exit");
printf("\nenter your choice");
scanf("%d",&option);
switch(option)
{
case 1: insert();
break;
case 2: delete();
break;
case 3: display();
break;
case 4: return 0;
}
}while(option!=4);
}
void insert()
{
int num;
printf("enter the number to be inserted");

scanf("%d",&num);
if(top==9)
printf("\nstack is full");
else
stack[++top]=num;
}
void delete()
{
int element;
if(top==-1)
{
printf("\n stack is empty");
}
else
{
element=stack[top--];
printf("\n popped element is %d",element);
}
}
void display()
{
int i;
if(top==-1)
printf("stack is empty");
else
{
for(i=top;i>-1;i--)
printf("\n%d",stack[i]);
}
}
OUTPUT:
program on stack
1.insert an element
2.delete an element
3.display stack

4.exit
enter your choice1
enter the number to be inserted12
1.insert an element
2.delete an element
3.display stack
4.exit
enter your choice1
1.insert an element
2.delete an element
3.display stack
4.exit
enter your choice1
1.insert an element
2.delete an element
3.display stack
4.exit
enter your choice3
56
34
12
1.insert an element
2.delete an element
3.display stack
4.exit
enter your choice2
popped element is 56
1.insert an element
2.delete an element
3.display stack

4.exit
enter your choice4
(B) Write c program that implement stack(its operations)using linked list.

#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
}*top = NULL;
void push(int);
void pop();
void display();
void main()
{
int choice, value;
printf("\n:: Stack using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)

{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}

OUTPUT :
:: Stack using Linked List ::
****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the value to be insert: 10
Insertion is Success!!!
****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
20--->10--->NULL
****** MENU ******
1. Push
2. Pop
3. Display
4. Exit
Deleted element: 20

****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
10--->NULL
****** MENU ******
1. Push
2. Pop
3. Display
4. Exit
(c )Write a c program that uses stack operations to convert infix expression to postfix
expression
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define size 50
char s[size];
int top=-1;
push(char elem)
{
s[++top]=elem;
}
char pop()
{
return s[top--];
}
int pr(char elem)
{
switch(elem)
{
case '#':return 0;
case '[':return 1;
case '+':
case '-':return 2;
case '*':

case '/':return 3;
}
}
int main()
{
char infix[50],postfix[50],ch,elem;
int i=0,k=0;
printf("\nRead infix expression");
gets(infix);
printf("\n%s",infix);
push('#');
while((ch=infix[i++])!='\0')
{
if(ch=='[')
push(ch);
else if(isalnum(ch))
{
postfix[k++]=ch;
}
else
if(ch==']')
{
while(s[top]!='[')
postfix[k++]=pop();
elem=pop();
}
else
{
while(pr(s[top])>=pr(ch))
postfix[k++]=pop();
push(ch);
}
}
while(s[top]!='#')
postfix[k++]=pop();

postfix[k]='\0';
printf("Infix:%s \n postfix: %s",infix,postfix);

return 0;
}
OUTPUT:
Read infix expression
a+b*c-d/e
Infix:a+b*c-d/e
postfix: abc*+de/-

EXERCISE 7:
(a) Write a c program that implement queue(its operations) using arrays.
#include<stdio.h>
#define MAX 100
void insert();
void delete();
void display();
int queue[MAX],front=-1,rear=-1;
int main()
{
int option;
printf("\n program on queue");
do
{
printf("\n\n1.insert an element");
printf("\n2.delete an element");
printf("\n 3.display queue");
printf("\n4.exit");
printf("\nenter your choice");
switch(option)
{
case 1: insert();
break;
case 2: delete();
break;
case 3: display();
break;
case 4: return 0;
}
}while(option!=4);
}
void insert()
{
int num;//10,20,30,40
printf("enter the number to be inserted");

scanf("%d",&num);
if(front==0 && rear==MAX-1)//front=-1
printf("\noverflow");
else if(front==-1 && rear==-1)
{
front=0;
rear=0;
queue[rear]=num;//queue[0]=10
}
else if(rear==MAX-1 && front!=0)
{
rear=0;
queue[rear]=num;
}
else
{
rear++;//rear=1,rear=2,rear=3
queue[rear]=num;//queue[1]=20,queue[2]=30,queue[3]=40
}
}
void delete()
{
int element;
if(front==-1)
{ printf("\n underflow");
}
element=queue[front];
if(front==rear)
front=rear=-1;
else
{
if(front==MAX-1)
front=0;
else
front++;
printf("\n deleted element is %d",element);
}
}

void display()
{
int i;
if(front==-1)
printf("queue is empty");
else
{
for(i=front;i<=rear;i++)
{
printf("\n%d",queue[i]);
}
}
}
OUTPUT
program on queue
1.insert an element
2.delete an element
3.display queue
4.exit
enter your choice1
1.insert an element
2.delete an element
3.display queue
4.exit
enter your choice1
1.insert an element
2.delete an element
3.display queue
4.exit
enter your choice1

1.insert an element
2.delete an element
3.display queue
4.exit
enter your choice3
12
45
67
1.insert an element
2.delete an element
3.display queue
4.exit
enter your choice2
deleted element is 12
1.insert an element
2.delete an element
3.display queue
4.exit
enter your choice4
(b) Write a c program that implements queue (its operations) using linked list
#include<stdio.h>
//#include<conio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
}*front = NULL,*rear = NULL;
void insert(int);
void delete();
void display();

void main()
{
int choice, value;
//clrscr();
printf("\n:: Queue Implementation using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
insert(value);
break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void insert(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode -> next = NULL;
if(front == NULL)
front = rear = newNode;
else{
rear -> next = newNode;
rear = newNode;
}
printf("\nInsertion is Success!!!\n");
}
void delete()
{

if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
front = front -> next;
printf("\nDeleted element: %d\n", temp->data);
free(temp);
}
}
void display()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
struct Node *temp = front;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL\n",temp->data);
}
}
Output:
:: Queue Implementation using Linked List ::
****** MENU ******

1. Insert
2. Delete
3. Display
4. Exit
****** MENU ******

1. Insert
2. Delete

3. Display
4. Exit
****** MENU ******

1. Insert
2. Delete
3. Display
4. Exit
****** MENU ******

1. Insert
2. Delete
3. Display
4. Exit
12--->23--->34--->NULL
****** MENU ******

1. Insert
2. Delete
3. Display
4. Exit
Deleted element: 12
****** MENU ******
1. Insert
2. Delete
3. Display
4. Exit

EXERCISE 8:
(A) WRITE A C PROGRAM THAT USES FUNCTIONS TO CREATE A SINGLE LINKED
LIST
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*start=NULL;
void create()
{
char ch;
do
{
struct node *newnode,*current;
newnode=(struct node *)malloc(sizeof(struct node));
printf("\n enter the data");
scanf("%d",&newnode->data);
newnode->next=NULL;
if(start==NULL)
{
start=newnode;
current=newnode;
}
else
{
current->next=newnode;
current=newnode;
}
printf("\n do you want to create another");
scanf("\n%c",&ch);
}while(ch!='n');
}
void display()
{

struct node *newnode;

printf("the linked list is:");
newnode=start;
while(newnode!=NULL)
{
printf("%d-->",newnode->data);
newnode=newnode->next;
}
printf("NULL");
}
main()
else
{
current=newnode;
}
scanf("\n%c",&ch);
}while(ch!='n');
}
void display()
{
printf("the linked list is:");
newnode=start;
{
printf("%d-->",newnode->data);
}
printf("NULL");
}
main()
{
{
create();
display();
}

OUTPUT :
:: Stack using Linked List ::
****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
****** MENU ******

1. Push
2. Pop
3. Display
4. Exit
20--->10--->NULL
****** MENU ******
1. Push
2. Pop
3. Display
4. Exit

Deleted element: 20
****** MENU ******
1. Push
2. Pop
3. Display
4. Exit
10--->NULL
****** MENU ******
1. Push
2. Pop
3. Display
4. Exit
b) Write a c program that uses functions to perform insertion operation on a singly

linked list
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*start=NULL;
void create()
{
char ch;
do
{
struct node *new_node,*current;
new_node=(struct node *)malloc(sizeof(struct node));
printf("\nEnter the data");
scanf("%d",&new_node->data);
new_node->next=NULL;
if(start==NULL)
{
start=new_node;
current=new_node;

}
else
{
current->next=new_node;
current=new_node;
}
printf("\nDo you want to create another:");
scanf("\n%c",&ch);
}while(ch!='n');
}
void display()
{
struct node *new_node;
printf("The linked list :\n");
new_node=start;
while(new_node!=NULL)
{
printf("%d---->",new_node->data);
new_node=new_node->next;
}
printf("NULL");
}
void insert_at_beg()
{
if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{
new_node->next=start;
start=new_node;

}
}
void insert_at_end()
{
struct node *new_node,*current,*temp;
if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{
temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=new_node;
}
}
void insert_at_sp()
{
int pos,i;
struct node *new_node,*current,*temp,*temp1;
if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{
printf("\nEnter the position where the data has to be inserted\n");

scanf("%d",&pos);
temp=start;
for(i=0;i<pos-1;i++)
temp=temp->next;
temp1=temp->next;
temp->next=new_node;
new_node->next=temp1;
}
}
int main()
{
char ch;
int option;
create();
display();
do
{
printf("\n1.insert at begining");
printf("\n2.insert at end");
printf("\n3.insert at specified position");
printf("\n4.exit");
printf("\n enter your choice");
switch (option)
{
case 1: insert_at_beg();
break;
case 2: insert_at_end();
break;
case 3: insert_at_sp();
break;
case 4:return 0;
}
display();
printf("\n do u want to do another operation");
scanf("\n%c",&ch);
}
while(ch!='n');

display();
}
OUTPUT :-
Enter the data10
Do you want to create another:y
Enter the data20
Do you want to create another:n

The linked list :
10---->20---->NULL
1.insert at begining
2.insert at end
3.insert at specified position
4.exit
enter your choice1
Enter the data5

The linked list :
5---->10---->20---->NULL
do u want to do another operationy
2.insert at end
4.exit
enter your choice2
Enter the data25

The linked list :
5---->10---->20---->25---->NULL
do u want to do another operationy
2.insert at end

4.exit
enter your choice3
Enter the data30
Enter the position where the data has to be inserted

4
The linked list :
5---->10---->20---->25---->30---->NULL
do u want to do another operationn
The linked list :
5---->10---->20---->25---->30---->NULL
(c )Write a c program to perform deletion operation operation in a singly linked list
#iinclude<stdio.h>
#include<ctype.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*start=NULL;
void create()
{
char ch;
do
{
if(start==NULL)
{
start=new_node;
current=new_node;
}
else
{

current->next=new_node;
current=new_node;
}
printf("\nDo you want to create another:");
scanf("\n%c",&ch);
}while(ch!='n');
}
void display()
{
struct node *new_node;
printf("The linked list :\n");
new_node=start;
while(new_node!=NULL)
{
printf("%d---->",new_node->data);
new_node=new_node->next;
}
printf("NULL");
}
void del_beg()
{
struct node*temp;
temp=start;
start=start->next;
free(temp);
printf("\n element is deleted");
}
void del_end()
{
int count=0,i;
struct node *temp,*temp1;
temp=start,temp1=start;
while (temp->next!=NULL)
{
count++;
temp=temp->next;
}
for(i=0;i<count-1;i++)

{
temp1=temp1->next;
}
temp1->next=NULL;
free(temp);
}
void del_specifiedposition()
{
int pos,i;
struct node *temp,*temp1,*temp2;
temp=start;
temp1=start;
temp2=start;
printf("enter position");
scanf("%d",&pos);
for(i=0;i<pos;i++)
{
temp=temp->next;
}
temp1=temp->next;
for(i=0;i<pos-1;i++)
{
temp2=temp2->next;
}
temp2->next=temp1;
free(temp);
}
main()
{
char ch;
int option;
create();
display();
do
{
printf("1.delete at the beginning\n");
printf("2.delete at the end\n");
printf("3.delete at the specified position\n");

printf("4.exit\n");
printf("enter option");
switch(option)
{
case 1:del_beg();
break;
case 2:del_end();
break;
case 3:del_specifiedposition();
break;
case 4:return 0;
}
display();
printf(" do yopu want to do another operation");
scanf("%d",&ch);
}while(ch!='n');
display();
}
Output:
Enter the data12
Enter the data23
Enter the data34
Enter the data45
Do you want to create another:n
The linked list :
12---->23---->34---->45---->NULL1.delete at the beginning
2.delete at the end
3.delete at the specified position
4.exit
enter option1
element is deletedThe linked list :
23---->34---->45---->NULL do yopu want to do another operation2
1.delete at the beginning
2.delete at the end


4.exit
enter option3
enter position1
The linked list :
23---->45---->NULL do yopu want to do another operationn
1.delete at the beginning
2.delete at the end
4.exit

EXERCISE 9:
(a) Adding two large integers which are represented in linked list fashion
#include<stdlib.h>
#include<stdio.h>
typedef struct node{

int data;
struct node *next;
} Node;
int length( Node * head ){

int len = 0;
Node * current = head;
while(current){
len++;
current = current->next;
}
return len;
}
Node * createNode(int value)

{
Node * newNode = (Node *)malloc(sizeof(Node));
newNode->next = NULL;
return newNode;
/* Addition of a node to linked list */

void push(Node **head, int value){
Node *newNode = createNode (value);

if(!(*head) ){
*head = newNode;

}
else{
newNode->next = (*head);
*head = newNode;
}
}
/* This function is actually helper function which
* does all house keeping like calculating lengths of lists,
* calling recursive implementation, creating extra
* node for carry in MSD,and adding any remaining nodes
* left in longer list. */
/* result is pointer to pointer to the head of resulting node */

void addTwoNumbers(Node *L1, Node *L2, int *carry, Node **result){
int len1 = length( L1 );
int len2 = length( L2 );
int diff = 0;
if(len1 < len2){

Node * current = L1;
L1 = L2;
L2 = current;
}
diff = abs(len1-len2)
Node * current = L1;
while(diff--)
/* Call the recursive implementation */

addListRecursively(current, L2, carry, result);
diff = abs(len1-len2);
/* Add remaining nodes in longer list */

addRemainingDigits(L1, carry, result, diff);
if(*carry){

push(result, *carry);
}
return;
}
void addListRecursively(Node *L1, Node *L2, int *carry, Node **result){
int sum;
if(!L1)
return;
addListRecursively(L1->next, L2->next, carry, result);
/*We have reached the last node of both lists, add them */
sum = L1->data + L2->data + (*carry);
int value = sum%10;

*carry = sum/10;
push(result, value);
return;
}
void addRemainingDigits(Node *L1, int *carry, Node **result, int diff){

int sum = 0;
if(!L1 || !diff)
return;
addRemainingDigits(L1->next, carry, result, diff-1);
sum = L1->data + (*carry);

int value = sum%10;
*carry = sum/10;
push(result, value);
return;
}

void printList( Node * head ){

Node * current = head;
while(current){
printf("%d ->", current->data);
}
printf("NULL");
}
/* Driver program to run above code */
int main()
{
int d;
Node * L1 = NULL;
Node * L2 = NULL;
Node * result = NULL;
int carry = 0;
/* creating list 1 */
push(&L1,3);
push(&L1,4);
push(&L1,6);
push(&L1,7);
/* creating list 2 */
push(&L2,8);
push(&L2,9);
push(&L2,7);
printList(L1);
printf("\n");
printList(L2);
addTwoNumbers(L1,L2, &carry, &result);

printf("\n");
printList(result);
return 0;
}

Output:
7 ->6 ->4 ->3 ->NULL
7 ->9 ->8 ->NULL
8 ->4 ->4 ->1 ->NULL
9(b) Write a c program to reverse elements of a single linked list

#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
struct node
{
int data;
struct node*next;
}*start=NULL;
void create()
{
char ch;
do
{
struct node *newnode,*current;
newnode=(struct node*)malloc(sizeof(struct node));
printf("\n enter the data");
scanf("%d",&newnode->data);
newnode->next=NULL;
if(start==NULL)
{
start=newnode;
current=newnode;
}
else
{
current=newnode;
}
scanf("\n %c",&ch);
}while(ch!='n');
}

void display()
{
printf("the linked list:\n");
newnode=start;
{
printf("%d--->",newnode->data);
}
printf("null");
}
void reverse()
{
struct node *prev,*current,*next;
current=start;
prev=NULL;
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
start=prev;
}
main()
{
create();
display();
reverse();
display();
}
Output:
enter the data12
do you want to create anothery

enter the data32
enter the data45
enter the data56
enter the data67
enter the data78
enter the data89
enter the data90
do you want to create anothern

the linked list:
12--->32--->45--->56--->67--->78--->89--->90--->nullthe linked list:
90--->89--->78--->67--->56--->45--->32--->12--->null
9(C) Aim: Write a c program to store a polynomial expression in memory using linked
list
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
struct poly
{

int coefficient;
int exp;
struct poly *next;
}*head=NULL;
void create()
{
char ch;
do
{
struct poly *newnode,*current;
newnode=(struct poly *)malloc(sizeof(struct poly));
printf("\nenter the coeficient");
scanf("%d",&newnode->coefficient);
printf("\nenter the exponent");
scanf("%d",&newnode->exp);
newnode->next=NULL;
if (head==NULL)
{
head=newnode;
current=newnode;
}
else
{
current=newnode;
}
scanf("\n%c",&ch);
}while(ch!='n');
}
void display()
{
struct poly *newnode;
printf("the polynomial expression :\n");
newnode=head;
{
if(newnode->exp!=0)

{
printf("%dx^%d+",newnode->coefficient,newnode->exp);
}
else
printf("%dx^%d",newnode->coefficient,newnode->exp);
}
}
main()
{
create();
display();
}
Output:
enter the coeficient5
enter the exponent5
enter the exponent4
enter the exponent3
enter the exponent2
enter the exponent1

enter the exponent0

do you want to create anothern
the polynomial expression :
5x^5+4x^4+3x^3+2x^2+1x^1+9x^0
9(D) Write a c program to represent the given sparse matrix using arrays
#include<stdio.h>
int main()
{
int i,j,k;
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
int size = 0;
for (i = 0; i < 4; i++)
for (j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
int compactMatrix[3][size];
for (i = 0; i < 4; i++)
for (j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
for (i=0; i<3; i++)
{
for (j=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);
printf("\n");

}
return 0;
}
Output :
0 2 3
0 4 4
1 2 5
1 3 7
3 1 2
3 2 6
9(E) Write a c program to represent the given sparse matrix using linked list
#include <stdio.h>
#include <stdlib.h>
/* structure to store data */

struct node {
int row, col, val;
struct node *right, *down;
};
/* structure of column head */

struct chead {
int col;
struct chead *next;
struct node *down;
};
/* structure of row head */

struct rhead {
int row;
struct rhead *next;
struct node *right;
};

struct sparsehead {
int rowCount, colCount;
struct rhead *frow;
struct chead *fcol;
};
/* main node */
struct sparse {
int row, *data;
struct node *nodePtr;
struct sparsehead *smatrix;
struct rhead **rowPtr;
struct chead **colPtr;
};
int count = 0;
/* Establish row and column links */

void initialize(struct sparse *sPtr, int row, int col) {
int i;
sPtr->rowPtr = (struct rhead **) calloc(1, (sizeof (struct rhead) * row));
sPtr->colPtr = (struct chead **) calloc(1, (sizeof (struct chead) * col));
for (i = 0; i < row; i++)
sPtr->rowPtr[i] = (struct rhead *) calloc(1, sizeof (struct rhead));
for (i = 0; i < row - 1; i++) {

sPtr->rowPtr[i]->row = i;
sPtr->rowPtr[i]->next = sPtr->rowPtr[i + 1];
}
for (i = 0; i < col; i++)

sPtr->colPtr[i] = (struct chead *) calloc(1, sizeof (struct chead));
for (i = 0; i < col - 1; i++) {

sPtr->colPtr[i]->col = i;
sPtr->colPtr[i]->next = sPtr->colPtr[i + 1];
}

/* update additional head information */

sPtr->smatrix = (struct sparsehead *) calloc(1, sizeof (struct sparsehead));
sPtr->smatrix->rowCount = row;
sPtr->smatrix->colCount = col;
sPtr->smatrix->frow = sPtr->rowPtr[0];
sPtr->smatrix->fcol = sPtr->colPtr[0];
return;
}
/* input sparse matrix */

void inputMatrix(struct sparse *sPtr, int row, int col) {
int i, n, x = 0, y = 0;
n = row * col;
sPtr->data = (int *) malloc(sizeof (int) * n);
for (i = 0; i < n; i++) {
if (y != 0 && y % col == 0) {
x++;
y = 0;
}
printf("data[%d][%d] : ", x, y);
scanf("%d", &(sPtr->data[i]));
if (sPtr->data[i])
count++;
y++;
}
return;
}
/* display sparse matrix */

void displayInputMatrix(struct sparse s, int row, int col) {
int i;
for (i = 0; i < row * col; i++) {
if (i % col == 0)
printf("\n");
printf("%d ", s.data[i]);
}
printf("\n");

return;
}
/* create 3-tuple array from input sparse matrix */

void createThreeTuple(struct sparse *sPtr, struct sparse s, int row, int col) {
int i, j = 0, x = 0, y = 0, l = 0;
struct node *n1, *n2;
struct sparsehead *smat = sPtr->smatrix;
int i, j;
/* update node values */

sPtr->nodePtr = (struct node *) malloc(sizeof (struct node));
sPtr->nodePtr->row = row;
sPtr->nodePtr->col = col;
sPtr->nodePtr->val = val;
/* get the row headnode */

rPtr = smat->frow;
/* move to corresponding row */

for (i = 0; i < row; i++)
rPtr = rPtr->next;
/* traverse the nodes in current and locate new node */

n1 = rPtr->right;
if (!n1) {
rPtr->right = sPtr->nodePtr;
sPtr->nodePtr->right = NULL;
}
else {
sPtr->row = count;
sPtr->data = (int *) malloc(sizeof (int) * (sPtr->row * 3));
for (i = 0; i < row * col; i++) {

if (y % col == 0 && y != 0) {
x++;
y = 0;
}

if (s.data[i] != 0) {
sPtr->data[l++] = x;
sPtr->data[l++] = y;
sPtr->data[l++] = s.data[i];
}
y++;
}
return;
}
/* insert element to the list */

void insert(struct sparse *sPtr, int row, int col, int val) {
struct rhead *rPtr;
struct chead *cPtr;
struct node *n1, *n2;
struct sparsehead *smat = sPtr->smatrix;
int i, j;
/* update node values */

sPtr->nodePtr = (struct node *) malloc(sizeof (struct node));
sPtr->nodePtr->row = row;
sPtr->nodePtr->col = col;
sPtr->nodePtr->val = val;
/* get the row headnode */

rPtr = smat->frow;
/* move to corresponding row */

for (i = 0; i < row; i++)
rPtr = rPtr->next;
/* traverse the nodes in current and locate new node */

n1 = rPtr->right;
if (!n1) {
rPtr->right = sPtr->nodePtr;
} else {
while (n1 && n1->col < col) {

n2 = n1;
n1 = n1->right;
}
n2->right = sPtr->nodePtr;
}
/* get the column head node */

cPtr = sPtr->smatrix->fcol;
/* move to corresponding column (1/2/3..) */

for (i = 0; i < col; i++)
cPtr = cPtr->next;
n1 = cPtr->down;
if (!n1) {
cPtr->down = sPtr->nodePtr;
sPtr->nodePtr->down = NULL;
} else {
while (n1 && n1->row < row) {
n2 = n1;
n1 = n1->down;
}
n2->down = sPtr->nodePtr;
sPtr->nodePtr->down = NULL;
}
return;
}
/* create list for 3-Tuple representation */

void createList(struct sparse *sPtr) {
int i, j = 0;
for (i = 0; i < sPtr->row; i++) {
insert(sPtr, sPtr->data[j], sPtr->data[j + 1], sPtr->data[j + 2]);
j = j + 3;
}
return;
}

/* Display data from linked list of 3-Tuple*/

void displayList(struct sparse s) {
struct node *n;
int row = s.smatrix->rowCount, i;
for (i = 0; i < row; i++) {
n = s.rowPtr[i]->right;
if (n) {
while (n->right) {
printf("%d %d %d\n", n->row, n->col, n->val);
n = n->right;
}
if (n->row == i) {
printf("%d %d %d\n", n->row, n->col, n->val);
}
}
}
printf("\n");
}
int main() {
struct sparse input, output;
int row, col;
printf("Enter the rows and columns:");
scanf("%d%d", &row, &col);
initialize(&input, row, col);
initialize(&output, row, col);
inputMatrix(&input, row, col);
printf("Given Sparse Matrix has %d non-zero elements\n", count);
printf("Input Sparse Matrix:\n");
displayInputMatrix(input, row, col);
printf("\n\n");
createThreeTuple(&output, input, row, col);
createList(&output);
printf("3-Tuple representation of the given sparse matrix:\n");
printf("%d %d %d\n", output.smatrix[0].rowCount,
output.smatrix[0].colCount, count);
displayList(output);

return 0;
}
Output
Enter the rows and columns:4 5
data[0][0] : 0
data[0][1] : 0
data[0][2] : 0
data[0][3] : 2
data[0][4] : 0
data[1][0] : 0
data[1][1] : 1
data[1][2] : 00
data[1][3] : 0
data[1][4] : 3
data[2][0] : 00
data[2][1] : 0
data[2][2] : 5
data[2][3] : 0
data[2][4] : 0
data[3][0] : 6
data[3][1] : 0
data[3][2] : 0
data[3][3] : 7
data[3][4] : 0
Given Sparse Matrix has 6 non-zero elements
Input Sparse Matrix:
00020
01003
00500
60070
3-Tuple representation of the given sparse matrix:
4 5 6
0 3 2
1 1 1
1 4 3
2 2 5
3 0 6
3 3 7

Exercise:10
(a) write a c program to create a binary tree of integers
(b) Write a recursive c program for traversing a binary tree in preorder, inorder,
postorder
(c) Write a non recursive c program for traversing a binary tree in preorder,
inorder,postorder
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct bint

{
int data,flag;
struct bint *left,*right;
}node;
node * create(node *r,int d)

{
if(r == NULL)
{
r = (node *)malloc(sizeof(node));
r->data = d;
r->left = r->right = NULL;
}
else
{
if(r->data <= d)
r->right = create(r->right,d);
else
r->left = create(r->left,d);
}
return r;
}

void inorder(node *r)

{
if(r != NULL)
{
inorder(r->left);
printf("%d\t",r->data);
inorder(r->right);
}
}
void non_in(node *r)
{
int top=0;
node *s[20],*pt=r;
s[0]=NULL;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
pt = s[top--];
while(pt != NULL)
{
printf("%d\t",pt->data);
if(pt->right != NULL)
{
pt = pt->right;
while(pt != NULL)
{
s[++top] = pt;
pt = pt->left;
}
}
pt = s[top--];
}
}

void preorder(node *r)

{
if(r != NULL)
{
preorder(r->left);
preorder(r->right);
}
}
void non_pre(node *r)
{
int top=0;
node *s[20],*pt=r;
s[0]=NULL;
while(pt != NULL)
{
printf("%d\t",pt->data);
if(pt->right != NULL)
s[++top] = pt->right;
if(pt->left != NULL)
pt = pt->left;
else
pt = s[top--];
}
}
void postorder(node *r)

{
if(r != NULL)
{
postorder(r->left);
postorder(r->right);
}
}
void non_post(node *root)

{

node *stack[100];
int top=-1;
node *temp=root;
while(temp!=NULL)
{
while(temp!= NULL)
{
top++;
stack[top] = temp;
temp = temp->left;
}
label:temp =stack[top];
top--;
if(temp->flag==1)
{
printf("%d\t",temp->data);
break;
}
else
{
temp->flag=1;
top++;
stack[top] = temp;
temp=temp->right;
}
}
if(top>=0)
goto label;
}
void main()
{
int d;
char ch = 'Y';
node *head = NULL;
//clrscr();
while(toupper(ch) == 'Y')
{
printf("\n Enter the item to insert");

scanf("%d",&d);
head = create(head,d);
printf("\n Do you want to continue(y/n)");
//fflush(stdin);
ch = getchar();
}
printf("\ninorder recursive\n");
inorder(head);
printf("\ninorder non recursive);
non_in(head);
printf("\n\n");
printf("\npostorder rrecursive\n");
postorder(head);
printf("\npostorder non recursive\n");
non_post(head);
printf("\n\n");
printf("\npreorder recursive\n");
preorder(head);
printf("\npreorder non recursive\n");
non_pre(head);
getch();

Output:
Enter item to insert 12

Do you want to continue y
Do you want to continue n
Inorder recursive
4 5 7 9 12 23
Inorder nonrecursive
4 5 7 9 12 23
Postorder recursive
4 7 5 9 23 12
Postorder nonrecursive
4 7 5 9 23 12
Preorder recursive
12 9 5 4 7 23
Preorder nonrecursive
12 9 5 4 7 23

Exercise 11:
(a) Write a c program to create a bst
(b) Write a c program to insert a node into a bst
(c) Write a c program to delete a node from bst
Program:
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;
void delete1();
void insert();
void delete();
void inorder(struct btnode *t);
void create();
void search(struct btnode *t);
void preorder(struct btnode *t);
void postorder(struct btnode *t);
void search1(struct btnode *t,int data);
int smallest(struct btnode *t);
int largest(struct btnode *t);
int flag = 1;
void main()
{
int ch;
printf("\nOPERATIONS ---");
printf("\n1 - Insert an element into tree\n");

printf("2 - Delete an element from the tree\n");

printf("3 - Inorder Traversal\n");
printf("4 - Preorder Traversal\n");
printf("5 - Postorder Traversal\n");
printf("6 - Exit\n");
while(1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
inorder(root);
break;
case 4:
preorder(root);
break;
case 5:
postorder(root);
break;
case 6:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
}
/* To insert a node in the tree */

void insert()
{

create();
if (root == NULL)
root = temp;
else
search(root);
}
/* To create a node */
void create()
{
int data;
printf("Enter data of node to be inserted : ");

scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}
/* Function to search the appropriate position to insert the new node */

void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL)) /* value more than root node
value insert at right */
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL)) /* value less than root node
value insert at left */
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}
/* recursive function to perform inorder traversal of tree */

void inorder(struct btnode *t)
{
if (root == NULL)

{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}
/* To check for the deleted node */

void delete()
{
int data;
if (root == NULL)
{
printf("No elements in a tree to delete");
return;
}
printf("Enter the data to be deleted : ");
scanf("%d", &data);
t1 = root;
t2 = root;
search1(root, data);
}
/* To find the preorder traversal */

void preorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)

preorder(t->l);
if (t->r != NULL)
preorder(t->r);
}
/* To find the postorder traversal */

void postorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display ");
return;
}
if (t->l != NULL)
postorder(t->l);
postorder(t->l);
if (t->r != NULL)
postorder(t->r);
}
/* Search for the appropriate position to insert the new node */

void search1(struct btnode *t, int data)
{
if ((data>t->value))
{
t1 = t;
search1(t->r, data);
}
else if ((data < t->value))
{
t1 = t;
search1(t->l, data);
}
else if ((data==t->value))
{
delete1(t);
}

/* To delete a node */
void delete1(struct btnode *t)
{
int k;
/* To delete leaf node */

if ((t->l == NULL) && (t->r == NULL))
{
if (t1->l == t)
{
t1->l = NULL;
}
else
{
t1->r = NULL;
}
else
{
t1->r = NULL;
}
t = NULL;
free(t);
return;
}
/* To delete node having one left hand child */

else if ((t->r == NULL))
{
if (t1 == t)
{
root = t->l;
t1 = root;
}
else if (t1->l == t)
{
t1->l = t->l;

}
else
{
t1->r = t->l;
}
t = NULL;
free(t);
return;
}
/* To delete node having right hand child */

else if (t->l == NULL)
{
if (t1 == t)
{
root = t->r;
t1 = root;
}
}
else if (t1->r == t)
t1->r = t->r;
else
t1->l = t->r;
t == NULL;
free(t);
return;
}
/* To delete node having two child */

else if ((t->l != NULL) && (t->r != NULL))
{
t2 = root;
if (t->r != NULL)
{
k = smallest(t->r);
flag = 1;
}

else
{
k =largest(t->l);
flag = 2;
}
search1(root, k);
t->value = k;
}
/* To find the smallest element in the right sub tree */

int smallest(struct btnode *t)
{
t2 = t;
if (t->l != NULL)
{
t2 = t;
return(smallest(t->l));
}
Else
return (t->value);
}
/* To find the largest element in the left sub tree */

int largest(struct btnode *t)
{
if (t->r != NULL)
{
t2 = t;
return(largest(t->r));
}
else
return(t->value);
}

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 : 12
12 -> 3 -> 34 -> 45 -> 67 -> 56 -> 78 ->
Enter the data to be deleted : 45
12 -> 3 -> 34 -> 67 -> 56 -> 78 ->
Enter your choice :6

Mca Ds Lab Manual

Uploaded by

Copyright:

Available Formats

Mca Ds Lab Manual

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mca Ds Lab Manual

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES LAB I MCA II SEMESTER

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 1

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 2

int gcd(int a,int b)

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 3

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 4

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 5

NON RECURSIVE PROGRAM

struct Stack_Structure* createStack(int max)

int isEmpty(struct Stack_Structure* stack_object)

int isFull(struct Stack_Structure* stack_object)

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 6

void display_shift(char fromTower, char toTower, int disk)

void add_element(struct Stack_Structure *stack_object, int item)

int remove_element(struct Stack_Structure* stack_object)

void shift_Disks(struct Stack_Structure *source_tower, struct Stack_Structure

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 7

void tower_of_hanoi(int limit, struct Stack_Structure *source_tower, struct Stack_Structure

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 8

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 9

Enter The Number of Disks: 3

Sequence of Disk Moves:

Move Disk 1 from 'S' to 'D'

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 10

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 11

element is found at 0 position

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 12

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 13

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 14

int bs(int a[],int,int);

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 15

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 16

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 17

//Utility function to find minimum of two elements

/* fibM is going to store the smallest Fibonacci

// Marks the eliminated range from front

/* while there are elements to be inspected. Note that

/* If x is greater than the value at index fibMm2,

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 18

cut the subarray array from offset to i */

/* If x is greater than the value at index fibMm2,

printf("Enter %d integers\n", n);

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

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 19

printf("Found at index: %d",

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 20

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 21

enter array elements 3 4 6 2

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 22

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 23

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 24

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 25

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 26

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 27

large = largest(a, n);

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 28

printf("Enter the number of elements :: ");

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 29

VIGNANS LARA INSTITUTE OF TECHNOLOGY & SCIENCE 30

MENU

MENU

MENU

MENU

MENU

MENU

MENU

MENU

MENU

MENU

MENU

MENU

void addListRecursively(Node L1, Node L2, int *carry, Node **result){

void addRemainingDigits(Node L1, int carry, Node **result, int diff){