Добавил:
Hist
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Программы c++ (сортировка, хэширование) / 3 / lab_3.6.2_vlad
.cpp/*
Гуров Егор
А6-09
Для компиляции был использован gcc 4.4.3 (linux)
*/
#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 ht1[N], sin_arr[Ns];
bool ht2[N];
void clear_ht(void)
{
int i;
system("clear");
for (i=0; i<N; i++)
{
ht1[i]=-1;
ht2[i]=false;
}
for (i=0; i<Ns; i++) {sin_arr[i]=-1;}
cout<<"Хэш таблица очищена"<<endl;
}
int Rash_2(char x[])
{
int StringLength,HashKey,i,tmp;
StringLength=strlen(x);
HashKey=0;
for (i=0; i<=StringLength; i++) {HashKey=HashKey+x[i];}
tmp=HashKey/100;
HashKey=HashKey-99*tmp;
if (HashKey>N) {HashKey=HashKey%N;}
return HashKey;
}
void ht_output(void)
{
int i;
system("clear");
cout<<"Ключ - Номер_строки - Строка - Наличие синонима"<<endl<<endl;
for (i=0; i<N; i++)
{
if (ht1[i]!=-1) {cout<<setw(3)<<i<<setw(10)<<ht1[i]<<"\t"<<" "<<st[ht1[i]]<<"\t"<<ht2[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<<" "<<sin_arr[i]<<"\t"<<" "<<st[sin_arr[i]]<<endl;}
}
void add_new_string(void)
{
int i,isempty,key,k;
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;
key=Rash_2(input_string);
if (ht1[key]==-1)
{
strcpy(st[isempty],input_string);
ht1[key]=isempty;
cout<<"Добавлен в st["<<isempty<<"] с ключом "<<key<<endl;
}
else //ht1[key]!=-1 ключ занят
{
ht2[key]=true;
// Поиск свободной ячейки (k) в sin_arr
for (i=0; i<Ns; i++)
{
if (sin_arr[i]==-1)
{
k=i;
break;
}
}//
sin_arr[k]=isempty;
strcpy(st[isempty],input_string);
cout<<"Синоним \""<<st[ht1[key]]<<"\". Добавлен в st["<<isempty<<"] \n"; //изменение только здесь!(23 мая)
}
}
}
bool line_search(char x[])
{
int i;
for (i=0; i<Ns; i++)
{
if (strcmp(x,st[sin_arr[i]])==0) {return true;}
}
return false;
}
void search(void)
{
char x[MaxStrLen];
int key;
system("clear");
cout<<"Введите строку"<<endl;
cin>>x;
key=Rash_2(x);
if (strcmp(st[ht1[key]],x)==0) {cout<<"Найден \n";}
else
{
if (ht2[key]==true)
{
if (line_search(x)==true) {cout<<"Найден в синонимах \n";}
else {cout<<"Не найден \n";}
}
else {cout<<"Не найден \n";}
}
}
bool remove_string(void)
{
char input_str[MaxStrLen];
int i,j,key;
system("clear");
cout<<"Введите строку"<<endl<<">";
cin>>input_str;
key=Rash_2(input_str);
if (strcmp(st[ht1[key]],input_str)==0)
{
strcpy(st[ht1[key]],"");
ht1[key]=-1;
cout<<"Удалён \n";
return 0;
}
else
{
if (ht2[key]==true)
{
for (i=0; i<Ns; i++)
{
if (strcmp(input_str,st[sin_arr[i]])==0)
{
//ht2[key]=false;
strcpy(st[sin_arr[i]],"");
sin_arr[i]=-1;
for (j=i; j<Ns; j++) {sin_arr[j]=sin_arr[j+1];}
cout<<"Удалён \n";
return 0;
}
}
}
else {cout<<"Не найден \n";}
}
return 1;
}
void menu_display(void)
{
system("clear");
cout<<"1 - Добавить"<<endl;
cout<<"2 - Удалить"<<endl;
cout<<"3 - Поиск"<<endl;
cout<<"4 - Вывод на экран хэш таблицы"<<endl;
cout<<"5 - Выход"<<endl;
}
void next(void)
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cin.clear();
cin.get();
}
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