#include <bits/stdc++.h>
using namespace std;
#define man 1
#define woman 0
#define maxnamelength 20

typedef struct lnode{
	struct lnode* next;
	int num,sex,age;
	char name[21];
	
}LNode,*Linklist;
//从键盘输入人数N（N<50）及N个人的编号（整型）、姓名、性别和年龄，正向建立带头节点的循环链表；
//输出循环链表各结点的值；
void InitList(Linklist &L);
void DestroyList(Linklist &L); 
bool ListInsert(Linklist L,int pos,int nu,int se,int ag,char* nam);
void PrintList(Linklist L); 
bool findandcut(int &n,int s,int x,int m,Linklist L); 

int main() {
	int t;
	printf("input t:");
	scanf("%d",&t);
	while(t-->0){
		int n;
		printf("input n: ");
		scanf("%d",&n);
		Linklist L=NULL;
		InitList(L);
		
		for(int i=0;i<n;i++){
			int num,sex,age;
			char name[21]={'\0'};
			printf("input num,age,sex(1 for man and 0 for woman),name for node %d: ",i+1);
			scanf("%d,%d,%d,%20s",&num,&age,&sex,name);
			while(getchar()!='\n');//清除缓冲区 
			ListInsert(L,i+1,num,sex,age,name);
		}
		PrintList(L);
		//输入开始报数的人的编号S、间隔的个数M和剩余人数X；
		int s,m,x;
		printf("input s,m,x:(m>0,x>=0) ");
		for(;;){
			scanf("%d,%d,%d",&s,&m,&x);
			if(m>0&&x>=0)break;
			printf("make sure m>0,x>=0,try again: ");
		}
		if(findandcut(n,s,x,m,L))printf("error");
	    DestroyList(L);
	}
	return 0;
}

void InitList(Linklist &L){
	L=(Linklist)malloc(sizeof(LNode));
	if(!L)exit(1);//分配失败异常退出 
	L->next=L;//空表标志 
}

void DestroyList(Linklist &L){
	for(;L->next!=L;){
		Linklist p=L->next->next;
		free(L->next);
		L->next=p;	
	}
	free(L);
	L=NULL;
}

bool ListInsert(Linklist L,int pos,int nu,int se,int ag,char* nam){
	Linklist p=L;
	int cur=0;if(pos<0)exit(1);
	for(;;p=p->next,cur++){
		if(cur==pos-1){
			//插到第pos个，就要找到第pos-1个
			//q指向新建的节点 
			Linklist q=(Linklist)malloc(sizeof(LNode));
			if(!q)exit(1);
			q->num=nu;q->age=ag;
			q->sex=se;strcpy(q->name,nam); 
			q->next=p->next;
			p->next=q;
			return 1;
		}
		if(p->next==L)break; //退出条件放在结尾，头结点至少执行一次 
	}
	//遍历到最后一个也没找到pos，返回1 插入失败 
	return 0;
}
void PrintList(Linklist L){
	Linklist p=L->next;
	int i=1;
	for(;p!=L;p=p->next,i++){
		printf("node %d: num=%d name=%s sex=%s age=%d\n",i,p->num,p->name,p->sex?"man":"woman",p->age);
	}
	
}
bool findandcut(int &n,int s,int x,int m,Linklist L){
	//在循环链表中查找到编号为S的结点；
	//从1开始向后报数，将报M的人（结点）从循环链表中删除，并输出该人的编号；
	//从刚才被删除人的下一个人开始重复上一步，直至最后只剩下 X 个人为止；
	//输出最后剩余的人的编号、姓名、性别和年龄。
	Linklist p=L;
	//空表则不进入循环 
	//1、找S ,防止m为1故从L开始找 
	for(;p->next!=L;p=p->next){
		if(p->next->num==s){
			printf("cut start:\n");
			int no=1;//cut 第no个 
			for(;n>x;n--,no++){
				int count=0;//删去报m的要找到报m-1的 
				int flag=0; 
				for(;count<m-1;p=p->next,count++){
					if(p->next==L)flag++;
				}
				if(p->next==L)p=p->next;//头结点不能删，要跳过去 
				while(flag-->0)p=p->next;
				//每次数到头结点，要用flag记一下，不应该数头结点 
				Linklist q=p->next->next;//保存删去节点的下一个
				printf("NO.%d cut %d\n",no,p->next->num);
				free(p->next);
				p->next=q;
			}
			printf("remained people:\n");
			PrintList(L);
			return 0;	
		} 
		
	}
	return 1;
	//遍历到最后一个也没找到s,异常退出 
}

测试用例（进行5组测试）

5
5
101,25,1,ZhangSan
102,30,0,LiSi  
103,22,1,WangWu
104,28,0,ZhaoLiu
105,35,1,QianQi
104,3,2
3
201,20,1,Tom
202,25,0,Lucy
203,30,1,Jack
201,2,0
4
301,18,1,Student1
302,19,0,Student2
303,20,1,Student3
304,21,0,Student4
301,1,4
1
401,40,1,OnlyOne
401,5,1
2
501,22,1,Test1
502,23,0,Test2
502,-1,1
502,5,1

 一、设计思路

本程序采用带头节点的循环链表数据结构来解决约瑟夫问题。主要设计思路如下：

- 数据结构选择：使用带头节点的循环链表来存储人员信息，头节点不存储实际数据，仅作为链表起始标志

- 模块化设计：将程序功能分解为初始化、插入、打印、删除、销毁等独立函数

- 约瑟夫算法：从指定编号开始报数，每隔M个人删除一个节点，直到剩余X个人为止

- 内存管理：动态分配内存，使用后及时释放，避免内存泄漏

- 输入验证：对用户输入进行合法性检查，确保程序健壮性

 二、代码说明

 1、结构体定义

typedef struct lnode{

    struct lnode* next;    // 指向下一个节点的指针

    int num,sex,age;       // 编号、性别、年龄

    char name[21];         // 姓名（最大20字符）

}LNode,*Linklist;

 2、宏定义

define man 1             // 男性标识

define woman 0           // 女性标识  

define maxnamelength 20  // 姓名最大长度

 3、函数功能说明

 3.1 void InitList(Linklist &L)

- 功能：初始化带头节点的循环链表

- 参数：链表头指针的引用

- 实现：分配头节点内存，设置next指向自身，标志空表

 3.2 void DestroyList(Linklist &L)

- 功能：销毁整个链表，释放内存

- 参数：链表头指针的引用

- 实现：循环释放所有节点，最后释放头节点

 3.3 bool ListInsert(Linklist L,int pos,int nu,int se,int ag,char* nam)

- 功能：在指定位置插入新节点

- 参数：链表头指针、插入位置、编号、性别、年龄、姓名

- 返回值：成功返回true，失败返回false

 3.4 void PrintList(Linklist L)

- 功能：打印链表中所有节点的信息

- 参数：链表头指针

- 输出格式：节点序号、编号、姓名、性别、年龄

 3.5 bool findandcut(int &n,int s,int x,int m,Linklist L)

- 功能：执行约瑟夫问题的核心算法

- 参数：当前人数n（引用）、起始编号s、剩余人数x、间隔m、链表头指针

- 返回值：找到起始节点返回false，未找到返回true

- 算法：定位起始节点后，循环报数删除节点，直到剩余指定人数

 三、运行结果

 五、程序特点

1. 健壮性：对输入参数进行合法性检查，避免非法操作

2. 模块化：各功能独立封装，代码结构清晰

3. 内存安全：动态分配的内存都能正确释放

4. 用户友好：清晰的输入提示和输出格式

5. 算法正确：约瑟夫问题求解逻辑准确，处理各种边界情况