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

using namespace std;
int  nmax, n1, n2, j, i, tmp, tmp1, menu, cmp, cmp1, n, nac, ht1, k, n3, tmp2, HashKey;
char inp_str[7];
int ac[40];
int ht[40];
int num[40];
char str[40][7];
char Hash[40][7];

void Sin(int HashKey)
{
	if(ac[HashKey]==-1 || strcmp(Hash[ac[HashKey]],"delete")==0 ) //  (||-or)
	{
		nac=HashKey;
		if (strcmp(Hash[ac[HashKey]],"delete")==0) {strcpy(Hash[ac[HashKey]],str[n2]);}
		else
		{
			ac[HashKey]=n1;
			strcpy(Hash[n1],str[n2]);
		}
	}
	else {Sin(ac[HashKey]);}
}


void Output(void)
{
	int i;
	system("cls");
	for(i=0; i<40; i++) /////!!!!!!!!!!
	{
		if(i<=9)
		{cout<<i<<" ";}
		else {cout<<i;}
		cout<<"   ";
		for(k=0; k<7 && str[i][k]>0; k++);
		cout<<str[i];
		for(j=1; j<7-k; j++) {cout<<" ";}
		cout<<"   ";
		if(ht[i]<=9 && ht[i]>=0) {cout<<" "<<ht[i];}
		else {cout<<ht[i];}
		cout<<"   ";
		for(k=0; k<7 && Hash[i][k]>0; k++);
		cout<<Hash[i];
		for(j=1; j<7-k; j++) {cout<<" ";}
		cout<<"   ";
		if(ac[i]<=9 && ac[i]>=0) {cout<<" "<<ac[i];}
		else {cout<<ac[i];}
		cout<<"\n";
	}
	cout<<"\n";
	cout<<"------------------"<<"\n";
}

int mult(char x[]) //вычисление хэш ключа
{
	int i,l;
	unsigned long tmp1,tmp2;
	float tmp;
	l=strlen(x);
	//tmp=pow(1000,l);
	tmp=0;
	for (i=0; i<l; i++)
	{
		tmp=tmp+x[i]*pow(1000,i);
		//cout<<tmp<<" "<<str[i]<<endl;;
	}
	tmp=tmp*tmp;
	//cout<<endl<<tmp<<endl;
	tmp1=(tmp/pow(1000,l));
	tmp1=tmp1%10;
	tmp2=tmp1*10;
	//cout<<tmp1<<endl;
	tmp1=(tmp/pow(1000,l)/10);
	tmp1=tmp1%10;
	tmp2=tmp2+tmp1;
	//cout<<tmp1<<endl;
	//cout<<tmp2<<endl;
	tmp2=tmp2%20;
	//cout<<tmp2<<endl;
	return tmp2;
}

void hash_calc(void)
{
	tmp=0;
	for(i=0; i<7 && str[n2][i]!='0'; i++)
	{
		tmp1=str[n2][i];
		tmp=tmp+tmp1;
	}
	HashKey=tmp%19;
	ht[n2]=HashKey;
	while (HashKey>nmax-1)
	{
		HashKey=HashKey%19;
		ht[n2]=HashKey;

	}
	//HashKey=mult(str[n2]);
	if(strcmp(Hash[HashKey],"empty")==0 )
	{
		nac=HashKey;
		strcpy(Hash[HashKey],str[n2]);
	}
	else
	{
		cmp=-1;
		cmp1=-1;
		for(i=20; i<=40 && cmp!=0 ; i++ ) {cmp=strcmp(Hash[i],"empty");}
		n1=i-1;
		Sin(HashKey);
	}
	//cout<<"!!!\n";
	
}

void Find(int n)
{
	if (strcmp(Hash[n],inp_str)==0) {nac=n;}
		else
		{
			ht1=n;
			Find(ac[n]);
		}
}

void RemoveCh(int x)
{
	if (ac[x]!=-1 )
		{
			num[0]=n3;
			num[j]=ac[x];
			j=j+1;
			RemoveCh(ac[x]);
		}
	else
		{
			tmp2=j-1;
			for (k=j-1; k>=0 && cmp==0; k--)
			{
				//cout<<"k="<<k<<"  "<<num[k]<<"\n";
				cmp=strcmp(Hash[num[k]],"delete");
				if (cmp==0)
				{tmp2=tmp2-1;}
			}
					//cout<<"h="<<tmp2<<"\n";
			for (i=j-1; i>tmp2; i--)
			{
				//cout<<"i="<<i<<"  "<<num[i]<<"\n";
				//cout<<num[i]<<"\n";
				//if (strcmp(Hash[num[i]],"empty")==0)
				//{
					ac[num[i-1]]=-1;
					strcpy(Hash[num[i]],"empty");
				//}
			}
			//for (i=j; i>tmp2; i--)
			//{
			//	strcpy(Hash[num[i+1]],"empty");
			//}
		}
	}

void remove_find(int n)
{
	if (strcmp(Hash[n],inp_str)==0)
		{
			strcpy(Hash[n],"delete");
			nac=n;
			RemoveCh(n3);

		}
		else
		{
			ht1=n;
			nac=n;
			remove_find(ac[n]);
		}
}

void Remove(void)
{
	system("cls");
	cout<<"Enter the key \n";
	cin>>inp_str;
	cmp=-1;
	for(i=0; i<nmax-1 && cmp!=0; i++ )
	{
		cmp=strcmp(str[i],inp_str);
	}
	if (cmp!=0) {cout<<"Key not found\n";}
	else
	{
		strcpy(str[i-1],"empty");
		n=ht[i-1];
		n3=ht[i-1];
		ht[i-1]=-1;
		j=1;
		remove_find(n);
		cout<<inp_str<<" removed\n";
	}
}

void Add(void)
{
	system("cls");
	cmp=-1;
	for(i=0; i<=40 && cmp!=0; i++ ) //проверка на заполненность таблицы (1)
	{cmp=strcmp(str[i],"empty");}
	n2=i-1;
	if(n2>nmax-1)
	{
		cout<<"The table is full \n";
	} //конец проверки (1)
	else
	{
		cout << "Enter the key \n";
		cin>>inp_str;
		cmp=-1;
		for(i=0; i<nmax-1 && cmp!=0; i++ ) //проверка на наличие ключа в таблице (2)
		{
			cmp=strcmp(str[i],inp_str);
		}
		if (cmp==0)
		{
			cout << "Key is already entered \n";
		} //конец проверки (2)
		else
		{
			strcpy(str[n2],inp_str);
			hash_calc();
			cout<<"Added with key="<<ht[n2]<<" and ac="<<ac[nac]<<endl;
		}
	}
}

void Search(void)
{
	system("cls");
	cout << "Enter the key";
	cin>>inp_str;
	cmp=-1;
	for(i=0; i<nmax-1 && cmp!=0; i++ )
	{
		cmp=strcmp(str[i],inp_str);
	};
	if (cmp!=0) {cout << "Key not found \n";}
	else
	{
		n=ht[i-1];
		Find(n);
		cout<<Hash[nac]<<"   "<<nac<<"\n";
	}
	cout<<"-----"<<"\n";
}

void next(void)
{
	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.clear();
	cin.get();
}

int main(void)
{
	menu=0;
	nmax=20;
	n2=-1;
	n1=nmax-1;
	for(i=0; i<40; i++)
	{
		strcpy(Hash[i],"empty"); 
		ac[i]=-1;
		ht[i]=-1;
		strcpy(str[i],"empty");
	};
	while(menu<5)
	{
		cout<<"1-Add\n";
		cout<<"2-Remove\n";
		cout<<"3-Find\n";
		cout<<"4-OutPut\n";
		cout<<"5-Exit\n";
		cin>>menu;
		switch(menu)
		{
			case 1: {Add(); next(); system("cls"); break;}
			case 2: {Remove(); next(); system("cls"); break;}
			case 3: {Search(); next(); system("cls"); break;}
			case 4: {Output(); next(); system("cls"); break;}
			case 5: {return 0;}
		}
	}
	return 0;
}
Соседние файлы в папке 3