K&R的名著:<C程序设计语言>自引用结构

自引用结构

任务：统计输入中所有出现单词的次数。

两种解决方法：

<1>、在读取输入中任意单词的同时，就将它放置到正确的位置，从而始终保证所有单词是按顺序排列的。

<2>、采用一种二叉树的数据结构

每个不同的单词在树中都是一个节点，每个节点包括：

一个指向该单词内容的指针

一个统计出现次数的计数值

一个指向左子树的指针

一个指向右子树的指针

任何节点最多拥有两个子树，也可能只有一个子树或一个都没有。

要点：对节点的所有操作都要保证，任何节点的左子树只包含按字典序小于该节点中单词的那些单词，右子树只包含按字典序大于该节点中单词的那些单词。

标准库函数malloc能满足对齐要求

#include <stdio.h>#include<string.h>#include<ctype.h>#define MAXWORD 100struct tnode {char *word;int count;struct tnode *left;struct tnode *right;};struct tnode *addtree(struct tnode *, char *);void treeprint(struct tnode *);int getword(char *, int );int main(void){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 *strdup1(char *);/* *addtree函数：在p的位置或p的下方增加一个w节点 */struct tnode *addtree(struct tnode *p, char *w){int cond;if (p == NULL) {p = talloc();p->word = strdup1(w);p->count = 1;p->left = p->right = NULL;}else if ((cond = strcmp(w, p->word)) == 0)p->count++;else if (cond < 0)p->left = addtree(p->left, w);elsep->right = addtree(p->right, w);return p;}/* *treeprint函数：按序打印树p */void treeprint(struct tnode *p){if (p != NULL) {treeprint(p->left);printf("%4d %s\n",p->count, p->word);treeprint(p->right);}}/* *talloc函数：创建一个tnode */#include <stdlib.h>struct tnode *talloc(void){return (struct tnode *)malloc(sizeof(struct tnode));}/* *strdup函数：把传入的参数字符串复制到某个安全的位置 */char *strdup1(char *s){char *p;p = (char *)malloc(strlen(s) + 1);if (p != NULL)strcpy(p, s);return p;}int getch1(void);void ungetch1(int);/**getword函数：从输入中读取下一个单词或字符*/int getword(char* word, int lim){int c;char *w = word;while (isspace( c = getch1()));if (c != EOF)*w++ = c;if (!isalpha(c)){*w = '\0';return c;        }        for (; --lim > 0; w++)if ( !isalnum( *w = getch1())){//printf("in the getword()");ungetch1(*w);break;}*w = '\0';return word[0];}#define BUFSIZE 1000char buf[BUFSIZE];int bufp = 0;int getch1(void){return (bufp > 0) ?buf[--bufp] : getchar();}void ungetch1(int c){    if (bufp >= BUFSIZE)printf("ungetch: too many characters\n");    elsebuf[bufp++] = c;}