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