본문 바로가기

개발/자료구조6

[포인터 정리] 2차원 구조체포인터를 함수에 인자로 전달 / 링크드리스트 / 해시테이블 ※ 이 글은 본인이 이해한 것을 저장용으로 정리한 것으로 오류가 있을 수도 있습니다. [포인터 정리] 2차원 구조체포인터를 함수에 인자로 전달 / 링크드리스트 / 해시테이블링크드리스트(linked list)로 해쉬 테이블(Hash Table) 만들기 이러한 링크드리스트(Linked List)를 만든다고 하자 ( 해시테이블(Hash Table)을 만들때 주로 사용되는 형태이다) 예시를 보자(편의를 위해 불필요한 부분은 생략하였다) typedef struct linkedlist* lptr;typedef struct linkedlist{int value;lptr next;}linkedlist; int main(){lptr* hashtable;hashtable = (lptr*)malloc(sizeof(lptr).. 2019. 3. 11.
트리(Tree), 이진트리(Binary Tree) 트리(Tree) 트리는 1개 이상의 노드로 이루어진 유한집합으로서,1) 노드 중에는 루트(root)라는 노드가 하나 있고,2) 나머지 노드들은 n(>=0)개의 분리 집합 T1,T2, ... , Tn으로 분할될 수 있다. 차수(Degree): 한 노드의 서브트리의 수- Leaf/Terminal Node: 차수가 0인 노드- Sibling Node: 같은 부모노드를 가진 노드들- Degree of a tree: 트리에 있는 노드의 최대 차수- Ancestor: 루트에서부터 그 노드까지 경로상의 모든 노드 위의 그림의 예시로 들어보겠다.1) Leaf/Terminal Nodes: K, L, F, G, M, I, J2) Sibling Nodes: (K & L) , (F & G & H), (B & C & D) 등3.. 2017. 12. 11.
[C언어] Stack 구현 코드 #include #include #include typedef struct stack* sptr;typedef struct stack {char data;sptr low;sptr high;}stack; sptr top;int sCnt=0; void push(char n){sptr temp;temp = (sptr)malloc(sizeof(stack));if (sCnt == 0){top->data = n;top->low = NULL;top->high = NULL;sCnt++;}else if (sCnt >= 1){temp->data = n;temp->low = top;temp->high = NULL;top->high = temp;top = temp;sCnt++;}}void pop(){sptr temp;if (.. 2017. 11. 22.
완전 이진트리(Complete Binary Tree) 연결리스트(Linked List)로 만들기 서론 완전 이진트리(Complete Binary Tree)는 규칙적으로 모든 노드가 순차적으로 2개의 지식 노드를 갖는다. 따라서, 배열은 사용할 경우 배열의 모든 칸이 낭비없이 가득 차게 되어 구현하기 편한 배열을 주로 사용한다. 하지만 연결리스트(Linked List)를 사용해서 구현하려면 어떻게 해야할까? 생각보다 복잡하지 않다. 이 글에서는 방법만을 설명하도록 하겠다. 필요지식 - 완전이진트리란? 본론 완전이진트리를 구성함에 있어 가장 걸림돌이 되는 부분은 새로 노드를 삽입해야 할 때, 이를 "어디에" 삽입해야 될 지를 모른다는 것이다. 여러가지 방법이 있지만, 필자가 소개하는 방법은 큐(Queue)를 사용하는 방법이다. 바로 방법을 소개하도록 하겠다. IF (Queue가 비어있을 경우)(1) 첫.. 2017. 11. 17.
완전이진트리(Complete Binary Tree)란? 필요한 사전지식 - 이진트리란? 본론 이진트리의 한 종류인 완전 이진트리는 그림으로 보면 쉽게 이해됩니다. 위의 그림은 완전이진트리(Complete Binary Tree)인 트리들이고, 밑의 그림은 아닌 트리들입니다. 차이가 느껴지시나요? 완전 이진트리들은 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리입니다. 완전이진트리가 아닌 트리들을 보시면 왼쪽이 비어있는데 오른쪽부터 들어가 있죠? 이런 트리들은 완전 이진트리가 아닙니다. 2017. 11. 17.
이진트리(Binary Tree)란? - From 위키백과 From https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC 이진 트리위키백과, 우리 모두의 백과사전.크기가 9이고, 높이가 3인 이진 트리이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽(left)과 오른쪽(right)으로 불린다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰인다.목차 [숨기기] 1정의2종류3특징4이진 트리 탐색5표현 방법정의[편집]방향 간선(directed edge)은 부모에서 자식으로 가는 경로를 가리킨다. (그림의 화살표 부분)루트 노드(root node)는 부모가 없는 노드이다. 트리는 하나의 .. 2017. 11. 17.

티스토리툴바