数据结构之单链表基本运算的实现[18]

【例】用链表求解约瑟夫问题

算法思路由于约瑟夫问题是n个人围坐一圈所以采用循环链表实现又由于报数时可能循环到开始所以采用不带头结点的循环链表结构

算法步骤

()在不带头结点的循环链表中查找第s个结点用p作为第s个结点的指针pre指向p 的前驱;

()从p所指的结点开始计数查找第m个结点;

()输出该结点元素值;

() 删除该结点同时将该结点下一结点指针作为当前指针即p指针重复到步骤()直到链表中所有结点都被删除完为止

算法如下

int josephus_ LinkList (LinkList josephus_Link int s int m)

{ /*求约瑟夫问题的出列元素序列入口参数已经存放数据的链表头指针起始位置s数m 出口参数表示成功表示表中没有元素*/

LinkList ppre; /*p指向当前结点pre指向其前驱结点*/

int count;

if ( ! josephus_Link)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []