try this code as it may help you
problem 1)Merge sort
// merge sort
// run using turbo c/c++ compiler
#include<iostream.h>
#include<conio.h>
#define N 1000
void msort(int *,int ,int );
void merge(int *,int ,int ,int );
void main()
{
int array[N],i,j,len;
clrscr();
cout<<"Enter the length of list to be sorted :: ";
cin>>len;
cout<<endl<<endl;
for(i=0;i<len;i++)
{
cout<<"Enter number "<<i+1<<" of the list :";
cin>>array[i];
}
msort(array,0,len-1);
cout<<"\n The sorted list is ::\n";
for(i=0;i<len;i++)
{
cout<<array[i]<<" ";
}
getch();
}
void msort(int array[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
msort(array,low,mid);
msort(array,mid+1,high);
merge(array,low,mid,high);
}
}
void merge(int array[],int low,int mid,int high)
{
int i,j,k=low;
int temp_arr[N];
i=low;
j=mid+1;
while(i<=mid&&j<=high)
{
if(array[i]<array[j])
temp_arr[k++]=array[i++];
else
temp_arr[k++]=array[j++];
}
while(i<=mid)
temp_arr[k++]=array[i++];
while(j<=high)
temp_arr[k++]=array[j++];
for(i=low;i<=high;i++)
array[i]=temp_arr[i];
}
//*****************************************************************************
//*****************************************************************************
//Problem2
// run Code using turbo c/c++ compiler
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<fstream.h>
#include<process.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
//Function Declarations
void createdb();
void route(char *to);
void assert_path(char *from,char *to);
void push(char *from,char *to);
void pop(char *from,char *to);
int ispath(char *from,char *to);
int find(char *from,char *anywhere);
int find1(char *from,char *anywhere);
int match(char *from, char *to);
//Structure for path datbase
struct pt
{
char from[4];
char to[4];
char skip; //for back tracking
char tskip; //for temp back tracking
};
struct pt path[MAX];
int p_pos=0; //number of emtries in path database
int find_pos=0; //index for searching path database
int tos=0; //top of stack
struct stack
{
char from[4];
char to[4];
};
struct stack bt_stack[MAX]; //back track stack
void main()
{
clrscr();
char from[4],to[4];
createdb();
cout<<"\n\n\nEnter Start vertex :: ";
gets(from);
cout<<"\n\nEnter End vertex :: ";
gets(to);
if(ispath(from,to)==1)
{
cout<<"\n\nThe path is.........\n\n";
route(to);
}
else
cout<<"\n\nThere is no path from :: "<<from<<" to "<<to;
getch();
}
//Function Definations
//Initialize path database
void createdb()
{
char ch,*file;
cout<<"Enter the file name :: ";
cin>>file;
cout<<endl<<endl;
ifstream in(file);
if(!in)
{
cout<<"Unable to open file........\n";
getch();
exit(0);
}
int ch1,len,count=0,flag=1,n;
char vertex[4];
in.get(ch);
while(in)
{
len=0;
while(in&&!(ch==' '||ch=='\t'||ch=='\n'))
{
vertex[len]=ch;
len++;
in.get(ch);
}
vertex[len]='\0';
while(in&&(ch==' '||ch=='\t'||ch=='\n'))
in.get(ch);
count++;
if(flag==1 && vertex!='\0')
{
n=atoi(vertex);
}
if(n<=atoi(vertex) && flag==0)
{
cout<<"\n\n Wrong entries :> internal enteries greater than total
number of vertices....\n";
getch();
exit(0);
}
flag=0;
}
if(count%2!=1)
{
cout<<"\n\nEntries are not correct in the file...\n";
exit(0);
}
else
cout<<"\n\nCreating database...........\n\n";
// Enter Graph Data
in.close();
in.open(file);
char from[4],to[4];
flag=1;
in.get(ch);
while(in)
{
while(in &&(ch==' '||ch=='\t'||ch=='\n'))
in.get(ch);
if(flag==1)
{
while(in && !(ch==' '||ch=='\t'||ch=='\n'))
{
in.get(ch);
flag=0;
}
}
else
{
len=0;
while(in && !(ch==' '||ch=='\t'||ch=='\n'))
{
from[len]=ch;
len++;
in.get(ch);
}
from[len]='\0';
while(in &&(ch==' '||ch=='\t'||ch=='\n'))
in.get(ch);
len=0;
while(in && !(ch==' '||ch=='\t'||ch=='\n'))
{
to[len]=ch;
len++;
in.get(ch);
}
to[len]='\0';
cout<<"\nFrom : "<<from<<" to "<<to;
assert_path(from,to);
}
}
in.close();
}
//Enter facts into database
void assert_path(char *from,char *to)
{
if(p_pos<MAX)
{
strcpy(path[p_pos].from,from);
strcpy(path[p_pos].to,to);
path[p_pos].skip=0;
path[p_pos].skip=0;
p_pos++;
}
else
cout<<"\nPath database full.......\n";
}
//Show the route
void route(char *to)
{
int t=0;
cout<<endl;
while(t<tos)
{
cout<<bt_stack[t].from<<" to ";
t++;
}
cout<<to;
}
//if path between from and to than return 1 else 0
int match(char *from,char *to)
{
register int t;
for(t=p_pos-1;t>-1;t--)
if(!strcmp(path[t].from,from)&&!strcmp(path[t].to,to))
return 1;
return 0; //not found
}
//Given from, find anywhere..
int find(char *from,char *anywhere)
{
find_pos=0;
while(find_pos<p_pos)
{
if(!strcmp(path[find_pos].from,from) &&!path[find_pos].skip)
{
strcpy(anywhere,path[find_pos].to);
path[find_pos].skip=1; //make active
return 1;
}
find_pos++;
}
return 0;
}
int find1(char *from,char *anywhere)
{
find_pos=0;
while(find_pos<p_pos)
{
if(!strcmp(path[find_pos].from,from) &&!path[find_pos].tskip)
{
strcpy(anywhere,path[find_pos].to);
path[find_pos].tskip=1; //make active
return 1;
}
find_pos++;
}
return 0;
}
//Determine if there is route between from and to..
int ispath(char *from,char *to)
{
char anywhere[4];
//see if at destination
if(match(from,to))
{
push(from,to);
return 1;
}
while(find(from,anywhere))
{
//breath first modification
if(match(anywhere,to))
{
push(from,to);
push(anywhere,to);
return 1;
}
}
//try any connection
if(find1(from,anywhere))
{
push(from,to);
ispath(anywhere,to);
}
else if(tos>0)
{
//backtrack
pop(from,to);
if(ispath(from,to))
return 1;
}
}
//Stack Routines
void push(char *from,char *to)
{
if(tos<MAX)
{
strcpy(bt_stack[tos].from,from);
strcpy(bt_stack[tos].to,to);
tos++;
}
else
cout<<"\nStack full....";
}
void pop(char *from,char *to)
{
if(tos>0)
{
tos--;
strcpy(from,bt_stack[tos].from);
strcpy(to,bt_stack[tos].to);
}
else
cout<<"\nStack Underflow.....";
} |
