✅ [ WEEK05 ] 탐험준비 - C언어, 자료구조, 알고리즘
WEEK 진행률
🎯 1. 키워드 공부
- ☑️ 포인터
- ☑️ 가상화
- ☑️ GCC
- ☑️ 포인터의 연산
- ☑️ 동적 메모리 할당
- ☑️ malloc, calloc, realloc
- ❗️B Tree
- ❗️위상정렬
- ❗️Trie
- ❗️KMP 알고리즘
- ❗️보이어-무어 알고리즘
🎯 2. 테스트 케이스
- ☑️ Linked List
- ☑️ Stack
- ☑️ Queue
- ☑️ Binary Tree
- ☑️ Binary Search Tree
🎯 3. 책 읽기
- ☑️ CS APP : 6장 메모리 계층구조
진행률 : 70%
트러블 슈팅 : 포인터는 꼭 초기화 하자
C언어는 정말 어려운 것 같습니다..
저는 Stack 과 Queue 를 사용할 때, 포인터 초기화를 안해줘서 코드가 예상치 못하게 동작하는 경험을 했어요.
포인터가 어떻게 동작하는지 확인하고, 제 코드의 어떤 부분에서 문제가 생겼는지 볼게요.
엄청 간단한 함수입니다.
변수 a를 선언하고 int* 에 a 의 주소를 할당해줬어요.
그리고 포인터 변수 p를 출력하면 , a의 주소가 정상적으로 출력되는 것을 확인할 수 있습니다.
근데 만약 포인터 변수에 아무것도 안 넣으면 어떻게 될까요?
int* p와 우리가 과제를 해결하면서 사용했던 Stack의 top값을 출력해 보았습니다.
int* p 에는 운좋게 NULL값이 들어있었지만
우리고 초기화 해주지 않은 Stack의 top 값에는 알 수 없는 주소가 들어있습니다.
이렇게 포인터를 초기화 해주지 않으면 쓰레기 값(garbage value) 가 들어있게 됩니다.
즉, 임의의 주소값이 들어있게 되며, 이로 인해 코드가 예상치 못하게 동작할 수 있어요.
왜 이러냐면 C 언어는 성능 우선언어라 int *p를 자동으로 초기화 해주면 성능 오버헤드가 생긴대요.
그래서 메모리만 잡아주고 값은 초기화 하지 않아요.
그래서 잡힌 메모리가 NULL 이면 운 좋게 NULL 이 되겠지만, 그렇지 않으면 원래 그 메모리 주소에 있던 임의의 값이 저장되는거예요.
이렇게 NULL 초기화를 해주지 않았을 때 어떤 문제가 생겼을까요?
Q4_F_BST.c ( 스택을 사용한 중위 순회 )
이 코드는 제가 트리의 중위순회를 해결한 코드지만, s.top 의 값을 주석처리 해주는 부분을 초기화해서 제대로 작동하지 않아요.
왜냐하면 push 와 pop 연산이 예측대로 동작하지 않기 때문이예요.
우리가 Stack 의 top 값을 초기화 해주지 않고, NULL이 있을거라 생각하고 코드를 작동하면
실제로 Stack 의 값에는 아까 봤던 쓰레기 값이 들어있기 때문에 이 코드는 else 문으로 넘어갈 거예요.
그리고는 Stack 의 top 에 있던 쓰레기 주소를 temp->next 에 담을 거예요. 거기는 정체불명 뭐가 있을지 몰라요.
- NULL 값일 수도 있고
- Segmentation Falut 가 날수도 있고
- free() 를 해줄 때, 할당 안 된 주소를 해제하려고 하기 때문에 오류가 날 수 있어요.
그래서 반드시!!!
포인터를 쓸 때는 값을 초기화 해주거나, 값을 할당해주자!
void inOrderTraversal(BSTNode *root)
{
// root 가 NULL 값이면 필요없잖아
if ( root == NULL ) return;
// 스택 초기화
Stack s;
s.top = NULL;
BSTNode *current = root;
// 왼쪽 루트 오른쪽을 어떻게 할까?
// 스택이 비고 current 가 NULL 일때까지 반복
while( current != NULL || !isEmpty(&s) ) {
// 현재 노드를 따라 계속 왼쪽으로 push
while ( current != NULL ) {
push(&s , current);
current = current->left;
}
// 왼쪽이 끝나면 pop 해서 출력, 그리고 오른쪽 자식으로 이동.
current = pop(&s);
printf("%d " , current->item);
// 그리고 오른쪽으로 이동
current = current->right;
}
}