Добавил:
Hist
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Программы c++ (сортировка, хэширование) / 3 / old1 / lab_3
.5.cpp#include <iostream>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <limits>
#define N 20 //количество строк
#define MaxStrLen 10 //максимальная длина строки
#define Ns 8
using namespace std;
char st[N][MaxStrLen];
int ht[N], sin_arr[Ns];
void init_str(void)
{
strcpy(st[0],"zero");
strcpy(st[1],"one");
strcpy(st[2],"two");
strcpy(st[3],"three");
strcpy(st[4],"four");
strcpy(st[5],"five");
strcpy(st[6],"six");
strcpy(st[7],"seven");
strcpy(st[8],"eight");
strcpy(st[9],"nine");
strcpy(st[10],"ten");
strcpy(st[11],"eleven");
strcpy(st[12],"twelve");
strcpy(st[13],"thirteen");
strcpy(st[14],"fourteen");
strcpy(st[15],"fifteen");
strcpy(st[16],"sixteen");
strcpy(st[17],"seventeen");
strcpy(st[18],"eighteen");
strcpy(st[19],"nineteen");
strcpy(st[13],"");
}
int hash_calc_sv2(char x[])
{
int StringLength,HashKey,i,tmp;
StringLength=strlen(x);
HashKey=0;
if (StringLength%2==0) //Чётный случай
{
for (i=0; i<StringLength; i=i+2)
{
tmp=x[i];
tmp=tmp*1000;
tmp=tmp+x[i+1];
HashKey=HashKey+tmp;
}
}
if (StringLength%2!=0) //Нечётный случай
{
for (i=1; i<StringLength; i=i+2)
{
tmp=x[i];
tmp=tmp*1000;
tmp=tmp+x[i+1];
HashKey=HashKey+tmp;
}
HashKey=HashKey+x[0];
}
return (HashKey);
}
int hash_calc(char x[])
{
int StringLength,HashKey,i;
StringLength=strlen(x);
HashKey=0;
for (i=0; i<=StringLength; i++) {HashKey=HashKey+x[i];}
return (HashKey);
}
void init_hash_table(void)
{
int i,k,key;
system("clear");
for (i=0; i<N; i++) {ht[i]=-1;}
for (i=0; i<Ns; i++) {sin_arr[i]=-1;}
k=0;
for (i=0; i<N; i++)
{
if (strcmp(st[i],"")!=0)
{
key=hash_calc_sv2(st[i])%N;//Свёртка 2
if (ht[key]==-1) {ht[key]=i;}
else
{
key=hash_calc(st[i])%19;//Простое число
if (ht[key]==-1) {ht[key]=i;}
else
{
sin_arr[k]=i;
k++;
}
}
}
}
cout<<"хэш таблица перестроена"<<endl;
}
void ht_output(void)
{
int i;
system("clear");
cout<<"ключ - номер_строки - строка"<<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<<"********Синонимы********"<<endl<<endl;
cout<<"номер_строки - строка"<<endl<<endl;
for (i=0; i<Ns && sin_arr[i]!=-1; i++) {cout<<" "<<i<<"\t"<<" "<<st[sin_arr[i]]<<endl;}
}
void add_to_ht(int m)
{
int key,i,k=-1;
key=hash_calc_sv2(st[m])%N;//свёртка 2
if (ht[key]==-1) {ht[key]=m;}
else
{
key=hash_calc(st[m])%19; //простое число
if (ht[key]==-1) {ht[key]=m;}
else
{
for (i=0; i<Ns; i++)
{
if (sin_arr[i]==-1)
{
k=i;
break;
}
}// k=sizeof(sin_arr)
sin_arr[k]=m;
}
}
}
int search_result(char input_str[])
{
int i,key;
key=hash_calc_sv2(input_str)%N;//Свёртка 2
cout<<"hashkey (свёртка 2) = "<<key<<endl;
if (strcmp(input_str,st[ht[key]])==0) {return 1;}
else
{
key=hash_calc(input_str)%19; //Простое число
cout<<"hashkey (простое число) = "<<key<<endl;
if (strcmp(input_str,st[ht[key]])==0) {return 2;}
else //Линейный поиск
{
for (i=0; i<Ns; i++)
{
if (strcmp(input_str,st[sin_arr[i]])==0)
{
cout<<"линейный поиск "<<i+1<<" интерация"<<endl;
return (i+3);
}
}
}
}
return 0;
}
void add_new_string(void)
{
int i,isempty;
char input_string[MaxStrLen];
system("clear");
isempty=-1;
for (i=0; i<N; i++)
{
if (strcmp(st[i],"")==0)
{
isempty=i;
break;
}
}
if (isempty==-1) {cout<<"Таблица переполнена"<<endl;}
else
{
cout<<"Введите строку"<<endl<<">";
cin>>input_string;
if (search_result(input_string)==0)
{
strcpy(st[isempty],input_string);
add_to_ht(isempty);
cout<<"добавлено в st["<<isempty<<"]"<<endl;
}
else {cout<<"строка уже содержится в массиве"<<endl;}
}
}
void search(void)
{
char x[MaxStrLen];
int l;
system("clear");
cout<<"Введите строку"<<endl;
cin>>x;
l=search_result(x);
if (l==0) {cout<<"not found"<<endl;}
else {cout<<"found ("<<l<<")"<<endl;}
}
void remove_string(void)
{
char input_str[MaxStrLen];
int i,j,key;
bool result=false;
system("clear");
cout<<"Введите строку"<<endl<<">";
cin>>input_str;
key=hash_calc_sv2(input_str)%N;//Свёртка 2
if (strcmp(input_str,st[ht[key]])==0)
{
strcpy(st[ht[key]],"");
ht[key]=-1;
}
else
{
key=hash_calc(input_str)%19; //Простое число
if (strcmp(input_str,st[ht[key]])==0)
{
strcpy(st[ht[key]],"");
ht[key]=-1;
}
else
{
for (i=0; i<Ns; i++)
{
if (strcmp(input_str,st[sin_arr[i]])==0)
{
result=true;
cout<<"найден в лп"<<endl;
strcpy(st[sin_arr[i]],"");
sin_arr[i]=-1;
for (j=i; j<Ns; j++) {sin_arr[j]=sin_arr[j+1];}
break;
}
}
if (result==false) {cout<<"not found"<<endl;}
}
}
}
void clear_ht(void)
{
int i;
system("clear");
for (i=0; i<N; i++) {ht[i]=-1;}
for (i=0; i<Ns; i++) {sin_arr[i]=-1;}
cout<<"хэш таблица очищена"<<endl;
}
void menu_display(void)
{
system("clear");
cout<<"1 - добавить"<<endl;
cout<<"2 - удалить"<<endl;
cout<<"3 - поиск"<<endl;
cout<<"4 - вывод на экран хэш таблицы"<<endl;
cout<<"5 - перестроить хэш таблицу"<<endl;
cout<<"6 - очистить хэш таблицу"<<endl;
cout<<"7 - выход"<<endl;
}
void next(void)
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cin.clear();
cin.get();
}
int main(void)
{
int choose=0;
clear_ht();
//init_str();
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: {init_hash_table(); next(); break;}
case 6: {clear_ht(); next(); break;}
case 7: {return 0;}
}
}
}
Соседние файлы в папке old1