[转]用单向循环链表解决约瑟夫环问题

设有n个人围坐一圈,现以某个人开始报数,数到m的人出列,接着从出列的下一个人开始重新报数,数到m的人又出列,如此下去,直到所有人都出列为止.按出列顺序输出. 

这段代码是从网上找来的，在此特别说明！！！！！

C代码

1. #include   "stdlib.h"  
2. struct ele {  
3.     int no;  
4.     struct ele *link;  
5. } main() {   
6.   
7.     struct ele *h, *u, *p;  
8.     int n, m, i;  
9.     printf("Please   input   n&m:/n");  
10.     scanf("%d%d", &n, &m);/*输入n和m*/  
11.     h = u = (struct ele *) malloc(sizeof(struct ele));/*形成首表元*/  
12.     h->no = 1;  
13.     for (i = 2; i <= n; i++)/*形成其余的n-1个表元*/  
14.     {  
15.         u->link = (struct ele *) malloc(sizeof(struct ele));  
16.         u = u->link;  
17.         u->no = i;/*第i个表元置编号i*/  
18.     }  
19.     u->link = h;/*末表元后继首表元，形成环*/  
20.     puts(  
21.             "/nThe   numbers   of   who   will   quit   the   cycle   in   turn   are:");  
22.     while (n) {  
23.         for (i = 1; i < m; i++)  
24.             /*掠过m－1个表元*/  
25.             u = u->link;  
26.         p = u->link;/*p指向第m个表元*/  
27.         u->link = p->link;/*第m个表元从环中脱钩*/  
28.         printf("%4d", p->no);  
29.         free(p);/*释放第m个表元占用的空间*/  
30.         n--;  
31.     }  
32.     printf("/n/n   Press   any   key   to   quit.../n");  
33.     getchar();  
34. }   

#include   "stdlib.h"
struct ele {
    int no;
    struct ele *link;
} main() { 

    struct ele *h, *u, *p;
    int n, m, i;
    printf("Please   input   n&m:/n");
    scanf("%d%d", &n, &m);/*输入n和m*/
    h = u = (struct ele *) malloc(sizeof(struct ele));/*形成首表元*/
    h->no = 1;
    for (i = 2; i <= n; i++)/*形成其余的n-1个表元*/
    {
        u->link = (struct ele *) malloc(sizeof(struct ele));
        u = u->link;
        u->no = i;/*第i个表元置编号i*/
    }
    u->link = h;/*末表元后继首表元，形成环*/
    puts(
            "/nThe   numbers   of   who   will   quit   the   cycle   in   turn   are:");
    while (n) {
        for (i = 1; i < m; i++)
            /*掠过m－1个表元*/
            u = u->link;
        p = u->link;/*p指向第m个表元*/
        u->link = p->link;/*第m个表元从环中脱钩*/
        printf("%4d", p->no);
        free(p);/*释放第m个表元占用的空间*/
        n--;
    }
    printf("/n/n   Press   any   key   to   quit.../n");
    getchar();
} 

     当碰到问题,首先考虑这个问题是怎样的类型,第二从解决列表中选择中最合适的方案.以这个问题为例:问题中是一个循环性质，关键点“有n个人围坐一圈”。可选数据结构与算法中的可选方案：队列，栈，线性表，串。队列，栈和串都不大合适。以线性表中的单向循环链表最合适。