Bnmit File Structure Lab Manual 5h323n
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3b7i
Overview 3e4r5l
& View Bnmit File Structure Lab Manual as PDF for free.
More details w3441
- Words: 6,914
- Pages: 106
Department of Information Science & Engineering
FILE STRUCTURE LABORATORY MANUAL SUBCODE: 06ISL67, VI SEMESTER B.E
Vidyaya Amrutham Ashnuthe
BNM Institute of Technology (Approved by AICTE & d to VTU, Karnataka) (An ISO 9001:2008 Certified Institution) Post Box No, 7087, 27th cross, 12th Main Road, Banshankari 2nd Stage, Bengalore-560070 Phone: 91-8026711781/26711782 Fax: 91-80-26710881,E-mail:[email protected] Visit us at: www.bnmit.org
VTU LAB SYLLABUS FILE STRUCTURE LABORATORY Subject Code No. of Practical
: 06ISL67 : 03
IA Marks : 25 Exam Hours : 03
Hours/Week Total No. of Practical
: 42
Exam Marks : 50
Hours
1. Write a C++ program to read series of names, one per line, from standard input and write these names spelled in reverse order to the standard output using I/O redirection and pipes. Repeat the exercise using an input file specified by the instead of the standard input and using an output file specified by the instead of the standard output. 2. Write a C++ program to read and write student objects with fixed-length records and the fields delimited by “|”. Implement pack ( ), unpack ( ), modify ( ) and search ( ) methods. 3. Write a C++ program to read and write student objects with Variable - Length records using any suitable record structure. Implement pack ( ), unpack ( ), modify ( ) and search ( ) methods. 4. 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. 5. Write a C++ program to implement simple index on primary key for a file of student objects. Implement add ( ), search ( ), delete ( ) using the index. 6. 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.
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 2
7. Write a C++ program to read two lists of names and then match the names in the two lists using Cosequential Match based on a single loop. Output the names common to both the lists. 8. Write a C++ program to read k Lists of names and merge them using k-way merge algorithm with k = 8. 9. Write a C++ program to implement B-Tree for a given set of integers and its operations insert ( ) and search ( ). Display the tree. 10. Write a C++ program to implement B+ tree for a given set of integers and its operations insert ( ), and search ( ). Display the tree. 11. Write a C++ program to store and retrieve student data from file using hashing. Use any collision resolution technique. 12. Write a C++ program to reclaim the free space resulting from the deletion of records using linked lists.
Contents VTU LAB SYLLABUS......................................................................................2 Contents...................................................................................................... 3 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 3
Program 1.................................................................................................... 5 Program 2.................................................................................................... 9 Program 3.................................................................................................. 19 Program 4.................................................................................................. 27 Program 5.................................................................................................. 33 Program 6.................................................................................................. 42 Program 7.................................................................................................. 58 Progrm 8.................................................................................................... 63 Program 9.................................................................................................. 68 Program 10................................................................................................79 Program 11................................................................................................93 Program 12..............................................................................................100
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 4
Program 1 Write a C++ program to read series of names, one per line, from standard input and write these names spelled in reverse order to the standard output using I/O redirection and pipes. Repeat the exercise using an input file specified by the instead of the standard input and using an output file specified by the instead of the standard output. #include
#include
#include<process.h> #include<string.h> #include
class names { public:char name[50]; }; void reverse(ofstream &out,char name[255]) { char *rev; rev=name+strlen(name)-1; while(rev>=name) { cout<<*rev; out<<*rev; rev--; } cout<<endl; out<<"\n"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 5
} void main() { names n[10]; clrscr(); ofstream out; out.open("file.txt",ios::out|ios::app|ios::trunc); int m; cout<<"enter the no. of names to be entered\n"; cin>>m; for(int i=0;i<m;i++) { cout<<"enter name"; cin>>n[i].name; cout<<"the name in reverse order"; reverse(out,n[i].name); } out.close(); ifstream in; in.open("file.txt",ios::in|ios::binary); ofstream outf; outf.open("f1.txt",ios::out|ios::app|ios::trunc); char ch[255]; cout<<"names from files\n"; while(in) { in.getline(ch,255); if(in) reverse(outf,ch); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 6
} cout<<endl; in.close(); outf.close(); in.open("f1.txt",ios::in|ios::binary); outf.open("f2.txt",ios::out|ios::app|ios::trunc); cout<<"reverse order from files\n"; while(in) { in.getline(ch,255); if(in) reverse(outf,ch); } in.close(); outf.close(); getch(); } Output: Enter the no. of names to be entered 5 Enter name priya The name in reverse order ayirp Enter name pa The name in reverse order amdap Enter name BNMIT/ISE/2012/VI/ File Structure laboratory
Page 7
ajit The name in reverse order tija
Enter name sohan The name in reverse order nahos Enter name dilip The name in reverse order pilid The names from files (f1.txt) priya pa ajit soni dilip Reverse order from files (f2.txt) ayirp amdap tija nahos pilid
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 8
Program 2 Write a C++ program to read and write and student objects with fixed length records and the fields delimited by “|”.implement pack(),unpack(),modify() and search() methods.
#include<stdio.h> #include
#include
#include<stdlib.h> #include
#include<string.h> class student { public:char name[25],usn[15],branch[15],buffer[45]; }; student s,s1[100]; char extra[45]; int i,no=0,mode=0; void pack() { fstream app; if(mode==0) app.open("st1.txt",ios::app); else app.open("st1.txt",ios::out); if(!app) { cout<<"cant open the file in output mode"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 9
getch(); exit(0); } stry(s.buffer,s.name); strcat(s.buffer,"|"); strcat(s.buffer,s.usn); strcat(s.buffer,"|"); strcat(s.buffer,s.branch); int count=strlen(s.buffer); for(int k=0;k<45-count;k++) strcat(s.buffer,"|"); strcat(s.buffer,"\n"); app<<s.buffer; app.close(); } void unpack() { fstream in; in.open("st1.txt",ios::in); i=0,no=0; if(!in) { cout<<"cant open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(s1[i].name,15,'|'); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 10
in.getline(s1[i].usn,15,'|'); in.getline(s1[i].branch,15,'|'); in.getline(extra,45,'\n'); no++; i++; } in.close(); } void write() { cout<<"\n enter the student name\n"; cin>>s.name; cout<<"enter the student usn\n"; cin>>s.usn; cout<<"enter the student branch\n"; cin>>s.branch; pack(); mode=0; } void search() { char usn[15],extra[45]; cout<<"enter the usn to search="; cin>>usn; unpack(); for(i=0;i<no;i++) { if(strcmp(s1[i].usn,usn)==0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 11
cout<<"\nrecord found"; cout<<"\n"<<s1[i].name<<"\t"<<s1[i].usn<<"\t"<<s1[i].branch; getch(); return; } } cout<<"record not found"; getch(); return; } void display() { cout<<"name\t\t usn\t\t branch\n\n"; unpack(); for(int i=0;i<no;i++) cout<<"\n\n"<<s1[i].name<<"\t\t"<<s1[i].usn<<"\t\t"<<s1[i].branch; getch(); } void modify() { char usn[15],buffer[15],extra[45]; cout<<"enter the usn to search\n"; cin>>usn; unpack();no--; for(int j=0;j<no;j++) { if(strcmp(usn,s1[j].usn)==0) { cout<<"the old values of the record are with BNMIT/ISE/2012/VI/ File Structure laboratory
Page 12
usn"<<usn<<"are"; cout<<"\nname="<<s1[j].name; cout<<"\nusn="<<s1[j].usn; cout<<"\nbranch="<<s1[j].branch; cout<<"enter the new values\n"; cout<<"\nname="; cin>>s1[j].name; cout<<"\nusn="; cin>>s1[j].usn; cout<<"\nbranch="; cin>>s1[j].branch; break; } } if(j==no) { cout<<"the record with usn is not present"; getch(); return; } mode=1; for(j=0;j<no;j++) { stry(s.name,s1[j].name); stry(s.usn,s1[j].usn); stry(s.branch,s1[j].branch); pack(); mode=0; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 13
cout<<"record modified\n"; } void main() { clrscr(); int choice; for(;;) { //clrscr(); cout<<"\n0:exit"; cout<<"\n1:write"; cout<<"\n2:display"; cout<<"\n3:modify"; cout<<"\n4:search"; cout<<"enter u choice\n"; cin>>choice; switch(choice) { case 1:write(); break; case 2:display(); break; case 3:modify(); break; case 4:search(); break; case 0:exit(0); default:cout<<"\ninvalid input"; break; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 14
} } }
Output: 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Karthik Enter the student USN 1bg09is015 Enter the student branch Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Dhanvi Enter the student USN 1bg09is007 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 15
Enter the student branch Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 2 Name
USN
Karthik1bg09is015 Dhanvi
Branch Ise
1bg09is007
Ise
0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 3 Enter the USN to Modify 1bg09is007 Record found The old values of the record with usn 1bg09is007 are USN=1bg09is007 Name=Dhanvi Branch=ise Enter new values Name=dhruva USN=1bg09is023 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 16
Branch=ise Record modified 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 4 Enter the usn to search 1bg09is023 Record found Dhruva 1bg09is023 Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 0 Output from text file karthik|1bg09is015|ise||||||||||||||||||||||| dhruva|1bg09is023|ise||||||||||||||||||||||||
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 17
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 18
Program 3 Write a C++ program to read and write and student objects with variable length records using any suitable record structure. Implement pack(),unpack(),modify() and search() methods. #include<stdio.h> #include
#include
#include<stdlib.h> #include
#include<string.h> class student { public:char name[25],usn[15],branch[15],buffer[45]; }; student s,s1[100]; char extra[45]; int i,no=0,mode=0; void pack() { fstream app; if(mode==0) app.open("st2.txt",ios::app); else app.open("st2.txt",ios::out); if(!app) { cout<<"cant open the file in output mode"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 19
getch(); exit(0); } stry(s.buffer,s.name); strcat(s.buffer,"|"); strcat(s.buffer,s.usn); strcat(s.buffer,"|"); strcat(s.buffer,s.branch); //int count=strlen(s.buffer); //for(int k=0;k<45-count;k++) //strcat(s.buffer,"|"); strcat(s.buffer,"\n"); app<<s.buffer; app.close(); } void unpack() { fstream in; in.open("st2.txt",ios::in); i=0,no=0; if(!in) { cout<<"cant open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(s1[i].name,15,'|'); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 20
in.getline(s1[i].usn,15,'|'); in.getline(s1[i].branch,15,'\n'); //in.getline(extra,45,'\n'); no++; i++; } in.close(); } void write() { cout<<"\n enter the student name\n"; cin>>s.name; cout<<"enter the student usn\n"; cin>>s.usn; cout<<"enter the student branch\n"; cin>>s.branch; pack(); mode=0; } void search() { char usn[15],extra[45]; cout<<"enter the usn to search="; cin>>usn; unpack(); for(i=0;i<no;i++) { if(strcmp(s1[i].usn,usn)==0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 21
cout<<"\nrecord found"; cout<<"\n"<<s1[i].name<<"\t"<<s1[i].usn<<"\t"<<s1[i].branch; getch(); return; } } cout<<"record not found"; getch(); return; } void display() { cout<<"name\t\t usn\t\t branch\n\n"; unpack(); for(int i=0;i<no;i++) cout<<"\n\n"<<s1[i].name<<"\t\t"<<s1[i].usn<<"\t\t"<<s1[i].branch; getch(); } void modify() { char usn[15],buffer[15],extra[45]; cout<<"enter the usn to search\n"; cin>>usn; unpack();no--; for(int j=0;j<no;j++) { if(strcmp(usn,s1[j].usn)==0) { cout<<"the old values of the record are with usn" <<usn << " are"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 22
cout<<"\nname="<<s1[j].name; cout<<"\nusn="<<s1[j].usn; cout<<"\nbranch="<<s1[j].branch; cout<<"enter the new values\n"; cout<<"\nname="; cin>>s1[j].name; cout<<"\nusn="; cin>>s1[j].usn; cout<<"\nbranch="; cin>>s1[j].branch; break; } } if(j==no) { cout<<"the record with usn is not present"; getch(); return; } mode=1; for(j=0;j<no;j++) { stry(s.name,s1[j].name); stry(s.usn,s1[j].usn); stry(s.branch,s1[j].branch); pack(); mode=0; } cout<<"record modified\n"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 23
} void main() { int choice; for(;;) { clrscr(); cout<<"\n0:exit"; cout<<"\n1:write"; cout<<"\n2:display"; cout<<"\n3:modify"; cout<<"\n4:search"; cout<<"enter u choice\n"; cin>>choice; switch(choice) { case 1:write(); break; case 2:display(); break; case 3:modify(); break; case 4:search(); break; case 0:exit(0); default:cout<<"\ninvalid input"; break; } }
}
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 24
Output: 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Karthik Enter the student USN 1bg09is015 Enter the student branch Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Dhanvi Enter the student USN 1bg09is007 Enter the student branch Ise 0: Exit 1: write BNMIT/ISE/2012/VI/ File Structure laboratory
Page 25
2: Display 3: Modify 4: Search Enter your choice 2 Name
USN
Karthik1bg09is015 Dhanvi
Branch Ise
1bg09is007
Ise
0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 3 Enter the USN to Modify 1bg09is007 Record found The old values of the record with usn 1bg09is007 are USN=1bg09is007 Name=Dhanvi Branch=ise Enter new values Name=dhruva USN=1bg09is023 Branch=ise Record modified 0: Exit 1: write BNMIT/ISE/2012/VI/ File Structure laboratory
Page 26
2: Display 3: Modify 4: Search Enter your choice 4 Enter the usn to search 1bg09is023 Record found Dhruva 1bg09is023 Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 0 Output from file karthik|1bg09is015|ise dhruva|1bg09is023|ise
Program 4 Write a c++ program to write student objects with variable-length records using any sitable record structure and to read from this file a student record using RRN. #include<stdio.h> #include
#include
#include<stdlib.h>
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 27
#include
#include<string.h> class student { public:char name[25],usn[15],branch[15],buffer[45]; }; student s,s1[100]; char extra[45]; int i,no=0,mode=0; void pack() { fstream app; if(mode==0) app.open("st3.txt",ios::app); else app.open("st3.txt",ios::out); if(!app) { cout<<"cant open the file in output mode"; getch(); exit(0); } stry(s.buffer,s.name); strcat(s.buffer,"|"); strcat(s.buffer,s.usn); strcat(s.buffer,"|"); strcat(s.buffer,s.branch); //int count=strlen(s.buffer); //for(int k=0;k<45-count;k++) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 28
//strcat(s.buffer,"|"); strcat(s.buffer,"\n"); app<<s.buffer; app.close(); } void unpack() { fstream in; in.open("st3.txt",ios::in); i=0,no=0; if(!in) { cout<<"cant open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(s1[i].name,15,'|'); in.getline(s1[i].usn,15,'|'); in.getline(s1[i].branch,15,'\n'); //in.getline(extra,45,'\n'); no++; i++; } in.close(); } void write() { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 29
cout<<"\n enter the student name\n"; cin>>s.name; cout<<"enter the student usn\n"; cin>>s.usn; cout<<"enter the student branch\n"; cin>>s.branch; pack(); mode=0; } void search() { char usn[15],extra[45]; int rrn; cout<<"enter the rrn to search="; cin>>rrn; unpack(); for(int i=0;i<no-1;i++) { if(rrn==i+1) { cout<<"\nrecord found"; cout<<"\n"<<s1[i].name<<"\t"<<s1[i].usn<<"\t"<<s1[i].branch; getch(); return; } } cout<<"record not found"; getch(); return; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 30
} void main() { int choice; for(;;) { clrscr(); cout<<"\n0:exit"; cout<<"\n1:write"; cout<<"\n2:search"; cout<<"enter u choice\n"; cin>>choice; switch(choice) { case 1:write(); break; case 2:search(); break; case 0:exit(0); default:cout<<"\ninvalid input"; break; } } } Output: 0: Exit 1: write 2: Search Enter your choice BNMIT/ISE/2012/VI/ File Structure laboratory
Page 31
1 Enter the student name Satish Enter the student USN 1bg09is055 Enter the student branch Ise 0: Exit 1: write 2: Search Enter your choice 1 Enter the student name divya Enter the student USN 1bg09is408 Enter the student branch Ise 0: Exit 1: write 2: Search Enter your choice 2 Enter the RRN to search=1 Satish
1bg09is055
Ise
Enter the RRN to search=2 divya
1bg09is408
Ise
Enter your choice 0 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 32
Program 5 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<stdio.h> #include
#include<string.h> #include
#include<process.h> #include
#include
#include<stdlib.h> class record { public:char name[20],usn[20],branch[20],ind[5]; }rec[20]; char st_no[5]; int no; void pack() { fstream fle1,fle2; fle1.open("i.txt",ios::out); fle2.open("r.txt",ios::out); if((!fle1)||(!fle2)) { cout<<"cant open either\n"; getch(); exit(0); } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 33
for(int i=0;i<no;i++) { fle1<
<<"|"<< i<<"\n"; fle2<<<"|"<
<<"|"<
<<"|"<
<<"\n";
} fle1.close(); fle2.close(); } void unpack() { fstream fle2; fle2.open("r.txt",ios::in); for(int i=0;i<no;i++) { fle2.getline(rec[i].ind,5,'|'); fle2.getline(rec[i].name,20,'|'); fle2.getline(rec[i].usn,20,'|'); fle2.getline(rec[i].branch,20,'\n'); } fle2.close(); } void search() { char name[20],usn[20],branch[20],ind[5]; unpack(); for(int i=0;i<no;i++) if(strcmp(st_no,rec[i].ind)==0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 34
cout<<"search sucess\n"; cout<<"\nname="<
<<"usn="<
<<"bran="<
Page 35
cout<<"deleted\n"; pack(); return; } } void main() { char st_usn[20],rt_usn[20]; fstream fle1,fle2; char name[20],usn[20],branch[20],ind[5]; int i,flag,ch; clrscr(); for(;;) { cout<<"1:add\n2:search\n3:delete\n4:display\n"; cout<<"enter your choice\n"; cin>>ch; switch(ch) { case 1:cout<<"enter the no of records\n"; cin>>no; cout<<"enter the details of students\n"; for(i=0;i<no;i++) { cout<<"name="; cin>>rec[i].name; cout<<"usn="; cin>>rec[i].usn; cout<<"branch="; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 36
cin>>rec[i].branch; } pack(); break; case 2:cout<<"enter thye usn u want to search\n"; cin>>st_usn; //fstream fle1; fle1.open("i.txt",ios::in); if(!fle1) { cout<<"cant open the file\n"; getch(); exit(0); } flag=0; for(i=0;i<no;i++) { fle1.getline(rt_usn,20,'|'); fle1.getline(st_no,5,'\n'); if(strcmp(rt_usn,st_usn)==0) { search(); flag=1; } } if(!flag) cout<<"not found\n"; fle1.close(); break; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 37
case 3:cout<<"enter thye usn u want to delete\n"; cin>>st_usn; fle1.open("i.txt",ios::in); if(!fle1) { cout<<"cant open the file\n"; getch(); exit(0); } flag=0; for(i=0;i<no;i++) { fle1.getline(rt_usn,20,'|'); fle1.getline(st_no,5,'\n'); if(strcmp(rt_usn,st_usn)==0) { delete_rec(rt_usn); flag=1; } } if(!flag) cout<<"failure\n"; fle1.close(); break; case 4:for(int i=0;i<no;i++) { cout<<"name="<
<<"usn="<
<<" branch="<
<<"\n"; break; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 38
default:exit(0); break; } } } Output: 1: add 2: search 3: delete 4: display Enter your choice 1 Enter the number of records 2 Enter the details of students Name = anu Usn = 1bg09is003 Branch = ise Name= naveen Usn = 1bg09is089 Branch = ise 1: add 2: search 3: delete 4: display Enter your choice 4 Name= anu
usn= 1bg09is003
Name= naveenusn= 1bg09is067
branch=ise branch=ise
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 39
1: add 2: search 3: delete 4: display Enter your choice 2 Enter the usn you want to search 1bg09is067 Search success Name= naveenusn= 1bg09is067
branch=ise
1: add 2: search 3: delete 4: display Enter your choice 2 Enter the usn you want to search 1bg09is006 Not found 1: add 2: search 3: delete 4: display Enter your choice 3 Enter the usn you want to delete 1bg09is067 Deleted 1: add BNMIT/ISE/2012/VI/ File Structure laboratory
Page 40
2: search 3: delete 4: display Enter your choice 4 Name= anu
usn= 1bg09is003
branch=ise
Enter your choice 5. Output from Index file 1bg09is003|0 1bg09is067|1
Output from Record file 0|anu|1bg09is003|ise 1|Naveen|1bg09is067|ise
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 41
Program 6 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
#include<stdio.h> #include
#include<stdlib.h> #include<string.h> class buffer; class student { char age[5]; char usn[20]; char name[20]; char branch[10]; char sem[5]; public: void input(); void output(); friend class buffer; friend class primaryindexing; friend class secondaryindexing; }; class buffer { char b[70]; public: void pack(student &s); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 42
void unpack(student &s); void Read(fstream& fs); int Write(char* filename); buffer(); }; class primaryindexing { char keys[30][2][20]; int size; char *indexfilename; char *recordfilename; public: void retrieveOffset(int i,int &offset); primaryindexing(char *rfilename,char *ifilename,int &offset); ~primaryindexing(); void writeOffset(int &offset); int Insert(student &s,int &offset); void Delete(char * usn); void Search(char *usn); int find(char *usn); }; class secondaryindexing { char keys[30][2][20]; int size; char *indexfilename; char *recordfilename; public: void Insert(student &s); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 43
void Search(char *name,primaryindexing &p); void Delete(char *key); secondaryindexing(char *rfilename,char *ifilename); ~secondaryindexing(); }; secondaryindexing :: secondaryindexing(char *rfilename,char *ifilename) { indexfilename = ifilename; recordfilename = rfilename; fstream indexfile(indexfilename,ios::in); char usn[20],name[20]; size = 0; while(indexfile) { indexfile.getline(name,20,'|'); indexfile.getline(usn,20,'|'); if(indexfile.eof()) break; stry(keys[size][0],name); stry(keys[size][1],usn); size++; } indexfile.close(); } void secondaryindexing :: Insert(student& s) { int i = size-1; while(i>=0 && strcmp(s.name,keys[i][0]) < 0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 44
stry(keys[i+1][0],keys[i][0]); stry(keys[i+1][1],keys[i][1]); i--; } while(i>=0 && strcmp(s.name,keys[i][0]) == 0 && strcmp(s.usn,keys[i][1]) < 0) { stry(keys[i+1][0],keys[i][0]); stry(keys[i+1][1],keys[i][1]); i--; } i++; stry(keys[i][0],s.name); stry(keys[i][1],s.usn); size++; } void secondaryindexing :: Search(char *name,primaryindexing &p) { int offset,pos; student s; buffer b; fstream file(recordfilename,ios::in); int flag = 0; for(int i = 0; i < size; i++) { if(strcmp(name,keys[i][0]) == 0) { pos = p.find(keys[i][1]); if(pos!= -1) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 45
p.retrieveOffset(pos,offset); file.seekg(offset); b.Read(file); b.unpack(s); cout<<"-------------"<<endl; s.output(); cout<<"-------------"<<endl; flag = 1; } } } if(!flag) cout<<" The Record(s) with the given name was not found "<<endl; } void secondaryindexing :: Delete(char *key) { for(int i = 0; i < size; i++) if(strcmp(key,keys[i][1]) == 0) sprintf(keys[i][1],"%d",-1); } secondaryindexing :: ~secondaryindexing() { fstream indexfile(indexfilename,ios::out|ios :: trunc); for(int i = 0; i < size;i++) { indexfile.write(keys[i][0],strlen(keys[i][0])); indexfile<<'|'; indexfile.write(keys[i][1],strlen(keys[i][1])); indexfile<<'|'; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 46
} Indexfile.close(); } int primaryindexing :: find(char *usn) { int first = 0, last = size-1; int mid,temp; while(first <= last) { mid = (first+last)/2; temp = strcmp(keys[mid][0],usn); if(temp == 0) return mid; else if(temp > 0) last = mid-1; else first = mid+1; } return -1; } int primaryindexing :: Insert(student &s,int &offset) { int pos = find(s.usn); if( pos != -1) { cout<<" The Record With the Given Key Already Exists "<<endl; return 0; } buffer b; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 47
b.pack(s); int add = b.Write(recordfilename); int i = size-1; while(i >= 0 && strcmp(s.usn,keys[i][0]) < 0) { stry(keys[i+1][0],keys[i][0]); stry(keys[i+1][1],keys[i][1]); i--; } i++; char offstr[20]; sprintf(offstr,"%d",offset); stry(keys[i][0],s.usn); stry(keys[i][1],offstr); size++; offset = offset + add; return 1; } void primaryindexing :: Delete(char *usn) { int i = find(usn); if(i == -1) { cout<<"No Such Record Exists "<<endl; return; } if( i == size-1) { cout<<"Record With the Given usn Was successfully deleted!!!"<<endl; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 48
size--; return; } for(; i < size; i++) { stry(keys[i][0],keys[i+1][0]); stry(keys[i][1],keys[i+1][1]); } size--; cout<<"Record With the Given usn Was successfully deleted!!!"<<endl; } void primaryindexing :: Search(char *usn) { int i = find(usn); if(i == -1) { cout<<"No Such Record Exists "<<endl; return; } fstream fs(recordfilename,ios::in|ios::out); int offset; student s; retrieveOffset(i,offset); fs.seekg(offset); buffer b; b.Read(fs); b.unpack(s); s.output(); fs.close(); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 49
} primaryindexing :: primaryindexing(char *rfilename,char* ifilename,int &offset) { indexfilename = ifilename; recordfilename = rfilename; fstream indexfile(indexfilename,ios::in); char usn[20],offstr[20]; size = 0; if(!indexfile) { offset = 0; return; } indexfile.read((char*)&offset,sizeof(offset)); while(indexfile) { indexfile.getline(usn,20,'|'); indexfile.getline(offstr,20,'|'); if(indexfile.eof()) break; stry(keys[size][0],usn); stry(keys[size][1],offstr); cout<<usn<<" "<
<<endl; size++; } indexfile.close(); } void primaryindexing :: retrieveOffset(int i,int& offset) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 50
char offstr[20]; stry(offstr,keys[i][1]); offset = atoi(offstr); } void primaryindexing :: writeOffset(int &offset) { fstream indexfile(indexfilename,ios::out|ios :: trunc); indexfile.write((char*)&offset,sizeof(offset)); indexfile.close(); } primaryindexing :: ~primaryindexing() { fstream indexfile(indexfilename,ios::out|ios :: app); for(int i = 0; i < size;i++) { indexfile.write(keys[i][0],strlen(keys[i][0])); indexfile<<'|'; indexfile.write(keys[i][1],strlen(keys[i][1])); indexfile<<'|'; } indexfile.close(); } void student :: input() { cout<<"Enter The Usn"<<endl; cin>>usn; cout<<"Enter The Name"<<endl; cin>>name; cout<<"Enter The Branch"<<endl; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 51
cin>>branch; cout<<"Enter The Semester"<<endl; cin>>sem; } void student :: output() { cout<<"Usn:"; puts(usn); cout<<"Name:"; puts(name); cout<<"Branch:"; puts(branch); cout<<"Semester:"; puts(sem); } buffer :: buffer() { for(int i = 0; i < 70; i++) b[i] = '\0'; } void buffer :: pack(student &s) { stry(b,s.usn); strcat(b,"|"); strcat(b,s.name); strcat(b,"|"); strcat(b,s.branch); strcat(b,"|"); strcat(b,s.sem); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 52
strcat(b,"|"); } void buffer :: unpack(student &s) { char *p = b; while(*p) { if(*p == '|') *p = '\0'; p++; } p = b; stry(s.usn,p); p = p +strlen(p)+1; stry(s.name,p); p = p +strlen(p)+1; stry(s.branch,p); p = p +strlen(p)+1; stry(s.sem,p); } int buffer :: Write(char *filename) { fstream datafile(filename,ios::out|ios::app); datafile.write(b,sizeof(b)); datafile.close(); return sizeof(b); } void buffer :: Read(fstream& fs) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 53
fs.read(b,sizeof(b)); } int main() { int choice =1,flag; int offset; student s; char recordfilename[] = "record.txt"; char pindexfilename[] = "pindex.txt"; char sindexfilename[] = "sindex.txt"; char key[20]; primaryindexing iobj(recordfilename,pindexfilename,offset); secondaryindexing sobj(recordfilename,sindexfilename); while(choice < 4) { cout<<"1.Add Record"<<endl; cout<<"2.Delete Record"<<endl; cout<<"3.Search Record"<<endl; cout<<"4.Exit"<<endl; cin>> choice; switch(choice) { case 1: s.input(); flag = iobj.Insert(s,offset); if(flag) sobj.Insert(s); break; case 2: cout<<"Enter The Usn Of Record to be deleted"<<endl; cin>>key; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 54
iobj.Delete(key); sobj.Delete(key); break; case 3: cout<<"Enter The Name Of Record(s) to be Searched"<<endl; cin>>key; sobj.Search(key,iobj); break;
} } iobj.writeOffset(offset); return 0; }
Output: 1: add record 2: delete record 3:search record 4:exit 1 Enter the USN 1bg09is002 Enter the name Akshata Enter the branch Ise Enter the semester BNMIT/ISE/2012/VI/ File Structure laboratory
Page 55
6 1: add record 2: delete record 3:search record 4:exit 1 Enter the USN 1bg09is087 Enter the name sandeep Enter the branch Ise Enter the semester 6 1: add record 2: delete record 3:search record 4:exit 3 Enter the name of record to be searched Sandeep ---------------------------------USN: 1bg09is087 Name: sandeep Branch:ise Sem:6 ----------------------------------1: add record 2: delete record BNMIT/ISE/2012/VI/ File Structure laboratory
Page 56
3:search record 4:exit 3 Enter the name of record to be searched Anitha Record with the given name was not found 1: add record 2: delete record 3:search record 4:exit 2 Enter your usn of record to be deleted 1bg09is087 Record with given usn was successfully deleted 1: add record 2: delete record 3:search record 4:exit 3 Enter the name of record to be searched Sandeep Record with given name was not found 1: add record 2: delete record 3:search record 4:exit 4 Output from files before deletion Record.txt BNMIT/ISE/2012/VI/ File Structure laboratory
Page 57
1bg09is002|akshata|ise|6 1bg09is087|sandeep|ise|6 Pindex.txt 1bg09is002|0|1bg09is087|70 Sindex.txt Akshata|1bg09is002|sandeep|1bg09is087 Output from files after deletion Record.txt 1bg09is002|akshata|ise|6 Pindex.txt 1bg09is002|0 Sindex.txt Akshata|1bg09is002
Program 7 Write a C++ program to read two lists of names and then match the names in the two lists using Cosequential Match based on a single loop. #include
#include<stdio.h> #include
#include<stdlib.h> #include<string.h> #include<process.h> #include
class coseq { char list1[100][20],list2[100][20]; int n1,n2; public: void load(); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 58
void seq_sort(); void match(); }; fstream f1,f2,of; void coseq :: load() { n1=n2=-1; while(!f1.eof()) f1.getline(list1[++n1],20,'\n'); while(!f2.eof()) f2.getline(list2[++n2],20,'\n'); } void coseq :: seq_sort() { char temp[30]; for(int i=0;i
0) { stry(temp,list1[i]); stry(list1[i],list1[j]); stry(list1[j],temp); } } } for(i=0;i
Page 59
for(int j=i+1;j
0) { stry(temp,list2[j]); stry(list2[i],list2[j]); stry(list2[j],temp); } } } } void coseq :: match() { int i=0,j=0; while((i<=n1)&&(j<=n2)) { if(strcmp(list1[i],list2[j])==0) { cout<<list1[i]<<endl; of<<list1[i]<<endl; i++; j++; continue; } else if(strcmp(list1[i],list2[j])>0) j++; else i++; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 60
} void main() { clrscr(); coseq cq; f1.open("file1.txt",ios::in); f2.open("file2.txt",ios::in); if(!f1||!f2) { cout<<"\n ERROR file dont exist"; getch(); exit(1); } cq.load();f1.close();f2.close(); f1.open("file1.txt",ios::in); f2.open("file2.txt",ios::in); of.open("file3.txt",ios::out); cq.seq_sort(); cq.match(); f1.close(); f2.close(); of.close(); getch(); } Output: Sunil Input file “file1.txt” contains list1 sunil jyothi pradeep BNMIT/ISE/2012/VI/ File Structure laboratory
Page 61
Input file “file2.txt” contains list2 suma avinash sunil kruthi Output file “file3.txt” contains matched names sunil
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 62
Progrm 8 Write a C++ program to read k Lists of names and merge them using kway merge algorithm with k = 8. #include<stdio.h> #include
#include
#include<string.h> #include
#include<stdlib.h> fstream file[8]; char fname[8][8]={"1.txt","2.txt","3.txt","4.txt","5.txt","6.txt","7.txt","8.txt"}; int no; class record { public:char name[20],usn[20]; }rec[20]; void merge(char* file1,char* file2,char* filename) { int k=0; record rec[20]; fstream f1,f2; f1.open(file1,ios::in); f2.open(file2,ios::in); while(!f1.eof()) { f1.getline(rec[k].name,20,'|'); f1.getline(rec[k++].usn,20,'\n'); } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 63
while(!f2.eof()) { f2.getline(rec[k].name,20,'|'); f2.getline(rec[k++].usn,20,'\n'); } int t,y; record temp; for(t=0;t
0) { temp=rec[y]; rec[y]=rec[y+1]; rec[y+1]=temp; } fstream temp1; temp1.open(filename,ios::out); for(t=1;t
Page 64
for(i=0;i<8;i+=2) merge(fname[i],fname[i+1],filename[k++]); k=4; for(i=0;i<4;i+=2) merge(filename[i],filename[i+1],filename[k++]); merge(filename[4],filename[5],filename[6]); return; } void main() { char name[20],usn[20],branch[20]; int i; clrscr(); cout<<"enter the no of records\n"; cin>>no; cout<<"enter the details of students"; for(i=0;i<8;i++) file[i].open(fname[i],ios::out); for(i=0;i<no;i++) { cout<<"name:"; cin>>rec[i].name; cout<<"usn:"; cin>>rec[i].usn; file[i%8]<
<<"|"<
<<"\n"; } for(i=0;i<8;i++) file[i].close(); kwaymerge(); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 65
fstream result; result.open("1111.txt",ios::in); cout<<"sorted order\n"; for(i=0;i<no;i++) { result.getline(name,20,'|'); result.getline(usn,20,'\n'); cout<<"\nname="<
<<"\n"<<"usn="<<usn<<"\n"; } getch(); } Output: Enter the no of records
10
Enter the details Name: jyothi Usn: 1 Name: nidhi Usn: 2 Name: ashik Usn: 3 Name: suraj Usn: 4 Name: kruthi Usn: 5 Name: harsha Usn: 6 Name: shruthi Usn: 7 Name: teju Usn: 8 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 66
Name: seema Usn: 9 Name: kavitha Usn: 2 Sorted records are: Name: ashik Usn: 3 Name: harsha Usn: 6 Name: jyothi Usn: 1 Name: kavitha Usn: 2 Name: kruthi Usn: 5 Name: nidhi Usn: 2 Name: seema Usn: 9 Name: shruthi Usn: 7 Name: suraj Usn: 4 Name: teju Usn: 8
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 67
Program 9 Write a C++ program to implement B-Tree for a given set of integers and its operations insert ( ) and search ( ). Display the tree. #include
#include<stdio.h> #include
#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; publicc: BNMIT/ISE/2012/VI/ File Structure laboratory
Page 68
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<
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 69
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 70
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]; for(int i = 0; i < parent->size;i++) if(parent->a[i] == oldkey) { parent->a[i] = newkey; parent->next[i] = child; } } void btree :: insertIntoNode(node *n,int key,node *address) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 71
{ 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; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 72
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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 73
{ 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 "<
<<" Exists in the B-Tree at the level"<
<<endl; } if(!flag) cout<<"The Key Searched for was not found"<<endl; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 74
int main() { btree b; int choice = 1,key; while(choice <=2) { 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; } Output 1.Insert a Key 2.Search a key 3.Exit 1 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 75
Enter The Key to be inserted in B-Tree 5 1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 8 --------------5 8 ---------------1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 4 --------------4 5 8 ---------------1.Insert a Key 2.Search a key 3.Exit 1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 7 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 76
--------------4 5 7 8 ---------------1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 11 --------------5 11 4 5 7 8 11 ---------------1.Insert a Key 2.Search a key 3.Exit 2
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 77
Enter the key to be searched 11 Key found at level 2 1.Insert a Key 2.Search a key 3.Exit 3
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 78
Program 10 Write a C++ program to implement B+ tree for a given set of integers and its operations insert ( ), and search ( ). Display the tree. #include
#include<stdio.h> #include
#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; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 79
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 80
while(ptr) { for(i = 0; i < ptr -> data -> size; i++) cout<
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 81
p->data = newptr; } else { p = new linkleaf; p-> next = ptr; prevptr -> next = p; p->data = newptr; } } void btree :: traverse(node *ptr) { if(ptr == NULL) return; for(int i = 0; i < ptr->size; i++) cout<
a[i]<<" "; cout<<endl; for(int i = 0; i < ptr->size;i++) traverse(ptr->next[i]); } btree :: btree() { root = NULL; head = NULL; }
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 82
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]; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 83
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]; for(int i = 0; i < parent->size;i++) if(parent->a[i] == oldkey) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 84
parent->a[i] = newkey; parent->next[i] = child; } } 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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 85
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); }
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 86
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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 87
{ 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 "<
<<" 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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 88
{ 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; } Output 1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B+Tree 5 1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B+Tree BNMIT/ISE/2012/VI/ File Structure laboratory
Page 89
8 --------------5 8 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B-Tree 4 --------------4 5 8 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B-Tree 7 --------------4 5 7 8 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 90
Enter The Key to be inserted in B-Tree 11 --------------5 11 4 5 7 8 11 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 2 Enter the key to be searched 11 Key found at level 2 1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 3 -----------------------4
5
7
8
11
-----------------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 4 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 91
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 92
Program 11 Write a C++ program to store and retrieve student data from file using hashing. Use any collision resolution technique. #include<stdio.h> #include<stdlib.h> #include<string.h> #include
#include
#include
//Record specification class node { public: char name[15],usn[15]; node *link; }; node *h[29]; //Array of record pointers equal to size of hash keys – 29 void insert() { char name[15], usn[15], buffer[50]; fstream out; out.open("student.txt",ios::app); //opening student.txt in append mode if(!out) { cout<<"\nUnable to open the file in append mode"; getch(); return; } cout<<"\nEnter the name = "; cin>>name; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 93
cout<<"\n Enter the usn = "; cin>>usn; stry(buffer,name); //Packing the record onto the file using ‘|’ as a delimiter strcat(buffer,"|"); strcat(buffer,usn); strcat(buffer,"\n"); // \n delimiter for the record out<
//dynamically allocate space using ‘new’
stry(p->name,name1); stry(p->usn,usn1); p->link=NULL; prev=NULL; curr=h[hash_key]; if(curr==NULL)
//getting the hash pointer location Case: No collision
{ h[hash_key]=p; return; } while(curr!=NULL)
// Case : On collision – Insert at rear end
{ prev=curr; curr=curr->link; } prev->link=p; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 94
} void retrive() { fstream in; char name[15],usn[15]; int j,count; node *curr; in.open("student.txt",ios::in); // open the record file in input mode if(!in) { cout<<"\n Unable to open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(name,15,'|'); //unpacking the record in.getline(usn,15,'\n'); count=0; for(j=0; j<strlen(usn); j++) //Calculate sum of ascii values of USN { count=count+usn[j]; } count=count%29;
//Hash Key = ASCII count% 29
hash_insert(name,usn,count); } cout<<"\n Enter the usn = "; cin>>usn; count=0; for(j=0; j<strlen(usn); j++)
// Calculating Hash Key
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 95
count=count+usn[j]; count=count%29; curr=h[count]; if(curr == NULL) { cout<<"\nRecord not found"; getch(); return; } do { if(strcmp(curr->usn,usn)==0) //When the record is found, retrieve { cout<<"\nRecord found : "<<curr->usn<<" "<<curr->name; getch(); return; } else { curr=curr->link; } }while(curr!=NULL);
//Search till end of list
if(curr==NULL) //End of list reached with no record found { cout<<"\nRecord not found"; getch(); return; } } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 96
void main() { int choice; clrscr(); fstream out; out.open("student.txt",ios::out); if(!out) { cout<<"\nUnable to open the file in out mode"; getch(); exit(0); } for(;;) { cout<<"\n1:insert\n 2: retrive \n3:exit \nEnter the choice \n"; cin>>choice; switch(choice) { case 1: insert(); break; case 2: retrive(); break; case 3: exit(0); default: cout<<"\nInvalid option"; } } } Output: 1: insert BNMIT/ISE/2012/VI/ File Structure laboratory
Page 97
2: retrieve 3: exit Enter your choice 1 Enter name= sanjay Enter usn=1bg09is056 1: insert 2: retrieve 3: exit Enter your choice 1 Enter name= ashish Enter usn=1bg09is006 1: insert 2: retrieve 3: exit Enter your choice 1 Enter name= shreya Enter usn=1bg09is056 1: insert 2: retrieve 3: exit Enter your choice 2 Enter usn= 1bg09is056 Record found 1bg09is056
sanjay
1: insert 2: retrieve BNMIT/ISE/2012/VI/ File Structure laboratory
Page 98
3: exit Enter your choice 3
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 99
Program 12 Write a C++ program to reclaim the free space resulting from the deletion of records using linked lists. #include<stdio.h> #include
#include
#include<string.h> #include<stdlib.h> #include
class node { public:char name[20],usn[20]; node *link; }; node *first=NULL; void writefile() { fstream out; node *p; char buffer[500]; out.open("a1.txt",ios::out); if(!out) { cout<<"cant open the file\n"; getch(); exit(0); } p=first; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 100
while(p!=NULL) { stry(buffer,p->name); strcat(buffer,"|"); strcat(buffer,p->usn); strcat(buffer,"\n"); out<
link; } } void display() { node *p; if(first==NULL) { cout<<"the list is empty\n"; return; //getch(); //exit(0); } p=first; while(p!=NULL) { cout<
name<<" "<
usn<<"->"; p=p->link; } } void insert() { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 101
node *p,*q; char name[20],usn[20]; cout<<"name="; cin>>name; cout<<"usn="; cin>>usn; p=new node; stry(p->name,name); stry(p->usn,usn); p->link=NULL; if(first==NULL) { first=p; writefile(); display(); return; } for(q=first;q->link!=NULL;q=q->link); q->link=p; writefile(); display(); return; } void del1() { char usn[15]; node *prev,*curr,*del; //char usn; //int del; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 102
if(first==NULL) { cout<<"list is empty\n"; return; //getch(); //exit(0); } cout<<"enter the usn u want to delete\n"; cin>>usn; if(strcmp(first->usn,usn)==0) { del=first; delete del; first=first->link; writefile(); display(); return; } prev=NULL; curr=first; while((strcmp(curr->usn,usn)!=0)&&(curr!=NULL)) { prev=curr; curr=curr->link; } if(curr==NULL) { cout<<"the rec with the usn "<<usn<<"did not find"; getch(); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 103
exit(0); } prev->link=curr->link; writefile(); display(); } void main() { int ch; clrscr(); for(;;) { cout<<"1:insert\n2:delete\n3:quit"; cout<<"enter your choice\n"; cin>>ch; switch(ch) { case 1:insert(); break; case 2:del1(); break; case 3:exit(0); break; default:"invalid choice\n"; break; } } } Output: BNMIT/ISE/2012/VI/ File Structure laboratory
Page 104
1: insert 2. delete 3. exit Enter your choice 1 Name=menatha Usn=1bg09is048 Menatha 1bg09is048 1: insert 2. delete 3. exit Enter your choice 1 Name=subash Usn=1bg09is067 Menatha 1bg09is048 subash 1bg09is067 1: insert 2. delete 3. exit Enter your choice 1 Name=ayush Usn=1bg09is005 Menatha 1bg09is048 subash 1bg09is067 ayush 1bg09is005 1: insert 2. delete 3. exit Enter your choice 2 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 105
Enter the usn you want to delete 1bg09is048 subash 1bg09is067 ayush 1bg09is005 1: insert 2. delete 3. exit Enter your choice 1 Name=Samarth Usn=1bg09is063 subash 1bg09is067 ayush 1bg09is005 Samarth 1bg09is063 1: insert 2. delete 3. exit Enter your choice 3
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 106
FILE STRUCTURE LABORATORY MANUAL SUBCODE: 06ISL67, VI SEMESTER B.E
Vidyaya Amrutham Ashnuthe
BNM Institute of Technology (Approved by AICTE & d to VTU, Karnataka) (An ISO 9001:2008 Certified Institution) Post Box No, 7087, 27th cross, 12th Main Road, Banshankari 2nd Stage, Bengalore-560070 Phone: 91-8026711781/26711782 Fax: 91-80-26710881,E-mail:[email protected] Visit us at: www.bnmit.org
VTU LAB SYLLABUS FILE STRUCTURE LABORATORY Subject Code No. of Practical
: 06ISL67 : 03
IA Marks : 25 Exam Hours : 03
Hours/Week Total No. of Practical
: 42
Exam Marks : 50
Hours
1. Write a C++ program to read series of names, one per line, from standard input and write these names spelled in reverse order to the standard output using I/O redirection and pipes. Repeat the exercise using an input file specified by the instead of the standard input and using an output file specified by the instead of the standard output. 2. Write a C++ program to read and write student objects with fixed-length records and the fields delimited by “|”. Implement pack ( ), unpack ( ), modify ( ) and search ( ) methods. 3. Write a C++ program to read and write student objects with Variable - Length records using any suitable record structure. Implement pack ( ), unpack ( ), modify ( ) and search ( ) methods. 4. 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. 5. Write a C++ program to implement simple index on primary key for a file of student objects. Implement add ( ), search ( ), delete ( ) using the index. 6. 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.
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 2
7. Write a C++ program to read two lists of names and then match the names in the two lists using Cosequential Match based on a single loop. Output the names common to both the lists. 8. Write a C++ program to read k Lists of names and merge them using k-way merge algorithm with k = 8. 9. Write a C++ program to implement B-Tree for a given set of integers and its operations insert ( ) and search ( ). Display the tree. 10. Write a C++ program to implement B+ tree for a given set of integers and its operations insert ( ), and search ( ). Display the tree. 11. Write a C++ program to store and retrieve student data from file using hashing. Use any collision resolution technique. 12. Write a C++ program to reclaim the free space resulting from the deletion of records using linked lists.
Contents VTU LAB SYLLABUS......................................................................................2 Contents...................................................................................................... 3 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 3
Program 1.................................................................................................... 5 Program 2.................................................................................................... 9 Program 3.................................................................................................. 19 Program 4.................................................................................................. 27 Program 5.................................................................................................. 33 Program 6.................................................................................................. 42 Program 7.................................................................................................. 58 Progrm 8.................................................................................................... 63 Program 9.................................................................................................. 68 Program 10................................................................................................79 Program 11................................................................................................93 Program 12..............................................................................................100
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 4
Program 1 Write a C++ program to read series of names, one per line, from standard input and write these names spelled in reverse order to the standard output using I/O redirection and pipes. Repeat the exercise using an input file specified by the instead of the standard input and using an output file specified by the instead of the standard output. #include
Page 5
} void main() { names n[10]; clrscr(); ofstream out; out.open("file.txt",ios::out|ios::app|ios::trunc); int m; cout<<"enter the no. of names to be entered\n"; cin>>m; for(int i=0;i<m;i++) { cout<<"enter name"; cin>>n[i].name; cout<<"the name in reverse order"; reverse(out,n[i].name); } out.close(); ifstream in; in.open("file.txt",ios::in|ios::binary); ofstream outf; outf.open("f1.txt",ios::out|ios::app|ios::trunc); char ch[255]; cout<<"names from files\n"; while(in) { in.getline(ch,255); if(in) reverse(outf,ch); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 6
} cout<<endl; in.close(); outf.close(); in.open("f1.txt",ios::in|ios::binary); outf.open("f2.txt",ios::out|ios::app|ios::trunc); cout<<"reverse order from files\n"; while(in) { in.getline(ch,255); if(in) reverse(outf,ch); } in.close(); outf.close(); getch(); } Output: Enter the no. of names to be entered 5 Enter name priya The name in reverse order ayirp Enter name pa The name in reverse order amdap Enter name BNMIT/ISE/2012/VI/ File Structure laboratory
Page 7
ajit The name in reverse order tija
Enter name sohan The name in reverse order nahos Enter name dilip The name in reverse order pilid The names from files (f1.txt) priya pa ajit soni dilip Reverse order from files (f2.txt) ayirp amdap tija nahos pilid
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 8
Program 2 Write a C++ program to read and write and student objects with fixed length records and the fields delimited by “|”.implement pack(),unpack(),modify() and search() methods.
#include<stdio.h> #include
Page 9
getch(); exit(0); } stry(s.buffer,s.name); strcat(s.buffer,"|"); strcat(s.buffer,s.usn); strcat(s.buffer,"|"); strcat(s.buffer,s.branch); int count=strlen(s.buffer); for(int k=0;k<45-count;k++) strcat(s.buffer,"|"); strcat(s.buffer,"\n"); app<<s.buffer; app.close(); } void unpack() { fstream in; in.open("st1.txt",ios::in); i=0,no=0; if(!in) { cout<<"cant open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(s1[i].name,15,'|'); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 10
in.getline(s1[i].usn,15,'|'); in.getline(s1[i].branch,15,'|'); in.getline(extra,45,'\n'); no++; i++; } in.close(); } void write() { cout<<"\n enter the student name\n"; cin>>s.name; cout<<"enter the student usn\n"; cin>>s.usn; cout<<"enter the student branch\n"; cin>>s.branch; pack(); mode=0; } void search() { char usn[15],extra[45]; cout<<"enter the usn to search="; cin>>usn; unpack(); for(i=0;i<no;i++) { if(strcmp(s1[i].usn,usn)==0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 11
cout<<"\nrecord found"; cout<<"\n"<<s1[i].name<<"\t"<<s1[i].usn<<"\t"<<s1[i].branch; getch(); return; } } cout<<"record not found"; getch(); return; } void display() { cout<<"name\t\t usn\t\t branch\n\n"; unpack(); for(int i=0;i<no;i++) cout<<"\n\n"<<s1[i].name<<"\t\t"<<s1[i].usn<<"\t\t"<<s1[i].branch; getch(); } void modify() { char usn[15],buffer[15],extra[45]; cout<<"enter the usn to search\n"; cin>>usn; unpack();no--; for(int j=0;j<no;j++) { if(strcmp(usn,s1[j].usn)==0) { cout<<"the old values of the record are with BNMIT/ISE/2012/VI/ File Structure laboratory
Page 12
usn"<<usn<<"are"; cout<<"\nname="<<s1[j].name; cout<<"\nusn="<<s1[j].usn; cout<<"\nbranch="<<s1[j].branch; cout<<"enter the new values\n"; cout<<"\nname="; cin>>s1[j].name; cout<<"\nusn="; cin>>s1[j].usn; cout<<"\nbranch="; cin>>s1[j].branch; break; } } if(j==no) { cout<<"the record with usn is not present"; getch(); return; } mode=1; for(j=0;j<no;j++) { stry(s.name,s1[j].name); stry(s.usn,s1[j].usn); stry(s.branch,s1[j].branch); pack(); mode=0; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 13
cout<<"record modified\n"; } void main() { clrscr(); int choice; for(;;) { //clrscr(); cout<<"\n0:exit"; cout<<"\n1:write"; cout<<"\n2:display"; cout<<"\n3:modify"; cout<<"\n4:search"; cout<<"enter u choice\n"; cin>>choice; switch(choice) { case 1:write(); break; case 2:display(); break; case 3:modify(); break; case 4:search(); break; case 0:exit(0); default:cout<<"\ninvalid input"; break; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 14
} } }
Output: 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Karthik Enter the student USN 1bg09is015 Enter the student branch Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Dhanvi Enter the student USN 1bg09is007 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 15
Enter the student branch Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 2 Name
USN
Karthik1bg09is015 Dhanvi
Branch Ise
1bg09is007
Ise
0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 3 Enter the USN to Modify 1bg09is007 Record found The old values of the record with usn 1bg09is007 are USN=1bg09is007 Name=Dhanvi Branch=ise Enter new values Name=dhruva USN=1bg09is023 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 16
Branch=ise Record modified 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 4 Enter the usn to search 1bg09is023 Record found Dhruva 1bg09is023 Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 0 Output from text file karthik|1bg09is015|ise||||||||||||||||||||||| dhruva|1bg09is023|ise||||||||||||||||||||||||
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 17
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 18
Program 3 Write a C++ program to read and write and student objects with variable length records using any suitable record structure. Implement pack(),unpack(),modify() and search() methods. #include<stdio.h> #include
Page 19
getch(); exit(0); } stry(s.buffer,s.name); strcat(s.buffer,"|"); strcat(s.buffer,s.usn); strcat(s.buffer,"|"); strcat(s.buffer,s.branch); //int count=strlen(s.buffer); //for(int k=0;k<45-count;k++) //strcat(s.buffer,"|"); strcat(s.buffer,"\n"); app<<s.buffer; app.close(); } void unpack() { fstream in; in.open("st2.txt",ios::in); i=0,no=0; if(!in) { cout<<"cant open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(s1[i].name,15,'|'); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 20
in.getline(s1[i].usn,15,'|'); in.getline(s1[i].branch,15,'\n'); //in.getline(extra,45,'\n'); no++; i++; } in.close(); } void write() { cout<<"\n enter the student name\n"; cin>>s.name; cout<<"enter the student usn\n"; cin>>s.usn; cout<<"enter the student branch\n"; cin>>s.branch; pack(); mode=0; } void search() { char usn[15],extra[45]; cout<<"enter the usn to search="; cin>>usn; unpack(); for(i=0;i<no;i++) { if(strcmp(s1[i].usn,usn)==0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 21
cout<<"\nrecord found"; cout<<"\n"<<s1[i].name<<"\t"<<s1[i].usn<<"\t"<<s1[i].branch; getch(); return; } } cout<<"record not found"; getch(); return; } void display() { cout<<"name\t\t usn\t\t branch\n\n"; unpack(); for(int i=0;i<no;i++) cout<<"\n\n"<<s1[i].name<<"\t\t"<<s1[i].usn<<"\t\t"<<s1[i].branch; getch(); } void modify() { char usn[15],buffer[15],extra[45]; cout<<"enter the usn to search\n"; cin>>usn; unpack();no--; for(int j=0;j<no;j++) { if(strcmp(usn,s1[j].usn)==0) { cout<<"the old values of the record are with usn" <<usn << " are"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 22
cout<<"\nname="<<s1[j].name; cout<<"\nusn="<<s1[j].usn; cout<<"\nbranch="<<s1[j].branch; cout<<"enter the new values\n"; cout<<"\nname="; cin>>s1[j].name; cout<<"\nusn="; cin>>s1[j].usn; cout<<"\nbranch="; cin>>s1[j].branch; break; } } if(j==no) { cout<<"the record with usn is not present"; getch(); return; } mode=1; for(j=0;j<no;j++) { stry(s.name,s1[j].name); stry(s.usn,s1[j].usn); stry(s.branch,s1[j].branch); pack(); mode=0; } cout<<"record modified\n"; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 23
} void main() { int choice; for(;;) { clrscr(); cout<<"\n0:exit"; cout<<"\n1:write"; cout<<"\n2:display"; cout<<"\n3:modify"; cout<<"\n4:search"; cout<<"enter u choice\n"; cin>>choice; switch(choice) { case 1:write(); break; case 2:display(); break; case 3:modify(); break; case 4:search(); break; case 0:exit(0); default:cout<<"\ninvalid input"; break; } }
}
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 24
Output: 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Karthik Enter the student USN 1bg09is015 Enter the student branch Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 1 Enter the student name Dhanvi Enter the student USN 1bg09is007 Enter the student branch Ise 0: Exit 1: write BNMIT/ISE/2012/VI/ File Structure laboratory
Page 25
2: Display 3: Modify 4: Search Enter your choice 2 Name
USN
Karthik1bg09is015 Dhanvi
Branch Ise
1bg09is007
Ise
0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 3 Enter the USN to Modify 1bg09is007 Record found The old values of the record with usn 1bg09is007 are USN=1bg09is007 Name=Dhanvi Branch=ise Enter new values Name=dhruva USN=1bg09is023 Branch=ise Record modified 0: Exit 1: write BNMIT/ISE/2012/VI/ File Structure laboratory
Page 26
2: Display 3: Modify 4: Search Enter your choice 4 Enter the usn to search 1bg09is023 Record found Dhruva 1bg09is023 Ise 0: Exit 1: write 2: Display 3: Modify 4: Search Enter your choice 0 Output from file karthik|1bg09is015|ise dhruva|1bg09is023|ise
Program 4 Write a c++ program to write student objects with variable-length records using any sitable record structure and to read from this file a student record using RRN. #include<stdio.h> #include
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 27
#include
Page 28
//strcat(s.buffer,"|"); strcat(s.buffer,"\n"); app<<s.buffer; app.close(); } void unpack() { fstream in; in.open("st3.txt",ios::in); i=0,no=0; if(!in) { cout<<"cant open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(s1[i].name,15,'|'); in.getline(s1[i].usn,15,'|'); in.getline(s1[i].branch,15,'\n'); //in.getline(extra,45,'\n'); no++; i++; } in.close(); } void write() { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 29
cout<<"\n enter the student name\n"; cin>>s.name; cout<<"enter the student usn\n"; cin>>s.usn; cout<<"enter the student branch\n"; cin>>s.branch; pack(); mode=0; } void search() { char usn[15],extra[45]; int rrn; cout<<"enter the rrn to search="; cin>>rrn; unpack(); for(int i=0;i<no-1;i++) { if(rrn==i+1) { cout<<"\nrecord found"; cout<<"\n"<<s1[i].name<<"\t"<<s1[i].usn<<"\t"<<s1[i].branch; getch(); return; } } cout<<"record not found"; getch(); return; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 30
} void main() { int choice; for(;;) { clrscr(); cout<<"\n0:exit"; cout<<"\n1:write"; cout<<"\n2:search"; cout<<"enter u choice\n"; cin>>choice; switch(choice) { case 1:write(); break; case 2:search(); break; case 0:exit(0); default:cout<<"\ninvalid input"; break; } } } Output: 0: Exit 1: write 2: Search Enter your choice BNMIT/ISE/2012/VI/ File Structure laboratory
Page 31
1 Enter the student name Satish Enter the student USN 1bg09is055 Enter the student branch Ise 0: Exit 1: write 2: Search Enter your choice 1 Enter the student name divya Enter the student USN 1bg09is408 Enter the student branch Ise 0: Exit 1: write 2: Search Enter your choice 2 Enter the RRN to search=1 Satish
1bg09is055
Ise
Enter the RRN to search=2 divya
1bg09is408
Ise
Enter your choice 0 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 32
Program 5 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<stdio.h> #include
Page 33
for(int i=0;i<no;i++) { fle1<
} fle1.close(); fle2.close(); } void unpack() { fstream fle2; fle2.open("r.txt",ios::in); for(int i=0;i<no;i++) { fle2.getline(rec[i].ind,5,'|'); fle2.getline(rec[i].name,20,'|'); fle2.getline(rec[i].usn,20,'|'); fle2.getline(rec[i].branch,20,'\n'); } fle2.close(); } void search() { char name[20],usn[20],branch[20],ind[5]; unpack(); for(int i=0;i<no;i++) if(strcmp(st_no,rec[i].ind)==0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 34
cout<<"search sucess\n"; cout<<"\nname="<
Page 35
cout<<"deleted\n"; pack(); return; } } void main() { char st_usn[20],rt_usn[20]; fstream fle1,fle2; char name[20],usn[20],branch[20],ind[5]; int i,flag,ch; clrscr(); for(;;) { cout<<"1:add\n2:search\n3:delete\n4:display\n"; cout<<"enter your choice\n"; cin>>ch; switch(ch) { case 1:cout<<"enter the no of records\n"; cin>>no; cout<<"enter the details of students\n"; for(i=0;i<no;i++) { cout<<"name="; cin>>rec[i].name; cout<<"usn="; cin>>rec[i].usn; cout<<"branch="; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 36
cin>>rec[i].branch; } pack(); break; case 2:cout<<"enter thye usn u want to search\n"; cin>>st_usn; //fstream fle1; fle1.open("i.txt",ios::in); if(!fle1) { cout<<"cant open the file\n"; getch(); exit(0); } flag=0; for(i=0;i<no;i++) { fle1.getline(rt_usn,20,'|'); fle1.getline(st_no,5,'\n'); if(strcmp(rt_usn,st_usn)==0) { search(); flag=1; } } if(!flag) cout<<"not found\n"; fle1.close(); break; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 37
case 3:cout<<"enter thye usn u want to delete\n"; cin>>st_usn; fle1.open("i.txt",ios::in); if(!fle1) { cout<<"cant open the file\n"; getch(); exit(0); } flag=0; for(i=0;i<no;i++) { fle1.getline(rt_usn,20,'|'); fle1.getline(st_no,5,'\n'); if(strcmp(rt_usn,st_usn)==0) { delete_rec(rt_usn); flag=1; } } if(!flag) cout<<"failure\n"; fle1.close(); break; case 4:for(int i=0;i<no;i++) { cout<<"name="<
Page 38
default:exit(0); break; } } } Output: 1: add 2: search 3: delete 4: display Enter your choice 1 Enter the number of records 2 Enter the details of students Name = anu Usn = 1bg09is003 Branch = ise Name= naveen Usn = 1bg09is089 Branch = ise 1: add 2: search 3: delete 4: display Enter your choice 4 Name= anu
usn= 1bg09is003
Name= naveenusn= 1bg09is067
branch=ise branch=ise
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 39
1: add 2: search 3: delete 4: display Enter your choice 2 Enter the usn you want to search 1bg09is067 Search success Name= naveenusn= 1bg09is067
branch=ise
1: add 2: search 3: delete 4: display Enter your choice 2 Enter the usn you want to search 1bg09is006 Not found 1: add 2: search 3: delete 4: display Enter your choice 3 Enter the usn you want to delete 1bg09is067 Deleted 1: add BNMIT/ISE/2012/VI/ File Structure laboratory
Page 40
2: search 3: delete 4: display Enter your choice 4 Name= anu
usn= 1bg09is003
branch=ise
Enter your choice 5. Output from Index file 1bg09is003|0 1bg09is067|1
Output from Record file 0|anu|1bg09is003|ise 1|Naveen|1bg09is067|ise
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 41
Program 6 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
Page 42
void unpack(student &s); void Read(fstream& fs); int Write(char* filename); buffer(); }; class primaryindexing { char keys[30][2][20]; int size; char *indexfilename; char *recordfilename; public: void retrieveOffset(int i,int &offset); primaryindexing(char *rfilename,char *ifilename,int &offset); ~primaryindexing(); void writeOffset(int &offset); int Insert(student &s,int &offset); void Delete(char * usn); void Search(char *usn); int find(char *usn); }; class secondaryindexing { char keys[30][2][20]; int size; char *indexfilename; char *recordfilename; public: void Insert(student &s); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 43
void Search(char *name,primaryindexing &p); void Delete(char *key); secondaryindexing(char *rfilename,char *ifilename); ~secondaryindexing(); }; secondaryindexing :: secondaryindexing(char *rfilename,char *ifilename) { indexfilename = ifilename; recordfilename = rfilename; fstream indexfile(indexfilename,ios::in); char usn[20],name[20]; size = 0; while(indexfile) { indexfile.getline(name,20,'|'); indexfile.getline(usn,20,'|'); if(indexfile.eof()) break; stry(keys[size][0],name); stry(keys[size][1],usn); size++; } indexfile.close(); } void secondaryindexing :: Insert(student& s) { int i = size-1; while(i>=0 && strcmp(s.name,keys[i][0]) < 0) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 44
stry(keys[i+1][0],keys[i][0]); stry(keys[i+1][1],keys[i][1]); i--; } while(i>=0 && strcmp(s.name,keys[i][0]) == 0 && strcmp(s.usn,keys[i][1]) < 0) { stry(keys[i+1][0],keys[i][0]); stry(keys[i+1][1],keys[i][1]); i--; } i++; stry(keys[i][0],s.name); stry(keys[i][1],s.usn); size++; } void secondaryindexing :: Search(char *name,primaryindexing &p) { int offset,pos; student s; buffer b; fstream file(recordfilename,ios::in); int flag = 0; for(int i = 0; i < size; i++) { if(strcmp(name,keys[i][0]) == 0) { pos = p.find(keys[i][1]); if(pos!= -1) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 45
p.retrieveOffset(pos,offset); file.seekg(offset); b.Read(file); b.unpack(s); cout<<"-------------"<<endl; s.output(); cout<<"-------------"<<endl; flag = 1; } } } if(!flag) cout<<" The Record(s) with the given name was not found "<<endl; } void secondaryindexing :: Delete(char *key) { for(int i = 0; i < size; i++) if(strcmp(key,keys[i][1]) == 0) sprintf(keys[i][1],"%d",-1); } secondaryindexing :: ~secondaryindexing() { fstream indexfile(indexfilename,ios::out|ios :: trunc); for(int i = 0; i < size;i++) { indexfile.write(keys[i][0],strlen(keys[i][0])); indexfile<<'|'; indexfile.write(keys[i][1],strlen(keys[i][1])); indexfile<<'|'; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 46
} Indexfile.close(); } int primaryindexing :: find(char *usn) { int first = 0, last = size-1; int mid,temp; while(first <= last) { mid = (first+last)/2; temp = strcmp(keys[mid][0],usn); if(temp == 0) return mid; else if(temp > 0) last = mid-1; else first = mid+1; } return -1; } int primaryindexing :: Insert(student &s,int &offset) { int pos = find(s.usn); if( pos != -1) { cout<<" The Record With the Given Key Already Exists "<<endl; return 0; } buffer b; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 47
b.pack(s); int add = b.Write(recordfilename); int i = size-1; while(i >= 0 && strcmp(s.usn,keys[i][0]) < 0) { stry(keys[i+1][0],keys[i][0]); stry(keys[i+1][1],keys[i][1]); i--; } i++; char offstr[20]; sprintf(offstr,"%d",offset); stry(keys[i][0],s.usn); stry(keys[i][1],offstr); size++; offset = offset + add; return 1; } void primaryindexing :: Delete(char *usn) { int i = find(usn); if(i == -1) { cout<<"No Such Record Exists "<<endl; return; } if( i == size-1) { cout<<"Record With the Given usn Was successfully deleted!!!"<<endl; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 48
size--; return; } for(; i < size; i++) { stry(keys[i][0],keys[i+1][0]); stry(keys[i][1],keys[i+1][1]); } size--; cout<<"Record With the Given usn Was successfully deleted!!!"<<endl; } void primaryindexing :: Search(char *usn) { int i = find(usn); if(i == -1) { cout<<"No Such Record Exists "<<endl; return; } fstream fs(recordfilename,ios::in|ios::out); int offset; student s; retrieveOffset(i,offset); fs.seekg(offset); buffer b; b.Read(fs); b.unpack(s); s.output(); fs.close(); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 49
} primaryindexing :: primaryindexing(char *rfilename,char* ifilename,int &offset) { indexfilename = ifilename; recordfilename = rfilename; fstream indexfile(indexfilename,ios::in); char usn[20],offstr[20]; size = 0; if(!indexfile) { offset = 0; return; } indexfile.read((char*)&offset,sizeof(offset)); while(indexfile) { indexfile.getline(usn,20,'|'); indexfile.getline(offstr,20,'|'); if(indexfile.eof()) break; stry(keys[size][0],usn); stry(keys[size][1],offstr); cout<<usn<<" "<
Page 50
char offstr[20]; stry(offstr,keys[i][1]); offset = atoi(offstr); } void primaryindexing :: writeOffset(int &offset) { fstream indexfile(indexfilename,ios::out|ios :: trunc); indexfile.write((char*)&offset,sizeof(offset)); indexfile.close(); } primaryindexing :: ~primaryindexing() { fstream indexfile(indexfilename,ios::out|ios :: app); for(int i = 0; i < size;i++) { indexfile.write(keys[i][0],strlen(keys[i][0])); indexfile<<'|'; indexfile.write(keys[i][1],strlen(keys[i][1])); indexfile<<'|'; } indexfile.close(); } void student :: input() { cout<<"Enter The Usn"<<endl; cin>>usn; cout<<"Enter The Name"<<endl; cin>>name; cout<<"Enter The Branch"<<endl; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 51
cin>>branch; cout<<"Enter The Semester"<<endl; cin>>sem; } void student :: output() { cout<<"Usn:"; puts(usn); cout<<"Name:"; puts(name); cout<<"Branch:"; puts(branch); cout<<"Semester:"; puts(sem); } buffer :: buffer() { for(int i = 0; i < 70; i++) b[i] = '\0'; } void buffer :: pack(student &s) { stry(b,s.usn); strcat(b,"|"); strcat(b,s.name); strcat(b,"|"); strcat(b,s.branch); strcat(b,"|"); strcat(b,s.sem); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 52
strcat(b,"|"); } void buffer :: unpack(student &s) { char *p = b; while(*p) { if(*p == '|') *p = '\0'; p++; } p = b; stry(s.usn,p); p = p +strlen(p)+1; stry(s.name,p); p = p +strlen(p)+1; stry(s.branch,p); p = p +strlen(p)+1; stry(s.sem,p); } int buffer :: Write(char *filename) { fstream datafile(filename,ios::out|ios::app); datafile.write(b,sizeof(b)); datafile.close(); return sizeof(b); } void buffer :: Read(fstream& fs) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 53
fs.read(b,sizeof(b)); } int main() { int choice =1,flag; int offset; student s; char recordfilename[] = "record.txt"; char pindexfilename[] = "pindex.txt"; char sindexfilename[] = "sindex.txt"; char key[20]; primaryindexing iobj(recordfilename,pindexfilename,offset); secondaryindexing sobj(recordfilename,sindexfilename); while(choice < 4) { cout<<"1.Add Record"<<endl; cout<<"2.Delete Record"<<endl; cout<<"3.Search Record"<<endl; cout<<"4.Exit"<<endl; cin>> choice; switch(choice) { case 1: s.input(); flag = iobj.Insert(s,offset); if(flag) sobj.Insert(s); break; case 2: cout<<"Enter The Usn Of Record to be deleted"<<endl; cin>>key; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 54
iobj.Delete(key); sobj.Delete(key); break; case 3: cout<<"Enter The Name Of Record(s) to be Searched"<<endl; cin>>key; sobj.Search(key,iobj); break;
} } iobj.writeOffset(offset); return 0; }
Output: 1: add record 2: delete record 3:search record 4:exit 1 Enter the USN 1bg09is002 Enter the name Akshata Enter the branch Ise Enter the semester BNMIT/ISE/2012/VI/ File Structure laboratory
Page 55
6 1: add record 2: delete record 3:search record 4:exit 1 Enter the USN 1bg09is087 Enter the name sandeep Enter the branch Ise Enter the semester 6 1: add record 2: delete record 3:search record 4:exit 3 Enter the name of record to be searched Sandeep ---------------------------------USN: 1bg09is087 Name: sandeep Branch:ise Sem:6 ----------------------------------1: add record 2: delete record BNMIT/ISE/2012/VI/ File Structure laboratory
Page 56
3:search record 4:exit 3 Enter the name of record to be searched Anitha Record with the given name was not found 1: add record 2: delete record 3:search record 4:exit 2 Enter your usn of record to be deleted 1bg09is087 Record with given usn was successfully deleted 1: add record 2: delete record 3:search record 4:exit 3 Enter the name of record to be searched Sandeep Record with given name was not found 1: add record 2: delete record 3:search record 4:exit 4 Output from files before deletion Record.txt BNMIT/ISE/2012/VI/ File Structure laboratory
Page 57
1bg09is002|akshata|ise|6 1bg09is087|sandeep|ise|6 Pindex.txt 1bg09is002|0|1bg09is087|70 Sindex.txt Akshata|1bg09is002|sandeep|1bg09is087 Output from files after deletion Record.txt 1bg09is002|akshata|ise|6 Pindex.txt 1bg09is002|0 Sindex.txt Akshata|1bg09is002
Program 7 Write a C++ program to read two lists of names and then match the names in the two lists using Cosequential Match based on a single loop. #include
Page 58
void seq_sort(); void match(); }; fstream f1,f2,of; void coseq :: load() { n1=n2=-1; while(!f1.eof()) f1.getline(list1[++n1],20,'\n'); while(!f2.eof()) f2.getline(list2[++n2],20,'\n'); } void coseq :: seq_sort() { char temp[30]; for(int i=0;i
Page 59
for(int j=i+1;j
Page 60
} void main() { clrscr(); coseq cq; f1.open("file1.txt",ios::in); f2.open("file2.txt",ios::in); if(!f1||!f2) { cout<<"\n ERROR file dont exist"; getch(); exit(1); } cq.load();f1.close();f2.close(); f1.open("file1.txt",ios::in); f2.open("file2.txt",ios::in); of.open("file3.txt",ios::out); cq.seq_sort(); cq.match(); f1.close(); f2.close(); of.close(); getch(); } Output: Sunil Input file “file1.txt” contains list1 sunil jyothi pradeep BNMIT/ISE/2012/VI/ File Structure laboratory
Page 61
Input file “file2.txt” contains list2 suma avinash sunil kruthi Output file “file3.txt” contains matched names sunil
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 62
Progrm 8 Write a C++ program to read k Lists of names and merge them using kway merge algorithm with k = 8. #include<stdio.h> #include
Page 63
while(!f2.eof()) { f2.getline(rec[k].name,20,'|'); f2.getline(rec[k++].usn,20,'\n'); } int t,y; record temp; for(t=0;t
Page 64
for(i=0;i<8;i+=2) merge(fname[i],fname[i+1],filename[k++]); k=4; for(i=0;i<4;i+=2) merge(filename[i],filename[i+1],filename[k++]); merge(filename[4],filename[5],filename[6]); return; } void main() { char name[20],usn[20],branch[20]; int i; clrscr(); cout<<"enter the no of records\n"; cin>>no; cout<<"enter the details of students"; for(i=0;i<8;i++) file[i].open(fname[i],ios::out); for(i=0;i<no;i++) { cout<<"name:"; cin>>rec[i].name; cout<<"usn:"; cin>>rec[i].usn; file[i%8]<
Page 65
fstream result; result.open("1111.txt",ios::in); cout<<"sorted order\n"; for(i=0;i<no;i++) { result.getline(name,20,'|'); result.getline(usn,20,'\n'); cout<<"\nname="<
10
Enter the details Name: jyothi Usn: 1 Name: nidhi Usn: 2 Name: ashik Usn: 3 Name: suraj Usn: 4 Name: kruthi Usn: 5 Name: harsha Usn: 6 Name: shruthi Usn: 7 Name: teju Usn: 8 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 66
Name: seema Usn: 9 Name: kavitha Usn: 2 Sorted records are: Name: ashik Usn: 3 Name: harsha Usn: 6 Name: jyothi Usn: 1 Name: kavitha Usn: 2 Name: kruthi Usn: 5 Name: nidhi Usn: 2 Name: seema Usn: 9 Name: shruthi Usn: 7 Name: suraj Usn: 4 Name: teju Usn: 8
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 67
Program 9 Write a C++ program to implement B-Tree for a given set of integers and its operations insert ( ) and search ( ). Display the tree. #include
Page 68
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<
Page 69
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 70
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]; for(int i = 0; i < parent->size;i++) if(parent->a[i] == oldkey) { parent->a[i] = newkey; parent->next[i] = child; } } void btree :: insertIntoNode(node *n,int key,node *address) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 71
{ 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; } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 72
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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 73
{ 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 "<
Page 74
int main() { btree b; int choice = 1,key; while(choice <=2) { 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; } Output 1.Insert a Key 2.Search a key 3.Exit 1 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 75
Enter The Key to be inserted in B-Tree 5 1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 8 --------------5 8 ---------------1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 4 --------------4 5 8 ---------------1.Insert a Key 2.Search a key 3.Exit 1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 7 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 76
--------------4 5 7 8 ---------------1.Insert a Key 2.Search a key 3.Exit 1 Enter The Key to be inserted in B-Tree 11 --------------5 11 4 5 7 8 11 ---------------1.Insert a Key 2.Search a key 3.Exit 2
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 77
Enter the key to be searched 11 Key found at level 2 1.Insert a Key 2.Search a key 3.Exit 3
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 78
Program 10 Write a C++ program to implement B+ tree for a given set of integers and its operations insert ( ), and search ( ). Display the tree. #include
Page 79
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 80
while(ptr) { for(i = 0; i < ptr -> data -> size; i++) cout<
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; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 81
p->data = newptr; } else { p = new linkleaf; p-> next = ptr; prevptr -> next = p; p->data = newptr; } } void btree :: traverse(node *ptr) { if(ptr == NULL) return; for(int i = 0; i < ptr->size; i++) cout<
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 82
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]; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 83
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]; for(int i = 0; i < parent->size;i++) if(parent->a[i] == oldkey) { BNMIT/ISE/2012/VI/ File Structure laboratory
Page 84
parent->a[i] = newkey; parent->next[i] = child; } } 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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 85
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); }
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 86
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) BNMIT/ISE/2012/VI/ File Structure laboratory
Page 87
{ 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 "<
Page 88
{ 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; } Output 1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B+Tree 5 1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B+Tree BNMIT/ISE/2012/VI/ File Structure laboratory
Page 89
8 --------------5 8 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B-Tree 4 --------------4 5 8 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 Enter The Key to be inserted in B-Tree 7 --------------4 5 7 8 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 1 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 90
Enter The Key to be inserted in B-Tree 11 --------------5 11 4 5 7 8 11 ---------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 2 Enter the key to be searched 11 Key found at level 2 1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 3 -----------------------4
5
7
8
11
-----------------------1.Insert a Key 2.Search a key 3.traverse tree 4.Exit 4 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 91
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 92
Program 11 Write a C++ program to store and retrieve student data from file using hashing. Use any collision resolution technique. #include<stdio.h> #include<stdlib.h> #include<string.h> #include
Page 93
cout<<"\n Enter the usn = "; cin>>usn; stry(buffer,name); //Packing the record onto the file using ‘|’ as a delimiter strcat(buffer,"|"); strcat(buffer,usn); strcat(buffer,"\n"); // \n delimiter for the record out<
//dynamically allocate space using ‘new’
stry(p->name,name1); stry(p->usn,usn1); p->link=NULL; prev=NULL; curr=h[hash_key]; if(curr==NULL)
//getting the hash pointer location Case: No collision
{ h[hash_key]=p; return; } while(curr!=NULL)
// Case : On collision – Insert at rear end
{ prev=curr; curr=curr->link; } prev->link=p; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 94
} void retrive() { fstream in; char name[15],usn[15]; int j,count; node *curr; in.open("student.txt",ios::in); // open the record file in input mode if(!in) { cout<<"\n Unable to open the file in input mode"; getch(); exit(0); } while(!in.eof()) { in.getline(name,15,'|'); //unpacking the record in.getline(usn,15,'\n'); count=0; for(j=0; j<strlen(usn); j++) //Calculate sum of ascii values of USN { count=count+usn[j]; } count=count%29;
//Hash Key = ASCII count% 29
hash_insert(name,usn,count); } cout<<"\n Enter the usn = "; cin>>usn; count=0; for(j=0; j<strlen(usn); j++)
// Calculating Hash Key
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 95
count=count+usn[j]; count=count%29; curr=h[count]; if(curr == NULL) { cout<<"\nRecord not found"; getch(); return; } do { if(strcmp(curr->usn,usn)==0) //When the record is found, retrieve { cout<<"\nRecord found : "<<curr->usn<<" "<<curr->name; getch(); return; } else { curr=curr->link; } }while(curr!=NULL);
//Search till end of list
if(curr==NULL) //End of list reached with no record found { cout<<"\nRecord not found"; getch(); return; } } BNMIT/ISE/2012/VI/ File Structure laboratory
Page 96
void main() { int choice; clrscr(); fstream out; out.open("student.txt",ios::out); if(!out) { cout<<"\nUnable to open the file in out mode"; getch(); exit(0); } for(;;) { cout<<"\n1:insert\n 2: retrive \n3:exit \nEnter the choice \n"; cin>>choice; switch(choice) { case 1: insert(); break; case 2: retrive(); break; case 3: exit(0); default: cout<<"\nInvalid option"; } } } Output: 1: insert BNMIT/ISE/2012/VI/ File Structure laboratory
Page 97
2: retrieve 3: exit Enter your choice 1 Enter name= sanjay Enter usn=1bg09is056 1: insert 2: retrieve 3: exit Enter your choice 1 Enter name= ashish Enter usn=1bg09is006 1: insert 2: retrieve 3: exit Enter your choice 1 Enter name= shreya Enter usn=1bg09is056 1: insert 2: retrieve 3: exit Enter your choice 2 Enter usn= 1bg09is056 Record found 1bg09is056
sanjay
1: insert 2: retrieve BNMIT/ISE/2012/VI/ File Structure laboratory
Page 98
3: exit Enter your choice 3
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 99
Program 12 Write a C++ program to reclaim the free space resulting from the deletion of records using linked lists. #include<stdio.h> #include
Page 100
while(p!=NULL) { stry(buffer,p->name); strcat(buffer,"|"); strcat(buffer,p->usn); strcat(buffer,"\n"); out<
Page 101
node *p,*q; char name[20],usn[20]; cout<<"name="; cin>>name; cout<<"usn="; cin>>usn; p=new node; stry(p->name,name); stry(p->usn,usn); p->link=NULL; if(first==NULL) { first=p; writefile(); display(); return; } for(q=first;q->link!=NULL;q=q->link); q->link=p; writefile(); display(); return; } void del1() { char usn[15]; node *prev,*curr,*del; //char usn; //int del; BNMIT/ISE/2012/VI/ File Structure laboratory
Page 102
if(first==NULL) { cout<<"list is empty\n"; return; //getch(); //exit(0); } cout<<"enter the usn u want to delete\n"; cin>>usn; if(strcmp(first->usn,usn)==0) { del=first; delete del; first=first->link; writefile(); display(); return; } prev=NULL; curr=first; while((strcmp(curr->usn,usn)!=0)&&(curr!=NULL)) { prev=curr; curr=curr->link; } if(curr==NULL) { cout<<"the rec with the usn "<<usn<<"did not find"; getch(); BNMIT/ISE/2012/VI/ File Structure laboratory
Page 103
exit(0); } prev->link=curr->link; writefile(); display(); } void main() { int ch; clrscr(); for(;;) { cout<<"1:insert\n2:delete\n3:quit"; cout<<"enter your choice\n"; cin>>ch; switch(ch) { case 1:insert(); break; case 2:del1(); break; case 3:exit(0); break; default:"invalid choice\n"; break; } } } Output: BNMIT/ISE/2012/VI/ File Structure laboratory
Page 104
1: insert 2. delete 3. exit Enter your choice 1 Name=menatha Usn=1bg09is048 Menatha 1bg09is048 1: insert 2. delete 3. exit Enter your choice 1 Name=subash Usn=1bg09is067 Menatha 1bg09is048 subash 1bg09is067 1: insert 2. delete 3. exit Enter your choice 1 Name=ayush Usn=1bg09is005 Menatha 1bg09is048 subash 1bg09is067 ayush 1bg09is005 1: insert 2. delete 3. exit Enter your choice 2 BNMIT/ISE/2012/VI/ File Structure laboratory
Page 105
Enter the usn you want to delete 1bg09is048 subash 1bg09is067 ayush 1bg09is005 1: insert 2. delete 3. exit Enter your choice 1 Name=Samarth Usn=1bg09is063 subash 1bg09is067 ayush 1bg09is005 Samarth 1bg09is063 1: insert 2. delete 3. exit Enter your choice 3
BNMIT/ISE/2012/VI/ File Structure laboratory
Page 106
Related Documents 3m3m1z
Bnmit File Structure Lab Manual 5h323n
December 2019 38
Data Structure Lab Manual 6t6e6r
December 2019 44
Standard Midi File Structure 6q3d6p
November 2019 62
Cbnst Lab File 41394w
January 2022 0
Dbms Lab File u5c2h
November 2021 0