Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
33
Добавлен:
10.05.2014
Размер:
3.92 Кб
Скачать
#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_result(char input_str[])
{
	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;
}

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

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

void search(void)
{
	
}

void remove_string(void)
{
	
}

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