josephus.cpp

来自「文件夹中包括常用的数据结构的算法」· C++ 代码 · 共 64 行

#include <malloc.h>
#include <stdio.h>
#define NUM_CIRCLE 9

typedef struct  LNode 
{ 
	int data;  // 数据域
	int nextOut;
    struct LNode   *next;  // 指针域
}LNode, *LinkList;  


void Josephus(LinkList  L)
{
	LNode *pre, *cur;
	int nextOutNum;
	
	pre = cur = L;
	nextOutNum = cur->nextOut;  //将第一次出局的号赋给初值
	if(nextOutNum == 1)  
		printf("The nextOutNum of the first node is not allow to be 1\n"); //第一个节点的nextOutNum不允许等于1
	
	while(cur->next != cur )
	{
		for(int i=1; i < nextOutNum; i++ )     //注意第一次时计数是从当前节点开始
		{
			pre=cur;
		    cur = cur->next;
		}
		
		pre->next = cur->next;                  //删除当前节点
		nextOutNum = cur->nextOut;
		printf("%d out \n", cur->data);
		free(cur);
		cur = pre->next;
	}

	printf("The last one is %d \n", cur->data);

}

void main()
{
   // LinkList L;
    LNode *p, *Head;

    Head = p = (LinkList) malloc (sizeof (LNode));
//	p = *L;

	p->data = 1;               //令第一个节点编号1
	p->nextOut = 3;   //令每一个节点指向的下一次出局的数全部等于3 

	for(int i = 2; i <= NUM_CIRCLE; i++)
	{
	   p->next = (LNode *) malloc (sizeof (LNode));
	   p = p->next;
       p->data = i;               //令第一个节点编号1
       p->nextOut = 3;   //令每一个节点指向的下一次出局的数全部等于3 
	};
	p->next = Head;

    Josephus(Head);

}