约瑟夫问题实现

约瑟夫问题的由来

---

据说著名犹太历史学家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;
}