Добавил:
Hist
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Программы c++ (сортировка, хэширование) / 3 / lab_3.7_galya
.cpp#include <iostream>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <limits>
using namespace std;
int nmax, nmin, n1, n2, j, i, p, p1, p2, p3, menu, cmp, cmp1, n, nchain, nchain1, k, n3, h, n4;
int prand, pr1, pr2;
char massn2[7];
long int pro;
int chain[40];
int chain1[40];
int number[40];
char mass[40][7];
char Hash[40][7];
void Synonim(int pr1)
{
if(chain[pr1]==-1 || strcmp(Hash[chain[pr1]],"delete")==0 )
{
nchain=pr1;
if (strcmp(Hash[chain[pr1]],"delete")==0)
{
strcpy(Hash[chain[pr1]],mass[n2]);
}
else
{
chain[pr1]=n1;
strcpy(Hash[n1],mass[n2]);
}
}
else
{
Synonim(chain[pr1]);
}
}
void Output(void)
{
int i;
for(i=0; i<35; i++)
{
if(i<=9)
{
cout<<i<<" ";
}
else
{
cout<<i;
}
cout<<" ";
for(k=0; k<7 && mass[i][k]>0; k++);
cout<<mass[i];
for(j=1; j<7-k; j++)
{
cout<<" ";
}
cout<<" ";
if(chain1[i]<=9 && chain1[i]>=0)
{
cout<<" "<<chain1[i];
}
else
{
cout<<chain1[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(chain[i]<=9 && chain[i]>=0)
{
cout<<" "<<chain[i];
}
else
{
cout<<chain[i];
}
cout<<"\n";
}
cout<<"\n";
cout<<"-----"<<"\n";
}
void Hashing(void)
{
p=0;
for(i=0; i<7 && mass[n2][i]!='0'; i++)
{
p1=mass[n2][i];
p=p+p1;
};
pr1=p%19;
chain1[n2]=pr1;
while (pr1>nmax-1)
{
pr1=pr1%19;
chain1[n2]=pr1;
};
if(strcmp(Hash[pr1],"empty")==0 )
{
nchain=pr1;
strcpy(Hash[pr1],mass[n2]);
}
else
{
cmp=-1;
cmp1=-1;
for(i=20; i<=40 && cmp!=0 ; i++ )
{
cmp=strcmp(Hash[i],"empty");
};
n1=i-1;
Synonim(pr1);
};
cout<<"-----"<<"\n";
}
void Find(int n)
{
if (strcmp(Hash[n],massn2)==0)
{
nchain=n;
}
else
{
nchain1=n;
Find(chain[n]);
}
}
void DeleteChain(int param)
{
if (chain[param]!=-1 )
//&& strcmp(Hash[chain[param]],"empty")!=0
{
number[0]=n3;
number[j]=chain[param];
j=j+1;
DeleteChain(chain[param]);
}
else
{
h=j-1;
//cmp=strcmp(Hash[number[j-1]],"empty");
for (k=j-1; k>=0 && cmp==0; k--)
{
cout<<"k="<<k<<" "<<number[k]<<"\n";
//cmp=strcmp(Hash[number[j-1]],"empty");
cmp=strcmp(Hash[number[k]],"delete");
if (cmp==0)
{h=h-1;};
};
//cout<<Hash[number[j-1]]<<"\n";
cout<<"h="<<h<<"\n";
cout<<"\n";
for (i=j-1; i>h; i--)
{
cout<<"i="<<i<<" "<<number[i]<<"\n";
//cout<<number[i]<<"\n";
//if (strcmp(Hash[number[i]],"empty")==0)
//{
chain[number[i-1]]=-1;
strcpy(Hash[number[i]],"empty");
//};
};
//for (i=j; i>h; i--)
//{
// strcpy(Hash[number[i+1]],"empty");
//};
};
}
void FindDelete(int n)
{
if (strcmp(Hash[n],massn2)==0)
{
strcpy(Hash[n],"delete");
nchain=n;
DeleteChain(n3);
}
else
{
nchain1=n;
nchain=n;
FindDelete(chain[n]);
};
}
void Delete(void)
{
cout<<"Enter the key \n";
cin>>massn2;
cmp=-1;
for(i=0; i<nmax-1 && cmp!=0; i++ )
{
cmp=strcmp(mass[i],massn2);
};
if (cmp!=0) {cout<<"Key not found \n ***** \n";}
else
{
strcpy(mass[i-1],"empty");
n=chain1[i-1];
n3=chain1[i-1];
chain1[i-1]=-1;
j=1;
FindDelete(n);
}
}
void Add(void)
{
cmp=-1;
for(i=0; i<=40 && cmp!=0; i++ ) //проверка на заполненность таблицы (1)
{
cmp=strcmp(mass[i],"empty");
}
n2=i-1;
if(n2>nmax-1)
{
cout<<"The table is full";
cout<<"\n";
cout<<"-----"<<"\n";
} //конец проверки (1)
else
{
cout << "Enter the key:";
cin>>massn2;
cmp=-1;
for(i=0; i<nmax-1 && cmp!=0; i++ ) //проверка на наличие ключа в таблице (2)
{
cmp=strcmp(mass[i],massn2);
}
if (cmp==0)
{
cout << "This key is already entered";
cout<<"\n";
cout<<"-----"<<"\n";
} //конец проверки (2)
else
{
strcpy(mass[n2],massn2);
Hashing();
cout<<mass[n2]<<" "<<chain1[n2]<<" "<<chain[nchain]<<"\n";
}
}
}
void FindKey(void)
{
cout << "Enter the key:";
cin>>massn2;
cmp=-1;
for(i=0; i<nmax-1 && cmp!=0; i++ )
{
cmp=strcmp(mass[i],massn2);
};
if (cmp!=0)
{
cout << "Such key is not entered";
cout<<"\n";
}
else
{
n=chain1[i-1];
Find(n);
cout<<Hash[nchain]<<" "<<nchain<<"\n";
};
cout<<"-----"<<"\n";
}
int main(void)
{
menu=0;
nmax=20;
n2=-1;
n1=nmax-1;
for(i=0; i<40; i++)
{
strcpy(Hash[i],"empty");
chain[i]=-1;
chain1[i]=-1;
strcpy(mass[i],"empty");
};
while(menu<5)
{
cout<<"1-out\n";
cout<<"2-add\n";
cout<<"3-delete\n";
cout<<"4-find the key\n";
cout<<"5-exit\n";
cin>>menu;
switch(menu)
{
case 1:{Output();break;}
case 2:{Add();break;}
case 3:{Delete();break;}
case 4:{FindKey();break;}
case 5:{return 0;}
}
}
return 0;
}
Соседние файлы в папке 3