我使用C中的hashtable库函数实现了下面的问题声明。由于我从未在C中使用标准库hashtable,因此我的问题是:
我是否正确使用了哈希表函数(我相信获得输出并不意味着正确使用)?
有没有更好的方法来解决给定的问题陈述?
问题说明:查找数组中n个最频繁的元素。
1-1000000我已经在so上讨论过一些类似的问题,在其中一个answers中,我确实看到推荐的方法是使用哈希表。
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
#include <stdbool.h>
#define REPEAT 3
#define BUFFERSIZE 10
void freqElement(int* arr, int len, int times);
int createHT(int* arr, int len);
int main(void)
{
int arr[] = {2, 3, 5, 6, 10, 10, 2, 5, 2};
int len = sizeof(arr)/sizeof(int);
ENTRY e;
ENTRY *ep;
hcreate(len);
if (!createHT(arr, len))
{
printf(" error in entering data \n");
}
freqElement(arr, len, REPEAT);
hdestroy();
return 0;
}
int createHT(int* arr, int len)
{
ENTRY e, *ep;
for(int i = 0; i < len; i++)
{
char buffer[BUFFERSIZE];
snprintf(buffer, BUFFERSIZE, "%d", arr[i]);
e.key = buffer;
e.data = (void *)1;
ep = hsearch(e, FIND);
if (ep)
{
ep->data = (void *)((int)ep->data + (int)e.data);
}
ep = hsearch(e, ENTER);
if (ep == NULL)
{
fprintf(stderr, "entry failed\n");
exit(EXIT_FAILURE);
}
}
return 1;
}
void freqElement(int* arr, int len, int times)
{
ENTRY *ep, e;
for (int i = 0; i < len; i++)
{
char buffer[BUFFERSIZE];
snprintf(buffer, BUFFERSIZE, "%d", arr[i]);
e.key = buffer;
ep = hsearch(e, FIND);
if(ep)
{
if((int)ep->data == times)
{
printf(" value %s is repeated %d times \n", ep->key, times);
break;
}
}
}
}
最佳答案
我不确定我是否会为这个任务使用hcreate()
,hsearch()
,hdestroy()
三个函数,但它可以使用。POSIX规范在某些问题上并不明确,例如通过htdestroy()
释放密钥,但是MacOSX手册上说:hdestroy()
函数处理搜索表,然后可能调用另一个hcreate()
。调用hdestroy()
之后,数据将不再被视为可访问的hdestroy()
函数为搜索表中的每个比较键调用free(3)
,但不调用与该键关联的数据项。
(posix没有提到在比较键上调用hdestroy()
。)
这里有一个相对简单的代码改编,它可以在free()
下运行,至少在macosx10.11.4上使用gcc 6.1.0和valgrind 3.12.0-svn。
$ gcc -O3 -g -std=c11 -Wall -Wextra -Wmissing-prototypes \
> -Wstrict-prototypes -Wold-style-definition -Werror hs17.c -o hs17
$
代码
#include <search.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFFERSIZE 10
void freqElement(int *arr, int len, int times);
int createHT(int *arr, int len);
int main(void)
{
int arr[] = { 2, 3, 5, 6, 10, 10, 2, 5, 2, 8, 8, 7, 8, 7, 8, 7, };
int len = sizeof(arr) / sizeof(int);
if (hcreate(len) == 0)
fprintf(stderr, "Failed to create hash table of size %d\n", len);
else
{
if (!createHT(arr, len))
fprintf(stderr, "error in entering data\n");
else
{
for (int i = 1; i < len; i++)
freqElement(arr, len, i);
}
hdestroy();
}
return 0;
}
int createHT(int *arr, int len)
{
ENTRY e, *ep;
for (int i = 0; i < len; i++)
{
char buffer[BUFFERSIZE];
snprintf(buffer, sizeof(buffer), "%d", arr[i]);
e.key = strdup(buffer);
e.data = (void *)0;
printf("Processing [%s]\n", e.key);
ep = hsearch(e, ENTER);
if (ep)
{
ep->data = (void *)((intptr_t)ep->data + 1);
if (ep->key != e.key)
free(e.key);
}
else
{
fprintf(stderr, "entry failed for [%s]\n", e.key);
free(e.key); // Not dreadfully important
exit(EXIT_FAILURE);
}
}
return 1;
}
// Check whether this number has been processed before
static bool processed_before(int *arr, int len, int value)
{
for (int j = 0; j < len; j++)
{
if (value == arr[j])
return true;
}
return false;
}
void freqElement(int *arr, int len, int times)
{
ENTRY *ep, e;
for (int i = 0; i < len; i++)
{
char buffer[BUFFERSIZE];
snprintf(buffer, BUFFERSIZE, "%d", arr[i]);
e.key = buffer;
ep = hsearch(e, FIND);
if (ep)
{
if ((intptr_t)ep->data == times && !processed_before(arr, i, arr[i]))
printf(" value %s is repeated %d times\n", ep->key, times);
}
}
}
valgrind
函数防止多次打印多个条目的值-这是对processed_before()
函数的更改的结果,该函数报告具有给定外观数量的所有条目,而不仅仅是第一个这样的条目这并不完全是可取的,但是代码包含一些打印,以便可以监视进度,这有助于确保代码正常工作。示例输出
Processing [2]
Processing [3]
Processing [5]
Processing [6]
Processing [10]
Processing [10]
Processing [2]
Processing [5]
Processing [2]
Processing [8]
Processing [8]
Processing [7]
Processing [8]
Processing [7]
Processing [8]
Processing [7]
value 3 is repeated 1 times
value 6 is repeated 1 times
value 5 is repeated 2 times
value 10 is repeated 2 times
value 2 is repeated 3 times
value 7 is repeated 3 times
value 8 is repeated 4 times
关于c - 在C中的数组中找到n个重复数字,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/36961397/