c언어 알고리즘 썸네일형 리스트형 C언어 이진 탐색 트리(Binary Search Trees in C) C언어 이진 탐색 트리(Binary Search Trees in C) - 이진 탐색 트리는 각 노드가 객체인 연결된 데이터 구조로 표현된다. - 각 노드를 기준으로 노드의 키 값보다 작은 값은 좌측, 큰 값은 우측으로 보낸다. - 각 노드는 키 값 외에도 left, right, p의 포인터 변수를 포함한다. - left, right는 자신의 자노드들을, p는 상위 노드를 가르킨다. - root 노드는 유일하게 상위 노드가 없는 노드이다. [ Fig. 1 ] 이진 탐색 트리 1. 동작 원리 (1) root 노드를 가르키는 root 포인터를 선언하고 초기화 한다. (2 - 1) 노드 삽입 명령 시 새로운 노드를 생성하고, 키 값을 입력한다. (2 - 2) 현재 트리를 구성하고 있는 노드들의 키 값과 비교하여.. 더보기 C언어 원형 이중 연결리스트(Circular, doubly linked lists in C) C언어 원형 이중 연결리스트(Circular, doubly linked lists in C) - 이중 연결리스트의 구조에서 가장 처음과 마지막 노드가 서로 연결 되어있는 구조 - 시작 위치를 알기 위해 연결리스트의 맨 앞에 NULL 노드를 추가 [ Fig. 1 ] 원형 이중 연결리스트, site: introduction to algorithm 3/E 1. 동작 원리 (1) NULL 노드를 생성하고 초기화하고 HEAD 포인터가 이를 가르키게 한다. (2-1) 삽입 명령시 새로운 노드를 생성한다. (2-2) NULL 노드의 이전 노드를 새로 생성한 노드로 지정하고, 새로 생성한 노드의 다음 노드를 NULL 노드로 지정한다. (2-3) 연결리스트의 가장 마지막 노드를 찾아서, 이 노드의 다음 노드를 새로 생성.. 더보기 C언어 이중 연결리스트(Doubly linked lists in C) C언어 이중 연결리스트(Doubly linked lists in C) - 연결 리스트의 한 종류이다. - 각 노드가 자신의 다음 노드 및 자신의 이전 노드를 가르킨다. [ Fig. 1 ] Doubly linked list, site : introduction to algorithms 3/E 1. 동작 원리 (1) 연결리스트의 가장 처음을 가르키는 HEAD 포인터를 초기화한다. (2 - 1) 삽입 명령시 연결리스트의 가장 마지막 노드를 찾는다. (2 - 2) 연결된 노드가 없을 경우, HEAD가 새로 생성한 노드를 가르키게 한다. (2 - 2) 연결된 노드가 있을 경우 가장 마지막 노드 다음에 새로 생성한 노드를 연결하고, 새로 생성한 노드가 마지막 노드를 가르키게 한다. (3 - 1) 제거 명령시 제거하.. 더보기 C언어 단일 연결리스트(Singly linked lists in C) C언어 단일 연결리스트(Singly linked lists in C) - 연결리스트는 객체가 선형순서로 정렬되는 자료구조이다. - 배열의 인덱스가 아닌 각 객체의 포인터에 의해 연결리스트의 순서가 결정된다. - 연결리스트는 동적 구조를 위해 간단하고 유연한 표현을 제공한다. - HEAD 포인터가 리스트의 맨 앞을 가르키고, 각 노드가 다음 노드를 가르킨다. [ Fig. 1 ] Singly linked list 1. 동작 원리 (1) 연결리스트의 가장 처음 노드를 가르키는 HEAD 포인터를 초기화한다. (2 - 1) 삽입 명령시 새로운 노드를 생성하고, key 값을 입력한다. (2 - 2) HEAD 포인터가 가르키는 노드가 없을 경우 HEAD 포인터에 노드를 연결한다. (2 - 3) or 연결리스트의 가장.. 더보기 C언어 원형 큐(circular queues in C) C언어 원형 큐(circular queues in C) - 선형 큐의 문제점을 개선하기 위해 고안(= 큐의 포화 상태와 빈(empty) 상태를 구별하지 못함) - 큐의 한 칸을 비워두고 이것을 포화 상태와 빈(empty) 상태를 구분하기 위해 사용한다. [ Fig. 1 ] process of circular queue 위의 그림을 보면 (A)는 시작 부분이라 T(Tail)과 H(Head)가 동일한 위치에 있다. 즉, 이것은 큐가 비어있다는 것을 의미한다. 큐에 데이터를 삽입할 때 H가 가르키는 위치에 데이터를 삽입하게 되면 모든 큐에 데이터를 삽입했을 경우(=포화 상태) T와 H가 같은 곳을 가르키게 된다. 즉 포화 상태인지 큐가 비어있는 상태인지 알 수가 없다. 따라서 H가 가르키는 위치가 아니라 H .. 더보기 C언어 큐(Queues in C) - 연결리스트로 구현(The implementation with the linked lists) C언어 큐(Queues in C) - 연결리스트로 구현(The implementation with the linked lists) - 큐에 대한 내용은 이전 글 참고 1. 동작 원리 (1) 최근 노드를 가르키는 HEAD 포인터와 가장 오래된 노드를 가르키는 TAIL 포인터 초기화 (2 - 1) 삽입 명령 시 새로운 노드를 생성하고, 데이터를 입력한다. (2 - 2) TAIL 포인터가 가르키는 노드가 없을 경우(= 큐가 비어있을 경우) (2 - 2) HEAD와 TAIL이 새로운 노드를 가리킨다. (2 - 3) 가르키는 노드가 있을 경우, HEAD의 위치를 갱신하면서 새로운 노드를 추가한다. (3 - 1) 제거 명령 시 큐가 비어있는지 확인한다. (3 - 2) 큐에 노드가 있을 경우에 TAIL은 그 다음 노.. 더보기 C언어 큐(Queues in C) - 배열로 구현(The implementation with the array) C언어 큐(Queues in C) - 배열로 구현(The implementation with the array) - FIFO(First In First Out) 정책을 사용한다. - 먼저 삽입된 데이터가 먼저 나온다. - 선형 큐의 경우 큐의 포화상태와 빈(empty)상태를 구분하지 못한다. ( 이를 해결하기 위해 환형 큐가 고안 되었다. ) - 삽입 명령을 ENQUEUE라고 부른다. - 삭제 명령을 DEQUEUE라고 부른다. 1. 동작 원리 (1) 삽입할 위치를 가리키는 head와 내보낼 위치를 가르키는 tail의 위치를 초기화 한다. (2) 삽입 명령 시 head가 가르키는 곳에 큐의 위치에 데이터를 입력하고 head의 값을 증가시킨다. (3 - 1) 삭제 명령 시 큐가 비어있는지 확인한다. (3 -.. 더보기 C언어 스택(Stacks in C) - 연결리스트로 구현(The implementation with the linked lists) C언어 스택(Stacks in C) - 연결리스트로 구현(The implementation with the linked lists) - 스택에 관한 내용은 이전 글 참고 1. 동작 원리 (1-1) push 명령 시 새로운 노드를 생성한 후 Top 포인터가 이를 가르키게 한다. ( Top 포인터는 항상 가장 최근 노드(가장 위)를 가르킨다. ) (1-2) 각 노드들은 자신의 이전 노드를 가르킨다. ( pop 명령 시 삭제되는 노드의 이전 노드를 가르키기 위함 ) (2-1) pop 명령 시 Top 포인터가 가르키고 있는 노드의 값을 반환하고, Top 포인터는 이전 노드를 가르킨다. (2-2) 값을 반환한 노드는 삭제한다. ( 메모리를 반환한다. ) 2. 함수 설명 int stack_empty( STACK *.. 더보기 C언어 스택(Stacks in C) - 배열로 구현(The implementation with the array) C언어 스택(Stacks in C) - 배열로 구현(The implementation with the array) - LIFO(Last In First Out) 정책을 수행한다. - 가장 최근에 들어간 데이터가 가장 먼저 나온다. - 삽입 명령을 스택에서는 PUSH 라고 불리운다. - 삭제 명령은 주로 POP이라고 불리운다. 1. 동작원리 (1) 새로운 데이터를 PUSH하면 TOP은 해당 데이터를 가르킨다. (2) 데이터를 POP하면 TOP이 가르키고 있는 데이터를 반환하고, TOP은 이전 데이터를 가르킨다. [ Fig. 1 ] process of the stack, site : introduction to algorithms 3/E 2. 함수 설명 stack_empty( struct stack) : 스.. 더보기 최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘 최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘 프림 알고리즘(Prim's algorithm) - 프림 알고리즘은 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다. - 알고리즘이 동작되는 동안에, 트리에 연결되지 않은 정점들은 큐에 배정되어 있다. - 각 정점들은 key 값을 가지고, 인접한 정점 중 최소 비용으로 이동가능한 정점을 선택한다. 1. 동작 원리 (1) 각 정점들의 key 값과, 다른 정점을 가르키는(pre) 값을 초기화한다. (2) 모든 정점들을 큐에 배정하고, 시작 위치의 key값을 0으로 초기화한다. (3) 큐에 배정된 정점 중, key 값이 가장 작은 정점을 꺼낸다. (4) 꺼내온 정점을 기준으로, 인접한 정점 중에 큐에 아직 배정되어 있고(=트.. 더보기 이전 1 2 다음
