2008年苏州大学上机复试题

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