バイオプログラミング第 1 榊原康文 佐藤健吾 慶應義塾大学理工学部生命情報学科
ポインタ変数の扱い方 1 ポインタ変数の宣言 int *p; double *q; 2 ポインタ変数へのアドレスの代入 int *p; と宣言した時,p がポインタ変数 int x; と普通に宣言した変数に対して, p = &x; は x のアドレスのポインタ変数 p への代入
ポインタ変数の扱い方 3 間接参照 ( 演算子 ) * ポインタ変数名 例 ) *p; により, ポインタ変数が指す変数の実体を 間接的 に扱える
データ構造とポインタ 構造体とポインタ 関数とポインタ 配列とポインタ 文字列とポインタ ポインタ配列 ポインタのポインタ 引数付きmain 関数
構造体とポインタ 1 構造体のポインタ変数宣言 : struct 構造体タグ名 * 構造体ポインタ変数名 ; 例 ) struct DATE_DATA { int year; int month; int day; }; struct DATE_DATA today; struct DATE_DATA *pdata;
構造体とポインタ 2 構造体ポインタ変数の参照 代入 : 構造体ポインタ変数名 -> メンバ名 (* 構造体ポインタ変数名 ). メンバ名 と同じ 例 ) pdata=&today; とアドレスを代入した時, today.year (*pdata).year pdata->year
関数とポインタ 1 ポインタと関数引数 : 値による呼び出し (call by value) 変数の値を引数として関数へ渡す 参照による呼出し (call by reference) アドレスを引数として関数へ渡す 関数の引数はポインタでなければならない
#include <stdio.h> int add20(int x); void addp20(int *p); void main(void) { int k, m, n; m=10; n=10; } k=add20(m); addp20(&n); printf( %d %d %d, k, m, n); 30 10 30 int add20(int x) { } x+=20; return x; void addp20(int *p) { } *p+=20;
関数とポインタ 2 ポインタを返す関数戻り値がポインタとなる関数の宣言 関数のデータ型 * 関数名 ( 引数の並び ) 例 ) void main(void) { int *p; p=func(10); } int *func(int x) { int y; y=x+100; return &y; }
リンクによるリスト (linked list) 目的 : ポインタの応用 動的な記憶領域の確保
リンクによるリスト リストは, 配列のような一種のデータ構造 1 リストは, 項目 ( 要素 ) を一列に並べるという点で配列と同じ 2 配列では, 逐次的な構造が ( 配列中の位置によって ) 自然に指定される 3 リストでは, 項目を入れる 節点 の中に次の節点を明示的に指示するリンク ( ポインタ ) を入れて表現する
配列 : char a[5] A L I S T a[0] a[1] a[2] a[3] a[4] リンクによるリスト : A L I S T 節点 リンク
リンクによるリスト 1 リストの先頭の節点を指すダミーの節点を設定して, これを head ( または root) で表すことにする 2 リスト中で最後に位置する節点として, ダミーの節点を設定して, これを tail で表すことにする head tail A B C NULL
C 言語によるリストの実現 準備 1 記号定数 NULL ポインタに対する特別な値であることを示す記号としてゼロの代わりに使われる 2 sizeof 演算子 ( 教科書 p-22) データ型や変数の大きさ ( バイト数 ) を求める演算子 sizeof( 型名または変数名 ) 例 ) sizeof(int) 4 バイト
C 言語によるリストの実現 3 型変換演算子 ( キャスト演算子 ) ( 教科書 p-40) データ型の一時的変換を行う演算子 ( 型 ) ( 変数または式 ) 例 ) (float) 8
C 言語によるリストの実現 4 動的に記憶領域を確保するための標準関数 #include <stdlib.h> malloc ( 記憶領域の大きさ ( バイト数 n) ) n バイトの初期化されていないメモリへのポインタを返す malloc から返されるポインタは, 適当な型に変換されなければならない
C 言語によるリストの実現 5 記憶領域を解放する #include <stdlib.h> free ( 解放する記憶領域を指すポインタ ) 必要の無くなった記憶領域を OS へ返す メモリの無駄をなくす
C 言語によるリストの実現 構造体を使った節点の実現 struct node { int key; struct node *next; }; node key next 自己参照構造体 : 構造体の中に, 自分自身の構造体を参照するメンバを含めることができる
C 言語によるリストの実現 malloc を使った新しい節点の動的な生成 struct node *x; x=(struct node *) malloc(sizeof(*x)); 型変換 標準関数 sizeof 演算子
初期化 head tail struct node *head, *tail; void listinitialize(void) { }; NULL head = (struct node *) malloc(sizeof(* head)); tail = (struct node *) malloc(sizeof(* tail)); head->next = tail; tail->next = NULL;
リスト表現を用いた操作 挿入 削除 参照 節点 ( 要素 ) の並べ変え
挿入 head tail A B C NULL X
挿入 head tail A B C NULL X
挿入 struct node *insertafter(int v, struct node *p) { struct node *x; x = (struct node *) malloc(sizeof(* x)); x->key = v; x->next = p->next; p->next = x; return x; p }; q
挿入 struct node *insertafter(int v, struct node *p) { struct node *x; x = (struct node *) malloc(sizeof(* x)); x->key = v; x->next = p->next; p->next = x; return x; p x }; v q
削除 void deletenext(struct node *p) { struct node *x; x = p->next; p->next = p->next->next; free(x); }; p v x q
削除 void deletenext(struct node *p) { struct node *x; x = p->next; p->next = p->next->next; free(x); }; p q v
削除 void deletenext(struct node *p) { struct node *x; x = p->next; p->next = p->next->next; free(x); }; p q
参照 k 番目の要素 ( 節点 ) の値を参照 リストでは,head からリンクをたどっていくしかない (k ステップかかる ) 配列では,1 ステップ, すなわち a[k] ですむ
配列 : char a[5] A L I S T a[0] a[1] a[2] a[3] a[4] リンクによるリスト : A L I S T
参照 head tail A B C struct node *x; NULL x = head; while(x->next->next!= NULL) { x = x->next; printf("%d ", x->key); };
節点の並べ変え ポインタのつけかえのみ head tail A B C 例 ) C をリストの末尾から先頭へ移動 NULL
節点の並べ変え ポインタのつけかえのみ head tail A B C NULL
節点の並べ変え ポインタのつけかえのみ head tail A B C NULL
節点の並べ変え ポインタのつけかえのみ head tail A B C NULL 3 つのポインタのつなぎ変え
今日の課題 課題 1 授業中に紹介した linked list のプログラムを完全なプログラムにしなさい main 関数の中で scanf を使って数字を読み込むこと
今日の課題 課題 2 課題 1 で作成したプログラムに 登録した値すべてを表示する機能を追加しなさい
今日の課題 課題 3( 発展課題 ) 課題 2 で作成したプログラムに 登録した値が小さい順にソートする機能を追加しなさい
考察で期待すること linked list の挿入や削除を理解する 各ステップにおけるリストの状態を表示してみる etc