C语言K&R圣经笔记 6.4结构体指针 6.5自引用结构体

本文介绍: 如果匹配，则答案是肯定的。新节点的存储空间通过 talloc 例程获取，它返回一个指针，指向一段适合保存树节点的可用内存空间，而新单词通过 strdup 被拷贝到一个隐藏的内存空间。在每个节点上，它打印左子树（所有比当前节点单词小的），然后是当前节点上的单词，然后是右子树（所有比当前节点单词大的）。如果 p 是指向结构体的指针，对 p 的指针运算会将结构体的大小考虑在内，因此 p++ 能正确地对 p 递增，使其指向结构体数组的下一个元素，而 for 循环中的判断条件能在正确的时候停止循环。

为了说明结构体指针和数组的某些注意事项，我们把上一节的关键字计数程序再写一次，不过这回使用指针而不是数组下标。

keytab 的外部声明不需要动，但 main 和 binsearch 确实需要修改。

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 1000

int getword(char *, int);
struct key *binsearch(char *, struct key *, int);

/* C语言关键字计数，指针版本 */
main()
{
    char word[MAXWORD];
    struct key *p;

    while (getword(word, MAXRORD) != EOF)
        if (isalpha(word[0]))
            if ((p=binsearch(word, keytab, NKEYS)) != NULL)
                p->count++;
    for (p = keytab; p < keytab + NKEYS; p++)
        if (p->count > 0)
            printf("%4d %s", p->count, p->word);
    return 0;
}

/* binsearch：在tab[0]...tab[n-1]中查找word */
struct key *binsearch(char *word, struct key *tab, int n)
{
    int cond;
    struct key *low = &tab[0];
    struct key *high = &tab[n-1];
    struct key *mid;

    while (low <= high) {
        mid = low + (high - low) / 2;
        if ((cond = strcmp(word, mid->word)) < 0)
            high = mid;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return NULL;
}

这里有几个地方值得一提。首先，binsearch 的声明必须指出它返回 struct key 的指针而不是（第三章版本里面的）整数；在函数原型和 binsearch 内部都声明了这一点。如果 binsearch 找到一个单词，则返回其指针；若没找到，则返回NULL。

第二，keytab 的元素现在通过指针和不是数组下标来访问。这要求对 binsearch 做大改。

low 和 high 的初始化表达式现在分别是指向表的开头和结尾的指针。

mid = (low + high) / 2     /* 错误 */

mid = low + (high-low) / 2

for (p = keytab; p < keytab + NKEYS; p++)

struct {
    char c;
    int i;
};

struct key *binsearch(char *word, struct key *tab, int n)

struct key *
binsearch(char *word, struct key *tab, int n)

struct tnode {             /* 树节点： */
    char *word;            /* 指向文本 */
    int count;             /* 出现次数 */
    struct tnode *left;    /* 左子节点 */
    struct tnode *right;   /* 右子节点 */
};

struct tnode *left;

struct t {
    ...
    struct s *p;    /* p 指向一个 s */
};
struct s {
    ...
    struct t *q;    /* q 指向一个 t */
};

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

#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

/* 单词频率计算 */
main()
{
    struct tnode *root;
    char word[MAXWORD];

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

struct tnode *talloc(void);
char *strdup(char *);

/* addtree: 在p的位置或其下层，加入带w的节点 */
struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;

    if (p == NULL) {            /* 来了新词 */
        p = talloc();           /* 创建新节点 */
        p->word = strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(p->word, w)) == 0)
        p->count++;            /* 重复单词 */
    else if (cond < 0)         /* 小于左子树 */
        p->left = addtree(p->left, w);
    else                       /* 大于右子树 */
        p->right = addtree(p->right, w);
    return p;
}

/* treeprint: 中序遍历树p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %sn", p->count, p->word);
        treeprint(p->right);
    }
}

#include <stdlib.h>

struct tnode *talloc(void)
{
    return (struct tnode *)malloc(sizeof(struct tnode));
}

char *strdup(char *s)    /* 复制s */
{
    char *p;

    p = (char *)malloc(sizeof(strlen(s)+1));  /* +1是给''的 */
    if (p != NULL)
        strcpy(p, s);
    return p;
}