插入哈希表

Question

我正試圖在哈希表中插入一個整數。要做到這一點，我創建了一個節點*的數組，我試圖讓像listarray[i]->data=5這樣的分配成爲可能。不過，我仍然對指針感到困惑，而且我在評論'//這裏崩潰'時就崩潰了，我不明白爲什麼。我在main（）中的初始化是否無效？

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

    typedef struct node 
     { 
     int data; 
     struct node * next; 
     } node; 

    //------------------------------------------------------------------------------ 
    void insert (node **listarray, int size) 
    { 

    node *temp; 
    int value = 11; //just some random value for now, eventually will be scanned in 
    int index = value % size; // 11 modulo 8 yields 3 

    printf ("index is %d\n", index); //prints 3 fine 

    if (listarray[index] == NULL) 
     { 
     printf("listarray[%d] is NULL",index); //prints because of loop in main 
     listarray[index]->data = value; //crashes here 
     printf("listarray[%d] is now %d",index,listarray[index]->data); //never prints 
     listarray[index]->next = NULL; 
     } 

    else 
     { 
     temp->next = listarray[index]; 
     listarray[index] = temp; 
     listarray[index]->data = value; 
     } 
    }//end insert() 



//------------------------------------------------------------------------------ 
    int main() 
     { 
    int size = 8,i; //set default to 8 

    node * head=NULL; //head of the list 
    node **listarray = malloc (sizeof (node*) * size); //declare an array of Node * 
              //do i need double pointers here? 

      for (i = 0; i < size; i++) //malloc each array position 
      { 
      listarray[i] = malloc (sizeof (node) * size); 
      listarray[i] = NULL; //satisfies the first condition in insert(); 
      } 

      insert(*&listarray,size); 
     } 

輸出：

index is 3 
    listarray[3] is NULL 

（崩潰）

所需的輸出：

index is 3 
listarray[3] is NULL 
listarray[3] is now 11 

Answer 1

有各種各樣的問題在這裏：

如果你有一個哈希表一定size，那麼哈希碼必須映射到0和size - 1之間的值。您的默認大小是8，但您的散列碼是x % 13，這意味着您的索引可能超出範圍。

您的insert函數也應該傳遞該項目以插入（除非這是參數size，在這種情況下，它是嚴重錯誤名稱）。

if (listarray[index] == NULL) { 
    listarray[index]->data = value; //crashes here 
    listarray[index]->next = NULL; 
} 

這也難怪，它崩潰了：當節點是NULL，你不能解引用它要麼*或->。你應該在這裏分配新的內存。

，你不應該在這裏分配內存：

 for (i = 0; i < size; i++) //malloc each array position 
     { 
     listarray[i] = malloc (sizeof (node) * size); 
     listarray[i] = NULL; //satisfies the first condition in insert(); 
     } 

分配內存，然後將其重置爲NULL是無稽之談。 NULL是一個特殊的值，這意味着沒有內存在指向的位置。只需將所有節點設置爲NULL，這意味着散列表在沒有任何節點的情況下啓動。分配何時需要某個位置的節點。

在else條款，你寫的：

else 
    { 
    temp->next = listarray[index]; 
    listarray[index] = temp; 
    listarray[index]->data = value; 
    } 

但temp尚未分配，但你取消對它的引用。這與解除引用'NULL'一樣糟糕。

你的散列表還需要一種手段來處理衝突。它看起來好像在散列表中的每個索引處都有一個鏈表。這是處理它的好方法，但是你沒有正確實施。

您似乎有理解指針的問題。也許你應該從一個簡單的數據結構像鏈表開始，只是爲了練習？當你牢牢掌握了這些之後，你可以使用你學到的來實現你的散列表。