HW#2 #1과 동일한 방법으로 argc와 argv를 사용함 Input (Inputfile1) 파일과 출력 방법도 #1과 동일함 학번_이름.c로 jano@sejong.edu로 제출할 것 Deadline – 5/7(수)

희소 행렬 (1) 희소 행렬의 연결 리스트 표현 희소 행렬의 각 열과 행을 헤더 노드가 있는 원형 연결 리스트로 표현 각 노드에는 헤더노드와 엔트리 노드를 나타내기 위한 tag 필드가 있음 헤더 노드 down : 열 리스트로 연결하는데 사용 right : 행 리스트로 연결하는데 사용 next : 헤드 노드들을 서로 연결하는데 사용 헤더 노드의 총 수 : max{행의 수, 열의 수} 엔트리 노드 Tag필드 외에 5개의 필드(row, col, down, right, value)가 있음 down: 같은 열에 있는 0이 아닌 다음 항 연결 right : 같은 행에 있는 0이 아닌 다음 항 연결

희소 행렬 (2) 5*4 희소 행렬 a 필요한 노드 수 numTerms개의 0이 아닌 항을 가진 numRows * numCols 희소 행렬이라면 max{numRows, numCols}+numTerms+1개

희소 행렬 a의 연결 표현 (노드의 tag필드는 생략되어 있음)

희소 행렬 (4) 희소 행렬의 표현을 위한 자료 구조 정의 #define MAX_SIZE 50 /* 최대 행렬 크기 */ typedef enum {head,entry} tagfield; typedef struct matrixNode *matrixPointer; typedef struct entryNode { int row; int col; int value; }; typedef struct matrixNode { matrixPointer down; matrixPointer right; tagfield tag; union { matrixPointer next; entryNode entry; } u; matrixPointer hdnode[MAX_SIZE];

희소 행렬 (5) 희소 행렬 입력 입력을 위해 보조 배열 hdnode를 사용 적어도 입력될 행렬의 가장 큰 차원의 크기라고 가정 변수 hdnode[i]는 열 i와 행 i에 대한 헤더 노드를 가리키는 포인터 입력 행렬을 구성하는 동안 임의의 열을 효과적으로 접근할 수 있게 함 matrixPointer mread(void) { /* 행렬을 읽어 연결 표현으로 구성한다. 전역 보조 배열 hdnode가 사용된다. */ int numRows, numCols, numTerms, numHeads, i; int row, col, value, currentRow; matrixPointer temp,last,node; /* 헤더 노드 리스트에 대한 헤더 노드를 생성한다. */ node = newNode(); node->tag = entry; node->u.entry.row = numRows; node->u.entry.col = numCols; if (!numHeads) node->right = node; else { /* 헤더 노드들을 초기화한다. */ for (i = 0; i < numHeads; i++) { temp = newNode; hdnode[i] = temp; hdnode[i]->tag = head; hdnode[i]->right = temp; hdnode[i]->u.next = temp; }

currentRow = 0; last = hdnode[0]; /* 현재 행의 마지막 노드 */ for (i = 0; i < numTerms; i++) { “Input row, col, value”; if (row > currentRow) { /* 현재 행을 종료함 */ last->right = hdnode[currentRow]; currentRow = row; last = hdnode[row]; } temp = newNode(); temp->tag = entry; temp->u.entry.row = row; temp->u.entry.col = col; temp->u.entry.value = value; last->right = temp; /* 행 리스트에 연결 */ last = temp; /* 열 리스트에 연결 */ hdnode[col]->u.next->down = temp; hdnode[col]->u.next = temp; /* 마지막 행을 종료함 */ /* 모든 열 리스트를 종료함 */ for (i = 0; i < numCols; i++) hdnode[i]->u.next->down = hdnode[i]; /* 모든 헤더 노드들을 연결함 */ for (i = 0; i < numHeads-1; i++) hdnode[i]->u.next = hdnode[i+1]; hdnode[numHeads-1]->u.next = node; node->right = hdnode[0]; return node;

희소 행렬 (6) 희소 행렬의 출력 void mwrite(matrixPointer *node) { /* 행렬을 행 우선으로 출력한다. */ int i; matrixPointer temp, head = node->right; /* 행렬의 차원 */ printf("\n numRows = %d, numCols = %d \n", node->u.entry.row, node->u.entry.col); printf(" The matrix by row, column, and value: \n\n"); for (i = 0; i < node->u.entry.row; i++) { /* 각 행에 있는 엔트리들을 출력 */ for (temp = head->right; temp != head; temp = temp->right) printf("%5d%5d%5d \n", temp->u.entry.row, temp->u.entry.col, temp->u.entry.value); head = head->u.next; /* 다음 행 */ }