yuesefu.txt

这也是一个关于josephus算法的程序

#include <stdlib.h>
#include <malloc.h>

struct node
{
    int number; /* 人的序号 */
    int cipher; /* 密码 */
    struct node *next; /* 指向下一个节点的指针 */
};

struct node *CreatList(int num) /* 建立循环链表 */
{
    int i;
    struct node *ptr1,*head;

    if((ptr1=(struct node *)malloc(sizeof(struct node)))==NULL)
    {
        perror("malloc");
        return ptr1;
    }
    head=ptr1;
    ptr1->next=head;
    for(i=1;i<num;i++)
    {
        if((ptr1->next=(struct node *)malloc(sizeof(struct node)))==NULL)
        {
            perror("malloc");
            ptr1->next=head;
            return head;
        }
        ptr1=ptr1->next;
        ptr1->next=head;
    }
    return head;
}

main()
{
    int i,n=30,m; /* 人数n为30个 */
    struct node *head,*ptr;
    randomize();
    head=CreatList(n);
    for(i=1;i<=30;i++)
    {
        head->number=i;
        head->cipher=rand();
        head=head->next;
    }
    m=rand(); /* m取随机数 */
    i=0; /* 因为我没办法删除head指向的节点，只会删除head的下一节点，所以只能从0数起。*/
    while(head->next!=head) /* 当剩下最后一个人时，退出循环 */
    {
        if(i==m)
        {
            ptr=head->next; /* ptr记录数到m的那个人的位置 */
            printf("number:%d\n",ptr->number);
            printf("cipher:%d\n",ptr->cipher);
            m=ptr->cipher; /* 让m等于数到m的人的密码 */
            head->next=ptr->next; /* 让ptr从链表中脱节，将前后两个节点连接起来 */
            head=hea/d->next; /* head移向后一个节点 */
            free(ptr); /* 释放ptr指向的内存 */
            i=0; /* 将i重新置为0，从0再开始数 */
        }
        else
        {
            head=head->next;
            i++;
        }
    }
    printf("number:%d\n",head->number);
    printf("cipher:%d\n",head->cipher);
    free(head); /* 让最后一个人也出列 */
}