이중포인터를 쓰는 이유
이중포인터는 포인터의 메모리 주소를 저장하는 변수다. 포인터가 변수의 메모리 주소를 저장한다는 점에서 차이가 있다. 이중 포인터 그 자체는 의미가 없다. 하지만 이중포인터와 함수를 함께 쓴다면 그 의미가 살아난다.
이중포인터와 함수의 선언
#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 전략은 삭제 될 노드의 우측 자식 노드 중에 가장 작은 노드를 본인의 자리에 배치하는 전략이다.