更新时间: 2016-09-23 22:42:29       分类: 算法


#include <iostream>
#include <malloc.h> 

using namespace std;

typedef int Type;

struct node{
	Type data,num;
	node * next;
};

void josephRing(int n,int m)//n为人数,m为初始值
{
	Type temp;
	node * phead = NULL,*p,*q;//p用于开辟新节点,q用于在插入时指向尾部

	//创建链表
	for(int i=1;i<=n;i++)
	{
		cin>>temp;
		p = (node *)malloc(sizeof(Type));
		p->data = temp;//密码
		p->num = i;//标号
		p->next = NULL;

		if(phead==NULL)
			phead = p;//如果链表为空就把新申请的空间当做第一个节点
		else
			q->next = p;//修改尾指针的位置
		q = p;
	}

	q->next = phead;//使链表循环

	
	//开始操作,p当做行走指针,q保存p的前驱
	p = phead;
	
	while(phead->next!=phead)//在只剩下一个人之前执行这个循环
	{
		for(int i=1;i<m;i++) //只用移动m-1次 
		{
			q = p;
			p = p->next;
		}

		//删除p指向的节点
		q->next = p->next;
		
		m = p->data;
		cout<<"编号"<<p->num<<"出列"<<endl;
		
		if(p==phead)//注意这里,删除头节点会导致头指针指向错乱,所以务必在这里修改头指针的指向 
		{
			phead = p->next;
		}
		
		free(p);
		p = q->next;//p已经被释放了这个指针就成了野指针,所以要修正它的指向 
	}

	//只剩下一个人了 直接报出他的编号
	cout<<"编号"<<phead->num<<"出列"<<endl;

}

int main()
{
	int n,m;

	cin>>n>>m;

	josephRing(n,m);

	return 0;
}

评论

还没有评论