chap2 배열과 구조체

int list[5]; *plist[5];

list + i = &list[i] *(list + i) = list[i]

Array Create(j, list) // j 차원의 배열을 반환, list는 j-tuple로서 i번째 원소의 값은 i번째 차원의 크기를 나타냄 Item Retrieve(A, i) Array Store(A, i, x)

int *A = (int *)malloc(sizeof(int) * 100); int *B = (int *)calloc(100, sizeof(int)); A = (int *)realloc(A, sizeof(int) * 200); free(A);

int **C = (int **)malloc(sizeof(int *) * 10); for (int i = 0; i < 10; i++) { C[i] = (int *)malloc(sizeof(int) * 20); }

// 구조체 struct humanBeing { char name[10]; int age; double salary; }; typedef struct humanBeing human_being;

int humans_qual(human_geing person1, human_being person2) { if (strcmp(person1.name, person2.name)) return FALSE; if (person1.age != person2.age) return FALSE; if (person1.salary != person2.salary) return FALSE; return TRUE; } // memcmp(&person1, &person2, sizeof(human_being))

struct list { char data; struct list *link; };

struct human { enum {female, male} gender; union { int children; int beard; } u; } person1, person2; person1.gender = female; person1.u.children = 4; person2.gender = male; person2.u.beard = FALSE;

Polynomial Zero() Boolean IsZero(poly) Coefficient Coef(poly, expon) Exponent Lead_Exp(poly) Polynomial Attach(poly, coef, expon) Polynomial Remove(poly, expon) Polynomial SingleMult(poly, coef, expon) Polynomial Add(poly1, poly2) Polynomial Mult(poly1, poly2)

#define MAX_DEGREE 101 typedef struct { int degree; float coef[MAX_DEGREE]; } polynomial; // 2x^3 + x^2 -1. => [3, (2, 1, 0, -1]

#define MAX_TERMS 100 typedef struct { float coef; int expon; } polynomial; polynomial terms[MAX_TERMS]; int avail = 0;

void padd (int startA, int finishA, int startB, int finishB, int *startD, int *finishD) { float coefficient; *startD = avail; while (startA <= finishA && startB <= finishB) switch (COMPARE(terms[startA].expon, terms[startB].expon)) { case -1: // a.expon < b.expon attach(terms[startB].coef, terms[startB].expon); startB++; break; case 0: coefficient = terms[startA].coef + terms[startB].coef; if (coefficient) attach(coefficient, terms[startA].expon); startA++; startB++; break; case 1: // a.expon > b.expon attach(terms[startA].coef, terms[startA].expon); startA++; } for (; startA <= finishA; startA++) attach(terms[startA].coef, terms[startA].expon); for (; startB <= finishB; startB++) attach(terms[startB].coef, terms[startB].expon); *finishD = avail - 1; }

void attach(float coefficient, int exponent) { // 다항식에 새로운 항을 추가하는 함수 if (avail >= MAX_TERMS) { fprintf(stderr, "Too many terms in the polynomial\n"); exit(1); } terms[avail].coef = coefficient; terms[avail++].expon = exponent; }

typedef struct { int row; int col; int value; } term; term a[MAX_TERMS];

Sparse_Matrix Create(rows, cols) // rows x cols개의 항목을 저장할 수 있는 행렬 반환 Sparse_Matrix Transpose(a) // a[i][j] = v 일때, c[j][i] = v 인 전치 행렬 c를 반환 Sparse_Matrix Add(a, b) // if (a와 b의 dimension이 동일) // c[i][j] = a[i][j] + b[i][j]인 c 반환 // else return error Sparse_Matrix Multiply(a, b) // if (a의 열의 수 == b의 행의 수) // c[i][j] = Sum(a[i][k] x b[k][j])인 c 반환 // else return error

for each row i take element <i, j, value> and store it as element <j, i, value> of the transpose

for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) b[i][j] = a[j][i]; // 시간복잡도 = O(rows * cols)

void transpose(term a[], term b[]) { // a는 입력행렬, b는 출력행렬, b = a^T int count, i, j, currentB; count = a[0].value; // a에서 0이 아닌 원소의 수 b[0].row = a[0].col; // b의 행의 수 = a의 열의 수 b[0].col = a[0].row; // b의 열의 수 = a의 행의 수 b[0].value = count; // 0이 아닌 원소 수는 a와 동일 if (count > 0) { // a가 empty matrix가 아니라면 currentB = 1; // 새로운 원소가 b에 저장될 위치 for (i = 0; i < a[0].col; i++) { // a의 열 순서로 전치 연산 실행 (i: 현재 열) for (j = 1; j <= count; j++) { // a에서 현재 열을 찾자 (a는 행 순서로 저장) if (a[j].col == i) { // 현재 열의 원소 발견, b에 추가 b[currentB].row = a[j].col; b[currentB].col = a[j].row; b[currentB].value = a[j].value; currentB++; // b의 저장될 위치를 1 증가 } }}} } // 시간복잡도 = O(columns * elements) -> O(n^3)

#define MAX_COL 50 void fast_transpose(term a[], term b[]) { // a는 입력행렬, b는 출력행렬, b = a^T int row_terms[MAX_COL]; // a의 열의 원소 수 저장 int starting_pos[MAX_COL]; // 각 열의 시작 위치 저장 int num_col = a[0].col; int num_terms = a[0].value; b[0].row = num_col; b[0].col = a[0].row; b[0].value = num_terms; if (num_terms > 0) { // a에 0이 아닌 원소들이 존재 for (int i = 0; i < num_col; i++) row_terms[i] = 0; // 초기화 for (int i = 1; i <= num_col; i++) row_terms[a[i].col]++; // a의 각 열의 원소 수 계산 // row_terms를 이용하여 시작위치 계산 starting_pos[0] = 1; for (int i = 1; i < num_col; i++) starting_pos[i] = starting_pos[i-1] + row_terms[i-1]; // 시작위치를 이용하여, 특정 원소의 저장위치 파악 for (int i = 1; i <= num_terms; i++) { j = starting_pos[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; // b에서 동일한 행에 대해 열 순서로 저장되는가? } } }

for (i = 1; i <= num_terms; i++) row_terms[a[i].col]++; tmp1 = 1; for (i = 0; i < num_cols; i++) { tmp2 = row_terms[i]; row_terms[i] = tmp1; tmp1 += tmp2; } for (i = 1; i <= num_terms; i++) { j = row_terms[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; }

void mmult(term a[], term b[], term d[]) { // a, b:입력, d:출력, d=a*b int i, j, column, totalD = 0; int totalA = a[0].value; int totalB = b[0].value; int row_begin = 1, row = a[1].row, sum = 0; // row : a의 현재 행 term new_b[MAX_TERMS]; if (a[0].col != b[0].row) { // a의 열의 수와 b의 행의 수는 동일 fprintf(stderr, "Incompatible matricses\n"); exit(1); } else fast_transpose(b, new_b); // 경계 조건을 설정 a[totalA+1].row = a[0].row; new_b[totalB+1].row = b[0].col; for (i = 1; i <= totalA;) { column = new_b[1].row; // b의 현재열 for (j = 1; j <= totalB + 1;) { // a의 현재 행과 b의 현재 열에 대해 곱셈 수행 if (a[i].row != row) { // a의 현재 행을 벗어남 storesum(d, &totalD, row, column, &sum); i = row_begin; // b는 다음 열로, a는 원위치로 for (; new_b[j].row == column; j++); column = new_b[j].row; } else if (new_b[j].row != column( { // b의 현재 열을 벗어남 storesum(d, &totalD, row, column, &sum); i = row_begin; // a는 원위치 column = new_b[j].row // b는 당므 열로 } else switch(COMPARE(a[i].col, new_b[j].col)) { case -1: // a[i].col < new_b[j].col, a증가 i++; break; case 0: // 계산 후, a와 b를 모두 진행 sum += (a[i++].value * new_b[j++].value); break; case 1: // a[i].col > new_b[j].col, b증가 j++; } } for (; a[i].row == row; i++); // b의 모든 원소를 처리한 후 row_begin = i; row = a[i].row; // a의 현재 행을 다음 행으로 } // end of for i <= totalA d[0].row = a[0].row; d[0].col = b[0].col; d[0].value = totalD; }

void storesum(term d[], int *totalD, int column, int *sum) { // sum이 0이 아니면, d배열의 *totalD+1 위치에 row, column 값과 함께 저장 if (*sum) if (*totalD < MAX_TERMS) { d[++*totalD].row = row; d[*totalD].col = column; d[*totalD].value = *sum; *sum = 0; } else { fprintf(stderr, "Numbers of terms in product exceeds %d\n", MAX_TERMS); exit(1); } }

for (int i = 0; i < row_a; i++) { for (int j = 0; j < cols_b; j++) { sum = 0; for (int k = 0; k < cols_a; k++) { sum += a[i][k] * b[k][j]; } d[i][j] = sum; } }