c - 我得到一个奇怪的 sysmalloc: Assertion error when using a trie

Question

我有一项任务是检查某些输入单词是否来自字典并打印并计算不是的单词。最初字典是一个数组，我不得不将其更改为 trie 以使其更快（/* */ 之间的代码是更改后的代码）。尝试编译后我觉得很奇怪

我不知道现在该怎么办。我使用的文件和代码如下：dictionary.h：

// declares a dictionary

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// maximum length for a word
#define LENGTH 45
//Nr of possible children=size of the alphabet
#define N 26

//a trie as dictionary
typedef struct dict
{
    bool is_word;
    struct dict *children[N];
} dict;


// a dictionary is an array
/* typedef struct dict {
  int numWords;
  int maxWords;
  char **words;
} dict; 
*/



dict *newEmptyDict();
void addWord(char word[LENGTH + 1], dict *d);
bool check(const char *word, dict *d);
void freeDict(dict *n);

#endif // DICTIONARY_H

字典.c：

// implements a dictionary

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

#include "dictionary.h"
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

/* dict *newEmptyDict() {
  dict *d = malloc(sizeof(dict));
  if (d == NULL) {
    return NULL;
  }
  d->numWords = 0;
  d->maxWords = 1;
  d->words = malloc(sizeof(char*) * d->maxWords);
  return d;
}
*/

//create an empty trie dictionary
dict *newEmptyDict() {
    dict *pN = NULL;
    pN=(dict*)malloc(sizeof(dict));
    if (pN){
        int i;
        pN->is_word=false;
        for (i=0;i<=N;i++)
            pN->children[i]=NULL;

    }
    return pN;
}

// add word to the dictionary if it is is not already known
/* void addWord(char word[LENGTH + 1], dict *d) {
  if (!check(word, d)) {
    // if we need more space before adding the word, double the size
    if (d->numWords == d->maxWords) {
      d->words = realloc(d->words,(sizeof(char*)) * (d->maxWords * 2));
      if (d->words == NULL) {
        printf("Out of memory.\n");
        exit(-1);
      }
      d->maxWords = d->maxWords * 2;
    }
    // now we actually add the word
    d->words[d->numWords] = malloc(sizeof(char) * (LENGTH + 1));
    strcpy(d->words[d->numWords],word);
    d->numWords++;
  }
} */

void addWord(char word[LENGTH + 1], dict *d) {
    int level;
    int len=strlen(word);
    int index;
    dict *pC = d;
    for (level=0;level<len;level++){
        index = CHAR_TO_INDEX(word[level]);
        if(!pC->children[index])
            pC->children[index] = newEmptyDict();
        pC=pC->children[index];
    }
    pC->is_word = true;

}

// check whether word is in dictionary
/* bool check(const char *word, dict *d) {
  for (int i = 0; i < d->numWords; i++) {
    if (strcmp(d->words[i],word) == 0) {
      return true;
    }
  }
  return false;
} */

bool check(const char *word, dict *d) {
    int level; 
    int len=strlen(word); 
    int index;
    dict *pC = d;
    for (level=0;level<len;level++){
        index = CHAR_TO_INDEX(word[level]); 
        if (!pC->children[index]) 
            return false; 
        pC=pC->children[index]; 
    } 

    return (pC!=NULL && pC->is_word); 
} 


/* void freeDict(dict *d) {
  for (int i = 0; i < d->numWords; i++) {
    free(d->words[i]);
  }
  free(d->words);
  free(d);
}
*/
void freeDict(dict *d) {
    int i;
    for (i=0;i<=N;i++)
        if (d->children[i]) freeDict(d->children[i]);
    free (d);
}

拼写者.c：

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

#include "dictionary.h"

// remove non-alphabetic characters and convert to lower case
void trimWord(char *word) {
  int k = 0;
  for (int i = 0; i < (int) strlen(word); i++) {
    if (isalpha(word[i])) {
      word[k] = tolower(word[i]);
      k++;
    }
  }
  word[k] = '\0';
}

int main(int argc, char *argv[]) {

  char word[LENGTH + 1] = "";

  // step 1: read in the dictionary
  dict *dictionary = newEmptyDict();
  while (scanf("%45s",word) && word[0] != '!') {
    trimWord(word);
    addWord(word,dictionary);
    memset(word,0,strlen(word));
  }

  // step 2: read in text
  int counter = 0; // number of unknown words

  // BUG: This loop is wrong. It will read "one,twwo" as one word "onetwwo".
  /* while (scanf("%45s", word) != EOF) {
    trimWord(word);
    if (!check(word,dictionary)) {
      counter++;
      printf("%s\n",word);
    }
  }
  */
  int index = 0; int wcheck=0; //wcheck is for knowing if a word has begun so no unnecesary \n's are printed
  int c = EOF;
  while ((c = getchar()) && c != EOF) {
    if (isalpha(c)){
        word[index]=c;
        index++;
        wcheck=1;
    }else if (wcheck){
        trimWord(word);
        if(!check(word,dictionary)){
            counter++;
            printf("%s\n", word);
        }
        memset(word,0,strlen(word));
        index=0;
        wcheck=0;
    }
  } 
  // TODO: Replace the above while loop with a correct solution.
  // Hints:
  // - you should read one character at a time, using getchar()
  // - alphabetical characters should be appended to the current word
  // - any other symbol should terminate the word
  // this code might be useful:
  /*
  int index = 0;
  int c = EOF;
  while ((c = getchar()) && c != EOF) {
    // ...
  }
  */

  // step 3: print number of unknown words
  printf("%d\n", counter);

  freeDict(dictionary);
  return 0;
}

你能帮忙吗？我相信这与分配有关，但我仍然卡住了。谢谢！

标签： cdictionarymalloctrie