阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 本程序从正文文件text.in中读入一篇英文短文,统计该短文中不同单词及出现次数,并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。 程序用一棵有

admin2010-01-15  31

问题 阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。
    【说明】
   本程序从正文文件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。
转载请注明原文地址:https://jikaoti.com/ti/IXW7FFFM
0

最新回复(0)