자료구조 썸네일형 리스트형 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) : 스.. 더보기 이전 1 다음
