数据结构课程设计：约瑟夫生者死者游戏（c++实现、单循环链表、输出死者姓名和编号、附可执行源代码）_用循环链表实现:n个乘客同乘一艘船,因为严重超载,加上风高浪大,危险万分,因此船长

1.1设计内容：

        有N个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难；无奈，大家只得同意这种办法，并议定N个人围成一圈，由第一个人开始，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人开始，数到第9人，再把他投入大海中，如此循环地进行，直到剩下N/2个乘客为止。问哪些乘客是将被投入大海的？输出这些乘客的姓名和位置。

        设计要求：

        掌握单循环链表结构下的基本操作实现算法；能够运用单循环链表的结构特点实现本游戏规则。

        重点难点：

        【本课程设计重点】单循环链表的结构特点和存储。

        【本课程设计难点】单循环链表的建立和表中结点的删除。

1.2 概要设计

A.游戏目录模块：展示一个菜单页面供使用者选择进行约瑟夫游戏或是退出游戏。

B.初始化单循环链表：创建一个单循环链表以供存储乘客信息。

C.输入初始人数模块：用户输入所有乘客数量。

D.上船（录入乘客信息)模块:用户将所有乘客信息输入，并存储在数组中，以供单循环链表使用。

E.进行约瑟夫游戏（输出跳船者信息）模块：依照约瑟夫游戏规则进行筛选，选出需要跳船的乘客。

F.输出剩余人数模块：将最后船上剩余的乘客数量输出。

计难点】单循环链表的建立和表中结点的删除。

1.3 详细设计和编码

        算法设计说明：

        由于约瑟夫生者死者游戏需要从第一人开始依次报数，当有人报至最大数时，该人跳船，然后从下一人开始重新报数，当报数至末尾一人时，则返回第一人报数。因此可以将约瑟夫生者死者游戏看作一个环。

        首先要求用户输入的信息为：

1. 船上的乘客总数，用变量N来表示。
2. 乘客的信息：建立乘客结构体，属性暂定为姓名，用一个字符串数组接收，可修改添加其他属性。
3. 计数最大值M，由于题目要求，将M值固定为9，可根据需要进行修改。

        游戏进行后程序需要输出的信息：

1. 需要跳船的乘客的姓名及编号。
2. 船上剩余的乘客人数

        根据以上题目分析，环状约瑟夫生者死者游戏可以定义一个单循环链表的数据结构来实现算法，首先要定义一个乘客的结构体，以及一个字符串数组，结构体中包含乘客的姓名以及编号，字符串数组用来接收用户输入的乘客姓名。然后定义一个单链表，其中包括数据域（其中存放数据类型为乘客结构体）以及一个指针域。用户需要输入一个乘客人数，在全局区定义int型变量n来接收，同时定义int型变量m，初始化为9，代表报数最大值。

        流程图：

        存储结构说明：

        定义了一个单循环链表的数据结构来实现算法，首先定义一个乘客的结构体，以及一个字符串数组，结构体中包含乘客的姓名以及编号，字符串数组用来接收用户输入的乘客姓名。然后定义一个单链表，其中包括数据域（其中存放数据类型为乘客结构体）以及一个指针域。

        重点函数说明：

        1.void showmenu()

        为用户交互页面，建立一个较为美观的菜单。利用while循环语句与if条件语句实现用户对开始游戏，退出游戏的选择，并且游戏进行一次后，用户依旧可以选择继续开始新游戏还是退出游戏。

void showmenu()
{
	cout << "* * * * * * * * * * * * * * * * * " << endl;
	cout << "*     <约瑟夫生者死者游戏>      *" << endl;
	cout << "*        1----开始游戏          *" << endl;
	cout << "*        2----退出游戏          *" << endl;
	cout << "* * * * * * * * * * * * * * * * * " << endl;
}

        2.void initlist(Linklist& L)

        建立一个单向循环链表并进行初始化，并且在建立循环链表的过程中将各个旅客的编号以及姓名存入结构体的数据域中，并直接存入已定义的乘客结构体。

void initlist(Linklist& L)//初始化单链表
{
	Linklist p, q;
	L = new LNode();
	L->next = NULL;
	L->pa.num = 0;
	p = L;
	for (int i = 0; i < n; i++)
	{
		q = new LNode();
		q->pa.name = name[i];
		q->pa.num = i + 1;
		q->next = NULL;
		p->next = q;
		p = q;
	}
	p->next = L;
}

 3.void choose(Linklist& L)

        实现投入海中的旅客和幸存的旅客的选择。此函数为该问题的核心，即程序中最关键的部分。核心算法需要借助链表的循环，通过while循环与for循环的结合，利用指针的移动来定位要删除的节点，并且将其删除。

void choose(Linklist& L)//选出需要跳船的乘客
{
 
	Linklist p, q;//p表示要出列元素的前驱，q表示要出列的元素
	p = L;
	q = L->next;
	int temp = m;//
	int temp2 = 1;//记录跳船乘客序号
	int a = n; int b = n / 2;
	while (a > b)//当人数大于n/2时则继续选人跳船
	{
		if (temp==1&&q->pa.num!=0)
		{
			p->next = q->next;//改变后继
			temp = q->pa.num;//改变序号
			cout << "第" << temp2 << "个需要跳船的乘客为：" << q->pa.num << "号" << q->pa.name << endl;
			q = q->next;//往后移动一个单位
			a--;
			temp2++;
		}
		else
		{
			if (q->pa.num != 0)
				temp--;
				p = p->next;
				q = q->next;
		}
		
	}
	cout << "跳船后此时船上还剩：" << n - temp2 + 1 << "人。" <<endl<< "祝生者幸福安康！";
}

 1.4 调试分析及运行结果

        

 1.5 源代码

#include<iostream>
#include<string>
using namespace std;
 
int n;//乘客数量
int m=9;//报数上限值
string name[100];//乘客姓名数组
void showmenu()
{
	cout << "* * * * * * * * * * * * * * * * * " << endl;
	cout << "*     <约瑟夫生者死者游戏>      *" << endl;
	cout << "*        1----开始游戏          *" << endl;
	cout << "*        2----退出游戏          *" << endl;
	cout << "* * * * * * * * * * * * * * * * * " << endl;
}
struct passenger//定义一个乘客的结构体
{
	int num;//乘客序号
	string name;//乘客姓名
};
 
typedef struct LNode //创建一个单循环链表
{
	passenger pa;//数据类型为passenger，乘客信息
	struct LNode* next;
}LNode/*单链表中的一个节点*/, * Linklist/*表示一个单链表*/;
 
void initlist(Linklist& L);//初始化单链表
 
void choose(Linklist& L);//选出需要跳船的乘客
 
int main()
{
 
	int ch = 0;
	while (1)
	{
		showmenu();
		cout << "请输入您的选择：";
		cin >> ch;
		if (ch == 1)
		{
			cout << "请输入本船乘客数量：";
			while (1)//要求船上人数必须大于0
			{
				cin >> n;
				if (n > 1)
				{
					break;
				}
				else {
					cout << "请重新输入人数！(人数必须大于1)" << endl;
				}
			}
 
			for (int i = 0; i < n; i++)//上船
			{
				cout << "请输入第" << i + 1 << "个乘客的姓名:";
				cin >> name[i];
			}
			system("pause");
			system("cls");
			Linklist L;
			initlist(L);
			choose(L);
			system("pause");
			cout << "请继续选择：" << endl;
			cout << "1-----重新开始游戏"<<endl;
			cout << "2-----退出游戏" << endl;
			int ch2 = 0;
			cin >> ch2;
			switch(ch2)
			{
				case 1:system("cls"); break;
				case 2:return 0; break;
				defult: 
				{	cout << "无效选择，请重新开始游戏！" << endl;
					system("pause");
					system("cls");
 
				}
			}
		}
		else if (ch == 2)
		{
			cout << "欢迎下次使用！" << endl;
			system("pause");
				return 0;
		}
		else
		{
			cout << "请重新输入正确的选项:" << endl;
		}
	}
}
void initlist(Linklist& L)//初始化单链表
{
	Linklist p, q;
	L = new LNode();
	L->next = NULL;
	L->pa.num = 0;
	p = L;
	for (int i = 0; i < n; i++)
	{
		q = new LNode();
		q->pa.name = name[i];
		q->pa.num = i + 1;
		q->next = NULL;
		p->next = q;
		p = q;
	}
	p->next = L;
}
void choose(Linklist& L)//选出需要跳船的乘客
{
 
	Linklist p, q;//p表示要出列元素的前驱，q表示要出列的元素
	p = L;
	q = L->next;
	int temp = m;//
	int temp2 = 1;//记录跳船乘客序号
	int a = n; int b = n / 2;
	while (a > b)//当人数大于n/2时则继续选人跳船
	{
		if (temp==1&&q->pa.num!=0)
		{
			p->next = q->next;//改变后继
			temp = q->pa.num;//改变序号
			cout << "第" << temp2 << "个需要跳船的乘客为：" << q->pa.num << "号" << q->pa.name << endl;
			q = q->next;//往后移动一个单位
			a--;
			temp2++;
		}
		else
		{
			if (q->pa.num != 0)
				temp--;
				p = p->next;
				q = q->next;
		}
		
	}
	cout << "跳船后此时船上还剩：" << n - temp2 + 1 << "人。" <<endl<< "祝生者幸福安康！";
}