転置行列のメモリを確保できていません

以下のようなコードを用いて標準入力された疎行列の転置行列を出力したいのですが、どうやら
smatrix smatrix_transpose(smatrix S)
という関数の
T = smatrix_new(S->m, S->n);
という箇所でメモリを確保する部分がうまくいってないようです。

ちゃんとmallocで定義はしているので、メモリ確保はちゃんとできているはずなのですが、、、

C
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5#define NEW(p, n){p = malloc((n)*sizeof(p[0]));}
6
7typedef struct slobj_{
8    struct slobj_* next;
9    int j;
10    double v;
11}* slobj;
12
13typedef struct{
14    slobj head;
15    slobj tail;
16}* slist;
17
18typedef struct{
19    int n,m;
20    slist* A;
21}* smatrix;
22
23slist slist_new(void){
24    slist L;
25    NEW(L, 1);
26    L -> head = NULL;
27    L -> tail = NULL;
28    return L;
29}
30
31slobj slobj_new(int x, double y){
32    slobj p;
33    NEW(p, 1);
34    p -> j = x;
35    p -> v = y;
36    p -> next = NULL;
37    return p;
38}
39
40void slist_insert_head(slist L, slobj p){
41    p -> next = L -> head;
42    L -> head = p;
43}
44
45void slist_insert_tail(slist L, slobj p){
46    if(L -> head == NULL){
47        L -> tail = p;
48        L -> head = p;
49    }
50    else if(L -> head == L -> tail){
51        L -> tail = p;
52        L -> head -> next = p;
53    }
54    else{
55        L -> tail -> next = p;
56        L -> tail = p;
57    }
58}
59
60void slist_print(slist L)
61{
62    slobj p;
63    p = L->head;
64    while (p != NULL){
65        printf("%d ", p -> j);
66        printf("%lf ", p -> v);
67        p = p-> next;
68    }
69}
70
71smatrix smatrix_new(int n, int m){
72    smatrix S;
73    int i;
74    NEW(S->A, n);
75    S -> n = n;
76    S -> m = m;
77    for(i=0; i<= n-1; i++){
78        S->A[i]=slist_new();
79    }
80    return S;
81}
82
83smatrix smatrix_read(void){
84    smatrix S;
85    slobj p;
86    int i, n, m, j;
87    double v;
88    scanf("%d", &n);
89    scanf("%d", &m);
90    S = smatrix_new(n, m);
91    for(i = 0; i <= n-1; i++){
92        while(1){
93            scanf("%d", &j);
94            if (j < 0){
95                break;
96            }
97            scanf("%lf", &v);
98            slobj p = slobj_new(j, v);
99            slist_insert_tail(S->A[i], p);
100        }
101    }
102    return S;
103}
104
105void smatrix_print(smatrix S){
106    int i;
107    printf("%d ", S->n);
108    printf("%d\n", S->m);
109    for(i = 0; i <= S->n-1; i++){
110        slist_print(S->A[i]);
111        printf("%d\n", -1);
112    }
113}
114
115smatrix smatrix_transpose(smatrix S){
116    int i, k;
117    double x;
118    slobj p, q;
119    smatrix T;
120    T = smatrix_new(S->m, S->n);
121    for(i = 0; i <= S->n; i++){
122        p = S->A[i]->head;
123        k = p->j;
124        x = p->v;
125        q = slobj_new(i+1, x);
126        slist_insert_tail(T->A[k-1], q);
127        p = p->next;
128    }
129    return T;   
130}
131
132void slist_free(slist L)
133{
134    slobj p, q, r;
135    p = L->head;
136    q = p->next;
137    while (q != NULL){
138        r = q;
139        q = q-> next;
140        free(p);
141        p = r;
142    }
143    free(L);
144}
145
146void smatrix_free(smatrix S){
147    int i;
148    for(i = 0; i <= S->n-1; i++){
149        if(S->A[i]->head != NULL){
150            slist_free(S->A[i]);
151        }
152    }
153}
154
155int main(){
156    smatrix A,B;
157    A = smatrix_read();
158    B = smatrix_transpose(A);
159    smatrix_print(A);
160    smatrix_print(B);
161    smatrix_free(A);
162    smatrix_free(B);
163    return 0;
164}コード

編集:皆様、ありがとうございます。
コードを以下のように編集し、valgrindをランしてみたところ、以下のようなメッセージが出ました。
こちらはどのように解釈されるのでしょうか？

C
1#include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5#define NEW(p, n){p = malloc((n)*sizeof(p[0]));}
6
7typedef struct slobj_{
8    struct slobj_* next;
9    int j;
10    double v;
11}* slobj;
12
13typedef struct{
14    slobj head;
15    slobj tail;
16}* slist;
17
18typedef struct{
19    int n,m;
20    slist* A;
21} smatrix;
22
23slist slist_new(void){
24    slist L;
25    NEW(L, 1);
26    L -> head = NULL;
27    L -> tail = NULL;
28    return L;
29}
30
31slobj slobj_new(int x, double y){
32    slobj p;
33    NEW(p, 1);
34    p -> j = x;
35    p -> v = y;
36    p -> next = NULL;
37    return p;
38}
39
40void slist_insert_head(slist L, slobj p){
41    p -> next = L -> head;
42    L -> head = p;
43}
44
45void slist_insert_tail(slist L, slobj p){
46    if(L -> head == NULL){
47        L -> tail = p;
48        L -> head = p;
49    }
50    else if(L -> head == L -> tail){
51        L -> tail = p;
52        L -> head -> next = p;
53    }
54    else{
55        L -> tail -> next = p;
56        L -> tail = p;
57    }
58}
59
60void slist_print(slist L)
61{
62    slobj p;
63    p = L->head;
64    while (p != NULL){
65        printf("%d ", p -> j);
66        printf("%lf ", p -> v);
67        p = p-> next;
68    }
69}
70
71smatrix smatrix_new(int n, int m){
72    smatrix S;
73    int i;
74    NEW(S.A, n);
75    S.n = n;
76    S.m = m;
77    for(i=0; i<= n-1; i++){
78        S.A[i]=slist_new();
79    }
80    return S;
81}
82
83smatrix smatrix_read(void){
84    smatrix S;
85    slobj p;
86    int i, n, m, j;
87    double v;
88    scanf("%d", &n);
89    scanf("%d", &m);
90    S = smatrix_new(n, m);
91    for(i = 0; i <= n-1; i++){
92        while(1){
93            scanf("%d", &j);
94            if (j < 0){
95                break;
96            }
97            scanf("%lf", &v);
98            slobj p = slobj_new(j, v);
99            slist_insert_tail(S.A[i], p);
100        }
101    }
102    return S;
103}
104
105void smatrix_print(smatrix S){
106    int i;
107    printf("%d ", S.n);
108    printf("%d\n", S.m);
109    for(i = 0; i <= S.n-1; i++){
110        slist_print(S.A[i]);
111        printf("%d\n", -1);
112    }
113}
114
115smatrix smatrix_transpose(smatrix S){
116    int i, k;
117    double x;
118    slobj p, q;
119    smatrix T;
120    for(i = 0; i <= S.n-1; i++){
121        p = S.A[i]->head;
122        while(1){
123           k = p->j;
124           x = p->v;
125           q = slobj_new(i+1, x);
126           slist_insert_tail(T.A[k-1], q);
127           p = p->next;
128           if(p=NULL){
129               break;
130           }
131        }
132    }
133    return T;   
134}
135
136void slist_free(slist L)
137{
138    slobj p, q, r;
139    p = L->head;
140    q = p->next;
141    while (q != NULL){
142        r = q;
143        q = q-> next;
144        free(p);
145        p = r;
146    }
147    free(L);
148}
149
150void smatrix_free(smatrix S){
151    int i;
152    for(i = 0; i <= S.n-1; i++){
153        if(S.A[i]->head != NULL){
154            slist_free(S.A[i]);
155        }
156    }
157}
158
159int main(){
160    smatrix A;
161    smatrix B;
162    A = smatrix_read();
163    smatrix_print(A);
164    B = smatrix_transpose(A);
165    smatrix_print(B);
166    smatrix_free(A);
167    smatrix_free(B);    
168    return 0;
169}

valgrind
1==1188== Memcheck, a memory error detector
2==1188== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
3==1188== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
4==1188== Command: ./a.out
5==1188== 
6==1188== error calling PR_SET_PTRACER, vgdb might block
72 3
81 1.0 -1
92 3.4 -1
102 3
111 1.000000 -1
122 3.400000 -1
13==1188== Use of uninitialised value of size 8
14==1188==    at 0x108BD3: smatrix_transpose (in /home/keigoh/a.out)
15==1188==    by 0x108D26: main (in /home/keigoh/a.out)
16==1188== 
17==1188== Invalid read of size 8
18==1188==    at 0x108BD3: smatrix_transpose (in /home/keigoh/a.out)
19==1188==    by 0x108D26: main (in /home/keigoh/a.out)
20==1188==  Address 0x2b911eb00 is not stack'd, malloc'd or (recently) free'd
21==1188== 
22==1188== 
23==1188== Process terminating with default action of signal 11 (SIGSEGV)
24==1188==  Access not within mapped region at address 0x2B911EB00
25==1188==    at 0x108BD3: smatrix_transpose (in /home/keigoh/a.out)
26==1188==    by 0x108D26: main (in /home/keigoh/a.out)
27==1188==  If you believe this happened as a result of a stack
28==1188==  overflow in your program's main thread (unlikely but
29==1188==  possible), you can try to increase the size of the
30==1188==  main thread stack using the --main-stacksize= flag.
31==1188==  The main thread stack size used in this run was 8388608.
32==1188== 
33==1188== HEAP SUMMARY:
34==1188==     in use at exit: 120 bytes in 6 blocks
35==1188==   total heap usage: 8 allocs, 2 frees, 2,168 bytes allocated
36==1188== 
37==1188== LEAK SUMMARY:
38==1188==    definitely lost: 0 bytes in 0 blocks
39==1188==    indirectly lost: 0 bytes in 0 blocks
40==1188==      possibly lost: 0 bytes in 0 blocks
41==1188==    still reachable: 120 bytes in 6 blocks
42==1188==         suppressed: 0 bytes in 0 blocks
43==1188== Rerun with --leak-check=full to see details of leaked memory
44==1188== 
45==1188== For counts of detected and suppressed errors, rerun with: -v
46==1188== Use --track-origins=yes to see where uninitialised values come from
47==1188== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
48Segmentation fault (core dumped)

takabosoft

2020/04/26 08:27

（本題とはあんまり関係ないですが）行列の一部にリスト構造を使っているようですが、それはそういう作りにしなさいという指示がありますか？私が勉強不足なら良いんですが、行列でリスト構造って見たことがなかったので・・・。

takabosoft

2020/04/26 08:30

あと、好みの問題と言われればそれまでですが、構造体の型宣言を > }* slobj; とするのは、とても読みにくいので、 > } slobj; などとして、使う側で > slobj *p; などとポインタ変数を宣言した方が読みやすいです。

episteme

2020/04/26 11:22 編集

疎行列なら要素をリストで持つのはアリでしょう。てか真面目にROWxCOLUMN個の領域確保したら疎行列の意味がない。ただ、リストだと各要素ごとにポインタを持たなきゃならないんで圧縮効率がよろしくないのは確か。

takabosoft

2020/04/26 23:42

あー、なるほどwikipediaに説明がっつりありました。 https://ja.wikipedia.org/wiki/%E7%96%8E%E8%A1%8C%E5%88%97 失礼しました。

行動規範の内容に同意します

回答2件

自己解決

これでいけました。

C
1smatrix smatrix_transpose(smatrix S){
2    int i, k;
3    double x;
4    slobj p, q;
5    smatrix T;
6    T = smatrix_new(S.m, S.n);
7    for(i = 0; i <= S.n-1; i++){
8        p = S.A[i]->head;
9        while(1){
10           if(p==NULL){
11               break;
12           }
13           k = p->j;
14           x = p->v;
15           q = slobj_new(i+1, x);
16           slist_insert_tail(T.A[k-1], q);
17           p = p->next;
18        }
19    }
20    return T;   
21}