Вывести 10 самых популярных слов на экран - C (СИ)
Формулировка задачи:
условие задачи: есть текстовый файл ft.txt в него записан текст длиной более 50 слов. Необходимо вывести 10 самый популярный слов на экран
проблема: пытался это реализовать, но не смог, код глючит.
#include <stdio.h>
#include <stdlib.h>
#include <string>
struct word{
char a[30];
int freq;
word *ptr;
}first,tail;
void main(){
char buffer[30]={0};
bool found=false, finish=false;
word *act=&first, *mem=&first, *tmp;
int c=0,d=0,max=0,premax=0;
FILE *f1;
f1=fopen("ft.txt","r");
first.ptr=&tail;
first.freq=1;
fscanf(f1,"%s ",first.a);
while(!feof(f1)){
found=false;
finish=false;
act = &first;
fscanf(f1,"%s ", buffer);
while(act!=&tail){
d++;
if( strcmp(act->a,buffer)>0 ){
printf("d=%d c=%d mem=%s %s else!\n",d,c,mem,buffer);
found = false;
break;
} else if( strcmp(act->a,buffer)==0 ){
printf(" found!\n");
found = true;
act->freq++;
if(act->freq>max)
max=act->freq;
break;
}
mem=act;
act=act->ptr;
}
if(!found){
//printf("\n");
tmp = (word *)malloc(sizeof(word));
sprintf(tmp->a,"%s",buffer);
tmp->freq=1;
mem->ptr=tmp;
tmp->ptr=act;
c++;
printf("\nmem=%s act=%s else!\n",mem,act->a);
}
}
printf("words=%d\n",c);
c=0;
while(c<12){
act=&first;
while(act!=&tail){
if(act->freq>premax && act->freq<max){
premax=act->freq;
//printf("\npremax=%d max=%d",premax,max);
}
if(act->freq == max )
printf("%s freq=%d c=%d\n",act->a,act->freq,++c);
act=act->ptr;
}
max=premax;
premax=0;
}
//printf("\npremax=%d",premax);
fclose(f1);
printf("\nd=%d",d);
getchar();
getchar();
}Решение задачи: «Вывести 10 самых популярных слов на экран»
textual
Листинг программы
#include <stdio.h>
#include <string.h>
int *index;
//----------------------------------------------
struct index_amount
{
int index;
int amount;
};
//----------------------------------------------
void qSort_pchar(char** A, int low, int high)
{
int i = low;
int j = high;
int x = A[index[(low+high)/2]];
int temp;
do
{
while(strcmp(A[index[i]],x) < 0) ++i;
while(strcmp(A[index[j]],x) > 0) --j;
if(i <= j)
{
temp = index[i];
index[i] = index[j];
index[j] = temp;
i++; j--;
}
}
while(i < j);
if(low < j) qSort_pchar(A, low, j);
if(i < high) qSort_pchar(A, i, high);
}
//----------------------------------------------
void qSort_IA(struct index_amount* A, int low, int high)
{
int i = low;
int j = high;
int x = A[(low+high)/2].amount;
struct index_amount temp;
do
{
while(A[i].amount < x) ++i;
while(A[j].amount > x) --j;
if(i <= j)
{
temp = A[i];
A[i] = A[j];
A[j] = temp;
i++; j--;
}
}
while(i < j);
if(low < j) qSort_IA(A, low, j);
if(i < high) qSort_IA(A, i, high);
}
int main()
{
FILE *f;
int i,j,s_length, words_amount, cur_word, cur_struct;
char ** words;
char tmp_buf[128]; // 128 - максимальная длина слова в тексте
struct index_amount* sia;
words_amount = 512; // 512 - макс. число слов в массиве из текста
// + открываем файл
f = fopen("text.txt","r");
if(f == NULL)
{
printf("unable to open test.txt");
}
// + выделяем память для массива words
words = (char**)malloc(sizeof(char*)*words_amount);
// + считываем в массив слова из текста
cur_word = 0;
while(5051)
{
fscanf(f,"%s",tmp_buf);
if(feof(f)) break;
s_length = strlen(tmp_buf);
words[cur_word] = (char*)malloc(sizeof(char)*s_length+1);
strcpy(words[cur_word],tmp_buf);
cur_word++;
}
// + создаем индексный массив (сами строки сортировать трудоемко). Сортировка необходима для ускорения поиска частоты появлнения каждого слова
index = (int*)malloc(sizeof(int)*cur_word);
for(i = 0; i < cur_word; i++)
{
index[i] = i;
}
qSort_pchar(words,0,cur_word-1);
// + выделяем память под массив структур, содержащих позицию в массиве слов и количество вхождений слова
sia = (struct index_amount*)malloc(sizeof(struct index_amount)*cur_word);
// + подсчитываем сколько раз каждое слово встречается в тексте
cur_struct = 0;
for(i = 0; i < cur_word-1; i++)
{
sia[cur_struct].index = index[i];
sia[cur_struct].amount = 1;
j = i+1;
while(j < cur_word && strcmp(words[index[i]],words[index[j]]) == 0)
{
sia[cur_struct].amount++;
j++;
}
i=j-1;
cur_struct++;
}
// + сортируем структуру index_amount, чтобы получить наиболее частотные слова (они с конца структуры)
qSort_IA(sia,0,cur_struct);
// + выводим топ 10
for(i=0; i < 10; i++)
{
printf("word = %s amount = %d\n",words[sia[cur_struct-i].index],sia[cur_struct-i].amount);
}
fclose(f);
free(sia);
free(index);
free(words);
for(i=0; i < words_amount; i++)
{
free(words[i]);
}
return 0;
}
Объяснение кода листинга программы
В данном коде реализована сортировка массива строк (слов) и подсчёт их частоты встречаемости в тексте. Затем, с помощью функции qSort_IA, происходит сортировка массива структур index_amount по убыванию количества упоминаний каждого слова. И, наконец, выводятся 10 наиболее часто встречающихся слов.
Список функций и переменных:
- #include
- подключает файл стандартного ввода/вывода - #include
- подключает файл со стандартными функциями работы со строками - *int index;** - указатель на массив индексов
- struct index_amount - структура, содержащая индекс слова в массиве и количество его упоминаний
- void qSort_pchar(char A, int low, int high)** - сортировка массива строк по возрастанию (без учета регистра)
- *void qSort_IA(struct index_amount A, int low, int high)** - сортировка массива структур
index_amountпо убыванию количества упоминаний - int main() - точка входа в программу
- *FILE f;** - указатель на файл
- int i,j,s_length, words_amount, cur_word, cur_struct; - основные переменные для работы с массивами и циклы
- char words;** - двумерный массив строк (слов)
- char tmp_buf[128]; - временная буферная строка для считывания слов из файла
- *struct index_amount sia;** - указатель на массив структур
index_amount - for(i = 0; i < words_amount; i++) - цикл для работы с массивом
words - free(sia); - освобождение памяти, выделенной под массив структур
index_amount - free(index); - освобождение памяти, выделенной под массив индексов
- free(words); - освобождение памяти, выделенной под двумерный массив строк (слов)
- for(i=0; i < words_amount; i++) - цикл для освобождения памяти, выделенной под каждое слово в массиве
wordsСтоит отметить, что данный код не учитывает некоторые особенности русского языка, такие как мягкий знак, дефис, цифры и знаки препинания в словах. Также он не обрабатывает ошибки, связанные с открытием файла или некорректным форматом данных в нем.