Question

单链表解决约瑟夫环问题

编写一个程序求解约瑟夫问题。有n个小孩围成一圈，给他们从1 开始依次编号，现指定从第W个小孩开始报数，报到第s个时，该小孩出列，然后从下一个小孩开始报数，仍是报到第s个时出列，如此重复下去，直到所有的小孩都出列，求小孩出列的顺序。 n,s,w都是变量，利用单循环链表解决该问题～

Answer 1

#include <stdlib.h>#include <stdio.h>#include<conio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef char ElemType;typedef int Status;typedef struct node{int data;struct node *next;}LNode; main(){LNode* Create(int,int);LNode* GetNode(LNode *);int Print(LNode *,int);LNode *p;int n,k,m;do{printf ("输入总人数");scanf ("%d",&n);}while (n<=0);do{printf ("输入开始人的序号(1~%d)",n);scanf ("%d",&k);}while (k<=0 || k>n);do{printf ("输入间隔数字");scanf ("%d",&m);}while(m<=0); p=Create(n,k);Print(p,m);getch();} LNode* Create(int n,int k){int start=k-1;LNode *s,*p,*L=0,*t;if (start==0) start=n;while (n!=0){s=(LNode *)malloc(sizeof(LNode));if (L==0) p=s;if (n==start) t=s;s->data=n;s->next=L;L=s;n--;}p->next=L;return t;} LNode* GetNode(LNode *p){LNode *q;for (q=p;q->next!=p;q=q->next);q->next=p->next;free (p);return (q);} Print(LNode *p,int m){int i;printf ("出队编号:\n");while (p->next!=p){for (i=1;i<=m;i++)p=p->next;printf ("%d ",p->data);p=GetNode(p);}printf("%d\n",p->data);}