VTU ISE !!!!: File Structure Lab Programs -Part B

File structure- PART-B

PROGRAM-7

#include<fstream.h>
#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<process.h>

void write_file()
{
char name[20][20],temp[20];
fstream f1("file1.txt",ios::out);
fstream f2("file2.txt",ios::out);
int i,j,m,n;
if((!f1)||(!f2))
{
cout<<"Unable to open the files!!\n";
exit(0);
}
cout<<"Enter the number of records in file 1: ";
cin>>m;
cout<<"Enter the names:\n";
for(i=0;i<m;i++)
cin>>name[i];
for(i=0;i<m-1;i++)
{
for(j=0;j<m-i-1;j++)
{
if(strcmp(name[j],name[j+1])>0)
{
strcpy(temp,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],temp);
}
}
}
for(i=0;i<m;i++)
f1<<name[i]<<endl;
cout<<"Enter the number of records in file 2: ";
cin>>n;
cout<<"Enter the names:\n";
for(i=0;i<n;i++)
cin>>name[i];
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(strcmp(name[j],name[j+1])>0)
{
strcpy(temp,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],temp);
}
}
}
for(i=0;i<n;i++)
f2<<name[i]<<endl;
f1.close();
f2.close();
}

void main()
{
fstream f1("file1.txt",ios::in);
fstream f2("file2.txt",ios::in);
fstream f3("output.txt",ios::out);
char l1[100][20],l2[100][20],l3[100][20];
int i=0,j=0,k=0,m=0,n=0;
write_file();
if((!f1)||(!f2)||(!f3))
{
cout<<"Unable to open the files!!\n";
exit(0);
}
cout<<"Contents of file 1 are:\n";
while(!f1.eof())
{
f1.getline(l1[i],20,'\n');
cout<<l1[i++]<<endl;
m++;
}
cout<<"Contents of file 2 are:\n";
while(!f2.eof())
{
f2.getline(l2[j],20,'\n');
cout<<l2[j++]<<endl;
n++;
}
m--;
n--;
i=0,j=0;
while(i<m&&j<n)
{
if(strcmp(l1[i],l2[j])==0)
{
strcpy(l3[k],l1[i]);
f3<<l3[k]<<endl;
i++;
j++;
k++;
}
else if(strcmp(l1[i],l2[j])<0)
i++;
else
j++;
}
if(k==0)
cout<<"No common names!!\n";
else
{
cout<<"The names that are common are:\n";
for(i=0;i<k;i++)
cout<<l3[i]<<endl;
}
}
==========================================================
==========================================================
PROGRAM-8

#include<stdio.h>
#include<iostream.h>
#include<fstream.h>
#include<string.h>

class record
{
public:
char name[20],usn[20];
}rec[20];

char fname[8][8]={"1.txt","2.txt","3.txt","4.txt","5.txt","6.txt","7.txt","8.txt"};
fstream file[8];
int n;

void merge_file(char *fil1,char *fil2,char *fil)
{
record rcd[20];
fstream f1(fil1,ios::in);
fstream f2(fil2,ios::in);
fstream f3(fil,ios::out);
int i,j,k=0,k1;
record temp;
while(!f1.eof())
{
f1.getline(rcd[k].name,20,'|');
f1.getline(rcd[k++].usn,20);
}
while(!f2.eof())
{
f2.getline(rcd[k].name,20,'|');
f2.getline(rcd[k++].usn,20);
}
k1=k;
for(i=0;i<k-2;i++)
{
for(j=0;j<k-i-2;j++)
{
if(strcmp(rcd[j].name,rcd[j+1].name)>0)
{
temp=rcd[j];
rcd[j]=rcd[j+1];
rcd[j+1]=temp;
}
else if(strcmp(rcd[j].name,rcd[j+1].name)==0)
{
if(strcmp(rcd[j].usn,rcd[j+1].usn)>0)
{
temp=rcd[j];
rcd[j]=rcd[j+1];
rcd[j+1]=temp;
}
else if(strcmp(rcd[j].usn,rcd[j+1].usn)==0)
{
j++;
k1--;
n--;
}
}
}
}
for(i=1;i<k1-1;i++)
{
f3<<rcd[i].name<<"|"<<rcd[i].usn<<endl;
}
f1.close();
f2.close();
f3.close();
}

void k_merge()
{
char filname[7][20]={"11.txt","22.txt","33.txt","44.txt","111.txt","222.txt","1111.txt"};
int i,j=0;
for(i=0;i<8;i+=2)
merge_file(fname[i],fname[i+1],filname[j++]);
j=4;
for(i=0;i<4;i+=2)
merge_file(filname[i],filname[i+1],filname[j++]);
merge_file(filname[4],filname[5],filname[6]);
}

void main()
{
int i;
char name[20],usn[20];
n=0;
for(i=0;i<8;i++)
file[i].open(fname[i],ios::out);
cout<<"Enter number of records: ";
cin>>n;
cout<<"Enter Name and USN:\n";
for(i=0;i<n;i++)
{
cout<<"Student "<<i+1<<" : ";
cin>>rec[i].name>>rec[i].usn;
file[i%8]<<rec[i].name<<"|"<<rec[i].usn<<endl;
}
for(i=0;i<8;i++)
file[i].close();
k_merge();
fstream output("1111.txt",ios::in);
cout<<"\nThe sorted records are:\n";
cout<<"NAME\tUSN\n";
for(i=0;i<n;i++)
{
output.getline(name,20,'|');
output.getline(usn,20);
cout<<name<<"\t"<<usn<<endl;
}
}

==========================================================

PROGRAM-9

#include<iostream.h>

#include<stdio.h>

#include<fstream.h>

#include<stdlib.h>

#include<string.h>

class node

{

public:

int a[4];

node * next[4];

node * parent;

int size;

node();

};

node :: node()

{

for(int i = 0; i < 4; i++)

next[i] = NULL;

parent = NULL;

size = 0;

}

class btree

{

node * root;

public:

node* findLeaf(int key,int &level);

void updateKey(node *p,node *c,int newKey);

void search(int key);

void insert(int key);

void insertIntoNode(node *n,int key,node *address);

void promote(node *n,int key,node *address);

node* split(node *n);

void traverse(node *ptr);

btree();

};

void btree :: traverse(node *ptr)

{

if(ptr == NULL)

return;

for(int i = 0; i < ptr->size; i++)

cout<<ptr->a[i]<<" ";

cout<<endl;

for(i = 0; i < ptr->size;i++)

traverse(ptr->next[i]);

}

btree :: btree()

{

root = NULL;

}

node* btree :: findLeaf(int key,int &level)

{

node *ptr = root;

node *prevptr = NULL;

level = 0;

int i;

while(ptr)

{

i = 0;

level++;

cout<<level<<endl;

while(i < ptr -> size-1 && key > ptr -> a[i])

i++;

prevptr = ptr;

ptr = ptr -> next[i];

}

return prevptr;

}

node* btree :: split(node *n)

{

int midpoint = (n -> size+1)/2;

int newsize = n->size - midpoint;

node *newptr = new node;

node *child;

newptr->parent = n -> parent;

int i;

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

{

newptr->a[i] = n->a[i];

newptr ->next[i] = n->next[i];

n->a[i] = n->a[i+midpoint];

n->next[i] = n->next[i+midpoint];

}

n->size = midpoint;

newptr -> size = newsize;

for( i = 0; i < n->size; i++)

{

child = n->next[i];

if(child!= NULL)

child -> parent = n;

}

for( i = 0; i < newptr -> size; i++)

{

child = newptr -> next[i];

if(child!= NULL)

child -> parent = newptr;

}

return newptr;

}

void btree :: updateKey(node *parent,node *child,int newkey)

{

if(parent == NULL)

return;

if(parent->size == 0)

return;

int oldkey = child->a[child->size-2];

while(parent)

{

for(int i = 0; i < parent->size;i++)

if(parent->a[i] == oldkey)

{

parent->a[i] = newkey;

parent->next[i] = child;

}

child=parent;

parent=parent->parent;

}

void btree :: insertIntoNode(node *n,int key,node *address)

{

int i;

if( n == NULL)

return;

for(i = 0; i < n->size; i++)

if(n->a[i] == key)

return;

i = n->size-1;

while(i >= 0 && n -> a[i] > key)

{

n->a[i+1] = n->a[i];

n->next[i+1] = n->next[i];

i--;

}

i++;

n->a[i] = key;

n->next[i] = address;

n->size++;

if( i == n->size-1)

updateKey(n->parent,n,key);

}

void btree :: promote(node *n,int key,node *address)

{

if( n == NULL)

return;

if(n -> size < 4)

{

insertIntoNode(n,key,address);

return;

}

if( n == root)

{

root = new node;

n->parent = root;

}

node *newptr = split(n);

node *t;

if(key < n->a[0])

t = newptr;

else

t = n;

insertIntoNode(t,key,address);

promote(n->parent,n->a[n->size-1],n);

promote(newptr->parent,newptr->a[newptr->size-1],newptr);

}

void btree :: insert(int key)

{

if( root == NULL)

{

root = new node;

root->a[root->size] = key;

root->size++;

return;

}

int level;

node *leaf = findLeaf(key,level);

int i;

for(i = 0; i < leaf->size; i++)

if(leaf -> a[i] == key)

{

cout<<"The Key to be inserted already exists"<<endl;

return;

}

promote(leaf,key,NULL);

cout<<"---------------\n";

traverse(root);

cout<<"----------------\n";

}

void btree :: search(int key)

{

if(root == NULL)

{ cout<<"The tree Does not exist"<<endl;

return;

}

int level;

node *leaf = findLeaf(key,level);

int flag = 0;

for(int i = 0; i < leaf ->size; i++)

if(leaf->a[i] == key)

{

flag = 1;

cout<<"The Key "<<key<<" Exists in the B-Tree at the level"<<level<<endl;

}

if(!flag)

cout<<"The Key Searched for was not found"<<endl;

}

int main()

{

btree b;

int choice = 1,key;

while(choice !=3)

{

cout<<"1.Insert a Key\n";

cout<<"2.Search a key\n";

cout<<"3.Exit\n";

cin>>choice;

switch(choice)

{

case 1: cout<<"Enter The Key to be inserted in B-Tree\n";

cin>>key;

b.insert(key);

break;

case 2: cout<<"Enter The key to be searched\n";

cin>>key;

b.search(key);

break;

}

return 0;

}

==========================================================

PROGRAM-10

#include<iostream.h>

#include<stdio.h>

#include<fstream.h>

#include<stdlib.h>

#include<string.h>

class node

{

public:

int a[4];

node * next[4];

node * parent;

int size;

node();

};

class linkleaf

{

public:

node * data;

linkleaf *next;

linkleaf();

};

linkleaf :: linkleaf()

{

next = NULL;

}

node :: node()

{

for(int i = 0; i < 4; i++)

next[i] = NULL;

parent = NULL;

size = 0;

}

class btree

{

node * root;

linkleaf *head;

int flag;

public:

node* findLeaf(int key,int &level);

void updateKey(node *p,node *c,int newKey);

void search(int key);

void insert(int key);

void insertIntoNode(node *n,int key,node *address);

void promote(node *n,int key,node *address);

node* split(node *n);

void traverse(node *ptr);

void connectLeaf(node *n,node *newptr);

void traverseleaf();

btree();

};

void btree :: traverseleaf()

{

linkleaf * ptr = head;

int i;

while(ptr)

{

for(i = 0; i < ptr -> data -> size; i++)

cout<<ptr -> data -> a[i]<<" ";

cout<<endl;

ptr = ptr ->next;

}

void btree :: connectLeaf(node *n,node *newptr)

{

linkleaf *ptr = head,*prevptr = NULL,*p;

while(ptr)

{

if(ptr-> data == n)

break;

prevptr = ptr;

ptr = ptr ->next;

}

if( ptr == NULL)

{

cout<<"Unexpected Error!!";

exit(0);

}

if( ptr == head)

{

p = new linkleaf;

p -> next = head;

head = p;

p->data = newptr;

}

else

{

p = new linkleaf;

p-> next = ptr;

prevptr -> next = p;

p->data = newptr;

}

void btree :: traverse(node *ptr)

{
int i;

if(ptr == NULL)

return;

for(i = 0; i < ptr->size; i++)

cout<<ptr->a[i]<<" ";

cout<<endl;

for(i = 0; i < ptr->size;i++)

traverse(ptr->next[i]);

}

btree :: btree()

{

root = NULL;

head = NULL;

}

node* btree :: findLeaf(int key,int &level)

{

node *ptr = root;

node *prevptr = NULL;

level = 0;

int i;

while(ptr)

{

i = 0;

level++;

while(i < ptr -> size-1 && key > ptr -> a[i])

i++;

prevptr = ptr;

ptr = ptr -> next[i];

}

return prevptr;

}

node* btree :: split(node *n)

{

int midpoint = (n -> size+1)/2;

int newsize = n->size - midpoint;

node *newptr = new node;

node *child;

newptr->parent = n -> parent;

int i;

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

{

newptr->a[i] = n->a[i];

newptr ->next[i] = n->next[i];

n->a[i] = n->a[i+midpoint];

n->next[i] = n->next[i+midpoint];

}

n->size = midpoint;

newptr -> size = newsize;

for( i = 0; i < n->size; i++)

{

child = n->next[i];

if(child!= NULL)

child -> parent = n;

}

for( i = 0; i < newptr -> size; i++)

{

child = newptr -> next[i];

if(child!= NULL)

child -> parent = newptr;

}

return newptr;

}

void btree :: updateKey(node *parent,node *child,int newkey)

{

if( parent == NULL)

return;

if(parent->size == 0)

return;

int oldkey = child->a[child->size-2];

while(parent)

{

for(int i = 0; i < parent->size;i++)

if(parent->a[i] == oldkey)

{

parent->a[i] = newkey;

parent->next[i] = child;

}

child=parent;

parent=parent->parent;

}

void btree :: insertIntoNode(node *n,int key,node *address)

{

int i;

if( n == NULL)

return;

for(i = 0; i < n->size; i++)

if(n->a[i] == key)

return;

i = n->size-1;

while(i >= 0 && n -> a[i] > key)

{

n->a[i+1] = n->a[i];

n->next[i+1] = n->next[i];

i--;

}

i++;

n->a[i] = key;

n->next[i] = address;

n->size++;

if( i == n->size-1)

updateKey(n->parent,n,key);

}

void btree :: promote(node *n,int key,node *address)

{

if( n == NULL)

return;

if(n -> size < 4)

{

insertIntoNode(n,key,address);

return;

}

if( n == root)

{

root = new node;

n->parent = root;

}

node *newptr = split(n);

node *t;

if(key < n->a[0])

t = newptr;

else

t = n;

insertIntoNode(t,key,address);

if(!flag)

{ connectLeaf(n,newptr);flag = 1;}

promote(n->parent,n->a[n->size-1],n);

promote(newptr->parent,newptr->a[newptr->size-1],newptr);

}

void btree :: insert(int key)

{

flag = 0;

if( root == NULL)

{

root = new node;

root->a[root->size] = key;

root->size++;

head = new linkleaf;

head -> data = root;

return;

}

int level;

node *leaf = findLeaf(key,level);

int i;

for(i = 0; i < leaf->size; i++)

if(leaf -> a[i] == key)

{

cout<<"The Key to be inserted already exists"<<endl;

return;

}

promote(leaf,key,NULL);

cout<<"---------------\n";

traverse(root);

cout<<"----------------\n";

}

void btree :: search(int key)

{

if(root == NULL)

{ cout<<"The tree Does not exist"<<endl;

return;

}

int level;

node *leaf = findLeaf(key,level);

int flag = 0;

for(int i = 0; i < leaf ->size; i++)

if(leaf->a[i] == key)

{

flag = 1;

cout<<"The Key "<<key<<" Exists in the B-Tree at the level"<<level<<endl;

}

if(!flag)

cout<<"The Key Searched for was not found"<<endl;

}

int main()

{

btree b;

int choice = 1,key;

while(choice <=3)

{

cout<<"1.Insert a Key\n";

cout<<"2.Search a key\n";

cout<<"3.Traverse Leaf\n";

cout<<"4.Exit\n";

cin>>choice;

switch(choice)

{

case 1: cout<<"Enter The Key to be inserted in B-Tree\n";

cin>>key;

b.insert(key);

break;

case 2: cout<<"Enter The key to be searched\n";

cin>>key;

b.search(key);

break;

case 3: b. traverseleaf();

break;

}

return 0;

}

===========================================================

PROGRAM-11

#include<iostream.h>

#include<fstream.h>

#include<stdio.h>

#include<string.h>

class node

{

public:

char name[15],usn[15];

node* next;

};

node*h[29];

void insert()

{

char name[15],usn[15],buf[50];

fstream file("student.txt",ios::app);

cout<<"enter name and usn";

cin>>name>>usn;

strcpy(buf,name);

strcat(buf,"|");

strcat(buf,usn);

strcat(buf,"\n");

file<<buf;

file.close();

}

void hash_ins(char name[],char usn[],int hash_key)

{

node*p,*prev,*cur;

p=new node;

strcpy(p->name,name);

strcpy(p->usn,usn);

p->next=NULL;

prev=NULL;

cur=h[hash_key];

if(cur==NULL)

{

h[hash_key]=p;

return;

}

while(cur!=NULL)

{

prev=cur;

cur=cur->next;

}

prev->next=p;

}

void display()

{

node*cur;

fstream file("student.txt",ios::in);

char name[15],usn[15];

int j,count;

for(int i=0;i<29;i++)

{

h[i]=NULL;

}

while(!file.eof())

{

file.getline(name,15,'|');

file.getline(usn,15);

count=0;

for(j=0;j<strlen(usn);j++)

count+=usn[j];

count=count%29;

hash_ins(name,usn,count);

}

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

{

cur=h[i];

if(cur!=NULL)

{

cout<<i<<"---";

while(cur!=NULL)

{

cout<<cur->name<<"|"<<cur->usn<<"\t";

cur=cur->next;

}

cout<<"\n";

}

file.close();

}

void retrieve()

{

fstream file("student.txt",ios::in);

char name[15],usn[15];

int j,count;

node*cur;

for(int i=0;i<29;i++)

{

h[i]=NULL;

}

while(!file.eof())

{

file.getline(name,15,'|');

file.getline(usn,15);

count=0;

for(j=0;j<strlen(usn);j++)

count+=usn[j];

count=count%29;

hash_ins(name,usn,count);

}

cout<<"enter usn\n";

cin>>usn;

count=0;

for(j=0;j<strlen(usn);j++)

count+=usn[j];

count=count%29;

cur=h[count];

if(cur==NULL)

{

cout<<"record not found\n";

return;

}

{

if(strcmp(cur->usn,usn)==0)

{

cout<<"record found\nname:"<<cur->name<<"\nUSN:"<<cur->usn<<endl;

return;

}

else

cur=cur->next;

}while(cur!=NULL);

}

void main()

{

int ch;

{

cout<<"1:insert 2:retrive 3:display the table 4:exit\n";

cout<<"enter your choice";

cin>>ch;

switch(ch)

{

case 1:insert();break;

case 2:retrieve();break;

case 3:display();break;

case 4:break;

}

}while(ch!=4);

}

=========================================================

PROGRAM-12

#include<iostream.h>

#include<fstream.h>

#include<ostream.h>

#include<string.h>

#include<stdio.h>

class node

{

public:

node* next;

int offset;

node()

{

next=NULL;

offset=0;

}

};

node*first;

char p[20][20];

int nor;

char buff[90];

class student

{

public:

char name[20],usn[20],branch[20],sem[20];

void del();

void insert();

void display();

};

void student::insert()

{

fstream f1("record.txt",ios::in|ios::out);

fstream f2("avail.txt",ios::out);

node*cur=first;

cout<<"enter the usn,name,branch,sem\n";

cin>>usn>>name>>branch>>sem;

for(int i=0;i<90;i++)

buff[i]=NULL;

strcpy(buff,usn);

strcat(buff,"|");

strcat(buff,name);

strcat(buff,"|");

strcat(buff,branch);

strcat(buff,"|");

strcat(buff,sem);

strcat(buff,"|");

if(cur==NULL)

{

f1.seekp(0,ios::end);

f1.write(buff,sizeof(buff));

strcpy(p[nor],usn);

nor++;

}

else

{

i=first->offset;

f1.seekp(i,ios::beg);

f1.write(buff,sizeof(buff));

node *cur=first;

first=first->next;

delete(cur);

strcpy(p[i/sizeof(buff)],usn);

}

cur=first;

while(cur)

{

f2<<cur->offset<<endl;

cur=cur->next;

}

f1.close();

f2.close();

}

void student::del()

{

fstream f1("record.txt",ios::in|ios::out);

fstream f2("avail.txt",ios::out);

cout<<"enter the usn to deleted\n";

char key[20];

int flag=-1;

cin>>key;

node *a;

for(int i=0;i<nor;i++)

if(strcmp(p[i],key)==0)

{

flag=i;

}

if(flag!=-1)

{

cout<<"record deleted\n";

a=new node;

f1.seekp(flag*sizeof(buff),ios::beg);

a->offset=f1.tellp();

for(i=0;i<(int)strlen(key);i++)

f1<<"*";

a->next=first;

first=a;

}

else

{

cout<<"not found";

}

node *cur=first;

while(cur)

{

f2<<cur->offset<<endl;

cur=cur->next;

}

f1.close();

f2.close();

}

void student::display()

{

fstream f1("record.txt",ios::in|ios::out);

fstream f2("avail.txt",ios::out);

int j=0;

while(!f1.eof())

{

f1.seekp(j,ios::beg);

f1.getline(usn,20,'|');

f1.getline(name,20,'|');

f1.getline(branch,20,'|');

f1.getline(sem,20,'|');

cout<<"usn\tname\tbranch\tsem\n";

if(usn[0]!='*')

{

cout<<usn<<"\t"<<name<<"\t"<<branch<<"\t"<<sem<<endl;

}

j=j+sizeof(buff);

}

f1.close();

f2.close();

}

void main()

{

student s;

int ch;

{

cout<<"1:insert 2:delete 3:display 4:exit\n";

cout<<"enter your choice";

cin>>ch;

switch(ch)

{

case 1:s.insert();

break;

case 2:s.del();

break;

case 3:s.display();

break;

case 4:remove("record.txt");

remove("avail.txt");

break;

}

}while(ch!=4);

}

File Structure Lab Programs -Part B

1 comment: