Как я определю, что определенный индекс в моей таблице ha sh еще не имеет значения? - PullRequest
Новая
       61

Как я определю, что определенный индекс в моей таблице ha sh еще не имеет значения?

0 голосов
/ 12 апреля 2020

Я пытаюсь создать программу, которая читает файл, который заполнен словами в словаре, затем сохраняет каждое слово в таблице ha sh, у меня уже есть функция ha sh, например, ha sh функция возвращает индекс 123 как я могу определить, имеет ли этот индекс еще значение, иначе, если определенный индекс имеет значение, я должен просто сделать слово новым заголовком списка или добавить это до конца списка? Должен ли я сначала инициализировать весь массив чем-то вроде «NULL», потому что если переменная не была инициализирована, она содержит значение мусора, то же самое работает с массивами из структуры .. 

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
//                  N = 2 ^ 13
const unsigned int N = 8192;


// Hash table
node *table[N];

Это часть моего кода ДЛИНА здесь определена выше со значением 45 ..

1 Ответ

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

как я могу определить, имеет ли этот индекс еще значение

"Слоты" в вашей таблице являются связанными списками. table хранит указатели на заголовочные узлы этих связанных списков. Если этот указатель равен NULL, список пуст, но вам не нужно делать его особым случаем: когда вы ищите слово, просто пролистайте список, пока указатель на следующий узел не равен нулю. Если указатель на головной узел нулевой, ваша прогулка рано останавливается, вот и все.

если я просто сделаю слово новым заголовком списка или добавлю его в конец список?

Это не должно иметь значения. Отдельные списки в узлах должны быть короткими. Идея таблицы ha sh состоит в том, чтобы превратить линейный поиск по всем W словам в более быстрый линейный поиск в среднем по W/N словам. Если вы видите, что в вашей таблице только несколько длинных списков, ваша функция ha sh не годится.

Вы должны пройти по списку один раз, чтобы убедиться, что вы не вставляете дубликаты, так что вы можете вставить в конце. Или вы можете попытаться сохранить каждый связанный список в алфавитном порядке. Выберите один метод и придерживайтесь его.

Должен ли я сначала инициализировать весь массив чем-то вроде "NULL", потому что если переменная не была инициализирована, она содержит значение мусора, то же самое работает с массивами из структуры.

Да, пожалуйста, инициализируйте ваш массив указателей головных узлов на NULL, чтобы таблица ha sh находилась в определенном состоянии. (Если ваш массив находится в области видимости файла или static, таблица должна быть уже инициализирована с нулевыми указателями, но это не помешает сделать инициализацию явной.)

...