سلام
من تونستم ترانهاده ماتریس اسپارس رو بنویسم ولی جمع و ضربشو نه!خوشحال می شم اگه کمکم کنید!:46:
Printable View
سلام
من تونستم ترانهاده ماتریس اسپارس رو بنویسم ولی جمع و ضربشو نه!خوشحال می شم اگه کمکم کنید!:46:
الگوریتمش دقیقاً توی کتاب ساختمان داده های هوروویتز هست. اول بگو ساختمان داده شما چه جوری هست؟
مثلاً اگر از یه آرایه n*n استفاده می کنید می توان از همان الگوریتم معمولی ضرب استفاده کرد:
ولی چون از مزتبه n^3 می باشد می توان از الگوریتم دیگری استفاده کرد:کد:1 void mm_mul_sa (sa_t *A, sa_t *B, sa_t *C)
2 {
3 int i, j, k;
4 int sum;
5
6 for (i = 0; i < A->num_rows; i++) {
7 for (j = 0; j < B->num_cols; j++) {
8 sum = 0;
9 for (k = 0; k < A->num_cols; k++) {
10 sum += saGet (A,i,k) * saGet (B,k,j);
11 }
12 saSet (C,i,j,sum);
13 }
14 }
15 }
که از مرتبه R+C است (R تعداد ردیف و C تعداد ستون).کد:1 void mm_mul_sa_fast (sa_t *A, sa_t *B, sa_t *C)
2 {
3 int i, j, sum;
4 sa_cell_t *row_p, *col_p;
5
6 for (i = 0; i < A->num_rows; i++) {
7 for (j = 0; j < B->num_cols; j++) {
8 row_p = A->rows [i];
9 col_p = B->cols [j];
10 sum = 0;
11
12 while ((row_p != NULL) && (col_p != NULL)) {
13 if (row_p->index == col_p->index) {
14 sum += row_p->value * col_p->value;
15 row_p = row_p->next;
16 col_p = col_p->next;
17 }
18 else if (row_p->index < col_p->index)
19 row_p = row_p->next;
20 else
21 col_p = col_p->next;
22 }
23 saSet (C, i, j, sum);
24 }
25 }
26 }
البته این الگوریتم ها برای حالتی است که ما از یک آرایه دو بعدی استفاده کرده ایم.
اگر از ساختمان داده ساده کننده استفاده کرده ایم، می تونی الگوریتمشو تو کتاب هوروویتز ببینی.
من راجع به ساختمان داده ماتریس اسپارس اطلاعات دقیق می خوام . کسی میتونه کمکم کنه؟