Sl.
No. |
Assignment
|
Page No.
|
1.
|
Write a menu driven program in C that implements the following
searching method - (a) Linear Search, (b) Binary Search. |
2-3
|
2.
|
Write a menu driven program in C that implements the following
sorting method - (a) Bubble Sort, (b) Selection Sort, (c) Insertion Sort, (d) Quick Sort, (e) Merge Sort, (f) Heap Sort. |
4-10
|
3.
|
Write a program in C that implements Stack. Use dynamic memory
allocation. |
10-11
|
4.
|
Write a program in C that implements Queue. Use dynamic memory
allocation. |
12-13
|
5.
|
Write a program in C that implements Circular Queue. Use dynamic
memory allocation. |
13-15
|
6.
|
Write a program in C that implements Singly Linked list and performs
the following- (a) Insert at any position, (b) Delete from any position, (c) Reverse, (d) Remove duplicate elements. |
15-23
|
7.
|
Write a program in C that implements Binary tree and traverse the
tree in Inorder, Preorder & Postorder further recursive & non recursive. |
23-27
|
8.
|
Write a program in C that implements Binary Search Tree and
perform insert and delete operation. |
27-31
|
9.
|
Write a program in C that implements Prim’s algorithm.
|
31-32
|
10.
|
Write a program in C that implements DFS.
|
32-34
|
11.
|
Write a program in C that implements Newton Raphson method.
|
34-35
|
12.
|
Write a program in C that implements Euler method.
|
35-35
|
1. Write a menu driven program in C that implements the following searching method - (a) Linear Search, (b) Binary Search.
Code
/* Searching (Linear Search, Binary Search) */
#include<stdio.h>
#include<stdlib.h>
void linearSearch(int *,int ,int );
void binarySearch(int *,int ,int ,int );
main(){
int ch=1,*a,i,n,item;
printf("Enter the number of element: ");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("Enter elements: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
while(ch){
printf("1_Linear Search\n2_Binary Search\n0_Exit\nChose your choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("Enter the element that you want to search: ");
scanf("%d",&item);
linearSearch(a,n,item);
break;
case 2:
printf("Enter the element that you want to search: ");
scanf("%d",&item);
binarySearch(a,0,n-1,item); //(array,beg-index,end-index,item)
break;
case 0:
ch=0;
break;
default:
printf("\nWrong choice\n\n");
}
}
}
/* Linear Search */
void linearSearch(int *a,int n,int item){
int i;
for(i=0;i<n;i++){
if(a[i]==item){
printf("%d found at %d possition\n\n",item,i+1);
return ;
}
}
printf("%d Not Found \n",item);
}
/* Binary Search */
void binarySearch(int *a,int beg,int end,int item){
int mid=(beg+end)/2;
if(beg<=end){
if(a[mid]==item){
printf("%d found at %d possition\n\n",item,mid+1);
return ;
}
else if(item>a[mid])
binarySearch(a,mid+1,end,item);
else
binarySearch(a,beg,mid-1,item);
}
else
printf("%d is not found\n\n",item);
}
Output
Enter the number of element: 5
Enter elements: 3 5 6 9 12
1_Linear Search
2_Binary Search
0_Exit
Chose your choice: 1
Enter the element that you want to search: 5
5 found at 2 possition
1_Linear Search
2_Binary Search
0_Exit
Chose your choice: 2
Enter the element that you want to search: 9
9 found at 4 possition
1_Linear Search
2_Binary Search
0_Exit
Chose your choice: 1
Enter the element that you want to search: 12
12 found at 5 possition
1_Linear Search
2_Binary Search
0_Exit
Chose your choice: 1
Enter the element that you want to search: 15
15 Not Found
1_Linear Search
2_Binary Search
0_Exit
Chose your choice: 2
Enter the element that you want to search: 5
5 found at 2 possition
2. Write a menu driven program in C that implements the following sorting method - (a) Bubble Sort, (b) Selection Sort, (c) Insertion
Sort, (d) Quick Sort, (e) Merge Sort, (f) Heap Sort
Sort, (d) Quick Sort, (e) Merge Sort, (f) Heap Sort
Code
/*All sorting algorithm*/
#include<stdio.h>
#include<stdlib.h>
void bubbleSort(int *,int );
void selectionSort(int *,int );
int mLoc(int *,int ,int );
void insertionSort(int *,int );
void quickSort(int *,int ,int);
int pertition(int *a,int ,int);
void margeSort(int *,int ,int );
void marge(int *,int ,int ,int );
void heapSort(int *,int );
void heaping(int *,int );
void adjust(int *,int ,int );
int* readArray(int *, int *);
int main(){
int *a,i,n,ch=1;
while(ch){
printf("\n1)Bubble Sort \n2)Selection Sort \n3)Insertion Sort \n4)Quick Sort \n5)Marge Sort \n6)Heap Sort");
printf("\n0)Exit \nChose your choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
a=readArray(a,&n);
bubbleSort(a,n);
break;
case 2:
a=readArray(a,&n);
selectionSort(a,n);
break;
case 3:
a=readArray(a,&n);
insertionSort(a,n);
break;
case 4:
a=readArray(a,&n);
quickSort(a,0,n-1);
printf("\nAfter Quick sort: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
break;
case 5:
a=readArray(a,&n);
margeSort(a,0,n-1);
printf("\nAfter Marge sort: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
break;
case 6:
a=readArray(a,&n);
heapSort(a,n-1);
printf("\nAfter heap sort: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
break;
case 0:
break;
default:
printf("\nWrong choice !\n");
}
}
return 0;
}
int* readArray(int *a, int *n){
int i;
printf("Enter the size of array: ");
scanf("%d",n);
a=(int*)malloc(*n*sizeof(int));
printf("Entre the array elements: ");
for(i=0;i<*n;i++)
scanf("%d",&a[i]);
return a;
}
/* Bubble Sort */
void bubbleSort(int *a,int n)
{
int i,j,t,f=1;
for(i=0;i<n-1 && f;i++)
{
f=0;
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
f=1;
}
}
}
printf("After bubble sort: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
/* Selection Sort */
void selectionSort(int *a,int n)
{
int i,j,ml,t;
for(i=0;i<n-1;i++)
{
ml=mLoc(a,i,n);
if(i!=ml)
{
t=a[i];
a[i]=a[ml];
a[ml]=t;
}
}
printf("After selection sort: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
int mLoc(int *a,int f,int n)
{
int min,j,i;
min=a[f]; j=f;
for(i=f+1;i<n;i++)
{
if(min>a[i])
{
min=a[i];
j=i;
}
}
return j;
}
/* Insertion Sort */
void insertionSort(int *a,int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
j=i-1;
temp=a[i];
while(j>=0 && temp<a[j])
{
a[j+1]=a[j];
j--;
}
j++;
a[j]=temp;
}
printf("After insertion sort: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
/* Quick Sort */
void quickSort(int *a,int low,int high)
{
int pi;
if(low<high)
{
pi=pertition(a,low,high); //pi is the pertitioning place
quickSort(a,low,pi-1);
quickSort(a,pi+1,high);
}
}
int pertition(int *a,int low,int high)
{
int pivot,i,j,temp;
pivot=a[high];
for(i=low-1,j=low;j<=high-1;j++)
{
if(a[j]<=pivot)
{
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
i++;
temp=a[i];
a[i]=a[j];
a[j]=temp;
return i;
}
/* Marge sort */
void margeSort(int *a,int low,int high)
{
int m=(low+high)/2;
if(low<high){
margeSort(a,low,m);
margeSort(a,m+1,high);
}
marge(a,low,m,high);
}
void marge(int *a,int low,int mid,int high){
int i,j,k,*c;
c=(int*)malloc((high-low+1)*sizeof(int));
for(i=low,j=mid+1,k=0;i<=mid && j<=high; ){
if(a[i]<a[j])
c[k++]=a[i++];
else
c[k++]=a[j++];
}
while(i<=mid)
c[k++]=a[i++];
while(j<=high)
c[k++]=a[j++];
for(i=low,k=0;i<=high;i++,k++)
a[i]=c[k]; //copy the sorted array to a
}
/* heap sort */
void heapSort(int *a,int n){
int t;
if(n>0){
heaping(a,n);
t=a[0];
a[0]=a[n]; //last index n N:B: indexing start from 0
a[n]=t;
heapSort(a,n-1);
}
}
void heaping(int *a,int n){
int i;
for(i=n/2;i>=0;i--)
adjust(a,i,n);
}
void adjust(int *a,int i,int n){
int j=2*i+1; //left chield of i , N:B: index starting from 0
int item=a[i];
while(j<=n){
if(j<n && a[j]<a[j+1])
j=j+1;
if(item>=a[j])
break;
a[(j-1)/2]=a[j];
j=j*2+1;
}
a[(j-1)/2]=item;
}
Output
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 1
Enter the size of array: 5
Entre the array elements: 6 5 4 3 2
After bubble sort: 2 3 4 5 6
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 2
Enter the size of array: 3
Entre the array elements: 15 20 8
After selection sort: 8 15 20
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 3
Enter the size of array: 5
Entre the array elements: 45 12 56 14 5
After insertion sort: 5 12 14 45 56
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 4
Enter the size of array: 5
Entre the array elements: 54 12 34 45 14
After Quick sort: 12 14 34 45 54
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 5
Enter the size of array: 4
Entre the array elements: 12 5 48 63
After Marge sort: 5 12 48 63
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 6
Enter the size of array: 5
Entre the array elements: 85 45 65 12 7
After heap sort: 7 12 45 65 85
1)Bubble Sort
2)Selection Sort
3)Insertion Sort
4)Quick Sort
5)Marge Sort
6)Heap Sort
0)Exit
Chose your choice: 0
3. Write a program in C that implements Stack. Use dynamic memory allocation.
CODE
/* Stack using dynamic memory allocation */
#include<stdio.h>
#include<stdlib.h>
int *stack,size,top=-1;
void PUSH(){
if(top==size-1)
printf("Stack Overflow\n");
else
{
top++;
printf("Enter the element: ");
scanf("%d",&stack[top]);
printf("%d is pushed\n",stack[top]);
}
}
void POP(){
if(top==-1)
printf("Stack is Underflow\n");
else{
printf("%d is poped\n",stack[top]);
top--;
}
}
int main(){
int ch,item;
printf("Enter the size of stack: ");
scanf("%d",&size);
stack=(int*)malloc(size*sizeof(int));
while(1){
printf("1_PUSH\n2_POP\n3_Exit\nChose your choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
PUSH();
break;
case 2:
POP();
break;
case 3:
return 0;
}
}
}
OUTPUT
Enter the size of stack: 3
1_PUSH
2_POP
3_Exit
Chose your choice: 1
Enter the element: 10
10 is pushed
1_PUSH
2_POP
3_Exit
Chose your choice: 1
Enter the element: 20
20 is pushed
1_PUSH
2_POP
3_Exit
Chose your choice: 1
Enter the element: 30
30 is pushed
1_PUSH
2_POP
3_Exit
Chose your choice: 1
Stack Overflow
1_PUSH
2_POP
3_Exit
Chose your choice: 2
30 is poped
1_PUSH
2_POP
3_Exit
Chose your choice: 2
20 is poped
1_PUSH
2_POP
3_Exit
Chose your choice: 2
10 is poped
1_PUSH
2_POP
3_Exit
Chose your choice: 2
Stack is Underflow
1_PUSH
2_POP
3_Exit
Chose your choice: 3
4. Write a program in C that implements Queue. Use dynamic memory allocation.
CODE
/* Queue Implementation */
#include <stdio.h>
#include <stdlib.h>
int *queue,size,f=-1,r=-1;
void inQueue(int data){
if(r==size-1)
printf("Queue is full\n");
else{
r++;
queue[r]=data;
printf("%d is inQueued\n",queue[r] );
if(r==0)
f=0; //first time
}
}
int deQueue(){
if(f>r || f==-1)
printf(" Queue is empty\n");
else{
printf(" %d is deQueued\n",queue[f] );
f++;
}
}
int main(){
int item,ch;
printf("Enter the size of queue: ");
scanf("%d",&size);
queue=(int*)malloc(size*sizeof(int));
while(1){
printf("\n1_InQueue\n2_DeQueue\n3_Exit\nChose your choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("Enter the item: ");
scanf("%d",&item);
inQueue(item);
break;
case 2:
deQueue();
break;
case 3:
return 0;
default:
printf("Wrong input !!\n");
}
}
}
OUTPUT
Enter the size of queue: 5
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 1
Enter the item: 10
10 is inQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 1
Enter the item: 20
20 is inQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 1
Enter the item: 30
30 is inQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 1
Enter the item: 40
40 is inQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 1
Enter the item: 50
50 is inQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 1
Enter the item: 60
Queue is full
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 2
10 is deQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 2
20 is deQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 2
30 is deQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 2
40 is deQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 2
50 is deQueued
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 2
Queue is empty
1_InQueue
2_DeQueue
3_Exit
Chose your choice: 3
5. Write a program in C that implements Circular Queue. Use dynamic memory allocation.
CODE
/*Circular queue*/
#include<stdio.h>
#include<stdlib.h>
int *queue,f=-1,r=-1,n;
void inqueue(){
if(f==(r+1)%n)
printf("\nQueue is Full\n");
else{
if(f==-1)
f=0;
r=(r+1)%n;
printf("Enter the item: ");
scanf("%d",&queue[r]);
printf("%d enqued\n",queue[r]);
}
}
void dequeue(){
if(f==-1)
printf("\nQueue is Empty\n");
else{
printf("\n%d is dequeued\n",queue[f]);
if(f==r)
f=r=-1;
else
f=(f+1)%n;
}
}
int main(){
int ch;
printf("Inter the size of queue: ");
scanf("%d",&n);
queue=(int*)malloc(n*sizeof(int));
while(1){
printf("\n1 Enqueue \n2 Dequeue \n0 Exit \n Chose option: ");
scanf("%d",&ch);
switch(ch){
case 1:
inqueue();
break;
case 2:
dequeue();
break;
case 0:
exit(1);
default:
printf("\nWrong Input");
}
} }
OUTPUT
Inter the size of queue: 4
1 Enqueue
2 Dequeue
0 Exit
Chose option: 1
Enter the item: 10
10 enqued
1 Enqueue
2 Dequeue
0 Exit
Chose option: 1
Enter the item: 20
20 enqued
1 Enqueue
2 Dequeue
0 Exit
Chose option: 1
Enter the item: 30
30 enqued
1 Enqueue
2 Dequeue
0 Exit
Chose option: 1
Enter the item: 40
40 enqued
1 Enqueue
2 Dequeue
0 Exit
Chose option: 1
Queue is Full
1 Enqueue
2 Dequeue
0 Exit
Chose option: 2
10 is dequeued
1 Enqueue
2 Dequeue
0 Exit
Chose option: 1
Enter the item: 50
50 enqued
6. Write a program in C that implements Singly Linked list and performs
the following- 1) Insert First 2) Delete First 3) Insert Last 4) Delete Last 5) Insert Any Position 6)Delete Any Possition 7)Reverse 8)Display 9)Sort 10)Remove Duplicate Element
CODE
/*Link list operation*/
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int info;
struct node *next;
}N;
N* creatNode();
N* ins_first(N* );
N* del_first(N* );
N* ins_last(N* );
N* del_last(N* );
N* insAnyPos(N* );
N* delAnyPos(N* );
N* Reverse(N* );
N* sort(N* );
N* insLast(N* ,int );
N* delDesire(N* ,int ,int *);
int display(N* );
N* delAnyPos(N* );
N* removeDuplicate(N *);
void main(){
int f=1,ch;
N *start=NULL;
while(f){
printf("\n 1_Insert First\n 2_Delete First\n 3_Insert Last\n 4_Delete Last\n 5_insAnyPos\n 6_delAnyPos\n 7_Reverse\n 8_Display\n 9_Sort\n 10_Remove Duplicate\n 0_Exit\nSelect Your Choice : ");
scanf("%d",&ch);
switch(ch){
case 1:
start=ins_first(start);
break;
case 2:
start=del_first(start);
break;
case 3:
start=ins_last(start);
break;
case 4:
start=del_last(start);
break;
case 5:
start=insAnyPos(start);
break;
case 6:
start=delAnyPos(start);
break;
case 7:
start=Reverse(start);
break;
case 8:
display(start);
break;
case 9:
start=sort(start);
break;
case 10:
start=removeDuplicate(start);
break;
case 0:
f=0;
break;
default:
printf("You have enter wrong input!!!\n");
}
}
}
/* NEW NODE CREATE WITH VALUE */
N* creatNode(){
N *newNode=(N*)malloc(sizeof(N));
printf("Enter info: ");
scanf("%d",&newNode->info);
newNode->next=NULL;
return newNode;
}
/*INSERT FIRST NODE IN LINK LIST*/
N* ins_first(N *head){
N *newNode=creatNode();
if(newNode){
newNode->next=head;
head=newNode;
}
else
printf(" Insertion failed due to memory full \n");
return head;
}
/*DELETE FIRST NODE IN LINK LIST*/
N* del_first(N* head){
if(head==NULL)
printf("\nLink list empty\n");
else{
printf("\n%d is deleted..\n\n",head->info);
head=head->next;
}
return head;
}
/*INSERT LAST NODE IN LINK LIST*/
N* ins_last(N* head){
N *currNode=head,*newNode=creatNode();
if(newNode){
if(head==NULL)
head=newNode;
else
{
while(currNode->next!=NULL)
currNode=currNode->next;
currNode->next=newNode;
}
}
else
printf(" Insertion failed due to memory full \n");
return head;
}
/*DELETE LAST NODE IN LINK LIST*/
N* del_last(N* head){
N *prevNode,*t;
if(head==NULL)
printf("\nLink list Empty\n");
else if(head->next==NULL) //if only one node have in LS
{
t=head;
printf("\n%d is deleted...\n\n",head->info);
head=NULL;
free(t); //release memory
}
else
{
prevNode=head;
while(prevNode->next->next!=NULL) //reach the last two number node
prevNode=prevNode->next;
t=prevNode->next; //last node
printf("\n%d is deleted..\n\n",t->info);//prevNode->next=t
prevNode->next=NULL;
free(t);
}
return head;
}
/*REVERSE LINK LIST*/
N* Reverse(N *head){
N *t,*head2=NULL;
if(head){
while(head!=NULL){
t=head;
head=head->next; //first del
t->next=head2;
head2=t;
}
}
else
printf("\n Inverse not possible due to memory full \n");
return head2;
}
/*DISPLAY LINK LIST*/
int display(N *head){
N *currNode=head;
if(currNode==NULL)
printf("\nLink list empty\n");
else{
while(currNode!=NULL)
{
printf("%d ",currNode->info);
currNode=currNode->next;
}
}
return 0;
}
/*Insert any place */
N* insAnyPos(N* head){
N *t,*newNode;
int c,pos;
printf("Enter possition: ");
scanf("%d",&pos);
for(t=head,c=0;t!=NULL;t=t->next,c++); /*Count the nodes*/
if(c>=pos-1 && pos>0) /*position start from 1*/
{
if(pos==1){
head=ins_first(head);
}
else{
for(t=head,c=1;t->next!=NULL && c<pos-1;t=t->next,c++);
newNode=creatNode();
newNode->next=t->next;
t->next=newNode;
}
}
else{
printf("\nInvalid position\n");
}
return head;
}
/* Delete any place */
N* delAnyPos(N* head){
N *t,*m;
int c,pos;
printf("Enter possition:");
scanf("%d",&pos);
for(t=head,c=0;t!=NULL;t=t->next,c++); /*Count the node*/
if(c>=pos&& pos>0){
if(pos==1){
head=del_first(head);
}
else{
for(t=head,c=1;t->next!=NULL && c<pos-1;t=t->next,c++);
m=t->next;
t->next=t->next->next;
printf("%d is deleted..\n",m->info);
free(m);
}
}
else{
printf("\nInvalid position\n");
}
return head;
}
N* insLast(N* head,int info){
N *currNode=head,*newNode=(N*)malloc(sizeof(N));
if(newNode){
newNode->next=NULL;
newNode->info=info;
if(head==NULL)
head=newNode;
else
{
while(currNode->next!=NULL)
currNode=currNode->next;
currNode->next=newNode;
}
}
else
printf(" Insertion failed due to memory full \n");
return head;
}
/*Sort in link list*/
N* sort(N *head){
N *i,*j;
if(head){
int t;
for(i=head;i->next!=NULL;i=i->next){
for(j=head;j->next!=NULL;j=j->next){
if(j->info>j->next->info){
t=j->info;
j->info=j->next->info;
j->next->info=t;
}
}
}
}
else
printf("\n Sort not possible, List empty \n ");
return head;
}
N* removeDuplicate(N *head){
N *p1 = head,*p2,*p0;
if(head){
while(p1){
p0 = p1;
p2 = p1->next;
while(p2){
if(p1->info == p2->info)
p0->next = p2->next; //remove
else
p0 = p0->next;
p2 = p2->next;
}
p1 = p1->next;
}
}
else
printf("\n Remove not posible due to memory full \n");
return head;
}
OUTPUT
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 10
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 20
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 8
20 10
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 7
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 8
10 20
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 3
Enter info: 40
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 5
Enter possition: 4
Enter info: 80
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 8
10 20 40 80
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 6
Enter possition:3
40 is deleted..
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 8
10 20 80
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 0
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 10
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 20
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 30
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 40
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 50
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 30
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 1
Enter info: 50
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 8
50 30 50 40 30 20 10
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 10
1_Insert First
2_Delete First
3_Insert Last
4_Delete Last
5_insAnyPos
6_delAnyPos
7_Reverse
8_Display
9_Sort
10_Remove Duplicate
0_Exit
Select Your Choice : 8
50 30 40 20 10
7. Write a program in C that implements Binary tree and traverse the
tree in Inorder, Preorder & Postorder further recursive & non
recursive.
CODE
/* Binary tree (recursive)*/
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int info;
struct node *lc,*rc;
}N;
N* getNode(){
N *newNode=malloc(sizeof(N));
printf("Enter the data: ");
scanf("%d",&newNode->info);
newNode->lc=newNode->rc=NULL;
return newNode;
}
void createBinaryTree(N* root){
char ch;
printf("Left chield of %d ? (Y/N) ",root->info);
scanf(" %c",&ch);
if(ch=='y' || ch=='Y'){
root->lc=getNode();
createBinaryTree(root->lc);
}
printf("Right chield of %d ? (Y/N) ",root->info);
scanf(" %c",&ch);
if(ch=='y' || ch=='Y'){
root->rc=getNode();
createBinaryTree(root->rc);
}
}
void preorder(N *r){
if(r==NULL) return ;
printf("%d, ",r->info);
preorder(r->lc);
preorder(r->rc);
}
void inorder(N *r){
if(r==NULL) return ;
inorder(r->lc);
printf("%d, ",r->info);
inorder(r->rc);
}
void postorder(N *r){
if(r==NULL) return ;
postorder(r->lc);
postorder(r->rc);
printf("%d, ",r->info);
}
int main(){
printf("Root node\n");
N *root=getNode();
createBinaryTree(root);
int ch;
while(1){
printf("\n1_Preorder_Traversal\n2_Inorder_Traversal\n3_Postorder_Traversal\n0_Exit\nChose choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("After Preorder: ");
preorder(root);
break;
case 2:
printf("After Inorder: ");
inorder(root);
break;
case 3:
printf("After Postorder: ");
postorder(root);
break;
case 0:
exit(1);
}
}
}
OUTPUT
Root node
Enter the data: 10
Left chield of 10 ? (Y/N) y
Enter the data: 20
Left chield of 20 ? (Y/N) y
Enter the data: 4
Left chield of 4 ? (Y/N) n
Right chield of 4 ? (Y/N) n
Right chield of 20 ? (Y/N) y
Enter the data: 5
Left chield of 5 ? (Y/N) n
Right chield of 5 ? (Y/N) n
Right chield of 10 ? (Y/N) y
Enter the data: 30
Left chield of 30 ? (Y/N) y
Enter the data: 7
Left chield of 7 ? (Y/N) n
Right chield of 7 ? (Y/N) n
Right chield of 30 ? (Y/N) y
Enter the data: 6
Left chield of 6 ? (Y/N) n
Right chield of 6 ? (Y/N) n
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 1
After Preorder: 10, 20, 4, 5, 30, 7, 6,
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 2
After Inorder: 4, 20, 5, 10, 7, 30, 6,
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 3
After Postorder: 4, 5, 20, 7, 6, 30, 10,
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 0
CODE (Non Recursive)
/* Binary tree (non recursive) */
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int info;
struct node *lc,*rc;
}N;
int s=0;
N* getNode(){
N *newNode=malloc(sizeof(N));
printf("Enter the data: ");
scanf("%d",&newNode->info);
newNode->lc=newNode->rc=NULL;
return newNode;
}
void createBinaryTree(N* root){
char ch;
printf("Left chield of %d ? (Y/N) ",root->info);
scanf(" %c",&ch);
if(ch=='y' || ch=='Y'){
root->lc=getNode();
s++;
createBinaryTree(root->lc);
}
printf("Right chield of %d ? (Y/N) ",root->info);
scanf(" %c",&ch);
if(ch=='y' || ch=='Y'){
root->rc=getNode();
s++;
createBinaryTree(root->rc);
}
}
void preorder(N *root){
N *stack[s],*temp;
int top=-1;
stack[++top]=root;
while(top>=0){
temp=stack[top--];
if(temp){
printf("%d, ",temp->info);
stack[++top]=temp->rc;
stack[++top]=temp->lc;
}
}
}
void postorder(N *root){
N *stack[s],*temp;
int top1=-1,top2=s;
stack[++top1]=root;
while(top1>=0 ){
temp=stack[top1--];
stack[--top2]=temp;
if(temp->lc){
stack[++top1]=temp->lc;
}
if(temp->rc)
{
stack[++top1]=temp->rc;
}
}
while(top2<s)
printf("%d, ",stack[top2++]->info);
}
void inorder(N *t){
N *st[s],*p;
int top = -1;
p = t;
while(top >= 0 || p){
if(p){
st[++top] = p;
p = p->lc;
}
else{
p = st[top--];//POP
printf("%d,",p->info);
p = p->rc;
}
}
}
int main(){
printf("Root node\n");
N *root=getNode();
s++;
createBinaryTree(root);
int ch;
while(1){
printf("\n1_Preorder_Traversal\n2_Inorder_Traversal\n3_Postorder_Traversal\n0_Exit\nChose choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
printf("After Preorder: ");
preorder(root);
break;
case 2:
printf("After Inorder: ");
inorder(root);
break;
case 3:
printf("After Postorder: ");
postorder(root);
break;
case 0:
exit(1);
}
}
}
OUTPUT
Root node
Enter the data: 10
Left chield of 10 ? (Y/N) y
Enter the data: 20
Left chield of 20 ? (Y/N) y
Enter the data: 4
Left chield of 4 ? (Y/N) n
Right chield of 4 ? (Y/N) n
Right chield of 20 ? (Y/N) y
Enter the data: 5
Left chield of 5 ? (Y/N) n
Right chield of 5 ? (Y/N) n
Right chield of 10 ? (Y/N) y
Enter the data: 30
Left chield of 30 ? (Y/N) y
Enter the data: 7
Left chield of 7 ? (Y/N) n
Right chield of 7 ? (Y/N) n
Right chield of 30 ? (Y/N) y
Enter the data: 6
Left chield of 6 ? (Y/N) n
Right chield of 6 ? (Y/N) n
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 1
After Preorder: 10, 20, 4, 5, 30, 7, 6,
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 2
After Inorder: 4, 20, 5, 10, 7, 30, 6,
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 3
After Postorder: 4, 5, 20, 7, 6, 30, 10,
1_Preorder_Traversal
2_Inorder_Traversal
3_Postorder_Traversal
0_Exit
Chose choice: 0
8. Write a program in C that implements Binary Search Tree and perform insert and delete operation.
CODE
/*Binary search tree */
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int info;
struct node *lc,*rc;
}N;
N* getNode(){
N* newNode=malloc(sizeof(N));
printf("Enter the info: ");
scanf("%d",&newNode->info);
newNode->lc=newNode->rc=NULL;
return newNode;
}
void insert(N* root){
N *ptr=root,*pptr=NULL,*newNode=getNode();
while(ptr){
if(newNode->info < ptr->info){
pptr=ptr;
ptr=ptr->lc;
}
else if(newNode->info > ptr->info){
pptr=ptr;
ptr=ptr->rc;
}
else{
printf("Info already exists\n");
return;
}
}
if(newNode->info < pptr->info)
pptr->lc=newNode;
else
pptr->rc=newNode;
}
void delBST(N* root){
int item,ch;
printf("Enter item to delete: ");
scanf("%d",&item);
N *ptr=root,*prnt,*sc,*pc,*prnt1; //prnt = parent
int f=0;
if(root==NULL)
printf("\nTree is empty\n");
else{
while(ptr!=NULL && f==0){
if(item < ptr->info){
prnt=ptr;
ptr=ptr->lc;
}
else if(item > ptr->info){
prnt=ptr;
ptr=ptr->rc;
}
else
f=1;
}
if(f==1) //if info found
{
if(ptr->lc==NULL && ptr->rc==NULL) //deleted node leaf node
{
if(prnt->lc==ptr)
prnt->lc=NULL;
else
prnt->rc=NULL;
free(ptr);
}
else if(ptr->lc!=NULL && ptr->rc==NULL) //if left chield available
{
if(prnt->lc==ptr)
prnt->lc=ptr->lc;
else
prnt->rc=ptr->lc;
}
else if(ptr->lc==NULL && ptr->rc!=NULL) //if right chield available
{
if(prnt->lc==ptr)
prnt->lc=ptr->rc;
else
prnt->rc=ptr->rc;
}
else if(ptr->lc!=NULL && ptr->rc!=NULL) // two child available
{
printf("Two chaild available\n1 successor\n2 precessor \nchose: ");
scanf("%d",&ch);
if(ch==1)
{
prnt=ptr;
sc=ptr->rc; /*sc=successor pointer,right sub-tree's left-most node*/
while(sc->lc)
{
prnt=sc;
sc=sc->lc;
}
ptr->info = sc->info; /*item deleted*/
if(prnt->lc==sc)
prnt->lc = sc->rc;
else
prnt->rc = sc->rc; /*should not left chield of sc*/
free(sc);
}
else{
prnt=ptr;
pc=ptr->lc; /*pc=preceessor pointer,left sub-tree's right-most node*/
while(pc->rc){
prnt=pc;
pc=pc->rc;
}
ptr->info = pc->info;
if(prnt->lc = pc)
prnt->lc = pc->lc;
else
prnt->rc = pc->lc;
free(pc);
}
}
}
else
printf("\n%d is Not found ",item);
}
}
void inorder(N *root){
if(root==NULL) return ;
inorder(root->lc);
printf("%d, ",root->info);
inorder(root->rc);
}
int main(){
int ch;
N *root=getNode();
while(1){
printf("1-Insert node\n2-Delete node\n3-Display\n0-Exit\nChose choice: ");
scanf("%d",&ch);
switch(ch){
case 1:
insert(root);
break;
case 2:
delBST(root);
break;
case 3:
printf("Display (inorder):");
inorder(root);
printf("\n");
break;
case 0:
exit(1);
default:
printf("\nwrong input\n");
}
}
}
OUTPUT
Enter the info: 10
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 8
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 15
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 5
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 9
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 12
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 17
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 2
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 1
Enter the info: 6
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 3
Display (inorder):2, 5, 6, 8, 9, 10, 12, 15, 17,
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 2
Enter item to delete: 8
Two chaild available
1 successor
2 precessor
chose: 1
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 3
Display (inorder):2, 5, 6, 9, 10, 12, 15, 17,
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 2
Enter item to delete: 5
Two chaild available
1 successor
2 precessor
chose: 2
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 2
Enter item to delete: 15
Two chaild available
1 successor
2 precessor
chose: 2
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 3
Display (inorder):2, 6, 9, 10, 12, 17,
1-Insert node
2-Delete node
3-Display
0-Exit
Chose choice: 0
9. Write a program in C that implements Prim’s algorithm.
CODE
/*Prim's Algorithm*/
#include<stdio.h>
#include<stdlib.h>
int min(int *,int *,int );
void primes(int tv,int sv,int **costm){
int status[tv],cost[tv],next[tv],i,mv,j,t;
status[sv]=1;
cost[sv]=0;
next[sv]=sv;
for(i=0;i<tv;i++){
if(i==sv)
continue;
status[i]=0;
cost[i]=costm[sv][i];
next[i]=sv;
}
i=0;
while(i<tv){
mv=min(cost,status,tv);
status[mv]=1;
for(j=0;j<tv;j++){
if(status[j]==1)
continue;
t=costm[mv][j]; /* ****** */
if(t < cost[j]){
cost[j]=t;
next[j]=mv;
}
}
i++; }
printf("\n----------after execution-------------\n");
for(i=0;i<tv;i++){
printf("%2d ",cost[i]);
}
printf("\n");
for(i=0;i<tv;i++){
printf("V%d ",next[i]);
}
}
int min(int *cost,int *status,int tv){
int m=9999,i,k;
for(i=0;i<tv;i++){
if(status[i]==0 && cost[i]<m){
m=cost[i];
k=i;
}
}
return k;
}
int main(){
int **costm,tv,i,j,sv;
printf("Enter the number of vertex: ");
scanf("%d",&tv);
costm=(int **)malloc(tv*sizeof(int *));
printf("Enter the cost matrix: \n");
for(i=0;i<tv;i++){
costm[i]=(int*)malloc(tv*sizeof(int)); //Memory allocation for every row-array
for(j=0;j<tv;j++)
scanf("%d",&costm[i][j]);
}
printf("\nEnter the source vartex: ");
scanf("%d",&sv);
primes(tv,sv,costm);
}
OUTPUT
Enter the number of vertex: 7
Enter the cost matrix:
0 4 5 2 999 999 999
4 0 999 1 2 999 999
5 999 0 8 999 1 999
2 1 8 0 3 4 7
999 2 999 3 0 999 9
999 999 1 4 999 0 6
999 999 999 7 9 6 0
Enter the source vartex: 0
----------after execution-------------
0 1 1 2 2 4 6
V0 V3 V5 V0 V1 V3 V5
10. Write a program in C that implements DFS.
CODE
/*DFS*/
#include<stdio.h>
#include<stdlib.h>
void dfs(int**,int);
void push(int,int*,int*);
int pop(int*,int*);
int main(){
int tv,i,j;
int **adj;
start:
printf("Enter the total number of vartex: ");
scanf("%d",&tv);
if(tv>0){
adj=(int**)malloc(tv*sizeof(int*));
for(i=0;i<tv;i++)
adj[i]=(int*)malloc(tv*sizeof(int));
for(i=0;i<tv;i++)
for(j=0;j<tv;j++)
adj[i][j]=0;
printf("Enter lower triangular Adjacency matrix: \n");
for(i=0;i<tv;i++){
for(j=0;j<i;j++){
scanf("%d",&adj[i][j]);
adj[j][i]=adj[i][j];
}
}
dfs(adj,tv);
}
else{
printf("Total number of vartex should not zero\n ");
goto start;
return 0;
}
}
void dfs(int**adj,int tv){
int p;
int sv,top=-1,s,i;
int visit[tv],check[tv],st[tv];
for(i=0;i<tv;i++)
visit[i]=check[i]=0;
printf("Enter the starting vartex: ");
scanf("%d",&sv);
push(sv,&top,st);
check[sv]=1;
printf("The dfs travarsal list is ");
while(top>=0){
p=pop(&top,st);
if(visit[p]==0){
printf("%d ",p);
visit[p]=1;
}
for(i=0;i<tv;i++){
if(adj[p][i]==1 && check[i]==0){
push(i,&top,st);
check[i]=1;
}
}
}
}
void push(int item,int *top, int *st){
(*top)++;
st[*top]=item;
}
int pop(int *top,int *st){
return st[(*top)--];
}
OUTPUT
Enter the total number of vartex: 8
Enter lower triangular Adjacency matrix:
1
0 0
1 0 1
0 0 1 1
0 1 1 0 0
0 0 0 0 1 1
0 0 0 0 0 0 1
Enter the starting vartex: 0
The dfs travarsal list is 0 3 4 6 7 5 2 1
11 . Write a program in C that implements Newton Raphson method.
CODE
/*Newton Rapson x1=x0-(f(xo)/f'(x0)) */
#include<stdio.h>
#include<stdlib.h>
void raphson(float,int,int);
int main()
{
float x0;
int a,b;
printf(" Enter the value of x0,a,b :");
scanf("%f%d%d",&x0,&a,&b);
raphson(x0,a,b);
return 0;
}
void raphson(float x0,int a,int b)
{
float f_x0,f1_x0,x1,t;
printf(" Enter the value of thresold :");
scanf("%f",&t);
while(1)
{
f_x0 = (a*x0*x0*x0) - (b*x0) - 4;
f1_x0 = (3*a*x0*x0) - b;
x1 = (x0 - (f_x0/f1_x0));
if(x0 == x1)
break;
else if(x1 > x0)
if(x1-x0 <= t)
break;
else if(x0 > x1)
if(x0-x1 <= t)
break;
x0 = x1;
printf(" %f \n",x0);
}
printf("\n The approximation root is %f \n",x0);
}
OUTPUT
Enter the value of x0,a,b :3 1 8
Enter the value of thresold :0.0001
3.052632
3.051375
3.051374
The approximation root is 3.051374
12. Write a program in C that implements Euler method.
CODE
/*Eulars methods*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void euler(float,float,float,float);
int main()
{
float y0,x0,h,x;
int d=2;
printf("Enter the value of x0,y0,h and x : ");
scanf("%f%f%f%f",&x0,&y0,&h,&x);
euler(x0,y0,h,x);
return 0;
}
void euler(float x0,float y0,float h,float x)
{
float y1;
while(1)
{
y1 = y0 + h*((x0*x0*x0) + y0); //y1=y0 + h*fn(x0,y0)
x0 = x0 + h;
y0 = y1;
if(x0-x>0)
break;
printf(" f(%.2f) = %.4f \n",x0,y0);
}
printf("\n .’. f(%.2f) = %f \n",x,y0);
}
OUTPUT
Enter the value of x0,y0,h and x : 0 1 .01 .03
f(0.01) = 1.0100
f(0.02) = 1.0201
f(0.03) = 1.0303
.'.f(0.03) = 1.040604