선입선출(先入先出, First In First Out; FIFO)의 자료구조로써, 데이터가 나가는 위치, 큐의 첫번째 위치를 Front 라고 하고 데이터가 삽입되는 지점, 큐의 마지막 데이터의 한 칸 다음 위치를 Rear 혹은 Back이라고 한다 큐에 데이터를 삽입하는 과정을 Enqueue, 빼는 과정을 Dequeue라고 한다. 선입선출 형태이므로 주로 대기열, 줄서기 같은곳에 쓰이는 구조이다. 선형 큐 (Linear Queue) 예를들어 사이즈가 5인 큐가 있다고 하자. 초기에는 Front와 Rear 둘다 0을 가리키고 있는상태이다. 데이터를 하나 삽입하면 Front값을 그대로 Rear값은 하나 증가한다 (1번방 가리키고있는상태) 그 다음 방금 넣었던 데이터를 삭제하면 Front값이 하나 증가하여 1번방을 가리키고, 이 상태는 큐가 비었다는것을 뜻 한다....
“트리 (Tree)” 자료구조란 나무를 뒤집은 모습으로 계층구조를 표현하기에 적합한 자료구조이다. 맨 위의 노드가 “루트노드 (Root Node)” 라고 하며 이 노드 아래에 있는 노드들은 다시 트리 구조가 된다. 이런 구조를 “서브 트리 (Sub Tree)“라고 한다. 또한, 임의의 노드의 조상과 자손을 지칭 할 수 있는데, 임의의 노드 바로 위에 있는 노드를 “부모 노드 (Parent Node)” 라고 하고 그 바로 아래 노드들을 “자식 노드 (Children Node)“라 한다. 이런 트리구조에서 파생된 자료구조를 이진트리 (Binary Tree) 라고 부르는데, 이진트리는 모든 노드들의 자식 노드가 두 개 이하인 트리를 의미한다....
Graph 그래프 자료구조를 나타내는 방법으로 두 가지가 있다. 하나는 인접 행렬 (adjacent Matrix) 이고 하나는 인접 리스트 (adjacent List)법이있다. 이번 글에서는 인접행렬로 그래프를 나타내는 방법을 알아보겠다. 인접행렬법은 배열로 그래프를 나타내는 것이므로 밀집그래프 (완전그래프)를 표현하는데 적절하다. 2차원 배열 특성상 한번에 메모리를 잡아햐 하기때문에 빈 공간이 생기면 메모리 낭비가 생기므로 밀집그래프를 표현하는데 있어 좋은 방법이다. (※무방향 그래프를 표현 시 대칭성을 고려해야 한다.) Implementaion Define extern int check[]; /*---------------------------------------------- GraphMatrix 처리 구조체 및 활용 함수 -----------------------------------------------*/ typedef struct { int graph[MAX_VERTEX][MAX_VERTEX]; /* 인접 행렬법 표기 배열 - 2차원 배열 */ int vertexCnt; /* 정점 개수 */ int edgeCnt; /* 간선 개수 */ }GraphMatrix; void initGraph(GraphMatrix *gm, char *fileName); /*데이터파일에서 그래프의 정점과 간선 정보를 입력 받아 그래프를 초기화하는 함수 */ void outputGraph(GraphMatrix *gm); /* 그래프내의 정점과 간선의 관계를 인접 행렬 형태로 출력 함 */ void DFS_Matrix(GraphMatrix *gm); /* 여러 개의 연결 요소로 구성된 그래프를 깊이 우선 탐색하기 위한 함수(재귀판) - DFS_recursive()함수를 호출하여 처리(이 함수 자체는 재귀하지 않음) */ void DFS_recursive(GraphMatrix *gm, int vNum); /* 연결되어있는 하나의 그래트내의 모든 정점을 재귀호출기법으로 방문하는 함수 */ void visit(int vNum); /* 방문한 정점의 처리 */ void nrDFS_Matrix(GraphMatrix *gm); /* 여러 개의 연결 요소로 구성된 그래프를 깊이 우선 탐색하기 위한 함수(비 재귀판) */ void BFS_Matrix(GraphMatrix *gm); /* 여러 개의 연결 요소로 구성된 그래프를 너비 우선 탐색하기 위한 함수(비 재귀판) */ int countGraphComponents(GraphMatrix *gm); /* 인접 행렬법으로 표기되 그래프 내의 연결 요소별로 정점들을 출력하고 연결 요소의 개수를 리턴하는 함수 */ extern 전역 변수로 방문처리를 확인 할 1차원 배열을 하나 선언해준다....
자료구조의 일종인 링크드리스트는 각 노드당 데이터를 저장하는 데이터필드 영역과 다음 노드를 가리키는 노드 포인터 영역으로 구성된 자료구조이다. 비슷한 방식으로 배열이 있지만 배열은 처음부터 메모리를 할당하고 시작하기 때문에, 링크드리스트에 비해 데이터의 삽입이나 삭제가 어렵다. 반면, 링크드리스트는 노드를 데이터를 삽입할 때마다 메모리를 할당하고 데이터를 이어주는 형식이라 배열에 비해 메모리 낭비가 덜 하다는 장점이 있다. Implementation structure typedef struct _node Node; // 구조체 노드 형명재지정 struct _node{ // 데이터를 보관할 노드(자기참조 구조체) Node *prev; // 앞 노드를 가리키는 멤버 DataType data; // 데이터 저장 멤버 Node *next; // 뒷 노드를 가리키는 멤버 }; typedef struct _linkedList{ // 리스트 관리 구조체 Node *head; // 헤드포인터 (헤드노드 가리킴) Node *cur; // 특정 작업 시 노드를 가리키기 위한 포인터 Node *tail; // 테일포인터 (테일노드 가리킴) int length; // 실제 데이터노드의 갯수 }LinkedList; LinkedList 구조체는 리스트 관리 구조체로서,...
후입선출(Last In First Out; LIFO)의 특성을 갖는 자료구조로, 데이터를 쌓아올리는(stack)의 형태를 갖는다. push: 데이터를 넣는 작업 pop: 데이터를 꺼내는 작업 Implementation 스택은 배열(array)와 연결리스트(linked list)로 구현할 수 있는데, 여기서는 연결리스트를 이용해서 스택을 구현할 것이다. structure typedef struct node { void* data; struct node *next; } node; typedef struct stack { int size; node *head; } stack; 동적으로 할당할 data와 다음 노드를 가리킬 next 포인터로 하나의 element 형태를 갖는다. initialize stack init_stack() { stack st; st....