전체 글 (86) 썸네일형 리스트형 힙(우선순위 큐) 구현 #2 실행소스:github.com/KJT9109/Data_Structure/tree/master/Heap_ProrityQueue 앞서 설계한 구조를 가지고 설계를 해보자 우선 힙 구조체 선언은 다음과 같다. Heap Data Structure 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #define MAXIMUM_SIZE 255 typedef char HData; typedef int HNode; typedef HData (*HPriorityCompare)(HData, HData); typedef struct { int heapNode; HPriorityCompare HPriorityFunc; HData heapData[MAXIMUM_SIZE]; }HeapStruct; Colored.. 힙(우선순위 큐) 구현 #1 힙 구현은 곧 우선순위 큐의 완성으로 이어진다. 일반적으로 큐는 FIFO 이다. 하지만 우선순위 큐의 OUT은 들어간 순서 상관 없이 우선순위에 따라 나온다. 힙(Heap)이란? 1. 힙은 '이진트리' 이되 '완전 이진트리'이다 2. 모든 노드에 저장된 값은 자식 노드에 저장된 값도가 크거나 같아야한다. 3. 같은 노드 사이는 상관 없다. 힙은 최대 힙(Max Heap) 과 최소 힙(Min Heap)이 있는데 루트노드로 올라갈수록 저장된 값이 작아지면 최소 힙, 커지면 최대 힙이라고 한다. 힙에서 데이터 저장 과정 위 그림처럼 힙이 있다고 하자 여기에 9라는 데이터를 저장한다고 하면 일단 완전 이진트리를 만든다. 부모노드와 우선순위를 비교해서 높으면 부모노드와 바꿔 준다. 부모노드가 우선순위 클때까지 9.. 수식트리의 구현 #2 구현 코드 URL:github.com/KJT9109/Data_Structure 앞서 설명했던 부분을 코드로 구현해보자 후기표현법변환은 이전 Stack 공부 할때 설명했으므로 생략 후기표현법에서 수식트리로 변환하는 함수이다. PostfixToTree함수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 void PostfixToTree(BTreeNode *curNode, int *char_arr) { BTreeNode *changeN.. 수식트리의 구현 #1 공부한 이진트리로 수식트린을 구현해보자 앞서 공부했던 계산기에서 후위변환법을 가지고 온 다음 그 식을 가지고 TREE로 구현한다. 책에서는 다시 스택을 활용해서 만드는데 그냥 다 트리에 넣어서 만들어보았다. 트리로 변환 할 식 ->51-8/(3*4-4)-20 우선 위 식을 후위변환표현으로 변경한다. ->51 8 3 4 * 4 - / - 20 - 여기서 포인터는 마지막 연산자인 -를 가리키고 있다. 이제 트리에 다 집어 넣는다 트리에 집어 넣을 때 다음과 같은 규칙을 지키며 집어 넣는다. 1. 연산자가 나오면 왼쪽에 피 연산자가 나오면 오른쪽에 넣는다. 2. 피 연산자노드는 자식 노드를 생성 할 수 없다. 위 규칙을 지키며 트리를 만들면 다음과 같은 트리가 만들어진다. 51 8 3 4 * 4 - / - 2.. 이진트리 구현 열혈 C 자료구조를 통해 공부한 내용을 가지고 계산기를 이진트리를 직접 구현 해보자 CPU 입장에서는 이진트리나 양방향 리스트로 똑같은 거 같다. 노드: node 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 구성요소 간선: edge 노드와 노드를 연결하는 연결선 루트 노드: root node 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드: terminal node 아래로 또 다른 노드가 연결되어 있지 않은 D, E, F 내부 노드: internal node 단말 노드를 제외한 모든 노드로 A, B와 같은 노드 이진트리 구조체 typedef int BTData; typedef struct _bTreeNode { BTData data; struct _bTreeNode *lef.. 리눅스 및 커널 프로그래밍 스터디 정리 #1 테스크 구조체 테스크는 Task_Struct이라는 구조체에서 관리를 한다. Task_Struct은 Page table fd를 포함하고 있다. User Space에서는 System call 함수를 호출하여 Kernel Stack(8KB)에 접근할 수 있으며 kernel Stack의 Current Macro를 통해 Task_struct의 접근하여 우선순위나 fd등에 접근 할 수 있다. Process Context 리눅스에서는 Stack이 3개로 쓰여진다. interrupt Stack: 인터럽트 발생 시 사용하는 Stack 이다. (CPU 에서는 Core 갯수만큼만 있다) Kernel Stack: 시스템 콜 함수를 호출하였을 시 사용하는 Stack이다. (USER Process 만큼만 있다.) USER Sta.. Queue - LinkedList로 구현 Queue를 리스트로 구현해보자 다음과 같이 그림을 그린 후 코드로 구현했다. 초기화 코드 구현 typedef struct __LinkedList { int data; struct __LinkedList *next; }LinkedList; typedef struct __Queue { LinkedList *front; LinkedList *rear; LinkedList *body; } LQueue_Struct; void LQueue_init(LQueue_Struct *lqueue) { lqueue->body = (LinkedList*) malloc(sizeof(LinkedList)); lqueue->body->data = '\0'; lqueue->front = lqueue->body; lqueue->rea.. Queue - 배열 구현 Queue를 배열로 구현 해보자. 이전 RTOS Study에서 Queue를 구현 해 보고 공부 해 본적 있으니 설명은 링크 참고 kjt9109.tistory.com/entry/%EC%9E%84%EB%B2%A0%EB%94%94%EB%93%9C-OS-%EA%B0%9C%EB%B0%9C-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8-15%EB%A9%94%EC%84%B8%EC%A7%95 임베디드 OS 개발 프로젝트 15(메시징) http://www.yes24.com/Product/Goods/84909414. ├── boot │ ├── Entry.S │ ├── Handler.c │ ├── Main.c │ └── main.h ├── hal │ ├── HalInterrupt.h.. kjt9109.t.. 이전 1 2 3 4 5 6 7 ··· 11 다음
