【说明】 本程序从正文文件text.in中读入一篇英文短文，统计该短文中不同单词及出现次数，并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。 程序用一棵有序二叉树存储这些单词及其出现的次数，边读入边建立，然后中序遍历该二叉树，将遍历经过的二叉树上的结点内容输出。 【函数】 # include ＜stdio.h＞ # include ＜malloc.h＞ # include ＜ctype.h＞ # include ＜string.h＞ # define INF"text.in" # define OUTF "word.our’ typedef struct treenode { char *word; int count; struct treenode *left, *right; } BNODE; int getword(FILE *fpt, char *word) { char c;c=fgetc(tpt); if (c==EOF) return 0; while(!(tolower(c)＞= ’a’ && tolower(c)＜= ’z’)) { c=fgetc(fpt); if (c==EOF) return 0; } /* 跳过单词间的所有非字母字符 */ while(tolower(c)＞= ’a’ && tolower(c)＜= ’z’) { *word++=c; c=fgetc(fpt); } *word=’\0’;return 1; } void binary_tree(BNODE **t, char *word) { BNODE *ptr, *p; int compres;p=NULL;(1) ;while (ptr) /* 寻找插入位置 */{ compres=strcmp(word, ptr-＞word);/* 保存当前比较结果 */ if (!compres) { (2) ; return;} else { p=ptr;ptr=compres＞0 ptr-＞right: ptr-＞left; } } ptr=(BNODE *)malloc(sizeof(BNODE)); ptr-＞left=ptr-＞right=NULL; ptr-＞word=(char *)malloc(strlen(word)+1); strcpy(ptr-＞word, word); (3) ; if (p==NULL) *t=ptr; else if (compres＞0) p-＞right=ptr; else p-＞left=ptr; } void midorder(FILE *fpt, BNODE *t) { if (t==NULL) return; midorder(fpt, (4) ); fprintf(fpt, "%s %d\n", t-＞word, t-＞count); midorder(fpt, t-＞right); } void main() { FILE *fpt; char word[40];BNODE *root=NULL;if ((fpt=fopen(INF, "r"))==NULL){ printf("Can’t open file %s\n", INF); return;}while(getword(fpt, word)==1) binary_tree( (5) );fclose(fpt);fpt=fopen(OUTF, "w");if (fpt==NULL){ printf("Can’t open fife %s\n", OUTF); return;}midorder(fpt, root);fclose(fpt); }
参考答案：
解析：(1)ptr=*t (2)ptr-＞count++ (3)ptr-＞count=1 (4)t-＞left (5)&root，word
[分析]： 本题考查在C语言中实现字母的统计和有序二叉树的建立及遍历。 题目要求统计一篇英文短文中不同单词及出现次数，并将这些单词及其出现的次数用一棵有序二叉树存储，然后中序遍历该二叉树，将遍历经过的二叉树上的结点的内容输出。内容的输出是按词典编辑顺序将单词及出现次数输出的，因此二叉树的排序是按单词在词典中编辑顺序进行的，并且有序二叉树是动态生成的。 本题目的关键是有序二叉树是动态生成的，我们先来看其生成的步骤： (1)如果相同键值的结点已在二叉排序中，则不再插入，只需修改其count的值即可； (2)如果二叉排序树为空树，则以新结点为根建立二叉排序树； (3)根据要插入结点的键值与插入后父结点的键值比较，就能确定新结点是父结点的左子结点，还是右子结点，并作相应插入。 重复这几步，直到单词统计结束。 下面我们来分析代码。函数getword()已经完全实现了，用来统计短文中的单词，并返回1，说明此单词出现了一次。函数binary_tree()是用来生成有序二叉树的。函数 midorder()用来实现中序遍历。 第(1)空在函数binary_tree()中，结合程序不难看出，此空应该是赋初值，而且是给指针变量ptr赋值。函数binary_tree()的形参中有一个指针变量*t，用来传递待插入到有序二叉树中的结点地址，在这里是让指针变量ptr指向这个地址，因此答案为ptr=*t。 第(2)空在条件判断语句if(!compres)下，而compres存放的是上步的比较结果值，如果条件判断语句结果为真，说明word与ptr-＞word的值相等，即树中已经存在该字母结点，根据有序二叉树的生成步骤知道，不需要再插入，只需修改其count的值即可，因此，第(2)空答案为ptr-＞count++。 第(3)空在动态生成了新结点后面。生成了一个新结点后，自然要对新结点的几个域值进行赋初值，程序中对指针域都赋了空，对字符指针域也赋了值，剩下的只有count值没有被修改，那么此空应该是用来修改count的值。在一个字母对应的结点刚插入树中时，它肯定是第一次出现，因此，此空答案为ptr-＞count=1。 第(4)空在函数midorder()中，此函数的功能是实现对有序二叉树的中序遍历。它是用递归方法来实现的，如果树不为空，应该先对其左子树进行递归遍历，然后才是右子树，因此，第(4)空答案为t-＞left。 第(5)空是当主函数调用函数binary_tree()时，需要传递的参数。根据binary_tree()的定义，我们知道它的第一个参数是指向有序二叉树的二重指针，而第二个参数是指向当前需要处理的字母的指针。在主函数中，表明有序二叉树是一重指针root，而存放当前需要处理字母的是word数组。在一重指针与二重指针进行参数传递时，需要注意加取地址运算符“&”，因此，此空答案为&root，word。