检查c中的链表中是否已存在元素 [英] check if an element already exist in a linked list in c

问题描述

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

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

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

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

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

解决方案

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

但是这似乎效率不高，因为即使阵列增加到n个大小，您也必须每次都要检查一次阵列.

我认为这将是更好的方法.

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

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

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

Suppose I have a linked list that stores a book struct and the next node pointer:

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

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

And when I am constructing the linked list, I will check if the new book's price is the same as the price of one of the books that have been linked. Basically make sure that there is no duplicate prices.

I have an idea of constructing an price array and compare the new price with the existing ones. However, since C does not support unlimited size of arrays, I dont think my way is a good idea. What should I do? Thanks

解决方案

Instead of creating an array or all that jazz you could just check if the price already exists in the linked list. Another method could be to add the price as you are adding it to the linked list to a dynamically sized array using the malloc function. http://www.cplusplus.com/reference/cstdlib/malloc/

But that seems inefficient because you will have to check the array every single time even as it grows to n size.

I think that would be the better way to do it.

You could even use a better data structure which is based on a linked list and its called a skip list.

Read here on skip lists http://en.wikipedia.org/wiki/Skip_list These are actually really cool. Might be worth the time to try and implement this way.

EDIT: As the others have commented a binary search tree would be a better data structure for this problem.

这篇关于检查c中的链表中是否已存在元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！