约瑟夫问题

问题分析

约瑟夫（Joseph）问题的一种描述是：30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。无奈，大家只好同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置？

1. 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。
2. 为了不失一般性，将30改为一个任意输入的正整数n，而报数上限（原为9）也为一个任选的正整数k。这样该算法描述如下：

（1） 创建含有n个结点的单循环链表；

（2） 生者与死者的选择：

p指向链表第一个结点，初始i 置为1；

while (i<=n/2)   //删除一半的结点

{
   
     
从p指向的结点沿链前进k-1步；

删除第k个结点（q所指向的结点）；

p指向q的下一个结点；

输出其位置q->data；

i自增1；
}

（3） 输出所有生者的位置。

1. 测试结果
   对于总人数30，报数上限为9，则
   死者编号为：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23
   生者编号为：1，2，3，4，10，11，13，14，15，17，20，21，25，28，29

传统的约瑟夫问题可以采用循环数组来解决，在前面介绍vector中就提及过利用循环数组解决约瑟夫问题，那么这里题目要求我们用链表来解决这个问题

那么现在整个流程就分为这么几个阶段，首先要搭建好链表，其次将数据插入进链表中，再把所求元素删除链表外，最后将链表输出即可

==整个流程中需要注意的有下面几个问题==

1. 要解决循环链表问题

通过画图就能知道，每次要让尾节点指向头，每次插入后都需要找到尾节点，改变尾节点的指向

2. 要解决如何找到要删元素的问题

首先说明思路：思路就是把定义一个cur指针，这个指针用来指向要删除的节点，这个思路本身是没有问题的，但是问题在于在实现代码过程中出现了问题

第一个问题在于cur在找要删除元素的过程中是需要经过cur=cur->next，问题就在于循环几次
这个题的要求是删15个元素，每次报到9就删除，因此实际上cur只需要循环8次就能推进到9的位置

第二个问题是删除元素后导致前后不一致的问题，删除元素后如果未对cur节点进行处理，那么cur元素当前位置和最初始的位置实际上是不一样的，假设链表元素是1，2，3...依次排序，那么cur又开始指向1，经过遍历，现在要删除的是元素9，删除掉元素9后，实际上应该对cur再推进一次，这样cur才能指向初始位置的"1"

解决这两个问题后续过程就很简单了，这里代码并没有提前进行宏定义，后续需要进行改变直接进行修改数据即可

代码实现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int LTDataType;
typedef struct ListNode
{
   
   
    LTDataType data;
    struct ListNode* next;
}ListNode;

void ListNodePush(ListNode** phead,LTDataType x)
{
   
   
    assert(phead);
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
   
   
        perror("malloc fail");
        return;
    }
    newnode->data = x;
    newnode->next = NULL;

    if (*phead == NULL)
    {
   
   
        *phead = newnode;
        newnode->next = newnode;
    }
    else
    {
   
   
        ListNode* tail = *phead;
        while (tail->next != *phead)
        {
   
   
            tail = tail->next;
        }
        newnode->next = *phead;
        *phead = newnode;
        tail->next = *phead;
    }
}

void ListNodePop(ListNode** phead,ListNode* cur)
{
   
   
    ListNode* prev = *phead;
    ListNode* next = *phead;
    while (prev->next != cur)
    {
   
   
        prev = prev->next;
    }
    next = cur->next;
    prev->next = next;
    //free(cur);
    //cur = NULL;
}

void ListNodePrint(ListNode* head)
{
   
   
    assert(head);
    ListNode* cur = head->next;
    printf("%d->", head->data);
    while (cur!=head)
    {
   
   
        printf("%d->", cur->data);
        cur = cur->next;
    }
}

int main()
{
   
   
    ListNode* plist = NULL;
    for (int i = 30; i > 0; i--)
    {
   
   
        ListNodePush(&plist, i);
    }
    int a = 15;
    ListNode* cur = plist;
    while (a--)
    {
   
   
        for (int i = 0; i < 8; i++)
        {
   
   
            cur = cur->next;
        }
        ListNodePop(&plist, cur);
        cur = cur->next;
    }
    ListNodePrint(plist);
    return 0;
}