分别用 数组和链表处理约瑟夫环问题

#include  
#include  
 
int main()  
{  
 
   int k=0,n=0,s=0,m=0;           //k为1,2,3报数时的计数变量,m为退出人数 
   int num [100]; 
   int *p=num; 
   int i; 
   printf("Enter the number of person and the key:"); 
   scanf("%d%d",&n,&s); 
   for (i=0; i   {  
      *(p+i)=i+1;                //以1至n为序给每个人编号 
   }                           
   i = 0; 
   while (m<(n-1))              //当未退出人数大于1时执行循环体   (n-m) > 1 
   { 
      if (*(p+i)!=0) 
          k++; 
      if (k==s)                //对退出的人编号置为0 
      { 
          printf("%d\n",*(p+i));                      
          *(p+i)=0; 
          k = 0; 
          m++; 
      } 
       i++; 
      if (n==i)                
           i = 0;               //报数到尾后,i恢复为0 
    } 
     while (*p==0) 
        p++; 
    printf("The last one is :%d\n",*p); 
    system("PAUSE");     
    return 0; 
} 

====================================================== 
#include  
#include  
#include  
#include  
 
/* 结构体和函数声明 */ 
typedef struct _node_t 
{ 
    int             n_num; 
    struct _node_t *next; 
} node_t; 
 
node_t         *node_t_create(int n); 
node_t         *node_t_get(node_t **pn, int m); 
 
node_t * node_t_create(int n) 
{ 
    node_t *p_ret   = NULL; 
 
    if (0 != n) 
    { 
        int     n_idx   = 1; 
        node_t *p_node  = NULL; 
 
        /* 构造 n 个 node_t */ 
        p_node = (node_t *) malloc(n * sizeof(node_t)); 
        if (NULL == p_node) 
            return NULL; 
        else 
            memset(p_node, 0, n * sizeof(node_t)); 
 
        /* 内存空间 申请 成功 */ 
        p_ret = p_node; 
 
 
        for (; n_idx < n; n_idx++) 
        { 
            p_node->n_num = n_idx; 
            p_node->next = p_node + 1; 
            p_node = p_node->next; 
        } 
        p_node->n_num = n; 
        p_node->next = p_ret; 
    } 
 
    return p_ret; 
} 
 
 
int main() 
{ 
    int     n, m; 
    node_t *p_list, *p_iter; 
    printf("Please enter the total and the key :"); 
    scanf("%d%d",&n,&m); 
    printf("The total num is : %d \nThe   key   is   : %d \n",n,m); 
 
    /* 构造环形单向链表 */ 
    p_list = node_t_create(n); 
 
    /* Josephus 循环取数 */ 
    p_iter = p_list; 
    m %= n; 
    while (p_iter != p_iter->next) 
    { 
        int i   = 1; 
 
        /* 取到第 m-1 个节点 */ 
        for (; i < m - 1; i++) 
        { 
            p_iter = p_iter->next; 
        } 
 
        /* 输出第 m 个节点的值 */ 
        printf("%d ", p_iter->next->n_num); 
 
        /* 从链表中删除第 m 个节点 */ 
        p_iter->next = p_iter->next->next; 
        p_iter = p_iter->next; 
    } 
    printf("%d ", p_iter->n_num); 
 
    /* 释放 申请 的空间 */ 
    free(p_list); 
 
    system("PAUSE"); 
}