cinux

1. 개요 [그림 1] 인접리스트로 표현한 그래프 이전에는 인접행렬이 아닌 링크드리스트를 이용하여 인접리스트로 그래프를 표현하는 방법에 대해 알아보겠다. 인접행렬이 최소그래프에 있어서 메모리 낭비가 심했다면, 인접리스트는 정점의 갯수, 간선의 갯수만큼 메모리를 할당하므로 메모리적인 측면에 있어 인접행렬법보다 좋다. 따라서 최소그래프 표현에 적합하다. 그림과 같이 각 정점에서 간선으로 연결된 정점들을 리스트 형태로 연결해 놓는 기법이다. (※ 인접리스트법도 당연히 무방향 그래프에서의 대칭성을 고려하여 코드를 구현하여야 한다) 2. 그래프 구현 1. 구조체 및 함수 선언 typedef struct _node { int vertex; struct _node *next; }Node; typedef struct ..

1. 개요 [그림 1] 인접행렬로 나타낸 그래프 그래프 자료구조를 나타내는 방법으로 두 가지가 있다. 하나는 인접 행렬 (adjacent Matrix) 이고 하나는 인접 리스트 (adjacent List)법이있다. 이번 글에서는 인접행렬로 그래프를 나타내는 방법을 알아보겠다. 인접행렬법은 배열로 그래프를 나타내는 것이므로 밀집그래프 (완전그래프)를 표현하는데 적절하다. 2차원 배열 특성상 한번에 메모리를 잡아햐 하기때문에 빈 공간이 생기면 메모리 낭비가 생기므로 밀집그래프를 표현하는데 있어 좋은 방법이다. (※무방향 그래프를 표현 시 대칭성을 고려해야 한다.) 2. 그래프 구현 1. 구조체 및 함수 선언 extern int check[]; /*----------------------------------..

1. 개요 [그림 1] 트리 (Tree) "트리 (Tree)" 자료구조란 나무를 뒤집은 모습으로 계층구조를 표현하기에 적합한 자료구조이다. 맨 위의 노드가 "루트노드 (Root Node)" 라고 하며 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 "서브 트리 (Sub Tree)"라고 한다. 또한, 임의의 노드의 조상과 자손을 지칭 할 수 있는데, 임의의 노드 바로 위에 있는 노드를 "부모 노드 (Parent Node)" 라고 하고 그 바로 아래 노드들을 "자식 노드 (Children Node)"라 한다. [그림 2] 이진 트리 (Binary Tree) 이런 트리구조에서 파생된 자료구조를 "이진트리 (Binary Tree)"라고 부르는데, 이진트리는 모든 노드들의 자식 노드가 두 개 ..

1. 개요 선형 큐 (Linear Queue) 의 삽입 및 삭제 과정 스택(Stack)자료구조와 달리 선입선출(先入先出, First In First Out; FIFO)의 자료구조로써, 데이터가 나가는 위치, 큐의 첫번째 위치를 Front 라고 하고 데이터가 삽입되는 지점, 큐의 마지막 데이터의 한 칸 다음 위치를 Rear 혹은 Back이라고 한다. 큐에 데이터를 삽입하는 과정을 Enqueue, 빼는 과정을 Dequeue라고 한다. 선입선출 형태이므로 주로 대기열, 줄서기 같은곳에 쓰이는 구조이다. 1. 선형 큐 (Linear Queue) 예를들어 큐 사이즈가 5인 큐가 있다고 하자. 초기에는 Front와 Rear 둘다 0을 가리키고 있는상태이다. 데이터를 하나 삽입하면 Front값을 그대로 Rear값은 ..

1. 개요 후입선출(後入先出, Last In First Out; LIFO) 의 자료구조로, 상자의 형태를 한 자료구조이다. 데이터의 삽입을 Push, 데이터의 출력을 Pop이라고 하며, 스택을 크게 두 가지로 나누면 Ascending Stack VS Descending Stack으로 나눌 수 있다. 스택은 배열과 링크드 리스트로 구현할 수 있는데, 여기서는 링크드리스트를 이용한 스택을 구현해 보겠다. 2. 코드 구현 2-1 ) 구조체 구현 typedef struct _stacknode Snode; struct _stacknode { DataType data; Snode *next; }; typedef struct _stack { Snode *head; Snode *tail; Snode *cur; }Sta..

1. 개요 자료구조의 일종인 링크드리스트는 각 노드당 데이터를 저장하는 데이터필드 영역과 다음 노드를 가리키는 노드 포인터 영역으로 구성된 자료구조이다. 비슷한 방식으로 배열이 있지만 배열은 처음부터 메모리를 할당하고 시작하기 때문에, 링크드리스트에 비해 데이터의 삽입이나 삭제가 어렵다. 반면, 링크드리스트는 노드를 데이터를 삽입할 때마다 메모리를 할당하고 데이터를 이어주는 형식이라 배열에 비해 메모리 낭비가 덜 하다는 장점이 있다. 단일 연결 리스트 (Single LinkedList) 단순 연결 리스트 (Single LinkedList)는 단 방향 연결 리스트로 다음 노드에 대한 참조만을 가지는 가장 단순한 형태의 연결 리스트이다. 단순 연결 리스트는 단 방향이기 때문에 Head 노드의 주소를 잃어버릴..