Почему нет данных в хэш-таблице?

Question

[Retr0Hacker]

Задача:

Разработать программу для формирования и обработки хэш-таблицы, построенной по принципу открытой адресации (закрытое хеширование).
Практическую реализацию хэш-таблицы выполнить для набора структур, в которых ключом данных является
N-разрядный цифровой код (N >= 10).
Исследовать два метода зондирования: линейное и квадратичное.

Делаю сейчас сейчас вариант с линейным зондированием, но при попытке напечатать данные вылезает ошибка:


Пишет что в полях нет данных. Как решить проблему?

Код

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct inform {
	long key;
	const char* name;
} INFO;

typedef struct hash_table {
	int count;
	int size;
	INFO** array;
}HTAB;

INFO* New_Item(long key, const char* name)
{
	INFO* result = (INFO*)malloc(sizeof(INFO));

	result->key = key;
	result->name = name;

	return result;
}

void free_item(INFO* item)
{
	if (item != NULL) {
		free(item);
	}
}

HTAB* NewHTAB(int size)
{
	HTAB* result = (HTAB*)malloc(sizeof(HTAB));
	
	result->count = 0;
	result->size = size;

	result->array = (INFO**)malloc(sizeof(INFO*) * size);

	return result;
}

void free_hash_table(HTAB* table)
{
	if (table != NULL) {
		for (int i = 0; i < table->size; i++) {
			INFO* item = table->array[i];
			if (item != NULL) free_item(item);
		}
		free(table->array);
		free(table);
	}
}

int ht_hasItem(HTAB* table, int idx)
{
	return table->array[idx] != NULL;
}

int ht_IsFull(HTAB* table)
{
	return table->count == table->size;
}

int Hash_Code(long key, int size)
{
	return key % size;
}

int Insert(HTAB* table, long key, const char* name)
{
	int result = 0;

	if (ht_IsFull(table)) {

		printf("Hash table is FULL!!!");
	}
	else {
		INFO* item = New_Item(key, name);

		int idx = Hash_Code(key, table->size);

		while (ht_hasItem(table, idx))
			idx = Hash_Code(idx + 1, table->size);

		table->array[idx] = item;
		table->count++;
	}
	return result;
}

void Display(HTAB* table)
{
	for (int i = 0; i < table->size; i++) {
		if (ht_hasItem(table, i)) {

			INFO* item = table->array[i];
			printf("\t%d) %ld\t%s\n", i, item->key, item->name);
		}
		else {
			printf("%d) ---\n", i);
		}
	}
	printf("\n");
}

int Search(HTAB* table, long key)
{
	int result = -1;
	int idx = Hash_Code(key, table->size);

	while (ht_hasItem(table, idx)) {

		if (table->array[idx]->key == key)
		{
			result = idx;
			break;
		}
		else
		{
			idx = Hash_Code(idx + 1,table->size);
		}
	}
	return result;
}

INFO* Remove(HTAB* table, long key)
{
	INFO* result = NULL;
	
	int idx = Search(table, key);
	if (idx != -1) {

		result = table->array[idx];
		table->array[idx] = NULL;
		table->count--;
	}
	return result;
}

int main() {

	int itemIdx = -1;
	INFO* item = NULL;

	HTAB* table = NewHTAB(10);

	Display(table);

	Insert(table, 2345676201, "Jacob");
	Insert(table, 8723487236, "Elsa");
	Insert(table, 578478749854, "Dazai");
	Insert(table, 315834534523, "Lisa");
	Insert(table, 13243245345, "Demian");
	Insert(table, 430134434087, "Lucy");

	Display(table);

	printf("Search item 578478749854\n");
	itemIdx = Search(table, 578478749854);
	if (itemIdx != -1) {
		item = table->array[itemIdx];
		printf("item: (%ld, %s)\n", item->key, item->name);
	}
	else {
		printf("578478749854 not found\n");
	}

	printf("Remove item 578478749854\n");
	Remove(table, 578478749854);

	Display(table);

	free_hash_table(table);
	printf("End...");
	return 0;
}

Answer 1

[res2001]

malloc не зануляет выделенную память. После выделения mallocом в выделенной памяти содержится мусор.
А у тебя в ht_hasItem определение занят ли элемент идет через сравнение с NULL. Когда выделил array надо обнулить массив memsetом или использовать calloc для выделения.

Comments

[Retr0Hacker]

И еще один вопросик: В задании сказано что ключом является N-розрядный цифровой код(N >= 10). Я использовал тип данных unsigned long long чтобы выводились именно такие числа как мне надо. Но, есть проблемка с именами теперь:



Пока не использовал тип unsigned long long, имена выводились. А сейчас тупо NULL(

[res2001]

Retr0Hacker, Спецификатор формата для вывода в printf типа unsigned long long в винде %llu
Судя по тому, что значение key у вас то же выводится не верно, дело в этом.
https://docs.microsoft.com/ru-ru/cpp/c-runtime-lib...

Спецификаторы могут различаться в зависимости от компилятора. Поэтому в стандартной библиотеке есть заголовочный файл inttypes.h где заданы макросы с фиксированным именем описывающие формат для данного компилятора и платформы. Рекомендую использовать эти макросы, особенно для 64 битных целых, а так же типов с переменным (в зависимости от платформы) размером (size_t и его производных)

Answer 2

[mayton2019]

А зачем здесь две звездочки?

typedef struct hash_table {
  int count;
  int size;
  INFO** array;
}HTAB;

Мне кажется что 1 уровня вложенности достаточно (массив).