2008年上机复试题

题目

（1）用IE从FTP上下载org.dat，并保存在D盘的根目录中。
（2）此文件中按文本方式存放了一段其他文章，其中有若干长度小于15的英 文单词，单词之间用空格分开，无其他符号。
（3）顺序读取这段文章的不同的单词（大小写敏感），同时在读取的过程中排除 所有的单词THE以及变形，即这些单词不能出现在读取的结果中。
（4）将读取的所有单词的首字母转大写后，输出D根目录下new.txt，每个单词一行。
那段文字可以点右键打开方式中用记事本打开，内容是：
The constructor is used to initialize the object The destructor is used to delete the Object the calling sequence of constructor is opposite to the calling sequence of destructor
运行结果是：
Constructor
Is
Used
To
Initialize
Object
Destructor
Delete
Object
Calling
Seqence
Of
Opposite

题目分析

  不知道我为什么看到这样的题目第一个反应就是字典树。因为我的C语言写的十分不熟练，所以这种难一点的对我来说就有了无数的Bug。一般的数组也是可以，思想还简单一点，学长给了代码。好像集合也是可以做，但是考虑到可能只给我们用C（虽然他说C++也是可以的，但是我不信），所以最后还是基本用了C。
  用字典树的话这道题分成三个部分：
  （1）读单词并建树（丁大佬教育我这两个应该分开）：将读到的单词保存，并将它的小写形式与"the"比较。如果不一样的就加入到字典树中。我额外给了一个scount变量表示这个单词有多少个。
  （2）字典树遍历：递归遍历字典树，对所有的单词先转换为小写，然后将首字母转为大写输出。
  （3）删除字典树并释放指针：递归删除，有点像后序遍历。
  需要注意的是一开始读文章中的字母大小写是敏感的，所以一开始建树的时候只能保存单词的原型。

代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Trienode
{
    char sletter;
    int scount;
    Trienode * child[52]; // 前26个存放小写，后26个存放大写
    void initNode(){
        for (int i = 0; i < 52; i++) {
            child[i] = NULL;
        }
        scount = 0;
    }
};

void treeBuild(Trienode * head, FILE *fp);
void treeTraversal(Trienode * node, char * words, int len);
void treeDestroy(Trienode * node);

void main()
{
    FILE * fp = fopen("org.dat", "r");
    if (fp == NULL) {
        printf("FILE OPEN ERROR!\n");
        exit(1);
    }

    char words[20];
    Trienode * head= (Trienode *)malloc(sizeof(Trienode));
    head->initNode();
    treeBuild(head, fp);
    for (int i = 0; i < 52; i++) {
        treeTraversal(head->child[i], words, 0);
    }
    treeDestroy(head);

    fclose(fp);
}

void treeBuild(Trienode * head, FILE *fp)
{
    char temp[20];
    Trienode * t;

    while (fscanf(fp, "%s", temp) != EOF) {
        t = head;
        int i = 0;
        char word[20];
        strcpy(word, temp);
        _strlwr(temp);
        if (strcmp(temp, "the") != 0) {
            while (word[i] != '\0') {
                if (word[i] >= 'a'&& word[i] <= 'z') {
                    if (t->child[word[i] - 'a'] == NULL) {
                        Trienode * n = (Trienode*)malloc(sizeof(Trienode));
                        n->initNode();
                        n->sletter = word[i];
                        t->child[word[i] - 'a'] = n;
                        t = n;
                    }
                    else {
                        t = t->child[word[i] - 'a'];
                    }
                }
                else
                {
                    if (t->child[word[i] - 'A' + 26] == NULL) {
                        Trienode * n = (Trienode*)malloc(sizeof(Trienode));
                        n->initNode();
                        n->sletter = word[i];
                        t->child[word[i] - 'A' +26] = n;
                        t = n;
                    }
                    else {
                        t = t->child[word[i] - 'A' + 26];
                    }
                }
                i++;
            }
        }
        t->scount++;
    }
}

void treeTraversal(Trienode * node, char * words, int len)
{
    if (node == NULL) {
        return;
    }
    words[len] = node->sletter;
    if (node->scount > 0) {
        words[len + 1] = '\0';
        char temp[20];
        strcpy(temp, words);
        _strlwr(temp);
        temp[0] = temp[0] + 'A' - 'a';
        printf("%s\n", temp);
    }
    for (int i = 0; i < 52; i++) {
        if (node->child[i] != NULL) {
            treeTraversal(node->child[i], words, len + 1);
        }
    }
    words[len] = '\0';
}
//  删除树
void treeDestroy(Trienode * node)
{
    if (node == NULL) {
        return;
    }
    for (int i = 0; i < 52; i++) {
        treeDestroy(node->child[i]);
    }
    free(node);
}