【数据结构】约瑟夫环

#include <stdio.h>
#include <stdlib.h>
#define STATUS int
#define TRUE 1
#define FALSE 0
struct _Node
{
	int data;//数据域
	struct _Node *next;//下个节点
	struct _Node *pre;//上个节点
};
struct LinkList
{
	_Node *head;//表头
	_Node *rear;//表尾
	int len;//当前表长
};
LinkList L;
/**
 * 建立链表函数
 * @param  n  节点数
 * @param  mi 密码数组,从1开始
 * @return    返回建表状态
 */
STATUS CreatLinklist(int n,int mi[])
{
	_Node *p=(_Node *)malloc(sizeof(_Node));
	L.head=p;
	L.len=n;
	_Node *pre=NULL;
	for(int i=1; i<n; i++)
	{
		p->data=mi[i];
		p->next=(_Node *)malloc(sizeof(_Node));
		p->pre=pre;
		pre=p;
		p=p->next;
	}
	p->data=mi[n];
	L.rear=p;
	L.rear->pre=pre;
	L.rear->next=L.head;
	L.head->pre=L.rear;
	return TRUE;
}
/**
 * 删除节点函数
 * @param  p 节点指针
 * @return   返回删除状态
 */
STATUS DelNode(_Node *&p)
{
	p->pre->next=p->next;
	p->next->pre=p->pre;
	free(p);
	return TRUE;
}
int num;
/**
 * 执行函数 
 * @param  m 起始密码
 * @return   执行状态
 */
STATUS Go(int m)
{
	_Node *now=L.head;
	_Node *del;
	while(now->pre!=now->next||now->next!=now)
	{
		for(int i=1; i<m; i++)
		{
			now=now->next;
			num++;
		}
		printf("%d ",now->data);
		m=now->data;
		del=now;
		now=now->next;
		DelNode(del);
		L.len--;
		if(m>L.len)
		{
			m=m%L.len;
			if(m==0)
				m=L.len;
		}
	}
	printf("%dn",now->data);
	return TRUE;
}
int main()
{
	int n,m;
	printf("共n个人，第m个人出列n");
	int mi[1000];
	while(scanf("%d%d",&n,&m))
	{
        num=0;
		for(int i=1; i<=n; i++)
		{
			scanf("%d",&mi[i]);
		}
		if(m>n)
		{
			m=m%n;
			if(m==0)
				m=n;
		}
		CreatLinklist(n,mi);
		Go(m);
		printf("报号次数%dn",num);
	}
}
//7 20 3 1 7 2 4 8 4

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!