ポインタを使った 連結リストの動作 INSERT(x,p,L)の例 （一部） 磯 直行 2009年5月5日 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ ５０ NULL 初期状態 →いまからポインタpが指すセルの次に 変数xの値のセルを追加したい 2 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ ５０ NULL temp セルのメモリを確保(malloc関数を呼び出す） 型変換してセルを構成して（struct cell *を使う) 一時保存用ポインタtempに保存 3 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ ５０ NULL temp pが先頭のポインタかどうかを調べる →ここではinit≠pとして話を進めるが， init=pの場合は各自考えよ 4 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ ５０ NULL temp pが指すセルの次のポインタを tempが指すセルの次のポインタへ代入 →ポインタtempが指すセルの次のセルが同じになる 5 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ ５０ NULL temp pが指すセルの次のポインタを tempが指すセルの次のポインタへ代入 →tempが指すセルとpが指すセルが同じセルを指す 6 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ × ５０ NULL temp tempをポインタpの次のポインタとして代入 →ポインタpの次のセルが変わり， ポインタpの次のセルはtempになる 7 連結リストによる INSERT( x,p,init ) p init ３０ x 48 ４０ ５０ NULL temp 48 tempが指すセルにxの値を代入 8 連結リストによる INSERT( x,p,init ) p init ３０ x 48 48 ４０ temp 完成！ 保存されているデータ数に関係なく いつも同じ回数の処理で終わって速いぞ！ ５０ NULL （横一列に伸ばしてみればよくわかる！） 先頭のポインタinitは変更がないので INSERT関数はinitを返す 9 配列を使った リストの動作 INSERT(x,p,A)の例 （一部） 磯 直行 2009年5月5日 配列による INSERT(x,p,A) p n 4 10 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ ･･･ 11 48 初期状態（現在のデータ数n=10個） →いまから変数pに保存された番号のセルの次に値xのセルを追加したい 配列による INSERT(x,p,A) p n temp 4 10 10 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 注目するセルの番号を保存する変数tempへnを代入 （n=temp+1となる場所を探す） ･･･ 12 配列による INSERT(x,p,A) p n temp 4 10 10 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ ･･･ pとtempと比較して配列の最後または途中に追加するのかを判定 →ここではp＝temp+1でないので途中に追加するときを考える 13 （最後に追加するのは容易にできる） 配列による INSERT(x,p,A) p n temp 4 10 9 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 注目するセルを1つ戻す（tempにtemp-1を代入） ･･･ 14 配列による INSERT(x,p,A) p n 4 10 temp：いま注目しているセルの番号を 9 保存している変数 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 保存されている最後のセルを1つ後ろへ代入して空きを1つ作る ･･･ 15 配列による INSERT(x,p,A) p n temp 4 10 9 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（２回目） →p＝temp+1でないので繰り返す ･･･ 16 配列による INSERT(x,p,A) p n temp 4 10 8 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 注目するセルを1つ戻す（tempにtemp-1を代入）（２回目） ･･･ 17 配列による INSERT(x,p,A) p n temp 4 10 8 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ セルを1つ後ろへ代入して空きを1つ移動（３回目） ･･･ 18 配列による INSERT(x,p,A) p n temp 4 10 8 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（３回目） →p＝temp+1でないので繰り返す ･･･ 19 配列による INSERT(x,p,A) p n temp 4 10 7 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 注目するセルを1つ戻す（tempにtemp-1を代入）（３回目） ･･･ 20 配列による INSERT(x,p,A) p n temp 4 10 7 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ セルを1つ後ろへ代入して空きを1つ移動（３回目） ･･･ 21 配列による INSERT(x,p,A) p n temp 4 10 7 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（４回目） →p＝temp+1でないので繰り返す ･･･ 22 配列による INSERT(x,p,A) p n temp 4 10 6 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 注目するセルを1つ戻す（tempにtemp-1を代入）（４回目） ･･･ 23 配列による INSERT(x,p,A) p n temp 4 10 6 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ セルを1つ後ろへ代入して空きを1つ移動（４回目） ･･･ 24 配列による INSERT(x,p,A) p n temp 4 10 6 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（5回目） →p＝temp+1でないので繰り返す ･･･ 25 配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ 注目するセルを1つ戻す（tempにtemp-1を代入）（5回目） ･･･ 26 配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ セルを1つ後ろへ代入して空きを1つ移動（5回目） ･･･ 27 配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ x 48 １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ pとtempと比較（６回目） →p＝tempとなり，挿入位置を発見！ ･･･ 28 配列による INSERT(x,p,A) p n temp 4 10 5 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ A ０ １０ ２０ ３０ ４０ 48 ５０ ６０ ７０ ８０ ９０ x 48 変数xを配列のtempの場所に代入 ･･･ 完成！ でも，データがたくさんあったら やたら遅いぞ！ 29 パラパラマンガにするには １．このパワーポイントを印刷するときに次の設 定にして印刷せよ． ・「印刷対象」を「配布資料」に設定 ・「1ページ当たりのスライド」を６～９に設定 （スライドに枠をつけると良い） ２．枠にそってはさみで切り取る． ３．大型クリップで挟んでパラパラマンガ完成 30
© Copyright 2024 ExpyDoc
![[Vol.56] Shinwasorb を用いた保存料の分析例](http://s1.expydoc.com/store/data/006013954_1-dc10b3259c3f299f37f009dc63e68ef7-250x500.png)
