Добавил:
Hist
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Программы c++ (сортировка, хэширование) / 3 / lab_3.6.7_Sokolov_w
.cpp#include <iostream>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <limits>
#include "math.h"
using namespace std;
int nmax, n1, n2, j, i, tmp, tmp1, menu, cmp, cmp1, n, nac, ht1, k, n3, tmp2, HashKey;
char inp_str[7];
int ac[40];
int ht[40];
int num[40];
char str[40][7];
char Hash[40][7];
void Sin(int HashKey)
{
if(ac[HashKey]==-1 || strcmp(Hash[ac[HashKey]],"delete")==0 ) // (||-or)
{
nac=HashKey;
if (strcmp(Hash[ac[HashKey]],"delete")==0) {strcpy(Hash[ac[HashKey]],str[n2]);}
else
{
ac[HashKey]=n1;
strcpy(Hash[n1],str[n2]);
}
}
else {Sin(ac[HashKey]);}
}
void Output(void)
{
int i;
system("cls");
for(i=0; i<40; i++) /////!!!!!!!!!!
{
if(i<=9)
{cout<<i<<" ";}
else {cout<<i;}
cout<<" ";
for(k=0; k<7 && str[i][k]>0; k++);
cout<<str[i];
for(j=1; j<7-k; j++) {cout<<" ";}
cout<<" ";
if(ht[i]<=9 && ht[i]>=0) {cout<<" "<<ht[i];}
else {cout<<ht[i];}
cout<<" ";
for(k=0; k<7 && Hash[i][k]>0; k++);
cout<<Hash[i];
for(j=1; j<7-k; j++) {cout<<" ";}
cout<<" ";
if(ac[i]<=9 && ac[i]>=0) {cout<<" "<<ac[i];}
else {cout<<ac[i];}
cout<<"\n";
}
cout<<"\n";
cout<<"------------------"<<"\n";
}
int mult(char x[]) //вычисление хэш ключа
{
int i,l;
unsigned long tmp1,tmp2;
float tmp;
l=strlen(x);
//tmp=pow(1000,l);
tmp=0;
for (i=0; i<l; i++)
{
tmp=tmp+x[i]*pow(1000,i);
//cout<<tmp<<" "<<str[i]<<endl;;
}
tmp=tmp*tmp;
//cout<<endl<<tmp<<endl;
tmp1=(tmp/pow(1000,l));
tmp1=tmp1%10;
tmp2=tmp1*10;
//cout<<tmp1<<endl;
tmp1=(tmp/pow(1000,l)/10);
tmp1=tmp1%10;
tmp2=tmp2+tmp1;
//cout<<tmp1<<endl;
//cout<<tmp2<<endl;
tmp2=tmp2%20;
//cout<<tmp2<<endl;
return tmp2;
}
void hash_calc(void)
{
tmp=0;
for(i=0; i<7 && str[n2][i]!='0'; i++)
{
tmp1=str[n2][i];
tmp=tmp+tmp1;
}
HashKey=tmp%19;
ht[n2]=HashKey;
while (HashKey>nmax-1)
{
HashKey=HashKey%19;
ht[n2]=HashKey;
}
//HashKey=mult(str[n2]);
if(strcmp(Hash[HashKey],"empty")==0 )
{
nac=HashKey;
strcpy(Hash[HashKey],str[n2]);
}
else
{
cmp=-1;
cmp1=-1;
for(i=20; i<=40 && cmp!=0 ; i++ ) {cmp=strcmp(Hash[i],"empty");}
n1=i-1;
Sin(HashKey);
}
//cout<<"!!!\n";
}
void Find(int n)
{
if (strcmp(Hash[n],inp_str)==0) {nac=n;}
else
{
ht1=n;
Find(ac[n]);
}
}
void RemoveCh(int x)
{
if (ac[x]!=-1 )
{
num[0]=n3;
num[j]=ac[x];
j=j+1;
RemoveCh(ac[x]);
}
else
{
tmp2=j-1;
for (k=j-1; k>=0 && cmp==0; k--)
{
//cout<<"k="<<k<<" "<<num[k]<<"\n";
cmp=strcmp(Hash[num[k]],"delete");
if (cmp==0)
{tmp2=tmp2-1;}
}
//cout<<"h="<<tmp2<<"\n";
for (i=j-1; i>tmp2; i--)
{
//cout<<"i="<<i<<" "<<num[i]<<"\n";
//cout<<num[i]<<"\n";
//if (strcmp(Hash[num[i]],"empty")==0)
//{
ac[num[i-1]]=-1;
strcpy(Hash[num[i]],"empty");
//}
}
//for (i=j; i>tmp2; i--)
//{
// strcpy(Hash[num[i+1]],"empty");
//}
}
}
void remove_find(int n)
{
if (strcmp(Hash[n],inp_str)==0)
{
strcpy(Hash[n],"delete");
nac=n;
RemoveCh(n3);
}
else
{
ht1=n;
nac=n;
remove_find(ac[n]);
}
}
void Remove(void)
{
system("cls");
cout<<"Enter the key \n";
cin>>inp_str;
cmp=-1;
for(i=0; i<nmax-1 && cmp!=0; i++ )
{
cmp=strcmp(str[i],inp_str);
}
if (cmp!=0) {cout<<"Key not found\n";}
else
{
strcpy(str[i-1],"empty");
n=ht[i-1];
n3=ht[i-1];
ht[i-1]=-1;
j=1;
remove_find(n);
cout<<inp_str<<" removed\n";
}
}
void Add(void)
{
system("cls");
cmp=-1;
for(i=0; i<=40 && cmp!=0; i++ ) //проверка на заполненность таблицы (1)
{cmp=strcmp(str[i],"empty");}
n2=i-1;
if(n2>nmax-1)
{
cout<<"The table is full \n";
} //конец проверки (1)
else
{
cout << "Enter the key \n";
cin>>inp_str;
cmp=-1;
for(i=0; i<nmax-1 && cmp!=0; i++ ) //проверка на наличие ключа в таблице (2)
{
cmp=strcmp(str[i],inp_str);
}
if (cmp==0)
{
cout << "Key is already entered \n";
} //конец проверки (2)
else
{
strcpy(str[n2],inp_str);
hash_calc();
cout<<"Added with key="<<ht[n2]<<" and ac="<<ac[nac]<<endl;
}
}
}
void Search(void)
{
system("cls");
cout << "Enter the key";
cin>>inp_str;
cmp=-1;
for(i=0; i<nmax-1 && cmp!=0; i++ )
{
cmp=strcmp(str[i],inp_str);
};
if (cmp!=0) {cout << "Key not found \n";}
else
{
n=ht[i-1];
Find(n);
cout<<Hash[nac]<<" "<<nac<<"\n";
}
cout<<"-----"<<"\n";
}
void next(void)
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cin.clear();
cin.get();
}
int main(void)
{
menu=0;
nmax=20;
n2=-1;
n1=nmax-1;
for(i=0; i<40; i++)
{
strcpy(Hash[i],"empty");
ac[i]=-1;
ht[i]=-1;
strcpy(str[i],"empty");
};
while(menu<5)
{
cout<<"1-Add\n";
cout<<"2-Remove\n";
cout<<"3-Find\n";
cout<<"4-OutPut\n";
cout<<"5-Exit\n";
cin>>menu;
switch(menu)
{
case 1: {Add(); next(); system("cls"); break;}
case 2: {Remove(); next(); system("cls"); break;}
case 3: {Search(); next(); system("cls"); break;}
case 4: {Output(); next(); system("cls"); break;}
case 5: {return 0;}
}
}
return 0;
}
Соседние файлы в папке 3