보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)

Presentation on theme: "보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)"— Presentation transcript:

1 보고서 #2(제출기한: 09/23) 다음 문제를 해결하시오. (7)
10장 연습문제 #20에 나타나 있는 그래프 g를 선언문 상에서 초기화 하라. g의 타입 graph_array_type은 (int n, int a[][])의 구조체로 표현된다(n은 g에 속한 노드의 개수, a는 g의 인접 행렬 표현이다) 위에서 초기화된 g를 전달 받아서 인접 리스트로 변환하여 반환하는 함수 graph_list_type*cvt_garray2glist(graph_array_type *g)를 작성하라. graph_list_type은 인접 리스트로 표현된 그래프 타입이며, (int n, graph_node *list[])의 구조체로 표현된다. 여기서 graph_node는 (int vertex, graph_node *link)의 구조체 타입이다. 위에서 인접 리스트로 변환된 그래프를 전달 받아서 출력하는 void print_alist(graph_list_type *)를 작성하라. 위의 과정을 통합하는 main()을 작성하고 실행시켜라. 알고리즘-순천향대컴공의 네이버 카페에 회원으로 신청하고, 수락된 이후에 우선순위큐나 그래프 게시판에 적어도 한번 이상 글을 올려라(3)

2 Solution: 보고서 #2 (1) # define MAX 50 // 그래프의 정점의 최대 개수
typedef struct { // 인접 행렬 그래프 타입 정의 int n; // 정점의 개수 int amat[MAX][MAX]; // 인접 행렬 표현 } graph_array_type ; typedef struct gnode { // 인접리스트에 포함되는 노드 타입 정의 int v; struct gnode *link; } gnode; typedef struct { // 인접 리스트 그래프 타입 정의 int n; gnode *list[MAX]; // 인접 리스트 표현 } graph_list_type; // 함수 원형 선언 graph_list_type*cvt_garray2glist(graph_array_type *); void print_alist(graph_list_type *); int main(void) { graph_list_type *lg; graph_array_type ag = (10, {0,1,0,0,0,0,0,0,0,0}, {1,0,1,1,0,0,0,0,0,0},….} // 선언시 초기화 lg = cvt_garray2glist(&g); // 인접 행렬을 인접 리스트 버전으로 변환 print_alist(lg); // 인접 리스트 그래프를 출력 return 0; }

3 Solution: 보고서 #2 (2) graph_list_type*cvt_garray2glist(graph_array_type *g) { int i, j; graph_list_type *glist; gnode *node; glist = (graph_list_type *)malloc(sizeof(graph_list_type)); // 인접 리스트 생성 // 리스트를 동적 생성하는 것이 중요 // 그렇지 않으면 함수 종료시 사라짐 graph_init(glist); // 그래프 초기화 glist->n = g->n; // 정점의 개수 설정 // 각 정점에 대해서 인접 리스트를 구성한다. for (i = 0; i <g->n; i++) { // 인접 행렬의 각 행에 대해서 for (j=0; j < g->n; j++) { // 각 열에 대해서 if (g->amat[i][j] == 1) { // (i,j)의 간선이 존재하면 node = (node *) malloc(sizeof(node)); // 노드를 생성하고 node->v = j; // 초기화하고 node->link = glist->list[i]; // 정점 i의 리스트 맨 앞에 연결한다. glist->[i] = node; } return glist;

4 Solution: 보고서 #2 (3) void print_alist(graph_list_type *g) { int i;
gnode *ptr; for (i=0; I < g->n; i++ ) { ptr = g->list[i]; // 정점 i 리스트의 첫번째 노드를 가리킨다 printf(“[%d]”, i); // “[i]”를 출력 while (ptr != null) { printf(“ -> %d”, ptr->v); // “->v”를 출력 ptr = ptr->link; // 다음 번째 노드로 이동 }

5 과제 수행시 유의사항 절대 복사하지 말 것 => 진위 여부에 상관 없이 -10점 처리
문제를 정확히 이해할 것 => 잘못 이해시 대폭 감점 조치 보고서를 문제 이해, 분석, 설계, 코딩, 테스트/검증, 의견의 순서로 작성할 것 => 이행하지 않으면 대폭 감점 조치 순서를 반드시 지킬 것: 테스트나 의견이 코딩 앞에 오면 안됨 코드에 주석을 달 것 => 감점 조치 코드는 한 줄에 통째로 출력된 그대로 포함시킬 것 => 두 단으로 나누거나 절단하여 붙이거나 하지 말 것 글자 크기를 작게 하지 말 것 실행 결과를 검증할 것 => 이행하지 않으면 감점 조치 주어진 입력대비 결과를 분석하여 그 정확성을 설명할 것