约瑟夫环

曾经终败给现在 2022-02-28 00:54 237阅读 0赞

约瑟夫环：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

定义很简单，根据定义，采用循环链表来实现，有一点需要注意的是边界问题，把边界问题处理好了，程序就容易真正实现了。以下是代码：

//约瑟夫环
    
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Linklist
    {
        int data;
        struct Linklist * next;
    }ListNode,*List;
    
    //约瑟夫环
    void Josephus( int n, int k, int m);
    
    int main()
    {
        Josephus(9,1,5);
    }
    
    
    //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
    void Josephus( int n, int k, int m)
    {
        // p为当前结点,r为辅助结点，指向p的前驱结点,L为头节点
        List p,r,L;
        p = r = L = NULL;
        int i;
        for ( i = 0; i < n; i++ )
        {
    	p = (List)malloc(sizeof(ListNode));
    	p->data = i + 1;
    	if ( L == NULL )
    	{
    	    L = p;
    	    r = p;
     	}
    	else
    	{
    	    r->next = p;
    	    r = p;
    	}
        }
        //使链表连起来
        p->next = L;
        //打印链表
        p = L;
        
        printf("链表元素：");
        for ( i = 0; i < n; i++ )
        {
    	printf("%4d",p->data);
    	p = p->next;
        }
        p = L;
        //把指针指向第一个报数的人
        for ( i = 1; i < k; i++ )
        {
    	r = p;
    	p = p->next;
        }
        printf("\n出列顺序：");
    
        //循环的删除队列结点
        while ( p->next != p )
        {
    	for ( i = 0; i < m - 1; i++ )
    	{
    	    r = p;
    	    p = p->next;
    	}
    	//指向的是第一个人，则将r指向最后一个元素
    	if ( p == L )
    	{
    	    L = p->next;
    	    r = p;
    	    while( r->next != p )
    		r = r->next;
    	}
    	    
            r->next = p->next;
    	printf("%4d",p->data);
    	free(p);
    	p = r->next;
        }
        printf("%4d\n",p->data);
    
    }

运行结果：

![20130503094829342][]

[20130503094829342]: /images/20220228/6c72cdefe52d4179a138a74327ae0441.png