如何删除结构 C 数组中的重复值

Question

我有一个结构数组，它们按ID排序，数组中存在该ID的重复条目。数组中的每个结构都有与其关联的点数，我想找到每个 ID 的总点数。我想删除任何重复项并将其总点值存储在单个结构中，从而减小数组的大小。

typedef struct boat_data {
int ID;
int time_to_complete_race; //This can be ignored
int points;
} boat_node;
typedef boat_node boat_ptr;

我制作的当前代码似乎没有按预期工作。tot_boats是船只的数量，tot_members是已找到的成员数量(我的意思是存在的非重复ID的数量(。我有两个数组结构，其中final_boat_scores的大小与存在的成员数相同，我想存储ID值和points值

for(int boat = 0; boat < (total_boats - tot_members); boat++) {
for (int next_boat = 0; next_boat < (total_boats - tot_members); next_boat++) {
if (boat_scores[boat].ID == boat_scores[next_boat].ID) {
final_boat_scores[boat].ID = boat_scores[next_boat].ID;
final_boat_scores[boat].points += boat_scores[next_boat].points;
break;
}
}
}

Answer 1

如果您可以更改数组输入，请告诉我。如果是，难道每次需要将新元素存储到数组中时都检查 ID 吗？如果 ID 与已存储的元素匹配，则只需让 recordedPoint += 点(即，将要存储的点直接添加到数组上记录的总点中(。这样，您就不会创建重复的条目。

编辑：由于您无法更改输入数组，因此您可以遍历boat_score数组和final_boat_score数组，并检查当前船的ID是否已记录到final_boat_score数组中。如果是，则只需将其添加到总分中即可。我认为您的代码的问题在于您没有遍历数组中的所有元素，因为您的数组大小绝对不是total_boats - tot_members。你也不需要那final_boat_scores[boat].ID = boat_scores[next_boat].ID;行，因为它是多余的，你的 if 语句只有在这是真的时才执行。 您的break;语句也会过早地结束循环，在这种情况下，您无法提前脱离循环，因为您真的不知道有多少个具有相同ID的条目，对吗？

//remember to initialize final_boat_score first with all IDs you have
for (int i = 0; i < final_boat_score_size; i++) {
//initialize the total point = 0 first
final_boat_score[i].points = 0;
//then loop through your input data
for (int j = 0; j < boat_score_size; i++) {
//if there exist an input element boat_score[j] with the same ID
//as the current final_boat_score[i] element, add its points to the total
if (final_boat_score[i].ID == boat_score[j].ID) {
final_boat_score[i].points += boat_score[j].points;
}
}
}

这不会删除原始数组，因此如果您不再需要它，则需要自己删除它。我希望这有帮助！

Answer 2

越来越多的数据使得排序和删除重复项变得越来越不可行(尽管这可能需要一段时间(。一种是描述由id确定的相等集合。这是一种非常常见的数据结构;例如，在关系数据库中，id将是您的密钥。该集不是每次都删除重复，而是首先不允许重复。常见的实现是实现为从键(在本例中为ID，(到指示键存在的哨兵值的哈希映射的哈希集(任何char或int都可以(。静态集在 gperf 中有一个非常好的C实现，它创建了一个最小的完美哈希，但我相信你想要有动态内容，(这将转化为允许其他竞争对手加入俱乐部。

由于一个键是一个数字，因此从投影创建哈希函数相当容易，

int hash(const struct boat_data *const b) {
return b->ID;
}

许多语言在其标准库中都支持哈希映射(例如，您的问题的JavaScript版本(，但C没有。但是，人们会发现很多实现。请参阅在 C 语言中实现字典的快速方法。此外，uthash，Android(使用void *键，(Git，statsd hashmap(使用字符串，(GHash，HMap。

如果ID是有界的(并且在可计算性范围内(，则创建一个(不是最小的(完美哈希函数很简单。

#include <stdlib.h> /* EXIT */
#include <stdio.h>  /* printf */
static unsigned points_by_id[1000];
static size_t id_size = sizeof points_by_id / sizeof *points_by_id;
int main(void) {
size_t i;
/* First race between [45 36, 10]. */
points_by_id[45] += 45;
points_by_id[36] += 20;
points_by_id[10] += 100;
/* Second race between [10, 12, 45] */
points_by_id[10] += 31;
points_by_id[12] += 40;
points_by_id[45] += 30;
/* Print out. */
printf("Total stadings:n");
for(i = 0; i < id_size; i++) {
if(points_by_id[i])
printf("%lut%un", (unsigned long)i, points_by_id[i]);
}
return EXIT_SUCCESS;
}