Singly linked list
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *head,*tp,*temp;
int ch,key,value;
clrscr();
head = NULL;
do
{
printf("1.Insert @ first\t 2.Insert @ last\t 3.Insert @ middle\n");
printf("4.Deletion\t 5.Display");
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: {
printf("\nenter a no to insert @ first:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->data=value;
temp->next=NULL;
if(head==NULL)
{
head=temp;
}
else
{
temp->next=head;
head=temp;
}}
break;
case 2: {
printf("\nenter a no to insert @ last:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->data=value;
temp->next=NULL;
if(head==NULL)
{
head=temp;
}
else
{
tp=head;
while(tp->next!=NULL)
{
tp=tp->next;
}
tp->next=temp;
}}
break;
case 3: {
printf("\nEnter a no to find:");
scanf("%d",&key);
printf("\nenter a no to insert @ middle:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->data=value;
temp->next=NULL;
if(head==NULL)
head=temp;
else
{
tp=head;
while(tp!=NULL && tp->data!=key)
tp=tp->next;
if(tp!=NULL)
{
temp->next=tp->next;
tp->next=temp;
}
else
printf("\nElement not found...");
}}
break;
case 4: {
printf("\nEnter a no to delete:");
scanf("%d",&key);
if(head==NULL)
printf("\nlist is empty");
else
{
tp=head;
while(tp!=NULL && tp->data!=key)
{
temp=tp;
tp=tp->next;
}
if(tp!=NULL)
{
if(tp==head)
{
head=head->next;
free(tp);
}
else
{
temp->next=tp->next;
free(tp);
} }
else
printf("\nelement not found");
}}
break;
case 5: {
if(head!=NULL)
tp=head;
while(tp!=NULL)
{
printf("%d\t",tp->data);
tp=tp->next;
}
printf("\n");
}break;
default:printf("\nenter correct choice");
break;
}
}while(ch<=5);
getch();
}
Doubly Linked List
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
struct node *prev;
int data;
struct node *next;
};
void main()
{
struct node *head,*tp,*temp;
int ch,key,value;
clrscr();
head = NULL;
printf("\n1.Insert @ first\t 2.Insert @ last\t 3.Insert @ middle\n");
printf("4.Deletion\t 5.Display");
do
{
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: {
printf("\nenter a no to insert @ first:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->prev=NULL;
temp->data=value;
temp->next=NULL;
if(head==NULL)
head=temp;
else
{
temp->next=head;
head->prev=temp;
head=temp;
}}
break;
case 2: {
printf("\nenter a no to insert @ last:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->prev=NULL;
temp->data=value;
temp->next=NULL;
if(head==NULL)
head=temp;
else
{
tp=head;
while(tp->next!=NULL)
{
tp=tp->next;
}
tp->next=temp;
temp->prev=tp;
}}
break;
case 3: {
printf("\nEnter a no to find:");
scanf("%d",&key);
printf("\nenter a no to insert @ middle:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->prev=NULL;
temp->data=value;
temp->next=NULL;
if(head==NULL)
head=temp;
else
{
tp=head;
while(tp!=NULL && tp->data!=key)
tp=tp->next;
if(tp!=NULL)
{
temp->next=tp->next;
temp->prev=tp;
tp->next->prev=temp;
tp->next=temp;
}
else
printf("\nElement not found...");
}}
break;
case 4: {
printf("\nEnter a no to delete:");
scanf("%d",&key);
if(head==NULL)
printf("\nlist is empty");
else
{
tp=head;
while(tp!=NULL && tp->data!=key)
{
tp=tp->next;
}
if(tp!=NULL)
{
if(tp==head)
{
head=head->next;
head->prev=NULL;
free(tp);
}
else
{
if(tp->next!=NULL)
{
temp->prev->next=tp->next;
temp->next->prev=tp->prev;
free(tp);
}
else
{
tp->prev->next=NULL;
free(tp);
}
}}
else
printf("\nelement not found");
} }break;
case 5: {
if(head!=NULL)
tp=head;
while(tp!=NULL)
{
printf("%d\t",tp->data);
tp=tp->next;
}
}break;
default:printf("\nenter correct choice");
break;
}
}while(ch<=5);
getch();
}
CIRCULAR LINKED LIST
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *head,*temp,*tp,*tmp;
int value,ch,key;
clrscr();
head=NULL;
printf("1.Insert at first\n2.insert at last\n");
printf("3.insert in middle\n4.delete\n5.display\n");
do
{
printf("\nEnter choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
tp=head;
printf("\nEnter no:");
scanf("%d",&value);
temp=(struct node *)malloc(sizeof(struct node));
temp->data=value;
temp->next=NULL;
if(head==NULL)
{
head=temp;
head->next=head;
}
else
{
temp->next=head;
head->next=temp;
head=temp;
}
break;
case 2:
printf("\nEnter no:");
scanf("%d",&value);
temp=(struct node *)malloc(sizeof(struct node));
temp->data=value;
temp->next=NULL;
if(head==NULL)
{
head=temp;
head->next=head;
}
else
{
tp=head;
while(tp->next!=head)
tp=tp->next;
temp->next=head;
tp->next=temp;
}
break;
case 3:
printf("\nEnter no:");
scanf("%d",&value);
printf("\nEnter target:");
scanf("%d",&key);
temp=(struct node *)malloc(sizeof(struct node));
temp->data=value;
temp->next=NULL;
if(head==NULL)
{
head=temp;
head->next=head;
}
else
{
tp=head;
while(tp->data!=key && tp!=NULL)
tp=tp->next;
if(tp!=NULL)
{
temp->next=tp->next;
tp->next=temp;
}
else
printf("\nTarget not found");
}
break;
case 4:
printf("\nEnter target:");
scanf("%d",&key);
if(head==NULL)
printf("\nList is empty");
else
{
tp=head;
while(tp->data!=key && tp!=NULL)
{
temp=tp;
tp=tp->next;
}
if(tp!=NULL)
{
if(tp==head)
{
while(tp->next!=head)
tp=tp->next;
head=head->next;
free(tp);
tp->next=head;
}
else
{
temp->next=tp->next;
free(tp);
}
}
else
printf("\nTarget not found");
}
break;
case 5:
tp=head;
while(tp->next!=head)
{
printf("%d\t",tp->data);
tp=tp->next;
}
printf("%d",tp->data);
break;
}
}while(ch<6);
getch();
}
Balancing paranthesis in data structures
#include<stdio.h>
#include<conio.h>
#define MAX 50
struct stack
{
int a[MAX];
}s1;
int top=-1,i;
char s[MAX];
void main()
{
clrscr();
printf("\nEnter the expression:");
scanf("%s",&s);
for(i=0;s[i]!='\0';i++)
{
if(s[i]=='(')
{
top=top+1 ;
s1.a[top]=s[i];
}
else if(s[i]==')')
{
top=top-1;
}}
if(top==-1)
printf("\nBalanced Paranthesis");
else
printf("\nUnbalanced Paranthesis");
getch();
}
Implementation of queue
#include<stdio.h>
#include<conio.h>
struct queue
{
int a[10],front,rear,size;
};
void main()
{
struct queue *q;
int ch,i;
q->front=0;
q->rear=-1;
clrscr();
printf("\n\nenter the size:");;
scanf("%d",&q->size);
printf("\nQueue operations:");
//printf("\n1.enqueue \n2.dequeue \n3.display");
do
{
printf("\n1.enqueue \n2.dequeue \n3.display");
printf("\n\nenter choice:");
scanf("%d",&ch) ;
switch(ch)
{
case 1: {
printf("\nenter the element:");
if(q->rear<q->size-1)
{
q->rear++;
scanf("%d",&q->a[q->rear]);
}
else
{
printf("\n\nqueue overflow");
}
}break;
case 2: {
if(q->front<=q->rear)
{
printf("\n\ndequeued element:");
printf("%d",q->a[q->front]);
q->front++;
}
else
{
printf("\n\nqueue underflow:");
}}break;
case 3: {
printf("\n\nelements are:");
for(i=q->front;i<=q->rear;i++)
{
printf("%d\t",q->a[i]);
}}break;
default:printf("\n\nenter correct choice");
break;
}
}while(ch<4);
}
BINARY SEARCH TREE
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct treenode;
typedef struct treenode *position;
typedef struct treenode *searchtree;
searchtree makeempty(searchtree T);
position find(int X,searchtree T);
position findmin(searchtree T);
position findmax(searchtree T);
searchtree insert(int X,searchtree T);
searchtree Delete(int X,searchtree T);
struct treenode
{
int element;
searchtree left;
searchtree right;
}*root;
searchtree makeempty(searchtree T)
{
if(T!=NULL)
{
makeempty(T->left);
makeempty(T->right);
free(T);
}
return NULL;
}
position find(int X,searchtree T)
{
if(T==NULL)
return NULL;
if(X<T->element)
return find(X,T->left);
else
if(X>T->element)
return find(X,T->right);
else
return T;
}
position findmin(searchtree T)
{
if(T==NULL)
return NULL;
else
if(T->left==NULL)
return T;
else
return findmin(T->left);
}
searchtree insert(int X,searchtree T)
{
if(T==NULL)
{
T=(struct treenode*)malloc(sizeof(struct treenode));
if(T==NULL)
printf("\n Error");
else
{
T->element=X;
T->left=T->right=NULL;
}
}
else
if(X<T->element)
T->left=insert(X,T->left);
else
if(X>T->element)
T->right=insert(X,T->right);
return T;
}
searchtree Delete(int X,searchtree T)
{
position tmpcell;
if(T==NULL)
printf("\n Element not found");
else
if(X<T->element)
T->left=Delete(X,T->left);
else
if(X>T->element)
T->right=Delete(X,T->right);
else
if(T->left && T->right)
{
tmpcell= findmin(T->right);
T->element=tmpcell->element;
T->right=Delete(T->element,T->right);
}
else
{
tmpcell=T;
if(T->left==NULL)
T=T->right;
else
if(T->right==NULL)
T=T->left;
free(tmpcell);
}
return T;
}
void inorder(searchtree T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d\t",T->element);
inorder(T->right);
}
}
void main()
{
int ch,value;
root=NULL;
clrscr();
printf("\n 1.Insert 2. Delete 3. Display 4.Find ");
do
{
printf("\n Enter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n Enter a no. to insert:");
scanf("%d", &value);
root=insert(value,root);
break;
case 2:
printf("\n Enter the no. to delete:");
scanf("%d",&value);
root=Delete(value,root);
break;
case 3:
printf("\n Tree Elements\n");
inorder(root);
break;
case 4:
printf("\n Enter the element to find:");
scanf("%d",&value);
root=find(value,root);
printf("\n The found element:%d",root->element);
break;
default:
break;
}
}while(ch<5);
getch();
}
Queue using linked list
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int data;
struct node *next;
};
void main()
{
struct node *front,*rear,*tp,*temp;
int ch,key,value;
clrscr();
front = rear = NULL;
do
{
printf("1.Insert @ last\t ");
printf("2.Delete @ first\t 3.Display");
printf("\n\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: {
printf("\nenter a no to insert @ last:");
temp=(struct node*)malloc(sizeof(struct node));
scanf("%d",&value);
temp->data=value;
temp->next=NULL;
if(rear==NULL&& front==NULL)
{
rear=temp;
front=temp;
}
else
{
tp=rear;
while(tp->next!=NULL)
{
tp=tp->next;
}
tp->next=temp;
}}
break;
case 2: {
if(front==NULL)
printf("\n list is empty");
else
{
tp=front;
front=front->next;
free(tp);
}
}break;
case 3: {
if(rear==NULL)
printf("\nlist is empty");
else
{
tp=front;
printf("\nvalues are:\n");
while(tp!=NULL)
{
printf("%d\t",tp->data);
tp=tp->next;
}
}
break;
default: printf("\nenter correct choice");
break;
}}
}while(ch<4);
getch();
}
SHORTEST PATH USING DIJIKSTRA’S ALGORITHM..
METHOD 1
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void main()
{
int graph[15][15],s[15],pathestimate[15],mark[15];
int num_of_vertices,source,i,j,u,predecessor[15],dest;
int count=0;
int minimum(int a[],int m[],int k);
void printpath(int,int,int[]);
clrscr();
printf("\nenter the no.of vertices\n");
scanf("%d",&num_of_vertices);
if(num_of_vertices<=0)
{
printf("\nthis is meaningless\n");
exit(1);
}
printf("\nenter the adjacent matrix\n");
for(i=1;i<=num_of_vertices;i++)
{
printf("\nenter the elements of row %d\n",i);
for(j=1;j<=num_of_vertices;j++)
{
scanf("%d",&graph[i][j]);
}}
printf("\nenter the source vertex\n");
scanf("%d",&source);
for(j=1;j<=num_of_vertices;j++)
{
mark[j]=0;
pathestimate[j]=999;
predecessor[j]=0;
}
pathestimate[source]=0;
while(count<num_of_vertices)
{
u=minimum(pathestimate,mark,num_of_vertices);
s[++count]=u;
mark[u]=1;
for(i=1;i<=num_of_vertices;i++)
{
if(graph[u][i]>0)
{
if(mark[i]!=1)
{
if(pathestimate[i]>pathestimate[u]+graph[u][i])
{
pathestimate[i]=pathestimate[u]+graph[u][i];
predecessor[i]=u;
}}}}}
printf("\n possible path for source node having minimun cost:");
for(i=1;i<=num_of_vertices;i++)
{
printpath(source,i,predecessor);
if(pathestimate[i]!=999)
printf("is %d \n",pathestimate[i]);
}
printf("\n Enter the end node:");
scanf("%d",&dest);
printf("\n path of minimum cost for the source and dest:");
printpath(source,dest,predecessor);
printf("is %d \n",pathestimate[dest]);
getch();
}
int minimum(int a[],int m[],int k)
{
int mi=999;
int i,t;
for(i=1;i<=k;i++)
{
if(m[i]!=1)
{
if(mi>=a[i])
{
mi=a[i];
t=i;
}}}
return t;
}
void printpath(int x,int i,int p[])
{
printf("\n");
if(i==x)
{
printf("%d",x);
}
else if(p[i]==0)
printf("no path from %d to %d",x,i);
else
{
printpath(x,p[i],p);
printf("->%d",i);
}}
OUTPUT:
enter the no.of vertices
5
enter the adjacent matrix
enter the elements of row 1
0 6 15 8 1
enter the elements of row 2
6 0 7 10 11
enter the elements of row 3
15 7 0 1 1
enter the elements of row 4
8 10 1 0 9
enter the elements of row 5
1 11 1 9 0
enter the source vertex
2
possible path for source node having minimun cost:
2->1 is 6
2 is 0
2->3 is 7
2->3->4 is 8
2->1->5 is 7
Enter the end node:5
Path of minimum cost for the source and dest:
2->1->5 is 7
METHOD 2
#include<stdio.h>
#include<conio.h>
#define INFINITY 999
void read();
void initialize();
int getClosestUnmarkedNode();
void dijkstra();
void output();
void printPath(int);
int adjMatrix[15][15],predecessor[15],distance[15],mark[15],source,n,i,j;
void read()
{
printf("\nEnter the number of vertices of the graph(should be > 0)\n");
scanf("%d",&n);
//Read the adjacency matrix for the graph with +ve weights
printf("\nEnter the adjacency matrix for the graph\n");
printf("\nTo enter infinity enter %d\n",INFINITY);
for(i=1;i<=n;i++)
{
printf("\nEnter the (+ve)weights for the row %d ",i);
for(j=1;j<=n;j++)
scanf("%d",&adjMatrix[i][j]);
}
printf("\nEnter the source vertex\n");
scanf("%d",&source);
}
void initialize()
{
for(i=1;i<=n;i++) {
mark[i] = 0;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance[source] = 0;
}
int getClosestUnmarkedNode()
{
int minDistance = INFINITY;
int closestUnmarkedNode;
for(i=1;i<=n;i++)
{
if((!mark[i]) && ( minDistance >= distance[i]))
{
minDistance = distance[i];
closestUnmarkedNode = i;
}
}
return closestUnmarkedNode;
}
void dijkstra()
{
int closestUnmarkedNode,count = 0;
initialize();
while(count < n)
{
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = 1;
for(i=1;i<=n;i++)
{
if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) )
{
if(distance[i] >distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i])
{
distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}
void printPath(int node)
{
if(node == source)
printf("%d...",node);
else if(predecessor[node] == -1)
printf("\nNo path from %d to %d \n",source,node);
else
{
printPath(predecessor[node]);
printf("%d...",node);
}
}
void output()
{
for(i=1;i<=n;i++)
{
if(i == source)
printf("%d ...%d",source,source);
else
printPath(i);
printf("-> %d\n",distance[i]);
}
}
void main()
{
clrscr();
printf("\nDijikstra's single source shortest path algorithm \n\n");
read();
dijkstra();
output();
getch();
}
IMPLEMENTATION OF PRIMS ALGORITHM
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void distance(int destination);
int n;
int load[100][100];
char mst[100];
int m[100];
int whoto[100];
void distance(int destination)
{
int i;
for(i=0;i<n;++i)
if((load[destination][i]!=0)&&(m[i]>load[destination][i]))
{
m[i]=load[destination][i];
whoto[i]=destination;
}}
void main()
{
int i,j,total,minspan;
clrscr();
printf("enter the number of nodes:");
scanf("%d",&n);
for(i=0;i<n;++i)
for(j=0;j<n;++j)
{
printf("enter the weight from %d to %d",i,j);
scanf("%d",&load[i][j]);
}
for(i=0;i<n;++i)
m[i]=10000;
for(i=0;i<n;++i)
mst[i]=0;
printf("adding node %c\n",0+'a');
mst[0]=1;
distance(0);
total=0;
for(minspan=1;minspan<n;++minspan)
{
int min=-1;
for(i=0;i<n;++i)
if(!mst[i])
if((min==-1)||(m[min]>m[i]))
min=i;
printf("adding edges %c---%c\n",whoto[min]+'a',min+'a');
mst[min]=1;
total+=m[min];
distance(min);
}
printf("total distance:%d\n",total);
getch();
}
OUTPUT:
enter the number of nodes:3
enter the weight from 0 to 0 5
enter the weight from 0 to 1 4
enter the weight from 0 to 2 3
enter the weight from 1 to 0 3
enter the weight from 1 to 1 7
enter the weight from 1 to 2 4
enter the weight from 2 to 0 1
enter the weight from 2 to 1 2
enter the weight from 2 to 2 4
adding node a
adding edges a---c
adding edges c---b
total distance:5
IMPLEMENTATION OF KRUSKAL’S ALGORITHM
#include<stdio.h>
#define INFINITY 999
typedef struct graph
{
int v1;
int v2;
int cost;
}graph;
graph c[20];
int min(int);
int find(int v2,int p[]);
void combine(int i,int j,int p[]);
void main()
{
int t[10][10],v1,v2,cost,low,i,k,j,n,m;
int p[20],count=0,sum=0;
clrscr();
printf("\nenter the no of vertices:");
scanf("%d",&n);
printf("\n enter the no of edges:");
scanf("%d",&m);
for(k=0;k<m;k++)
{
printf("\nthe cost of the edge from");
scanf("%d",&c[k].v1);
printf("\t\t to ");
scanf("%d",&c[k].v2);
printf(" and the cost is");
scanf("%d",&c[k].cost);
}
for(i=0;i<n;i++)
p[i]=i;
k=0;
while(count!=(n-1))
{
low=min(m);
if(low==-1)
break;
v1=c[low].v1;
v2=c[low].v2;
i=find(v1,p);
j=find(v2,p);
if(i!=j)
{
t[k][0]=v1;
t[k][1]=v2;
k++;
count++;
sum=sum+c[low].cost;
combine(i,j,p);
}
c[low].cost=INFINITY;
}
printf("\nminimum spanning tree is:");
if(count==(n-1))
{
for(i=0;i<(n-1);i++)
printf("\t%d->%d",t[i][0],t[i][1]);
printf("\n\nthe cost of the spanning tree is %d",sum);
}
getch();
}
int min(int n)
{int i,s,min;
s=INFINITY;
min=-1;
for(i=0;i<n;i++)
if(c[i].cost<s)
{
s=c[i].cost;
min=i;
}
return min;
}
int find(int v2,int p[])
{while(p[v2]!=v2)
{
v2=p[v2];
}
return v2;
}
void combine(int i,int j,int p[])
{if(i<j)
p[j]=i;
else
p[i]=j;
}
OUTPUT:
enter the no of vertices:6
enter the no of edges:9
the cost of the edge from 1 to 2
the cost is5
the cost of the edge from 2 to 3
the cost is5
the cost of the edge from 1 to 4
the cost is3
the cost of the edge from 2 to 4
the cost is2
the cost of the edge from 2 to 5
the cost is6
the cost of the edge from 4 to 5
the cost is1
the cost of the edge from 3 to 5
the cost is1
the cost of the edge from 5 to 6
the cost is2
the cost of the edge from 3 to 6
the cost is4
minimum spanning tree is: 4->5 3->5 2->4 5->6 1->4
the cost of the spanning tree is 9
Insertion sort
#include<stdio.h>
#include<conio.h>
int i;
void insert(int b[20],int m)
{
int j,p,temp;
for(p=1;p<m;p++)
{
temp=b[p];
for(j=p;j>0 && b[j-1]>temp;j--)
b[j]=b[j-1];
b[j]=temp;
}
}
void main()
{
int a[20],n;
clrscr();
printf("\n Enter size of array ");
scanf("%d",&n);
printf("\n Enter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
insert(a,n);
printf("\n Elements after sorting :");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
Shell sort
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],n,i; void shell(int a[],int n);
clrscr();
printf("\n Enter the size of the array ");
scanf("%d",&n);
printf("\n Enter the elements: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
shell(a,n);
printf("\n Elements after sorting:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
void shell(int a[],int n)
{
int j,p,k,temp;
for(k=n/2;k>0;k=k/2)
{
for(p=k;p<n;p++)
{
temp=a[p];
for(j=p; j>=k && a[j-k]>temp;j=j-k)
a[j]=a[j-k];
a[j]=temp;
}
}
}
Quick sort
#include<stdio.h>
#include<conio.h>
void main()
{
int a[20],n,i; void quick(int a[],int lb,int ub);
clrscr();
printf("\n Enter size of array: ");
scanf("%d",&n);
printf("\n Enter the elements: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick(a,0,n-1);
printf("\n Elements after sorting:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
void quick(int a[],int lb,int ub)
{
int i,j,temp,pivot;
if(lb<ub)
{
i=lb+1;
j=ub;
pivot=a[lb];
while(1)
{
while((a[i]<pivot)&&(i<=ub))
i++;
while((a[j]>pivot)&&(j>lb))
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;j--;
}
else
break;
}
a[lb]=a[j];
a[j]=pivot;
quick(a,lb,j-1);
quick(a,j+1,ub);
}
}
Merge sort
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void main()
{
int a[20],n,i; void mergesort(int a[],int n);
clrscr();
printf("\n Enter size of array:");
scanf("%d",&n);
printf("\n Enter the elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,n);
printf("\n Elements After Sorting:");
for(i=0;i<n;i++)
printf("%d\t",a[i]);
getch();
}
int leftend,tmppos,numelem,i;
void msort(int a[],int tmparray[],int left,int right);
void merge(int a[],int tmparray[],int lpos,int rpos,int rightend);
void mergesort(int a[],int n)
{
int *tmparray;
tmparray=malloc(n * sizeof(int));
if(tmparray!=NULL)
{
msort(a,tmparray,0,n-1);
free(tmparray);
}
}
void msort(int a[20],int tmparray[],int left,int right)
{
int center;
if(left<right)
{
center=(left+right)/2;
msort(a,tmparray,left,center);
msort(a,tmparray,center+1,right);
merge(a,tmparray,left,center+1,right);
}
}
void merge(int a[20],int tmparray[],int lpos,int rpos,int rightend)
{
leftend=rpos-1;
tmppos=lpos;
numelem=rightend-lpos+1;
while(lpos<=leftend && rpos<=rightend)
{
if(a[lpos]<=a[rpos])
tmparray[tmppos++]=a[lpos++];
else
tmparray[tmppos++]=a[rpos++];
}
while(lpos<=leftend)
tmparray[tmppos++]=a[lpos++];
while(rpos<=rightend)
tmparray[tmppos++]=a[rpos++];
for(i=0;i<numelem;i++,rightend--)
a[rightend]=tmparray[rightend];
}
Binary search
#include<stdio.h>
#include<conio.h>
int binsearch(int a[],int lb,int ub,int target)
{
int i,mid;
while(lb<=ub)
{
mid=(lb+ub)/2;
if(target==a[mid])
return mid;
else
if(target<a[mid])
{
ub=mid-1;
i=binsearch(a,lb,ub,target);
return i;
}
else
{
lb=mid+1;
i=binsearch(a,lb,ub,target);
return i;
}
}
return (-1);
}
void main()
{
int a[10],n,target,i;
clrscr();
printf("\n Enter the size of the array ");
scanf("%d",&n);
printf("\n Enter the array elements ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the element to find ");
scanf("%d",&target);
printf("\n The element %d is found in %d position",target,binsearch(a,0,n-1,target));
getch();
}
Sequential search
#include<stdio.h>
#include<conio.h>
int seqsearch(int k[],int n,int target)
{
int i=0;
while(i<n)
{
if(target==k[i])
return i;
i++;
}
return (-1);
}
void main()
{
int k[10],n,target,i;
clrscr();
printf("\n Enter the size of the array ");
scanf("%d",&n);
printf("\n Enter the array values ");
for(i=0;i<n;i++)
scanf("%d",&k[i]);
printf("\n Enter the element to find ");
scanf("%d",&target);
printf("\n The element %d is found in %d position",target,seqsearch(k,n,target));
getch();
}
Counting number of lines in a file
#include<stdio.h>
#include<conio.h>
#include<process.h>
void main()
{
FILE *fp;
char x;
int count=0;
clrscr();
fp=fopen("f:/ds/f1.txt","r");
if(fp==NULL)
{
printf("Error!!!!");
exit(0);
}
x=fgetc(fp);
while(x!=EOF)
{
if(x=='\n')
{
++count;
}
x=fgetc(fp);
}
printf("no of lines are : %d",count);
fclose(fp);
getch();
}
Comparing two files using pointers
#include<stdio.h>
#include<conio.h>
#include<process.h>
void main()
{
FILE *fp1,*fp2;
char a1,a2;
int flag=0;
clrscr();
fp1=fopen("f:/ds/file1.txt","r");
fp2=fopen("f:/ds/file3.txt","r");
a1=fgetc(fp1);
a2=fgetc()
{
if(a1==a2)
{
a1=fgetc(fp1);
a2=fgetc(fp2);
}
else
{
printf("files are not same");
flag=1;
break;
}
}
if(flag==0)
{
printf("files are same");
}
fclose(fp1);
fclose(fp2);
getch();
}
#include<conio.h>
#include<process.h>
void main()
{
FILE *fp1,*fp2;
char a1,a2;
int flag=0;
clrscr();
fp1=fopen("f:/ds/file1.txt","r");
fp2=fopen("f:/ds/file3.txt","r");
a1=fgetc(fp1);
a2=fgetc()
{
if(a1==a2)
{
a1=fgetc(fp1);
a2=fgetc(fp2);
}
else
{
printf("files are not same");
flag=1;
break;
}
}
if(flag==0)
{
printf("files are same");
}
fclose(fp1);
fclose(fp2);
getch();
}
No comments:
Post a Comment