• 书中指出：也不能分别对输入中的每个单词都执行一次线性查找，看其是否已经出现过。（程序执行的时间将会与输入单词的数量的二次方成比例）

说实话，我对这句话不是特别明白，或者认同，怎么会是二次方成正比呢？当然，确实不能使用一次线性查找。对此问题，我的分析如下：

• 折半查找的话，必须要将排序放入一个数组内（因为需要对下标进行计算），那样的话，新来的单词，即使我们找到它该存在的位置而没有它，我们打算将其插入数组，由会涉及数组元素的挪动，说到挪动，肯定是又要增加时间
• 顺序查找：那顺序查找为什么不可以呢？顺序查找可以用使用链表了了吧，我们只要在查找时找到这个新单词该出现的位置，没有找到它的话，那么我们再插入它，对于列表来说插入一个单词是非常方便的。当然，即使如此，查找的时间复杂度为O(n)
• 二叉数：如果使用二叉数来完成这个问题，我们将会得到更好的时间复杂度O（lgn），n为节点个数。也可以说，所花费的时间将会和树的高度成正比。二叉数的所有操作的时间复杂度都是这么多，包括插入、删除、建立、查找（来自：算法导论 第三版 第12章）。所以，对于一个单词而言，如果已经存放在了树中，那么就是查找，将新单词放入的就是插入。然而，实际上这两个动作应该是结合起来的，因为在其该在的位置找不到的时候，我们已经得到新单词该在的位置，所以直接插入即可。具体请看下面代码的实现。

使用二叉数，我们以字典顺序排序，为了更好的理解，我们构建的二叉数的节点大概是这样的：
对于这样一句话：now is the time for all good men to come to the aid of their party

1. 自身数据
2. 左孩子
3. 右孩子

struct tnode {
	char *word;
	int count;
	struct tnode *left;
	struct tnode *right;
};

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 *addtree(struct tnode *p, char *w)
{
	//判断是否是新节点
	if (p == NULL) {
		/* a new word has arrived */
		p = talloc();
		/* make a new node */
		p->word = strdup1(w);//复制w的过程，如单纯的赋值，就会使p->word和w指向了一处。
		p->count = 1;
		p->left = p->right = NULL;
		return p;
	}
	//不是新节点
	int cond;
	cond = strcmp(w, p->word);
	if (cond== 0){
			p->count++;/* repeated word */
	}else if (cond < 0){//就到左子树去找
		p->left = addtree(p->left, w);
	}else{//就到右子树去找
		p->right = addtree(p->right, w);
	}
	return p;
}

/* talloc: make a tnode */
/**
 * 为新节点分配内存
 */
struct tnode *talloc(void)
{
	return (struct tnode *) malloc(sizeof(struct tnode));
}
/**
 * 完成对单词的复制，避免不同指针指向同一个单词，对单词产生干扰
 */
char *strdup1(char *s)
{
	char *p;
	/* make a duplicate of s */
	p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
	if (p != NULL)
		strcpy(p, s);
	return p;
}

/* 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];
}

#define BUFSIZE 100
char buf[BUFSIZE];
int bufp = 0;
/* buffer for ungetch */
/* next free position in buf */
int getch(void) /* get a (possibly pushed-back) character */
{
	return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c)
/* push character back on input */
{
	if (bufp >= BUFSIZE)
	printf("ungetch: too many characters\n");
	else
	buf[bufp++] = c;
}

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);

struct tnode {
	char *word;
	int count;
	struct tnode *left;
	struct tnode *right;
};
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 *strdup1(char *s);

struct tnode *addtree(struct tnode *p, char *w)
{
	//判断是否是新节点
	if (p == NULL) {
		/* a new word has arrived */
		p = talloc();
		/* make a new node */
		p->word = strdup1(w);//复制w的过程，如单纯的赋值，就会使p->word和w指向了一处。
		p->count = 1;
		p->left = p->right = NULL;
		return p;
	}
	//不是新节点
	int cond;
	cond = strcmp(w, p->word);
	if (cond== 0){
			p->count++;/* repeated word */
	}else if (cond < 0){//就到左子树去找
		p->left = addtree(p->left, w);
	}else{//就到右子树去找
		p->right = addtree(p->right, w);
	}
	return p;
}


/* 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);
	}
}


/* talloc: make a tnode */
/**
 * 为新节点分配内存
 */
struct tnode *talloc(void)
{
	return (struct tnode *) malloc(sizeof(struct tnode));
}
/**
 * 完成对单词的复制，避免不同指针指向同一个单词，对单词产生干扰
 */
char *strdup1(char *s)
{
	char *p;
	/* make a duplicate of s */
	p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
	if (p != NULL)
		strcpy(p, s);
	return p;
}
/* 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];
}

#define BUFSIZE 100
char buf[BUFSIZE];
int bufp = 0;
/* buffer for ungetch */
/* next free position in buf */
int getch(void) /* get a (possibly pushed-back) character */
{
	return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c)
/* push character back on input */
{
	if (bufp >= BUFSIZE)
	printf("ungetch: too many characters\n");
	else
	buf[bufp++] = c;
}