约瑟夫环问题

3.约瑟夫环问题
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #define  MAXSIZE  30
  4 typedef int DataType;
  5 
  6 typedef  struct  node 
  7 {   
  8     DataType  data[MAXSIZE];
  9     int  length;
 10 } SeqList,* PSeqList;
 11 //typedef SeqList* PSeqList;
 12 
 13 
 14 PSeqList  Init_SeqList( );
 15 PSeqList  Create_SeqList(PSeqList PL);
 16 int josephus_SeqList (PSeqList  josephus_seq, int s, int m);
 17 int Delete_SeqList(PSeqList PL,int i);
 18 Print_SeqList(PSeqList PL);
 19 
 20 main()
 21 {
 22    int t=1;
 23    int s,m;
 24    int op;
 25    //DataType x;
 26    //int flag;
 27    //int l;
 28    PSeqList PL;
 29    
 30          
 31    while(t)
 32        {
 33             printf("



");
 34             printf("			---顺序表---
");
 35             printf("
			*******************************************");
 36             printf("
			*          1---初始化及创建               *");
 37             printf("
			*          2---约瑟夫环                   *");            
 38             printf("
			*          0---退     出                  *");
 39             printf("
			*******************************************");
 40             printf("			请选择菜单号(0--2):");
 41             scanf("%d",&op);
 42             switch(op)
 43             {
 44    
 45                 case 1:
 46                     PL=Init_SeqList();//初始化顺序表
 47                     PL=Create_SeqList(PL);
 48                     printf("新创建的顺序表为:
");
 49                     Print_SeqList(PL);
 50                     break;
 51                     
 52                 case 2:
 53                     printf("请输入s和m的值:
");
 54                     scanf("%d,%d",&s,&m);
 55                     josephus_SeqList (PL, s, m);
 56 
 57                     
 58                     break;
 59 
 60                 
 61                 case 0:
 62                       t=0;
 63                       printf("
			程序结束!
");
 64                       break;
 65           
 66                 default: 
 67                     printf("
				输入错误!请重新输入!
");
 68                     break;
 69 
 70               }
 71                    
 72         }
 73 
 74 
 75 }
 76 
 77 
 78 
 79 PSeqList  Init_SeqList(void)
 80 {  /*创建一顺序表，入口参数无，返回一个指向顺序表的指针，指针值为零表示分配空间失败*/
 81    PSeqList  PL;
 82    PL=( PSeqList )malloc(sizeof(SeqList)); 
 83    if (PL)       /*若PL=0表示分配失败*/
 84         PL->length=0;     
 85    return (PL);
 86 } 
 87 
 88 PSeqList  Create_SeqList(PSeqList PL)
 89 {
 90        int i,n;
 91        printf("请输入需初始化的元素个数
");
 92        scanf("%d",&n);
 93        printf("请输入%d个整数，中间用空格隔开:
",n);
 94        for(i=0;i<n;i++)//输入10个整数
 95        { 
 96            scanf("%d",&PL->data[i]);
 97            PL->length++; 
 98        }
 99        return (PL);
100 
101 
102 }
103 
104 int josephus_SeqList (PSeqList  josephus_seq, int s, int m)
105 {  
106     int s1,i,w;
107     if (!josephus_seq->length)
108     {
109          printf("表中无元素"); 
110          return (0);
111     }
112     s1=s-1;   /*data数组中下标从0开始*/
113     printf("输出约瑟夫序列：");
114    
115     for(i=josephus_seq->length; i>0; i--)
116     {  
117        s1=(s1+m-1)%i;   /*找到出列元素的下标*/
118        w=josephus_seq->data[s1];
119        printf("%d	", w);
120        Delete_SeqList(josephus_seq,s1+1);  //
121     } 
122     return(1);//
123 }
124 
125 
126 int Delete_SeqList(PSeqList PL,int i)
127 {  /*顺序表删除，入口参数：顺序表指针，删除元素位置，返回标志1表示成功，0表示删除位置不合法，-1表示表不存在*/
128     int  j;
129     if (! PL)
130     { 
131        printf("表不存在"); 
132        return(-1);    /*表不存在，不能删除元素*/
133     }
134     if(i<1 || i> PL -> length)  /*检查删除位置的合法性*/
135     {  
136         printf ("删除位置不合法"); 
137         return(0);
138     } 
139     //*x= PL ->data[i-1];
140     for(j=i;j< PL -> length; j++)
141          PL ->data[j-1]=PL ->data[j];    //向上移动
142     PL-> length --;    
143     return (1);        /*删除成功*/
144 }
145 
146 
147 Print_SeqList(PSeqList PL)
148 {
149     int i;
150     if(!PL)
151     {
152         printf("无此顺序表");
153         return -1;
154     }
155     if(PL->length==0)
156     {
157         printf("空表");
158         return 0;
159     }
160 
161     printf("顺序表的长度为%d
",PL->length);
162     printf("顺序表的各元素值为：");
163     for(i=0;i<=PL->length-1;i++)
164         printf("%4d",PL->data[i]);
165     return 1;
166 
167 }