blackbearwow

분리 집합이란 서로 공통된 원소를 갖지 않는 집합들을 말한다. 서로 구분되어야 하는 데이터 집합을 다룰 때 유용하다. // gcc -o Test_DisjointSet.exe Test_DisjointSet.c DisjointSet.c; ./Test_DisjointSet.exe #include #include typedef struct tagDisjointSet { struct tagDisjointSet* Parent; void* Data; } DisjointSet; void DS_UnionSet( DisjointSet* Set1, DisjointSet* Set2 ) { Set2 = DS_FindSet(Set2); Set2->Parent = Set1; } DisjointSet* DS_FindSet( Disj..

수식 트리를 구축하는 방법 1. 중위 표기식을 후위 표기식으로 변환한다. 중위 표기식을 후위 표기식으로 변환하는것은 생략한다. https://owwowo.tistory.com/127?category=1084279 2. 후위 표기식 기반 수식 트리 구축 알고리즘을 이용하여 구축한다. ①수식을 뒤에서부터 앞쪽으로 읽어나간다. ②수식에서 제일 마지막에 있는 토큰은 루트 노드가 된다. 후위 표기식에서 가장 마지막에 있는 토큰은 항상 연산자이다. ③수식에서 읽어낸 토큰이 연산자인 경우에는 가지 노드가 되며, 이 토큰 다음에 따라오는 두개의 토큰은 각각 오른쪽 자식 노드와 왼쪽 자식 노드가 된다. 단, 다음 토큰에도 연속해서 연산자인 경우에는 이 토큰으로부터 만들어지는 하위 트리가 완성된 이후에 읽어낸 토큰이 왼쪽..

이진 트리는 노드의 최대 차수가 2인 트리이다. Binary Tree는 데이터를 담는 용도로로는 사용하기 곤란하지만, 이런 구조를 이용한 훌륭한 알고리즘들이 개발되어 있다. 수식 이진 트리(Expression Binary Tree)와 이진 탐색 트리(Binary Search Tree)가 대표적인 알고리즘이다. 포화 이진 트리(Full Binary Tree) : 잎 노드를 제외한 모든 노드가 자식을 둘씩 가진 이진 트리 완전 이진 트리(Complete Binary Tree) : 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리 높이 균형 트리(Height Balanced Tree) : 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진 트리 완전 높이 균형 트리(C..

노드의 깊이(Depth) : 루트 노드에서 해당 노드까지의 경로의 길이 레벨(Level) : 깊이가 같은 노드의 집합 트리의 높이(Height) : '가장 깊은 곳'에 있는 잎 노드까지의 깊이 노드의 차수(Degree) : 그 노드의 자식 노드 개수 트리의 차수(Degree) : 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수 노드 노드의 깊이(Depth) 노드의 차수(Degree) A 0 3 B 1 2 C 2 0 D 2 1 E 3 0 F 3 0 G 1 1 H 2 0 I 1 1 J 2 1 K 3 0 레벨 0 : {A} 레벨 1 : {B, G, I} 레벨 2 : {C, D, H, J} 레벨 3 : {E, F, K} 트리의 높이 : 3 트리의 차수 : 3 노드 표현법은 N-Link 표현법과..

Linked Queue는 Singly Linked List와 구조가 똑같다. 주요 연산: Enqueue(삽입) Dequeue(삭제) enqueue는 rear 뒤에, dequeue는 front를 반환해주면 된다. // gcc -o Test_LinkedQueue.exe Test_LinkedQueue.c LinkedQueue.c; ./Test_LinkedQueue.exe typedef struct tagNode { char* Data; struct tagNode* NextNode; } Node; typedef struct tagLinkedQueue { Node* Front; Node* Rear; int Count; } LinkedQueue; void LQ_CreateQueue( LinkedQueue** Que..

Queue는 FIFO(first in first out)방식이다. 주요 연산: Enqueue(삽입) Dequeue(삭제) circular queue는 capacity보다 1 더 많은 공간을 할당해 front == rear면 빈공간이고 rear+1 mod capacity == front면 큐가 꽉 찬것으로 본다. // gcc -o Test_CircularQueue.exe Test_CircularQueue.c CircularQueue.c; ./Test_CircularQueue.exe #include #include typedef int ElementType; typedef struct tagNode { ElementType Data; } Node; typedef struct tagCircularQueue {..

스택을 사용하여 [0-9+-*/()] 로 구성된 사칙연산을 계산할 수 있다. 스택에서 사칙연산하기 위해 사용하는 표기법은 후위 표기법(Postfix Notation)이다. 우리가 보통 사용하는 수식은 중위 표기법(Infix Notation)인데, 이것을 계산하려면 다음 두 단계를 거쳐야 한다. 1. 중위 표기법을 후위 표기법으로 변환 2. 후위 표기법을 계산 1. 중위 표기법을 후위 표기법으로 변환 (다익스트라의 중위-후위 표기 변환 알고리즘) ①입력받은 중위 표기식에서 토큰을 읽는다. ②토큰이 피연산자이면 토큰을 결과에 출력한다. ③토큰이 연산자(괄호 포함)인 경우, 스택의 최상위 노드에 담겨있는 연산자가 토큰보다 우선 순위가 높은지를 검사한다. 검사 결과가 참이면 최상위 노드를 스택에서 꺼내 결과에 ..

배열로 스택을 구현하는 방법도 있지만, 링크드 리스트로 스택을 구현하면 용량의 제한 없이 스택을 구현할 수 있다. 주요 연산: PUSH(삽입) POP(삭제) // gcc -o Test_LinkedListStack.exe Test_LinkedListStack.c LinkedListStack.c; ./Test_LinkedListStack.exe #include #include #include typedef struct tagNode { char* Data; struct tagNode* NextNode; } Node; typedef struct tagLinkedListStack { Node* List; Node* Top; } LinkedListStack; void LLS_CreateStack( LinkedLi..

stack은 LIFO(last in first out)이다. 프로그램 실행에서 지역변수, 대부분의 네트워크 프로토콜도 스택으로 이루어져 있다. 주요 연산: PUSH(삽입) POP(삭제) // gcc -o Test_ArrayStack.exe Test_ArrayStack.c ArrayStack.c; ./Test_ArrayStack.exe #include #include typedef int ElementType; typedef struct tagNode { ElementType Data; } Node; typedef struct tagArrayStack { int Capacity; int Top; Node* Nodes; } ArrayStack; void AS_CreateStack(ArrayStack** St..

Circular Linked List는 양쪽 방향으로 엮어 있고, head와 tail또한 엮여 있는 Linked List이다. 주요 연산: -노드 생성/소멸 -노드 추가 -노드 탐색 -노드 삭제 -노드 삽입 // gcc -o Test_CircularDoublyLinkedList.exe Test_CircularDoublyLinkedList.c CircularDoublyLinkedList.c; ./Test_CircularDoublyLinkedList.exe #include #include typedef int ElementType; typedef struct tagNode { ElementType Data; struct tagNode* PrevNode; struct tagNode* NextNode; } No..

Doubly Linked List는 양쪽 방향으로 엮어 있는 Linked List이다. 주요 연산: -노드 생성/소멸 -노드 추가 -노드 탐색 -노드 삭제 -노드 삽입 // gcc -o Test_DoublyLinkedList.exe Test_DoublyLinkedList.c DoublyLinkedList.c; ./Test_DoublyLinkedList.exe #include #include typedef int ElementType; typedef struct tagNode { ElementType Data; struct tagNode* PrevNode; struct tagNode* NextNode; } Node; /* 노드 생성 */ Node* DLL_CreateNode( ElementType NewD..

Singly Linked List는 한쪽 방향으로만 엮어 있는 Linked List이다. 주요 연산: -노드 생성/소멸 -노드 추가 -노드 탐색 -노드 삭제 -노드 삽입 장점: 새로운 노드의 추가/삽입/삭제가 쉽고 빠르다. 배열은 요소를 삽입하거나 제거하기가 어렵다. 단점: 포인터 때문에 노드마다 추가의 메모리가 필요하다. 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도도 느리다. 노드 포인터는 head와 tail이 있고, 노드 구성은 data와 pointer로 되어있다. // g++ -o singlyLinkedList.exe singlyLinkedList.cpp; ./singlyLinkedList.exe #include typedef int ElementType; typedef struct ta..