Скачиваний:
33
Добавлен:
10.05.2014
Размер:
4.81 Кб
Скачать
#include <iostream>
#include <string.h>
#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[],const int size)
{
	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[],const int size)
{
	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;
	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],MaxStrLen)%N;//Свёртка 2
			//cout<<st[i]<<" "<<key<<endl;
			if (ht[key]==-1)
			{
				ht[key]=i;
				//cout<<key<<" "<<st[ht[key]]<<endl;
			}
			else
			{
				key=hash_calc(st[i],MaxStrLen)%19;//Простое число
				if (ht[key]==-1)
				{
					ht[key]=i;
					//cout<<key<<" "<<st[ht[key]]<<endl;
				}
				else
				{
					sin_arr[k]=i;
					k++;
				}
			}
		}
	}
	//for (i=0; i<k; i++) {cout<<sin_arr[i]<<endl;}
}

void ht_output(void)
{
	int i;
	cout<<"ключ - номер_строки - строка"<<endl<<endl;
	for (i=0; i<N; i++) 
	{
		if (ht[i]!=-1) {cout<<" "<<i<<"      "<<ht[i]<<"\t"<<"      "<<st[ht[i]]<<endl;}
		else {cout<<" "<<i<<"\t"<<"<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],MaxStrLen)%N;//свёртка 2
	if (ht[key]==-1)
	{
		ht[key]=m;
		//cout<<"(1)"<<endl;
	}
	else
	{
		key=hash_calc(st[m],MaxStrLen)%19; //простое число
		if (ht[key]==-1)
		{
			ht[key]=m;
			//cout<<"(2)"<<endl;
		}
		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,IntNum=0;
	key=hash_calc_sv2(input_str,strlen(input_str))%N;//Свёртка 2
	cout<<"hashkey (свёртка 2) = "<<key<<endl;
	if (strcmp(input_str,st[ht[key]])==0)
	{
		IntNum=1;
	}
	else
	{
		key=hash_calc(input_str,strlen(input_str))%19; //Простое число
		cout<<"hashkey (простое число) = "<<key<<endl;
		if (strcmp(input_str,st[ht[key]])==0)
		{
			IntNum=2;
		}
		else //Линейный поиск
		{
			for (i=0; i<Ns; i++)
			{
				if (strcmp(input_str,st[sin_arr[i]])==0)
				{
					cout<<"линейный поиск "<<i+1<<" интерация"<<endl;
					IntNum=i+3;
					break;
				}
			}
		}
	}
	return IntNum;
}

void add_new_string(void)
{
	int i,isempty;
	char input_string[MaxStrLen];
	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;
	cout<<"Введите строку"<<endl;
	cin>>x;
	l=search_result(x);
	if (l==0) {cout<<"not found"<<endl;}
	else {cout<<"found ("<<l<<")"<<endl;}
}

int main(void)
{
	int i;
	for (i=0; i<N; i++)
	{
		ht[i]=-1;
		sin_arr[i]=-1;
	}
	init_str();
	init_hash_table();
	add_new_string();
	//search();
	ht_output();
	return 0;
}
Соседние файлы в папке old1