[자료구조 4장] - 연결리스트(4)

연결리스트(4)

 

원형 연결리스트

 

구조와 구현방법

단순 연결리스트의 마지막 노드 포인터 : NULL

이 마지막 노드 포인터를 첫 번째 노드(head node)의 주소를 가리키도록 할 때 이 리스트를 원형 연결리스트 라고 한다.

 

원형 연결리스트의 장점 : 어느 하나의 노드로부터 다른 모든 노드로 접근 가능, 검색 시 처음부터 찾지 않고 현재 노드부터 검색 가능, 리스트 결합도 효율적

 

주의 : 검색을 끝낼 수 있는 노드가 있어야 한다. 없으면 무한루프에 걸릴 수 있다.

 

학생번호와 학점을 노드에 저장한 자기참조구조체 struct cnode를 다음과 같이 정의하고 이를 기본으로 원형 연결리스트의 구조와 구현방법에 대하여 알아보자.

typedef struct cnode *npointer;
struct cnode {
    int num;
    char grade;
    npointer link;
};
npointer ptr = NULL;

 

이러한 노드구조를 가진 연결리스트에 노드를 원형 연결리스트로 구축하는 함수 build()를 살펴보자.

void build(npointer inode)
{
    if(!ptr) {
        ptr = inode;
        inode->link = inode;
    }
    else {
        inode->link = ptr->link;
        ptr->link = inode;
    }
}

 

원형리스트에 노드가 하나도 없는 빈 리스트인 경우, 리스트의 포인터 ptr은 NULL로 초기화 되어있다. 이떄 처음 노드를 삽입하기 위해 할당받은 inode의 num에 180, grade에 B의 값을 가지고 위 함수에 적용하면, 코드 1열의 if의 조건을 만족하여 2열과 3열의 문장을 수행한 후 num : 180, grade : B, link : ptr로 구성된 노드가 만들어지고 link에서 inode 가리키며 자기 자신을 가리키는 노드를 만들게 된다.

 

이후 inode의 num에 230, grade에 C의 값을 가지고 build() 함수를 적용하면 코드 1열의 if 조건을 만족하지 못하므로 else문의 6열과 7열의 문장을 수행한 후 다음과 같이 된다.

 

2개의 노드 원형 연결리스트 만들기

 

이를 응용한 프로그램을 알아보자.

 

응용 프로그램

이전에 설명한 노드구조 cnode를 가지고 원형 연결리스트를 구축하고 구축된 자료구조를 순회하여 데이터를 출력하는 함수 c_print()와 연결리스트의 데이터 수를 구하는 함수 how_many()를 작성하여 실습하면서 원형 연결리스트의 개념을 더 명확히 하자.

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

typedef struct cnode *npointer;
struct cnode {
    int num;
    char grade;
    npointer link;
};

void build(npointer node);
void c_print();
int how_many();
npointer ptr = NULL;

void main()
{
    int cond = 1;
    npointer temp;
    while (cond) {
        temp = (npointer)malloc(sizeof(struct cnode));
        printf("Enter id and grade: ");
        scanf("%d %c", &(temp->num), &(temp->grade));
        build(temp);
        printf("Continue?(0/1): ");
        scanf("%d", &cond);
    }
    c_print();
    printf("The number of nodes in this list = %d\n", how_many());
}

void build(npointer inode)
{
    if (!ptr) {
        inode->link = inode;
        ptr = inode;
    else {
        inode->link = ptr->link;
        ptr->link = inode;
    }
}

void c_print()
{
    npointer temp = ptr;
    if (ptr) {
        do {
            temp = temp->link;
            printf("%d: %c\n", temp->num, temp->grade);
        } while (temp != ptr);
    }
}

int how_many()
{
    npointer temp;
    int count = 0;
    if (ptr) {
        temp = ptr;
        do {
            count++;
            temp = temp->link;
        } while (temp != ptr);
    }
    return count;
}

 

실행결과

Enter id and grade : 180 B
Continue?(0/1) : 1
Enter id and grade : 230 C
Continue?(0/1) : 1
Enter id and grade : 100 B
Continue?(0/1) : 0
100 : B
230 : C
180 : B
The number of nodes in this list = 3

 

다음에는 이중 연결리스트에 대해 알아보도록 하자.