2014-5 - Researchmap

THE UNIVERSITY OF TOKYO
数理情報工学演習第一Ｃ
プログラミング演習 (第5回 )
2014/05/12
DEPARTMENT OF MATHEMATICAL INFORMATICS
1
THE UNIVERSITY OF TOKYO
今日の内容:
 プロトタイプ宣言
 ヘッダーファイル，プログラムの分割
 双方向リスト
 課題：リスト，疎行列
2
THE UNIVERSITY OF TOKYO
プロトタイプ宣言
• C言語では，関数や変数は使用する前(ソースの上のほう)に
定義されている必要がある．
double sub(int x, double y)
{
return (double)x * y;
}
int main()
{
double z;
z = sub(1, 2.5); // OK
}
3
int main()
{
int z;
z = sub(1, 2.5); // NG
}
double sub(int x, double y)
{
return (double)x * y;
}
THE UNIVERSITY OF TOKYO
関数のプロトタイプ宣言
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
THE UNIVERSITY OF TOKYO
ヘッダーファイル
• (標準)ライブラリに入っている関数や定数が宣言してある
#include <stdio.h> // 標準入出力ヘッダー
int main()
{
printf(“Hello.∖n”); // stdio.h 内で宣言してある
}
5
THE UNIVERSITY OF TOKYO
stdio.h で宣言してあるもの
• FILE構造体
• fopen, fclose, fprintf, fscanf, …
• NULL
• EOF
6
THE UNIVERSITY OF TOKYO
stdlib.h で宣言してあるもの
• malloc, free
• exit
• atoi, atof
• rand (乱数発生)
• qsort (ソート)
• bsearch (2分探索)
7
THE UNIVERSITY OF TOKYO
プログラムの分割
• 1つのファイルに全ての処理を書くと
– 長くて分かりにくい
– プログラムの再利用がしにくい
– (再コンパイルに時間がかかる)
• まとまった処理ごとに分割してファイルを作る
– 行列演算 (matrix.c)
– 全体 (main.c)
– gcc main.c matrix.c
• 注: それぞれのファイルは単独でコンパイルできるようにする
⇒ヘッダーファイルを使う
8
THE UNIVERSITY OF TOKYO
matrix.h の中身
typedef struct {
int n,m;
slist **R;
} smatrix;
smatrix *smatrix_read(char *filename);
void smatrix_write(char *filename, smatrix *a);
smatrix *smatrix_product(smatrix *A, smatrix *B);
9
THE UNIVERSITY OF TOKYO
matrix.c の中身
#include “matrix.h” // 構造体の定義を読み込む
自分で作ったファイルを読み込む
ときは “…” で括る
smatrix *smatrix_read(char *filename)
{
// 関数の中身を書く
}
void smatrix_write(char *filename, smatrix *a)
{
//
}
10
THE UNIVERSITY OF TOKYO
main.c の中身
#include “matrix.h” // 構造体の定義や関数のプロトタイプ宣言
int main(int argc, char *argv[])
{
smatrix *A, *B, *C; // smatrixは matrix.h で定義してある
A = smatrix_read(argv[1]);
B = smatrix_read(argv[2]);
C = smatrix_product(A, B);
smatrix_write(argv[3], C);
}
11
THE UNIVERSITY OF TOKYO
分割コンパイル
• 各ソースファイルを個別にコンパイルし，最後に実行ファイルを作る
– 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
THE UNIVERSITY OF TOKYO
2重インクルードの防止
• ヘッダーファイル中で別のヘッダーファイルをインクルードする場合などに，
構造体等の宣言が2回出てくるとエラーになる
• 2重インクルードを防止するために，ヘッダーファイル内にフラグを用意する
#ifndef MATRIX_H // MATRIX_Hが定義されていなければ以下が読まれる
#define MATRIX_H // 1回目に読まれたときに MATRIX_H を定義する
// matrix.h の中身を書く
…
#endif // #ifndef の行と対応
13
THE UNIVERSITY OF TOKYO
Tips
• ヘッダファイルの中で構造体を宣言する場合，その中で他の構造体を
使っているとそれの宣言も必要になる
• ヘッダファイルではプロトタイプ宣言だけにしておく
• 構造体内部へのアクセスは matrix.c 内のみで行うようにする
// matrix.h
// matrix.h
typedef struct smatrix_{
int n,m;
typedef struct smatrix_ smatrix;
smatrix *smatrix_read(char *);
slist **R;
} smatrix;
smatrix *smatrix_read(char *);
14
THE UNIVERSITY OF TOKYO
Tips
• 全ての関数は外部のオブジェクトファイル (.o) から参照できる
• 下手に名前をつけると，名前の衝突が起きてしまう
• 外部で使用しない関数には static をつける
// matrix.c
static sub(smatrix *A) {…} // matrix.c の外からは見えない
smatrix *smatrix_transpose(smatrix *A) // 外から見える
{
smatrix *B;
B = sub(A); // matrix.c 内ではsubは使える
}
15
THE UNIVERSITY OF TOKYO
連結リスト (Linked Lists)
オブジェクトをある線形順序に並べて格納するデータ構造
単方向連結リスト (singly linked list) L の要素 x
キーフィールド key
ポインタフィールド next
x->next: リスト中の x の直後の要素のポインタ
x->next = NIL のとき，x は最後の要素
L->head: リストの先頭の要素のポインタ
L->head = NIL のとき，リストは空
key
L
16
9
16
next
NIL
4
THE UNIVERSITY OF TOKYO
リストの種類
一方向 (singly linked) と双方向 (doubly linked)
一方向のとき，各要素は prev を持たない
既ソート (sorted) と未ソート
既ソート: リストの線形順序はキーの線形順序に対応
未ソート: 任意の順序
循環 (circular list) と非循環
循環: リストの先頭要素の prev はリストの末尾を指し，末尾の next はリスト
の先頭を指す
17
THE UNIVERSITY OF TOKYO
双方向リストの構造体
リストの要素
typedef struct dlobj_ {
struct dlobj_ *prev; // 前の要素へのポインタ
struct dlobj_ *next; // 後の要素へのポインタ
data key;
// キー
} dlobj;
双方向リスト
typedef struct {
dlobj *head;
} dlist;
18
// 先頭要素のポインタ
THE UNIVERSITY OF TOKYO
連結リストの探索
dlist_search(L, k): リスト L に属する，キー k を持つ最初の要素のポインタを返す
キー k を持つ要素が存在しなければ NULL を返す
(n) 時間
head(L)
19
dlobj *dlist_search(dlist *L, data k)
{
dlobj *x;
x = L->head;
while (x != NULL && x->key != k) {
x = x->next;
}
return x;
}
9
16
4
THE UNIVERSITY OF TOKYO
連結リストへの挿入
dlist_insert(L, x): x を L の先頭に挿入
x のキーは既にセットされているとする
O(1) 時間
x
void dlist_insert(dlist *L, dlobj *x)
{
x->next = L->head;
if (L->head != NIL)
L->head->prev = x;
L->head = x;
x->prev = NIL;
}
9
head(L)
head(L)
20
9
16
4
16
4
THE UNIVERSITY OF TOKYO
連結リストからの削除
dlist_delete(L, x): L から x を削除
O(1) 時間 void dlist_delete(dlist *L, dlobj *x)
{
if (x->prev != NULL) x->prev->next = x->next;
else
L->head = x->next;
if (x->next != NIL) x->next->prev = x->prev;
}
21
head(L)
9
head(L)
9
x
16
4
4
THE UNIVERSITY OF TOKYO
双方向循環リストの構造体
リストの要素 (以前と同じ)
typedef struct dlobj_ {
struct dlobj_ *prev; // 前の要素へのポインタ
struct dlobj_ *next; // 後の要素へのポインタ
data key;
// キー
} dlobj;
双方向リスト
typedef struct {
dlobj *nil;
} dlist;
22
// NILを表す要素のポインタ
THE UNIVERSITY OF TOKYO
データ構造の変更点
リスト L は NIL を表現するオブジェクトを持つ
双方向リストをNILを含めた循環リストに変更
先頭要素は L->nil->next
nil(L)
9
16
4
NIL
23
THE UNIVERSITY OF TOKYO
連結リストの探索
dlist_search(L, k): リスト L に属する，キー k を持つ最初の要素のポインタを返す
キー k を持つ要素が存在しなければ NIL を返す
dlobj *dlist_search(dlist *L, data k)
(n) 時間
{
dlobj *x;
x = L->nil->next;
while (x != L->nil && x->key != k) {
x = x->next;
}
nil(L)
return x;
}
9
24
16
4
THE UNIVERSITY OF TOKYO
連結リストへの挿入
dlist_insert(L, x): x を L の先頭に挿入 void dlist_insert(dlist *L, dlobj *x)
{
x のキーは既にセットされているとする x->next = L->nil->next;
L->nil->next->prev = x;
L->nil->next = x;
x->prev = L->nil;
O(1) 時間
x
nil(L)
9
9
25
}
16
4
16
4
THE UNIVERSITY OF TOKYO
課題（初級）: 双方向循環リスト
 x を含むリストの要素を作成
 dlobj *dlobj_new(data x);
 空のリストの作成
 dlist *dlist_new(void);
 リストから，k を含む要素を探索
 dlobj *dlist_search(dlist *L, data k)
 リストの先頭に r を挿入
 void dlist_insert(dlist *L, dlobj *r)
 リストの末尾に r を追加
 void dlist_append(dlist *L, dlobj *r)
26
THE UNIVERSITY OF TOKYO
リストから，r を削除
 void dlist_delete(dlist *L, dlobj *r)
 r のメモリは解放しない
リスト全体を消去
 void dlist_free(dlist *L)
 リスト自体と，その中の全要素のメモリを解放 (free) する
• dlist.h, dlist.c, main.c に分割する
• 初級：明日（5/13）の正午までに提出
• 宛先：[email protected]
27
THE UNIVERSITY OF TOKYO
課題（中級）
 双方向循環リストを用いて疎行列を作る
 疎行列をファイルから読み込み，新たに確保した疎行列に代入
 smatrix *smatrix_read(char *filename);
 疎行列を入力と同じ形式でファイルに出力
 void smatrix_write(char *filename, smatrix *a);
 2つの疎行列 A, B の積を計算し，新たに確保した疎行列 C に代入
 smatrix *smatrix_product(smatrix *A, smatrix *B);
 リストの途中への追加は遅いので，先頭または末尾への追加のみ用いる
 積の計算も，(i,j) 要素へのaccessを用いると遅いので，リストを先頭から見て
いく操作のみで実現する
28
THE UNIVERSITY OF TOKYO
• dlist.h, dlist.c, matrix.h, matrix.c, main.c に分割する
• 中級：5/16(金) の正午までに提出
• 宛先：[email protected]
29
THE UNIVERSITY OF TOKYO

Download Report