/*
约瑟夫Joseph问题（指针）
时间：四月一日
人员：wcn
问题描述：任意n个人围成一圈，每人有一个密码k（整数）；从第一个人（其密码为k1）开始往后计数，数到第k1个人退出；
接着，将退出者的密码k2作为下一个退出依据，继续从下一个人开始计数，数到k2个人退出....依次循环，直到全部人员全部出列。
要求：(1)人数N不确定，用户可以输人任意个人。
(2)用户分别依次输人任意个人名，同时输人每个人的密码k。
(3)用单向、循环链表处理。
(4)输人完成后，给出操作菜单让用户选择操作。
(5)此操作可以反复进行，直到用户选择退出程序。
*/

//头文件引用
#include <stdio.h>
#include <conio.h> //getch() 从控制台读取一个字符，但不显示在屏幕上。原型：int getch(void) 返回值：读取的字符
#include <string.h>
#include <malloc.h>
/*
malloc() memory allocation动态内存分配函数，分配所需的内存空间并返回一个指针，若分配成功返回指向被分配内存的指针,若不成功返回空指针NULL。
原型：void *malloc(size_t,size) 对未分配过的内存块直接进行分配，不会设置内存为零
calloc() 原型：void *calloc(size_t,size_t) 会设置分配的内存为零
realloc() 原型：void *realloc(void *ptr,size_t) 在已经分配过好的内存块的重新分配
*/
#include <stdlib.h>//exit()关闭所有文件，终止正在进行的进程。exit（x）（x不为零）：非正常运行导致异常退出。exit（0）：正常运行程序并退出程序

#define LEN 21 //人名长度（20字符以内）
#define OVER "exit"//输入结束的字符串

//结构体定义
typedef struct ps Person;
struct ps
{
char name[LEN];//姓名
int pwd;//密码password
struct ps* next;
};

//函数声明
Person* head = NULL;//指向表结点的指针
Person* tail = NULL;//指向末节点的指针
char choice; //用户选择的菜单项

void InputPersons();//输入操作，初始化链表
void ShowMenu(); //显示操作菜单
void DisplayLink(); //显示链表信息
void ResetPwd(); //重输密码
void CountAndQuit();//开始约瑟夫游戏

//全局变量声明及初始化
int num = 0;//记录输入人数

//主函数
int main()
{
InputPersons();//调用，进行游戏人员的输入，完成游戏人员的初始化。
while (1)//循环，反复执行显示，重设游戏密码，开始游戏等操作，直到退出。
{
ShowMenu();
switch (choice)//switch(控制表达式) 控制表达式只能是整数型的结果
{
case\'1\':
DisplayLink();
break;
case\'2\':
ResetPwd();
break;
case\'3\':
CountAndQuit();
break;
}
}
}

//输入操作，初始化链表
void InputPersons()//完成人员输入，创建单项循环列表
{
char name[LEN];
Person* p; //新增加的人
head = tail; //初始化指向头和尾的指针，一开始首尾都是NULL
while (1)//接受用户输入
{
printf("请输入第%d个人的信息，输入%s结束：\n", num + 1, OVER);//num=0人数
printf("人名（<=%d个字符）：", LEN - 1);//LEN=21 人名20字符以内
scanf_s("%s", name,sizeof(name));
name[LEN - 1] = \'\0\';

//若输入的是表示退出的字符串，则停止输入，初始化完成
if (strcmp(name, OVER) == 0) //strcmp（s1，s2） string compare 比较两个字符串并根据比较结果返回整数。s1=s2返回0，s1>s2返回正数，s1<s2返回负数。
return;

//否则表示要增加一个参与游戏的人员，于是分配结构体（Person）大小的内存空间
p = (Person*)malloc(sizeof(Person));

strcpy_s(p->name, name);
/*strcpy(s1,s2) string copy 字符串复制并复制结束符
原型：char *strcpy(char*dest,const char *str),表示把src所指向的字符串复制到dest中
dest(destination)目的字符串，str(source)源字符串 ,const（constant常量）：源字符串参数用const修饰，防止修改源字符串 */
//"->"结构体指针运算符，用来访问结构体内部成员 （*p）.a等价于p->a

//输入密码k
//即他出列，该密码作为下一次出列应该数的数字
printf("密码（整数）:");
scanf_s("%d", &p->pwd);

p->next = head;//尾首相连，形成循环,将新节点插入到头节点之前

//创建链表
//若此时头指针head为NULL，表示还没有人员，链表为空，则新来的节点是第一个也是唯一一个节点，于是head和tail均指向它
if (NULL == head)
{
head = tail = p;
p->next = head;
}

//若head不为NULL，表示链表不为空
else
{
tail->next = p;//于是原来指向最后一个节点的指针的下一个节点为新加入的节点
tail = p;//心节点自然就成为新链的最后一个节点
}
num++;//新人添加到链表中以后，计数器才加1，至此表示游戏人员你的单向循环链表形成并不断增加
printf("\n");
}
}

//显示操作菜单
void ShowMenu()
{
while (1)
{
printf("\n\n请选择操作：");
printf("\n==========================");
printf("\n(1)显示信息");
printf("\n(2)重新输入每个人的密码");
printf("\n(3)开始“数N退出”游戏");
printf("\n(0)退出程序");
printf("\n==========================");
choice = _getche();
if (\'0\' == choice)
exit(0);
else if ((choice - \'0\') >= 1 && (choice - \'0\') <= 3)
return;
}
}

//显示菜单信息，供用户操作。
//显示链表当前人员信息，实际上就是对链表节点进行遍历
//由于分别有head和tail指针指向链表的头节点和尾节点，因此只需要从头开始依次移动指针并读取节点信息。
void DisplayLink()
{
int i = 0;
Person* p = head;//从头结点开始
//技巧：始终保持head和tail指针分别指向的链表的第一个和最后一个节点不变，以方便任何时候对链表的节点进行索引和定位。
//为此，新增一个专门用于移动和遍历链表的指针p,一开始指向链表头

//如果没有，就终止
if (NULL == p)
return;

printf("\n\n当前链表信息如下：");
printf("\n=============================");

//先输出头结点
//然后一直循环输人当前节点信息，继续移动到下一个节点，直到重新回到head节点，遍历完成
printf("\n%2d:\t%s\t%d", ++i, p->name, p->pwd);
p = p->next;
while (p != head)
{
printf("\n%2d:\t%s\t%d", ++i, p->name, p->pwd);
p = p->next;
}

printf("\n============================");
}

//重输密码
void ResetPwd()
{
Person* p = head;//从头结点开始

//若没有，则终止
if (NULL == p)
return;

printf("\n\n请重新输入每个人的密码：");
printf("\n===========================");

//先处理第一个人的密码
printf("%s:", p->name);
scanf_s("%d", &p->pwd);//对节点的密码进行修改
p = p->next;
while (p != head)
{
printf("%s:", p->name);
scanf_s("%d", &p->pwd);//修改节点
p = p->next;
}
printf("\n==========================");
}

//开始游戏
void CountAndQuit()
{
int i, n, pwd;//用于计数，和保存当前密码

/*
由于参与游戏的人员信息存放在内存(链表)中，不能像存放在文件中那样可以反复读取，而游戏运行过程中会逐个移除链表节点.
也就是说，一次游戏完成后,节点会全部删除，若想在程序没有退出的情况下，反复玩游戏，就不得不反复重新输人游戏人员信息，
为此，项目实现中采用了“复制链表”的操作，
即:每次游戏时，都将原来的链表“复制”一份，此后的操作在新的链表中进行，原始链表信息保持不变。
*/
//先复制一个链表，
Person* p, * c, * q;//分别指向临时结点，新链表的当前结点，当前结束的前结点
Person* head2 = NULL, * tail2 = NULL;//分别指向新链表的头，尾结点
c = head;

if (NULL == head)//首结点不能为空指针
return;

//复制首结点
p = (Person*)malloc(sizeof(Person));
strcpy_s(p->name, c->name);
p->pwd = c->pwd;
p->next = p;
head2 = tail2 = p;//第一给结点首尾在一起
c = c->next;

//复制其他结点
while (c != head)
{
p = (Person*)malloc(sizeof(Person));
strcpy_s(p->name, c->name);
p->pwd = c->pwd;
p->next = head2;
tail2->next = p;
tail2 = p;
c = c->next;
}

//开始数N退出
printf("\n\n游戏处理结果：");
printf("\n==========================");
i = 0;

//游戏从头节点head2开始，首先获取头节点的密码，作为第一个退出者的计数依据。
c = head2;//将当前指针（用于循环）指向首结点
q = tail2;//q记录当前结点的一个前结点
pwd = c->pwd;//记录首结点的密码

//循环操作，至移动着的当前指针c所指向的节点的下一个节点为自己时（此时表面该节点为最后一个节点，其他节点都已被移除）
while (c->next != c)
{
n = 1;//每次数数时，计数器都为1

//数数，边数边移动当前指针c至数到退出密码指定的数pwd
while(n < pwd)
{
q = c;//记录下当前节点的一个前节点
c = c->next;
n++;
}

//当前指针c所指的应该退出
//由于达到指定的pwd时，c所指的节点要被移除掉，并且移除后要保持链表不能“断链”。
//算法思想是:要删除当前节点c,可以让c的前节点q的next指向C的后节点，然后释放C所指的节点。

//删除c节点
q->next = c->next;
printf("\n第%2d个退出者：%s", ++i, c->name);
pwd = c->pwd;//退出者的密码作为下一个退出的依据
free(c);
c = q->next;
}
//由于当前节点c随时可能被删除，所以在c移动时，设计了一个“跟随指针”q始终指向c的前一个节点，
//在删除时，借助q将c所指向的当前节点删除掉，然后再将指针恢复指向到q的下一个节点，进而继续进行游戏操作。

//退出最后一个
printf("\n第%2d个退出者：%s", ++i, c->name);
free(c);//malloc()分 配的内存空间不再使用后(即节点从链表中移除后)，需要释放节点所占用的内存空间，free(c) 即完成此功能。
printf("\n==========================");
}