환형 연결리스트(Circular Linked List)-요셉의 문제

환형 연결리스트(Circular Linked List)

-단순 연결리스트와 같은 구조를 가지지만 다른점은 제일 마지막 노드가 제일 처음 노드를 가리키고 있다. 그러므로 tail이라는 개념이 없다.

환형 연결리스트를 이용한 문제----요셉의 문제

예를 들어 A부터 J까지의 10명의 사람이 시계방향으로 순서대로 원을 지어 앉아 있다고 하자. 이때, A부터 시작하여 4명간격으로 사람을 그 원에서 뽑아낸다고 하면 그 순서는 어떻게 될것인가하는 문제이다. 이 경우는 A E I D J G F H C B 이런순이 될것이다.

이제 문제이다---> 프로그램은 사용자로부터 사람의 수 n과 간격 step을 입력받아 사람의 수 만큼 1부터 n까지의 정수를 키로 가지는 노드를 환형 연결리스트로 구성한다. 다음에 처음의 노드로부터 시작하여 step만큼 이동 한 다음 그 위치의 노드를 삭제하고 다음에 또 step만큼 이동하고, 그 노드를 삭제하는 식으로 계속 하여 노드가 하나도 안남을 때까지 반복..--->>요셉의 문제.

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

typedef struct _node{
 int key;
 struct _node *next;
}node;

node* head;

void insert_node(int k)   //1부터 k까지의 값을 가지는 환형 연결리스트 구성
{
 node *t;
 int i;

 t=(node*)malloc(sizeof(node));
 t->key = 1;
 head = t;
 for(i=2; i<=k; i++)
 {
  t->next = (node*)malloc(sizeof(node));
  t = t->next;  //결국 t->next가 t를 가리키게 된다. 새로운 t형성
  t->key = i;
 }
 t->next = head;   //마지막을 처음으로 물림, 환형
}

void delete_after(node *t)  //다음 노드를 삭제
{
 node *s;
 s = t->next;
 t->next = t->next->next;
 free(s);
}

void josephus(int n, int step)  //요셉 문제 해결, n개의 노드를 step간격으로..
{
 node *t;
 int i;

 insert_node(n);     //환형리스트 구성
 t = head;
 while(t != t->next)    //연결리스트에 노드가 남아 있을 동안..
 {
  for(i=0; i < step-1; i++) //즉, step만큼 가서 그 노드의 값 출력
   t = t->next;
  printf("%d ", t->next->key);
  delete_after(t);   //출력하고 삭제.
 }
 printf("%d \n", t->key);   //마지막 노드 출력
}
void main(void)
{
 int n, step;

 while(1)
 {
  printf("n과 step을 입력하시오 : ");
  scanf("%d %d", &n, &step);
  if(n <= 0 || step <= 0)
   return;
  josephus(n, step);
 }
}


출처 : http://blog.naver.com/green_kingka/21649833