这些天我一直在发布一些代码，因为我正在做一个练习，最后似乎完成了，但我发现它不起作用。这个练习要求输入：
- N 一个整数，表示要读取的字符串数量
- K 一个整数
- N 个字符串
这些字符串可以重复。输出是K个最常见的字符串，按照它们的频率排序（降序）。
例子测试集： 输入：
感谢所有有耐心和时间阅读这段代码的人。
编辑：
我忘了补充一下它存在的问题。 如果由于调试原因我不使用qsort，并且我使用以下输入作为示例： 5 2 //随机数，我仍然需要完成“打印k个字符串”的部分， hello hello hello hello hello
它会输出： hello 3 (频率) hello 2 (频率)
所以它不能正常工作。正如您在评论中建议的那样，二分搜索存在缺陷，因为它只能在有序列表上运行。我可以每次都对数组进行排序，但我认为这样做是适得其反的。如何摆脱只定位不存在于数组中的字符串的问题呢？
例子测试集： 输入：
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个字符串”的部分， hello hello hello hello hello
它会输出： hello 3 (频率) hello 2 (频率)
所以它不能正常工作。正如您在评论中建议的那样，二分搜索存在缺陷，因为它只能在有序列表上运行。我可以每次都对数组进行排序，但我认为这样做是适得其反的。如何摆脱只定位不存在于数组中的字符串的问题呢？
i，但实际上你的数组中可能没有i个值（也可能更少），而且你的数组没有排序，因此你的二分查找无法正常工作。 - Holt