[C++] vector 사용 중에 포인터가 이상하게 꼬여버립니다.
안녕하세요
tree검색을 수행하는 프로그램을 작성 중에 문제가 생겨서 도움을 요청하고자 글을 올리게됬습니다.
struct Node {
char value;
Node *left;
Node *right;
Node(char val) { // 생성자
value = val;
left = NULL;
right = NULL;
}
};구조체를 이용해서 tree를 구성하려고 시도했습니다.
Input값의 형태는 parent_node, left_node, right_node형태로 받고있습니다.
ex) . 은 NULL을 가리킵니다.
A B C
B D .
C E F
E . .
F . G
D . .
G . .
전체 코드는 다음과 같습니다.
메인 아이디어는, A B C를 입력받았을 때, 자식 노드(B, C)는 추후에 부모 노드로써 정보가 주어지기 때문에 (B D .) (C E F)
vector에 자식 노드 리스트(B, C)를 추가하여 추후에 부모 노드로써 정보가 주어졌을 때 vector에서 검색해서 사용하려고 했습니다.
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
struct Node {
char value;
Node *left;
Node *right;
Node(char val) { // 생성자
value = val;
left = NULL;
right = NULL;
}
};
void preorder_traversal(Node *root, string *sequence);
void inorder_traversal(Node *root, string *sequence);
void postorder_traversal(Node *root, string *sequence);
int main()
{
Node root = Node('A');
vector<Node *> list(1, &root);
int N;
scanf("%d", &N);
getchar(); // delete 개행 문자(\n)
char parent, left, right;
for (int i = 1; i <= N; i++)
{
scanf("%c %c %c", &parent, &left, &right);
getchar(); // delete 개행 문자(\n)
Node *temp_left = NULL, *temp_right = NULL;
for (vector<Node *>::iterator iter = list.begin(); iter != list.end();) {
if ((*iter)->value == parent) {
if (left != '.') {
temp_left = &Node(left);
(*iter)->left = temp_left;
}
if (right != '.') {
temp_right = &Node(right);
(*iter)->right = temp_right;
}
iter = list.erase(iter);
break;
}
else
iter++;
}
if(temp_left != NULL)
list.push_back(temp_left);
if(temp_right != NULL)
list.push_back(temp_right);
}
string sequence;
preorder_traversal(&root, &sequence);
printf("%s\n", sequence.c_str());
sequence.clear();
inorder_traversal(&root,&sequence);
printf("%s\n", sequence.c_str());
sequence.clear();
postorder_traversal(&root,&sequence);
printf("%s\n", sequence.c_str());
sequence.clear();
return 0;
}
void preorder_traversal(Node *root , string *sequence)
{
if (root->left != NULL)
preorder_traversal(root->left, sequence);
sequence->push_back(root->value);
if (root->right != NULL)
preorder_traversal(root->right, sequence);
}
void inorder_traversal(Node *root, string *sequence)
{
sequence->push_back(root->value);
if (root->left != NULL)
inorder_traversal(root->left, sequence);
if (root->right != NULL)
inorder_traversal(root->right, sequence);
}
void postorder_traversal(Node *root, string *sequence)
{
if (root->right != NULL)
postorder_traversal(root->right, sequence);
sequence->push_back(root->value);
if (root->left != NULL)
postorder_traversal(root->left, sequence);
}디버깅을 해본 결과, 문제가 발생하는 부분입니다.
if (left != '.') {
temp_left = &Node(left);
(*iter)->left = temp_left;
}
if (right != '.') {
temp_right = &Node(right);
(*iter)->right = temp_right;
}처음에 A B C가 주어졌을 때,
temp_left = &Node('B')가 되어, temp_left는 B 노드를 가리키게 되고,
부모노드 A의 left포인터가 B 노드를 가리키게 됩니다. // (*iter)->left = temp_left;
마찬가지로 temp_right = &Node('C')가 되어 A 노드의 right포인터가 가리키게 됩니다.
그런데 문제는
B D .
가 다음 입력으로 주어졌을 때,
temp_left = &Node('D')가 실행되자마자
이전 부모 노드 A의 left 포인터가 B노드를 가리키다가 D노드로 바뀌여서 가리키게 되버렸습니다...(A->left = D)
(이 때, vector list에는 A노드에 대한 정보자체가 없어서 iter 반복자가 A노드에 접근자체가 불가합니다.)
추측상으로는 구조체의 left, right 포인터에 주소값이 직접적으로 들어간게 아니라
temp_left 또는 temp_right가 가리키는 주소값을 참조하는 도중에
temp_left 또는 temp_right의 값이 바뀌니까 이전 구조체의 left, right 포인터도 덩달아 바뀐걸로 보입니다....
이 문제에 대해 알고있거나 경험해보신 분 계신가요? ㅜㅜ
도움이 필요합니다..!
g++ 과 clang++ 모두 컴파일 에러를 내는군요
g++ 과 clang++ 모두 컴파일 에러를 내는군요.
ttt.c:39:28: error: taking address of temporary [-fpermissive] temp_left = &Node(left); ^ ttt.c:44:30: error: taking address of temporary [-fpermissive] temp_right = &Node(right); ^설명 안드려도 무엇이 잘못되었는지 아실 것 같습니다.
그리고 C 와 C++ 을 섞어 사용하셨군요. 기본적으로 C로 작성된 코드에 C++을 이상한 스타일로 섞어넣은 듯 한 모습입니다. 좋지 않은 스타일입니다. 몇 가지 눈에 띄는 것만 얼른 말씀드리자면 1) 생성자에서 멤버 변수를 초기화할 때에는 초기화 리스트 (initializer list) 를 사용하세요. 지금 하신 것 처럼 생성 후에 대입하지 마시구요. 2) iter++보다 ++iter가 더 효율적일 가능성이 큽니다. 최소한 덜 효율적이지는 않습니다. i의 경우도 i++ 보다 ++i 가 일반적으로 더 권장되는 습관입니다. 3) traversal 함수들에서 string을 포인터로 받는 것보다 레퍼런스로 받는 것이 좋습니다. 포인터 사용은 가능한 한 피하세요. 4) traversal 함수들은 Node를 수정하지 않는 것 같습니다. 그렇다면 const Node& 로 받으세요. 5) nullptr에 대해 찾아보세요. 6) stdio.h 말고 cstdio를 사용하세요. 7) cin / cout 대신 굳이 scanf / printf 를 사용할 이유가 없는 듯 합니다.
하나 하나 설명드리자면 힘들고 왜 그래야하는지 생각을 해보시고 검색을 해보시면 될 듯 합니다.
고마워요!
덕분에 해결했습니다 감사합니다 ㅜㅜ
그리고 천금같은 c++ 코딩 스타일 알려주셔서 고마워요 ㅎㅎ 덕분에 검색하면서 많이 배웠습니다~!!
...
음 뭐 사실 코딩 스타일은 잘못 건드리면 성전 내지는 지하드를 불러올 수 있으니 안 건드리는 게 상책입니다만...
...그냥 다른 분들을 위해서, 위에 나온 아이템 1-6이 절대적으로 옳은 건 아니고, 몇몇은 사람이나 조직에 따라 정 반대의 정책을 사용하는 경우도 종종 있다는 말씀을 드립니다.
댓글 달기