Попытка создания таблицы ha sh, не может отобразить все ключи, также происходит сбой программы - PullRequest
Новая
       6

Попытка создания таблицы ha sh, не может отобразить все ключи, также происходит сбой программы

1 голос
/ 07 апреля 2020

Мне нужно создать программу с таблицей ha sh, которая отображает в таблицу отдельные случайные символы. Программа работает, но иногда дает сбой, и не отображает каждый элемент. Некоторые из них просто не попадут внутрь стола, и в нем всегда есть свободные места. Я не знаю, что делать, чтобы решить эти 2 проблемы. Я использовал 3 версии открытого адреса, и каждая из них вызывает те же 2 проблемы. Извините за мой плохой Энгли sh. Заранее спасибо.

Отредактировано. Конечно, я забыл о динамическом распределении c. Но проблема не решена. 

#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;
}
...