c - 使用 GLib 集合删除列表中的重复项

Question

我有一个应用程序可以从 v4l2 设备扫描频率并管理它们。为此有两个功能:

扫描并将找到的频率附加到GList * 电台的功能:

typedef struct {
    GList *stations;
} FreqScanData;

gboolean scan_cb (gpointer data)
{
    static gfloat  freq = FREQ_MIN - 4.0f/STEPS;
    FreqScanData  *fsd = data;

g_assert (fsd);

    if (check_station (freq)) {
        gfloat *f;

        f = g_malloc (sizeof (gfloat));

        *f = freq;
        fsd->stations = g_list_append (fsd->stations, f);
    }

    freq += 1.0/STEPS;

    return TRUE;
}

将 freq 从 GList * 电台 附加到现有列表 GList * 预设 的函数:

typedef struct {
{
    GList *presets;
} Settings;

typedef struct Preset preset;
struct Preset
{
    gchar *name;
    gfloat freq;
};

void scan (void)
{
    FreqScanData data;
    Settings settings;
    GList *node;

    for (node = data.stations; node; node = node->next) {
        preset *ps;

        ps = g_malloc0 (sizeof (preset));
        ps->name = g_strdup (_("unnamed"));
        ps->freq = * ((gfloat *) node->data);                       

        settings.presets = g_list_append (settings.presets, ps);
        g_free (node->data);
    }
}

我需要有关此案的帮助:

如果在data.stations列表中找到并附加的freq已经在settings.presets列表中，< strong>然后不要再次附加它们。

例如:

扫描发现的电台列表:

87.50
92.20
101.50
104.50
106.60

预设列表包含以下项目:

101.50
92.20

-> 不要在结果列表中重复它们

Answer 1

正如 Philip 提到的，使用哈希表(或树)可能会更好。也就是说，这不是你的问题(我认为这就是他在评论中建议它而不是答案的原因)。

如果您想继续使用链表，实际上只有两个选择:每次要插入数据时都进行完整扫描，或者保持数据排序，而完整扫描将成为您的最差 情况，但平均而言您只需扫描一半列表。

自从您使用 g_list_append 以来，您实际上已经在进行全面扫描了而不是g_list_prepend 。要消除重复项，您所要做的就是亲自遍历列表，直到到达末尾，检查每个值以查看频率是否等于您要插入的频率，如果是，则中止插入。但是，最好对预设进行排序，所以...

如果您按频率对列表进行排序，则只需遍历列表，检查每个值以查看每个项目的频率是否等于您要插入的项目。如果是这样，则中止插入。如果不是，并且现有项目的频率大于您尝试插入的值，请在当前项目之前插入该值。如果频率小于您尝试插入的值，请继续执行下一项。它看起来像这样:

static void preset_free (preset* ps)
{
  g_free (ps->name);
  g_free (ps);
}

static int preset_compare (preset* a, preset* b) {
  if (a->freq < b->freq)
    return -1;
  else if (a->freq > b->freq)
    return 1;
  else
    return 0;
}

static GList* insert_or_ignore_sorted (GList* list, preset* ps, GCompareFunc func) {
  GList* cur = list;
  int cmp_res;

  for (; cur != NULL ; cur = cur->next) {
    cmp_res = preset_compare ((preset*) cur->data, ps);
    if (cmp_res == 0) {
      preset_free (ps);
      return;
    }
    if (cmp_res > 0)
      break;
  }

  return g_list_insert_before (list, cur, ps);
}

void scan (FreqScanData* data)
{
  Settings settings = { NULL };
  GList *node;

  for (node = data->stations; node; node = node->next) {
    preset *ps;

    ps = g_malloc0 (sizeof (preset));
    ps->name = g_strdup (_("unnamed"));
    ps->freq = * ((gfloat *) node->data);

    settings.presets = insert_or_ignore_sorted (settings.presets, ps, (GCompareFunc) preset_compare);
    g_free (node->data);
  }
}