[串] 统计每个单词出现的次数，降序输出（快排）

曾经终败给现在 2022-04-05 07:38 293阅读 0赞

【题目】从键盘输入一系列英文单词，单词用空格分割，结束输入后统计每个单词出现的次数，并按照出现次数降序输出每个单词及其出现的次数。可用strcmp()、qsort()库函数

/* 【问题】从键盘输入一系列英文单词，单词用空格分割，结束输入后统计每个单词出现的次数，并按照出现次数降序输出每个单词及其出现的次数 【说明】可用strcmp()、qsort()库函数 【方法一】使用结构体数组来对单词进行统计，然后使用qsort对次数进行排序 - 不建议 【方法二】事先不清楚单词的个数，使用链表来组织每个单词，再进行排序 - 普通 【拓展】面对海量数据的读取，应该使用键树（Trie树）进行统计，然后用链表组织每个单词，再进行排序 - 海量处理应用实例 */
    
    
    /*【举例】题目中提示用qsort进行排序，那就用方法一，这种方法要实现开辟较大的空间 */
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct{ 
    	char str[255]; //单个单词的长度不能超过255
    	int cnt;
    }Str;
    
    // a=b 返回0
    // a<b 返回负值
    // a>b 返回正值
    int comp(const void *a, const void *b) { 
    	return ((Str *)a)->cnt - ((Str *)b)->cnt;
    }
    
    int main() { 
    	char tmp[255]; //单个单词长度不超过255
    	FILE *fp;
    	Str words[2048]; //单词量不超过2048
    	int num=0;
    	int i;
    	int j;
    
    	fp = fopen("2018-6.txt", "r");
    	while ( fscanf(fp, "%s", tmp)!=EOF ) { 
    		for (i=0; i<num; i++) { 
    			if ( strcmp(tmp, words[i].str)==0 ) { 
    				words[i].cnt++;
    			}
    		}
    		if (i==num) { 
    			// 复制字符串（题目没有给出strcpy，最好不要使用）
    			for (j=0; tmp[j]!='\0'; j++) { 
    				words[num].str[j] = tmp[j];
    			}
    			words[num].str[j] = '\0';
    			// 增加
    			words[num].cnt = 1;
    			num++;
    		}
    	}
    	// 排序
    	qsort(words, num, sizeof(Str), comp); //qsort默认是从小到大排序
    	for (i=num-1; i>=0; i--) { 
    		printf("%s %d\n", words[i].str, words[i].cnt);
    	}
    
    
    	fclose(fp);
    	return 0;
    }