约瑟夫问题

/* 约瑟夫问题(单循环链表) */

#include <stdio.h>
#include <stdlib.h>

typedef struct _node_ {
    int data;
    struct _node_ *next;
}linknode;

linknode *list_init(int n);
void list_show(linknode *H);
void jose(linknode *H, int k, int m);

int main(void)
{
    int n, k, m;
    linknode *H = NULL;

    n = 8, k = 1, m = 3;        /* n为人数，k代表从第几个人开始，m代表数的次数 */
    if ((H = list_init(n)) == NULL)
        return 0;
    list_show(H);
    jose(H, k, m);

    return 0;
}

linknode *list_init(int n)
{
    linknode *p = NULL,
             *H = NULL,
             *q = NULL;
    int i = 2;

    if (NULL == (H = malloc(sizeof(linknode)))) {
        printf("fail to malloc\n");
        return NULL;
    }
    H->next = H;
    H->data = 1;
    q = H;

    while (i <= n) {
        if (NULL == (p = malloc(sizeof(linknode)))) {
            printf("fail to malloc\n");
            return NULL;
        }
        p->data = i++;
        q->next = p;
        p->next = H;
        q = p;
    }

    return H;
}

void list_show(linknode *H)
{
    linknode *p = H;

    while (p->next != H) {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("%d\n", p->data);
}

void jose(linknode *H, int k, int m)
{
    linknode *p = H,
             *q = NULL;
    int i;

    while (p->next->data != k)
        p = p->next;

    while (p->next != p) {
        for (i = 0; i < m - 1; i++)
            p = p->next;
        q = p->next;
        p->next = q->next;
        printf("%d->", q->data);
        free(q);
        q = NULL;
    }
    printf("%d\n", p->data);
}