约瑟夫环问题

约瑟夫环问题 题目描述

有M个人围坐成一圈， 编号依次从1开始递增，现从编号为1的人开始报数，报到N的人出列，然后再从下一人开始重新报数，报到N的人出列；重复这一过程，直至所有人出列。求出列次序。本题要求用循环单链表实现

输入描述

每行包括M、N两个正整数

输出描述

每个测试用例结果占一行，每个编号占4位

样例输入

10 3

样例输出

3 6 9 2 7 1 8 5 10 4

算法分析

约瑟夫环是一个很有意思的题目的，利用循环链表不断循环，直到链表为空，才停止循环。同时当一个结点重新d出，便重新开始计数。但是在循环链表的创建过程中，首先头节点注意要有赋值，否则下次循环会报错，其次在判断约瑟夫环的过程中，d出一个结点，不用重新设定头节点，直接用count计数即可。

代码演示 链表的结点

typedef struct CNode *Clist;
struct CNode
{
    int data;//数据域
    Clist next;//指针域
};

创建链表

创建链表主要有两种方法，类似与单链表的创建，链表创建有两种创建方法，一种头插法一种尾插法，由于使用头插法创建的结果会使得输入的数据出现倒序，为此推荐使用尾插法来实现。

//创建链表,头插法
void createCList_h(Clist plist,int num)
{
    //创建临时结点
    Clist ltemp;
    for(int i=0;i<num;i++)
    {
        ltemp=(Clist)malloc(sizeof(struct CNode));
        ltemp->data=i+1;

        ltemp->next=plist->next;
        plist->next=ltemp;
    }

}

//尾插法
void createList_R(Clist plist,int num)
{
    
    Clist ltemp,rtemp;
    rtemp=plist;
    for(int i=2;i<=num;i++)
    {
        ltemp=(Clist)malloc(sizeof(struct CNode));
        ltemp->data=i;
        ltemp->next=plist;
        rtemp->next=ltemp;
        rtemp=ltemp;
    }
}

约瑟夫环判断

本判断函数主要的难点在与要使用两个指针，一个指针指向前驱结点，一个指针指向当前结点。主要在d出结点的过程中能够使得接下来的结点仍能维持循环链表的形状。

void yueshefuHuan(Clist plist,int count)
{
    Clist p=plist;
    Clist pNext=plist->next;
    int i=2;
    while(pNext->next!=pNext)
    {
        if(i<count)
        {
            p=p->next;
            pNext=pNext->next;
            i++;
        }
        else{
            printf("%4d",pNext->data);
            p->next=pNext->next;
            free(pNext);
            pNext=p->next;
            i=1;

        }
    }
    printf("%4d",pNext->data);
    free(pNext);

}

遍历函数

//打印链表
void printList(Clist plist)
{
    Clist p=plist;
    while(p->next!=plist)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d",p->data);
    printf("\n");
}

相比与单链表以链表最后的结点是否为null为终止条件，循环链表采用的是用循环链表是判断下一个结点是否是原始链表的头节点来作为循环终止条件

主函数

int main()
{
    int M,N;
    scanf("%d%d",&M,&N);
    Clist plist=(Clist)malloc(sizeof(struct CNode));
    plist->data=1;
    plist->next=plist;
    createList_R(plist,M);
    // printList(plist);
    yueshefuHuan(plist,N);
    // printList(plist);

}

程序运行的所有函数

#include
#include
//构建循环链表的结点
//循环链表将表中的最后一个结点的指针域指向头节点，整个链表形成一个环
//表中任意结点出发均能找到表中其他结点

typedef struct CNode *Clist;
struct CNode
{
    int data;//数据域
    Clist next;//指针域
};


//创建链表,头插法
void createCList_h(Clist plist,int num)
{
    //创建临时结点
    Clist ltemp;
    for(int i=0;i<num;i++)
    {
        ltemp=(Clist)malloc(sizeof(struct CNode));
        ltemp->data=i+1;

        ltemp->next=plist->next;
        plist->next=ltemp;
    }

}

void createList_R(Clist plist,int num)
{
    
    Clist ltemp,rtemp;
    rtemp=plist;
    for(int i=2;i<=num;i++)
    {
        ltemp=(Clist)malloc(sizeof(struct CNode));
        ltemp->data=i;
        ltemp->next=plist;
        rtemp->next=ltemp;
        rtemp=ltemp;
    }
}



void yueshefuHuan(Clist plist,int count)
{
    Clist p=plist;
    Clist pNext=plist->next;
    int i=2;
    while(pNext->next!=pNext)
    {
        if(i<count)
        {
            p=p->next;
            pNext=pNext->next;
            i++;
        }
        else{
            printf("%4d",pNext->data);
            p->next=pNext->next;
            free(pNext);
            pNext=p->next;
            i=1;

        }
    }
    printf("%4d",pNext->data);
    free(pNext);

}

//打印链表
void printList(Clist plist)
{
    Clist p=plist;
    while(p->next!=plist)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("%d",p->data);
    printf("\n");
}


int main()
{
    int M,N;
    scanf("%d%d",&M,&N);
    Clist plist=(Clist)malloc(sizeof(struct CNode));
    plist->data=1;
    plist->next=plist;
    createList_R(plist,M);
    // printList(plist);
    yueshefuHuan(plist,N);
    // printList(plist);

}