Question

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

Answer 1

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

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

　　算法步骤

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

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

　　( )输出该结点元素值;

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

　　算法如下

　　int josephus_ LinkList (LinkList josephus_Link int s int m)

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

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

　　int count;

　　if ( ! josephus_Link)

lishixinzhi/Article/program/sjjg/201311/23072