2015年初级软考辅导:面试系列2--约瑟夫环问题(Josephus)
发布时间：2010/3/13 14:02:56 来源：城市学习网 编辑：MOON
原题：
用户输入M，N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题Josephus）
提示：
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环链表来描述。设头指针为p，并根据具体情况移动。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组。如：intquit[n];n为一个根据实际问题定义的一个足够大的整数。
代码：
/
created:2006/06/14
filename:C:“DocumentsandSettings“Administrator“桌面mpp“josephus.c
filepath:C:“DocumentsandSettings“Administrator“桌面mpp
filebase:josephus
fileext:c
author:A.TNG
version:0.0.1
purpose:实现Josephus环问题
用户输入M，N值，从1至N开始顺序循环数数，每数到M输出该数值，
直至全部输出。写出C程序。（约瑟夫环问题Josephus）
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
/结构体和函数声明/
typedefstruct_node_t
node_t;
node_tnode_t_create;
node_tnode_t_get;
/功能函数实现/
/
name:node_t_create
params:
n[in]输入要构造的链表的个数
return:
返回构造成功的环形单向链表指针
notes:
构造节点数量为n的环形单向链表
author:A.TNG2006/06/1417:56
/
node_tnode_t_create
{
node_tp_ret=NULL;
if
{
intn_idx=1;
node_tp_node=NULL;
/构造n个node_t/
p_node=malloc);
if
returnNULL;
else
memset);
/内存空间成功/
p_ret=p_node;
