2014-4 - Researchmap

THE UNIVERSITY OF TOKYO
数理情報工学演習第一Ｃ
プログラミング演習 (第4回 )
2014/04/28
DEPARTMENT OF MATHEMATICAL INFORMATICS
1
THE UNIVERSITY OF TOKYO
今日の内容:
 リスト
 疎行列の演算
 課題：リスト，疎行列
2
THE UNIVERSITY OF TOKYO
mallocを簡単に
エラーチェックを毎回書くのは面倒なので…
double *p;
p = malloc(sizeof(double));
if (p == NULL) {
printf("not enough memory.∖n"); exit(1);
}
プログラムの最初の方でマクロを定義
#define mymalloc(p,n) {p = malloc((n)*sizeof(*p));
if ((p)==NULL) {printf("not enough memory∖n"); exit(1);};}
注: 改行は入れない
使うときは
double *p;
mymalloc(p,n); // doubleで n 個分の領域を確保し，ポインタを p に入れる
3
THE UNIVERSITY OF TOKYO
連結リスト (Linked Lists)
オブジェクトをある線形順序に並べて格納するデータ構造
単方向連結リスト (signly linked list) L の要素 x
キーフィールド key
ポインタフィールド next
x->next: リスト中の x の直後の要素のポインタ
x->next = NIL のとき，x は最後の要素
L->head: リストの先頭の要素のポインタ
L->head = NIL のとき，リストは空
key
L
4
9
16
next
NIL
4
THE UNIVERSITY OF TOKYO
単方向リストの構造体
リストの要素
typedef struct slobj {
struct slobj *next; // 後の要素へのポインタ
data key;
// キー
} slobj;
単方向リスト
typedef struct {
lobj *head;
} slist;
5
// 先頭要素のポインタ
THE UNIVERSITY OF TOKYO
連結リストの探索
slist_search(L, k): リスト L に属する，キー k を持つ最初の要素の
ポインタを返す
キー k を持つ要素が存在しなければ NULL を返す
slobj *slist_search(slist *L, data k)
{
slobj *p;
p = L->head;
while (p != NULL && p->key != k) {
p = p->next;
}
return p;
}
key next
L
6
9
16
NIL
4
THE UNIVERSITY OF TOKYO
連結リストの先頭への挿入
slist_insert_head(L, p): p を L の先頭に挿入
p のキーは既にセットされているとする
void slist_insert_head(slist *L, slobj *p)
{
p->next = L->head;
L->head = p;
}
p
9
L
7
L
9
16
4
16
4
THE UNIVERSITY OF TOKYO
連結リストの中間への挿入
slist_insert(L, r): r を L に挿入
挿入場所は (p->key) < (r->key) となる最初の p の直後
つまり，リストの要素は常に key の小さい順に並んでいる
r
2
8
L
1
3
L
1
2
3
THE UNIVERSITY OF TOKYO
リストを先頭から探索し，挿入場所を決める
挿入場所がリストの先頭かそれ以外かで処理を変える必要あり
r
2
9
L
1
3
L
1
2
3
THE UNIVERSITY OF TOKYO
課題（初級）
 x を含むリストの要素を作成
 slobj *make_slobj(data x);
 空のリストの作成
 slist *make_slist(void);
 リストの中身を画面に表示する
 void slist_print(slist *L)
 リストから，k を含む要素を探索
 slobj *slist_search(slist *L, data k)
 リストに r を挿入．ソート順を保つ
 void slist_insert(slist *L, slobj *r)
10
THE UNIVERSITY OF TOKYO
リストを用いた疎行列の表現
R
• 密行列の表現
1 3 2 6
– 各行は，1次元配列
8 5 4 1
– 行列は，(行へのポインタ)の1次元配列 R
9 2 3 1
• 疎行列の表現
– 各行は，非零要素のリスト
– 行列は，(行を表すリスト)の1次元配列 R
R
1, 3.0
5, 1.0
2, 1.0
3, 1.0
11
4, 2.0
THE UNIVERSITY OF TOKYO
•
行の配列 R の実現方法は2つある
1. (slistのポインタ)の配列
•
slist **R;
slistの配列: slist R[10]; // サイズ固定
slist *R; // サイズ可変
slistのポインタの配列: slist *R[10];
slist **R;
2. (slobjのポインタ)の配列
•
12
slobj **R;
•
1. の方が楽（これまでのプログラムをそのまま使える）だが，
2. の方が多少効率がよい．
•
2. では，i 行目のリストの先頭要素は R[i]->head ではなく R[i] になる
THE UNIVERSITY OF TOKYO
リストと行列の要素を変更
typedef struct slobj {
struct slobj *next; // 後の要素へのポインタ
int j;
// j 列目
data v;
// 値
} slobj;
リストに挿入する際は，値の小さい順ではなく，j の小さい順にする
typedef struct {
int n,m;
slist **R;
} smatrix;
13
THE UNIVERSITY OF TOKYO
課題（中級）
 零行列を作る
 smatrix *smatrix_new(int n, int m)
 行列 S の (i,j) 要素を x にする
 void smatrix_insert(smatrix *S, int i, int j, data x)
 挿入前の (i,j) 要素は 0 と仮定してよい
 行列 S の (i,j) 要素を求める
 data smatrix_access(smatrix *S, int i, int j)
 (i,j) 要素がリストになければ 0 を返す
14
THE UNIVERSITY OF TOKYO
課題（上級）
 疎行列をファイルから読み込み，新たに確保した疎行列に代入
 smatrix *smatrix_read(char *filename);
 疎行列を入力と同じ形式でファイルに出力
 void smatrix_write(char *filename, smatrix *a);
 2つの疎行列 A, B の積を計算し，新たに確保した疎行列 C に代入
 smatrix *product(smatrix *A, smatrix *B);
 行列のサイズが合わないときは C は確保せずに NULL を返す
 演算の効率も考慮する
 疎行列のメモリを開放する
 void smatrix_free(smatrix *A);
15
THE UNIVERSITY OF TOKYO
行列のファイル形式
5
1
1
2
4
5
5
1.0
2.0
2.0
1.0
1.0
2 2.0 -1
2 1.0 3 2.0 -1
3 1.0 -1
-1
-1
行数列数
1行目
2行目
３行目
4行目
５行目
0
0 
 1.0 2.0 0


0 
 2.0 1.0 2.0 0
 0 2.0 1.0 0
0 


0
0 1.0 0 
 0
 0

0
0
0
1
.
0


各要素は列の位置と要素の値で表現される
行の最後には -1 を書く
16
THE UNIVERSITY OF TOKYO
課題の提出:
 初級：本日（4/28）の18時までに提出
• 宛先：[email protected]
– 中級：5/7までに提出
• 宛先：[email protected]
– 上級：5/7まで（できる人だけ）
• 宛先：中級と同じ
17
THE UNIVERSITY OF TOKYO

Download Report