C言語
1#include <stdio.h>2#include <stdlib.h>3 4#define NEW(p, n) {p = malloc((n) * sizeof(p[0]));}5 6typedef double * row_vector;7typedef row_vector *matrix;8typedef struct slobj_ {9 struct slobj_ * next;10 int j;11 double v;12} * slobj;13 14typedef struct {15 slobj head;16 slobj tail;17} *slist;18 19typedef struct {20 int n, m;21 slist *A;22} *smatrix;23 24//これを使った場合にはメモリ解放を行わなければいけない。25slist slist_new(void) {26 slist L;27 NEW(L, 1);28 L -> head = NULL;29 L -> tail = NULL;30 return L;31}32 33smatrix smatrix_new(int n, int m) {34 smatrix M;35 NEW(M, 1);36 M -> n = n;37 M -> m = m;38 NEW(M -> A, n);39 for (int i = 0; i < n; i++) {40 M -> A[i] = slist_new();41 }42 return M;43}44 45void smatrix_free(smatrix M) {46 for (int i = 0; i < M -> n; i++) {47 slobj current = M -> A[i] -> head;48 while (current != NULL) {49 slobj next = current -> next;50 free(current);51 current = next;52 }53 free(M -> A[i]);54 }55 free(M -> A);56 free(M);57}58 59void slist_insert_tail(slist L, slobj p) {60 if (L -> tail == NULL) {61 L -> head = p;62 L -> tail = p;63 p -> next = NULL;64 }65 else {66 L -> tail -> next = p;67 L -> tail = p;68 p -> next = NULL;69 }70}71 72smatrix smatrix_read(void) {73 smatrix M;74 int n, m;75 scanf("%d %d", &n, &m);76 M = smatrix_new(n, m);77 int count = 0;78 while (count < n) {79 while (1) {80 double input;81 int j;82 if (scanf("%d", &j) == 1) {83 if (j == -1) {84 count = count + 1;85 break;86 }87 if (scanf("%lf", &input) == 1) {88 slobj obj;89 NEW(obj, 1);90 obj -> j = j;91 obj -> v = input; 92 slist_insert_tail(M -> A[count], obj);93 94 }95 }96 }97 }98 return M;99}100 101void print_smatrix(smatrix M) {102 int n, m;103 n = M -> n;104 m = M -> m;105 printf("%d ", n);106 printf("%d\n", m);107 for (int idx = 0; idx < n; idx++) {108 slist X;109 slobj p;110 X = M -> A[idx];111 p = X -> head;112 while (p != NULL) {113 printf("%d %lf ", p-> j, p->v);114 p = p -> next;115 }116 printf("-1\n");117 }118}119 120smatrix transpose(smatrix M) {121 int n, m;122 n = M -> n;123 m = M -> m;124 smatrix N;125 NEW(N, 1);126 N -> n = m;127 N -> m = n;128 NEW(N -> A, m);129 for (int i = 0; i < m; i++) {130 NEW(N -> A[i], 1);131 N -> A[i] -> head = NULL;132 N -> A[i] -> tail = NULL;133 }134 for (int idx = 0; idx < n; idx++) {135 slist X;136 slobj p;137 X = M -> A[idx];138 p = X -> head;139 while (p != NULL) {140 int j;141 j = p -> j;142 slobj obj; //こいつもメモリ解放必須143 NEW(obj, 1);144 obj -> j = idx + 1;145 obj -> v = p -> v;146 obj -> next = NULL;147 if (N -> A[j - 1] == NULL) {148 NEW(N -> A[j - 1], 1);149 N -> A[j -1] -> head = NULL;150 N -> A[j -1] -> tail = NULL;151 }152 slist_insert_tail(N -> A[j - 1], obj);153 p = p -> next;154 }155 }156 smatrix_free(M);157 return N;158}159 160smatrix smatrix_copy(smatrix M) {161 int n = M->n;162 int m = M->m;163 164 // Create a new matrix N with the same dimensions165 smatrix N = smatrix_new(n, m);166 167 // Copy each element from M to N168 for (int i = 0; i < n; i++) {169 slist A = M->A[i];170 slobj p = A->head;171 172 while (p != NULL) {173 // Create a new object and copy the values174 slobj obj;175 NEW(obj, 1);176 obj->j = p->j;177 obj->v = p->v;178 obj->next = NULL;179 180 // Insert the new object into the copied matrix181 slist_insert_tail(N->A[i], obj);182 183 p = p->next;184 }185 }186 return N;187}188 189double shared_col_slist(slist L_1, slist L_2){190 slobj p_1 = L_1 -> head;191 slobj p_2 = L_2 -> head;192 double sum = 0.0;193 while((p_1 != NULL) && (p_2 != NULL)){194 int j_1 = p_1 -> j;195 int j_2 = p_2 -> j;196 if (j_1 == j_2) {197 double v_1 = p_1 -> v;198 double v_2 = p_2 -> v;199 sum = sum + v_1 * v_2;200 p_1 = p_1 -> next;201 p_2 = p_2 -> next;202 }203 if (j_1 < j_2) {204 p_1 = p_1 -> next;205 }206 if (j_1 > j_2) {207 p_2 = p_2 -> next;208 }209 }210 return sum;211}212 213smatrix smatrix_product(smatrix X, smatrix Y) {214 int m_x = X -> m;215 int n_x = X -> n;216 int m_y = Y -> m;217 int n_y = Y -> n;218 smatrix Y_T = transpose(Y);219 smatrix Z = smatrix_new(n_x, m_y);220 for (int idx = 0; idx < n_x; idx++){221 Z -> A[idx] = slist_new();222 for (int col = 0; col < m_y; col++){223 slist a_v = X -> A[idx];224 slist b_T_v = Y_T -> A[col];225 double sum = shared_col_slist(a_v, b_T_v);226 slobj obj;227 NEW(obj, 1);228 obj -> j = col;229 obj -> v = sum;230 slist_insert_tail(Z -> A[idx], obj);231 }232 }233 smatrix_free(Y_T);234 return Z;235}236 237 238int main() {239 smatrix M, N, L, X;240 M = smatrix_read();241 N = smatrix_product(M, M);242 print_smatrix(N);243 smatrix_free(X);244 return 0;245}
0 コメント