Добавил:
Hist
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Программы c++ (сортировка, хэширование) / 3 / lab_3.6.3_B
.cpp#include <iostream>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <limits>
#define N 20
#define MaxStrLen 7
#define Ns 8
using namespace std;
char st[N][MaxStrLen];
int ht[N],sin_arr[Ns];
void menu_display(void)
{
system("cls");
cout<<"1 - dobavit"<<endl;
cout<<"2 - udalit"<<endl;
cout<<"3 - poisk"<<endl;
cout<<"4 - vyvod na ekran hesh tablicy"<<endl;
cout<<"5 - vyhod"<<endl;
}
void next(void)
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cin.clear();
cin.get();
}
void clear_ht(void)
{
int i;
system("cls");
for (i=0; i<N; i++)
{
ht[i]=-1;
strcpy(st[i],"");
}
for (i=0; i<Ns; i++)
{
sin_arr[i]=-1;
}
cout<<"hesh tablica ochishena"<<endl;
}
int Rash_1(char x[])
{
int StringLength,HashKey,i,tmp;
StringLength=strlen(x);
HashKey=0;
for (i=0; i<=StringLength; i++) {HashKey=HashKey+x[i];}
tmp=HashKey/10;
HashKey=HashKey-10*tmp+HashKey/10;
if (HashKey>N) {HashKey=HashKey%N;}
return HashKey;
}
int add_to_ht(int m)
{
//dobavleno s rashepleniem 2, return hashkey [0..19]
//dobavleno v sinonemy, return (-соотв_ключ_хэш_табл-2) [-2..-21]
int i,key,isempty_sa,isempty_ht;
key=Rash_1(st[m]);
if (ht[key]==-1) //key svoboden
{
ht[key]=m;
return key;
}
//dobavleno v sinonemy
//poisk cvobodnoi icheiki sin_arr
isempty_sa=-1;
for (i=0; i<Ns; i++)
{
if (sin_arr[i]==-1)
{
isempty_sa=i;
break;
}
}
//poisk sverhu svobodnogo elementa ht
//for (i=0; i<N; i++)
for (i=key+1; i<N; i++)
{
if (ht[i]==-1)
{
isempty_ht=i;
break;
}
}
// zapis v sin_arr nomera cvobodnoi icheiki hesh tablicy, a v hesh tablicy nomera stroki
sin_arr[isempty_sa]=isempty_ht;
ht[isempty_ht]=m;
return -isempty_ht-2;
}
void search(void)
{
int i,key;
char inp_str[MaxStrLen];
bool result=false;
system("cls");
cout<<"vvedite stroku dli poiska \n";
cin>>inp_str;
key=Rash_1(inp_str);
if (strcmp(st[ht[key]],inp_str)==0)
{
result=true;
cout<<"naiden s klichom "<<key<<endl;
}
else
{
for (i=0; i<Ns && sin_arr[i]!=-1; i++)
{
//cout<<st[ht[sin_arr[i]]]<<endl;
if (strcmp(st[ht[sin_arr[i]]],inp_str)==0)
{
result=true;
cout<<"naiden v sinonemah \n";
break;
}
}
}
if (result==false) {cout<<"ne naiden \n";}
}
void add_new_string(void)
{
int i,isempty,result;
char inp_str[MaxStrLen];
system("cls");
//proverka zapolnennsti tablicy strok i vozvrashenie nomera pustoi stroki.
isempty=-1;
for (i=0; i<N; i++)
{
if (strcmp(st[i],"")==0)
{
isempty=i;
break;
}
}
if (isempty==-1) {cout<<"tablica strok perepolnenna \n";}
else //vvod stroki, proverka na ee nalishie v massive
{
cout<<"vvedite stroku \n";
cin>>inp_str;
//cout<<search_result(inp_str)<<endl;
//if (search_result(inp_str)!=-1) {cout<<"stroka yche soderzitci v massive \n";}
//else //dobavlenie v massiv strok i hesh tablicu
{
strcpy(st[isempty],inp_str); //zapis massiv v strok
result=add_to_ht(isempty);
if (result>-1) {cout<<"dobavlen s klichom "<<result<<endl;}
if (result<-1) {cout<<"sinonem. dobavlen v hesh tablicu s klichom "<<-result-2<<endl;}
}
}
}
void ht_output(void)
{
int i;
system("cls");
cout<<"key - nomer stroki - stroka"<<endl<<endl;
for (i=0; i<N; i++)
{
if (ht[i]!=-1) {cout<<setw(3)<<i<<setw(10)<<ht[i]<<"\t"<<" "<<st[ht[i]]<<endl;}
else {cout<<setw(3)<<i<<setw(15)<<"<empty>"<<endl;}
}
cout<<endl<<endl<<endl<<"********sinonemy********"<<endl<<endl;
cout<<"nomer_stroki"<<endl<<endl;
for (i=0; i<Ns && sin_arr[i]!=-1; i++) {cout<<setw(6)<<sin_arr[i]<<endl;}
}
bool remove_string(void)
{
char inp_str[MaxStrLen];
int i,j,key;
system("cls");
cout<<"vvedite stroku"<<endl<<">";
cin>>inp_str;
key=Rash_1(inp_str);
if (strcmp(st[ht[key]],inp_str)==0)
{
cout<<"naiden s klichom "<<key<<", udalen \n";
strcpy(st[ht[key]],"");
ht[key]=-1;
return 0;
}
else
{
for (i=0; i<Ns && sin_arr[i]!=-1; i++)
{
if (strcmp(st[ht[sin_arr[i]]],inp_str)==0)
{
cout<<"naiden v sinonemah, udalen \n";
strcpy(st[ht[sin_arr[i]]],"");
ht[sin_arr[i]]=-1;
sin_arr[i]=-1;
for (j=i; j<Ns; j++) {sin_arr[j]=sin_arr[j+1];}
return 0;
}
}
}
cout<<"ne naiden \n";
return 1;
}
int main(void)
{
int choose=0;
clear_ht();
while (choose<8)
{
menu_display();
cout<<">";
cin>>choose;
switch (choose)
{
case 1: {add_new_string(); next(); break;}
case 2: {remove_string(); next(); break;}
case 3: {search(); next(); break;}
case 4: {ht_output(); next(); break;}
case 5: {return 0;}
}
}
}
Соседние файлы в папке 3