词频统计 求最大k个数

题外话：想当年，编译原理课偷懒没自己实现这玩意，欠的终究还是要还的，现在补回来了。。。

Write a program for displaying the ten most frequent words in a file

such that your program should be efficient in all complexity measures.

/*（针对大量数据的作法）
思路：每读一个单词 ，存入字典序的平衡二叉搜索树中，这样判断是否新单词或旧单词词频加一
的扫描时间复杂度大大减小；读取完整个文本，建好树后，遍历一遍树，用最小堆存取
词频最大的10个单词，堆顶为词频最小的单词，所以每次只要与堆顶比较，需要替换则重排，
遍历完即出结果
*/
/*
本来打算建一张10个数据结构大小的哈希表，存储10个出现频数最大的单词词频，逐个读短文单词
边插入树结点时边更新表，
之后想若同一单词出现的频数很多，这样同一个单词得更新表很多次，不划算，
不如建好等平衡树后
遍历一遍，找出count最大的十个单词，这样每个不同的单词只遍历一次。
*/
/*
以下程序strcpy虽然能正确执行，但实际上有问题，可以换为如下，我就不换了，就重写个strcpy函数就好
strncpy(path, src, sizeof(path) - 1);
path[sizeof(path) - 1] = '/0';
len = strlen(path);
*/

#include<stdio.h> #include<string> #include<string.h> #include<vector> #include<stdlib.h> using namespace std;#define wordLength 20 #define maxCountNum 10struct AVLTree {char word[wordLength];//单词int count;//计数int height;//树的深度struct AVLTree* lTree;//左子树struct AVLTree* rTree;//右子树 };/*存储出现频率最大的十个结点*/ struct MAXCount {//string word;char word[wordLength];//单词int count;//计数 }; vector <struct MAXCount> maxCount(maxCountNum);/*返回大值*/ int Max(int a,int b); /*返回结点的深度*/ int Height(struct AVLTree* node); /*插入子结点*/ struct AVLTree* insertNode(char *word,struct AVLTree* root); /*删除树所有结点*/ void deleteTree(struct AVLTree** root); /*遍历显示树*/ void display(struct AVLTree* root); /*右旋转*/ struct AVLTree* LLRotate(struct AVLTree* root); /*左旋转*/ struct AVLTree* RRRotate(struct AVLTree* root); /*先左后右旋转*/ struct AVLTree* LRRotate(struct AVLTree* root); /*先右后左旋转*/ struct AVLTree* RLRotate(struct AVLTree* root); /*判断是否是出现频率最多的10个单词 与堆顶最小值比较 是：替换，重排*/ void maxCountWord(struct AVLTree* root); /*去除单词尾的标点符号 并把首字母为大写的转换为小写*/ void punctuationRid_LetterChange(char *temp); /*堆排序 最小堆*/ void heapSort(vector<struct MAXCount> &maxCount, int root, int end); /*结果显示 词频最大的十个单词*/ void showMaxCountWord(); /*返回大值*/ int Max(int a,int b) {return a>b?a:b; }/*返回结点的深度*/ int Height(struct AVLTree* node) {if(node == NULL)return -1;return node->height; }/*按字典序比较strcmp() str1>str2 返回正数str1=str2 返回零str1<str2 返回负数 *//*插入子结点*/ struct AVLTree* insertNode(char *word,struct AVLTree* root) {if(root == NULL){root=(struct AVLTree*)malloc(sizeof(struct AVLTree));strcpy(root->word,word);root->count=1;root->height=0;root->lTree=NULL;root->rTree=NULL;}else if(strcmp(word,root->word) == 0){root->count++;}/*插入左子树*/else if(strcmp(word,root->word) < 0){root->lTree=insertNode(word,root->lTree);if (Height(root->lTree) - Height(root->rTree) == 2) /*AVL树不平衡*/{if (strcmp(word,root->lTree->word) < 0)//LL 右旋转{/*插入到了左子树左边, 做单旋转*/root = LLRotate(root);}else //LR 先左后右{/*插入到了左子树右边, 做双旋转*/root = LRRotate(root);}}}/*插入右子树*/else if(strcmp(word,root->word) > 0){root->rTree=insertNode(word,root->rTree);if (Height(root->rTree) - Height(root->lTree) == 2) /*AVL树不平衡*/{if (strcmp(word,root->rTree->word) > 0)//RR 左旋转{/*插入到了右子树右边, 做单旋转*/root = RRRotate(root);}else //RL 先右后左{/*插入到了右子树左边, 做双旋转*/root = RLRotate(root);}}}root->height=Max(Height(root->lTree),Height(root->rTree))+1;return root; }/*删除树所有结点*/ void deleteTree(struct AVLTree** root) {if(root == NULL || *root == NULL)return;deleteTree(&((*root)->lTree));deleteTree(&((*root)->rTree));free(*root);*root=NULL; }/*遍历显示树*/ void display(struct AVLTree* root) {if(root==NULL)return;static int cnt=0;display(root->lTree);//输出每个单词的词频//printf("[%2d]word:%20s\tcount:%d\r\n",cnt++,root->word,root->count);/*判断是否是出现频率最多的10个单词*/maxCountWord(root);display(root->rTree); }/*右旋转*/ struct AVLTree* LLRotate(struct AVLTree* root) {struct AVLTree* node;node=root->lTree;root->lTree=node->rTree;node->rTree=root;/*结点的位置变了, 要更新结点的高度值*/root->height=Max(Height(root->lTree),Height(root->rTree))+1;node->height=Max(Height(node->lTree),Height(node->rTree))+1;return node; }/*左旋转*/ struct AVLTree* RRRotate(struct AVLTree* root) {struct AVLTree* node;node = root->rTree;root->rTree = node->lTree;node->lTree = root;/*结点的位置变了, 要更新结点的高度值*/root->height=Max(Height(root->lTree),Height(root->rTree))+1;node->height=Max(Height(node->lTree),Height(node->rTree))+1;return node; }/*先左后右旋转*/ struct AVLTree* LRRotate(struct AVLTree* root) {root->lTree=RRRotate(root->lTree);return LLRotate(root); }/*先右后左旋转*/ struct AVLTree* RLRotate(struct AVLTree* root) {root->rTree=LLRotate(root->rTree);return RRRotate(root); }/*判断是否是出现频率最多的10个单词 与堆顶最小值比较 是：替换，重排*/ void maxCountWord(struct AVLTree* root) {if(root->count>maxCount[0].count){//替换strcpy(maxCount[0].word,root->word);maxCount[0].count=root->count;heapSort(maxCount,0,10);} }/*去除单词尾的标点符号 并把首字母为大写的转换为小写*/ void punctuationRid_LetterChange(char *temp) {char *p=temp;if(*p >= 'A' && *p <= 'Z')*p=*p+32;while( *p != '\0')p++;//若最后一个字符不是字母 ，去除--p;if(*p >= 'a' && *p <= 'z');else*p='\0'; }/*堆排序 最小堆*/ void heapSort(vector<struct MAXCount> &maxCount, int root, int end) {for(int j=end-1;j>root;j--){int parent = (j-1-root)/2+root;//parent=（j-1）/2if(maxCount[parent].count > maxCount[j].count){//交换maxCount[parent].count += maxCount[j].count;maxCount[j].count = maxCount[parent].count - maxCount[j].count;maxCount[parent].count -= maxCount[j].count;char temp[20]="word_count";strcpy(temp,maxCount[parent].word);strcpy(maxCount[parent].word,maxCount[j].word);strcpy(maxCount[j].word,temp);}} }/*结果显示 词频最大的十个单词*/ void showMaxCountWord() {printf("------最大词频的十个单词如下-----\r\n");printf("word:\t\t\tcount:\r\n");for(int n=0;n<maxCountNum;n++){printf("%-20s\t%3d\r\n",maxCount[n].word,maxCount[n].count);}printf("------最大词频的十个单词如上-----\r\n"); }int main() {/*打开文件*/FILE *fp;if((fp=fopen("F:\\interview2\\Englishstory.txt","r")) == NULL){printf("File cannot be opened\n");exit(1);}else{/*初始化vector<struct MAXCount> maxCount(10) 建立最小堆*/ char *a="word_count";for(int n=0;n<10;n++){//maxCount[n].word[wordLength]=strcpy(maxCount[n].word,a);maxCount[n].count=0;}heapSort(maxCount,0,maxCountNum);//printf("File can be opened\n");char temp[wordLength];/*依据单词首字母依次转换为26棵树的根节点地址*/struct AVLTree *rootAddress=NULL;/*循环读取文本中的内容*/while((fscanf(fp,"%s",temp)) != EOF){//printf("temp:%s\r\n",temp);/*fscanf读出来的单词若是句尾，则会包含句尾的标点符号，punctuationRid_LetterChange函数 去掉尾的标点 转换头的大写*/punctuationRid_LetterChange(temp);//printf("temp:%s\r\n",temp);rootAddress=insertNode(temp,rootAddress);}display(rootAddress);showMaxCountWord();deleteTree(&rootAddress);/*关闭文件*/fclose(fp);}return 0; }

总结

以上是生活随笔为你收集整理的词频统计 求最大k个数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。