c - c 中的单链表数据结构 : linking a list

Question

我正在尝试在链接列表中选择一个随机节点。我的想法是重新链接列表 n 次，以便每次 n 次头部变化都是不同的值。例如:列表包含他->需要->一些->牛奶。从milk开始，将其链接为另一个列表节点的头，当n-time=2时，头将成为需求。如果n-times=3，则头部变为he。作为一个函数，执行此操作的参数是一个列表和一个随机数。 我的想法写如下:

typedef  struct Stops

 {

    char name[51];

    struct Stops *nxt;
  }Stops;

     Stops *relinking (Stops *alist_torelink, int rndtimes)

  {

    int linkcnt=0; //to count how many times it's been linked, i.e how many links//

    Stops *leknd=NULL;


    while(  alist_torelink!=NULL  && linkcnt < rndtimes  )
    {  
        leknd= (Stops*) malloc(sizeof(Stops));
        strcpy(leknd->name, alist_torelink->name);
        leknd->nxt=alist_torelink;
        linkcnt++;
        if(alist_torelink==NULL) 
        {alist_torelink=leknd;} //so if it reaches the end of the original list, it starts back at the head of the list being relinked and continues. this will mean the loop exits when linkcnt=rndtimes-1//
        alist_torelink=alist_torelink->nxt;
    } return leknd;

     }

这足以有效地获得随机头，但是我没有看到代码存在问题。与包含 5 个元素的原始列表一样，如果创建新列表为 停止 *newlist= relinking(original, 4)，该函数的行为，我不明白，我只能看到创建的 newlist 是

Answer 1

有一种通用算法可以从预先未知长度的列表中选择具有均匀概率的项目，而链表结构通常是它的良好候选者。

它的工作原理是这样的

If empty(list)
   return a non-selection/throw an error
currentItem := firstItem
i := 1
interimSelection := currentItem
While (there is another item)
   i := i + 1
   currentItem := next(currentItem)
   if ( random() <= 1/i )
      interimSelection := currentItem
Return interimSelection

这里 random() 返回范围 [0,1) 上的随机值，因此条件表示“以概率 1/i 选择当前项目。

对于列表中的项目数，该算法的运行时间为 O(n)，并且需要超出列表本身占用的恒定空间。

<小时/>

为了让自己相信此过程可以实现您想要的效果(给您 1/n 的机会获得 n 个项目列表中的每个项目)，请考虑选择第​​ m 个项目必须发生什么:

1. 到达第 m 个项目时必须选择它 (P = 1/m)。
2. 不得选择每个后续项目 (P = (k-1)/k)。

因此第 m 个节点的总概率为

P_m = (1/m) * prod_{k=m+1}^{n} (k-1)/k . 

但是乘积第一项的 (k-1) 是 m+1-1=m，因此可以用原项的分母取消第一项乘积的分子。第二个乘积项的分子抵消了第一个乘积项的分母。依此类推，直到最终结果为1/n。

<小时/>

在 c 中实现它需要您将上面草图中的伪语句转换为代码。

这里有一些建议

• 如果头为NULL，则列表为空
• 通过分配和返回指针来分配和返回项目
• 测试另一个项目是否存在意味着检查当前节点的下一个成员。
• 用于绘制随机值的常用函数返回某个范围 [0,N) 中的整数值，而不是 [0,1) 中的实数，并且 c 中整数算术的行为是这样的，我编写选择条件的方式是不太理想；您应该将其转换为更惯用的形式。