循环链表-约瑟夫环问题

本文主要是介绍循环链表-约瑟夫环问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正好这几天在看数据结构，觉得链表应用挺广的，特写一实例。

问题描述：

选首领。N个游戏者围成一圈，从第一个开始顺序报数1,2,3.凡报到3者退出圈子，最后留在圈中的人为首领。

思路：

创建一个包含N个节点的单循环链表来模拟N个人围成的圈。节点的数据域存放游戏者的编号。

在程序中，以删除节点模拟人退出圈子的处理，整型变量c（初始值为1）用于计数，指针变量p的初始值为head，运行时，从p所指的节点开始计数，p沿链表中的指针每次向后指一个节点，c值随p指针的移动相应地递增。当c计数到2时，就删除下一个节点，然后将c置为0。为了避免将剩下的最后一个节点删除，另外设置一个计数器k，其初值为参加游戏的人数。每当删除一个节点时，k值就减1，当k等于1时，首领就选出来了！

代码：

[cpp]  view plain copy  
 #include <stdio.h>  
 #include <stdlib.h>  
 typedef struct node{  
       int   code;          /*  游戏者的编号 */  
       struct node *next;  
 }NODE,*LinkList;  
 LinkList  create_list(int n)  
 /* 创建一个节点数为n的单循环链表，返回值为游戏编号为1的节点的指针  */  
 { LinkList head,p;  
   int i;  
   head=(NODE*)malloc(sizeof(NODE));/*创建循环链表的第一个节点*/  
   if(!head){  
      printf("内存位置错误！/n");return NULL;  
   }  
   head->code=1;  head->next=head;  
   for(i=n;i>1;--i){/* 尾插法创建循环链表的其余n-1个节点*/  
      p=(NODE*)malloc(sizeof(NODE));  
      if(!p){  
          printf("内存位置错误！/n");return NULL;  
      }  
      p->code=i;  p->next=head->next; head->next=p;  
   }/*for*/  
   return head;  
 }/*create_list*/  
 void output(LinkList head)/*输出链表中的节点的数据*/  
 {   LinkList p;  
     p=head;  
     do{  
        printf("%4d",p->code);  p=p->next;  
     }while(p!=head);  
      printf("/n");  
 }/*output*/  
 void play(LinkList head,int n)  
 {   LinkList p,q;  
     int c=0,k;  
     p=head; c=1;k=n;  
     while(k>1){  
         if(c==2){  /* 当c等于2时，p指向的节点后继即为被删除的节点*/  
            q=p->next;p->next=q->next;  
            printf("%4d",q->code); free(q);  
            c=0;  k--;  
         }/*if*/  
         else{c++;p=p->next;}  
     }/*while*/  
     printf("/n%4d 是首领.",p->code);  /*输出最后留在圈子内的人的编号*/  
 }/*play*/  
 void main(void)  
 { LinkList head;    
   int n;  
   printf("请输入游戏者的游戏编号："); scanf("%d",&n);  
   head=create_list(n);               /*创建单循环链表*/  
   if(head){   
   output(head);                      /*输出单循环链表中的节点的信息*/  
   play(head,n);  
   }  
 }  