memo

Transcription

1 数理情報工学演習第一 C プログラミング演習 ( 第 5 回 ) 2015/05/11 DEPARTMENT OF MATHEMATICAL INFORMATICS 1

2 今日の内容 : プロトタイプ宣言 ヘッダーファイル, プログラムの分割 課題 : 疎行列 2

3 プロトタイプ宣言 3 C 言語では, 関数や変数は使用する前 ( ソースの上のほう ) に定義されている必要がある. double sub(int x, double y) { return (double)x * y; } int main() { double z; z = sub(1, 2.5); // OK } int main() { int z; z = sub(1, 2.5); // NG } double sub(int x, double y) { return (double)x * y; }

4 関数のプロトタイプ宣言 double sub(int x, double y); // 後 ( 下 ) に出てくる関数の型を示す int main() { double z; z = sub(1, 2.5); // OK } double sub(int x, double y) { return (double)x * y; } 4

5 ヘッダーファイル ( 標準 ) ライブラリに入っている関数や定数が宣言してある #include <stdio.h> // 標準入出力ヘッダー int main() { printf( Hello. n ); // stdio.h 内で宣言してある } 5

6 stdio.h で宣言してあるもの FILE 構造体 fopen, fclose, fprintf, fscanf, NULL EOF 6

7 stdlib.h で宣言してあるもの malloc, free exit atoi, atof rand ( 乱数発生 ) qsort ( ソート ) bsearch (2 分探索 ) 7

8 プログラムの分割 1つのファイルに全ての処理を書くと 長くて分かりにくい プログラムの再利用がしにくい ( 再コンパイルに時間がかかる ) まとまった処理ごとに分割してファイルを作る 行列演算 (matrix.c) 全体 (main.c) gcc main.c matrix.c 8 注 : それぞれのファイルは単独でコンパイルできるようにする ヘッダーファイルを使う

9 matrix.h の中身 typedef struct { int n,m; slist **R; } smatrix; smatrix *smatrix_read(file *fin); void smatrix_write(file *fout, smatrix *a); smatrix *smatrix_product(smatrix *A, smatrix *B); 9

10 matrix.c の中身 #include matrix.h // 構造体の定義を読み込む smatrix *smatrix_read(file *fin) { } // 関数の中身を書く void smatrix_write(file *fout, smatrix *a) { } // 自分で作ったファイルを読み込むときは で括る 10

11 main.c の中身 #include matrix.h // 構造体の定義や関数のプロトタイプ宣言 int main(int argc, char *argv[]) { smatrix *A, *B, *C; // smatrixは matrix.h で定義してある A = smatrix_read(stdin); B = smatrix_read(stdin); C = smatrix_product(a, B); smatrix_write(stdout, C); } 11

12 分割コンパイル 各ソースファイルを個別にコンパイルし, 最後に実行ファイルを作る gcc c o matrix.o matrix.c O3 #matrix.c のコンパイル gcc c o main.o main.c O3 #main.c のコンパイル gcc o main.out matrix.o main.o # リンク 修正したファイルだけ再コンパイルできる 注 : ヘッダーファイルを修正した場合, それをインクルードしている全てのソースファイルは再コンパイルする必要がある 自動化するには make コマンドを使用する 12

13 2 重インクルードの防止 ヘッダーファイル中で別のヘッダーファイルをインクルードする場合などに, 構造体等の宣言が 2 回出てくるとエラーになる 2 重インクルードを防止するために, ヘッダーファイル内にフラグを用意する #ifndef MATRIX_H // MATRIX_H が定義されていなければ以下が読まれる #define MATRIX_H // 1 回目に読まれたときに MATRIX_H を定義する // matrix.h の中身を書く #endif // #ifndef の行と対応 13

14 Tips 全ての関数は外部のオブジェクトファイル (.o) から参照できる 下手に名前をつけると, 名前の衝突が起きてしまう 外部で使用しない関数には static をつける // matrix.c static sub(smatrix *A) { } // matrix.c の外からは見えない smatrix *smatrix_transpose(smatrix *A) // 外から見える { smatrix *B; B = sub(a); // matrix.c 内ではsubは使える } 14

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

16 リストの要素を変更 typedef struct slobj { struct slobj *next; // 後の要素へのポインタ int j; // j 列目 data v; // 値 } slobj; リストに挿入する際は, 値の小さい順ではなく,j の小さい順にする typedef struct { slobj *head; slobj *tail; } slist; L head tail // 先頭要素のポインタ // 末尾要素のポインタ key next NULL

17 行列の構造体 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,

18 課題 2つの疎行列の積を計算する プログラムの仕様 入出力は標準入力 / 出力 標準入力から行列 A と B のデータを続けて読み込む 行列積 AB を標準出力に出力 締切 5/13( 水 ) 17:00 宛先 :miprogramming2015+5@gmail.com 18

19 注意 domjudge に投稿する際は, 必要なファイルすべてを選択してアップロードする ファイルを分割した場合, インクルードファイル内でも stdio.h 等をインクルードしないとエラーになる 19

20 行列のファイル形式 行数列数 1 行目 2 行目 3 行目 4 行目 5 行目 各要素は列の位置と要素の値で表現される行の最後には -1 を書く 20

21 ヒント ( 作成する関数 ) リストの末尾に r を追加 void slist_append(slist *L, slobj *r) 零行列を作る 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 を返す 21

22 疎行列を読み込み, 新たに確保した疎行列に代入 smatrix *smatrix_read(file *in); 疎行列を入力と同じ形式出力 void smatrix_write(file *out, smatrix *a); 2つの疎行列 A, B の積を計算し, 新たに確保した疎行列 C に代入 smatrix *smatrix_product(smatrix *A, smatrix *B); 行列のサイズが合わないときは C は確保せずに NULL を返す 演算の効率も考慮する 疎行列のメモリを開放する void smatrix_free(smatrix *A); 22