数据结构与算法18讲约瑟夫的作业

安吉

/*编号为1~N的N个人按顺时针方向坐一圈，每个人持有一个密码（正整数，可以自由输入），
开始人选一个正整数作为报数上限值M，从第一个人按顺时针方向自1开始顺序报数，报到M时
停止报数。报M的人出列，将他的密码作为新的M值，从他顺时针方向上的下一个人开始从1报数，
如此下去，直至所有人出列*/
#include<stdio.h>
#include<stdlib.h>

typedef struct circular_linked_list{
        int password;
        int index;
        struct  circular_linked_list *next;
} Node;

Node * Creat (int n);

int main()
{
        int i,n,m;
        Node *p, *temp;
        printf("输入一个正整数n，代表有n个人围成一个圈。\n");
        scanf("%d",&n);
        p=Creat(n);
        printf("输入一个正整数M，代表第一个人报数的上限值。\n");
        scanf("%d",&m);

    m=m>n?m%n:m;
        while(p->next!=p)
        {
                for(i=1;i<m-1;i++)
                        p=p->next;
                printf("%d->",p->next->index);
                m=p->next->password;
        m=m>n?m%n:m;
                temp=p->next;
                p->next=temp->next;
                free(temp);
                p=p->next;
        }
        return 0;
}
Node *Creat(int n)
{
        int i;
        Node *head, *p, *s;
        head = (Node *)malloc(sizeof(Node));
        p=head;
        printf("输入N个正整数，代表每个人手中的密码\n");
        for(i=0;i<n;i++)
        {
                s=(Node *)malloc(sizeof(Node));
                scanf("%d",&s->password);
                s->index=i+1;
                p->next=s;
                p=s;
        }
        s->next=head->next;
        free(head);
        return s->next;
}

ps：小甲鱼老师，我欠你一个会员。