Программы c++ (сортировка, хэширование) / 3 / lab_3.6.2_B

#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("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();
}

void clear_ht(void)
{
	int i;
	system("clear");
	for (i=0; i<N; i++)
	{
		ht[i]=-1;
		strcpy(st[i],"");
	}
	for (i=0; i<Ns; i++)
	{
		sin_arr[i]=-1;
	}
	cout<<"Хэш таблица очищена"<<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)
{
	//Добавлено с ращеплением 2, return hashkey [0..19]
	//Добавлено в синонимы, return (-соотв_ключ_хэш_табл-2) [-2..-21]
	int i,key,isempty_sa,isempty_ht;
	key=Rash_1(st[m]);
	if (ht[key]==-1) //Ключ свободен
	{
		ht[key]=m;
		return key;
	}
	//Добавление в синонимы
	//Поиск свободной ячейки sin_arr
	isempty_sa=-1;
	for (i=0; i<Ns; i++)
	{
		if (sin_arr[i]==-1)
		{
			isempty_sa=i;
			break;
		}
	}
	//Поиск сверху свободного элемента ht
	for (i=0; i<N; i++)
	{
		if (ht[i]==-1)
		{
			isempty_ht=i;
			break;
		}
	}
	// Запись в sin_arr номера свободной ячейки хэш таблицы, а в хэш таблицу номера строки
	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("clear");
	cout<<"Введите строку для поиска \n";
	cin>>inp_str;
	key=Rash_1(inp_str);
	if (strcmp(st[ht[key]],inp_str)==0)
	{
		result=true;
		cout<<"Найден с ключом "<<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<<"Найден в синонимах \n";
				break;
			}
		}
	}
	if (result==false) {cout<<"Не найден \n";}
}

void add_new_string(void)
{
	int i,isempty,result;
	char inp_str[MaxStrLen];
	system("clear");
	//Проверка заполненности таблицы строк и возвращение номера пустой строки.
	isempty=-1;
	for (i=0; i<N; i++)
	{
		if (strcmp(st[i],"")==0)
		{
			isempty=i;
			break;
		}
	}
	if (isempty==-1) {cout<<"Таблица строк переполнена \n";}
	else //Ввод строки, проверка на её налчие в массиве
	{
		cout<<"Введите строку \n";
		cin>>inp_str;
		//cout<<search_result(inp_str)<<endl;
		//if (search_result(inp_str)!=-1) {cout<<"Строка уже содержится в массиве строк \n";}
		//else //добавление в массив строк и хэш таблицу
		{
			strcpy(st[isempty],inp_str); //запись строки в массив строк
			result=add_to_ht(isempty);
			if (result>-1) {cout<<"Добавлен с ключом "<<result<<endl;}
			if (result<-1) {cout<<"Синоним. Добавлен в хэш таблицу с ключом "<<-result-2<<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<<setw(6)<<sin_arr[i]<<endl;}
}

bool remove_string(void)
{
	char inp_str[MaxStrLen];
	int i,j,key;
	system("clear");
	cout<<"Введите строку"<<endl<<">";
	cin>>inp_str;
	key=Rash_1(inp_str);
	if (strcmp(st[ht[key]],inp_str)==0)
	{
		cout<<"Найден с ключом "<<key<<", удалён \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<<"Найден в синонимах, удалён \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<<"Не найден \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;}
		}
	}
}