책보면서 어떻게든 트리구조를 자고 있습니다.. 부탁드립니다..
글쓴이: rainbow2316 / 작성시간: 화, 2013/11/12 - 11:21오후
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
char data;
struct TreeNode *left, *right;
}TreeNode;
#define MAX_STACK_SIZE (100)
typedef TreeNode* element;
typedef struct
{
element stack[MAX_STACK_SIZE];
void postorder(TreeNode *p);
element push(StackType *s, TreeNode *p);
element pop(TreeNode *p);
TreeNode * makeET(char *expr, StackType *s);
int evalET(TreeNode *p);
int main()
{
StackType s;
top = -1;
char expr[10];
printf("input expr :");
scanf("%s", expr);
makeET(expr,s);
inorder(?);
preorder(?);
postorder(?);
}
TreeNode * makeET(char *expr, StackType *s)
{
char ch;
TreeNode *p;
while(*expr != '\0')
{
ch = *expr;
switch(ch)
{
case '+':
case '-':
int top;
}StackType;
int sum=0;
void inorder(TreeNode *p);
void preorder(TreeNode *p);
case '*':
case '/':
p = (TreeNode*)malloc(sizeof(TreeNode));
p->data = ch;
p->right = pop(s);
p->left = pop(s);
push(s, p);
break;
default:
p = (TreeNode*)malloc(sizeof(TreeNode));
p->data = ch;
p->right = NULL;
p->left = NULL;
push(s,p);
break;
}
}
}
element push(StackType *s, TreeNode *p)
{
return s->stack[++(s->top)] = p;
}
element pop(StackType *s)
{
return s->stack[(s->top)--];
}
void inorder(TreeNode *p)
{
if(p != NULL)
{
inorder(p->left);
printf("%d", p->data);
inorder(p->right);
}
}
void preorder(TreeNode *p)
{
if( p != NULL)
{
printf("%d", p->data);
preorder(p->left);
preorder(p->right);
}
}
void postorder(TreeNode *p)
{
if(p != NULL)
{
postorder(p->left);
postorder(p->right);
printf("%d", p->data);
}
} 자료구조를 배우고 있습니다. 전역하고 공부한지 얼마 안 되지만... 일단 책보면서 어떻게든 해보고 있습니다...
근데 .. 여기서 입력을 후위연산자로 입력을 해서 전,중,후위 트리로 출력을 할려고 하는데 ...
어떻게 책보고 꾸역꾸역 해보긴 했는데 어떻게 고쳐야 할 지 모르겠습니다.
아직은 어렵네요 자료구조가 ..머릿속으로는 이해가 되긴 하는데 ... 이걸 소스로 옮기는게 아직은 저에게 능력이 부족한가봅니다 ...ㅠ
더 공부를 해야하는데 너무 답답해서 글을 올려봅니다...ㅠ 부탁드립니다. . .
Forums:
일단. 계산기 먼저 만들어보세요 ㅇ_ㅇ;;
대충 코드 정리는 해보지만... 저도 머리가 나쁘네요. ㅡ_ㅡ;;
만화로 차근 차근 설명하면 더 잘 만들텐데 말입니다.
문서로 만들어 놓긴 했는데. 원하시는 답변과 맞는지는 모르겠습니다. 참고해보세요.
그리고. 밤에 너무 무리하시면. 건강에 해롭습니다.
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct TreeNode { char data; struct TreeNode *left, *right; }TreeNode; #define MAX_STACK_SIZE 100 typedef TreeNode* element; typedef struct DF_ST { int top; element stack[MAX_STACK_SIZE]; }StackType; element push(StackType *s, TreeNode *p) { s->top++; printf("PUSH %c \t\t\t\t", p->data); int i=0; while(1) { if(s->stack[i] == 0x00) break; printf("%c", s->stack[i]->data); i++; } printf("%c", p->data); printf("\n"); return s->stack[s->top] = p; } element pop(StackType *s) { s->top--; if(s->stack[s->top] != 0x00) { printf("POP %c \t\t\t\t", s->stack[s->top]->data); } int i=0; while(1) { if(s->stack[i] == 0x00) break; printf("%c", s->stack[i]->data); i++; } printf("\n"); return s->stack[s->top]; } TreeNode * makeET(char *expr, StackType *s) { char ch; TreeNode *p; int len; int i=0; while(1) { ch = *(expr+i); if( *(expr+i) == '\0' ) { break; } switch(ch) { case '+': case '-': case '*': case '/': len = sizeof(TreeNode); p = (TreeNode*)malloc(len); p->data = ch; p->right = pop(s); p->left = pop(s); push(s, p); break; default: len = sizeof(TreeNode); p = (TreeNode*)malloc(len); p->data = ch; p->right = NULL; p->left = NULL; push(s,p); break; } i++; } return p; } void inorder(TreeNode *p) { if(p != NULL) { inorder(p->left); printf("%c", p->data); inorder(p->right); } } void preorder(TreeNode *p) { if( p != NULL) { printf("%c", p->data); preorder(p->left); preorder(p->right); } } void postorder(TreeNode *p) { if(p != NULL) { postorder(p->left); postorder(p->right); printf("%c", p->data); } } //계산기 int main() { StackType s; s.top = -1; char expr[10]; memset((void*)&s, 0x00, sizeof(s)); memset(expr, 0x00, 10); printf("input expr :"); // scanf("%s", expr); printf("\n"); strcpy(expr, "10+20+30"); TreeNode * p; p = makeET(expr, &s); // inorder(p); // preorder(p); // postorder(p); system("pause"); } /* input expr : PUSH 1 1 PUSH 0 0 POP 1 PUSH + + PUSH 2 2 PUSH 0 0 POP 2 POP + PUSH + + PUSH 3 3 PUSH 0 0 원하시는 답변은 이것을 참고하시면 좋을거 같습니다. http://warmz.tistory.com/619 알고리즘 http://book.naver.com/search/search.nhn?sm=sta_hty.book&sug=pre&where=nexearch&query=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 자료구조 http://book.naver.com/search/search.nhn?sm=sta_hty.book&sug=&where=nexearch&query=%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0 전위 이진트리 http://search.naver.com/search.naver?ie=utf8&sm=stp_hty&where=se&query=%EC%A0%84%EC%9C%84+%EC%9D%B4%EC%A7%84+%ED%8A%B8%EB%A6%AC 제가 구현해본 방식은 이렇습니다 https://docs.google.com/presentation/d/1x6WGw46UrzSHl2Y4EAG0ublviRrv2FO2O4x7GLTpERY/edit?usp=sharing http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=50&MAEULNO=20&no=899407&ref=899407&page=1 http://www.devpia.com/Maeul/Contents/Detail.aspx?BoardID=50&MAEULNo=20&no=899303&ref=899303 http://warmz.tistory.com/619 http://www.devpia.com/Maeul/Contents/Detail.aspx?BoardID=50&MAEULNO=20&no=891247&ref=891247&page=1 전 잘 모르겠네요. ㅡ_ㅡ;; 만약. 계산기를 구현한다고 한다면. 이런식으로 구현할 겁니다. 깊이값은 * / + - 로 4단계 같은 그림 지우기. 게임 같은거다. AAAAAA BBBBBBB ++++++ ******* 먼저 * 곱하기를 찾고. 이전과 다음값을 곱한다. 다음 / 나누기를 찾고. 이전과 다음값을 나눈다. 다음 + 더하기를 찾고. 이전과 다음값을 더한다. 다음 - 빼 기를 찾고. 이전과 다음값을 뺀 다. 입력 10+20*30 우선순위 0 1 2 3 4 * / + - 문자 ------------------ 10 +2 ------------------ 20 *1 30 ------------------ //AAAAAA BBBBBBB CCCCCCC //++++++ /////// ******* 입력 10+20/30+40*50+60 우선순위 0 1 2 3 4 * / + - 문자 ------------------ 10 + ------------------ 20 /2 30 ------------------ + ------------------ 40 *1 50 ------------------ + 60 ------------------ */----------------------------------------------------------------------------
젊음'은 모든것을 가능하게 만든다.
매일 1억명이 사용하는 프로그램을 함께 만들어보고 싶습니다.
정규 근로 시간을 지키는. 야근 없는 회사와 거래합니다.
각 분야별. 좋은 책'이나 사이트' 블로그' 링크 소개 받습니다. shintx@naver.com
댓글 달기