우선순위 큐 : 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐의 구현 방법 1. 배열 기반 2. 연결 리스트 기반 3. 힙(heap) 이용 힙이라는 자료구조를 이용해서 구현하는 것이 일반적 힙 : 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드에 저장된 값이 가장 커야 한다.(값은 말 그대로 값이 될수도 있고 우선순위가 될 수도 있다.) heap : 무엇인가를 차곡차곡 쌓아올린 더미 최대 힙(max healp) : 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리 최소 힙(min heap) : 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리 힙은 우선순위 큐의 구현에 어울리는, 완전 이..
트리(Tree)
트리는 계층적 관계를 표현하는 자료구조이다. 노드(node) : 트리의 구성요소에 해당하는 요소(A, B, C, D) 간선(edge) : 노드와 노드를 연결하는 연결선 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드(terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드(E, F) 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 서브 트리 : 큰 트리에 속하는 작은 트리 이진 트리(Binary Tree) 1. 루트 노드를 중심으로 두 개의 서브트리로 나뉘어야 한다. 2. 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. (노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주..
큐 : 선입선출 배열에서 할 때 dequeue를 하면 f를 뒤로 이동시킨다. => 배열 크기 10인데 앞에꺼가 비어있으면 넣을 수가 없어 => 원형 큐 => F, R의 위치만으로는 꽉 찬 경우와 빈 경우를 구분X => 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주 ex) 원형 큐 CircularQueue.h #ifndef __C_QUEUE_H__ #define __C_QUEUE_H__ #define TRUE1 #define FALSE0 #define QUE_LEN100 typedef int Data; typedef struct _cQueue { int front; int rear; Data queArr[QUE_LEN]; } CQueue; typedef CQueue Que..
스택 : 먼저 들어간 것이 나중에 나온다. 후입선출. LIFO(Last-In, First-Out) ex) 배열기반 스택 ArrayBaseStack.h #ifndef __AB_STACK_H__ #define __AB_STACK_H__ #define TRUE1 #define FALSE0 #define STACK_LEN100 typedef int Data; typedef struct _arrayStack { Data stackArr[STACK_LEN]; int topIndex; } ArrayStack; typedef ArrayStack Stack; void StackInit(Stack * pstack); int SIsEmpty(Stack * pstack); void SPush(Stack * pstack, Da..
앞에 우리가 구현한 연결 리스트의 마지막 노드는 NULL을 가리켰다. 이 마지막 노드가 첫 번째 노드를 가리키게 하면 '원형 연결 리스트'가 된다. 머리에 추가할려면 머리 하나만 필요. 꼬리에 추가할려면 꼬리도 필요. 장점이 반감 원형 연결 리스트의 장점 : 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다. 변형된 원형 연결 리스트 하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 하자. => 꼬리를 가리키는 포인터 변수 : tail 머리를 가리키는 포인터 변수 : tail->next 어렵지 않게 머리와 꼬리에 노드 추가 가능 ex) CLinkedList.h #ifndef __C_LINKED_LIST_H__ #define __C_LINKED_LIST_H__ #define TR..
자료구조를 제대로 공부하려면 다음 세가지 순서를 지켜서 공부 1. 자료구조의 ADT 정의 2. 정의한 ADT의 구현 3. 구현이 완료된 자료구조의 활용 ex) 연결 리스트. 간단 예제(ADT를 정의 X, 삽입, 삭제, 조회의 기능이 함수로 구분 X) #include #include typedef struct _node { int data; struct _node* next; } Node; int main(void) { Node* head = NULL; // NULL 포인터 초기화 Node* tail = NULL; Node* cur = NULL; Node* newNode = NULL; int readData; /**** 데이터를 입력 받는 과정 ****/ while (1) { printf("자연수 입력: ..
추상 자료형(Abstract Data Type) : 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것 리스트 순차 리스트 : 배열을 기반으로 구현된 리스트 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트 리스트 자료구조 1. 리스트 자료구조의 ADT를 정의한다. 2. ADT를 근거로 리스트 자료구조를 활용하는 main 함수를 정의한다. 3. ADT를 근거로 리스트를 구현한다. ex) 순차 리스트 ArrayList.h #ifndef __ARRAY_LIST_H__ #define __ARRAY_LIST_H__ #define TRUE1 #define FALSE0 /*** ArrayList의 정의 ****/ #define LIST_LEN100 typedef int LDa..