二josephu问题.cpp

数据结构课程设计题目

// 二josephu问题.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include<stdio.h>
#include<malloc.h>
typedef struct node 
{
	int data;
	struct node *next;
}lnode;
typedef struct pnode
{
	struct node *h;
    int length;
}tnode;
tnode creat()     //创建循环单链表
{
	tnode l;
	lnode*q,*p,*t;
	int x,y=1;
	printf("请输入各个人的密码以0为结束标志：\n");
	scanf("%d",&x);
	p=(lnode*)malloc(sizeof(lnode));
	p->data=x;
    p->next=NULL;
	t=p;
	scanf("%d",&x);
	while(x!=0)
	{
		q=(lnode*)malloc(sizeof(lnode));
        q->data=x;
		q->next=NULL;
		t->next=q;
		t=q;
        scanf("%d",&x);
		y++;      //记录链表中的结点个数
	}
   t->next=p;         //使尾结点的指针域指向头结点
   l.h=p;
   l.length=y;
   return(l);
}
void fun(tnode l,int m)
{
	lnode *p,*t,*q;
    int y=0,x=m;    //y用来记录各人所报的数
	p=l.h;
	printf("依次出列的各个人手持的密码是：\n");
    while(l.length!=0)
	{	  q=p;
		  y++;
		  p=p->next;
		  while(y<x)
		  {
			y++;
			t=q;      //t指向要删除结点的前一结点
            p=p->next;
			q=q->next;  //q指向要删除的结点
		  }		
		x=q->data;
		printf("%d ",q->data);
		t->next=p;
		free(q);
		l.length--;
		y=0;
	}	
}
void putout(tnode l)
{
	int x=0;
	lnode *p;
	p=l.h;
	printf("从1号开始个人的密码是：\n");
	while(x!=l.length)
	{
		x++;
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
}
void main()
{
   int m;
   tnode l;
   printf("建立循环单链表：\n");
   l=creat(); 
   putout(l);
   printf("请输入初始报数的上限值m：\n");
   scanf("%d",&m);
   fun(l,m);
   printf("\n");
}