C++语言循环链表(约瑟夫环)源程序

#include<stdio.h>

#include<stdlib.h>





typedef struct node{

    int number;

    struct node* next;

}person;



person *initLink(int n)

{

    person *head=(person*)malloc(sizeof(person));

    head->number=1;

    head->next=NULL;

    person *cyclic=head;

    int i;

    for(i=2;i<=n;i++)

    {

        person *temp=(person*)malloc(sizeof(person));

        temp->number=i;

        temp->next=NULL;



        head->next=temp;

        head=head->next;

    }

    head->next=cyclic;

    return cyclic;

}





void linkPrint(person *temp)

{

    person *head=temp;

    if(!temp)

        printf("the link is empty\n");

    else

    {

        while(temp)

        {

            printf("%d\t",temp->number);

            temp=temp->next;

            if(temp==head)

                break;

        }

    }

}



void findANDkill(person *head,int k,int m)

{

    person *tail=head;

    //找到链表第一个结点的上一个结点，为删除操作做准备

    while(tail->next!=head)

        tail=tail->next;

    person * p=head;

    //找到编号为k的人

    while(p->number!=k)

    {

        tail=p;

        p=p->next;

    }

    //从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，

    while(p->next!=p)

    {

        //找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。

        for(int i=1;i<m;i++)

        {

            tail=p;

            p=p->next;

        }



        tail->next=p->next;//从链表上将p结点摘下来

        printf("出列人的编号为:%d\n",p->number);

        free(p);

        p=tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续

    }

    printf("出列人的编号为:%d\n",p->number);

    free(p);

}



int main()

{

    int n,k,m;

    printf("请输入圆桌上的人数：\n");

    scanf("%d",&n);

    person *head=initLink(n);

    //linkPrint(head);

    printf("从第k人开始报数(k>1且k<%d)：",n);

    scanf("%d",&k);

    printf("数到m的人出列：");

    scanf("%d",&m);



    findANDkill(head,k,m);

    return 0;

}