Вывести табличную функцию ha sh (она не работает и программа вылетает)

Question

Я только начал узнавать о таблицах ha sh. Мне нужно написать программу, которая отображает и выводит список таблицы ha sh. Ключи представляют собой список слов из txt-файла, являющегося словарем.

Я написал код, но у меня появилась точка останова в главном файле, когда я вызываю функцию list для печати таблицы. Программа вылетает. Как это исправить? Функция list находится в файле функций.

Вот код, который я написал:

основной файл

#include <iostream>
#include <fstream>
#include <string>
#include "header.h"
using namespace std;

int main()
{
    elem* HT[M];
    initHT(HT);
    ifstream fs("dictionar_termeni_PC.txt");

    if (fs)
    {
        std::string text;

        while (!fs.eof())
        {
            fs >> text;
            char* S = new char[text.length() + 1];
            strcpy_s(S, text.length() + 1, text.c_str());
            insert(HT, S);
        }
        list(HT);
    }
}

файл функций

#include <iostream>
#include <string>
#include "header.h"
using namespace std;

int f(char* key)
{
    int i, suma;
    suma = 0;

    for (i = 0; i < strlen(key); i++)
    {
        suma = suma + *(key + i);
    }

    return suma%M;
}

void initHT(elem *HT[])
{
    for (int i = 0; i < M; i++)
    {
        HT[i] = nullptr;
    }
}

elem* find(elem *HT[], char* key)
{
    int h;
    elem* p;
    h = f(key);
    p = HT[h];

    while (p != 0)
    {
        if (strcmp(key, p->key) == 0)
            return p;
        p = p->leg;
    }

    return 0;
}

void insert(elem *HT[M], char* key)
{
    elem *p = new elem;
    p->key = new char[strlen(key) + 1];
    strcpy_s(p->key, strlen(p->key) + 1, key);
    int h = f(key);

    if (HT[h] == nullptr)
    {
        HT[h] = p;
        p->leg = nullptr;
    }
    else
    {
        elem* q = find(HT, key);

        if (q == nullptr)
        {
            p->leg = HT[h];
            HT[h] = p;
        }
    }
}

void list(elem* HT[])
{
    for (int i = 0; i<M; i++) {
        if (HT[i] != 0) {
            cout << "Hash code is " << i << endl;
            elem* p = HT[i];

            while (p != 0) {
                cout << p->key;
                p = p->leg;
            }
        }
    }
}

заголовочный файл

#ifndef HEADER_H_
#define HEADER_H_
#define M 10000
struct elem {
    char* key;
    elem* leg;
};


int f(char* key);
void initHT(elem *HT[]);
elem* find(elem *HT[], char* key);
void insert(elem *HT[M], char* key);
void list(elem* HT[]);
#endif

Answer 1

Я думаю, что это, возможно, связано с константой M, которую вы объявили, при каждом запуске вашей программы предполагается, что в вашем файле будет 10.000 строк.

void list(elem* HT[])
{
    elem* tmp;/*call it tmp or temp*/
    for (int i = 0; i < M/*use a parameter instead*/; i++) {
        if (HT[i] != 0 /*Use NULL instead*/) {
            cout << "\nHash code is " << i << ", key: ";
            tmp = HT[i];
            while (tmp != 0) {
                cout << tmp->key;
                tmp = tmp->leg;
            }
        }
    }
}

Что бы я сделал is:

#include <cstring>

struct elem {
    std::string key;
    std::string value;//because a hashtable has key-value pairs
    elem* next;
};

std::string поставляется со своими собственными функциями.

Если вы хотите просто изучить язык, вы можете использовать вместо него std::map и адаптировать его к вашим потребностям. Надеюсь, что это помогло.

Я предлагаю map из-за реализации Java, помните, что дизайн структуры данных зависит от вас, если вам нужна таблица, чтобы распределить ключ по карте использования значений, если нет, используйте set.

M. Гудрич Т., Р. Тамассия и М. Гольдвассер Х. Структуры данных и алгоритмы в Java. John Wiley & Sons, 2014. Они реализуют ключевые значения.