从C中的列表中选择随机节点

Question

我有一个列表,我想从中随机选择一个节点.由于它不是一个阵列,我事先并不知道它的长度.有没有办法随机选择一个节点(均匀分布)而不必扫描整个列表(在最坏的情况下)两次(即获得其长度并在随机选择其位置后到达所选节点)？

这是我用于列表的代码:

struct mynode {
    in_addr_t paddr;
    struct mynode *prev, *next;
};

struct mylist {
    struct mynode *first, *last;
    char *name;
};

Answer 1

根据joop和Ilja Everil\xc3\xa4的评论中的建议，我在 C 中实现了水库采样。

\n\n

struct mynode *select_mynode(struct mylist *list) {\n    struct mynode *list_iter = list->first; // An iterator to scan the list\n    struct mynode *sel_node = list_iter; // The node that will be selected\n    int count = 2; // Temporary size of the list\n    srand((unsigned int) time(NULL)); // Seed\n    // Select a random element in O(n)\n    while (list_iter->next != NULL) {\n        if (rand() % count == (count - 1))\n            sel_node = list_iter->next;\n        list_iter = list_iter->next;\n        count++;\n    }\n    return sel_node;\n}\n

\n\n

注意：有关随机选择的更多信息，请参阅此处。

\n