INSERT(x,p,L)の例 （一部） 磯 直行 2009年5月5日 ポインタを使った 連結リストの動作 INSERT(x,p,L)の例 （一部） 磯　直行 2009年5月5日

連結リストによる INSERT(x,p,init) NULL ３０ ４０ ５０ x 初期状態 →いまからポインタpが指すセルの次に 変数xの値のセルを追加したい 48

連結リストによる INSERT(x,p,init) NULL ３０ ４０ ５０ temp x セルのメモリを確保(malloc関数を呼び出す） 型変換してセルを構成して（struct cell *を使う) 一時保存用ポインタtempに保存 48

連結リストによる INSERT(x,p,init) NULL ３０ ４０ ５０ temp x pが先頭のポインタかどうかを調べる →ここではinit≠pとして話を進めるが， init=pの場合は各自考えよ 48

連結リストによる INSERT(x,p,init) NULL ３０ ４０ ５０ temp x pが指すセルの次のポインタを tempが指すセルの次のポインタへ代入 →ポインタtempが指すセルの次のセルが同じになる 48

連結リストによる INSERT(x,p,init) NULL ３０ ４０ ５０ temp x pが指すセルの次のポインタを tempが指すセルの次のポインタへ代入 →tempが指すセルとpが指すセルが同じセルを指す 48

連結リストによる INSERT(x,p,init) × NULL ３０ ４０ ５０ temp x tempをポインタpの次のポインタとして代入 →ポインタpの次のセルが変わり， ポインタpの次のセルはtempになる 48

連結リストによる INSERT(x,p,init) NULL ３０ ４０ ５０ temp x 48 48 tempが指すセルにxの値を代入

連結リストによる INSERT(x,p,init) 48 NULL ３０ ４０ ５０ temp 完成！ （横一列に伸ばしてみればよくわかる！） 先頭のポインタinitは変更がないので INSERT関数はinitを返す x 48 保存されているデータ数に関係なく いつも同じ回数の処理で終わって速いぞ！

INSERT(x,p,A)の例 （一部） 磯 直行 2009年5月5日 配列を使った リストの動作 INSERT(x,p,A)の例 （一部） 磯　直行 2009年5月5日

配列による INSERT(x,p,A) p n 4 10 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 初期状態（現在のデータ数n=10個） →いまから変数pに保存された番号のセルの次に値xのセルを追加したい 48

配列による INSERT(x,p,A) p n temp 4 10 10 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 注目するセルの番号を保存する変数tempへnを代入 （n=temp+1となる場所を探す） 48

配列による INSERT(x,p,A) p n temp 4 10 10 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較して配列の最後または途中に追加するのかを判定 →ここではp＝temp+1でないので途中に追加するときを考える （最後に追加するのは容易にできる） x 48

配列による INSERT(x,p,A) p n temp 4 10 9 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 注目するセルを1つ戻す（tempにtemp-1を代入） 48

配列による INSERT(x,p,A) p n temp：いま注目しているセルの番号を 保存している変数 4 10 9 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ０ １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 保存されている最後のセルを1つ後ろへ代入して空きを1つ作る 48

配列による INSERT(x,p,A) p n temp 4 10 9 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（２回目） →p＝temp+1でないので繰り返す x 48

配列による INSERT(x,p,A) p n temp 4 10 8 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 注目するセルを1つ戻す（tempにtemp-1を代入）（２回目） 48

配列による INSERT(x,p,A) p n temp 4 10 8 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x セルを1つ後ろへ代入して空きを1つ移動（３回目） 48

配列による INSERT(x,p,A) p n temp 4 10 8 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（３回目） →p＝temp+1でないので繰り返す x 48

配列による INSERT(x,p,A) p n temp 4 10 7 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 注目するセルを1つ戻す（tempにtemp-1を代入）（３回目） 48

配列による INSERT(x,p,A) p n temp 4 10 7 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x セルを1つ後ろへ代入して空きを1つ移動（３回目） 48

配列による INSERT(x,p,A) p n temp 4 10 7 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（４回目） →p＝temp+1でないので繰り返す x 48

配列による INSERT(x,p,A) p n temp 4 10 6 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 注目するセルを1つ戻す（tempにtemp-1を代入）（４回目） 48

配列による INSERT(x,p,A) p n temp 4 10 6 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x セルを1つ後ろへ代入して空きを1つ移動（４回目） 48

配列による INSERT(x,p,A) p n temp 4 10 6 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（5回目） →p＝temp+1でないので繰り返す x 48

配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x 注目するセルを1つ戻す（tempにtemp-1を代入）（5回目） 48

配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ x ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ x セルを1つ後ろへ代入して空きを1つ移動（5回目） 48

配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（６回目） →p＝tempとなり，挿入位置を発見！ x 48

配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A 48 ･･･ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 完成！ でも，データがたくさんあったら やたら遅いぞ！ x 変数xを配列のtempの場所に代入 48

パラパラマンガにするには １．このパワーポイントを印刷するときに次の設定にして印刷せよ． ・「印刷対象」を「配布資料」に設定 ・「1ページ当たりのスライド」を６～９に設定 （スライドに枠をつけると良い） ２．枠にそってはさみで切り取る． ３．大型クリップで挟んでパラパラマンガ完成