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;
}

提前感谢所有有时间和耐心阅读此代码的人。

编辑:

我忘了添加它不能正常工作的地方。 如果出于调试原因我不使用 qsort，并且我使用此输入为例: 5个 2//随机数，我仍然需要执行“打印 k 个字符串”部分， 你好 你好 你好 你好 你好

它打印: 你好 3(频率) 你好 2(频率)

所以它不能正常工作。正如您在评论中所建议的那样，二进制搜索存在缺陷，因为它仅适用于有序列表。我能做的是每次都订购阵列，但我认为这会适得其反。摆脱仅定位数组中不存在的字符串的问题的想法是什么？

Answer 1

如果你想要一种无需排序的高效方法，请使用哈希表。 否则，只需将每个唯一字符串放入一个数组中并对其进行线性扫描，简单可靠。

在现代硬件上，由于缓存和最小化间接寻址，这种扫描实际上速度很快。对于少量项目，插入排序实际上比 qsort 在实践中更有效。以“Tim sort”算法为例，该算法稳定且避免了qsort对接近排序数据的不良性能，它混合了合并和插入排序以实现n Log n，在真实数据上没有极端情况。