【プログラマー面接宝典】データ構造基礎三サイクルチェーン表
873 ワード
試験問題説明:既知n人(番号1,2,3,4,...)円卓の周りに囲む.k番の人から数え始め、m番の人が出てきて、次の人は1から数え始め、m番の人が出てきて、円卓の周りの人が全部出るまで繰り返します.c++で実現します.
コアステップ:(1)n個の接続点、ヘッダレスノードを有するループチェーンテーブルを確立する.
(2)最初の報告者の位置を決定する.
(3)チェーンテーブルが空になるまでチェーンテーブルからノードを削除し続ける.
コードは次のとおりです.
コアステップ:(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);
}