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

他スレッドで単方向リスト問題が分かりやすかったので便乗でお願いします。

  関数oSerachは、引数keyで与えられた文字を単方向リストから探索し、一致する要素が見つかれば、その要素をリストの先頭に移動して、要素の値を返す。見つからなければ-1を返す。
  単方向リストの要素はNodeを用いて表現する。Node型の変数は、クラスNodeのインスタンスの参照を格納するものとする。大域変数firstには、プログラムで扱う単方向リストの先頭要素の参照があらかじめ格納されているものとする。

メンバ変数
next    Node型    次の要素の参照

次の要素がないときの状態は未定義
key       文字型     要素に格納する文字
value    整数型     要素に格納する正の整数値

  first
＋ーーー＋  +ーー＋-ーー＋ーー＋-ーー＋-ーー＋
｜      ｜→｜next｜next｜next｜next｜next｜
＋ーーー＋  +ーー＋-ーー＋ーー＋-ーー＋-ーー＋
               ｜   A ｜  B   |   C ｜  D   |   E   |
            ＋ーー＋-ーー＋ーー＋-ーー＋-ーー＋
            ｜  4  ｜ 10  |  17 ｜  9   |   5   |
            ＋ーー＋-ーー＋ーー＋-ーー＋-ーー＋
関数oSerchをoSerchとして呼び出すと、戻り値は17である。

大域：Node:first  /*リストの先頭要素の参照が格納されている*/

〇整数型：oSerch(文字型:key)
Node: current, temp
current ← first
while(current が 未定義でない)
    if(key が current.keyと等しい)
      if(current が first と等しくない)  
          temp.next ← current.next
        current.next ← first
        first ← current
      endif
        return current.value
    else
        temp ← current
        current ← current.next
    endif
endwhile
return -1

①二つ目のifからなんですが、一つ目のifが(key が current.keyと等しい)となってるのに、二つ目のifはなぜ(key が current.keyと等しくない)にはならないのでしょうか？first はcurrentを参照してるはずで(current が first と等しくない)の意味が分かりません。

②temp.next に current.nextを入れてやるとBだと思うのですが箱が変わっただけで参照先は変わらないのではないかと思うのですが、参照先を書き換えるだけでいいはずのリストのはずなのに、tempの働きが分かりません。

③この場合のtempは key と current.key が等しくなるまで何個もあるのでしょうか。

④current.next ← firstで二番目の要素Bを先頭にしてあげてると思うのですが、次の
first ← currentで後戻りしてる意味が不明。

よろしくお願いします

誤×  関数oSerchをoSerchとして呼び出すと、戻り値は17である。
正○  関数oSerchをoSerch('C')として呼び出すと、戻り値は17である。

説明上、単方向リストの要素の格納アドレスを 1111,2222,3333,4444,5555 とすると次の図のようになる。（以下、未定義とNULLを同じ概念として用います）

なので、currentはwhileループのたびに、
1111→2222→3333→4444→5555→未定義と変化する。

tempは、次のURLのスレッドのNo.6で述べた
https://www.fe-siken.com/bbs/5644.html
> 変数名prevは，英単語previous「順序が一つ前の，以前の」に由来しています。
という役割の変数なので、whileループのたびに、
未定義→1111→2222→3333→4444→5555と変化する。

なので、

(ア) oSerch('A') つまり リストの先頭が一致する文字だった場合は、
     要素の移動処理はまったくおこなわず、'A'に対応するvalueを返すだけ
なのに対して、
(イ) oSerch('B')、oSerch('C')、oSerch('D')、oSerch('E') の場合、
     つまり リストの先頭以外で一致する文字を見つけた場合は、
     currentが指す要素をリストの先頭に移動する処理をおこない、
     さらに、その文字に対応するvalueを返す
ことになる。
だから、

関連スレッド:
単方向リストの問題について
https://www.fe-siken.com/s/bbs/5644.html

単方向リストの問題について2
https://www.fe-siken.com/s/bbs/5645.html

> 関数oSerchをoSerchとして呼び出すと、戻り値は17である。

ここはoSearch(‘C’)の間違いでしょうか？

上記のように記載してくれていますが、これはリストが
（※valueは省略しています）
のように繋がっていることを表現しているのでしょうか？スレ主さんのリストの表現だと、配列と同じようにクラスNodeのインスタンス用のメモリが配列と同じように、連続した場所に確保されているように誤解が生じてしまうおそれが高いように感じます。実際は、Nodeクラスのアドレスはメモリに点在しています。リスト構造は、メンバ変数nextに次の要素のアドレスを格納することで、まるで連続している要素かのように見せかけているだけです。要するに、物理的にはNodeクラスのインスタンスは離れた位置に存在するが、論理的には近い位置に存在するということです。

>①二つ目のifからなんですが、一つ目のifが(key が current.keyと等しい)となってるのに、二つ目のifはなぜ(key が current.keyと等しくない)にはならないのでしょうか？first はcurrentを参照してるはずで(current が first と等しくない)の意味が分かりません。

１つ目のif文の目的が「値を探索する」
２つ目のif文の目的が「探索する値を持つリストの要素を先頭に付け替える」です。

> ②temp.next に current.nextを入れてやるとBだと思うのですが箱が変わっただけで参照先は変わらないのではないかと思うのですが、参照先を書き換えるだけでいいはずのリストのはずなのに、tempの働きが分かりません。

変数tempは、英単語temporary（意味:一時的な）に由来しています。tempはよく登場する変数名で、値の避難場所的な働きをします。例えば、変数aとbの値を入れ替えるコードが以下です。
変数tempを使わない場合、変数aに10が入っていた情報が失われてしまうため、一時的に変数tempに10を退避させています。

> ③この場合のtempは key と current.key が等しくなるまで何個もあるのでしょうか。

変数tempは一つだけです。whileループの度に次々と値が更新されていきますが、変数tempの数は増えていません。Excelファイルでいうところの、「名前をつけて保存」ではなく、「上書き保存」をしている感じです。

> ④current.next ← firstで二番目の要素Bを先頭にしてあげてると思うのですが、次の
first ← currentで後戻りしてる意味が不明。

keyが’C’である要素をリストの先頭要素にしています。

No.2で提示した説明図において、文字'C'をリスト中に発見した時点がこちら。
currentは'C'を発見した要素のアドレス、tempはその一つ前の要素のアドレス。

> (イ) oSerch('C') の場合、
> つまり リストの先頭以外で一致する文字を見つけた場合は、
> currentが指す要素をリストの先頭に移動する処理をおこない、
をおこなって、
first→'A'→'B'→'C'→'D' が
first→'C'→'A'→'B'→'D' になった図がこちら。

★1 を先、★3 を後に実行すると、
★3 で上書きするための 1111 が ★1 の実行によって消えてしまう。
よって正しい実行順は、★3 が先、★2 が後。

★3 を先、★2 を後に実行すると、
★2 で上書きするための 4444 が ★3 の実行によって消えてしまう。
よって正しい実行順は、★2 が先、★3 が後。

以上より、正しい実行順は、

jjon-comさん、まーぼさん、ありがとうございました。
脱字、脱表には気づいたのですが的確なご指摘そのとおりです。

理解できました。言ってる通りの動きにしたかったのですが、tempが次の要素次の要素へと参照先を移動してるように思えて仕方ありませんでした。
ポインターはあくまでnextであとは配列の入れ替えと同じということですね。
すぐ二番目のifに行ってしまったのが敗因でした。
これだと当該の要素が先頭以外はfirstとcurrentは一致しないですね。よくわかりました。

この投稿は投稿者により削除されました。(2024.10.14 08:29)