joseph问题代码详解

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


typedef struct node
{
    int data;  //编号
    struct node *next;
}linknode;


//一共n个围坐一圈，编号从1，2，... n。
//从编号为k的人开始报数，从1开始报数
//报到m，出列
int joseph(int n, int k, int m)
{
    //1.创建一个循环链表，存放n个人的信息
    int i;


    //指向创建出的第一个节点
    linknode *L = NULL;
    linknode *p = NULL;


    for(i=0; i<n; i++)
    {
        linknode *p_node = (linknode *)malloc(sizeof(linknode));
        p_node->data = i+1;
        p_node->next = NULL;


        if(L == NULL)
        {
            L = p_node;
            p = L;
        }
        else
        {
            p->next = p_node;
            p = p_node;
        }
    }


    p->next = L;
    
    //2.找到编号为k的人
    p = L;
    for(i=1; i<k ; i++)
    {
        p = p->next;
    }


    i = 1;
    linknode *p_temp;
    //3.开始报数，数到m的人，退出（从链表中删除该节点）
    while(p->next != p)
    {
        if(i == m)
        {
            //删除该节点
            //思路：将下一个结点的数据域复制给当前结点的数据域。然后删除下一个节点
            printf("%d ", p->data);
            p->data = p->next->data;
            //指向要删除的节点
            p_temp = p->next;
            p->next = p_temp->next;
            free(p_temp);


            i = 1;
            continue;
        }


        //继续报数，指针向后移动
        i++;
        p = p->next;
    }
    
    printf("%d\n", p->data);
}




int main(int argc, const char *argv[])
{
    
    joseph(8, 3, 4);


    return 0;
}