【数据结构】约瑟夫死亡游戏（C语⾔实现）
【数据结构】约瑟夫死亡游戏（C语⾔实现）
问题描述：
每30个乘客同乘⼀艘船，因为严重超载，加上风⾼浪⼤，危险万分，因此船长告诉乘客，只有将全船⼀半乘客投⼊海中，其余⼈才能幸免于难。⽆奈，⼤家只得同意这种办法，并议定30个⼈围成⼀圈，由第1个⼈数起，依次报数，数到第9⼈，便把他投⼊⼤海中，然后再从他的下⼀个⼈数起，数到第9⼈，再将他扔到⼤海中，如此循环地进⾏，直到剩下15个乘客为⽌。问哪些位置是将被扔下⼤海的位置。
简单分析：
从题⽬可以看出，需要满⾜这些特征：1、头尾相接，即最后⼀个结点的下⼀个结点是第⼀个结点。2、从第⼀个结点往后数到9，删除该结点，在从下⼀个结点开始重复上述过程。
基于上⾯的分析，循环单链表是⽐较容易实现的。
注意：创建的循环单链表有没有头结点，虽然基本上没有影响，为了⽅⾯不带头结点更好。
算法实现：
1、头⽂件
//定义枚举状态
typedef enum Status
{
success,fail,fatal,range_error
}Status;
//定义循环单链表的结点
typedef struct Listnode {
int person;/*数据域，整型数据1-30*/
struct Listnode *next;/*指针域*/
}Listnode;
typedef Listnode *ListnodePtr;
typedef ListnodePtr List,*ListPtr;
#define MAXSIZE = 30;
Status ListInit (ListPtr L);//初始化函数
Status ListCreate (ListPtr L, ListPtr S,int persondata[],int n);//创建函数
Status ListRemove (ListPtr L,ListPtr S, ListPtr ptr);//删除函数
void Ptrshift(ListnodePtr p, ListPtr ptr);//结点移动函数
2、创建链表，删除结点函数
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"list_JosephDeathGame.h"
//链表的初始化
Status ListInit(ListPtr L){
Status status = fatal;
*L =(ListnodePtr)malloc(sizeof(Listnode));/*分配空间*/
if(*L){
(*L)->next =NULL;
status = success;
}
return status;
}
/
/不带头结点循环链表的创建
Status ListCreate(ListPtr L,ListPtr S,int persondata[],int n){/*L是头指针，S是尾指针*/
c语言struct头文件Status status = fail;
ListnodePtr p, q;
p =(ListnodePtr)malloc(sizeof(Listnode));
q =(ListnodePtr)malloc(sizeof(Listnode));
int i = n -1;/*指向最后⼀个数据元素*/
while(i >=0)
{
p =(ListnodePtr)malloc(sizeof(Listnode));
if(!p){
status = fatal;
break;
break;
}/*空间分配失败，退出*/
p->person = persondata[i];
p->next =NULL;
if(i == n -1){
q = p;
*S = p;
}
else{
p->next = q;
q = p;
}
i--;
}
*L = p;
(*S)->next = p;
if((*L)->person == persondata[0]) status = success;
return status;
}
//删除算法，不同于⼀般的删除算法，结点从头结点依次往后移动9个
Status ListRemove(ListPtr L,ListPtr S, ListPtr ptr){/*ptr为需要删除结点的指针*/ Status status = success;
ListnodePtr  q;
q =(ListnodePtr)malloc(sizeof(Listnode));
if((*ptr)->next ==*L){
q =(*ptr)->next;
(*ptr)->next = q->next;
*L =(*ptr)->next;
free(q);
}/*正好删除了第⼀个结点*/
else if((*ptr)->next ==*S){
q =(*ptr)->next;
(*ptr)->next = q->next;
*S =(*ptr);//*ptr指向倒数第⼆个结点，删除最后⼀个结点⾃然就是尾指针了。free(q);
}/*正好删除最后⼀个结点*/
else{
q =(*ptr)->next;
(*ptr)->next = q->next;
free(q);
}
return status;
}
//每次指针向后移动7步
void Ptrshift(ListnodePtr p,ListPtr ptr){
int j =0;
while(p&&j <7){
p = p->next;
j++;
}
if(p&& j ==7){
*ptr = p;//这样，*ptr指向的删除的结点的前⼀个结点
}
}
3、main函数
int main(){
int person[30];
int i =0;
printf("船上原有30⼈，标号分别为：\n");
while(i <30){
person[i]= i +1;
i++;
printf(" %d ", i);
}
printf("\n");
//不带头结点的循环单链表的初始化和创建
ListPtr L,S;
L =(ListPtr)malloc(sizeof(List));
S =(ListPtr)malloc(sizeof(List));/*初始化头，尾指针的指针*/
Status status = range_error;
status =ListInit(L);
if(status == success){
status =ListCreate( L,S, person,30);
}
else{
printf("链表结点初始化失败！");
return-1;
}
if(status == success)
{
printf("带头指针和尾指针的循环单链表创建成功！\n");
}
else{
printf("链表创建失败！\n");
return-1;
}
//按照要求，循环依次下⼀个第9个⼈删去（~~⼤纲已给出，后⾯代码省略，需要私聊企鹅2407036891~~ ）结果展⽰

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。