据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
通过上面的问题描述可以将自杀的过程抽象为循环链表的节点删除
完成方法如下:
/*结构*/
typedef struct Node{
int data;
struct Node *next;
}*PtrNode;
/*返回状态*/
typedef enum Status{
_Success_,
_Fail
}Status;
/***************************************************
* 函数名称:InitJoseph(PtrNode jop_list, int n)
* 功能描述:初始化约瑟夫循环链表
* 传入参数:PtrNode jop_list 待初始化的循环链表
* int n 一共有n个结点
* 返回值:_Success_ 成功
* _Fail 失败
**************************************************/
Status InitJoseph(PtrNode jop_list,int n)
{
Status _outcome_ = _Fail;
int i;
jop_list = (PtrNode)malloc(sizeof(struct Node));
PtrNode temp = NULL,Tail = NULL;
if(jop_list != NULL)
{
jop_list ->data = n;/*头结点保存人数*/
jop_list ->next = NULL;
Tail = jop_list;
for(i =1; i <= n; i++)
{
temp = (PtrNode)malloc(sizeof(struct Node));
if(NULL != temp)
{
temp -> data = i;
temp -> next = NULL;
Tail -> next= temp;
Tail = temp;
}
}
Tail ->next = jop_list ->next;/*最后一个结点指向头结点的下一个结点,组成环*/
_outcome_ = _Success_;
}
return _outcome_;
}
/***************************************************
* 函数名称:DeleteJosephNode(PtrNode list, int k)
* 功能描述:删除从n开始之后的第k个结点
* 传入参数:PtrNode list 传入的循环链表
* int k 删除第k个结点
* 返回值:_Success_ 成功
* _Fail 失败
**************************************************/
Status DeleteJosephNode(PtrNode list, int k)
{
Status _outcome = _Fail;
int i;
PtrNode tem = list;
PtrNode p = list -> next;
PtrNode out;
while(p -> next -> next !=p)/**/
{
for(i = 1; i < k-1; i++)
{
tem = tem -> next;
}
p = temp -> next;
out = temp -> next;
temp -> next = out -> next;
printf("%d号----->自杀\n",out -> data);
free(out);
_outcome = _Success_;
}
printf("%d--->幸存!\n%d--->幸存!\n",(p -> data), ((p -> next) -> data));
free(p);
return _outcome;
}
如对本文有疑问, 点击进行留言回复!!
故事向|在3A游戏公司工作多年的3D建模师自述,制作3A大作经验心得(上)
「建模学习」zbrush中如何制作拉链?拉链笔刷来帮忙,轻松搞定
LeetCode hot-100 简单and中等难度,21-30.
Second season eighth episode,Ross made a list about Rachel,compared to Julie??!!
2020.08.07 J - MaratonIME goes to Mito
网友评论