约瑟夫环.cpp

约瑟夫环的实现,包括创建和演算,链表实现,很好的数据结构设计程序

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>

typedef struct Lnode
{
    int pos;
    int data;
    struct Lnode *next;
}Lnode,*linklist;

Lnode* Createlist(int n)
{

    int i=1,j=0;
    Lnode *p,*q,*L;
    p=q=(linklist)malloc(sizeof(Lnode));
    p->next=NULL;
    printf("Input the %dst person's code:",i);
    scanf("%d",&p->data);
    p->pos=i;
    for(i=2;i<=n;i++)
    {
	j=j+1;
	if(j==1)L=p;
	else q->next=p;
	q=p;
	p=(Lnode *)malloc(sizeof(Lnode));
	printf("Input the %dst person's code:",i);
	scanf("%d",&p->data);
	p->pos=i;
    }
    q->next=p;
    q=p;
    q->next=L;
    return L;
}

Print(Lnode *L,int m)
{
    int i;
    Lnode *p,*q;
    printf("Output:\n");
    p=L;
    while(p->next!=p)
    {
	for(i=1;i<m;i++)
	{
	    q=p;
	    p=p->next;
	}
	printf("%d",p->pos);
	m=p->data;
	q->next=p->next;
	free(p);
	p=q->next;
    }
    if(p->next==p)printf("%d",p->pos);
}

main()
{
    Lnode *p;
    int n,m;
    char cmd;
    do{
	printf("Please input the number of the person:");
	scanf("%d",&n);
	printf("Please input the upper limited number m:");
	scanf("%d",&m);
	p=Createlist(n);
	Print(p,m);
	printf("\nContinue?(y/n):");
	scanf("%s",&cmd);
    }while(cmd=='y'||cmd=='Y');
}