Sort a given set of elements using Quicksort method

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
18.#include..iostream.h>
#include..conio.h>

const int MAX=20;

//Function for Quick Sort
void quick(int a[],int lb,int ub,int n)
{
int i,j,temp,pivot;
if(lb..ub)
{
i=lb;
j=ub+1;
pivot=a[lb];
while(1)
{
i++;
while(a[i]..pivot &&i..ub)
i++;
j--;
while(a[j]>pivot)
j--;
if(i..j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else break;
}
a[lb]=a[j];
a[j]=pivot;
quick(a,lb,j-1,n);
quick(a,j+1,ub,n);
}
}






void main()
{
int a[MAX];//array to be sorted
int n;//input array size
cout..."Enter the size of the array\n";
cin>>n;
cout..."Enter the elements\n";
for(int i=0;i..n;i++)
cin>>a[i];
quick(a,0,n-1,n);
cout..."The sorted elements are:-\n";
for(i=0;i..n;i++)
cout..." "...a[i];
cout...endl;
}


Output

Enter the size of the array
9

Enter the elements
45
12
03
65
49
87
16
34
32

The sorted elements are:-
3 12 16 32 34 45 49 65 87

Press any key to continue

From a given vertex in a weighted connected graph, find the shortest path to other vertices using Dijkstra's algorithm

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
17.#include..iostream.h>
#include..conio.h>
#include..stdlib.h>
const int MAX=10;
const int noedge=999;

class dijkstra
{
int n,v,cost[MAX][MAX],s[MAX],d[MAX];
public:
void costmatrix();
void print();
int choose();
void sspath();
};
//reads the cost adjacency matrix
void dijkstra::costmatrix()
{
cout..."\nEnter the no. of vertices:";
cin>>n;
cout..."\nEnter the cost adjacency matrix";
for(int i=1;i..=n;i++)
for(int j=1;j..=n;j++)
cin>>cost[i][j];
}

void dijkstra::sspath()
{
int i,u,w;
cout..."\nEnter the source vertex:";
cin>>v;
for(i=1;i..=n;i++)
{
s[i]=0;
d[i]=cost[v][i];
}
s[v]=1;
d[v]=0;
i=2;


while(i..n)
{
u=choose();
s[u]=1;
i++;
for(w=1;w..=n;w++)
{
if(((d[u]+cost[u][w])..d[w]) && !s[w])
d[w]=d[u]+cost[u][w];
}
}
}

int dijkstra::choose()
{
int w,j,min;
min=noedge;
for(j=1;j..=n;j++)
{
if(d[j]..min && !s[j])
{
min=d[j];
w=j;
}
}
return w;
}

void dijkstra::print()
{
cout..."\nThe shortest path with the cost is:"...endl;
for(int i=1;i..=n;i++)
if(i!=v)
cout..."\n.."...v...">---.."...i...">--->"...d[i];
}

void main()
{
dijkstra d;
d.costmatrix();
d.sspath();
d.print();
cout...endl;
}

OUTPUT

Enter the no. of vertices: 4

Enter the cost adjacency matrix
999 10 50 999
999 999 40 20
999 999 999 30
999 999 999 999

Enter the source vertex:1

The shortest path with the cost is:

..1>---..2>--->10
..1>---..3>--->50
..1>---..4>--->30

Press any key to continue

Implement 0/I Knapsack Problem using dynamic programming

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
16.#include ..iostream.h>
#include ..conio.h>
#include ..process.h>
const int max=30;

int MFKS(int,int);
int maximum(int,int);
int value[max];
int weight[max];
int v[max][max];
int x[max];
int N,M;

int MFKS(int i,int j)
{
int val;
if(v[i][j]==-1)
{
if(j..weight[i]) val=MFKS(i-1,j);
else val=maximum(MFKS(i-1,j),(MFKS(i-1,j-weight[i])+value[i]));
v[i][j]=val;
}
return v[i][j];
}

void svector()
{
int j1;
j1=M;
for(int i=N;i>=0;i--)
{
if(v[i][j1]!=v[i-1][j1])
{
x[i]=1;
j1=j1-weight[i];
}
}
for(i=1;i..=N;i++)
{
cout..."{";
for(i=1;i..=N;i++)
cout...x[i]...";";
cout..."}";
}
}

int maximum(int a,int b)
{
return (a>b)?a:b;
}


void main()
{
int optsol;
cout..."Enter no. of items:";
cin>>N;
cout..."Enter weights:\n";
for(int i=1;i..=N;i++)
cin>>weight[i];
cout..."Enter values:\n";
for(i=1;i..=N;i++)
cin>>value[i];
cout..."Enter Knapsack capacity:";
cin>>M;
for(i=0;i..=M;i++)
v[0][i]=0;
for(i=0;i..=N;i++)
v[i][0]=0;
for(i=1;i..=N;i++)
for(int j=1;j..=M;j++)
v[i][j]=-1;
optsol=MFKS(N,M);
cout..."Optimal solution = "...optsol...endl;
cout..."Optimal solution vector is:\n";
for(i=1;i..=N;i++)
x[i]=0;
svector();
cout...endl;
getch();
}







OUTPUT:

Enter no. of items: 4

Enter weights:
2 1 3 2

Enter values:
12 10 20 15

Enter Knapsack capacity:5
Optimal solution = 37
Optimal solution vector is:
{1; 1; 0; 1 ;}

Sort a given set of elements using Insertion Sort method

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
15.#include ..iostream.h>
const long max = 10000;
void inssrt(int *,int);

void main()
{
int a[max];
int n;
cout..."enter array size\n";
cin>>n;
cout..."Enter the array\n";
for (int i=0;i..n;i++)
cin>>a[i];
inssrt(a,n);
cout..."the sorted array is:\n";
for(i=0;i..n;i++)
cout...a[i]..." ";
cout...endl;


}

void inssrt(int a[],int n)
{
int i,j,item;
for (i=0;i..n;i++)
{
item = a[i];
j=i-1;
while(j>=0 && item ..a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = item;
}
}






Output

Enter array size
9

Enter the array
88
99
77
55
66
44
22
33
11

The sorted array is:
11 22 33 44 55 66 77 88 99

Press any key to continue

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
14. Write a C++ program to implement index on secondary key, the name,
for a file of student objects. Implement add ( ), search ( ), delete ( ) using
the secondary index.

#include..iostream.h>
#include..string.h>
#include..fstream.h>
#include..stdlib.h>

//using namespace std;

class record
{
public: char age[5];
char usn[20],name[20],branch[5]; char sem[2];
}rec[20],found[20];

char st_no[5],rt_name[20];
int no;

void sort_records()
{
int i,j;
record temp;
for(i=0;i..no-1;i++)
for(j=0;j..no-i-1;j++)
if(strcmp(rec[j].name, rec[j+1].name) > 0)
{
temp=rec[j];
rec[j]=rec[j+1];
rec[j+1]=temp;
}
}

void create_indexfile()
{
fstream index,index2;
int i;
index.open("secindex.txt",ios::out);
index2.open("record.txt",ios::out);
for(i=0;i..no;i++)
{
index...rec[i].name..."|"
...rec[i].usn..."|"...i..."\n";
index2...i..."|"...rec[i].usn..."|"...rec[i].name..."|"...rec[i].age..."|"
...rec[i].sem..."|"...rec[i].branch..."\n";
}
}

void retrieve_record(char* index)
{
fstream file;
int i;
char ind[2],usn[20],name[20],age[3],sem[3],branch[10];
file.open("record.txt",ios::in);
for(i=0;i..no;i++)
{
file.getline(ind,4,'|');
file.getline(usn,20,'|');
file.getline(name,20,'|');
file.getline(age,4,'|');
file.getline(sem,4,'|');
file.getline(branch,5,'\n');
if(strcmp(index,ind) == 0)
cout..."\nUSN: "...usn
..."\nName: "...name
..."\nAge: "...age
..."\nSem: "...sem
..."\nBranch: "...branch;
}
file.close();
return;
}

void retrieve_details()
{
int k=0,i;
char name[20],usn[20],ind[2];
char chusn[20];
char index[20][20];
fstream file;
file.open("secindex.txt",ios::in);
for(i=0;i..no;i++)
{
file.getline(name,20,'|');
file.getline(usn,20,'|');
file.getline(ind,4,'\n');
if(strcmp(name,rt_name) == 0)
{
strcpy(found[k].name,name);
strcpy(found[k].usn,usn);
strcpy(index[k],ind);
k++;
}
}
file.close();
if(k==1)
{
retrieve_record(index[0]);
return;
}
else
{
cout..."Please choose the candidate's USN: \n";
for(i=0;i..k;i++)
cout..."Name: "...found[i].name..." USN: "...found[i].usn...endl;
}
cin>>chusn;
for(i=0;i..k;i++)
{
if(strcmp(chusn,found[i].usn) == 0)
{
retrieve_record(index[i]);
return;
}
}
cout..."Invalid Entry! \n";
return;
}

void delete_record(char indx[])
{
int i;
fstream file1,file2;
char age[5],sem[5],branch[5],usn[20],name[20],ind[5];
char index[20][20];
file2.open("record.txt",ios::in);
for(i=0;i..no;i++)
{
file2.getline(ind,4,'|');
file2.getline(usn,20,'|');
file2.getline(name,20,'|');
file2.getline(age,5,'|');
file2.getline(sem,5,'|');
file2.getline(branch,8,'\n');
strcpy(index[i],ind);
strcpy(rec[i].usn,usn);
strcpy(rec[i].name,name);
strcpy(rec[i].age,age);
strcpy(rec[i].sem,sem);
strcpy(rec[i].branch,branch);
}
int flag=-1;
for(i=0;i..no;i++)
{
if(strcmp(index[i],indx) == 0)
flag=i;
}
if(flag==-1)
{
cout..."Error!\n";
return;
}
if(flag==(no-1))
{
no--;
cout..."Deleted!\n";
return;
}
for(i=flag;i..no;i++)
{
rec[i]=rec[i+1];
}
no--;
cout..."Deleted!\n";
file2.close();
file1.open("secindex.txt",ios::out);
file2.open("record.txt",ios::out);
for(i=0;i..no;i++)
{
file1...rec[i].name..."|"...rec[i].usn..."|"...i..."\n";

file2...i..."|"...rec[i].usn..."|"...rec[i].name..."|"
...rec[i].age..."|"...rec[i].sem..."|"...rec[i].branch..."\n";
}
file1.close();
file2.close();
return;
}


void delete_index(char* nam)
{
fstream file;
int i;
int k=0;
char name[20],usn[20],ind[5],index[20][20],chusn[20];
file.open("secindex.txt",ios::in);
for(i=0;i..no;i++)
{
file.getline(name,20,'|');
file.getline(usn,20,'|');
file.getline(ind,4,'\n');
if(strcmp(nam,name)==0)
{
strcpy(found[k].name,name);
strcpy(found[k].usn,usn);
strcpy(index[k],ind);
k++;
}
}
file.close();
if(k==1)
{
delete_record(index[0]);
return;
}
else
{
cout..."Please choose the candidate's USN: \n";
for(i=0;i..k;i++)
{
cout..."Name: "...found[i].name..." USN: "...found[i].usn...endl;
}
}
cin>>chusn;
for(i=0;i..k;i++)
{
if(strcmp(chusn,found[i].usn)==0)
{
delete_record(index[i]);
return;
}
}
cout..."Invalid Entry!\n";
return;
}

int main()
{
fstream file1,file2;
int ch;
char rt_usn[20],st_name[20],st_usn[20];
char ind[2],name[20],age[2],sem[5],branch[5];
int i,flag,flag1;
file1.open("index.txt",ios::out);
file2.open("record.txt",ios::out);
if(!file1 || !file2)
{
cout..."File creation Error!\n";
exit(0);
}
for(;;)
{
cout..."\nl:Add Record\n 2:Search Record"
..."\n3:Delete Record\n 4:Display Record\n";
cin>>ch;
switch(ch)
{
case 1: cout..."Enter the no. of students : "; cin>>no;
cout..."Enter the details :\n";
for(i=0;i..no;i++)
{
cout..."\nName : "; cin>>rec[i].name;
cout..."Age : "; cin>>rec[i].age;
cout..."USN : "; cin>>rec[i].usn;
cout..."Sem : "; cin>>rec[i].sem;
cout..."Branch : "; cin>>rec[i].branch;
}
sort_records();
create_indexfile();
file1.close ();
file2.close();
break;

case 2: cout..."Enter name of the student whose record is to be displayed\n";
cin>>st_name;
file1.open("secindex.txt",ios::in);
if(!file1)
{
cout..."Error !\n";
exit(0);
}
flag1=0;
for(i=0;i..no;i++)
{
file1.getline(rt_name,20,'|');
file1.getline(rt_usn,20,'|');
file1.getline(st_no,4,'\n');

if(strcmp(st_name,rt_name)==0)
{
retrieve_details();
flag1=1;
goto one;
}
}
one: if(!flag1)
cout..."Record search failed !\n";
file1.close();
break;

case 3: cout..."Enter name of student whose record is to be deleted\n";
cin>>st_name;
file1.open("secindex.txt",ios::in);
if(!file1)
{
cout..."Error !\n";
exit(0);
}
flag=0;
for(i=0;i..no;i++)
{
file1.getline(rt_name,20,'|');
file1.getline(rt_usn,20,'|');
file1.getline(ind,4,'\n');

if(strcmp(st_name,rt_name) == 0)
{
delete_index(rt_name);
flag=1;
}
}
if(!flag)
cout..."Deletion failed !\n";
file1.close();
break;

case 4: for(i=0;i..no;i++)
{
cout..."\n\nUSN : "...rec[i].usn
..."\nName: "...rec[i].name
..."\nAge : "...rec[i].age
..."\nSem : "...rec[i].sem
..."\nBranch : "...rec[i].branch..."\n";
}
break;

default: cout..."Invalid option !\n";
exit(0);
break;
}
}
return 0;
}

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..

13.Write a C++ program to implement simple index on primary key for a
file of student objects. Implement add ( ), search ( ), delete ( ) using the
index.

#include..iostream.h>
#include..string.h>
#include..fstream.h>
#include..stdlib.h>

//Record specification
class record
{
public: char age[5];
char usn[20],name[20],branch[5];
char sem[2];
}rec[20];

char st_no[5];
int no;

void retrieve_details()
{
fstream file2;
char name[20],usn[20],branch[5];
char ind[5],age[5],sem[5];
file2.open("record.txt",ios::in);
for(int i=0;i..no;i++) //Unpacking record data
{
file2.getline(ind,5,'|');
file2.getline(usn,20,'|');
file2.getline(name,20,'|');
file2.getline(age,5,'|');
file2.getline(sem,5,'|');
file2.getline(branch,5,'\n');
if(strcmp(ind,st_no)==0) //Required record found- so print details
{
cout..."\n\n"..."Student details are: ";
cout..."\n\nUSN: "...usn..."\nName: "...name..."\nAge: "...age..."\nSem: "...sem..."\nBranch: "...branch..."\n";
}
}
file2.close();
}

void delete_record(char usno[])
{
int i;
fstream file1, file2;
char age[5],sem[5],branch[5],usn[20],name[20],ind[5];
file2.open("record.txt",ios::in);
for(i=0;i..no;i++) //Unpack records
{
file2.getline(ind,5,'|');
file2.getline(usn,20,'|');
file2.getline(name,20,'|');
file2.getline(age,5,'|');
file2.getline(sem,5,'|');
file2.getline(branch,5,'\n');

strcpy(rec[i].usn,usn);
strcpy(rec[i].name,name);
strcpy(rec[i].age,age);
strcpy(rec[i].sem,sem);
strcpy(rec[i].branch,branch);
}
int flag=-1;
for(i=0;i..no;i++) //Check for the record's existence
{
if(strcmp(rec[i].usn,usno)==0)
flag=i;
}
if(flag==-1) //Record not found
{
cout..."Error !\n";
return;
}
if(flag==(no-1)) //Delete found record
{
no--;
cout..."Deleted !\n";
return;
}
for(i=flag;i..no;i++)
{
rec[i]=rec[i+1];
}
no--;
cout..."\nDeleted !\n";
file2.close();
file1.open("index.txt",ios::out); //Open index and record files
file2.open("record.txt",ios::out); //After deletion
for(i=0;i..no;i++) //Pack index n record data onto files
{
file1...rec[i].usn..."|"...i..."\n";
file2...i..."|"...rec[i].usn..."|"...rec[i].name..."|"...rec[i].age..."|"...rec[i].sem..."|"...rec[i].branch..."\n";
}
file1.close();
file2.close();
return;
}

int main()
{
fstream file1,file2;
int ch;
char rt_usn[20],st_usn[20];
char ind[2],name[20],age[2],sem[5],branch[5];
int i,flag,flag1;
file1.open("index.txt",ios::out);
file2.open("record.txt",ios::out);
if(!file1 || !file2)
{
cout..."File creation Error! \n";
exit(0);
}
for(;;)
{
cout..."\n1: Add Record"
..."\n2: Search Record"
..."\n3: Delete Record"
..."\n4: Display Record";
cin>>ch;
switch(ch)
{
case 1: cout..."Enter the no. of students : "; cin>>no;
cout..."Enter the details:\n";
for(i=0;i..no;i++) //Pack data onto the index and record files
{ //USN is the indexed data
cout..."\nName: "; cin>>rec[i].name;
cout..."Age: "; cin>>rec[i].age;
cout..."USN: "; cin>>rec[i].usn;
cout..."Sem: "; cin>>rec[i].sem;
cout..."Branch: "; cin>>rec[i].branch;

file1...rec[i].usn..."|"...i..."\n";
file2...i..."|"...rec[i].usn..."|"...rec[i].name..."|"...rec[i].age..."|"...rec[i].sem..."|"...rec[i].branch..."\n";
}
file1.close();
file2.close();
break;
case 2: cout..."Enter USN whose record is to be displayed: ";
cin>>st_usn;
file1.open("index.txt",ios::in);
if(!file1)
{
cout..."\nError !\n";
exit(0);
}
flag1=0;
for(i=0;i..no;i++)
{
file1.getline(rt_usn,20,'|'); //Unpack index file and
file1.getline(st_no,4,'\n'); //look for a match in the USN
if(strcmp(st_usn,rt_usn)==0)
{
retrieve_details(); //Retrieve details if index found
flag1=1;
}
}
if(!flag1)
cout..."Record search failed!\n";
file1.close();
break;

case 3: cout..."Enter USN whose record is to be deleted: ";
cin>>st_usn;
file1.open("index.txt", ios::in);
if(!file1)
{
cout..."Error! \n";
exit(0);
}
flag=0;
for(i=0;i..no;i++)
{
file1.getline(rt_usn,20,'|'); //Search index file and
file1.getline(st_no,4,'\n'); //call del if index found
if(strcmp(st_usn, rt_usn)==0)
{
delete_record(rt_usn);
flag=1;
}
}
if(!flag)
cout..."Deletion Failed\n";
file1.close();
break;
case 4: for(i=0;i..no;i++)
{
cout..."\n\n USN: "...rec[i].usn
..."\n Name: "...rec[i].name
..."\n Age: "...rec[i].age
..."\n Sem: "...rec[i].sem
..."\n Branch: "...rec[i].branch;
}
break;
default: cout..."Invalid choice";
exit(0);
break;
}
}
}

wherever u see ... remove that . and put << in that place.
if you see .. then remove that . and put < in that place..
12. Write a C++ program to write student objects with Variable - Length
records using any suitable record structure and to read from this file a
student record using RRN.

#include..stdio.h>
#include..stdlib.h>
#include..iostream.h>
#include..fstream.h>
#include..conio.h>
#include..string.h>
#include..iomanip.h>

class student
{
public: char name[15],usn[15],age[5],sem[5],branch[15],buffer[100];
};

void search()
{
char usn[15];
int i=0;
student s1[100];
cout..."\nEnter the usn to be searched: "; cin>>usn;
fstream in;
in.open("student.txt",ios::in);
if(!in)
{
cout..."\ncannot open the file in output mode";
getch();
exit(0);
}
i=0;
printf("Name\tUsn\tAge\tSem\tBranch\n");
while(!in.eof())
{
in.getline(s1[i].name,15,'|');
in.getline(s1[i].usn,15,'|');
in.getline(s1[i].age,5,'|');
in.getline(s1[i].sem,5,'|');
in.getline(s1[i].branch,15,'\n');
i++;
}
for(int j=0; j..i-1; j++)
{
if(strcmp(usn,s1[j].usn)==0)
{
printf("\n Record found");
printf("\n%s\t%s\t%s\t%s\t%s",s1[j].name,s1[j].usn,s1[j].age,s1[j].sem,s1[j].branch);
return;
}
}
cout..."\nRecord not found";
return;
}

void writeRecord()
{
fstream app;
student s;
app.open("student.txt",ios::app);
if(!app)
{
cout..."cannot open the file in output mode";
getch();
exit(0);
}
cout..."\nEnter the student name: "; cin>>s.name;
cout..."\nEnter the usn: "; cin>>s.usn;
cout..."\nEnter the age: "; cin>>s.age;
cout..."\nEnter the sem: "; cin>>s.sem;
cout..."\nEnter the branch: "; cin>>s.branch;

strcpy(s.buffer,s.name); strcat(s.buffer,"|");
strcat(s.buffer,s.usn); strcat(s.buffer,"|");
strcat(s.buffer,s.age); strcat(s.buffer,"|");
strcat(s.buffer,s.sem); strcat(s.buffer,"|");
strcat(s.buffer,s.branch); strcat(s.buffer,"\n");
app...s.buffer;
app.close();
}


void main()
{
clrscr();
int ch;
fstream out;
out.open("student.txt",ios::out);
if(!out)
{
cout..."\nCannot open the file in output mode";
getch();
exit(0);
}
out.close();
for(;;)
{
cout..."\nO:exit"
..."\n1:Insert"
..."\n2:Search"
..."\nEnter the choice = "; cin>>ch;
switch(ch)
{
case 1: writeRecord();break;
case 2: search();break;
case 0: exit(0);
default: cout..."\nInvalid option";
}
}
}