问答题
【说明】
以下【C程序】的功能是从文件text_01.ini中读入一篇英文短文，统计该短文中不同单词和它的出现次数，并按词典编辑顺序将单词及它的出现次数输出到文件word_xml.out中。
该C程序采用一棵有序二叉树存储这些单词及其出现的次数，一边读入一边建立。然后中序遍历该二叉树，将遍历经过的二叉树上节点的内容输出。
程序中的外部函数
int getword(FILE *fpt，char *word)
从与fpt所对应的文件中读取单词置入word，并返回1；若已无单词可读，即到文件尾部时，则函数返回0。
【C程序】
#include ＜stdio.h＞
#include ＜malloc.h＞
#include ＜ctype.h＞
#include ＜string.h＞
#define INF "TEXT_01.INI"
#define OUTF "WORD_XML.OUT"
typedef struct treenode {
char *word;
int count;
struct treenode *left, *right;
} BNODE;
int getword(FILE *fpt,char *word);
void binary tree(BNODE **t,char *word)
{ BNODE *ptr, *p;
int cmpres;
p = NULL;
{{U}} (1) {{/U}};
while (ptr) { /*寻找插入位置*/
cmpres = strcmp(word,{{U}} (2) {{/U}}); /* 保存当前比较结果*/
if (!cmpres) {
{{U}} (3) {{/U}}
return;
}
else {
{{U}} (4) {{/U}};
ptr = cmpres ＞ 0 ? ptr-＞right : ptr-＞left;
}
}
ptr = (BNODE *)malloc(sizeof(BNODE));
ptr-＞right = ptr-＞left = NULL;
ptr-＞word = (char *)malloc(strlen(word)+1);
strcpy(ptr-＞word,word);
ptr-＞count = 1;
if (p == NULL)
{{U}} (5) {{/U}};
else
if (cmpres ＞ 0)
p-＞right = ptr;
else
p-＞left = ptr; }
}
void midorder(FILE *fpt, BNODE *t)
{ if ({{U}} (6) {{/U}})
return;
midorder(fpt , t-＞left);
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({{U}} (7) {{/U}});
fclose(fpt);
fopen(OUTF,"w");
midorder(fpt, root);
fclose(fpt);
}
【正确答案】
【答案解析】(1)ptr=*t
(2)ptr-＞word
(3)ptr-＞count++或其等价形式
(4)P=ptr
(5)*t=ptr
(6)t==NULL 或 !t
(7)&root，word
[要点解析]
这是一道要求读者掌握二叉树应用的程序设计题。本题的解答思路如下。
对于以下结构体定义语句。
typedef struct treenode {
char *word；
int count；
struct treenode *left，*right；
} BNODE；
显然，这是定义了一个用于构造二叉树的数据结构，从结构成员的名字上看，字符指针成员word是用来保存单词的，整型成员count是用来保存该单词在文章中出现次数的。
通过快速浏览程序，不难发现函数binary_tree()大体上是在二叉树中为单词寻找位置并插入，由于没有其他函数进行显式的二叉树创建工作，因此该函数可能还要承担创建二叉树的任务。函数midorder是一个典型的递归算法的中序遍历二叉树，对函数binary_tree()处理的结果进行中序遍历，并将每一个节点的内容写入文件word_xml.out中。而函数mam()则调用这两个函数完成全部处理工作。
首先从main()函数读起。(7)空缺处所在的语句是一个循环的循环体，是对函数binary_tree()的调用。我们看，在这个循环体中，函数getword()每从文章中抽取一个单词，便由函数binary_tree()插入二叉树中，循环结束时已经完成了创建二叉树以及把所有单词都插入二叉树的工作。因为此后已经是对二叉树的中序遍历了。
由于已经明确(7)空缺处需要填写的是函数binary_tree()调用的实际参数表，因此就需要研究函数 binary_tree()的形式参数——“BNODE**t,char*word”。首先，该函数的第2个参数(即char *word)是要插入的单词(这从函数对该参数的使用中也可以看出)。考虑到实际参数是一个数组(即char word[40]；)，而形式参数需要的是一个字符串指针，只要把数组首地址传入即可。因此(7)空缺处所填写的实际参数就应该是“word”。
函数binary_tree()的第1个参数要求是BNODE类型的，通读函数main()，只有一个BNODE类型的变量root(即BNODE *root=NULL；)，那么在(7)空缺处是以何种方式将root传入函数binary_tree()中的()呢?由于形式参数需要一个二级指针，而实际参数是一个指针，因此(7)空缺处所对应的实际参数只能填写"&root"，即把root的地址作为一个常量二级指针传递给函数binary_tree()。
综上所述，(7)空缺处所填写的实际参数是“&root，word”。
阅读函数binary_tree()可知，所传入的BNODE类型变量(*root)需要被函数中的BNODE型变量(*prt)接收。那么这个操作应该在何处完成?由于语句“ptr=cmpres＞0? ptr-＞right：ptr-＞left；”是在二叉树中查找的典型算法。因此BNODE类型变量接收问题是在进入while循环之前完成的，即(1)空缺处所填写的内容是完成该BNODE类型变量接收任务的语句。综合考虑形式参数中所传入变量的类型和ptr的类型可知，(1)空缺处所填写的语句是“ptr=*t”。
在C语言中，如果要比较两个字符串，则可以使用库函数Strcmp()。该函数可以比较两个字符串并根据结果返回一个整数值，具体语法如下：
int strcmp(string str1，string str2)；
其中，str1和str2是两个已声明并已初始化的字符数组，该函数返回负数表示str1小于str2；返回正数表示str1大于str2：返回0表示两个字符串相同。
(2)空缺处所在的语句中“word”要和谁比较，当然是ptr-＞word了，即(2)空缺处所填写的内容是“ptr-＞word”。若比较结果相同时，则需要把该单词的计数加1，即(3)空缺处所填写的语句是“ptr-＞count++”或其等价形式。
(4)空缺处所填写的语句作用比较模糊，可以暂时跳过，继续阅读之后的程序。很明显，(4)、(5)空缺处之间的语句是建立了一个新节点，并将左右链接置空，写入word，写入计数1。
对于(5)空缺处所在的条件判断语句，即
if (p == NULL) {{U}} (5) {{/U}}；
elSe if (cmpres ＞ 0) p-＞right = ptr；
elSe p-＞left = ptr；
其中，(5)空缺处所在的这个if判断也比较难理解。而else部分的if...else体(即p-＞right=ptr；和p-＞left =ptr；)，显然是将新建节点接入二叉树的操作，指针p到底指向哪里?从该句可以判断指针p是查找位置而未找到时的最后一个节点，即ptr由此执行p-＞fight=ptr或者p-＞left=ptr，操作后ptr值为NULL，然后退出while循环。那么指针p和ptr的这种关系是怎样建立起来的?从程序的流程来看，只能是在遍历二叉树的过程中建立起来的，因为p需要随时跟踪ptr的变化。而遍历二叉树部分的C代码并没有实现这样的功能，因此需要在(4)空缺处填写完成这个任务的语句，即“p=ptr”。
有了以上的理解，就不难理解条件判断“p==NULL”的含义了。因为只有在没有进入while循环而直接执行循环以后的语句才会形成这种情况。换言之，p==NULL表示这是第一次调用函数，即ptr是新建的树。此时就需要将新建树的树根回传，以便以后程序调用时使用，因此(5)空缺处所填写的语句是“*t=ptr”(提醒读者想一想，为什么不是t=ptr?)。
(6)空缺处是判断一个条件，以结束对递归函数midorder()的调用。递归函数midorder()何时结束呢?显然当传入的t为空时结束，因为这包含以下两种可能要求结束调用的条件：
1)首次传入的二叉树为空。对于一棵空的二叉树，自然是无须遍历的。
2)遍历结束。遍历结束后再调用递归函数midorder()时，传入的t-＞left或者t-＞fight为空，自然遍历就应该就此结束。
其实以上两个条件表达的意思一样，即(6)空缺处所填写的判断条件是“t==NULL”或“!t”。