数据结构实验1---约瑟夫环（“链表”实现）

[c++]代码库

//改程序用来模拟约瑟夫环游戏，用户输入环中结点个数和初始的密码值
//先打印出产生的结点编号、密码信息，再依次打印出当前密码和出列者的编号
#include<iostream>
#include<ctime>
using namespace std;


struct LNode{//LNode结构体 作为结点元素
	int a, b;
	LNode *next;
};

int createRand(){//createRand函数
	static int i = 0;
	i++;
	srand((unsigned)time(0) + i);//用不同的种子生成随机数
	int a = (rand() % 10 + 2);//产生2-11之间的随机数作为密码
	return a;
}

LNode* createLinkList(LNode *f, LNode *la, int &e1){//createLinkList函数
	int e2;
	cout<<"请输入初始密码："<<endl;
	cin>>e2;
	cout<<endl;
	if(!f)
		return la;
	else{
		f->a = e1;
		e1++;
		f->b = e2;
		f->next = f;
		la = f;
		return la;
	}
}

LNode* insertLinkList(LNode *f, LNode *la, int &e1){//insertLinkList函数 
	LNode *p = f;
	LNode *t = new LNode;
	int createRand();
	int e2 = createRand();
	if(!t)
		return la;
	else{
		t->a = e1;
		e1++;
		t->b = e2;
		while((p->next) != f){
			p = p->next;
		}
		p->next = t;
		t->next = f;
		la = t;
		return la;
	}
}

LNode* deleteLinkList(LNode *f, LNode *la, int &e1, int &e2){//createJoseph函数 e2是当前密码的值
	LNode *p = la;	
	for(int i = 1; i < e2; i++){
		p = p->next;
	}
	la = p;
	f = la->next;
	la->next = f->next;
	LNode *t = f;
	f = la->next;
	e1 = t->a;
	e2 = t->b;
	delete t;
	return la;
}

LNode* createJoseph(LNode *f, LNode *la){//createJoseph函数
	la = NULL;
	int n;
	cout<<"请输入结点个数："<<endl;
	cin>>n;
	static int e1 = 1;	
	la = createLinkList(f, la, e1);
	for(int i = 0; i < n - 1; i++){
		la = insertLinkList(f, la, e1);
	}
	void printCreate(LNode*);//调用测试函数
	printCreate(f);//调用测试函数
	return la;
}

void printJoseph(LNode *f, LNode *la){//printJoseph函数 打印出列的顺序
	int e1 = f->a;
	int e2 = f->b;
	int n = la->a;
	cout<<"出列顺序如下:"<<endl<<endl;
	for(int i = 1; i <= n; i++){
		cout<<"当前密码为:"<<e2<<endl;//监视e2的值
		la = deleteLinkList(f, la, e1, e2);
		cout<<"出列"<<e1<<"号"<<endl;//打出出列结点的编号信息
	}
	cout<<endl;
}

void printCreate(LNode *f){//printCreate函数 输出产生的结点的编号和密码
	LNode *p = f;
	cout<<"产生的结点的序号和密码如下："<<endl;
	while((p->next) != f){
		cout<<p->a<<" "<<p->b<<" "<<endl;//打印结点信息
		p = p->next;
	}
	cout<<p->a<<" "<<p->b<<" "<<endl<<endl;
}

void josephGame(){//josephGame函数
	LNode *f = new LNode;
	LNode *la = NULL;
	la = createJoseph(f, la);
	printJoseph(f, la);
}

void main(){//主函数
	josephGame();
	system("pause");
}