スライド

バイオプログラミング第２
榊原 康文、佐藤 健吾
慶應義塾大学理工学部 生命情報学科
ポインタ変数の扱い方
① ポインタ変数の宣言
ｉｎｔ ＊ｐ；
ｄｏｕｂｌｅ ＊ｑ；
② ポインタ変数へのアドレスの代入
ｉｎｔ ＊ｐ；
と宣言した時，ｐ がポインタ変数
ｉｎｔ ｘ；
と普通に宣言した変数に対して，
ｐ ＝ ＆ｘ；
はｘのアドレスのポインタ変数
ｐへの代入
ポインタ変数の扱い方
③ 間接参照（演算子）
＊【ポインタ変数名】
例） ＊ｐ；
により，ポインタ変数が指す変数の実体を
「間接的」に扱える
データ構造とポインタ
構造体とポインタ
n 関数とポインタ
n 配列とポインタ
n 文字列とポインタ
n ポインタ配列
n ポインタのポインタ
n 引数付きｍａｉｎ関数
n
構造体とポインタ
①構造体のポインタ変数宣言：
ｓｔｒｕｃｔ 【構造体タグ名】 ＊【構造体ポインタ変数名】；
例） struct DATE_DATA
{
int year;
int month;
int day;
};
struct DATE_DATA ｔｏｄａｙ;
struct DATE_DATA ＊pdata;
構造体とポインタ
②構造体ポインタ変数の参照・代入：
【構造体ポインタ変数名】->【メンバ名】
（＊【構造体ポインタ変数名】）.【メンバ名】 と同じ
例）
pdata=&today; とアドレスを代入した時，
today.year ⇔ (＊pdata).year
⇔ pdata->year
関数とポインタ
①ポインタと関数引数：
「値による呼び出し (call by value)」
変数の値を引数として関数へ渡す
「参照による呼出し (call by reference)」
アドレスを引数として関数へ渡す
関数の引数はポインタでなければならない
#include <stdio.h>
int add20(int x);
int add20(int x)
{
x+=20;
return x;
}
void addp20(int *p);
void main(void)
{
int k, m, n;
m=10; n=10;
void addp20(int *p)
k=add20(m);
{
addp20(&n);
printf(”%d %d %d”, k, m, n);
}
30 １0 ３0
*p+=20;
}
関数とポインタ
②ポインタを返す関数
戻り値がポインタとなる関数の宣言
【関数のデータ型】 *【関数名】 （【引数の並び】）
例）
void main(void)
{
int *p;
p=func(10);
}
int *func(int x)
{
int y;
y=x+100;
return &y;
}
リンクによるリスト（linked list）
目的：
ポインタの応用
n 動的な記憶領域の確保
n
リンクによるリスト
n
リストは，配列のような一種のデータ構造
①リストは，項目（要素）を一列に並べるという点
で配列と同じ
②配列では，逐次的な構造が（配列中の位置に
よって）自然に指定される
③リストでは，項目を入れる「節点」の中に次の節
点を明示的に指示するリンク（ポインタ）を入れて
表現する
配列：
ｃｈａｒ ａ［５］
Ａ
Ｌ
Ｉ
Ｓ
Ｔ
ａ［０］
ａ［１］
ａ［２］
ａ［３］
ａ［４］
リンクによるリスト：
Ａ
節点
Ｌ
Ｉ
Ｓ
リンク
Ｔ
リンクによるリスト
①リストの先頭の節点を指すダミーの節点を設定して，
これを「ｈｅａｄ」 （またはｒｏｏｔ）で表すことにする
②リスト中で最後に位置する節点として，ダミーの節点を
設定して，これを「ｔａｉｌ」で表すことにする
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
Ｃ言語によるリストの実現
n
準備
①記号定数 ＮＵＬＬ
ポインタに対する特別な値であることを示す記号
としてゼロの代わりに使われる
② ｓｉｚｅｏｆ 演算子 （教科書ｐ－２２）
データ型や変数の大きさ（バイト数）を求める演算子
ｓｉｚｅｏｆ（【型名または変数名】）
例） ｓｉｚｅｏｆ（ｉｎｔ）
４バイト
Ｃ言語によるリストの実現
③型変換演算子 （キャスト演算子） （教科書ｐ－４０）
データ型の一時的変換を行う演算子
（【型】） （【変数または式】）
例） （ｆｌｏａｔ） ８
Ｃ言語によるリストの実現
④動的に記憶領域を確保するための標準関数
#include <stdlib.h>
ｍａｌｌｏｃ （【記憶領域の大きさ（バイト数 ｎ）】）
lｎバイトの初期化されていないメモリへのポインタ
を返す
lｍａｌｌｏｃから返されるポインタは，適当な型に変換
されなければならない
Ｃ言語によるリストの実現
⑤記憶領域を解放する
#include <stdlib.h>
ｆｒｅｅ （【解放する記憶領域を指すポインタ】）
l必要の無くなった記憶領域をＯＳへ返す
lメモリの無駄をなくす
Ｃ言語によるリストの実現
n
構造体を使った節点の実現
ｓｔｒｕｃｔ ｎｏｄｅ
{
ｉｎｔ ｋｅｙ；
ｓｔｒｕｃｔ ｎｏｄｅ *ｎｅｘｔ；
}；
ｎｏｄｅ
ｋｅｙ
ｎｅｘｔ
自己参照構造体：
構造体の中に，自分自身の構造体を参照するメンバを
含めることができる
Ｃ言語によるリストの実現
n
ｍａｌｌｏｃを使った新しい節点の動的な生成
ｓｔｒｕｃｔ ｎｏｄｅ *ｘ；
ｘ＝（ｓｔｒｕｃｔ ｎｏｄｅ *） ｍａｌｌｏｃ（ｓｉｚｅｏｆ（*ｘ））；
型変換
標準関数 ｓｉｚｅｏｆ演算子
n
初期化
ｈｅａｄ
ｔａｉｌ
struct node *head, *tail;
void listinitialize(void)
ＮＵＬＬ
{
head = (struct node *) malloc(sizeof(* head));
tail = (struct node *) malloc(sizeof(* tail));
head->next = tail;
tail->next = NULL;
};
リスト表現を用いた操作
挿入
n 削除
n 参照
n 節点（要素）の並べ変え
n
挿入
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
Ｘ
挿入
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
Ｘ
n 挿入
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;
ｐ
ｑ
};
n 挿入
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;
ｐ
ｘ
ｑ
};
ｖ
n 削除
void deletenext(struct node *p)
{
struct node *x;
x = p->next;
p->next = p->next->next;
free(x);
};
ｐ
ｘ
ｖ
ｑ
n 削除
void deletenext(struct node *p)
{
struct node *x;
x = p->next;
p->next = p->next->next;
free(x);
};
ｐ
ｑ
ｖ
n 削除
void deletenext(struct node *p)
{
struct node *x;
x = p->next;
p->next = p->next->next;
free(x);
};
ｐ
ｑ
n 参照
ｋ番目の要素（節点）の値を参照
l リストでは，ｈｅａｄからリンクをたどっていくしかない
（ｋステップかかる）
l 配列では，１ステップ，すなわち ａ［ｋ］ ですむ
配列：
ｃｈａｒ ａ［５］
Ａ
Ｌ
Ｉ
Ｓ
Ｔ
ａ［０］
ａ［１］
ａ［２］
ａ［３］
ａ［４］
リンクによるリスト：
Ａ
Ｌ
Ｉ
Ｓ
Ｔ
n
参照
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
struct node *x;
x = head;
while(x->next->next != NULL)
{
x = x->next;
printf("%d ", x->key);
};
n 節点の並べ変え
ポインタのつけかえのみ
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
例） Ｃをリストの末尾から先頭へ移動
n 節点の並べ変え
ポインタのつけかえのみ
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
n 節点の並べ変え
ポインタのつけかえのみ
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
n 節点の並べ変え
ポインタのつけかえのみ
ｈｅａｄ
ｔａｉｌ
Ａ
Ｂ
Ｃ
ＮＵＬＬ
３つのポインタのつなぎ変え
今日の課題
■
課題１
– 授業中に紹介したlinked listのプログラ
ムを完全なプログラムにしなさい。main
関数の中でscanfを使って数字を読み込
むこと。
今日の課題
■
課題２
– 課題１で作成したプログラムに、登録し
た値すべてを表示する機能を追加しなさ
い。
今日の課題
■
課題３（発展課題）
– 課題２で作成したプログラムに、登録し
た値が小さい順にソートする機能を追加
しなさい。
考察で期待すること
■
linked listの挿入や削除を理解する
– 各ステップにおけるリストの状態を表示
してみる etc