이 진 트 리 알고리즘 으로 인 한 사고: 포인터 파라미터 전달, 인용 함정

최근 에 기본 적 인 데이터 구조 와 알고리즘 을 익히 고 싶 어서 이 진 트 리 프로그램 을 썼 습 니 다. 기능 은 간단 하고 이 진 트 리 의 구축 과 옮 겨 다 니 기만 합 니 다.이 과정 에서 평소에 알 아차 리 지 못 했 던 세부 적 인 문 제 를 발견 하고 총 결 로 써 여러분 과 나 누 었 습 니 다.
 
토론 하고 직면 해 야 할 세부 적 인 문 제 는 다음 과 같다.
(1) 흔히 볼 수 있 는 고정 적 사고: 포인터 가 매개 변수 로 전달 되면 더 이상 값 을 부여 할 필요 가 없 습 니까? 포인터 가 가리 키 는 값 이 동기 화 되 기 때 문 입 니 다. 그러나 포인터 변수 자체 의 값 이 변경 되면 고려 해 본 적 이 있 습 니까?어 떡 하지?
(2) 자주 사용 하지 않 는 용법 입 니 다. 포인터 변수 에 대한 인용 을 사용 해 보 셨 습 니까?
 
전제:
(1) 필 자 는 자신 이 C 와 C + + 를 계속 헷 갈 리 게 사용 하 는 것 을 고려 하여 이 간단 한 알고리즘 프로그램 은 순수한 C 로 쓰 려 고 했 기 때문에 C 컴 파 일 러 를 사용 했다.
(2) C 와 C + + 의 차이 점 에 대해 필 자 는 시 리 즈 를 따로 써 서 정리 하고 분석 할 계획 이다.
(3) 또한 쓰기 연습 프로그램 이기 때문에 메모리 방출 방법 을 아직 추가 하지 않 았 습 니 다.
프로그램의 머리 정의 및 일반적인 방법:

#include <stdio.h>
#include <malloc.h>

#define TRUE 1
#define FALSE -1

typedef char ElemType; 
typedef int BOOL;

typedef struct _BinaryTreeNode
{
ElemType elem;
struct _BinaryTreeNode* left;
struct _BinaryTreeNode* right;
}BinareTreeNode, *BiTree;

void PrintNode(ElemType elem)
{
printf("%c ", elem);
}

void PreOrderTraverse(BinareTreeNode* pNode, void(* Visit)(ElemType elem))
{
if (NULL != pNode)
{
Visit(pNode->elem);
PreOrderTraverse(pNode->left, PrintNode);
PreOrderTraverse(pNode->right, PrintNode);
}
}

필자 가 최초 로 쓴 절 차 는 다음 과 같다.

void PreOrderCreateBinaryTree(BinareTreeNode* pNode)
{
ElemType elem;
scanf("%c", &elem);
if ('#' == elem)
{
pNode = NULL;
}
else
{
pNode = (BinareTreeNode*)malloc(sizeof(BinareTreeNode));
pNode->elem = elem;
PreOrderCreateBinaryTree(pNode->left);
PreOrderCreateBinaryTree(pNode->right);
}
}

int main()
{
BinareTreeNode* pHeadNode = NULL;
PreOrderCreateBinaryTree(pHeadNode);
PreOrderTraverse(pHeadNode, PrintNode);
return 0;
}

 
너 는 문제 가 어디 에 있 는 지 알 수 있 니?먼저 생각 하고, 서둘러 뒤 를 보지 마라.
 
구체 적 인 문제 현상:
이렇게 쓰 는 것 은 문제 가 없다 고 생각 했 는데, 실제로 main 함수 의 pHeadNode 값 은 NULL 이 었 기 때문에 PreOrder Traverse 에 서 는 아무런 값 출력 이 없 었 습 니 다.입력: ABC \ # \ # E \ # \ # C \ # \ # 옮 겨 다 니 며 출력: 아니요, 들 어 오 는 매개 변수 값 pHeadNode 가 NULL 이기 때 문 입 니 다.
 
구체 적 인 문제 분석:
왜 이러 지?
본 논문 에서 토론 한 첫 번 째 문 제 는 수면 위로 떠 올 랐 다. 흔히 볼 수 있 는 정식 사고: 지침 을 매개 변수 로 전달 하면 더 이상 할당 할 필요 가 없 습 니까?
분석:
포인터 전달 이지 만 main 함수 의 pHeadNode 는 포인터 변수 로 포인터 변수의 값 이 비어 있 으 며 가리 키 는 값 이 존재 하지 않 습 니 다.
PreOrderCreate Binary Tree 함수 의 형 삼 pNode 는 다른 포인터 변수 입 니 다. 처음에 그 값 은 main 함수 에서 들 어 왔 고 NULL 이 었 습 니 다. 나중에 pNode 는 malloc 를 통 해 다시 할당 되 었 습 니 다.
문 제 는 main 함수 의 pHeadNode 가 동기 화 되 었 습 니까?포인터 가 전달 되면 값 이 같이 바뀐다 며?
사실은 여기 서 저급 오 류 를 범 했 습 니 다. 즉, 지침 을 함수 의 매개 변수 로 사용 하고 지침 이 다시 할당 되 지 않 은 상황 에서 지침 이 가리 키 는 값 은 반드시 동기 화 되 어 변 경 될 것 입 니 다. 그러나 지침 이 하나의 변수 로 서 자체 의 값 이 변 경 될 경우 매개 변수 가 변 하지 않 을 것 입 니 다.
예 를 들 어:

（1）            
void FuncChangeObj(int* pInt)
{
(*pInt)++;
}
(2)           ，  ，                  ，         
void FuncNoChangeObj(int* pInt)
{
pInt = (int*)malloc(sizeof(int));
*pInt = 10;
}

이전 두 갈래 트 리 프로그램 이 먼저 옮 겨 다 니 는 데 성공 하지 못 한 것 은 먼저 두 갈래 트 리 를 만 들 때 두 갈래 트 리 의 뿌리 노드 를 되 돌려 주지 않 았 기 때문에 pHeadNode 는 NULL 이 었 습 니 다.
그렇다면 상기 프로그램 이 이 진 트 리 를 만 드 는 데 성 공 했 을 뿐 트 리 의 뿌리 노드 를 되 돌려 주지 않 았 다 는 것 일 까?그렇지 않 으 면 똑 같은 원인 이기 때문에 이 두 갈래 나 무 는 만 들 지 못 했 고 각 나무 노드 간 에 관련 이 없 으 며 모두 고립 된 노드 이다.
 
구체 적 인 문제 해결 의 길:
어떻게 수정 합 니까?다음 과 같은 답 을 드 립 니 다: 방법 1: 함수 가 지침 을 되 돌려 주 고 원본 지침 에 값 을 부여 합 니 다.

BinareTreeNode* PreOrderCreateBinaryTree(BinareTreeNode* pNode)
{
ElemType elem;
scanf("%c", &elem);
if ('#' == elem)
{
pNode = NULL;
}
else
{
pNode = (BinareTreeNode*)malloc(sizeof(BinareTreeNode));
pNode->elem = elem;
pNode->left = PreOrderCreateBinaryTree(pNode->left);
pNode->right = PreOrderCreateBinaryTree(pNode->right);
}
return pNode;
}

int main()
{
BinareTreeNode* pHeadNode = NULL;
pHeadNode = PreOrderCreateBinaryTree(pHeadNode);
PreOrderTraverse(pHeadNode, PrintNode);
return 0;
}

 
방법 2: 포인터 의 인용 을 사용 하여 값 을 전달 합 니 다. 즉, 포인터 변수 자 체 를 참조 하 는 것 입 니 다. 포인터 변수 값 전달 주 가 아 닙 니 다. 이 방법 은 두 번 째 문제 에 대한 설명 이지 만 주의해 야 합 니 다. 이 방법 은 C 언어 컴 파일 러 에서 컴 파일 에 성공 한 적 이 없고 C 언어 에 인용 개념 이 존재 하지 않 기 때 문 입 니 다.

void PreOrderCreateBiTree2(BiTree& T)
{
ElemType elem;
scanf("%c", &elem);
if ('#' == elem)
{
T = NULL;
}
else
{
T = (BinareTreeNode *)malloc(sizeof(BinareTreeNode));
T->elem = elem;
PreOrderCreateBiTree2(T->left);
PreOrderCreateBiTree2(T->right);
}
}

int main()
{
BiTree T = NULL;
PreOrderCreateBiTree2(T);
PreOrderTraverse(T, PrintNode);
return 0;
}