그냥혀유 그냥혀유

그래프비선형 자료구조 그래프는 정점(V)와  간선(Eege)로 이루어진 자료구조이다. G(V,E)   - 정점(Vertex)는 노드(node)로 표현될 수 있다.  그래프 관련 용어  - 정점의 차수 (Degree)   -> 정점에 연결된 간선의 수  - outDegree / inDegree  -> 정점으로부터 나가는 간선을 outdegree, 정점으로 들어오는 간선을 indegree라고 한다.  - 가중치 그래프(Weighted Graph)    -> 간선에 자중치 혹은 비용이 할당된 그래프         연결된 정점들 간 탐색에 드는 비용이나, 연결 강도를 표현한다.        *가중치 그래프 구현시 객체로 묶어서 표현하면 가독성 좋은 코드를 작성할 수 있다. - 경로 (path)   -> 정점에 ..

1. 버블정렬 // int[] arr를 정렬한다고 가정 for(int i=0; i 0 ){ arr[dataIdx] = arr[getParent(dataIdx)]; dataIdx = getParent(dataIdx); }else break; } arr[dataIdx] = data; num++; } public int delete(){ int Dedata = arr[1]; int lastData = arr[num]; int DataIdx = 1; int child; while(true){ child = getHipriorityChildIdx(DataIdx); if(child == 0 && com.compare(lastData,arr[child]) >= 0) break; arr[DataIdx] = arr[ch..

1. 우선순위 큐란 > 데이터가 삽입된 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다. > 데이터의 우선순위는 우선순위 큐를 구현하면서 임의로 설정하도록 한다. > 우선순위 큐는 배열, 연결리스트, 힙(heap)등을 이용하여 구현할 수 있는데 일반적으로 힙을 이용한다. 2. 힙 > 완전 이진 트리이다. > 부모노드와 자식노드간 대소관계가 있다. > 이진탐색트리와 달리 중복 값을 허용한다. 최대힙 :루트노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 말한다. 최소힙: 루트노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 말한다. 3. 힙의 구현 및 우선순위 큐 완성 - 힙의 데이터 저장: 새로운 데이터는 우선순위가 제일 낮다는 가정하에 마지막 위치에 저장 적절한 위치를 찾을 때 까지 ..

앞 서 만든 이진트리를 만드는 도구를 활용하여 이진트리 구조 중 하나인 수식트리를 만들어보자 1. 수식트리란? 중위,후위,전위 표기법과 같은 여러가지 표기법 중 하나로 메모리에 수식을 표기하는 방식이다. 루트 노드에 연산자를, 두 개의 자식노드에 피연산자를 두어 연산이 진행된다. 이를 그림으로 표기하면 위와 같다. 이러한 수식트리의 장점은 한번 트리를 완성해두면, 중위,후위,전위 표기법으로 쉽게 전환할 수 있다. 2. 구현 중위표기법을 바로 수식트리로 나타내는 것보다 중위표기법을 후위표기법으로 전환한 뒤에 수식트리로 나타내는 것이 간편하므로, 여기서는 후위표기법을 수식트리로 변환하는 과정만 보일 것이다. 수식트리를 표현하기 위한 도구 : 1. Stack, 2 BTree 헤더 #ifndef __EXPRES..

1. 배열? 연결리스트? 이진트리는 배열로 구현할 수도 있고 연결리스트로 구현할 수 도 있다. 이때 트리가 완성 된 후 빈번한 탐색이 이루어지는 등 특정한 필요에 따라 배열로 구현할 수 있지만 (ex heap) 일단 연결리스트로 구현해 보자. 2. 이진 트리의 ADT BTreeNode* MakeBTreeNode(void) - 이진 트리 노드를 생성하여 그 주소 값을 반환 BTdata GetData(BtreeNode*bt) - 노드에 저장된 데이터를 반환 void SetData(BTreeNode*bt, BTdata data) - 노드에 데이터를 저장함 BTreeNode* GetLeftSubTree(BTreeNode* bt) - 왼쪽 서브트리의 주소를 반환 BTreeNode* GetRightSubTree(B..

1. 트리란? 트리는 계층적관계를 표현하는 자료구조이다. 1.2 선형자료구조와의 차이점 (약간) 자료구조는 데이터를 표현하는 방법이다. 저장, 삭제, 조회 등의 기능이 제공되는 것이다. - 선형자료구조는 데이터를 저장하는 것과 표현하는 것을 나누어 생각하기 힘들지만, 비선형은 데이터를 표현하는 관점에서 자료구조의 특징이 잘 들어난다. - 예를들어 위와 같은 연결리스트로 동물의 종의 데이터와 사원의 이름 데이터를 저장한다고 한다면, 정해진 순서에 맞게 데이터를 일정한 방향으로 추가하여 저장할 것이다. 이를 위해 우리는 동물에 맞는 연결리스트 혹은 사원에 맞는 연결리스트를 따로 만들진 않았다. - 이와 다르게 트리를 이용해 종속과목강문계에 따라 동물의 데이터를 나타내려는 것과 사원 데이터를 직급별로 나타내려..

Deque(덱)은 양방향으로 데이터를 꺼내거나, 삽입 할 수 있는 자료구조를 의미한다. 구현 덱의 구현은 양방향연결리스트의 소스를 참고하여 활용하면 비교적 간단하게 만들 수 있다. 헤더 #ifndef _DQUE_H #define _DQUE_H typedef int data; typedef struct _node{ data data; struct _node* next; struct _node* pre; }node; typedef struct _Dque{ node* head; node* tail; int size; }Dque; typedef Dque Deque; void DequeInit(Deque* pq1); int DQisEmpty(Deque* pq1); void DQAddFirst(Deque* pq1,..

큐는 먼저 들어온 데이터가 먼저 나가는 구조로 (FIFO) 스택과 반대되는 개념이라고 볼 수 있다. 큐에서 자료를 넣는 연산은 Enqueue, 자료를 꺼내는 연산을 Dequeue라고 한다. 단순히 스택과 반대되는 개념이므로 쉽게 생각할 수도 있지만, 한가지 생각할 점이 있다. Back 방향 데이터가 삽입되고, Rear가 그 위치를 나타낸다. Front 방향으로 데이터가 꺼내지고, 그 위치를 Front가 가리킨다. 1. 단순 배열 기반 큐 배열은 크기가 미리 정해져 있기 때문에, 이를 기반으로 한 큐를 구현하면, 같은 한계를 지닌다. 다음과 같이 배열의 크기가 6인 상황에서 모든 데이터를 Dequeue한다고 생각해보자. 그렇다면, 이제 Rear가 가리킬 수 있는 것은 배열의 마지막 인덱스 뿐이고, 넣을 수..