K&R 练习 6-2 - 自引用结构
K&R Exercise 6-2 - Self referencing Structures
我正在尝试做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 个单词，然后因 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] = '[=15=]';
return c;
}
while(isalnum(c = getch()) && i < l-1)
word[i++] = c;
word[i] = '[=15=]';
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)
这里至少有一个问题：
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 未初始化并且取消引用未初始化的指针将导致各种令人讨厌的事情，也就是 未定义的行为.
我正在尝试做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 个单词，然后因 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] = '[=15=]';
return c;
}
while(isalnum(c = getch()) && i < l-1)
word[i++] = c;
word[i] = '[=15=]';
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)
这里至少有一个问题：
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 未初始化并且取消引用未初始化的指针将导致各种令人讨厌的事情，也就是 未定义的行为.