編集履歴

回答編集履歴

ソートを止め, put/get で検索

2020/04/27 09:33

投稿

スコア13209

test CHANGED Viewed

@@ -12,12 +12,10 @@
 #修正
-リストを使うようにし, 2次元で動作するようにしました.
+リストを使うように戻し, 2次元的に動作するようにしました.
 データが無い所を 0 表示するようにしました.
-ソート部分がテキトウかもしれません.
 ```c
 #include <stdio.h>
@@ -76,7 +74,7 @@
-//リスト初期化
+//初期化
 void slist_init(SLIST *slist) {
@@ -88,14 +86,26 @@
-//リストに追加
+//書き換えor追加
-void slist_append(SLIST *slist, int x, int y, double v) {
+void slist_put(SLIST *slist, int x, int y, double v) {
   SLOBJ *p;
+  for(p=slist->next; p!=NULL; p=p->next) {
+    if(p->x == x && p->y == y) {
+      p->v = v;
+      return;
+    }
+  }
   p = slobj_new(x, y, v);
   slist->last->next = p;
@@ -106,234 +116,160 @@
-//リストをカウント
+//取り出し
-int slist_count(SLIST *slist) {
+double slist_get(SLIST *slist, int x, int y) {
-  int count;
   SLOBJ *p;
-  count = 0;
-  for(p=slist->next; p!=NULL; p=p->next) count++;
+  for(p=slist->next; p!=NULL; p=p->next) {
-  return count;
+    if(p->x == x && p->y == y) return p->v;
-}
+  }
+  return 0.0;
+}
-//リストをソート
+//解放
-void slist_sort(SLIST *slist) {
+void slist_clear(SLIST *slist) {
-  SLOBJ *o, *p, *q, *t;
+  SLOBJ *p, *q;
-  int count, changed;
-  count = slist_count(slist);
+  for(p=slist->next; p!=NULL; p=q) {
-  if(count <= 1) return;
-  t = NULL;
-  do { //バブル
-    changed = 0; //フラグクリア
-    o = (SLOBJ *)slist;
-    p = o->next;
     q = p->next;
-    while(q != t) {
+    free(p);
-      if(p->y > q->y || (p->y == q->y && p->x > q->x)) { //p>q
-        p->next = q->next; q->next = p; o->next = q; //入れ替え
-        changed = 1; //フラグセット
-      }
+  }
+  slist_init(slist);
+}
+//疎行列の構造体
+typedef struct {
+  int n, m;
+  SLIST a;
+} SMATRIX;
+//新しい疎行列を作成
+SMATRIX *smatrix_new(int n, int m) {
+  SMATRIX *s;
+  s = (SMATRIX *)malloc(sizeof(SMATRIX));
+  s->n = n;
+  s->m = m;
+  slist_init(&s->a);
+  return s;
+}
+//標準出力から行列を読み込み、別のメモリに記憶しておく
+SMATRIX *smatrix_read() {
+  int i, n, m, x, y, k=0;
+  double v;
+  SMATRIX *s;
+  int test[] = { 2,3,  1,1,1, /*2,1,2*/ 1,2,4,  2,2,5, 3,2,6, 3,1,3, }; //テストデータ
+  n = test[k++]; //scanf("%d",&n);
+  m = test[k++]; //scanf("%d",&m);
+  s = smatrix_new(n, m);
+  for (i=0; i<(sizeof(test)/sizeof(int)-2)/3; i++) {
+    x = test[k++]; //scanf("%d",&s->a[i].j);
+    y = test[k++];
+    v = test[k++]; //scanf("%lf",&s->a[i].v);
+    slist_put(&s->a, x, y, v);
+  }
+  return s;
+}
+//疎行列の転置を作成・出力
+SMATRIX *smatrix_transpose(SMATRIX *s) {
+  SLOBJ *p;
+  SMATRIX *t;
+  t = smatrix_new(s->m, s->n);
+  for(p=s->a.next; p!=NULL; p=p->next) {
-      o = o->next; p = o->next; q = p->next; //次
+    slist_put(&t->a, p->y, p->x, p->v); //行列変換
+  }
+  return t;
+}
+//疎行列をプリント
+void smatrix_print(char *label, SMATRIX *s) {
-      if(q == NULL) slist->last = p;
+  if(label != NULL) printf("%s\n", label);
+  printf("%d %d\n", s->n, s->m);
+  for(int y=1; y<=s->n; y++) {
+    for(int x=1; x<=s->m; x++) {
+      printf("(%d,%d)=%lf%s", x, y, slist_get(&s->a,x,y), x==s->m?"\n":" ");
     }
-    t = p;
-  } while(changed);
-}
-//リストを解放
-void slist_clear(SLIST *slist) {
-  SLOBJ *p, *q;
-  for(p=slist->next; p!=NULL; p=q) {
-    q = p->next;
-    free(p);
-  }
-  slist_init(slist);
-}
-//疎行列の構造体
-typedef struct {
-  int n, m;
-  SLIST a;
-} SMATRIX;
-//新しい疎行列を作成
-SMATRIX *smatrix_new(int n, int m) {
-  SMATRIX *s;
-  s = (SMATRIX *)malloc(sizeof(SMATRIX));
-  s->n = n;
-  s->m = m;
-  slist_init(&s->a);
-  return s;
-}
-//標準出力から行列を読み込み、別のメモリに記憶しておく
-SMATRIX *smatrix_read() {
-  int i, n, m, x, y, k=0;
-  double v;
-  SMATRIX *s;
-  int test[] = { 2,3,  1,1,1, /*2,1,2*/ 1,2,4,  2,2,5, 3,2,6, 3,1,3, }; //テストデータ
-  n = test[k++]; //scanf("%d",&n);
-  m = test[k++]; //scanf("%d",&m);
-  s = smatrix_new(n, m);
-  for (i=0; i<(sizeof(test)/sizeof(int)-2)/3; i++) {
-    x = test[k++]; //scanf("%d",&s->a[i].j);
-    y = test[k++];
-    v = test[k++]; //scanf("%lf",&s->a[i].v);
-    slist_append(&s->a, x, y, v);
-  }
-  return s;
-}
-//疎行列の転置を作成・出力
-SMATRIX *smatrix_transpose(SMATRIX *s) {
-  SLOBJ *p;
-  SMATRIX *t;
-  t = smatrix_new(s->m, s->n);
-  for(p=s->a.next; p!=NULL; p=p->next) {
-    slist_append(&t->a, p->y, p->x, p->v); //行列変換
-  }
-  return t;
-}
-//疎行列をプリント
-void smatrix_print(char *label, SMATRIX *s) {
-  double v;
-  SLOBJ *p;
-  if(label != NULL) printf("%s\n", label);
-  printf("%d %d\n", s->n, s->m);
-  slist_sort(&s->a);
-  p = s->a.next;
-  for(int y=1; y<=s->n; y++) {
-    for(int x=1; x<=s->m; x++) {
-      if(p != NULL && p->x == x && p->y == y) {
-        v = p->v;
-        p = p->next;
-      } else {
-        v = 0.0;
-      }
-      printf("(%d,%d)=%lf%s", x, y, v, x==s->m?"\n":" ");
-    }
   }
 }

コード見直し

2020/04/27 09:33

投稿

jimbe

スコア13209

test CHANGED Viewed

@@ -8,6 +8,16 @@
 テストを簡単にするため, smatrix_read を改造しています.
+#修正
+リストを使うようにし, 2次元で動作するようにしました.
+データが無い所を 0 表示するようにしました.
+ソート部分がテキトウかもしれません.
 ```c
 #include <stdio.h>
@@ -20,7 +30,9 @@
 typedef struct slobj {
+  struct slobj *next; //必ず構造体の先頭にすること
-  int j;
+  int x, y;
   double v;
@@ -28,13 +40,171 @@
+//新しい要素を作成
+SLOBJ *slobj_new(int x, int y, double v){
+  SLOBJ *p;
+  p = (SLOBJ *)malloc(sizeof(SLOBJ));
+  p->next = NULL;
+  p->x = x;
+  p->y = y;
+  p->v = v;
+  return p;
+}
+//リストの構造体
+typedef struct slist {
+  SLOBJ *next; //必ず構造体の先頭にすること
+  SLOBJ *last;
+} SLIST;
+//リスト初期化
+void slist_init(SLIST *slist) {
+  slist->next = NULL;
+  slist->last = (SLOBJ *)slist;
+}
+//リストに追加
+void slist_append(SLIST *slist, int x, int y, double v) {
+  SLOBJ *p;
+  p = slobj_new(x, y, v);
+  slist->last->next = p;
+  slist->last = p;
+}
+//リストをカウント
+int slist_count(SLIST *slist) {
+  int count;
+  SLOBJ *p;
+  count = 0;
+  for(p=slist->next; p!=NULL; p=p->next) count++;
+  return count;
+}
+//リストをソート
+void slist_sort(SLIST *slist) {
+  SLOBJ *o, *p, *q, *t;
+  int count, changed;
+  count = slist_count(slist);
+  if(count <= 1) return;
+  t = NULL;
+  do { //バブル
+    changed = 0; //フラグクリア
+    o = (SLOBJ *)slist;
+    p = o->next;
+    q = p->next;
+    while(q != t) {
+      if(p->y > q->y || (p->y == q->y && p->x > q->x)) { //p>q
+        p->next = q->next; q->next = p; o->next = q; //入れ替え
+        changed = 1; //フラグセット
+      }
+      o = o->next; p = o->next; q = p->next; //次
+      if(q == NULL) slist->last = p;
+    }
+    t = p;
+  } while(changed);
+}
+//リストを解放
+void slist_clear(SLIST *slist) {
+  SLOBJ *p, *q;
+  for(p=slist->next; p!=NULL; p=q) {
+    q = p->next;
+    free(p);
+  }
+  slist_init(slist);
+}
 //疎行列の構造体
 typedef struct {
   int n, m;
-  SLOBJ *a;
+  SLIST a;
 } SMATRIX;
@@ -54,7 +224,7 @@
   s->m = m;
-  s->a = (SLOBJ *)malloc(sizeof(SLOBJ) * n*m);
+  slist_init(&s->a);
   return s;
@@ -66,11 +236,13 @@
 SMATRIX *smatrix_read() {
-  int i, n, m, k=0;
+  int i, n, m, x, y, k=0;
+  double v;
   SMATRIX *s;
-  int test[] = { 2,3,  1,1, 2,2, 3,3,  1,4, 2,5, 3,6 }; //テストデータ
+  int test[] = { 2,3,  1,1,1, /*2,1,2*/ 1,2,4,  2,2,5, 3,2,6, 3,1,3, }; //テストデータ
@@ -80,11 +252,15 @@
   s = smatrix_new(n, m);
-  for (i=0; i<n*m; i++) {
+  for (i=0; i<(sizeof(test)/sizeof(int)-2)/3; i++) {
-    s->a[i].j = test[k++]; //scanf("%d",&s->a[i].j);
+    x = test[k++]; //scanf("%d",&s->a[i].j);
+    y = test[k++];
-    s->a[i].v = test[k++]; //scanf("%lf",&s->a[i].v);
+    v = test[k++]; //scanf("%lf",&s->a[i].v);
+    slist_append(&s->a, x, y, v);
   }
@@ -98,8 +274,6 @@
 SMATRIX *smatrix_transpose(SMATRIX *s) {
-  int i;
   SLOBJ *p;
   SMATRIX *t;
@@ -108,13 +282,9 @@
   t = smatrix_new(s->m, s->n);
-  for (i=0; i<s->n*s->m; i++) {
+  for(p=s->a.next; p!=NULL; p=p->next) {
-    p = &t->a[(i%s->m) * t->m + (i/s->m)];
+    slist_append(&t->a, p->y, p->x, p->v); //行列変換
-    p->j = i/s->m + 1;
-    p->v = s->a[i].v;
   }
@@ -128,7 +298,9 @@
 void smatrix_print(char *label, SMATRIX *s) {
-  int i;
+  double v;
+  SLOBJ *p;
@@ -136,11 +308,31 @@
   printf("%d %d\n", s->n, s->m);
+  slist_sort(&s->a);
+  p = s->a.next;
+  for(int y=1; y<=s->n; y++) {
-  for(i=0; i<s->n*s->m; i++) {
+    for(int x=1; x<=s->m; x++) {
-    printf("%d %lf%s", s->a[i].j, s->a[i].v,
+      if(p != NULL && p->x == x && p->y == y) {
+        v = p->v;
+        p = p->next;
+      } else {
+        v = 0.0;
+      }
-            i%s->m==s->m-1?"\n":" ");
+      printf("(%d,%d)=%lf%s", x, y, v, x==s->m?"\n":" ");
+    }
   }
@@ -150,7 +342,7 @@
 void smatrix_free(SMATRIX *s) {
-  free(s->a);
+  slist_clear(&s->a);
   free(s);
@@ -183,3 +375,25 @@
 }
 ```
+```plain text
+A:
+2 3
+(1,1)=1.000000 (2,1)=0.000000 (3,1)=3.000000
+(1,2)=4.000000 (2,2)=5.000000 (3,2)=6.000000
+B:
+3 2
+(1,1)=1.000000 (2,1)=4.000000
+(1,2)=0.000000 (2,2)=5.000000
+(1,3)=3.000000 (2,3)=6.000000
+```

説明変更

2020/04/27 09:17

投稿

jimbe

スコア13209

test CHANGED Viewed

@@ -4,13 +4,9 @@
 ということで, マトリクス生成時に大きさが決まっているのでリストにする必要が無いようですし, 実体とポインタが混在して分かり難く感じましたので, リスト関係を消し, SMATRIX の malloc をするようにしてみました.
-これなら解放抜けはし難いと思います.
+大きな行列で無ければこのほうが解放抜けはし難いと思います.
 テストを簡単にするため, smatrix_read を改造しています.
-...SLOBJ.j は"列番号"として表示しているだけのようですが構造体内に要るのでしょうか.
 ```c