1

I have to make a program with a hash table that maps single random characters into the table. The program kind of works but sometimes it crashes, also it doesn't map every element. Some of them just won't get inside the table and there are always spare spaces in the table. I don't know what to do to solve these 2 problems. I used 3 versions of open adressing and each of them causes the same 2 problems. Sorry for my bad English. Thank you in advance.

Edited. Of course, I forgot about dynamic allocation. But the problem isn't solved.

#include <time.h>
#include <string>
#include <cstdlib>

using namespace std;

int Liniowo(int i, int proby, int rozmiar) // (open adressing, Linear probing)
{
    if(i+proby<rozmiar)
        return i+proby;
    else
    {
        return -1;
    }
}

int Kwadratowo(int i, int proby, int rozmiar) // (open adressing, Quadratic probing)
{
    if (i+proby*proby<rozmiar)
        return i+proby*proby;
    else
    {
        return -1;
    }
}

int Podwojnie(int i, int proby, int rozmiar, char klucz) // (open adressing, Double hashing)
{
    if (i*(klucz*(701%klucz)-klucz%13)<rozmiar&&i*(klucz*(701%klucz)-klucz%13)>0)
        return i*(klucz*(701%klucz)-klucz%13);
    else
    {
        return -1;
    }
}

int modularnie(char c,int rozmiar) // modular
{
    return c%rozmiar;
}

void dodaj(char *tab,int max, char c) // add an element
{
    int i=modularnie(c, max);
    if (tab[i]== '\0')
        tab[i]=c;
    else
    {
        int u=0;
        int h;
        while (tab[i]!= '\0'&&h!=-1)
        {
            u++;
//            h=Kwadratowo(i, u, max);
            h=Podwojnie(i,u,max,c);
        }
        if (h!=-1)
            tab[h]=c;
        else
            cout << "no niestety, nie udalo sie wstawic " <<endl; //"I couldn't map the element"
    }
}

int wyszukaj(char *tab,int max, char c) // search an element
{
    int i=modularnie(c, max);
    int j=i;

    if (tab[i]== '\0')
        return -1;

    while (tab[i]==c)
    {
        i=(i+1)%max;
        if((i==j)||(tab[i]== '\0'))
            return -1;
    }
    return i;
}

int usun(char *tab,int max, char c) // remove an element
{
    int r,j,i=wyszukaj(tab,max,c);
    j=i;

    if (i==-1)
        return -1;

    tab[i]= '\0';

    while (tab[(++i)%max]!= '\0')
    {
        i%=max;
        r=modularnie(tab[i],max);
        if (((i<r)&&(r<=j)) || ((r<=j)&&(j<i)) || ((j<i)&&(i<r)))
        {
            tab[j]=tab[i];
            tab[i]= '\0';
            j=i;
            continue;
        }
    }
    return 0;
}

int main()
{
    srand( time( NULL ) );
    int ile;
    cout << "podaj wielkosc tablicy: "; //"Type the size of the table"
    cin >> ile;
    char* tab; // EDITED
    tab=new char(ile);

    for (int n=0; n<ile; n++)
    {
        tab[n]= '\0';
    }

    char e;

    for (int i=0; i<ile; i++)
    {
        e='!'+rand()%127;
        dodaj(tab, ile, e);
    }

    for(int j=0; j<ile; j++)
    {
        cout << j << ", " << tab[j] << endl;
    }
    return 0;
}

  • 2
    Welcome to Stack Overflow! It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) – NathanOliver Apr 07 '20 at 14:26
  • 3
    `char tab[ile];` -- This is not valid C++, as arrays must have their sizes denoted by a constant. Instead use `std::vector table(ile);`. Second, you should be [debugging](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) your code. – PaulMcKenzie Apr 07 '20 at 14:26
  • 1
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5910058) – Jesper Juhl Apr 07 '20 at 14:41

0 Answers0