HASH SORT
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <fstream.h>
#include <stdlib.h>
struct Student{
char del;
char edit;
char name[20];
char family[30];
long id;
};
struct fhash{
char family[30];
long id;
};
struct idhash{
long id;
long adrs;
};
int GetRecordCount(void){
long pos;
int result;
fstream file;
file.open("student.txt",ios::in|ios::binary);
file.seekg(0,ios::end);
pos=file.tellg();
result=pos/sizeof(Student);
file.close();
return result;
}
int ExistID(int index,Student* st){
if(index==-1)
return 0;
idhash hash;
Student st_temp;
int result;
long pos=index*sizeof(hash);
fstream file,idhfile;
idhfile.open("idhash.txt",ios::in|ios::binary);
idhfile.seekg(pos,ios::beg);
idhfile.read((char*)&hash,sizeof(hash));
idhfile.close();
file.open("student.txt",ios::in|ios::binary);
file.seekg(hash.adrs,ios::beg);
file.read((char*)&st_temp,sizeof(st_temp));
file.close();
if(st_temp.del=='0')
result=1;
else
result=0;
*st=st_temp;
return result;
}
void IDInFile(int index,long* id){
idhash hash;
long pos=index*sizeof(hash);
fstream idhfile;
idhfile.open("idhash.txt",ios::in|ios::binary);
idhfile.seekg(pos,ios::beg);
idhfile.read((char*)&hash,sizeof(hash));
idhfile.close();
*id=hash.id;
}
int BinarySearchID(long value,int low,int high){
int mid,result;
long x;
if(high<low)
result=-1;
else{
mid=low+((high-low)/2);
IDInFile(mid,&x);
if(x>value)
result=BinarySearchID(value,low,mid-1);
else if(x<value)
result=BinarySearchID(value,mid+1,high);
else // if x=value
result=mid;
}
return result;
}
void FamilyInFile(int index,char* str){
fhash hash;
long pos=index*sizeof(hash);
fstream fhfile;
fhfile.open("fhash.txt",ios::in|ios::binary);
fhfile.seekg(pos,ios::beg);
fhfile.read((char*)&hash,sizeof(hash));
fhfile.close();
strcpy(str,hash.family);
}
int BinarySearchFamily(char* value,int low,int high){
int mid,result;
char x[30]={"0"};
if(high<low)
result=-1;
else{
mid=low+((high-low)/2);
FamilyInFile(mid,x);
if(strcmp(x,value)>0) // x>value
result=BinarySearchFamily(value,low,mid-1);
else if(strcmp(x,value)<0) // x<value
result=BinarySearchFamily(value,mid+1,high);
else // if x=value
result=mid;
}
return result;
}
void Insert(Student st,int low,int high){
int mid,i,l,h,test;
char x1[30]={"0"};
long x2;
fstream file,fhfile,idhfile;
fhash fh,fhtemp;
idhash idh,idhtemp;
file.open("student.txt",ios::app |ios::binary);
file.seekg(0,ios::end);
idh.id=st.id;
idh.adrs=file.tellg();
fh.id=st.id;
strcpy(fh.family,st.family);
file.write((char*)&st,sizeof(st));
file.close();
l=low;
h=high;
if(high==-1){
fhfile.open("fhash.txt",ios::app|ios::binary);
fhfile.seekg(0,ios::end);
fhfile.write((char*)&fh,sizeof(fh));
fhfile.close();
idhfile.open("idhash.txt",ios::app|ios::binary);
idhfile.seekg(0,ios::end);
idhfile.write((char*)&idh,sizeof(idh));
idhfile.close();
}
else{
FamilyInFile(high,x1);
if(strcmp(x1,fh.family)<0){
fhfile.open("fhash.txt",ios::app|ios::binary);
fhfile.seekg(0,ios::end);
fhfile.write((char*)&fh,sizeof(fh));
fhfile.close();
}//bozorgtar az high
else{
test=0;
mid=low;
while(low<high){
mid=low+((high-low)/2);
FamilyInFile(mid,x1);
if(strcmp(x1,fh.family)>0)
high=mid;
else if(strcmp(x1,fh.family)<0){
low=mid+1;
mid=low;
}//else if
else{
test=1;
break;
}//else
}//while
fhfile.open("fhash.txt",ios::in | ios::out|ios::binary);
if(test==0){
for(i=h;i>=mid;i--){
fhfile.seekg(i*sizeof(fh),ios::beg);
fhfile.read((char*)&fhtemp,sizeof(fhtemp));
fhfile.seekg((i+1)*sizeof(fh),ios::beg);
fhfile.write((char*)&fhtemp,sizeof(fhtemp));
}//for
}//if test
fhfile.seekg(mid*sizeof(fh),ios::beg);
fhfile.write((char*)&fh,sizeof(fh));
fhfile.close();
}//else
low=l;
high=h;
IDInFile(high,&x2);
if(x2<idh.id){
idhfile.open("idhash.txt",ios::app |ios::binary);
idhfile.seekg(0,ios::end);
idhfile.write((char*)&idh,sizeof(idh));
idhfile.close();
}
else{
test=0;
mid=low;
while(low<high){
mid=low+((high-low)/2);
IDInFile(mid,&x2);
if(x2>idh.id)
high=mid;
else if(x2<idh.id){
low=mid+1;
mid=low;
}
else{
test=1;
break;
}
}
idhfile.open("idhash.txt",ios::in | ios::out|ios::binary);
if(test==0){
for(i=h;i>=mid;i--){
idhfile.seekg(i*sizeof(idh),ios::beg);
idhfile.read((char*)&idhtemp,sizeof(idhtemp));
idhfile.seekg((i+1)*sizeof(idh),ios::beg);
idhfile.write((char*)&idhtemp,sizeof(idhtemp));
}
}
idhfile.seekg(mid*sizeof(idh),ios::beg);
idhfile.write((char*)&idh,sizeof(idh));
idhfile.close();
}
}
}
long GetIDofFamily(int founded){
fhash hash;
long pos=founded*sizeof(hash);
fstream fhfile;
fhfile.open("fhash.txt",ios::in |ios::binary);
fhfile.seekg(pos,ios::beg);
fhfile.read((char*)&hash,sizeof(hash));
fhfile.close();
return hash.id;
}
void Delete(int founded){
idhash hash;
Student st_temp;
long pos=founded*sizeof(hash);
fstream file,idhfile;
idhfile.open("idhash.txt",ios::in |ios::binary);
idhfile.seekg(pos,ios::beg);
idhfile.read((char*)&hash,sizeof(hash));
idhfile.close();
file.open("student.txt",ios::in | ios::out |ios::binary);
file.seekg(hash.adrs,ios::beg);
file.read((char*)&st_temp,sizeof(st_temp));
st_temp.del='1';
file.seekg(hash.adrs,ios::beg);
file.write((char*)&st_temp,sizeof(st_temp));
file.close();
}
void Edit(int founded){
idhash hash;
Student st_temp;
long pos=founded*sizeof(hash);
fstream file,idhfile;
idhfile.open("idhash.txt",ios::in|ios::binary);
idhfile.seekg(pos,ios::beg);
idhfile.read((char*)&hash,sizeof(hash));
idhfile.close();
file.open("student.txt",ios::in | ios::out |ios::binary);
file.seekg(hash.adrs,ios::beg);
file.read((char*)&st_temp,sizeof(st_temp));
st_temp.edit='1';
file.seekg(hash.adrs,ios::beg);
file.write((char*)&st_temp,sizeof(st_temp));
file.close();
file.open("student.txt",ios::in | ios::out |ios::binary);
file.seekg(hash.adrs,ios::beg);
st_temp.edit='0';
cout << "enter new name : ";
cin >> st_temp.name;
file.write((char*)&st_temp,sizeof(st_temp));
file.close();
}
int main(){
Student st1,st2;
fhash fh;
idhash idh;
int quit=0,select,count=0,founded;
long id;
char family[30]={"0"};
fstream file,fhfile,idhfile;
file.open("student.txt",ios::in | ios::out |ios::binary);
file.close();
fhfile.open("fhash.txt",ios::in | ios::out |ios::binary);
fhfile.close();
idhfile.open("idhash.txt",ios::in | ios::out |ios::binary);
idhfile.close();
count=GetRecordCount();
while(!quit){
system("cls");
cout << "1: insert" << endl;
cout << "2: search by id" << endl;
cout << "3: search by family" << endl;
cout << "4: delete" << endl;
cout << "5: edit" << endl;
cout << "6: list not complete edited records" << endl;
cout << "7: quit" << endl;
cout << endl;
cout << "enter your select : ";
cin >> select;
cout << endl;
switch(select){
case 1:
cout << "enter id : ";
cin >> st1.id;
founded=BinarySearchID(st1.id,0,count-1);
if(!ExistID(founded,&st2)){
cout << "enter name : ";
cin >> st1.name;
cout << "enter family : ";
cin >> st1.family;
st1.del='0';
st1.edit='0';
Insert(st1,0,count-1);
count++;
}
else{
cout << "ID already exists!";
getch();
}
break;
case 2:
cout << "enter id : ";
cin >> id;
founded=BinarySearchID(id,0,count-1);
if(ExistID(founded,&st1)){
cout << "name : " << st1.name << " - "
<< "family : " << st1.family;
getch();
}
else{
cout << "ID not exists!";
getch();
}
break;
case 3:
cout << "enter family : ";
cin >> family;
founded=BinarySearchFamily(family,0,count-1);
id=GetIDofFamily(founded);
founded=BinarySearchID(id,0,count-1);
if(ExistID(founded,&st1)){
cout << "id : " << st1.id << " - "
<< "name : " << st1.name << " - "
<< "family : " << st1.family;
getch();
}
else{
cout << "family not exists!";
getch();
}
break;
case 4:
cout << "enter id : ";
cin >> id;
founded=BinarySearchID(id,0,count-1);
if(ExistID(founded,&st1)){
cout << "name : " << st1.name << " - "
<< "family : " << st1.family << endl;
Delete(founded);
cout << "deleted!";
getch();
}
else{
cout << "ID not exists!";
getch();
}
break;
case 5:
cout << "enter id : ";
cin >> id;
founded=BinarySearchID(id,0,count-1);
if(ExistID(founded,&st1)){
cout << "name : " << st1.name << " - "
<< "family : " << st1.family << endl;
Edit(founded);
}
else{
cout << "ID not exists!";
getch();
}
break;
case 6:
cout << "--------------------------------" << endl;
file.open("student.txt",ios::in|ios::binary);
file.read((char*)&st1,sizeof(st1));
while(!file.eof()){
if(st1.edit=='1')
cout << st1.id << " - " << st1.name << " - " << st1.family << endl;
file.read((char*)&st1,sizeof(st1));
}
file.close();
cout << "--------------------------------" << endl;
getch();
break;
case 7:
quit=1;
}
}
return 0;
}
پاسخ با نقل قول
