Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
33
Добавлен:
10.05.2014
Размер:
5.25 Кб
Скачать
#include <iostream>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <limits>

#define n 20
#define MaxStrLen 7
#define Ns 8
#define N 28

using namespace std;

char st[N][MaxStrLen];
int ht[N], ac[N];

void clear_ht(void)
{
	int i;
	for (i=0; i<N; i++)
	{
		ht[i]=-1;
		ac[i]=-1;
		//strcpy(st[i],"aaaSSS");
	}
}

void ht_output(void)
{
	int i;
	system("clear");
	cout<<"N_строки \t Строка \t Ключ \t Адрес_связи \n";
	for (i=0; i<n; i++) {cout<<setw(5)<<i<<setw(18)<<st[i]<<setw(13)<<ht[i]<<setw(10)<<ac[i]<<endl;}
	cout<<"------------------------------------------------------- \n";
	for (i=n; i<N; i++) {cout<<setw(5)<<i<<setw(18)<<st[i]<<setw(13)<<ht[i]<<setw(10)<<ac[i]<<endl;}
}

int mult_hash(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;
}

int search_key(int HashKey)
//N_строки
{
	int i;
	for (i=0; i<n; i++)
	{
		if (ht[i]==HashKey) {return i;}
	}
	return -1;
}

int search_result(char x[])
{
	//0 - не найдено
	//найдено - количество интераций
	int key,res;
	key=mult_hash(x);
	res=search_key(key); //номер строки
	if (res==-1) {return 0;}
	if (strcmp(st[res],x)==0) {return 1;}
	if (ac[res]==-1) {return 0;}
	if (strcmp(st[ac[res]],x)==0) {return 2;}
	//cout<<"ac[ac[res]]="<<ac[ac[ac[res]]]<<endl;
	if (strcmp(st[ac[ac[ac[res]]]],x)==0) {return 3;}
	return 0;
}

int empty_sin(int k)
//всё занято (-1)
//return (20..27)
{
	int i;
	for (i=k; i<N; i++)	
	{
		if (ht[i]==-1) {return i;}
	}
	return -1;
}

void add_new_string(void)
{
	int isempty,i,key,s,u,m,w,x,y;
	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)
		{
			cout<<"Строка уже содержится в массивe \n";
			return;
		}
		key=mult_hash(input_string);
		cout<<"Хэш ключ "<<key<<endl;
		//поиск ключа в хэш таблице
		m=search_key(key);
		if (m==-1) //ключ свободен
		{
			ht[isempty]=key;
			strcpy(st[isempty],input_string);
			cout<<"Хэш ключ "<<key<<" свободен, строка записано в st["<<isempty<<"] \n";
		}
		else //кюч занят
		{
			cout<<"Хэш ключ "<<key<<" занят \n";
			if (ac[m]==-1) //свободен
			{
				cout<<"Адрес связи ac["<<m<<"] свободен \n";
				s=empty_sin(n); //поиск св.пер. в переполн. (1)
				ac[m]=s;
				ht[s]=key;
				strcpy(st[s],input_string);
				cout<<"Строка записана в st["<<s<<"] \nАдрес связи ac["<<m<<"]="<<s<<endl;
			}
			else //не свободен
			{
				cout<<"Адрес связи ac["<<m<<"] занят \n";
				u=ac[m];
				cout<<"Адрес связи ac["<<m<<"]="<<u<<endl;
				if (ac[u]==-1)
				{
					cout<<"Адрес связи ac["<<u<<"] свободен \n";
					w=empty_sin(n+1); //(2)
					ac[u]=w;
					ht[w]=key;
					strcpy(st[w],input_string);
				}
				else
				{
					x=ac[u];
					if (ac[x]==-1)
					{
						y=empty_sin(n+2); //(3)
						ac[x]=y;
						strcpy(st[y],input_string);
						ht[y]=key;
					}
					//\\//
				}
			}
		}
	}
}

void search(void)
{
	char input_string[MaxStrLen];
	int l;
	system("clear");
	cout<<"Введите строку \n";
	cin>>input_string;
	l=search_result(input_string);
	if (l==0) {cout<<"Не найден \n";}
	else {cout<<"Найден с "<<l<<" интерации \n";}
}

void remove_string(void)
{
	int key,res;
	char input_string[MaxStrLen];
	system("clear");
	cout<<"Введите строку"<<endl<<">";
	cin>>input_string;
	key=mult_hash(input_string);
	res=search_key(key); //номер строки
	if (res==-1)
	{
		cout<<"Строка не найдена \n";
		return;
	}
	if (strcmp(st[res],input_string)==0)
	{
		strcpy(st[res],"");
		ht[res]=-1;
		cout<<"Удалён \n";
		if (ac[res]!=-1)
		{
			//cout<<"Адрес связи не пуст \n";
			strcpy(st[res],st[ac[res]]);
			ht[res]=ht[ac[res]];
			strcpy(st[ac[res]],"");
			ht[ac[res]]=-1;
			ac[res]=-1;
			cout<<"Удалён \n";
		}
	}
	
}

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;}
		}
	}
}
Соседние файлы в папке old1