约瑟夫（链表实现）.cpp

树的遍历等数据结构程序代码实现

#include<iostream>
#include<string.h>
using namespace std;

struct Node
{
	int data;
	struct Node *next;
};

Node *creatlist(int);
//void displist(Node *,int);
void joseph1(Node *,int,int);
void joseph2(int,int,int []);


void main()
{ 
	cout<<"输入参数："<<endl;
	int m,n;
	Node *u;
	cout<<"席上总人数n=:";cin>>n;
	cout<<"约定报的数m=:";cin>>m;
	cout<<endl;
	u=creatlist(n);
	//displist(u,n);
	cout<<"链表实现结果如下: ";
	joseph1(u,m,n);
	cout<<endl;

    int *M=new int[n];  //创建数组，存储退席序号
    for(int i=1;i<=n;i++)
	  M[i]=i;        
    cout<<"数组实现结果如下: ";
	joseph2(m,n,M);
	cout<<endl;
}


Node *creatlist(int n)   //创建循环链表
{ 
	Node *head,*u,*q;
	head=(Node *)new(Node);
	head->data=1;          
	head->next=head;
	u=head;
	for(int i=2;i<=n;i++)  //添加节点
	{ 
		q=(Node *)new(Node);
		q->data=i;           //数据域放那个人的编号
		q->next=u->next;
		u->next=q;
		u=q;
	}
	return u;              //返回最后节点的地址
} 


/*void displist(Node *u,int n)
{ 
cout<<"链表节点值:";
for(int i=1;i<=n;i++)
{ 
u=u->next;
cout<<u->data;
}
cout<<endl;
}*/


void joseph1(Node *u,int m,int n)//链表实现
{ 
	int *L=new int[n];      //n个人，报的数为m
	int j=1;                //设从第1个人报数
	Node *p;
	p=u;                    //设置遍历指针，指向最后节点
	while(p->next!=p)       //剩一个节点，退出循环
	{ 
		Node *q;
		q=p->next;            //跟踪指针，指向开始数数那个人
		for(int i=m-1;i>0;i--)  //遍历节点
		{
			q=q->next;
			p=p->next;
		}
		L[j]=q->data;           //暂存出列人编号
		p->next=q->next;        //删除节点
		delete q;     
		j++;                    //从下个人开始数数
	}
	L[j]=p->data;           //存入最后一个人的编号
	delete p;           
	for(j=1;j<=n;j++)
		cout<<" "<<L[j];
}


void joseph2(int m,int n,int L[])//数组实现
{           
	int s=1;                     //设从第1个人开始报数
	for(int j=n;j>1;j--)
	{ 
		s=(s+m-1)%j;               //下一个出列人的序号
		if(s==0) s=j;
		int t=L[s];            //暂存出列人原编号
		for(int k=s;k<=j-1;k++)//移动数组数据，删除出列人
			L[k]=L[k+1];
		L[j]=t;                //将出列人移到数组尾
	}
	for(int i=n;i>=1;i--)        //打印出列人编号
		cout<<" "<<L[i];
}