한다 공부

앞에서 본 이진트리는 순회하는 것 말고도 다양한 연산들이 있다. 이번 포스팅에서는 트리의 전체 노드 개수 세기 단말 노드의 개수 구하기 트리의 높이 구하기 를 알아보고자 한다. 앞에서 사용한 이 트리를 이용해보자 트리를 보면 알 수 있듯이 전체 노드는 7개이다. 단말 노드는 3개이다. (22 35 95) 트리의 높이는 4이다. #include #include typedef struct TreeNode { struct TreeNode* left; int data; struct TreeNode* right; }TreeNode; TreeNode n7 = { NULL,22,NULL }; TreeNode n6 = { NULL,95,NULL }; TreeNode n5 = { &n7,35,NULL }; TreeNod..

아까 이진트리를 구현할 때 10 / \ 20 30 위와 같은 트리를 어떻게 순회해야 잘 순회했다고 소문이 날까? 여기엔 크게 3가지 순회가 있다. 전위 순회란 루트를 방문하고 왼쪽 서브트리, 오른쪽 서브트리를 방문하는 순회이다. 위의 트리를 예시로 들면 10 -> 20 -> 30 순으로 순회하는 것이다. 아래 코드에서 preorder이라는 함수를 통해 구현을 할 것이다. 중위 순회란 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 순회이다. 위 트리를 예시로 들면 20 -> 10 -> 30 순으로 순회한다. 아래 코드에서 inorder이라는 함수를 통해 구현을 할 것이다. 후위 순회란 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문하는 순회이다. 위 트리에서 20 -> 30 ->..

앞에서의 스택, 큐, 연결리스트는 선형 자료구조였다. 선형 자료구조란 자료들이 선형으로 나열되어있는 구조이다. 트리는 자료가 계층적인 구조로 이루어져있다. 예를 들면 가족의 가계도, 컴퓨터의 디렉토리 구조 등이 있다. 그래프와 트리의 차이점은, 사이클이 존재하면 그래프이고 사이클이 없고 상하관계가 존재하면 트리이다. -트리의 용어 루트 : 가장 높은 곳에 존재하는 노드 서브트리 : 루트가 아닌 나머지 노드들 간선 : 노드들을 연결하는 연결선 = edge 관계 : 부모, 자식, 형제, 조상, 자손 관계가 존재 (개념은 인간 관계랑 같음!) 단말노드 : 자식이 없는 노드 비단말노드 : 단말노드의 반대 차수 : 한 노드가 가지고 있는 자식 노드의 개수 레벨 : 트리의 각 층에 번호를 매긴 것 (루트는 레벨 1..

연결리스트로 큐와 스택을 구현해보자 [스택] 간단히 말하자면 연결리스트의 맨 앞에 삽입하고 맨 뒤만 삭제하면 된다. insert_first, delete_first !! 단순연결리스트에서도 구현했었다~ #include #include typedef int element; typedef struct StackNode { element data; struct StackNode* link; }StackNode; //top은 정수가 아니고 노드를 가리키는 포인터이다 typedef struct { StackNode* top; }LinkedStackType; void init(LinkedStackType* s) { s->top = NULL; } //insert_first! void push(LinkedStackTy..

[원형연결리스트] 단순연결리스트에 한계가 있음을 깨달았다 ... 원형연결리스트를 이용해 삽입 삭제를 더 편리하게 해보자! 단순연결리스트에서는 마지막 노드가 NULL을 가리켰지만 원형연결리스트에서는 마지막 노드가 첫 번째 노드를 가리킨다. 원형연결리스트를 이용하면 맨 뒤에 노드를 삽입하는 것이 용이해진다! 헤드 포인터가 마지막 노드를 가키리도록 구성하자. 헤드 포인터를 첫 번째 노드를 가키리도록 하면 마지막 노드를 접근하기 위해 모든 노드들을 다 거쳐가야하고, 비효율적으로 동작하기 때문에 헤드 포인터가 마지막 노드를 가리켜야한다 ㅠ ㅠ print_list(list) insert_first(list, data) insert_last(list, data) 를 이용해서 원형연결리스트를 구현해보자 #include..

연결리스트를 복습해보자 연결된 리스트 형태의 자료구조를 연결리스트라고 한다 (단순) 연결리스트는 자기 참조 구조체를 쓸 것이며, lisert 함수를 생성해 연결리스트에 데이터를 추가할 것이며 delete함수를 생성해 연결리스트의 데이터를 삭제할 것이다. print_list함수를 따로 생성해 연결리스트에 있는 데이터를 순서대로 출력하기도 할 것이다. . . 외에 여러 연산이 있지만 추후 필요하면 기술하기로 하겠다 배열과 연결리스트의 장/단점 으로는 무엇이 있을까? 배열은 구현이 간단하고 노드를 찾는 검색 속도가 빠르다. 인덱스를 이용해 해당 위치로 바로 이동할 수 있기 때문이다. 하지만 동적으로 크기를 변경하는게 힘들다. +배열의 경우 중간 데이터를 삭제할 때, 해당 데이터 뒤에 있는 데이터를 앞으로 한칸..

안녕하이소.. 큐 문제를 풀어봤다.. 아니 근데 이거 어제 금방 다 했는데 런타임 에러가 떠가지고 한 3시간 고민하다가 모르겠어서 백준 질문 게시판에 올리고 늦게 잤다. 아침에 일어나니 어떤 정말 고마우신 분께서 에러난 부분 알려주셨는데 int main() 써야하는걸 void main() 써서 에러난 거였다 약간 슬펐다.. 그 분 아니었으면 평생 몰랐을 듯 ㅠㅠ 근데 나 void main 쓰던 사람 아닌데 왜 void main 이라 했지? 봤더니 처음에 return값 관련해서 에러가 나서 이것 저것 만져보다가 (해당 에러는 중간에 수정 완료..) void로 고쳐보기도 하고.. 그랬었던 것 같은데 원래대로인 int로 수정을 안한 것 같다. 그러니까.. 오늘의 교훈 : 평소에 안하던 짓 좀 하지말자 문제를 ..

방가방가 안녕들 하신가요. 오늘은 큐에 대해 복습을 하려고 합니다. 큐란? 선입선출 (FIFO: first in first out) 구조로, 먼저 들어온 데이터가 먼저 나가는 자료구조를 의미한다. 쉽게 말하면 선착순이다. 추상 자료형의로 정의하면.. create(max_size) >> 최대 크기가 max_size인 비어있는 큐 생성 init(q) >> 큐 초기화 is_empty(q) >> 큐의 사이즈가 0이면 return true, 아니면 return false is_full(q) >> 큐의 사이즈가 max_size와 같으면 return true, 아니면 return false enqueue(q,e) >> is_full 검사를 하고 자리가 있다면 q의 끝에 e를 추가 dequeue(q) >> is_emp..

스택 하는김에 하나 더 해봤다. "맞았습니다" 뜨는게 상당히 기쁘다 ^^ 이 맛에 코딩하남 괄호를 검사하기위해 check_vps 라는 함수를 만들었다. 리턴값이 1이면 yes를 (메인에서) 출력하도록 리턴값이 0이면 no를 출력하도록 했다. check_vps에서는 문자열의 길이만큼 반복을 하고 ' ( ' 를 만나면 push ' ) ' 를 만나면 pop, 빈 상태에서 ' ) ' 를 만나면 return 0, 문자열을 다 돌았는데 스택에 뭔가 남아있으면 return 0 정도를 구현했다 #include #include #include typedef char element; typedef struct { element data[50]; int top; }StackType; void init_stack(StackT..

첫번째 공부할 자료구조는 스택! 스택이란? LIFO(Last in First out)으로, 데이터의 삽입과 삭제가 후입선출인 자료구조를 말한다. 가장 나중에 들어온 데이터가 가장 먼저 나가게 되고 가장 먼저 들어온 데이터는 가장 나중에 나가게 된다... 추상 자료형으로 정의하면 . . creat(size) >> 최대 크기가 size만큼인 비어있는 스택 생성 is_full(s) >> 스택의 원소수 == size면 true (stack is full), 아니면 false is_empty(s) >> 스택의 원소수 == 0 이면 true, 아니면 false push(s, item) >> is_full(s) 이 false면 맨 위 (top)에 item 추가 pop(s) >> is_empty(s) 가 flase면 ..