題外話：想當年，編譯原理課偷懶沒自己實現這玩意，欠的終究還是要還的，現在補回來了。。。

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个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。