INSERT(x,p,L)の例 （一部） 磯 直行 2009年5月5日

Presentation on theme: "INSERT(x,p,L)の例 （一部） 磯 直行 2009年5月5日"— Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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