Добавил:
Hist
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Программы c++ (сортировка, хэширование) / 3 / old1 / lab_3.6.5_Sokolov
.cpp#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