newplan

阿基米德在洗澡時發現浮力原理,高興得來不及穿㆖褲子,跑到街㆖大喊:Eureka(我找到了)。
posts - 39, comments - 26, trackbacks - 0, articles - 4
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

约瑟夫环循环链表实现

Posted on 2007-10-05 20:17 山泉弯延 阅读(7196) 评论(7)  编辑 收藏 引用 所属分类: 数据结构实验集
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 //约瑟夫环的实现:一群人围成一圈,这群人共有 n个人,每个人身上都一个key,依次给这圈人编号:
  4 //12n 一开始报数的上限值为m从第一个人(编号:1)自一开始报数报到m时停止报数,报到m的人出列,
  5 //将他的密码做为新的m值,从他的顺时针方向开始的下个人开始从新从一报数,如此下去,直至所有的人出列为止 
  6 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 }
137 

Feedback

# re: 约瑟夫环循环链表实现  回复  更多评论   

2007-10-05 20:48 by 紫金梦幻
程序看得我晕头转向的。
写博客搞点大众化的嘛。

# re: 约瑟夫环循环链表实现  回复  更多评论   

2007-10-05 20:50 by 紫金梦幻
程序看得我晕头转向的。
写博客搞点大众化的嘛。

# re: 约瑟夫环循环链表实现  回复  更多评论   

2007-10-05 20:57 by Minidx全文检索
这个代码应该写得很清楚啊

# re: 约瑟夫环循环链表实现  回复  更多评论   

2007-11-15 17:28 by 苦难的人
谢谢大恩人啊.救人于水火

# re: 约瑟夫环循环链表实现  回复  更多评论   

2008-03-28 11:19 by C++菜鸟
好强大阿!万分钦佩!

# re: 约瑟夫环循环链表实现  回复  更多评论   

2008-10-16 01:07 by yyn
写的很好

# re: 约瑟夫环循环链表实现[未登录]  回复  更多评论   

2008-11-06 22:22 by 阿龙
谢谢啊大哥,我自己写了好久不知道哪错了,出不来结果,看了你的程序我才豁然开朗,真的感谢!

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理