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

假设我有一个存储book结构和下一个节点指针的链表：

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

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

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

Answer 1

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

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

我认为这是更好的方法。

您甚至可以使用基于链表的更好的数据结构，并将其称为跳过列表。

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

编辑 ：正如其他人评论二进制搜索树将是这个问题的更好的数据结构。

Answer 2

如果你的价格是一个整数，那将很容易：分配一些字节，将它们初始化为0.在你添加价格为m的新书之前，检查这些字节中的第m位，如果它是1，那么你已经有价格; 如果没有，请添加此书并将第m位设置为1.在这种情况下，您无需一次又一次地浏览链表以查找价格，并且存储成本也是有限的。