I117 プログラミング演習II

Transcription

1 I117 プログラミング演習 II I117 PROGRAMMING PRACTICE II メモリ管理 1 MEMORY MANAGEMENT 1 情報社会基盤研究センター Research Center for Advanced Computing Infrastructure (RCACI) 小原泰弘 / Yasuhiro Ohara yasu@jaist.ac.jp

2 スケジュール / SCHEDULE /06/07(Tue): プログラミングの基礎 / Basic of Programming /06/09(Thu): 基本データ構造 / Fundamental data structures /06/14(Tue): メモリ管理 1 / Memory Management /06/16(Thu): メモリ管理 2 / Memory Management /06/21(Tue): デバッグ / Debugging /06/23(Thu): ソフトウェア開発環境 1 / Software Development Env /06/28(Tue): ソフトウェア開発環境 2 / Software Development Env /06/30(Thu): 木 / Data Structure : Tree /07/05(Tue): ハッシュ / Data Structure: Hash /07/07(Thu): プログラム理解 1 / Understanding Programs /07/12(Tue): プログラム理解 2 / Understanding Programs /07/14(Thu): スクリプト言語 1 / Script Language /07/19(Tue): スクリプト言語 2 / Script Language /07/21(Thu): その他の言語 / Other Languages /07/26(Tue): 試験 / Examination

3 今日の目次 C 言語の基礎 構造体 メモリ管理 malloc () 基本データ構造 配列と連結リスト 木 スタック キュー 演習 プログラミング環境の整備 マルコフ連鎖プログラムの解説

4 VI の使い方 h j k l Ctrl-[ Esc で移動モード / 検索文字 : 検索文字までジャンプ Ctrl-G 状態表示 ':': コマンドモード u: Undo {: 前の空行へ : 次の空行へ編集モード i: 挿入モード a: 追加モード o: 次行挿入モード O: 前行挿入モード C: 後続行置き換え x: 一文字削除 dd: 一行削除 D: 後続行削除 J: 次の行を連結 1,$s/hoge/hage/g ( 置き換え ) 行数 : 行数へジャンプ r ファイル名 : ファイルを読み込み sp ファイル名 : 画面二分割で編集 e ファイル名 : 編集ファイルを変更 w: 保存 q: 終了 G: ファイルの最後まで t[ 文字 ]: 同行内次の文字の直前 f[ 文字 ]: 同行内次の文字 d[ 移動 ]: 移動先まで削除 c[ 移動 ]: 移動先まで置き換え c2f' ': 2 個先の空白まで置き換え 0: 行の先頭 $: 行の終わり

5 C 言語基礎

6 構造体

7 構造体 変数と配列の限界 同じ型のデータだけでは表現し切れない 異なる型の変数を一まとめにして使いたい 構造体

8 構造体の例 struct sockaddr_in { u_char sin_len; u_char sin_family; u_short sin_port; ; 構造体 struct in_addr sin_addr; char sin_zero[8]; 名前 struct xxx { ; ; 8bit 8bit 16bit 8bit x 4 8bit x 8 メンバー sin_len sin_family sin_port sin_addr sin_zero[0] sin_zero[4] sin_zero[1] sin_zero[5] sin_zero[2] sin_zero[6] sin_zero[3] sin_zero[7]

9 関数 関数 同じような処理を一まとめにしたもの 名前を付けられる 名前で呼び出すことができる 引数で呼び出した側からデータを渡すことができる { で囲まれている ( ブロック ) 処理の結果 あるいは処理中に発生したエラーを返り値で呼び出し側に伝えることができる ライブラリ関数 システムあるいは誰かが予め用意した関数群 printf(), str (), atoi() など 画像処理用の関数群 数学の関数群 データベース操作関数群

10 関数 (CONT'D) 関数の例 引数で渡された文字列の文字数を返す (strlen() と同じ ) int my_strlen(char *str) 関数名 引数 返り値 { 関数のはじまり char *cp; int nbyte = 0; for(cp = str; *cp!= 0; cp++) { 文字数を数える変数 nbyte++; return(nbyte); 文字を数える 文字配列走査のためのポインタ 関数の終わり 渡された文字列に 0 が現れない間繰り返す 数えた文字数を返り値として返す

11 関数 (CONT'D) main() { char buf[] = "this is test"; int nbyte; nbyte = my_strlen(buf); printf("buf: %s, length: %d n", buf, nbyte); 関数の呼び出し int my_strlen(char *str) {.

12 関数とポインタ 関数を呼び出す側の変数を関数の処理で変更したい時 upper(char *str) { while(*str!= NULL) { if(*str > 'a' && *str < 'z') { *str = *str - 26; str++; main() { char buf[256]; strcpy(buf, "This Is Test String."); upper(buf); printf("%s n", buf);

13 ポインタ VS 配列 巨大な配列があったときにどちらのアクセスが早いか? 個の配列 gettimeofday() delta_timeval(struct timeval *begin, struct timeval *end);

14 構造体 データをまとめて格納可能な型 C 言語での例 /* 日付を表す構造体を定義 */ struct date { int year; int month; int day; ; /* 構造体へのアクセスはメンバアクセス演算子 (.) を用いる */ Void func() { struct date today; /* 構造体宣言 */ today.year = 2010; /* today.month = 6; * 構造体のメンバ変数にアクセス today.day = 9; */

15 HOSTENT 構造体 struct hostent { char *h_name; /* official name of host */ char **h_aliases; /* alias list */ int h_addrtype; /* host address type */ int h_length; /* length of address */ char **h_addr_list; /* list of addresses from name server */ #define h_addr h_addr_list[0] /* address, for backward compatiblity */ ;

16 HOSTENT 構造体 hostent h_name h_aliases h_addrtype h_length h_addr_list AF_INET 4 ホスト名 (NULL) (NULL) エイリアス名エイリアス名 in_addr IP address IP address IP address h_length = 4

17 メモリレイアウト a.out の例 プログラムの実行可能コードはテキストセグメントに配置される 初期化済みの静的変数はデータセグメントに配置される 未初期化の静的変数は bss セグメントに配置される 動的変数はヒープ上に確保される malloc などで確保する領域 ローカル変数はスタック上に確保される 関数の引数 ローカル変数 ( 関数内の変数 ) 戻り値 テキストセグメント ( 読み出し専用 ) データ bss ヒープ スタック 0x1000 higher address

18 ポインタとメモリレイアウトの関係 普通の変数もポインタ変数も同じメモリ上に配置される 普通の変数には値が入っている ポインタ変数にはアドレスが入っている スタック領域 Void func() { int var = 10; 0xff int *p = &var; int **pp = &p; pp p var 0xff xff xff xff000008

19 構造体のポインタ 構造体ポインタを用いて メンバ変数へアクセスするためには アロー演算子 (->) を用いる /* 構造体 dateのポインタを引数にとる関数 */ Void func(struct date *today) { today->year = 2010; /* アロー演算子を用いて today->month = 6; * 構造体のメンバ変数にアクセス today->day = 9; */

20 値渡しと参照渡し 値渡し データをまるごとコピーして 関数に渡す方法 渡したデータの内容が変更されない 渡すデータのサイズが大きいと オーバヘッドも大 参照渡し データの参照 (C 言語ではポインタ ) だけを関数に渡す方法 データのコピーは行われないのでオーバヘッド小 渡したデータの内容が変更される場合がある Void val_func(struct date today) { today.year = 2010; today.month = 6; today.day = 9; Void ref_func(struct date *today) { today->year = 2010; today->month = 6; today->day = 9; Void main(void) { struct date d1 = {0, 0, 0; struct date d2 = {0, 0, 0; val_func(d1); ref_func(&d2); d1 と d2 の値はどうなるか?

21 様々な言語の値渡しと参照渡し C++ 基本的にすべて値渡し ポインタ変数と参照変数がある JavaScript Java 数値や真偽値などの基本データ型は値渡し その他の リストやオブジェクトは値渡し Python Ruby すべて参照渡し

22 参照渡しに関する問題 ( 上級者向け ) 以下の C 言語のプログラムは 777 を出力する Void func(int *var) { *var = 777; Void main(void) { int n = 0; func(&n); printf( %d n, n); /* 777と出力される */ しかし 以下の Pythonプログラムは0が出力される 参照渡しなのに値が変更されないのは何故か? def func(var): var = 777 n = 0 func(n) print n # 0 が出力される

23 キャスト ある変数 構造体を無理やり違う型の変数や構造体として扱う方法 変数を使う時に扱いたい型をカッコで括る (int)no_int_variable; int 型にキャスト 関数の引数を一般化するのに便利 sockaddr の例 struct sockaddr_in sin; (struct sockaddr)sin; 型やサイズに依存せず 1 バイトずつ読みたいときにも使う long addr = ; char *cp = (char *)&addr; for(j = 0; j < 4; j++) { printf("%c ", *cp++);

24 メモリ管理

25 配列 (ARRAY) 連続した記憶領域 文字列等の記憶に利用 char array[ ] = program ; N 次元表記 配列の添え字が 2 次 P r o g r a m 0 char array[n][m]; N M

26 メモリ関数 malloc () free () strdup ()

27 新しく必要となるメモリの確保 #include <stdlib.h> void * malloc (size_t size); void free (void *ptr); malloc: Memory ALLOCate の略 size バイト分のメモリを確保し 帰り値として返す free: malloc () で確保したメモリを解放する * 注 ) いらなくなった malloc () メモリはちゃんと free すること 例 ) struct listnode *target = (struct listnode *) malloc (sizeof (struct listnode)); free (target);

28

29 2 次元配列の動的割り当て char * の配列ではなく 実体を持ったcharの2 次元配列にすること malloc() を2 度使うこと free() すること strdup() は利用禁止 strncpy() を使うこと #include <stdio.h> 2 3 main () 4 { 5 int i, j; 6 char *alpha[] = { "abc", "def", "ghi", "" ; 7 8 for (i = 0; alpha[i][0]; i++) 9 printf (" %s", alpha[i]); 10