约瑟夫环1.txt

数据结构中常出的问题之一.约瑟夫环比较常见的问题,希望对大家有所帮助

typedef struct Node
  7 {
  8         int key;//每个人身上带的key 
  9         int NUM;//每个人的编号 
 10         struct Node *next;
 11 }Node;
 12 //=========================
 13 int n;//总共的人数 
 14 Node *L=NULL;//循环链表指针 
 15 //=========================
 16 void InitList(int x)//初始化第一个节点，这个节点有实际的意义 
 17 {
 18      
 19      L = (Node*)malloc(sizeof(Node));
 20      if(!L)
 21        { 
 22            printf("malloc fail\n");
 23            system("PAUSE");    
 24            exit(1);   
 25        }
 26      L->NUM=1;
 27      L->key=x;
 28      L->next=L;
 29 }       
 30 //===========================================
 31 void DelNode(Node *p_front)//p_front指向的是p的前一个节点，删除的却是p 
 32 
 33 {
 34      Node  *tmp=p_front->next;
 35      p_front->next = tmp->next;
 36      free(tmp);
 37  } 
 38  //============================================
 39 void CreateList(void)//创建循环链表 
 40 { 
 41      printf("Players n=");
 42      scanf("%d",&n);
 43      while(n<1||n>30)
 44      {  
 45                   printf("n must >=1 && <=30\n");
 46                   printf("Players n=");
 47                   scanf("%d",&n);
 48      }
 49      int key_tmp;
 50      printf("NUM=1  key=");
 51      scanf("%d",&key_tmp);
 52      while(key_tmp<1||key_tmp>300)
 53      {
 54               printf("key must >0&&<=300\n");
 55               printf("NUM=1  key=");
 56               scanf("%d",&key_tmp);
 57      }
 58      InitList(key_tmp);
 59      int i;
 60      Node *s,*p=L;
 61      for( i=2;i<=n;i++)
 62      {
 63           s=(Node*)malloc(sizeof(Node));
 64           if(!s)
 65           {
 66                 printf("malloc error\n");
 67                 system("PAUSE");    
 68                 exit(1);
 69           }
 70           printf("NUM=%d  key=",i); 
 71           scanf("%d",&key_tmp);
 72           while(key_tmp<1||key_tmp>300)
 73      {
 74               printf("key must >0 && <=300");
 75               printf("\nNUM=%d  key=",i);
 76               scanf("%d",&key_tmp);
 77      }
 78           s->key=key_tmp;
 79           s->next=L;//构成循环链表的next指针赋值 
 80           p->next=s;
 81           s->NUM=i;
 82           p=s;//指针p往前移动 
 83      }
 84 }
 85 //=============================================
 86 void PlayGame(void)//开始游戏！报数 
 87 {
 88      Node  *p=L;
 89      Node  *p_front=L;
 90      int m;
 91      printf("start  game !\n");
 92      printf("m=");
 93      scanf("%d",&m);
 94      while(m<1||m>300)
 95        {
 96                    printf("m must >0 && <=300\n m=");
 97                     scanf("%d",&m);
 98        }
 99      int i;
100      int count = n;
101      for(i=1;i<=m;i++)
102      {   
103         // printf("num =%d  key=%d\n",p->NUM,p->key);
104          
105          if(m==i)
106          {
107                 
108                  m=p->key;
109                  i=0;
110                  printf(" %d",p->NUM);
111                  DelNode(p_front);  
112                  p=p_front;
113                  count--;
114                  if(count==1)
115                      {       
116                              printf(" %d",p->NUM);
117                              //printf("num =%d  key=%d\n",p->NUM,p->key);
118                              printf(" all out !\n");
119                              system("PAUSE");    
120                              exit(0);
121                      }
122              
123          }
124          p_front=p;
125          p=p->next;
126          
127      }
128  }
129  //==================================================
130 int main(int argc, char *argv[])//运行游戏！ 
131 {
132   CreateList();
133   PlayGame();
134   system("PAUSE");    
135   return 0;
136 }