joseph.cpp

1． 以单项循环链表存储结构模拟约瑟夫环问题。即编号为1、2、3…、n的n个人按顺时针方向围坐一圈

#include <stdlib.h>
#include <iostream.h>

typedef struct Node 
{  
	int num,password;
	Node *next;
}Node, *LinkList;

void main()
{
	int m, n, a;                                 //m为报数上限，n为人数，a密码;
	cout << "请输入报数上限和人数：";
	cin >> m >> n;
	LinkList head,p,pre;                    //head 为头指针，tail为为指针，pre为p 的前一个结点
	head  = (LinkList)malloc(sizeof(Node));//生成第一个结点
	p = head;

	for ( int i=1; i<n; i++ )
	{
		pre= (LinkList)malloc(sizeof(Node));       //生成人数结点
		p -> next = pre;
		p = pre;
	}
	p -> next = head;                       //最后一个人的下一个人为第一个人
	pre = head;

	cout << "请依次输入" << n << "个人的密码：";
	for ( i=1; i<=n; i++)
	{
		cin >> a;
		pre ->num = i;
		pre ->password = a;
		pre = pre ->next;
	}
	pre = p;

	cout << "出列顺序为：";
	for (i=1; i<=n; i++)
	{
		for (int j=1; j<m; j++)
		{
			pre = pre -> next;
		}
		p = pre -> next;
		m = p -> password;
		cout << p->num << " ";
		pre -> next = p -> next;
		free (p);
	}
	cout << endl;
}