/*----------------------------------------------------------------------------------------------------------
实验三 （附加） 约瑟夫环
【问题描述】
编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，
从第一个人开始按顺时针方向自1开始顺序报数， 报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时
针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。
【基本要求】
(1) 利用单循环链表作为存储结构模拟此过程；
(2) 键盘输入总人数、初始报数上限值m及各人密码；
(3) 按照出列顺序输出各人的编号。
【测试数据】
m的初值为20；n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6（正确的出列顺序为6,1,4,7,2,3,5）。
【实现提示】
此题所用的循环链表中不需要“头结点”。
【选作内容】
用顺序表解决约瑟夫问题。
-------------------------------------------------------------------------------------------------------------*/

/* 约瑟夫环--by hoodlum1980 2008年10月7日*/
#include <stdio.h>
#include <stdlib.h>

typedef struct tnode
{
    int key;    /*密码*/
    int index; /*编号*/
    struct tnode*    next;
} NODE;

/* entry point */
int main()
{
    int i,j,m,n;
    NODE *head=NULL, *cur=NULL, *last=NULL;

    /*输入有多少个人--------------------------------------*/
    printf("input n=?\n");
    scanf("%d",&n);
    
    /*输入初始密码----------------------------------------*/
    printf("input m=?\n");
    scanf("%d",&m);
    
    /*输入n个密码-----------------------------------------*/
    printf("input %d keys: \n", n);
    for(i=0;i<n;i++)
    {
        cur=(NODE*)malloc(sizeof(NODE));
        scanf("%d",&(cur->key));
        cur->index=i+1; /*编号以1为起始*/
        cur->next = NULL;
        if(i==0)
        {
            head=last=cur;
        }
        else
        {
            last->next=cur;/*挂接*/
        }
        last=cur;
    }
    /*连成环*/
    if(last!=NULL) last->next=head;
    
    /*初始化-----------------------------------------------*/
    /*
        cur(head)        last
         |                 |
         O - O - O - ... - O
    */
    cur=head; /*此时，cur指向head节点，last指向尾部节点*/
    
    /*开始报数----------------------------------------------*/
    printf("\nExit Order: ");
    for(i=0;i<n;i++)
    {
        /*依次报数到第m个节点*/
        for(j=1;j<m;j++)
        {
            last=cur;
            cur=cur->next;
        }
        /*出列*/
        m=cur->key;/*更新key*/
        printf("%d,", cur->index);
        /*脱链*/
        last->next=cur->next;
        free(cur);
        cur=last->next;
    }
    printf("\n");
    return 0;
}

收到的鲜花

• liyanhong 于 2008-10-18 23:54 送鲜花  45朵   附言：好文章

非常专业，支持！！！

好文章!

#include <stdio.h>
#include <malloc.h>
struct node
{
    int num;//为方便表达，每个节点拥有一个序号
    int password;//密码
    struct node *next;
};
node * creatlist(int people)//构造链表
{
    int i=1;//序号
    int _password;
    node *r,*s;
    node *L=(node *)malloc(sizeof(node));//创造头结点
    r=L;
    while(i<=people)
    {
        printf("请输入第%d个人的密码：",i);
        scanf("%d",&_password);
        s=(node *)malloc(sizeof(node));
        s->num=i;
        s->password=_password;
        r->next=s;
        r=s;
        i++;
    }
    r->next=L;//循环链表
    return L;
}


void getoutseq(node *L,int firstp)//计算出列顺序并输出的函数
{
    int _password=firstp;
    node *p=L;
    node *r=L;//r为p的前驱节点
    int i=1;
    while(L->next!=L)//当L为非空表时一直循环，空表表示所有人已经出列，则退出循环
    {
        while (i<=_password)//根据密码移动指针
        {
            if (p->next!=L)//当p的下一个节点非头结点，直接向下移
                {
                    r=p;//p移动前先备份
                    p=p->next;
                }    
            else//当p的下一个节点是头节点，则令p指向一号节点
                {
                    r=L;
                    p=L->next;
                }
            i++;
        }
        printf("%d号出列\n",p->num);    
        _password=p->password;//获取节点中的密码
        r->next=p->next;//删除并释放p
        free(p);
        i=1;
        p=r;
    }
    printf("结束!\n");
}
/*
void print(node *L)//该函数用于打印每个节点的信息，方便测试
{
    node *p=L->next;
    while(p!=L)
    {
        printf("序号%d密码%d\n",p->num,p->password);
        p=p->next;
    }
    
}
*/
int main()
{
    node *list;
    int people;
    int firstp;
    printf("请输入人数：");
    scanf("%d",&people);
    putchar('\n');
    printf("请输入初始密码：");
    scanf("%d",&firstp);
    putchar('\n');
    list=creatlist(people);
/*    print(list);     //该语句用于测试
*/
    getoutseq(list,firstp);
    printf("按确定键退出。。。");
    getchar();
    getchar();
    return 0;
}


我写的

#include <stdio.h>
#include <malloc.h>
#define NULL 0
#define LEN sizeof(struct ring)


struct ring
{
    int number;
    int code;
    struct ring *next;
};

  
void main()
{
    int m;
    printf("请输入这个环的人数:");
    scanf_s("%d",&m);

    struct ring *p1,*p2,*head=NULL;
    head=p2=p1=(struct ring*)malloc(LEN);
    p1->number=1;
    printf("请输入第1个人的密码:");
    scanf_s("%d",&p1->code);
    p1->next=NULL;


    for(int i=1;i<m;i++)
    {
        p2=(struct ring*)malloc(LEN);
        p2->number=i+1;
        printf("请输入第%d个人的密码:",i+1);
        scanf_s("%d",&p2->code);
        p2->next=NULL;
        p1->next=p2;
        p1=p1->next;
    }
    p1->next=head;
    p1=p2=head;

    int myCode;
    myCode=20;
    do{
        if(myCode!=1)
        {
            for(int j=1;j<myCode-1;j++)
                p1=p1->next;
        }
        else
        {
            for(int j=1;j<m;j++)
                p1=p1->next;
        }
            p2=p1->next;
            p1->next=p2->next;
            p1=p1->next;
            printf("%d\n",p2->number);
            myCode=p2->code;
            p2=p1;
            m--;
    }while(m>1);
    printf("%d\n",p1->number);
}


试着编了一下

好文章

专业。

不懂啊；
功力还不够