【プログラマー面接宝典】データ構造基礎三サイクルチェーン表


試験問題説明:既知n人(番号1,2,3,4,...)円卓の周りに囲む.k番の人から数え始め、m番の人が出てきて、次の人は1から数え始め、m番の人が出てきて、円卓の周りの人が全部出るまで繰り返します.c++で実現します.
コアステップ:(1)n個の接続点、ヘッダレスノードを有するループチェーンテーブルを確立する.
(2)最初の報告者の位置を決定する.
(3)チェーンテーブルが空になるまでチェーンテーブルからノードを削除し続ける.
コードは次のとおりです.
#include
#include

typedef struct CircleLink{
	int data;
	struct CircleLink *next;
}LNode;

void JOSEPHUS(int n,int k,int m)
{
	LNode *p,*r,*curr;
	p=(LNode *)malloc(sizeof(LNode));
	p->data=0;
	p->next=p;
	curr=p;//    n        
	for(int i=1;idata=i;
		t->next=curr->next;
		curr->next=t;
		curr=t;
	}
	r=curr;
	while(k--){r=p;p=p->next;}
	while(n--)
	{
		for(int s=m-1;s--;r=p,p=p->next);
		r->next=p->next;
		printf("%d->",p->data);
		free(p);
		p=r->next;
	}
}
void main()
{
	JOSEPHUS(5,1,3);	
}