约瑟夫环.cpp

数据结构常用算法

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
struct jonse
{
	int code,scr; jonse * next;
};

jonse * create(int); 

void inputscr( jonse*, int);

void showlist(jonse*);

void out(jonse*,int,int);
////////////////////////////////////////////////////////////
void main()
{
	jonse * head;
	int num,val,beg;
	cout<<"\n请输入人员总数:\n";
	cin>>num;
	head=create(num);  //创建链环
	inputscr(head,num);    //输入各人持有密码
	showlist(head);    //输出链环序号
	cout<<"\n输入开始数数的位置:\n";
	cin>>beg;          //输入开始数数的位置
	cout<<"\n输入报数间隔:\n";
	cin>>val;          //输入报数间隔
	cout<<"新序列:\n";
	out(head,beg,val); //输出新序列并删除链表   

}
/////////////////////////////////////////////////////
jonse *create(int n)
{
	jonse * h, * p;
	h=new jonse;
	p=h;
	for(int i=1; i<=n;i++)
	{
		p->code=i;    //赋给每个结点顺序号
		if(i<n){p->next=new jonse; p=p->next;}
        
	}
	p->next=h;        //构成链环
	return h;
}
///////////////////////////////////////////////////
void inputscr(jonse*h,int n)
{
	jonse *p;
	p=h;
	int i;
	for(i=1;i<=n;i++)
	{
		cout<<"第"<<i<<"个人的密码为：";
		cin>>p->scr;
			p=p->next;
	}

}
//////////////////////////////////////////////////////
void showlist(jonse *h)
{
	jonse* p;
	p=h;
	cout<<"编号为："<<'\t';
	do                 //输出链环
	{
		cout<<p->code<<'\t';
		p=p->next;
	}while(p!=h);      //循环条件
	cout<<endl<<endl<<endl;
    cout<<"密码为："<<'\t';
	do                 //输出密码
	{
        cout<<p->scr<<'\t';
		p=p->next;
	}while(p!=h); 
}
//////////////////////////////////////////////////////////
void out(jonse*h,int i,int d)
{
	jonse *p,*q;
	int k;
	p=h;
	   for(k=1;k<i;k++)
	   { q=p; p=p->next;}    //寻找开始报数的位置
    while(p!=p->next)  //处理链环，直至剩下一个结点
	{
		for( k=1;k<d;k++)  //报数
		{ q=p; p=p->next;}
		cout<<p->code<<'\t'; //输出报到d的结点
		d=p->scr;
	    q->next=p->next;   //删除结点
	    delete p;
	    p=q->next;
	}
	cout<<p->code<<endl;   //处理最后一个结点
	free(p) ;
}