检查c中的链接列表中是否已存在元素

Question

假设我有一个存储书籍结构和下一个节点指针的链表:

struct book {
    unsigned short  size_of_content;
    unsigned short  price;
    unsigned char  *content;
};

struct list {
    struct book p;
    struct list *next;
};

当我构建链接列表时，我将检查新书的价格是否与已链接的其中一本书的价格相同。基本上确保没有重复的价格。

我有一个想法，构建一个价格数组并将新价格与现有价格进行比较。但是，由于 C 不支持无限大小的数组，所以我认为我的方法不是一个好主意。我应该怎么办？谢谢

Answer 1

您不必创建数组或所有这些爵士乐，您只需检查价格是否已存在于链接列表中即可。另一种方法可能是在使用 ma​​lloc 函数将价格添加到动态大小数组的链接列表中时添加价格。 http://www.cplusplus.com/reference/cstdlib/malloc/

但这似乎效率低下，因为即使数组增长到 n 大小，您也必须每次都检查数组。

我认为这是更好的方法。

您甚至可以使用更好的数据结构，它基于链接列表，称为跳跃列表。

在此处阅读跳过列表 http://en.wikipedia.org/wiki/Skip_list这些实际上非常酷。可能值得花时间尝试并以这种方式实现。

编辑:正如其他人评论的那样，二叉搜索树将是解决此问题的更好的数据结构。