Скачиваний:
34
Добавлен:
10.05.2014
Размер:
6.4 Кб
Скачать
/*
 Гуров Егор
 А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], outf[128];
int ht[N], sin_arr[Ns];

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,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 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 init_hash_table(void)
{
	int i,k,key;
	system("clear");
	clear_ht();
	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;}
}

int 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;
		return key;
	}
	else
	{
		key=hash_calc(st[m])%19; //простое число
		if (ht[key]==-1) 
		{
			ht[key]=m;
			return key;
		}
		else
		{
			for (i=0; i<Ns; i++)
			{
				if  (sin_arr[i]==-1)
				{
					k=i;
					break;
				}
			}// k=sizeof(sin_arr)
			sin_arr[k]=m;
			return -1;
		}
	}
	return -2;
}

int search_result(char input_str[])
{
	int i,key;
	//system("echo function search_result called>>3.6.2.log");
	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,result;
	char input_string[MaxStrLen];
	system("clear");
	//system("echo function add_new_string called>>3.6.2.log");
	isempty=-1;
	for (i=0; i<N; i++)
	{
		if (strcmp(st[i],"")==0)
		{
			isempty=i;
			break;
		}
	}
	if (isempty==-1) 
	{
		cout<<"Таблица переполнена"<<endl;
		//system("echo error Таблица переполнена>>3.6.2.log");
	}
	else
	{
		cout<<"Введите строку"<<endl<<">";
		cin>>input_string;
		if (search_result(input_string)==0)
		{
			strcpy(st[isempty],input_string);
			result=add_to_ht(isempty);
			if (result==-1) {cout<<"Добавлен в st["<<isempty<<"]"<<" в массив синонимов"<<endl;}
			if (result==-2) {cout<<"Не добавлен. Неизвестная ошибка."<<endl;}
			if (result>=0) {cout<<"Добавлен в st["<<isempty<<"]"<<" с ключом "<<result<<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<<"Не найден"<<endl;}
	else {cout<<"Найден с ("<<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;
		cout<<"Удалён"<<endl;
	}
	else
	{
		key=hash_calc(input_str)%19; //Простое число
		if (strcmp(input_str,st[ht[key]])==0)
		{
			strcpy(st[ht[key]],"");
			ht[key]=-1;
			cout<<"Удалён"<<endl;
		}
		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<<"Не найден"<<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();
	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;}
		}
	}
}
Соседние файлы в папке 3