使用c检测文件上的重复行
我有一个大约（15000-25000）行（固定大小）的csv文件，我想知道如何使用c语言检测重复的行。
输出的一个例子是这样的：
0123456789;CUST098WZAX;35 我没有记忆或时间限制，所以我想要最简单的解决方案。
谢谢你的帮助。
#include #include #include struct somehash { struct somehash *next; unsigned hash; char *mem; }; #define THE_SIZE 100000 struct somehash *table[THE_SIZE] = { NULL,}; struct somehash **some_find(char *str, unsigned len); static unsigned some_hash(char *str, unsigned len); int main (void) { char buffer[100]; struct somehash **pp; size_t len; while (fgets(buffer, sizeof buffer, stdin)) { len = strlen(buffer); pp = some_find(buffer, len); if (*pp) { /* found */ fprintf(stderr, "Duplicate:%s\n", buffer); } else { /* not found: create one */ fprintf(stdout, "%s", buffer); *pp = malloc(sizeof **pp); (*pp)->next = NULL; (*pp)->hash = some_hash(buffer,len); (*pp)->mem = malloc(1+len); memcpy((*pp)->mem , buffer, 1+len); } } return 0; } struct somehash **some_find(char *str, unsigned len) { unsigned hash; unsigned slot; struct somehash **hnd; hash = some_hash(str,len); slot = hash % THE_SIZE; for (hnd = &table[slot]; *hnd ; hnd = &(*hnd)->next ) { if ( (*hnd)->hash != hash) continue; if ( strcmp((*hnd)->mem , str) ) continue; break; } return hnd; } static unsigned some_hash(char *str, unsigned len) { unsigned val; unsigned idx; if (!len) len = strlen(str); val = 0; for(idx=0; idx < len; idx++ ) { val ^= (val >> 2) ^ (val << 5) ^ (val << 13) ^ str[idx] ^ 0x80001801; } return val; }
我不确定这是否是最简单的解决方案，但……
如果每个条目看起来像这样：
0123456789;CUST098WZAX;35
…并且最后两个字符始终是00 – 99的值，您可以使用此值来索引存储桶。 此存储桶是100个数组中的一个项（即0-99，与值类似），每个数据块指向存储属于该存储桶的字符串的结构的链接列表。
将字符串分类到存储桶中，识别重复项所需的全字符串比较的数量（希望）大大减少 – 只需比较同一存储桶中的字符串。
如果所有条目具有相同的值，则会将所有条目放在同一个存储桶中，将此方法降级为O（n ^ 2），仅用于比较步骤。 但是假设值的分布不同，这种方法在实践中会更快。
（当然，我只是描述了一个哈希表，但使用的哈希函数比通常使用的更为简单。）
最简单的算法：
- 将原始文件作为行数组A加载到内存中。
- 创建一个相同大小的单独数组B.
- 迭代A.对B中的当前行进行线性搜索。如果不存在，则将其添加到B并输入到输出文件中。
这是非常简单，残酷，低效的O（n ^ 2）解决方案。 假设您具备基本的C技能，那么实施起来非常简单。
顺便说一句，如果订单无关紧要，您可以对文件进行排序，然后任务更加直截了当。 您只需先对文件进行排序，然后为最后一行设置变量，您可以根据该变量检查当前值，如果它等于最后一行，则跳过当前值。