c - K&R 练习 6-2 - 自引用结构

Question

我正在尝试做K&R的练习6-2，练习的文字是:

Exercise 6-2. Write a program that reads a C program and prints in alphabetical order each group of variable names that are identical in the first 6 characters, but different somewhere thereafter . Don’t count words within strings and comments. Make 6 a parameter that can be set from the command line.

我尝试解决这个问题的方法是使用两个结构，一个结构group，它将包含具有相同的 6 个第一个字符的单词组:

struct group {
  struct group *left;
  struct group *right;
  struct word *word;
};

left 和 right 指向按字母顺序紧接当前组之前和之后的组，结构 word:

struct word{
  char *value;
  struct word *left;
  struct word *right;
};

将包含在value输入中读取的单词的字符串，left和right指向紧邻之前和紧随其后的单词当前的按字母顺序排列。

我使用函数addgroup和addword为新的groups/words分配内存:

struct word *addword(struct word *w, char *s)
{
  printf("[START]: addword(%s, %s)\n", (w == NULL ? "(null)": w->value), s);
  if(w == NULL){
    struct word *new_word = (struct word *) malloc(sizeof(struct word));
    if(new_word) {
      printf("[START]: Creating new word %s \n", s);
      new_word->left = NULL;
      new_word->right = NULL;
      new_word->value = strdup(s);
      printf("[END]: Created new word %s \n", new_word->value);
      return new_word;
      }
      else{
    printf("ERROR: Couldn't allocate memory for %s\n", s);
    return NULL;
      }
    }
    else if(strcmp(s, w->value) < 0){
      printf("[START]: Adding %s to left of %s\n", s, w->value);
      w->left = addword(w->left, s);
      printf("[END]: Added %s to left of %s\n", s, w->value);
    }
    else if(strcmp(s, w->value) > 0){
      printf("[START]: Adding %s to right of %s\n", s, w->value);
      w->right = addword(w->right, s);
      printf("[END]: Added %s to right of %s\n", s, w->value);
    }
    return w;
}

struct group *galloc()
{
  return (struct group *) malloc(sizeof(struct group));
}



struct group *addgroup(struct group *g, char *s)
{
  char *temp;
  if(g == NULL)
    {
      temp = strndup(s, 6);
      printf("[START]: creating new group %s\n", temp);
      struct group *new_group = galloc();
      if(new_group) {
    new_group->left = NULL;
    new_group->right = NULL;
    new_group->word = addword(NULL, s);
    printf("[END]: created new group %s\n", temp);
    return new_group;
      }
      else{
    printf("[ERROR]: Could not allocate space to new group\n");
    return NULL;
      }
    }
  else if(strncmp(s, (g->word)->value, 6) < 0) {
    printf("[START]: Adding word %s to left of group %s \n", s, strncpy(temp, (g->word)->value, 6));
    g->left = addgroup(g->left, s);
    printf("[END]: Added word %s to left of group %s \n", s, strncpy(temp, (g->word)->value, 6));
  }
  else if(strncmp(s, (g->word)->value, 6) > 0) {
    printf("[START]: Adding word %s to right of group %s \n", s, strncpy(temp, (g->word)->value, 6));
    g->right = addgroup(g->right, s);
    printf("[END]: Added word %s to right of group %s \n", s, strncpy(temp, (g->word)->value, 6));
      }
  else {
    printf("[START]: Adding word %s to group %s \n", s, strncpy(temp, (g->word)->value, 6));
    g->word = addword(g->word, s);
    printf("[END]: Added word %s to group %s \n", s, strncpy(temp, (g->word)->value, 6));
  }
  return g;
}

我的问题:代码适用于前 3 个单词，然后因段错误(核心转储) 错误而崩溃，这是一个输出示例(在我的主函数中，我打印了整个树)每个新单词后进行分组):

> Falsefiable
[START]: creating new group Falsef
[START]: addword((null), Falsefiable)
[START]: Creating new word Falsefiable 
[END]: Created new word Falsefiable 
[END]: created new group Falsef
Falsefiable

...After adding words Falsefact, Falsefiable, and Printingpress, all without a problem...

Falsefact
Falsefiable
Printingpress

> Printing
[START]: Adding word Printing to right of group Falsef 
[START]: Adding word Printing to group Printi 
[START]: addword(Printingpress, Printing)
[START]: Adding Printing to left of Printingpress
[START]: addword((null), Printing)
[START]: Creating new word Printing 
[END]: Created new word Printing 
[END]: Added Printing to left of Printingpress
[END]: Added word Printing to group Printi 
[END]: Added word Printing to right of group Falsef 
Segmentation fault (core dumped)

使用valgrind我所能了解到的是问题是由访问不在地址的映射区域内

引起的

知道我做错了什么吗？

编辑1:我的main函数

#define MAXWORD 100

int main(int agrc, char *argv[])
{
  char word[MAXWORD];
  struct group *root = NULL;
  while( getword(word, MAXWORD) != EOF)
    if(isalpha(word[0])){
      root = addgroup(root, word);
       printgroup(root);
    }     
  return 0;
}

函数getword:

char getword(char *word, int l)
{
  int c, i;
  while(isspace(c = getch()))
    ;

  i = 0;
  word[i++] = c;

  if(!isalpha(c)){
    word[i] = '\0';
    return c;
  }

  while(isalnum(c = getch()) && i < l-1)
    word[i++] = c;
  word[i] = '\0';

  ungetch(c);
  return word[0];
}

和获取/取消提取:

#define BUFFSIZE 100

int buffer[BUFFSIZE];
int buffp = 0;

int getch(void)
{
  if(buffp > 0)
    return buffer[--buffp];
  else
    return getchar();
}
void ungetch(int c)
{
  if(buffp <  BUFFSIZE - 1)
    buffer[buffp++] = c;
  else
    printf("ERROR: Not enough space in buffer\n");

}

编辑2:清理问题并添加valgrind输出

这是崩溃发生时valgrind在程序输出的最后一行之后的输出:

[END]: Added word Printing to right of group Falsef 
==13993== Invalid write of size 8
==13993==    at 0x1090CB: main (in /home/me/The C Programming Language/Chapter 6/6-2/main)
==13993==  Address 0x69746e6971d8 is not stack'd, malloc'd or (recently) free'd
==13993==
==13993==
==13993== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==13993==  Access not within mapped region at address 0x69746E6971D8
==13993==    at 0x1090CB: main (in /home/me/The C Programming Language/Chapter 6/6-2/main)
==13993==  If you believe this happened as a result of a stack
==13993==  overflow in your program's main thread (unlikely but
==13993==  possible), you can try to increase the size of the
==13993==  main thread stack using the --main-stacksize= flag.
==13993==  The main thread stack size used in this run was 8720384.
==13993==
==13993== HEAP SUMMARY:
==13993==     in use at exit: 203 bytes in 12 blocks
==13993==   total heap usage: 14 allocs, 2 frees, 2,251 bytes allocated
==13993==
==13993== LEAK SUMMARY:
==13993==    definitely lost: 14 bytes in 2 blocks
==13993==    indirectly lost: 0 bytes in 0 blocks
==13993==      possibly lost: 0 bytes in 0 blocks
==13993==    still reachable: 189 bytes in 10 blocks
==13993==         suppressed: 0 bytes in 0 blocks
==13993== Rerun with --leak-check=full to see details of leaked memory
==13993==
==13993== For counts of detected and suppressed errors, rerun with: -v
==13993== Use --track-origins=yes to see where uninitialised values come from
==13993== ERROR SUMMARY: 315 errors from 67 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

Answer 1

这里至少有一个问题:

struct group *addgroup(struct group *g, char *s)
{
  char *temp;
  if (g == NULL)
  {
    temp = strndup(s, 6);
    ...
  }
  else if (strncmp(s, (g->word)->value, 6) < 0) {
    printf("[START]: Adding word %s to left of group %s \n", s, strncpy(temp, (g->word)->value, 6));
    ...                                                                  ^
                                                                         |
                                          temp may be uninitialized here |

如果g不是NULL，则temp未初始化，并且取消引用未初始化的指针将导致各种令人讨厌的事情，又称为< em>未定义的行为。