최소 1개 이상의 노드로 이루어진 원형 연결 리스트(circular l… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
최소 1개 이상의 노드로 이루어진 원형 연결 리스트(circular linked list)에서 포인터 L이 리스트의 첫 번째 노드를 가리킨다고 할 때, 데이터의 값이 x인 노드를 탐색하여 반환하는 C 코드는?
1
ListNode *searchCList(ListNode *L, int x) {
ListNode *p=L;
while(p!=L) {
if(p->data==x) return p;
p=p->link;
}
return NULL;
}2
ListNode *searchCList(ListNode *L, int x) {
ListNode *p=L;
while(p->link!=L) {
if(p->data==x) return p;
p=p->link;
}
return NULL;
}3
ListNode *searchCList(ListNode *L, int x) {
ListNode *p=L;
do {
if(p->data==x) return p;
p=p->link;
} while(p!=L);
return NULL;
}4
ListNode *searchCList(ListNode *L, int x) {
ListNode *p=L;
do {
if(p->data==x) return p;
p=p->link;
} while(p->link!=L);
return NULL;
}해설
첫 노드부터 검사한 뒤 p가 다시 L로 돌아오면 멈추는 do-while(p!=L) 형태가 옳다.
원형 연결 리스트는 마지막 노드의 link가 첫 노드 L을 가리키므로 p가 L로 돌아오면 한 바퀴를 다 돈 것이다. 시작점 p가 이미 L이므로 조건 검사를 본문 실행 뒤에 해야 모든 노드를 검사할 수 있다.
- while(p!=L) 형태는 p=L에서 시작하므로 반복문이 한 번도 실행되지 않아 항상 NULL을 반환한다.
- while(p->link!=L) 형태는 마지막 노드에 도달하면 검사 전에 반복이 끝나 마지막 노드를 놓친다.
- do-while(p->link!=L) 형태도 p가 마지막 노드로 이동하는 순간 조건이 거짓이 되어 마지막 노드를 검사하지 못한다.
오류나 개정된 내용이 보이면 알려주세요