728x90
반응형
드디어 그래프의 기본 코드이다.
이전 포스팅에서 설명했듯이, 그래프를 표현하는 방법 중 인접 리스트 방법을 이용하여 기본적인 그래프를 구현해 볼 것이다. 그 인접 리스트에 해당하는 방법 또한 이미 이전에 포스팅 한 코드를 기반으로 만들 것이다. 해당 리스트 코드는 따로 첨부하도록 할 것이다.
C Data Structure - 그래프란?
드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다. 그래프란? 먼
typingdog.tistory.com
C Data Structure - 연결 리스트
하 코딩해놓고 묵혀뒀다가 포스팅하느라 다시 보고 시간 버리는게 너무 아깝다 앞으로는 정말 열심히 바로바로 정리해서 올려야겠다. 그래도 다시 복습할 기회가 되었으니 의미있는 시간이라
typingdog.tistory.com
먼저, 그래프를 만드는데 있어서 연결 리스트 자료구조를 이용한다. 그래서.. 하 골치 아프게거니 하다가 C++ STL의 리스트를 그냥 활용할까 했는데, 그래도 내가 전에 만든거 테스트도 할 겸, 그걸로 하자! 라고 생각해서 내가 만든 리스트를 100% 신뢰하며 쓰기로 결정했다.
이미 구현된 자료구조는 100% 신뢰하며 쓰는 것이 국룰이다.
그래프 초기화 및 정점 추가
그래프를 초기화 한다는 것은 코드 작성자 나름이고 기능에 따라 더 무언가 있겠지만, 나는 정점을 추가하는 용도로 사용되었다.
간선 추가
이런 식으로 간선이 연결되며 연결된 그래프의 모양은 대충 다음과 같다.
그래프 출력
각 정점 노드 별로 리스트 내에 제공하는 show 관련 함수를 이용하여 출력을 해주면 된다!
출력 결과는 다음과 같다.
리스트 구현할 때, 헤드 부분을 바보 같이 잘못 이해하고 잘못 구현했었다.. 그냥 가리키는 포인터로 두면 될 것을 노드로 처리해버려서.. 아무튼 노란 부분은 무시해도 전혀 문제 없다.
그래프 소멸
그래프가 겁나 어려울 줄 알았는데 생각보다 구현하기 쉬웠다. 다만 탐색에 대한 부분들이 들어가 있지 않기 때문에 모르고 하는 소리일 수 있으나, 진짜 생각했던 것 만큼 어렵지는 않다. 다만 그래프는 이전 자료구조들을 많이 활용하기 때문에 처음부터 구현하기에는 조금 까다로운 것은 사실이다.
다음 포스팅은 탐색에 대해서 하나하나 기록해볼 것이다.
---
코드들이다. 그래프 실행 결과는 이미 위에 있기 때문에 코드만 업로드한다.
그래프 코드
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
#include "NonPublishing/Graph/linkedlistforgraph.h"
struct DefaultGraph
{
int vertex_number; // 정점의 수
int edge_number; // 간선의 수
ListManager* lm; // 간선을 관리하는 매니저들
};
typedef struct DefaultGraph dgraph;
void GraphInit(dgraph* graph, int vertex_number);
void AddEdge(dgraph* graph, int from, int to);
void ShowGraphEdgeInfo(dgraph* graph);
void DestroyGraph(dgraph* graph);
int main(void)
{
dgraph graph;
GraphInit(&graph, 5);
//0 1 2 3 4
AddEdge(&graph, 0, 1);
AddEdge(&graph, 0, 3);
AddEdge(&graph, 1, 2);
AddEdge(&graph, 2, 3);
AddEdge(&graph, 3, 4);
AddEdge(&graph, 4, 0);
ShowGraphEdgeInfo(&graph);
DestroyGraph(&graph);
return 0;
}
void GraphInit(dgraph* graph, int vertex_number)
{
int i = 0;
graph->vertex_number = vertex_number;
graph->edge_number = 0;
graph->lm = (ListManager*)malloc(sizeof(ListManager) * vertex_number);
for (i = 0; i < vertex_number; i++)
ListInit(&(graph->lm[i]));
return;
}
void AddEdge(dgraph* graph, int from, int to)
{
if ((from >= graph->vertex_number) || (to >= graph->vertex_number))
{
printf("초과된 vertex 값이 왔습니다. \n");
return;
}
if (from == to)
{
printf("잘못된 vertex 값이 왔습니다. \n");
return;
}
LInsert(&(graph->lm[from]), to);
LInsert(&(graph->lm[to]), from);
graph->edge_number++;
return;
}
void ShowGraphEdgeInfo(dgraph* graph)
{
int i = 0;
for (i = 0; i < graph->vertex_number; i++)
{
printf("정점[%d] : ", i);
ShowList(&(graph->lm[i]));
}
return;
}
void DestroyGraph(dgraph* graph)
{
int i = 0;
if (graph->lm == NULL)
return;
for (i = 0; i < graph->vertex_number; i++)
DeleteList(&(graph->lm[i])); // 내부 연결된 노드를 모두 제거.
free(graph->lm); // 접점들 자체를 제거.
return;
}
|
cs |
리스트 자료구조 헤더 코드
|
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
#pragma once
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int data;
struct ListNode* link;
};
struct ListManager
{
struct ListNode* head;
struct ListNode* ci; // current index;
struct ListNode* pi; // previous index;
int node_count; // data 값이 유효한 node의 수
int malloc_count; // 할당된 수
};
void ListInit(struct ListManager* lm);
void LInsert(struct ListManager* lm, int data);
int LFirst(struct ListManager* lm, int* data);
int LNext(struct ListManager* lm, int* data);
int LCount(struct ListManager* lm);
int LRemove(struct ListManager* lm);
void* CreateNodeMemory(struct ListManager* lm, int len);
void ShowList(struct ListManager* lm);
void DeleteNode(struct ListManager* lm, struct ListNode* target);
void DeleteList(struct ListManager* lm);
void ListInit(struct ListManager* lm)
{
// count 초기화
lm->node_count = 0;
lm->malloc_count = 0;
// head 다음으로 항상 유지하는 빈 노드 생성
struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
new_node->data = -1;
new_node->link = NULL; // 제일 끝이므로 무조건 NULL을 갖는다.
// 연결리스트 헤드 초기화
lm->head = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
lm->head->data = -1;
lm->head->link = new_node;
// 인덱스 초기화
lm->ci = NULL;
lm->pi = NULL;
return;
}
void LInsert(struct ListManager* lm, int data)
{
struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
// head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
lm->head->link->data = data;
// empty_node 설정
new_node->data = -1;
new_node->link = lm->head->link;
lm->head->link = new_node;
lm->node_count++;
return;
}
int LFirst(struct ListManager* lm, int* data)
{
if (lm->node_count == 0)
{
printf("순회할 노드가 없습니다.\n");
return false;
}
lm->ci = lm->head->link->link;
lm->pi = lm->head->link;
*data = lm->ci->data;
return true;
}
int LNext(struct ListManager* lm, int* data)
{
if (lm->ci->link == NULL)
return false;
lm->pi = lm->ci;
lm->ci = lm->ci->link;
*data = lm->ci->data;
return true;
}
int LCount(struct ListManager* lm)
{
return lm->node_count;
}
int LRemove(struct ListManager* lm)
{
int remove_value = lm->ci->data;
struct ListNode* rtarget = lm->ci;
lm->pi->link = rtarget->link;
lm->ci = lm->pi;
DeleteNode(lm, rtarget);
return remove_value;
}
void* CreateNodeMemory(struct ListManager* lm, int len)
{
lm->malloc_count++;
return (void*)malloc(len);
}
void ShowList(struct ListManager* lm)
{
struct ListNode* index_node = NULL;
if (lm->malloc_count == 0)
{
printf("head와 new node 및 일반 node들까지 모두 존재하지 않습니다.");
return;
}
else if (lm->node_count == 0)
printf("추가된 노드는 모두 제거된 상태이지만, head와 new node가 존재하고 추가 가능한 상태입니다.\n");
for (index_node = lm->head; index_node != NULL; index_node = index_node->link)
{
printf("[%d|%p]", index_node->data, index_node);
if (index_node->link != NULL)
printf("->");
}
fputc('\n', stdout);
return;
}
void DeleteNode(struct ListManager* lm, struct ListNode* target)
{
if (target->data != -1)
lm->node_count--;
free(target);
lm->malloc_count--;
return;
}
void DeleteList(struct ListManager* lm)
{
struct ListNode* index_node = NULL;
struct ListNode* next_node = NULL;
for (index_node = lm->head; index_node != NULL; index_node = next_node)
{
next_node = index_node->link;
DeleteNode(lm, index_node);
}
if (lm->malloc_count != 0)
printf("메모리 해체에 문제가 있습니다\n");
return;
}
|
cs |
728x90
반응형
'프로그래밍응용 > C 자료구조' 카테고리의 다른 글
| C Data Structure - 깊이 우선 탐색(Depth First Search Graph) (0) | 2021.01.29 |
|---|---|
| C Data Structure - 땡땡 우선 탐색(Depth or Breadth First Search Graph) (0) | 2021.01.29 |
| C Data Structure - 그래프란? (0) | 2021.01.28 |
| C Data Structure - 이진 탐색 트리 4 (마지막) (0) | 2021.01.24 |
| C Data Structure - 이진 탐색 트리 3 (0) | 2021.01.24 |
