yuesefu.cpp

约瑟夫环源代码,用于解决约瑟夫问题,可以用户自己赋密码值

#include<iostream>
using namespace std;
struct node{
	int ID;
	int pwd;
	int num;
	node* next;
	int Length;
}; 
node* head=NULL;
node* tail=NULL;
int a[7]={3,1,7,2,4,8,4};
/*struct list{
node;
node* current;
node* head;
node* tail;

};*/


//创建链表,并返回链表的头和尾节点
node* creatlist()
{
head=(node*)malloc(sizeof(node));
tail=head;
tail->next=head;
//head->Length=1;
return head;
}//创建链表

//判表非空
int isEmpty(){
	if(head==tail&&head==NULL)
		return 0;
	else 
		return 1;
}//判表非空


//删除当前节点
/*void deleteCurrentNode(node* current){
	if(isEmpty()){

		if(current==head)
		{
		head=head->next;
		tail->next=head->next;
		}
		else
			if(current==tail)
			{
			
			}
	}

}*/


//插入新的节点，并返回当前刚插入的接点的地址
node* insert(){
node* p=(node*)malloc(sizeof(node));
tail->next=p;
p->next=head;//head=p->next;注意方向,这样写会出现严重的错误.
tail=p;
return p;
}


//创建一个循环链表，包含n个节点，并含有各个人的密码
node* initL(int n)
{
	node* p;
	node* current;
	p=creatlist();
	p->ID=1;
	p->pwd=3;
	for(int i=0;i<n;i++){
	current=insert();
	//cout<<"请输入第"<<i+1<<"个人的密码："<<endl;
	//cin>>current->pwd;
	current->ID=i+2;
	current->pwd=a[i+1];

	}
	head=p;
	return p;
}


void find(int m){
	node* pBegin=head;//遍历开始的指针
	node* p;
	node* p1;
	while(head!=head->next){
		p=pBegin;
		p->num=1;//第一个节点报数1
			while((p->num)!=m)//找报数为m的节点
			{	
				p1=p;//记录下p的位置，当p向后指是从而能找到p的前一个位置	
				p=p->next;
			p->num=p1->num+1;//注意此处不要写成p->num++,显然是错误的，因为p 已经指向新的节点，而新节点的num是
							//是没有初始化的
			}
		//循环结束，找到报数为m的节点
		pBegin=p->next;//记录当前节点的下一个位置，作为下次遍历开始的位置
		m=p->pwd;
		cout<<p->ID<<" ";//注意此处应打印ID，而不是他们报的数num
		if(p==tail)
			{
				p1->next=p->next;
				tail=p1;
				free(p);
			}
		else
			{	
				if(p==head)
					{
						tail->next=head->next;
						head=head->next;
						free(p);
					}
				else
					{
						p1->next=p->next;
						free(p);
					}
			}

	}
cout<<head->ID<<" ";
}
int main(){

initL(6);
find(6);
return 0;

}

//总结：本题不需要使用头节点，因为头节点不能赋值，故而当循环遍历时会出现问题，本题开始没有考虑到这一点
//，从而出现了上面这种很别扭的局面。即定义了头节点，却又对其赋值，实际上等于没有头节点。



//测试已经创建的链表
/*int main(){
node* p=NULL;
tail=head=creatlist();
tail->num=3;
for(int i=0;i<3;i++){
insert();

}
p=head->next;
for(int j=0;j<3;j++)
{cout<<(p->pwd)<<" ";
p=p->next;}	
return 0;
}*/