约瑟夫问题.cpp

约瑟夫问题的vc实现代码

#include <iostream.h>
#include <stdlib.h>
struct DNode  //定义双向链表型的节点类
{
	int data;
	DNode *left;
	DNode *right;
};

void InitList(DNode *&HL)//初始化节点
{
	HL=NULL;//表头指针置空
}

int ListEmpty(DNode *HL)//判断链表是否为空
{
	return (HL==NULL);
}

void NewInsert(DNode *&HL,const int &item)//向链表末尾插入新数值
{
	DNode *newptr;
	newptr=new DNode;//为保存新元素分配动态节点
	if(newptr==NULL)//若未分配成功，停止插入，输出错误信息
	{
		cerr<<"Memory allocation failure!"<<endl;
		exit(1);
	}
	newptr->data=item;//新元素保存在newptr的值域中
	newptr->right=newptr->left=HL;//左、右指针指向头节点，便于构成循环链表
	if(HL==NULL)//向空表插入的节点为表头节点
	{
		HL=newptr;
		HL->left=HL;
		HL->right=HL;
	}
    else{
		DNode *p=HL;
		p->left=newptr;
		while(p->right!=HL)//从表头遍历到尾节点
			p=p->right;
		p->right=newptr;//把新节点链接到表尾
		newptr->left=p;
	}
}

void main()
{
	int n,m,i;
    DNode *yue1,*yue2;//定义两个双向链表分别用以存储两队人
	DNode *yue,*pro;//yue用以作动态存储
    InitList(yue1);//初始化两个链表
	InitList(yue2);
	cout<<"请输入约瑟夫问题的总人数: "<<endl;
	cin>>n;
	for(i=1;i<=n;i++)//将每个人对应的号存入yue1链表中
		NewInsert(yue1,i);
	cout<<"请输入每一轮循环的长度: "<<endl;
	cin>>m;
	yue=yue1;//yue指向yue1的头指针
	do{//进行约瑟夫循环出队
		for(i=1;i<m;i++)//遍历找到第m个人
		    yue=yue->right;
		if(yue->right==yue)
		{
			yue1=NULL;
            NewInsert(yue2,yue->data);//将出队人的编号记入yue2队列中
			delete yue;//释放yue所指向的节点空间
		}
		else{//将yue指向的节点从从yue1链表中删除
		    yue->left->right=yue->right;
		    yue->right->left=yue->left;
		    pro=yue;//记录当前节点以便删除和记录其编号
		    yue=pro->right;//yue指向下次遍历的第一个人
		    NewInsert(yue2,pro->data);//将出队人的编号记入yue2队列中
		    delete pro;//释放pro所指向的节点空间
		}
	}while(ListEmpty(yue1)!=1);//到所有人都出队结束
	yue=yue2;//yue指向yue2的表头
	cout<<"出队顺序依次为:"<<endl;
	do{//依次输出每个出队人的编号
		cout<<yue->data<<" ";
		yue=yue->right;
	}while(yue!=yue2);//遍历依次即结束
	cout<<endl;
}