[ 알고리즘] Do it 자료구조와 함께 배우는 알고리즘 9장 정리

연습문제 Q_1 > 비교 함수인 compare 함수를 사용해 서로 같으 노드를, 가장 앞쪽의 노드를 남기고 모두 삭제하는 다음의 함수를 작성하세요.

void Purge(List *list, int compare(const Member *x, const Member *y));

// Q_1 서로 같은 노드가 여러개인 경우 가장 앞쪽의 노드를 남기고 모두 삭제.
void Purge(List *list, int compare(const Member *x, const Member *y)) {
    
    Node *ptr = list->head;
    Node *next_ptr;
    while(ptr != NULL) { // 맨 처음, 노드가 없다는 경우에도 자동 종료됨(list->head == NULL일 경우)
        next_ptr = ptr->next;
        
        while(next_ptr != NULL) {
            if(compare(&ptr->data, &next_ptr->data) == 0) {
                // next_ptr이 절대 머리노드는 아니므로, 머리노드를 제외한 삭제를 담당하는 RemoveCurrent를 사용하기 위해
                // crnt 값을 업데이트
                list->crnt = next_ptr;
                RemoveCurrent(list);
            }
            next_ptr = next_ptr->next;
        }
        ptr = ptr->next;
    }
    // 제공된 정답에서 Purge를 끝내면 list->crnt = list->head 하는데, 꼭 이렇게 해야만 하나? 왜해주나 싶음..
    list->crnt = list->head;
}

// 정답제공 Purge :
// 나처럼 RemoveCurrent를 쓰는 대신에, 변수를 3개 사용하고 직접 삭제하는 과정을 넣어줌.
//void Purge(List *list, int compare(const Member *x, const Member *y))
//{
//    Node *ptr = list->head;
//
//    while (ptr != NULL) {
//        Node *ptr2 = ptr;
//        Node *pre = ptr;
//
//        while (pre->next != NULL) {
//            ptr2 = pre->next;
//            if (!compare(&ptr->data, &ptr2->data)) {
//                pre->next = ptr2->next;
//                free(ptr2);
//            }
//            else {
//                pre = ptr2;
//            }
//        }
//        ptr = ptr->next;
//    }
//    list->crnt = list->head;
//}

내 방식은 RemoveCurrent를 사용한다. 아무래도 list->crnt의 '앞쪽 노드'를 다시 리스트 헤드부터 찾아줘야 하니까

정답 제공인 후자의 코드보다 조금 느릴 수 있다. 정답 제공인 후자의 코드는, 변수를 하나 더 둬서, 발견되는 즉시 직접 해제한다.

 

Q. Purge의 마지막에 list->crnt = list->head는 왜 꼭 해주는걸까.

 

 

연습문제 Q_2 > 머리부터 n개 뒤의 노드에 대한 포인터(n이 0이면 머리노드에 대한 포인터, n이 1이면 두 번째 노드에 대한 포인터...)를 반환하는 다음의 함수를 작성하세요. n이 음수거나 노드 개수보다 크거나 같으면 NULL을 반환합닌다.

Node *Retrieve(List *list, int n);

// Q_2 머리부터 n개 뒤의 노드에 대한 포인터를 반환하는 함수를 작성
Node *Retrieve(List *list, int n) {
    //n이 0이면 머리 노드에 대한 포인터, 1이면 두번째 노드에 대한 포인터.
    //n이 음수거나 노드 개수보다 크거나 같으면 NULL 반환
    
    Node *ptr = list->head;
    while(n > 0 && ptr != NULL) { // ptr != NULL로 인해, 맨 처음 리스트가 없는 경우도 체킹됨.
        n--;
        ptr = ptr->next;
    }
    // n이 첨부터 음수였거나, 혹은 리스트의 노드 갯수들보다 많다면 n은 0이 아니게 됨.
    // 나머지 경우들은 모두 n이 0으로 종료됨.
    if( n != 0 || ptr == NULL) // n 이 처음부터 0이면서 head가 NULL일 경우 & n번째가 NULL인 경우가 있으니, ptr == NULL 추가
        return NULL;
    
    list->crnt = ptr;
    return ptr;
    
}

// 정답제공 Retrieve : 내 코드와 비슷하나 조금 더 직관적임.
//Node *Retrieve(List *list, int n)
//{
//    Node *ptr = list->head;
//
//    while (n >= 0 && ptr != NULL) {
//        if (n-- == 0) {
//            list->crnt = ptr;
//            return ptr;                // 검색 성공
//        }
//        ptr = ptr->next;            // 다음 노드 선택
//    }
//    return NULL;                    // 검색 실패
//

 

연습문제 Q_3 > 앞에서 포인터로 만든 연결 리스트에 대해 연습문제 Q1과 Q2의 과제를 수행했다. 같은 방법으로 배열 커서로 만든 연결 리스트에 대해 같은 과제를 수행하시오.

// Q_3-1 서로 같은 노드가 여러개인 경우 가장 앞쪽의 노드를 남기고 모두 삭제.
void Purge(List *list, int compare(const Member *x, const Member *y)) {
    
    Index ptr = list->head;
    Index next_ptr;
    while(ptr != Null) {
        next_ptr = list->n[ptr].next;
        
        while(next_ptr != Null) {
            if(compare(&list->n[ptr].data, &list->n[next_ptr].data) == 0) {
                // next_ptr이 절대 머리노드는 아니므로, 머리노드를 제외한 삭제를 담당하는 RemoveCurrent를 사용하기 위해
                // crnt 값을 업데이트
                list->crnt = next_ptr;
                RemoveCurrent(list);
            }
            next_ptr = list->n[next_ptr].next;
        }
        ptr = list->n[ptr].next;
    }
    list->crnt = list->head;
}

// 정답 제공 Purge : 이전 정답Q1과 같은 방식이며, RemoveCurrent 안의 작업을 if문 내에서 해주고 있음.
// 마찬가지로 마지막에 list->crnt = list->head 이유는 모르겠음.
//--- 비교 함수를 사용하여 같은 노드를 삭제
//void Purge(List *list, int compare(const Member *x, const Member *y))
//{
//    Index ptr = list->head;
//
//    while (ptr != Null) {
//        Index ptr2 = ptr;
//        Index pre = ptr;
//
//        while (list->n[ptr2].next != Null) {
//            ptr2 = list->n[pre].next;
//            if (!compare(&list->n[ptr].data, &list->n[ptr2].data)) {
//                list->n[pre].next = list->n[ptr2].next;
//                DeleteIndex(list, ptr2);
//            }
//            else {
//                pre = ptr2;
//            }
//        }
//        ptr = list->n[ptr].next;
//    }
//    list->crnt = list->head;
//}

------

// Q_3-2 머리부터 n개 뒤의 노드에 대한 포인터를 반환하는 함수를 작성 (여기선 인덱스=레코드로 했음)
Index Retrieve(List *list, int n) {
    
    Index ptr = list->head;
    while(n > 0 && ptr != Null) { // ptr != Null로 인해, 맨 처음 리스트가 없는 경우도 체킹됨.
        n--;
        ptr = list->n[ptr].next;
    }
    
    // n이 첨부터 음수였거나, 혹은 리스트의 노드 갯수들보다 많다면 n은 0이 아니게 됨.
    // 나머지 경우들은 모두 n이 0으로 종료됨.
    if( n != 0 || ptr == Null) // n 이 처음부터 0이면서 head가 Null일 경우 & n번째가 Null인 경우가 있으니, ptr == Null 추가
        return Null;
    
    list->crnt = ptr;
    return ptr;
    
}
// 정답제공 Retrieve : 이전 정답Q2와 같은 방식. 마찬가지로 내 코드와 비슷하나 조금 더 직관적임.
//Index Retrieve(List *list, int n)
//{
//    Index ptr = list->head;
//
//    while (n >= 0 && ptr != Null) {
//        if (n-- == 0) {
//            list->crnt = ptr;
//            return ptr;                    /* 검색 성공 */
//        }
//        ptr = list->n[ptr].next;        /* 다음 노드 선택 */
//    }
//    return Null;
//}

 

 

연습문제 Q_4 > 363쪽의 연습문제로 풀었던 Q1, Q2와 같은 방법으로 원형 이중 연결 리스트 프로그램을 이용해 Purge, Retrieve 함수를 작성하세요.

// Q_4-1 서로 같은 노드가 여러개인 경우 가장 앞쪽의 노드를 남기고 모두 삭제.
void Purge(Dlist *list, int compare(const Member *x, const Member *y)) {
    
        
    Dnode *ptr = list->head->next;
    Dnode *next_ptr;
    while(ptr != list->head) {
        next_ptr = ptr->next;
        
        while(next_ptr != list->head) {
            if(compare(&ptr->data, &next_ptr->data) == 0) {
                // next_ptr이 절대 머리노드는 아니므로, 머리노드를 제외한 삭제를 담당하는 RemoveCurrent를 사용하기 위해
                // crnt 값을 업데이트
                // 또는 이 CircDblLinkedList에서는 Remove(list, next_ptr)를 사용해도 가능.
                list->crnt = next_ptr;
                RemoveCurrent(list);
            }
            next_ptr = next_ptr->next;
        }
        ptr = ptr->next;
    }
    
    list->crnt = list->head;

}
// 정답 제공 Purge : 이전 정답Q1과 같은 방식.
//void Purge(Dlist *list, int compare(const Member *x, const Member *y))
//{
//    Dnode *ptr = list->head->next;
//
//    while (ptr != list->head) {
//        Dnode *ptr2 = ptr;
//        Dnode *pre = ptr;
//
//        while (pre->next != list->head) {
//            ptr2 = pre->next;
//            if (!compare(&ptr->data, &ptr2->data)) {
//                pre->next = ptr2->next;
//                free(ptr2);
//            }
//            else {
//                pre = ptr2;
//            }
//        }
//        ptr = ptr->next;
//    }
//    list->crnt = list->head;
//}

이전 리스트들과 달리, 원형 이중 연결 리스트는 list->head가 더미 노드로써 항상 존재하는 노드이므로, 반복문 탈출은 NULL이 아닌 list->head로 체크한다.

 

이전에 Purge에서 삭제할 때 RemoveCurrent함수를 사용했었다, 이번에도 마찬가지로 사용했는데, 이전의 한 방향 연결 리스트는 삭제할  list->crnt를 지정해주더라도 RemoveCurrent 함수에서 다시 list->crnt 이전의 노드를 리스트 헤드부터 찾아줘야 해서, 정답제공의 코드처럼 삭제할 노드의 이전 노드를 미리 알았다가 바로 그 자리에서 삭제하고 해제하는 일에 비해 수고를 덜어야 했다.

하지만 이중 연결 리스트 같은 경우에는 돌지 않아도 바로 그 자리에서 prev로 구할 수 있기 때문에, RemoveCurrent 함수를 이용함으로써의 비 효율성을 이전보다 조금 덜게 되었다고 볼 수 있다. (물론 아예 처음부터 항상 정답제공방식처럼 그 자리에서 직접 삭제해주는게 항상 효율이 좋긴해)

 

// Q_4-2 머리부터 n개 뒤의 노드에 대한 포인터를 반환하는 함수를 작성
Dnode *Retrieve(Dlist *list, int n) {
    //n이 0이면 머리 노드에 대한 포인터, 1이면 두번째 노드에 대한 포인터.
    //n이 음수거나 노드 개수보다 크거나 같으면 NULL 반환
    
    Dnode *ptr = list->head->next;
    while(n > 0 && ptr != list->head) { // ptr != list->head로 인해, 맨 처음 리스트가 없는 경우(더미노드만 있는 경우)도 체킹됨.
        n--;
        ptr = ptr->next;
    }
    // n이 첨부터 음수였거나, 혹은 리스트의 노드 갯수들보다 많다면 n은 0이 아니게 됨.
    // 나머지 경우들은 모두 n이 0으로 종료됨.
    if( n != 0 || ptr == list->head) // n 이 처음부터 0이면서 list->head일 경우(리스트가 비어 있음=더미노드만 있음) & n번째가 list->head인 경우(리스트의 끝 다음으로 온 것임)가 있으니, ptr == list->head 추가
        return NULL;
    
    list->crnt = ptr;
    return ptr;
    
}
// 정답 제공 Retrieve : 이전 정답Q2와 같은 방식. 내 코드보다 조금 더 직관적임.
//Dnode *Retrieve(Dlist *list, int n)
//{
//    Dnode *ptr = list->head->next;
//
//    while (n >= 0 && ptr != list->head) {
//        if (n-- == 0) {
//            list->crnt = ptr;
//            return ptr;
//        }
//        ptr = ptr->next;
//    }
//    return NULL;
//}

 

 

참고로 원형 이중 연결 리스트에서 헷갈릴 수 있는 건, 원형 이중 연결 리스트에서는 항상 더미노드라는 노드가 존재하기 때문에 

리스트의 끝이나, 리스트의 비어 있는 상태를 NULL이 아닌 

list->head (더미 노드)를 활용해서 체크한다. (검색 결과를 찾지 못했을 때의 NULL과는 별개)

 

list->head->next == list->head 일 경우, 리스트가 비어 있는 것.

리스트의 노드 중 하나를 가리키는 p가 있을 때, p->next == list->head일 경우 p는 꼬리 노드인 것.

 

 

원형 이중 연결 리스트에서 리스트 탐색 예시 (search 함수)

Dnode *ptr = list->head->next;

while(ptr != list->head) {
    // ~~~~
    ptr = ptr->next;
}

이렇게 되면

1. 리스트가 비어 있을 때

list->head->next == list->head 참이므로 바로 반복문 탈출

(더미 노드는 모든 포인터가 자기 자신을 가리킴)

 

2. 리스트의 마지막을 넘어갔을 때

.... ptr->next == list->head 참이므로 돌다가 마지막 노드는 다시 더미 노드를 가리키므로 반복문 탈출

 

 

공부 내용 정리

 

 

리스트 

데이터를 순서대로 나열한(줄지어 늘어놓은) 자료구조. 

A(처음) B C D E F(끝) 

리스트는 순서가 있는 데이터를 나열한 구조다.
+ 스택과 큐도 리스트 구조다. 

가장 단순한 구조를 가진 리스트로는
선형 리스트(linear list)와 연결 리스트(linked list)가 있다.
-> 선형 리스트와 연결 리스트는 다르다.



선형 리스트(Linear list) 

배열과 같이 연속되는 기억장소에 저장되는 리스트.


선형 리스트 장단점 

장점 : 접근 속도가 빠르다.
단점 : 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않다.



연결 리스트(Linked list) 

자료들이 반드시 연속적으로 배열되어있지 않아도 노드 포인터 부분을 이용하여 서로 연결되어진 구조. 

선형리스트와는 달리, 노드부분에 다음 노드를 가리키는 노드 포인터가 포함되어 있다. 

A(머리 노드) -> B -> C -> D -> E -> F(꼬리 노드) 

데이터가 순서대로 나열되어 있고, 각각의 데이터가 한 방향의 화살표로 연결되어 있다. 

이처럼 연결되어 있는 형태여서, 건너뛸 수 없다. 

이 때 리스트의 각 데이터는 노드 또는 요소라고 한다. 

각각의 노드는 데이터와(값) 다음 노드를 가리키는 포인터를 가지고 있다. 

처음과 끝에 있는 노드를 특별히 머리 노드(Head node), 꼬리 노드(Tail node)라고 한다. 

하나의 노드에 대해, 바로 앞에 있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고 한다.
- 위에서 노드 C의 앞쪽 노드는 노드 B이고, 다음 노드는 노드 D다. 이 때 노드 C가 갖는 포인터는 다음 노드인 노드 D를 가리킨다.


연결 리스트 장단점
장점 : 데이터의 삽입, 삭제가 용이
단점 : 접근속도가 느리다.



포인터로 구현하는 연결 리스트


노드 객체
typedef struct __node {
Member data; //데이터
struct __node *next //다음 노드를 가리키는 포인터(자기 자신과 같은 구조체를 가리킨다)
} Node; 

위의 노드객체와 같이, 자기 자신과 같은 자료형의 객체를 가리키는 데이터를 가지고 있는 자료구조를 '자기참조형'이라고 한다. 따라서 이 구조체는 자기 참조 구조체다. 

next 멤버변수는 해당 노드의 다음 노드를 가리키는 포인터다. 다음 노드를 갖지 않는 꼬리 노드의 next 값은 NULL값을 대입한다. 

자기 참조라는 말에 속아 next가 항상 자기 자신을 가리키는 포인터라고 착각할 수 있는데, 자기 참조 구조체란 자기 자신과 같은 자료형의 객체를 가리키는 포인터를 멤버로 가지고 있다는 뜻이다. 

+ 자기참조형에서의 주의점
typedef struct __node {
Member data; //데이터
struct __node *next //다음 노드를 가리키는 포인터(자기 자신과 같은 구조체를 가리킨다)
} Node;
여기서 next의 자료형을 struct __node *가 아닌 Node *로 하면 컴파일 오류가 생기는데, Node형의 typedef 선언이 완료되지 않은 상태이기 때문이다.




커서로 연결 리스트(Linked List) 만들기 

각 노드를 배열 안의 요소에 저장하고, 그 요소를 잘 이용해 연결 리스트를 구현. 

프로그램 실행 중에 데이터의 개수가 크게 바뀌지 않고 데이터 개수의 최댓값을 미리 알 수 있다고 가정하면 배열을 사용해 연결 리스트를 운용할 수 있다. 

배열의 커서에 해당하는 값은 다음 노드에 대한 포인터가 아니라, 다음 노드가 들어 있는 요소의 인덱스에 대한 값이다. 포인터 역할을 해주는 Cursor 는 이렇게 인덱스값을 담는다. 

이 때, 일반적인 방법으로는 배열의 요소가 삭제될 때 해당 자리가 사용되지 않는 점을 보완하여 커서 기반의 연결리스트 구현 안에서 프리 리스트를 도입한다. 

프리 리스트
삭제한 레코드를 관리하기 위한 리스트 

커서 기반의 연결리스트를 구현하되, 그 안에서 삭제한 레코드를 관리하기 위한 부품으로써 프리 리스트를 도입하여, 프리 리스트에 등록된 레코드가 없다면 배열 꼬리 이후의 레코드를 사용하고, 프리 리스트에 등록된 레코드가 있다면 그 레코드값을 인덱스값으로 사용하여 새 요소를 넣는다.



원형 리스트 

연결 리스트의 꼬리 노드가 머리 노드를 가리키면 원형 리스트라고 합니다. 꼬리 노드의 다음 노드를 가리키는 포인터가 NULL이 아니라 머리 노드의 포인터 값인 것.


이중 연결 리스트(Doubly Linked List) 

각 노드에는 다음 노드에 대한 포인터와 앞쪽의 노드에 대한 포인터가 주어진다. 

이중 연결 리스트의 노드
typedef struct __node {
Member data; // 데이터
struct __node *prev; // 앞쪽 노드에 대한 포인터
struct __node *next; // 다음 노드에 대한 포인터
} Dnode;


원형 이중 연결 리스트(circular doubly linked list) 

위의 두 개념을 합함.

 

 

 

출처 - '자료구조와 함께 배우는 알고리즘 입문 C언어 편'  도서