Violation d'accès en C++ avec les tables de hachage et les listes liées

Question

J'ai donc essayé de créer une classe qui gère 1000 listes liées et qui déclare initialement des pointeurs vers celles-ci.

C'est le code qui traite directement de mes problèmes :

struct node
{
    char name[40];
    char numb[12];
    node * next;
};
class hashTable
{
public:
    //Creates a table of 1000 pointers to linked-list nodes
    node * table[1000];

//Functions
void addNode(char name[40], char numb[12])
{
    node * temp;        //Initializes temp node as pointer
    temp = new node;    //Points temp node to a new node

    int hash = h(g(name));  //The hash of the key (name) used to check nodes
    temp = table[hash];     //sets the temporary node to the first node of the list

    while (temp->next != 0)
    {
//...

C'est juste au niveau de la boucle while que j'obtiens l'erreur "Access violation reading location 0xcccccd00". Je ne sais pas pourquoi il ne peut pas accéder au membre de la table, à moins que ce ne soit parce que ces valeurs n'ont pas été initialisées ou autre chose ?

Answer 1

Vous ne faites probablement pas deux choses. Premièrement, assurez-vous que votre table de hachage est correctement initialisée pour contenir des pointeurs tous NULL. Deuxièmement, assurez-vous que tout pointeur récupéré dans la table de hachage est valide. avant pour le déréférencer :

Pour le premier numéro :

hashTable::hashTable() : table()
{
}

Aussi, vous voulez vous assurer que cette chose nettoie correctement

hashTable::~hashTable()
{
    for (size_t i=0;i<sizeof(table)/sizeof(table[0]); ++i)
    {
        node *temp = table[i];
        while (temp)
        {
            node *victim = temp;
            temp = temp->next;
            delete victim;
        }
    }
}

Pour le deuxième numéro :

void addNode(const char *name, const char *numb)
{
    int hash = h(g(name));    //The hash of the key (name) used to check nodes
    node *temp = table[hash]; //sets the temporary node to the first node of the list

    if (temp)
    {
        // preexisting entry. walk that list looking for matching key.
        node **pp = &temp->next;
        while (temp)
        {
            if (0 == strcmp(temp->name, name))
                break;
            pp = &temp->next;
            temp = temp->next;
        }

        // link to last node if not found in list
        if (!temp)
            *pp = new node(name, numb);
    }
    else
    {   // no prior entry. create a new one and store it at table[hash].
        table[hash] = new node(name, numb);
    }
}

Remarque : le code ci-dessus suppose que la classe de nœuds est implémentée en tant que

struct node
{
    char name[40];
    char numb[12];
    node * next;

    node(const char* name_, const char *numb_)
        : next()
    {
        strncpy(name, name_, sizeof(name)/sizeof(name[0])-1);
        name[ sizeof(name)/sizeof(name[0])-1 ] = 0;
        strncpy(numb, numb_, sizeof(numb)/sizeof(numb[0])-1);
        numb[ sizeof(numb)/sizeof(numb[0])-1 ] = 0;
    }
};

Personnellement, j'utiliserais std::string

Answer 2

Si la valeur de hash est supérieure (ou égale) à 1000, temp pointera vers une zone non valide.

Et vous faites fuir la mémoire allouée par new node puisque vous écrasez la variable temporaire.