c - 检查数据结构中的值是否等于 NULL 如何返回段错误？

Question

我正在尝试加载节点*(s)-的哈希表-

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

(不用担心长度，它在调用它的文件中定义)

-进入内存，但是这个:

//  make hash table
node* hashtable[729];

node* new_node = malloc(sizeof(node));
node* cursor = NULL;
int bucket;
while(sscanf(dictionary,"%s",new_node->word) != 0)
{
    bucket = hash(new_node->word);

    cursor = hashtable[bucket];
    while(cursor->next != NULL)
    {
        cursor = cursor->next;
    }

    cursor->next = new_node;
}
return true;

不断出现段错误(特别是 while 循环的情况)。我很困惑，这是怎么回事？提前感谢任何帮助的人!非常感谢您的帮助!

Answer 1

您需要为进入哈希表的每个节点分配内存。像下面这样的东西怎么样:

/* make hash table */
node* hashtable[729];

/* initialise all buckets to NULL */
memset(hashtable, 0, sizeof(node*)*729);

node new_node;  /* Use a stack node for the temporary */
new_node.next = NULL;
node** cursor = NULL;
int bucket;
while(sscanf(dictionary,"%s",new_node.word) != 0)
{
  bucket = hash(new_node.word);

  cursor = &hashtable[bucket];
  while(*cursor != NULL)
  {
    cursor = &(*cursor)->next;
  }

  if ((*cursor = malloc(sizeof(node))) != NULL)
    /* Copy from temporary to hashed node. Assumes structure is 'flat' */
    **cursor = new_node;
  else {
    /* panic! */
  }
}
return true;

编辑:

我重构了一些代码并生成了一个可以编译和运行的独立示例。为简单起见，我使用了一个完全伪造的哈希函数并减少了桶的数量以适应其 0-25 的输出。我尝试拆分哈希表“对象”，并开始努力更加自律，以避免缓冲区溢出等。

为了遍历哈希表桶中的节点链表，我提供了两个版本——一个使用节点**(指向指针的指针)，另一个不使用——在一个尝试演示双星的使用。将 #if 1 更改为 #if 0 以使用“单星”版本。

我希望，总的来说，这些更改有助于澄清(而不是模糊)最初的目的，尽管我对以下代码的冗长表示歉意:

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

#define LENGTH 64

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

typedef struct hashtable {
  node * table[26];
} hashtable;


/* The cleverest 'hashing' function in the world ever! */
int hash(const char * str) {
  if (str && str[0]) return tolower(str[0]) - 'a';
  return 0;
}

/* Allocate a new node and initialise it with the given word */
node * node_create(const char * word) {
  node * nd = NULL;
  if (word && (nd = malloc(sizeof(node)))) {
    strncpy(nd->word, word, sizeof(nd->word)-1);
    nd->word[sizeof(nd->word) - 1] = '\0';
    nd->next = NULL;
  }
  return nd;
}


/* Set all the buckets' pointers to NULL */
void hashtable_init(hashtable * ht) {
  if (ht) memset(ht, 0, sizeof(hashtable));
}

/* Place the given node into the hashtable, taking responsibility for it */
void hashtable_insert_node(hashtable * ht, node * nd) {
  if (ht && nd) {

#if 1 /* More succint version using node**  */

    /* Identify the bucket this node should go into */
    node ** cursor = ht->table + hash(nd->word);

    /* Append this node to this bucket's list of nodes */
    while (*cursor != NULL) cursor = &(*cursor)->next;

    *cursor = nd;

#else /* Version that avoids use of node**  */
    int bucket = hash(nd->word);

    /* Identify the bucket this node should go into */
    if (ht->table[bucket]) {
      node * cursor = ht->table[bucket];
      while (cursor->next) cursor = cursor->next;
      cursor->next = nd;
    } else {
      ht->table[bucket] = nd;
    }
#endif

    nd->next = NULL;  // Ensure the new node is the last in the list
  }
}

/* Free the contents of the given hashtable */
void hashtable_free_contents(hashtable * ht) {
  if (ht) {
    int i;
    for (i=0; i < sizeof(ht->table)/sizeof(ht->table[0]); ++i) {
      node * cursor = ht->table[i];
      while (cursor != NULL) {
        node * next = cursor->next;
        free(cursor);
        cursor = next;
      }
    }
  }
}

/* Dump the contents of the given hashtable to stdout */
void hashtable_dump(const hashtable * ht) {
  if (ht) {
    int i;
    for (i=0; i < sizeof(ht->table)/sizeof(ht->table[0]); ++i) {
      printf("Bucket %d:", i);
      node * cursor = ht->table[i];
      while (cursor != NULL) {
        printf(" %s", cursor->word);
        cursor = cursor->next;
      }
      printf("\n");
    }
  }
}

int main(int argc, char * argv[]) {
  char dictionary[] = {
    "apples "
    "apricots "
    "oranges "
    "lemons "
    "bananas "
    "raspberries "
    "carrots "
    "tomatoes "
    "aubergines "
    "limes "
    "blueberries "
    "plums "
    "pears "
    "peaches "
    "pineapples "
    "tangerines "
    "kiwis "
    "passion_fruit "
    "strawberries "
  };

  hashtable ht;
  hashtable_init(&ht);

  char * p = dictionary;  /* Pointer for traversing the dictionary */

  node new_node;  /* Temporary node for storing word read from dictionary */
  new_node.next = NULL;

  int n; /* Number of bytes read from dictionary in sscanf call */
  char format[16];

  /* If a huge word is in the dictionary, guard against buffer overflow */
  snprintf(format, sizeof(format), "%%%ds%%n", sizeof(new_node.word));

  while(sscanf(p, format, new_node.word, &n) == 1) {
    /* Insert (a copy of the) new node into hashtable */
    hashtable_insert_node(&ht, node_create(new_node.word));

    /* Move forwards through the dictionary */
    p += n;
  }

  hashtable_dump(&ht);

  hashtable_free_contents(&ht);
  return 0;
}