0

这是程序的代码,它计算某个输入中所有单词的出现次数。取自 K 和 R 一书。除了作者为什么要使用 strdup() 之外,我几乎理解了所有内容。为什么我们不能只分配(在函数 addtree 中)p->word=w。在结构 tnode 中,word 显然是一个指向字符的指针,而 addtree 函数的参数是一个字符指针。

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

#define MAXWORD 100
#define BUFSIZE 100

struct tnode {                        /* the tree node: */
 char *word;                          /* points to the text */
 int count;                           /* number of occurrences */
 struct tnode *left;                  /* left child */
 struct tnode *right;                 /* right child */
};

struct tnode *addtree(struct tnode *, char *);
struct tnode *talloc(void);
void treeprint(struct tnode *);
void ungetch(int);
int getword(char *, int);
int getch(void);

char buf[BUFSIZE];                    /* buffer for ungetch */
int bufp = 0;                         /* next free position in buf */


int main(void) {                      /* word frequency count */
 struct tnode *root;
 char word[MAXWORD];

 root = NULL;
 while(getword(word, MAXWORD) != EOF)
  if(isalpha(word[0]))
    root = addtree(root, word);

 treeprint(root);
 exit(0);
}

                                      /* getword: get next word or character from input */
int getword(char *word, int lim) {
 int c, getch(void);
 void ungetch(int);
 char *w = word;

 while(isspace(c = getch()))
  ;
 if(c != EOF)
  *w++ = c;
 if(!isalpha(c)) {
  *w = '\0';
  return c;
 }
 for(; --lim > 0; w++)
  if(!isalnum(*w = getch())) {
   ungetch(*w);
   break;
  }
 *w = '\0';
 return word[0];
}

                                       /* addtree: add a node with w, at or below p */
struct tnode *addtree(struct tnode *p, char *w) {
 int cond;

 if(p == NULL) {                       /* a new word has arrived */
  p = talloc();                        /* make a new node */
  p->word = strdup(w);
  p->count = 1;
  p->left = p->right = NULL;
 } else if((cond = strcmp(w, p->word)) == 0)
  p->count++;                          /* repeated word */
 else if(cond < 0)                     /* less than into left subtree */
  p->left = addtree(p->left, w);
 else                                  /* greater than into right subtree */
  p->right = addtree(p->right, w);

 return p;
}

                                       /* talloc: make a tnode */
struct tnode *talloc(void) {
 return(struct tnode *)malloc(sizeof(struct tnode));
}

                                       /* treeprint: in-order print of tree p */
void treeprint(struct tnode *p) {
 if(p != NULL) {
  treeprint(p->left);
  printf("%4d %s\n", p->count, p->word);
  treeprint(p->right);
 }
}

int getch(void) {
 return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c) {
 if(bufp >= BUFSIZE)
  printf("ungetch: too many characters\n");
 else
  buf[bufp++] = c;
}
4

2 回答 2

2

因为没有strdup您只需分配变量的地址,因此两者都将指向相同的内存(因此相同的数据)。

char *ptr2 = ptr1;

+----------+           +---------+
|   PTR1   |---------->|  VALUE  |
+----------+           +---------+
                            ^
+----------+                |
|   PTR2   |----------------+
+----------+

虽然strdup分配了新的内存块并将字符复制到新的内存块中:

char *ptr2 = strdup(ptr1);

+----------+           +---------+
|   PTR1   |---------->|  VALUE  |
+----------+           +---------+

+----------+           +---------+    
|   PTR2   |---------->|  VALUE  |
+----------+           +---------+

你看出区别了吗?

于 2013-01-06T21:03:34.157 回答
0

@DCoder 是对的,这确实是这篇文章的答案

第一次分配单词的行是:

char word[MAXWORD];

该程序一遍又一遍地反复进入这个记忆。如果不为每个节点复制这些数据,它们都会指向这个缓冲区。

于 2013-01-06T21:01:44.583 回答