K&R练习6-2 -自我参照结构

Question

我试着做K&R的练习6-2，练习的内容是：

练习6-2.编写一个读取C程序并按字母顺序打印每组变量名称的程序，这些变量名在前6个字符中是相同的，但在其后的某个地方不同。不要计算字符串和注释中的单词。使6成为可以从命令行设置的参数。

我试图解决这个问题的方法是有两个结构，一个结构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个单词起作用，然后出现一个segmentation fault (core dumped)错误，下面是输出的示例(在我的主要函数中，我在每个新单词之后打印整个组树)：

> 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，我所能了解到的就是这个问题是由Access not within mapped region at address引起的

知道我做错了什么吗？

编辑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];
}

和getch/ungetch

#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就没有初始化，取消引用一个未初始化的指针将导致各种讨厌的事情AKA未定义的行为。