用二叉树实现词频统计

xiaoxiao2021-02-28  69

编写程序统计一个英文文本文件中每个单词的出现次数(词频统计),并将统计结果按单词字典序输出到屏幕上。

要求:程序应用二叉排序树(BST)来存储和统计读入的单词。

注:在此单词为仅由字母组成的字符序列。包含大写字母的单词应将大写字母转换为小写字母后统计。在生成二叉排序树不做平衡处理。

【输入形式】

打开当前目录下文件article.txt,从中读取英文单词进行词频统计。

【输出形式】

程序应首先输出二叉排序树中根节点、根节点的右节点及根节点的右节点的右节点上的单词(即root、root->right、root->right->right节点上的单词),单词中间有一个空格分隔,最后一个单词后没有空格,直接为回车(若单词个数不足三个,则按实际数目输出)。

程序将单词统计结果按单词字典序输出到屏幕上,每行输出一个单词及其出现次数,单词和其出现次数间由一个空格分隔,出现次数后无空格,直接为回车。

【样例输入】

当前目录下文件article.txt内容如下:

"Do not take to heart every thing you hear."

"Do not spend all that you have."

"Do not sleep as long as you want;"

【样例输出】

do not take

all 1

as 2

do 3

every 1

have 1

hear 1

heart 1

long 1

not 3

sleep 1

spend 1

take 1

that 1

thing 1

to 1

want 1

you 3

【样例说明】

程序首先在屏幕上输出程序中二叉排序树上根节点、根节点的右子节点及根节点的右子节点的右子节点上的单词,分别为do not take,然后按单词字典序依次输出单词及其出现次数。

二叉树比用数组做词频统计的优势在于,不用事先分配空间,造成浪费或者溢出。以下为带详细注释的源代码:

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #define M 5000 typedef struct node{ int count; char word[26]; struct node *lchild, *rchild; //建立节点的时候 每个节点有左孩子和右孩子 }BTNode, *BTREE; int times = 0; int get_word(char *temp_word, FILE *in); BTREE insert(BTREE T, char temp_word[]); // remember to return a pointer so it can change its real address void inorder(BTREE root); int main() { char temp_word[26] = {0}; /*prepare to put the content of temp_word to real wordblock.word*/ FILE *in; int i,j; if( (in = fopen("article.txt", "r")) == NULL ) printf("No such file!\n"); BTREE root = NULL; //每次insert 都是把根节点当作参数传进去的 while( !feof(in) ) { char temp_word[26] = {0}; get_word(temp_word,in); root = insert(root, temp_word); } printf("%s ", root->word); if(root->rchild != NULL && root->rchild->rchild == NULL) printf("%s\n", root->rchild->word ); else printf("%s ", root->rchild->word ); if(root->rchild->rchild != NULL) printf("%s\n", root->rchild->rchild->word); inorder(root); /*traverse the tree using inorder way 因为是二叉排序树 所以输出就是按照字典序的*/ return 0; } int get_word(char *temp_word, FILE *in) { int i = 0; char temp = '0'; temp = fgetc(in); while( !isalpha(temp) ) { temp = fgetc(in); if(temp==EOF) return 1; } while(isalpha(temp) && !isspace(temp) ) { temp = tolower(temp); temp_word[i] = temp; i++; temp = fgetc(in); } return 0; } BTREE insert(BTREE p, char temp_word[]) { int cond; if(p == NULL) { p = (BTREE)malloc(sizeof(BTNode)); strcpy(p->word, temp_word); p->count = 1; p->lchild = p->rchild = NULL; } else if( (cond = strcmp(temp_word, p->word)) == 0) { p->count++; } else if( cond<0 ) { p->lchild = insert(p->lchild, temp_word); } else { p->rchild = insert(p->rchild, temp_word); } return (p); } void inorder(BTREE T) /*using inorder*/ { if(T!= NULL) { inorder(T->lchild); if( strlen(T->word) >0 ) printf("%s %d\n", T->word, T->count); inorder(T->rchild); } }
转载请注明原文地址: https://www.6miu.com/read-1450158.html

最新回复(0)