Circular Linked List 이다

참고 문헌 : C 로 배우는 알고리즘 1

/************************************************************************/
/*  CircularLinkedList.cpp : 환형 연결 리스트 구현                      */
/*  단순 링크드 리스트와 같은 노드 구조를 가지고 있지만 환형 연결리스트 */
/*  는  연결리스트의 제일 마지막 노드가 가장 처음의 노드를 가리킨다.    */
/************************************************************************/

#include <STDIO.H>
#include <MALLOC.H>

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

node *head;

/************************************************************************/
/* 함수명 : insert_nodes                                                */
/* 1 부터 K 까지의 값을 가지는 환형 연결 리스트를 구성한다.    */
/************************************************************************/
void insert_nodes(int k)
{
 node *t;
 int i;
 t = (node*)malloc(sizeof(node));
 t->key = 1;
 head = t; /* head */
 for(i = 2 ; i <= k ; i++)
 {
  t->next = (node*)malloc(sizeof(node)); // next node
  t = t->next;
  t->key = i;
 }
 t->next = head; // tail 다음 노드는 head
}

/************************************************************************/
/* 함수명 : delete_after                                                */
/* t 다음의 노드를 삭제한다.           */
/************************************************************************/
void delete_after(node *t)
{
 node *s;
 s = t->next;
 t->next = t->next->next;
 free(s);
}

/************************************************************************/
/* 함수명 : josephus                                                    */
/* 요셉의 문제를 푼다. n 개의 노드를 m 간격으로 뽑아낸다.    */
/************************************************************************/
void josephus(int n, int m)
{
 node *t;
 int i;
 insert_nodes(n); // 환형 연결 리스트 구성
 t = head;
 printf("\nAnswer : ");
 while(t != t->next)
 {
  for(i = 0 ; i < m - 1 ; i++)
  { 
   t = t->next;
  }
  printf("%d ", t->key);
  delete_after(t); /* 출력하고 삭제 */
 }
 printf("%d", t->key);
}

/************************************************************************/
/* 함수명 : main                                                        */
/* 메인 함수               */
/************************************************************************/
void main( void )
{
 int n, m;
 printf("\n나가려면 0 이나 음수 값을 넣으세요");
 while(1)
 {
  printf("\nEnter N and M -> ");
  scanf("%d %d", &n, &m);
  if(n <= 0 || m <= 0)
  {
   return;
  }
  josephus(n, m);
 }
}

Posted by 행복한 프로그래머 궁금쟁이박

댓글을 달아 주세요