(已验证)约瑟夫环问题(Josephus)

#include //在使用标准函数库中的输入输出函数时，编译系统要求程序提供有关的信息,调用库函数
#include
#include
#include
#include

/* 结构体和函数声明 */
typedef struct _node_t
{
int n_num;
struct _node_t *next;
} node_t;

node_t *node_t_create(int n);
node_t *node_t_get(node_t **pn, int m);

/* 功能函数实现 */

/*
* name: node_t_create
* params:
* n [in] 输入要构造的链表的个数
* return:
* 返回构造成功的环形单向链表指针
* notes:
* 构造节点数量为 n 的环形单向链表
*
*/
node_t *node_t_create(int n)
{
node_t *p_ret = NULL;

if (0 != n)
{
int n_idx = 1;
node_t *p_node = NULL;

/* 构造 n 个 node_t */
p_node = (node_t *)malloc(n*sizeof(node_t));
if (NULL == p_node)
return NULL;
else
memset(p_node, 0, n*sizeof(node_t));

/* 内存空间申请成功 */
p_ret = p_node;
for (; n_idx < n; n_idx++)
{
p_node->n_num = n_idx;
p_node->next = p_node+1;
p_node = p_node->next;
}
p_node->n_num = n;
p_node->next = p_ret;
}

return p_ret;
}

/*
* name: main
* params:
* none
* return:
* int
* notes:
* main function
*
*/
int main()
{
int n, m;
node_t *p_list, *p_iter;
cout<<" 约瑟夫生者死者游戏"<cout<<"请输入死刑犯的人数(大于等于零):";
cin>>n;
if(n<0)
{
cout<<"请重新输入死刑犯人数,谢谢合作~O(∩_∩)O~"<cout<<"请输入死刑犯的人数(大于等于零):";
cin>>m;
}
cout<<"请输入报数间隔:";
cin>>m;

/* 构造环形单向链表 */
p_list = node_t_create(n);
printf("死刑犯赴死顺序为(最后一个为其中的lucky dog):");
/* Josephus 循环取数 */
p_iter = p_list;
m %= n;
while (p_iter != p_iter->next)
{
int i = 1;

/* 取到第 m-1 个节点 */
for (; i < m-1; i++)
{
p_iter = p_iter->next;
}

/* 输出第 m 个节点的值 */
printf("%d\n", p_iter->next->n_num);
/* 从链表中删除第 m 个节点 */
p_iter->next = p_iter->next->next;
p_iter = p_iter->next;
}
printf("%d\n", p_iter->n_num);

/* 释放申请的空间 */
free(p_list);

system("PAUSE");
}