基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

ある参考書の問題で
□に入る字句を考えよ
List:pre,follow
follow←first
pre←follow
while(follow.nextが未定義でない)
pre←follow
follow←follow.next
endwhile
□←未定義の値
という問題があり、答えがpre.nextだったのですが、followではだめなのでしょうか？よろしくお願いいたします。

一応追記、リスト構造の末尾の要素を削除するプログラムの問題です。

どちらでもよいのではないでしょうか。

参考程度にjavaで書くと以下のようなコードになると思います。
このままだと回答のpre.next←未定義の値で
follow.remove()の行のコメントアウトを外して上の2行をコメントアウトすると、follow←未定義の値にした処理になります。
どちらも同じくリストの末尾を削除できます。

ありがとうございます。やっぱりfollowでもいいですよね。
続けて質問してしまい申し訳ないのですが、
下記の２分探索木から目的データを探索するプログラムの中にある変数tはインスタンスと呼んでいいのでしょうか？よろしくお願いいたします。

文字列型:lookup(Tree: t,整数型:data)
while(tが未定義でない)
if(data=t.value)
return "data is detected."
elseif(data<t.value)
t←t.left /*左の子へ移動*/
else
t←t.right /*右の子へ移動*/
endif
endwhile
return "data is not detected."

クラスTree のメンバ変数
メンバ変数 型 説明
value 整数型 節に格納する数値
left Tree 左の子の「参照」。左の子がないときは未定義。
right Tree 右の子の「参照」。右の子がないときは未定義。

追記  tabがスペースに変換されたので

クラスTree のメンバ変数
-----------------------------------------------------------------------
|メンバ変数    |型         |説明                                         |
-----------------------------------------------------------------------

|value         |整数型      |節に格納する数値                            |
-----------------------------------------------------------------------

|left          |Tree        |左の子の「参照」。左の子がないときは未定義。|
-----------------------------------------------------------------------

|right         |Tree        |右の子の「参照」。右の子がないときは未定義。|
-----------------------------------------------------------------------

クラスTreeのフィールドを利用できているので、広くいえばインスタンスと言えるのかも知れませんが、tは仮引数なのでt自体をインスタンスと呼ぶことは少ないかも知れません。もちろん実際に呼び出すときはメソッドの引数にクラスTreeのインスタンスを指定するので、その場合はインスタンスと呼べると思います。

#間違っていたら申し訳ないですが、科目Bでこのことが問われることはないと思います。

No.1ですが、参照先か変数のどちらを代入したか？の問題となっていると思うので、pre.nextが正解でfollowは不正解だと思います。

ちょっと難しい概念なのでうまく伝わるかわかりませんが・・・

・代入の考えはその瞬間に一緒のものになります。
自動販売機の例であれば、現在設置している自動販売機を捨てて新しい自動販売機に置き換えます。

・参照（今回であれば.nextの部分）なにかの中身と考えてください。
自動販売機の中身をいじっても、基本的には前の自動販売機のままです。

２つの事例で結果自動販売機は設置されていますが、もともとの自動販売機にお金が入っていた場合どうなるでしょう？
前者の代入では入っているお金そのものも全部入れ替わっています。
後者の参照では入っていたお金が変えられていないのであればそのままのハズです。

双方リストの参照でスタートしているpre,followで考えると
・followという場所に直接新品の未定義を設置したらもともとの自動販売機の情報の連鎖とは別物の場所が未定義に変えられます。
・pre.nextという一部を変更すると自動販売機の情報の連鎖の最後を未定義に変化させた事になります。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

リアル言語で記載するとこんな感じになります。
String[]a = {"A", "B", "C"};
String[]b = a;
この時点でbとaは同一。

パターン１：「参照」代入が変数bそのものではなく、変数bが指している先[2]。（今回で言えば.nextのようなもの）
b[2] = "未定義"; // aの内容も{"A", "B", "未定義"}になる

パターン２：「代入」代入が変数bそのもの。
b = new String[]{"未定義"};// 変数bとaの関係は別物となる。
                          // aとbは別物となっているので、aの内容は{"A", "B", "C"}のまま

まーぼさん
助かります。

まーぼさん、電タックさんお答えいただき、ありがとうございます。
電タックさんに追加で質問させていただきたいのですが、pre.nextが正解でfollowは不正解というのは、No.1のプログラムの□の部分にpre.nextではなく、followをいれるとプログラムそのものがリスト構造の末尾の要素を削除するという動きをしないものになるということなのでしょうか？
ちなみに参考書の問題の出され方としては、pre.nextとfollowを含む選択肢の中から選ぶというような形式ではなく、□の中に入る文字列を考えなさいというような形式の問題になります。あと、記載し忘れていましたが、プログラムの前に「変数firstにはリストの先頭の要素の「参照」が格納されているとする」という文言がありました。よろしくお願いいたします。

正答は pre.next であり，follow は誤答です。

> プログラムの前に「変数firstにはリストの先頭の要素の「参照」が
> 格納されているとする」という文言がありました。（No.9）
というヒントと No.1 から読み取れるデータ構造は次のようになると考えます。

物理的に連続した一次元配列のイメージでイラストにしましたが，
連結リスト構造なので物理的に連続している必要はありません。
（テキストエディタなどにコピーして等幅フォントで見てください）


上図より，pre.next←NULL と follow←NULL は異なります。

>No.1のプログラムの□の部分にpre.nextではなく、followをいれるとプログラムそのものがリスト構造の末尾の要素を削除するという動きをしないものになるということなのでしょうか？

そうなると思います。

> 変数firstにはリストの先頭の要素の「参照」が格納されているとする

単方向リストでよく行われる操作です。
下記例であればpre(４)から５に行くnextはあるが３や２に戻る術が無いリストで、戻る方法が無いとあまりにも使いにくいので先頭の状態を取っておいて居るというわけです。


文字だけだとわかりにくくなると思うので、以下のリストがあるとします。
[I]Firstの事
[P]reの事
[F]ollowの事
｛１，２，３，４，５｝
＿Ｉ，＿＿＿＿Ｐ，Ｆ（５）
この状態でpre.next（参照：No.7参考）は４から５に向けての部分で、それを５から未定義にしたい。とした場合リスト全体は下記となります。
｛１，２，３，４，未定義｝
＿Ｉ，＿＿＿＿Ｐ，Ｆ（５）
が、Followは５から未定義になるわけではなく５のままです。
リストの連鎖から外されてもFollowも５は生き残ります。
がその５にたどり着く術が存在しない→事実上消えたというわけです。

次に
[I]Firstの事
[P]reの事
[F]ollowの事
｛１，２，３，４，５｝
＿Ｉ，＿＿＿＿Ｐ，Ｆ（５）←未定義
この状態でFollowは５を設置した場所（代入）です。その場所を別の未定義に設置し直した（再代入）場合、１&#12316;５のリスト内部の操作ではなく代入のため無関係の所で値が変更されたとなります。（代入：No.7参考）

文字が見にくかったため最後の部分だけ。

この状態でFollowは５を設置した場所（代入）です。その場所を別の未定義に設置し直した（再代入）場合、１から５のリスト内部の操作ではなく代入のため無関係の所で値が変更されたとなります。（代入：No.7参考）

電タックさん、jjon-comさん

訂正いただきありがとうございます。

またB太さんも混乱を招く回答をしてしまい申し訳ないです。

皆さんがおっしゃっているようにpre.nextが正しいですね。

皆様丁寧に教えてくださりありがとうございます。
重ねて質問してしまい申し訳ないのですが、３つ質問があります。
・No.1のプログラムの最後の部分で、変数followに未定義の値を代入することと、変数preに代入されているリスト構造の要素のポインタ部が指す何かが未定義になることは別という理解はあっていますでしょうか？
・自動販売機の例でいうとリスト構造の１つの要素のポインタ部は自動販売機そのものを指しているのではなく、自動販売機のなかの一部を指しているという理解であっていますでしょうか？
・No.1のプログラムの変数followやpreはリスト構造の要素のデータ部及びポインタ部両方を含んでいるという理解はあっていますでしょうか？
よろしくお願いいたします。

> ・No.1のプログラムの最後の部分で、変数followに未定義の値を代入することと、変数preに代入されているリスト構造の要素のポインタ部が指す何かが未定義になることは別という理解はあっていますでしょうか？

そうなります。
参照型の変数にはクラスのインスタンスのアドレスが格納されていると思うと分かりやすいと思います。

whileのループが終了するとpreはリストの要素の最後から2番目、followは最後の要素のアドレスが入ってくることになります。

リストの最後から2番目の要素が”A000”、最後の要素が”A060”にあるならば

preにはA000、followにはA060が入っています。

pre.nextに未定義の値を代入すると、preの次の要素への参照ができなくなる(＝連結リストからなくなる）ということになります。
一方、followに未定義の値を代入するとfollowが何も参照できなくなる（=followが連結リストの最後の要素を指さなくなっただけで、連結リスト自体には何も影響を与えていない）。

> ・No.1のプログラムの変数followやpreはリスト構造の要素のデータ部及びポインタ部両方を含んでいるという理解はあっていますでしょうか？

一般的にはリストの要素はデータを格納する部分と次の要素への参照を格納する部分があるのですが、この問題ではデータを格納する部分にあたるメンバ変数が見当たらないように思います。

参照型の変数がデータ部やポインタ部を持つというよりも、参照型にはデータ部やポインタ部をもつインスタンスのアドレスが入っているという認識の方がいいと思います。

>・No.1のプログラムの最後の部分で、変数followに未定義の値を代入することと、変数preに代入されているリスト構造の要素のポインタ部が指す何かが未定義になることは別という理解はあっていますでしょうか？

あってます。

色々記載しましたが、参照を受け取った変数が直接に変化したか？
で大元に影響が波及したかで見て貰えればと思ってます。
・変数(followは）が直接かわってしまった。
follow←代入
※大元のリストとは別の扱い。
・変数(preは)が直接変わっていない。
pre.next←代入
※大元のリストに影響する変化。

>・自動販売機の例でいうとリスト構造の１つの要素のポインタ部は自動販売機そのものを指しているのではなく、自動販売機のなかの一部を指しているという理解であっていますでしょうか？

コレは私の説明がうまく出来ていないものと思われます。
自動販売機の例は、「代入」と「参照の変更・代入」の違いを説明したかったので出していました。

なので自動販売機１個がリスト全体ではなく、リストの何処かの参照という意味で使っていました。

>・No.1のプログラムの変数followやpreはリスト構造の要素のデータ部及びポインタ部両方を含んでいるという理解はあっていますでしょうか？

No.5の様に
List
value：値
next：次の要素へのポインタ
と示せるものが無いのでおそらくという回答になりますが、その理解であっていると思います。

皆様の丁寧な説明のおかげで、リスト構造への理解が深まった気がします。改めまして皆様ありがとうございました。