Блог

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

Сначала я подумал, что передаю неправильное значение функции printhashtable() но это не так, поскольку она печатает все правильные элементы, но в обратном порядке. Если бы, например, я передал последний элемент списка с условием i!= NULL , я бы получил пустую печать.

Что я думаю сейчас, так это то, что я каким-то образом даю конечный указатель, и поле ‘next’ на самом деле идет в обратном направлении.

     #include <stdio.h>
#include <stdlib.h>

int a;
int b;
int count_collisions;

// Linked list
typedef struct _list{
    int value;
    struct _list *next;
} list;


// Hash Table Structure
typedef struct _hash_t {
    int size; // Table Size
    list** table; // Table elements
} hash_t;


// Creating the HASH function
int hash(int x, int a, int b, int len) {
int h;
h=((((a*x) b)%999149)%len);
return h;
}


// Creating the table
hash_t* CreateTable(int size) {

hash_t* newtab;

if (size < 1) return NULL; // This size is not valid

newtab = malloc(sizeof(hash_t));  // ALlocate memory for the table structure
if (newtab == NULL) return NULL; // Checking if the malloc went good

newtab->table = malloc(sizeof(list*)*size); // Allocating memory for the table
if (newtab->table == NULL) return NULL; // Checking if the malloc went good

int i;
for (i=0; i<size; i  ) {
    newtab->table[i] = NULL; // Initialize the elements of the table
}

newtab->size = size; // Setting the size of the table

return newtab;
}


// Searching for a value
list* Search(int x, hash_t* hashtable) {

list* list;
int hashval = hash(x, a, b, hashtable->size);

if (hashtable == NULL) {
    return NULL;
}

for (list = hashtable->table[hashval]; // We start from the correct list, using the hash function
     list != NULL; list = list->next) {
    if (list->value == x) {
        return list;
    }
}

return NULL;
}


 // Insert a value
void Insert(int x, hash_t* hashtable) {

list* list;
int hashval = hash(x, a, b, hashtable->size);

list = malloc(sizeof(list)); // Allocate memory for the list
list->value = x;
list->next = hashtable->table[hashval];
hashtable->table[hashval] = list;

}


// Function that prints a list
void printList (list* list) {
struct _list* i;
for (i=list; i!= NULL; i = i->next) {
    printf("%d ", i->value);
}
}



// Function that prints hashtable
void printHashTable(hash_t* hashtable, int size) {
int i;
for (i=0; i<size; i  ) {
    printf("nPosition: %d | list: ", i);
    printList(hashtable->table[i]);
}

}



int main () {

int size;
scanf("%d", amp;size);
scanf("%d", amp;a);
scanf("%d", amp;b);

hash_t* table = CreateTable(size);
int i, x;
for (i=0; i<size; i  ) {
    scanf("%d", amp;x);
    Insert(x, table);
}

printf("Hash Table created is: ");
printHashTable(table, size);

printf("n");


return 0;
}
  

Пример тестового набора:

Ввод:

 5    // 5 elements
2    // a = 2
4    // b = 4
3    // h(3) = 0
12   // h(12) = 8
97   // h(97) = 8
18   // h(18) = 0
98   // h(98) = 0
  

Вывод:

 // hash table:
//  0 -> 3 18 98
// 1 -> NULL
// 2 -> NULL
// 3 -> NULL
// 4 -> NULL
// 5 -> NULL
// 6 -> NULL
// 7 -> NULL
// 8 -> 12 97
// 9 -> NULL
  

Что я получаю при 0 и 8, так это:

 0 -> 98 18 3
8 -> 97 12
  

Что может быть не так?
Заранее спасибо
P.S. Извините за мой плохой английский

Редактировать: Я думаю, что, возможно, в функции Insert я не разделяю случаи, в которых список пуст или нет. Я прав?

Из вашей функции insert:

 list->value = x;
list->next = hashtable->table[hashval];
hashtable->table[hashval] = list;
  

вы назначаете list-> next в качестве текущего списка, а затем назначаете запись хэш-таблицы в качестве вашего вновь созданного списка. Это вставка в начале.

Ваш список построен следующим образом (отображается только таблица [0]):

 0 -> 3
0 -> 18 3
0 -> 98 18 3