约瑟夫环

ktzlj

【问题描述】
编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。

【基本要求】
(1)利用单循环链表作为存储结构模拟此过程；
(2)键盘输入总人数、初始报数上限值m及各人密码；
(3)按照出列顺序输出各人的编号。

【详细设计】
1.元素类型，结点类型，指针类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int status;//函数值返回类型

typedef int ElemType;//元素值类型

typedef struct CList{
ElemType location;//编号
ElemType code;//密码
Struct CList *next;//指向后继的指针
}CList,*ListPtr;//结点类型，指针类型




（1）
status InitList(ListPtr *CL)
{//创建一个已知大小为size(1--32767)指针CL指向链尾的单循环链表
//若创建成功返回OK，否则返回ERROR
//count为计数器，初始化为count=0
//p,q,r为ListPtr类型的指针

scanf(&size);
if(size<=0)
return ERROR;
else {
q=(CList *)malloc(sizeof(CList));
if(!q)
exit(OVERFLOW);//存储空间分配失败

count=1;
p=q;//指针p指向链头
p->location=count;

do{//接收合法密码；
scanf(&cd);
if(cd<1||cd>32767)//非法数据报错
printf(“\nIncorrect data,Try again.\n”);
while(cd<1||cd>32767);

p->code=cd;

while(size>1)
{
r=(CList *)malloc(sizeof(CList));
if(!p)
exit (OVERFLOW);//存储空间分配失败

r->location=++count;

do{//接收合法密码；
scanf(&cd);
if(cd<1||cd>32767)//非法数据报错
printf(“\nIncorrect data,Try again.\n”);
while(cd<1||cd>32767);

r->code=cd;

q->next=r;//连接相邻结点；
q=r；
size--;
}//while

*CL=q;//指针CL指向链尾
q->next=p,//链尾指向链头

return OK;
}//else
}//InitList

(2)
Status ReadList(ListPtr CL)
{//查看并打印编号及相对应的密码
if(!CL)
return ERROR;//空的单循链表，返回值ERROR
else {
p=CL->next;
printf(p->location);//打印编号
printf(p->code);//打印密码
p=p->next;//指针下移

while(p!=CL->next){
printf(L->location);
printf(L->code);
p=p->next;
}
return OK；
}//else
}//ReadList

(3)
status Joseph(CListPtr CL){
//输入初始报数上限值BeginNum
//并显示出列顺序
if(!CL)
return ERROR;//空单循环链表
else {
do{// 任选一个合法正整数，作为报数上限值；
scanf(&BeginNum);
if(BeginNum<1||BeginNum>32767) //非法数据报错
printf(“\nIncorrect data,Try again.\n”);
while(BeginNum<1||BeginNum>32767);
p=CL;
while(p!=p->next){//将不同编号的人按游戏规则出环
for(n=1;n<=BeginNum-1;n++)
p=p->next;//报数

q=p->next;
printf(q->location);//出环

BeginNum=q->code;
p->next=q->next;
free (q);
}//while

printf(p->location)；//最后一个人出环

return OK;
}//else
}//Joseph

(4)
void main(){
ListPtr L=NULL; //初始化
int cmd=0;

scanf(&cmd);// 接受命令

while(cmd!=0){// “命令”！=“退出”
switch(cmd){// 命令
case 1：//命令1
InitList(L); //处理命令
break;
case 2:  //命令2
ReadList(L);//处理命令
break;
case 3: //命令3
Joseph(L); //处理命令；
break;
}

scanf(&cmd);// 接受命令
}//while
}//main

【源程序】(在turbo c 2.0 编译通过)
#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int status;
typedef int ElemType;

typedef struct CList{
   ElemType location;
   ElemType code;
   struct CList *next;
}CList,*ListPtr;

status InitList(ListPtr *CL);
status ReadList(ListPtr CL);
status Joseph(ListPtr CL);

void main(){
ListPtr L=NULL;
int cmd=0;

printf("******************************************************************\n");
printf("*     InitList--1      ReadList--2      Joseph--3     Exit--0    *\n");
printf("* Enter a operation code : 1, 2, 3, 0                            *\n");
printf("******************************************************************\n");

printf("\n------------------------------------------------------------------\n");
printf("\nOperation:");
scanf("%d",&cmd);

while(cmd!=0){
   switch(cmd){
      case 1:
         InitList(&L);
         break;
      case 2:
         ReadList(L);
         break;
      case 3:
         Joseph(L);
         break;
      }
   printf("\n\n------------------------------------------------------------------\n\n");
   printf("Operation:");
   scanf("%d",&cmd);
  }

}  

status InitList(ListPtr *CL){
   int count=0;
   int size=0;
   int cd=0;
   ListPtr p=NULL;
   ListPtr q=NULL;
   ListPtr r=NULL;

   printf("\nPlease enter the total numbers of people(1--32767):");
   scanf("%d",&size);
   if(size<1||size>32767){
      printf("Please check number(1--32767).\n");
      return ERROR;
      }
    else {
      q=malloc(sizeof(CList));
      if(!q)
         exit(OVERFLOW);
      count=1;
      p=q;
      p->location=count;
     
      do{
         printf("\nPlease enter NO.%d person's code:",count);      
         scanf("%d",&cd);
         if(cd<1||cd>32767)
            printf("\nIncorrect data,Try again.\n");
      }while(cd<1||cd>32767);

      p->code=cd;

      while(size>1)
      {
         r=malloc(sizeof(CList));
         if(!r)
            exit(OVERFLOW);
         r->location=++count;

         do{
            printf("\nPlease enter NO.%d person's code:",count);  
            scanf("%d",&cd);
            if(cd<1||cd>32767)
               printf("Incorrect data,try again.\n");
         }while(cd<1||cd>32767);

         r->code=cd;
         q->next=r;  
         q=r;
         size--;
      }

      *CL=q;
      q->next=p;

      return OK;
    }
}


status ReadList(ListPtr CL){
   int count=0;
   ListPtr p=NULL;
   
   if(!CL)
      return ERROR;
   else{
      p=CL->next;
      printf("\n[People:");
      printf("%d",p->location);
      printf("Code:%d]",p->code);
      p=p->next;

      while(p!=CL->next){
         count++;
         if(count%3==0)
            printf("\n");
         else
            printf("\t");
         printf("[People:");
         printf("%d",p->location);
         printf("Code:%d]",p->code);
         p=p->next;
        }
   return OK;
   }
}

status Joseph(ListPtr CL){
   int n=0;
   int BeginNum=0;
   ListPtr p=NULL;
   ListPtr q=NULL;
   
   if(!CL)
      return ERROR;
   else {

      do{
         printf("\nPlease enter the begin number(1--32767):");
         scanf("%d",&BeginNum);
      if(BeginNum<1||BeginNum>32767)
         printf("\nIncorrect data,Try again.\n");
      }while(BeginNum<1||BeginNum>32767);

      p=CL;

      printf("\n-----------------The Output List is:-----------------------\n");

      while(p!=p->next){
         for(n=1;n<=BeginNum-1;n++)
            p=p->next;
         
         q=p->next;
         printf("%d  ",q->location);
         BeginNum=q->code;
         p->next=q->next;
         free(q);
        }
      printf("%d  ",p->location);
      return OK;
     }
}

欢迎大家对此实现方法提供改进建议.

[ 本帖最后由 ktzlj 于 2007-5-6 17:43 编辑 ]

eugnal

问题的描述里已经告诉你算法了。
每一个算法都可以有不同的实现，所以你问的大抵就是其它实现方法。

ddvv

模一下

eugnal

原帖由 jamesr 于 2007-5-6 23:13 发表
用数组实现可能代码会简短些。

关键是这里加进了不必要的注释，代码也没有清理过，看起来混乱。

andyxie407

看看先

ye888

在等级考试中的上机题有过类似，算法很简单，这里你只不过用链表实现而已

thihy

高手就是不一样，挺简单的一道题目都能搞出这么长的代码。强！佩服啊！

goldensunflower

学习一下

doctorjxd

这个题目十年之前在网吧学习C语言的时候做过。
好象是谭浩强的那本C语言教材的课后题。
当时是先把程序写在纸上，然后去网吧运行。网吧老板很好，给装了Turbo C。真是美好的时代呀。

这样的条件下，过了计算机三级。
现在想想，还是本科的时代美好呀。

[ 本帖最后由 doctorjxd 于 2007-5-11 16:47 编辑 ]