数据结构 循环链表的应用：约瑟夫环问题

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <stdlib.h>
     
    
   

    

     

    
    

     

      #include <iostream.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define OK 1
     
    
   

    

     

    
    

     

      #define ERROR 0
     
    
   

    

     

    
    

     

      #define OVERFLOW -2
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef int ElemType;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct LNode
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	ElemType data;
     
    
   

    

     

    
    

     
	struct LNode *next;
     
    
   

    

     

    
    

     

      }LNode, *LinkList;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Create_LinkList(LinkList &L, int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int i = 2;
     
    
   

    

     

    
    

     

      	LinkList pCur = NULL,pPrev;
     
    
   

    

     

    
    

     

      	L = (LinkList)malloc(sizeof(LNode));
     
    
   

    

     

    
    

     
	if (!L)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		exit(OVERFLOW);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	L->data = 1;
     
    
   

    

     

    
    

     

      	L->next = NULL;
     
    
   

    

     

    
    

     

      	pPrev = L;
     
    
   

    

     

    
    

     
	while (--n > 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		pCur = (LinkList)malloc(sizeof(LNode));
     
    
   

    

     

    
    

     
		if (!pCur)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			exit(OVERFLOW);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		pCur->data = i;
     
    
   

    

     

    
    

     

      		pPrev->next = pCur;
     
    
   

    

     

    
    

     

      		pPrev = pCur;
     
    
   

    

     

    
    

     

      		i++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	pCur->next = L;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void KickFromRing(LinkList &L, int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	LinkList pCur,pPrev;
     
    
   

    

     

    
    

     
	int i = 1;
     
    
   

    

     

    
    

     

      	pCur = pPrev = L;
     
    
   

    

     

    
    

     
	while (1)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (i == n)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			printf("%d\n",pCur->data);
     
    
   

    

     

    
    

     

      			pPrev->next = pCur->next;
     
    
   

    

     

    
    

     
			free(pCur);
     
    
   

    

     

    
    

     

      			pCur = pPrev->next;
     
    
   

    

     

    
    

     

      			i = 1;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		pPrev = pCur;
     
    
   

    

     

    
    

     

      		pCur = pCur->next;
     
    
   

    

     

    
    

     
		if (pCur == pPrev)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			printf("%d\n",pCur->data);
     
    
   

    

     

    
    

     
			free(pCur);
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		i++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m,n;
     
    
   

    

     

    
    

     
	scanf("%d%d",&m,&n);
     
    
   

    

     

    
    

     

      	LinkList L;
     
    
   

    

     

    
    

     

      	Create_LinkList(L,m);
     
    
   

    

     

    
    

     

      	KickFromRing(L,n);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17249047