[실습6] 원형 연결 리스트

소개글

자료구조

목차

○ 실습 문제 소개
○ 해결 과정 설명
○ 실습 결과
○ 작성자의 코멘트 기재

본문내용

○ 실습 문제 소개

❒ n명의 사람들이 원탁에 둘러 앉아 있다.
❒ 시작 위치로부터 k번째 사람은 원탁에서 빠진다. 그리고 다음 사람을 시작 위치로 하여 다시 반복한다.
❒ 마지막에 남은 한 사람은 누구인가?


○ 해결 과정 설명


▷ 프로그램 작성 과정

1. 노드 구조

2. 함수 구현

❒ n명의 사람들이 원탁에 앉아 있는 것을 노드로 구성.
n개의 노드에 각 데이터 값은 1,2,3 ᠁᠁ n-1, n 이다.
원탁에 앉아있기 때문에 마지막 노드는 제일 처음 노드를 가리킨다.

make( l , n)
for i 는 1 부터 n 까지 루프
p ← getNode();
p.data ← n - i + 1;
p.link ← l;
l ← p;
if (p.link = NULL) do
last ← l ;
last.link ← p ; //마지막노드는 제일 앞을 가리킨다.

return l ;

❒ 시작위치로부터 k번째 위치의 사람은 빠지게 하고 한사람이 남을 때 까지
반복 한다.
k가 1일 경우와 k가 2이상일 경우를 생각해서 두 가지 경우를 수행한다.
k값이 1인 경우 처음 노드부터 순서대로 삭제하고 마지막 노드가 남게
된다. 이때 마지막 노드가 가리키는 노드가 계속 해서 삭제되기 때문에
삭제한 노드의 다음 노드를 연결 해주었다.

참고 자료

없음