memo

Transcription

1 計数工学プログラミング演習 ( 第 4 回 ) 2016/05/10 DEPARTMENT OF MATHEMATICA INFORMATICS 1

2 内容 リスト 疎行列 2

3 連結リスト (inked ists) オブジェクトをある線形順序に並べて格納するデータ構造 単方向連結リスト (signly linked list) の要素 x キーフィールド key ポインタフィールド next x->next: リスト中の x の直後の要素のポインタ x->next = NU のとき,x は最後の要素 ->head: リストの先頭の要素のポインタ ->head = NU のとき, リストは空 key next NU

4 単方向リストの構造体 リストの要素 単方向リスト typedef struct slobj { struct slobj *next; // 後の要素へのポインタ int key; // キー } slobj; typedef struct { slobj *head; } slist; // 先頭要素のポインタ 4

5 空のリストを作る slist *slist_new(void) { slist *; = (slist *)malloc(sizeof(slist)); ->head = NU; // リストの要素が無いことを表す return ; } 5

6 リストの要素を作る x を持つリストの要素を作る slobj *slobj_new(int x) { slobj *p; p = (slobj *)malloc(sizeof(slobj)); p->key = x; p->next = NU; // 必ず初期化しておく return p; } 6

7 連結リストの探索 slist_search(, k): リスト に属する, キー k を持つ最初の要素のポインタを返す キー k を持つ要素が存在しなければ NU を返す slobj *slist_search(slist *, int k) { slobj *p; p = ->head; while (p!= NU && p->key!= k) { p = p->next; } return p; } key next NU

8 連結リストの先頭への挿入 slist_insert_head(, p): p を の先頭に挿入 p のキーは既にセットされているとする void slist_insert_head(slist *, slobj *p) { p->next = ->head; ->head = p; } p

9 連結リストの中間への挿入 slist_insert(, r): r を に挿入 挿入場所は (p->key) > (r->key) となる最初の p の直前 つまり, リストの要素は常に key の小さい順に並んでいる r 2 q p 1 3 q r p

10 リストを先頭から探索し, 挿入場所を決める 挿入場所がリストの先頭かそれ以外かで処理を変える必要あり r

11 途中に挿入する場合 r 2 q q->next p 1 3 q q->next p r r->next

12 先頭に挿入する場合 r 0 ->head p p->next 1 3 ->head r r->next p p->next

13 リストを用いた疎行列の表現 密行列の表現 各行は,1 次元配列 行列は,( 行へのポインタ ) の1 次元配列 R 疎行列の表現 各行は, 非零要素のリスト 行列は,( 行を表すリスト ) の1 次元配列 R R 1, 3.0 5, 1.0 2, 1.0 3, 1.0 4, 2.0 R

14 リストの要素を変更 typedef struct slobj { struct slobj *next; int j; double v; } slobj; // 後の要素へのポインタ // j 列目 // (i, j) 要素 リストに挿入する際は, 値の小さい順ではなく,j の小さい順にする 14

15 行列の構造体 typedef struct { int n,m; // 行数, 列数 slist **R; // 行ベクトルを表すリストの配列 } smatrix; R R[0] R[1] R[2] 1, 3.0 5, 1.0 2, 1.0 3, 1.0 4,

16 行列のファイル形式 行数列数 1 行目 2 行目 3 行目 4 行目 5 行目 各要素は列の位置と要素の値で表現される位置は自然数 ( 最初が 1) 行の最後には -1 を書く同一行内の要素は列番号の小さい順になっている 16

17 第 4 回課題 : 2 つの疎行列の積を計算するプログラム 入力行列は標準入力から与えられる 1 行目は行列の行数と列数 1 つ目の行列のデータの直後に 2 つ目の行列のデータが来る 標準入力から続けて読めばいい 結果は標準出力に 入力と同じ形式 積を計算できない場合は 0 行 0 列の行列を出力する 出力は 0 0 の 1 行だけ main 関数の最後は return 0; をつけておく 提出するソースコードの中に, 学生証番号, 氏名, メールアドレスをコメントとして書いておく 締切 : 2016 年 5 月 10 日 ( 火 ) 17:35 ( 演習終了時 ) 17

18 ヒント ( 作成する関数 ) 零行列を作る smatrix *smatrix_new(int n, int m) 行列 S の (i,j) 要素を x にする void smatrix_insert(smatrix *S, int i, int j, double x) 挿入前の (i,j) 要素は 0 と仮定してよい 行列 S の (i,j) 要素を求める double smatrix_access(smatrix *S, int i, int j) (i,j) 要素がリストになければ 0 を返す access が実現できれば, 行列積は計算できる. ただし効率は悪い. 余力があれば, 効率の良い行列積アルゴリズムを実装する. 18

19 void smatrix_insert(smatrix *S, int i, int j, double x) { slobj *p; if (i <= 0 i > S->n j <= 0 j > S->m) { printf("smatrix_insert: n=%d m=%d i=%d j=%d n", S->n, S->m, i, j); exit(1); } p = slobj_new(j, x); slist_insert(s->r[i-1], p); } 19

20 double smatrix_access(smatrix *S, int i, int j) { slist *; slobj *p; if (i <= 0 i > S->n j <= 0 j > S->m) { printf("smatrix_access: n=%d m=%d i=%d j=%d n", S->n, S->m, i, j); exit(1); } = S->R[i-1]; p = slist_search(, j); if (p!= NU) return p->v; return 0; } 20