2024.04.15(월) - 이중포인터를 쓰는 이유, 재귀함수의 표현, BST,

이중포인터를 쓰는 이유

이중포인터는 포인터의 메모리 주소를 저장하는 변수다. 포인터가 변수의 메모리 주소를 저장한다는 점에서 차이가 있다. 이중 포인터 그 자체는 의미가 없다. 하지만 이중포인터와 함수를 함께 쓴다면 그 의미가 살아난다.

이중포인터와 함수의 선언

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

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;            // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;            // You should not change the definition of LinkedList


//////////////////////// function prototypes /////////////////////////////////////

// You should not change the prototype of this function
int testFunction1(ListNode **ptrHead);
int testFunction2(ListNode *ptrHead);

int main()
{
    LinkedList ll;
    ll.head = NULL;
    ll.size = 0;

    testFunction1(&(ll.head));
    testFunction2((ll.head));

    return 0;
}

int testFunction1(ListNode **ptrHead) 
{
    ListNode *cur = malloc(sizeof(ListNode));
    cur->item = 0;
    cur->next = NULL;

    *ptrHead = cur;

    return 0;
}

int testFunction2(ListNode *ptrHead)
{
    ListNode *cur = malloc(sizeof(ListNode));
    cur->item = ptrHead->item;
    return 0;
}

포인터를 통해 구조체의 구조를 변경할 때 포인터 값 대신에 포인터 메모리주소를 전달하면 된다. 포인터 값을 전달하면 구조체의 구조를 바꿀 수는 없고 구조체의 구조의 데이터 정보를 바꿀 수 있다. 값에 의한 함수 호출과 주소에 의한 함수호출 개념과 포인터 개념을 합친 것이 이중포인터의 용도가 된다.

재귀함수의 표현

사진으로 대체한다. 친구가 재귀함수의 작동원리를 설명했는데 그 어떤 교재보다도 직관적인 도해였다.

BST

이진탐색트리는 이진탐색을 트리계층을 활용해서 표현한 자료구조다.

이진탐색트리의 노드 삽입은 간단하다.
좌측 자식노드는 부모노드보다 작아야하고 우측 자식노드는 부모노드보다 커야한다.

이진탐색트리의 노드 삭제는 조금 더 복잡하다.
삭제 될 노드가 자식이 없는 경우, 1개 있는 경우, 2개 있는 경우로 나눌 수 있다.

자식이 없는 경우에는 삭제하면 된다.

자식이 1개가 있는 경우, 삭제 될 노드의 부모노드와 삭제 될 노드의 자식노드를 새로운 부모자식관계로 만들어주면 된다.

자식이 2개가 있는 경우, 2가지 전략으로 구분한다.successor 전략과 predecessor 전략 2가지다.
successor 전략은 삭제 될 노드의 좌측 자식 노드 중에 가장 큰 노드를 본인의 자리에 배치하는 전략이다.
predecessor 전략은 삭제 될 노드의 우측 자식 노드 중에 가장 작은 노드를 본인의 자리에 배치하는 전략이다.