C - Распечатайте наиболее часто используемые строки

Question

В эти дни я отправляю код, потому что делаю упражнение, в конце концов, кажется, что я его закончил, но я заметил, что он не работает. Упражнение на вход: - N целое число, представляющее число строк для чтения - K целое число - N строк Строки могут быть дублирующими. На выходе имеется печать наиболее часто используемых строк K, упорядоченная по их частоте (порядок уменьшения).

Пример набор тестов:

Вход:

6 
2 
mickey 
mouse 
mickey 
hello 
mouse 
mickey 

Выход:

mickey // Has freq 3 
mouse // Has freq 2 

Я надеюсь, что я объяснил упражнение в хорошем смысле, так как это моя попытка ,

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

typedef struct _stringa { 
    char* string; 
    int freq; 
} stringa; 


int compare(const void *elem1, const void *elem2) { 
    stringa *first = (stringa *)elem1; 
    stringa *second = (stringa *)elem2; 

    if (first->freq < second->freq) { 
     return -1; 
    } else if (first->freq > second->freq) { 
     return 1; 
    } else { 
    return 0; 
    } 
} 

int BinarySearch(stringa** array, char* string, int left, int right) { 
    int middle; 
    if (left==right) { 
     if (strcmp(string,array[left]->string)==0) { 
      return left; 
     } else { 
      return -1; 
     } 
    } 
    middle = (left+right)/2; 
    if ((strcmp(string,array[middle]->string)<0) || (strcmp(string,array[middle]->string)==0)) { 
     return BinarySearch(array, string, left, middle); 
    } else { 
     return BinarySearch(array, string, middle+1, right); 
    } 

} 


int main (void) 
{ 
    char value[101]; 
    int n = 0; 
    int stop; 
    scanf("%d", &n); // Number of strings 
    scanf("%d", &stop); // number of the most frequent strings to print 

    stringa **array = NULL; 
    array = malloc (n * sizeof (struct _stringa *)); 

    int i = 0; 

    for (i=0; i<n; i++) { 

     array[i] = malloc (sizeof (struct _stringa)); 
     array[i]->string = malloc (sizeof (value)); 

     scanf("%s", value); 

     int already; 
     already = BinarySearch(array, value, 0, i); // With a binary search, I see if the string is present in the previous positions of the array I am occupying. If it is not present, I copy the string into the array, otherwise, I use the value of binary search (which is the position of the element in the array) and I update the frequency field 


     if (already==-1) { 
      strcpy(array[i]->string,value); 
      array[i]->freq = 1; 
     } else { 
      array[already]->freq += 1; 
     } 

    } 


    stringa **newarray = NULL; // New struct array of strings 
    newarray = malloc (n * sizeof (struct _stringa *)); 

    int k = 0; 
    for (i=0; i<n; i++) { // I use this loop to copy the element that don't have a frequency == 0 
     if (array[i]->freq != 0) { 
      newarray[k] = malloc(sizeof(struct _stringa)); 
      newarray[k] = malloc(sizeof(value)); 
      newarray[k]->string = array[i]->string; 
      newarray[k]->freq = array[i]->freq; 
      k++; 
     } 
    } 
     qsort(newarray, n, sizeof(stringa*), compare); 

     i=0; 
     while ((newarray[i]!= NULL) && (i<k)) { 
      printf("%s ", newarray[i]->string); 
      printf("%d\n", newarray[i]->freq); 
      i++; 
     } 


// Freeing operations   

    while (--n >= 0) { 
     if (array[n]->string) free (array[n]->string); 
     if (array[n]) free (array[n]); 
    } 

    if (array) free (array); 
    if (newarray) free (newarray); 

    return 0; 
} 

Благодарим вас заблаговременно всем, у кого будет время и терпение, чтобы прочитать этот код.

EDIT:

Я забыл добавить, что это не работает правильно. Если я не использую QSort для отладки причинам, и я использую этот вход, например: 2 // случайное число, я до сих пор сделать «напечатать K строк» ​​часть, привет привет привет привет привет

он печатает: привет 3 (частота) привет 2 (частота)

Так он не работает должным образом. Как вы сказали в комментариях, двоичный поиск ошибочен, поскольку он работает только в упорядоченном списке. То, что я могу сделать, это упорядочить массив каждый раз, но я думаю, что это будет контрпродуктивным. Какова может быть идея избавиться от проблемы поиска только строк, отсутствующих в массиве?

Answer 1

Если вы хотите использовать эффективный метод без сортировки, используйте хеш-таблицу. В противном случае просто поместите каждую уникальную строку в массив и сканируйте ее линейно, просто и надежно.

На современном оборудовании этот вид сканирования на самом деле быстрый из-за кэшей и минимизации косвенности. Для небольшого количества элементов сортировка вставки фактически более эффективна, чем на практике qsort. Рассматривая алгоритм «сортировки по типу», который является стабильным и позволяет избежать низкой производительности qsort с почти отсортированными данными, он смешивает сортировки слияния и вставки для достижения n Log n, без крайних случаев для реальных данных.