Хэширование строк c++

[pit2332]

Доброе время суток!

Пользователь вводит строку, она записывается в массив (если он не переполнен);
Вычисляется её хэш адрес по алгоритму свёртка 2;
Если этот адрес в хэш таблице занят, выполняется повторное хэширование простым числом;
Если и тут занято, то номер строки добавляется в массив для синонимов (для последующего линейного поиска)

Привожу исходный код

Код: (cpp) [Выделить]

#include <iostream>
#include <string.h>
#define N 20 //количество строк
#define MaxStrLen 10 //максимальная длина строки
#define Ns 8

using namespace std;

char st[N][MaxStrLen];
int ht[N], sin_arr[Ns];

void init_str(void)
{
    strcpy(st[0],"zero");
    strcpy(st[1],"one");
    strcpy(st[2],"two");
    strcpy(st[3],"three");
    strcpy(st[4],"four");
    strcpy(st[5],"five");
    strcpy(st[6],"six");
    strcpy(st[7],"seven");
    strcpy(st[8],"eight");
    strcpy(st[9],"nine");
    strcpy(st[10],"ten");
    strcpy(st[11],"eleven");
    strcpy(st[12],"twelve");
    strcpy(st[13],"thirteen");
    strcpy(st[14],"fourteen");
    strcpy(st[15],"fifteen");
    strcpy(st[16],"sixteen");
    strcpy(st[17],"seventeen");
    strcpy(st[18],"eighteen");
    strcpy(st[19],"nineteen");
   
    strcpy(st[13],"");
}

int hash_calc_sv2(char x[],const int size)
{
int StringLength,HashKey,i,tmp;
StringLength=strlen(x);
HashKey=0;
if (StringLength%2==0) //Чётный случай
{
for (i=0; i<StringLength; i=i+2)
{
tmp=x[i];
tmp=tmp*1000;
tmp=tmp+x[i+1];
HashKey=HashKey+tmp;
}
}
if (StringLength%2!=0) //Нечётный случай
{
for (i=1; i<StringLength; i=i+2)
{
tmp=x[i];
tmp=tmp*1000;
tmp=tmp+x[i+1];
HashKey=HashKey+tmp;
}
HashKey=HashKey+x[0];
}
return (HashKey);
}

int hash_calc(char x[],const int size)
{
int StringLength,HashKey,i;
StringLength=strlen(x);
HashKey=0;
for (i=0; i<=StringLength; i++)
{
HashKey=HashKey+x[i];
}
return (HashKey);
}

/*void init_hash_table(void)
{
int i,k,key;
for (i=0; i<N; i++)
{
ht[i]=-1;
sin_arr[i]=-1;
}
k=0;
for (i=0; i<N; i++)
{
if (strcmp(st[i],"")!=0)
{
key=hash_calc_sv2(st[i],MaxStrLen)%N;//Свёртка 2
//cout<<st[i]<<" "<<key<<endl;
if (ht[key]==-1)
{
ht[key]=i;
//cout<<key<<" "<<st[ht[key]]<<endl;
}
else
{
key=hash_calc(st[i],MaxStrLen)%19;//Простое число
if (ht[key]==-1)
{
ht[key]=i;
//cout<<key<<" "<<st[ht[key]]<<endl;
}
else
{
sin_arr[k]=i;
k++;
}
}
}
}
//for (i=0; i<k; i++) {cout<<sin_arr[i]<<endl;}
}*/

void ht_output(void)
{
int i;
cout<<"ключ - номер_строки - строка"<<endl<<endl;
for (i=0; i<N; i++)
{
if (ht[i]!=-1) {cout<<" "<<i<<"      "<<ht[i]<<"\t"<<"      "<<st[ht[i]]<<endl;}
else {cout<<" "<<i<<"\t"<<"<empty>"<<endl;}
}
cout<<endl<<endl<<endl<<"********Синонимы********"<<endl<<endl;
cout<<"номер_строки - строка"<<endl<<endl;
for (i=0; i<Ns && sin_arr[i]!=-1; i++)
{
cout<<"      "<<i<<"\t"<<"       "<<st[sin_arr[i]]<<endl;
}
}

void add_to_ht(int m)
{
int key,i,k=-1;
key=hash_calc_sv2(st[m],MaxStrLen)%N;//свёртка 2
if (ht[key]==-1)
{
ht[key]=m;
//cout<<"(1)"<<endl;
}
else
{
key=hash_calc(st[m],MaxStrLen)%19; //простое число
if (ht[key]==-1)
{
ht[key]=m;
//cout<<"(2)"<<endl;
}
else
{
for (i=0; i<Ns; i++)
{
if  (sin_arr[i]==-1)
{
k=i;
break;
}
}// k=sizeof(sin_arr)
sin_arr[k]=m;
}
}
}

void add_new_string(void)
{
int i,isempty;
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>>st[isempty];
cout<<"добавлено в st["<<isempty<<"]"<<endl;
}
add_to_ht(isempty);
}

int main(void)
{
//init_str();
//init_hash_table();
add_new_string();
add_new_string();
add_new_string();
add_new_string();
ht_output();
return 0;
}

Проблема в том, что хэш таблица заполняется одними нулями. Почему, никак не пойму.

Процедуры вычисления хэш ключа отлажены, с них проблема маловероятна. Если использовать инициализацию не через построчное дополнение, а сразу (процедура init_str) и заполнить хэш таблицу процедурой init_hash_table, то всё работает. Проблема, скорее всего, именно в процедуре add_to_ht, запускаемой из процедуры add_new_string.

[mkarasik]

Массивы

Код: [Выделить]

int ht[N], sin_arr[Ns]; по коду должны содержать -1, никто и нигде их не инициализирует. Функция добавления не находит 'свободное' место и пишет хер знает куда. В хэш таблице остаются нули.
А, вообще, ставишь cout в каждую строку функции добавления и сам все поймешь.

Ну и не в тему. Почему все масивы глобальные, а индех строки локальный с оригинальным поиском свободной в начале add_new_string. Или все наверх, или все параметрами передавай. А то совсем криво как то. Вернее оно и так криво, а так еще кривее .