2022年4月25日公開分：科目Bサンプル  問3  単方向に追加するプログラムの問題について

基本的な問題で恐縮なのですが、疑似言語について、
設問の答えではなく、文法的な部分を詳しく理解しようとしていてわからない部分があるので質問させてください。

「単方向リストの各要素は，クラス ListElement を用いて表現する。クラス ListElement の説明を図に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead は，単方向リストの先頭の要素の参照を格納する。（略）

  ListElement:prev,curr
  curr ←ListElement(qVal)
  if (listHaed [  a  ])
    listHead  ←  curr  
  else   」

ListElement:prev,curr  の部分は、
ListElement型の変数prev  は要素番号（アドレス）/（prev.nextで次を示すポインタに）
ListElement型の変数curr  は要素（追加したい文字）  を入れるものではないのでしょうか？  

変数qVal（文字型）をcurrに入れているので、currは文字型の変数だと思ったのですが、if中で、先頭の要素のポインタの変数listHeadにcurrを入れているように見え、
アドレス（番号）に文字を入れる？？  と混乱してしまいました。

そもそも「listHead  ←  curr」がcurr（の中身＝文字）をlistHeadに入れる、という意味ではなかったりしますか？

問の解くにはあまり関係のない部分かもしれませんが、なにとぞよろしくお願いいたします。

>ListElement:prev,curr
型：変数名
の解釈はおおよそ記載の内容で合ってます。
また一旦変数が作られたら処理の途中で型が変更されることは通常無いと思ってください。
※型の変更に一部例外的な操作で基本情報ででてくる用語ポリモーフィズムがありますが基本情報の擬似言語ではおそらくでてこないので用語の理解だけでいいと思ってます。

>curr ←ListElement(qVal)
の解釈が少し違っていると思われます。
１．まず←（代入）をする場合、型は一緒でないといけません。
※左辺（curr）がListElement型で、右辺が文字列型ということはありえないということになります。

２．つぎに、ListElement(qVal)の動きですが、クラス名（）と記述された場合、クラスのコンストラクタが呼ばれます。
コンストラクタの説明によれば、引数qValの値でメンバ変数valが初期化されるとなってます。

通常の変数型に比べオブジェクトは箱で表現されたりしていて
ListElementという箱の中に、メンバ変数の文字列valが潜んでいるという状態です。

結果として内部にqvalの文字列で初期化されたvalを保持している、
>ListElementのcurr
が作られるということになります。

curr自体はListElement型のままなのでその後の疑問はなくなると思われます。

>問の解くにはあまり関係のない部分かもしれませんが、
オブジェクトは初めは難しい部分ではありますがそこまで複雑でもないのでゆっくりでも確実モノにしていければすぐ理解できると思います。

頑張ってください。

コメントありがとうございます。

>>curr ←ListElement(qVal)
>の解釈が少し違っていると思われます。
>１．まず←（代入）をする場合、型は一緒でないといけません。
とのことですが、
例えば、ListElement型の変数prevはあくまでもListElement型であって整数型ではないのでしょうか？  
ListElement型であり整数型、のようになっているのかと思っていたのですが、javaで言うObject型のようななんでも型になっているのでしょうか？

>２．つぎに、ListElement(qVal)の動きですが
ListElementというvalとprevとprev.nextの3つセットがいくつか並んでいるリストがあり、
「ListElement(qVal)がvalをqVal（文字）で上書きする」という処理をcurrに対して行うことで、新しい要素としてqValが入ったcurrを作ることができる
この時はcurrとセットになっているprevは未定義、currはリストの末尾となっている。
else以下の部分はprevを設定していく部分
リストのcurrのひとつ前のポインタprev.nextがcurrのprevと等しいので、prev.nextが未定義のval、つまりcurrまでたどる。ここでwhileを抜ける
……とこのような流れだと思っているのですが、

そしてまた
「prev.next ← curr」[ b ]欄の部分で
prev.nextはポインタなのに、currを代入？？  と最初の疑問に戻ってしまいます。
currには要素（文字）のほかにアドレスとなるデータ（整数？）も持っているのでしょうか？
currの要素（文字）を直接ポインタとして扱ってる？
そもそもcurrは「リストのどこに追加するか」という入力ができるようになってないと思うので、末尾に追加しているのだと思うのですが、末尾ならcurrのpre.nextは未定義となるのでは？  
と、currがどんな状態・どんな属性になっているのかわからなくて困っています。

すみません、一部おかしいことを書いてたので訂正します。
> そもそもcurrは「リストのどこに追加するか」という入力ができるようになってないと思うので、末尾に追加しているのだと思うのですが、末尾ならcurrのpre.nextは未定義となるのでは？

ですが、
「prev.next ← curr」[ b ]欄の部分で追加するのは、currを追加する前に末尾だった、
ひとつ前のprev.nextですね。
currが追加されたことで末尾でなくなったので、currを示すポインタが必要になったのでここで設定している。
ので[ b ]はcurrのアドレス（prev）。
消去法で[b]がcurrとなるけど、
ということは、やっぱりcurrにはアドレスの情報も含んでる…ということになります？

https://www.fe-siken.com/kakomon/sample20220425/b3.html
いくらか箇条書きで書かさせていただきます。
また実プログラミングを含めてはコメントしてません、あくまで擬似言語問題を解く上でと読んでください。

>例えば、ListElement型の変数prevはあくまでもListElement型であって整数型ではないのでしょうか？  
>ListElement型であり整数型、のようになっているのかと思っていたのですが、javaで言うObject型のようななんでも型になっているのでしょうか？
ListElement型であって整数型ということは絶対と考えてＯＫです。
またObject型や、キャスト（型変換）のような操作も出てこないと思いますので無いと考えていいと思ってます。
型は明確で必ず指定されていて処理中には変わらないと考えてください。

>currとセットになっているprevは未定義
の部分ですが、
定義した時にListElement：curr,prevと並べて書いてありますがこちらはそれぞれ
・ListElement：curr
・ListElement：prev
という２つの独立して変数でなんら関係を持たずセットで扱われることはありません。

>else以下の部分はprevを設定していく部分
>リストのcurrのひとつ前のポインタprev.nextがcurrのprevと等しいので、
currとprevがセットで扱われているように読み取れました。
問題のなかで定義されているものを再度ご確認いただきたいのですが、ListElementの箱の中に入っているものは
・val（文字列）
・next（次の要素）
のみでprev（前の要素）を持っていません。
なのでcurrのprev（作られたばかりのcurrの前の要素）というものが存在していません。

>prev.nextはポインタなのに、currを代入？？  と最初の疑問に戻ってしまいます。
prev.nextはクラスListElementの説明によればnextはListElement型ですよね。
currもListElement型なのでなんら問題はありません。

>currには要素（文字）のほかにアドレスとなるデータ（整数？）も持っているのでしょうか？
内部的にはアドレスで扱われていますが、あまり考えなくて良いと思ってます。

この考えに至った場所は以下によるものだと思うのですが
prev.next ← curr
こちらもポインタなどの複雑な考えは持つ必要なく、
prev.nextがcurrの値で上書きされた。
というもので
prev.val ← "なにかの値"
とした時と何ら変わりません。
※厳密にはオブジェクトの代入は参照を渡しているだけなので真にすべての値を書き換えているわけではありませんが擬似言語を解く上ではあまり気にしなくて良いと思ってます。
今後プログラムを書く時に参照ってこういう事だったんだと知れれば良いと思ってます。

>(No.4) 
についてですがプログラムではなく、実際に以下の様な状態を想像してみたほうがわかりやすいと思います。

リスト全部の中身
東京→品川→新横浜→「未定義」

listHeadが（先頭要素）
東京→品川
currが
小田原→「未定義」

この状態から
１．prev  ←  listHead
でprevがlistHeadで書き換わる
２．prev  ←  prev.next
でprevが末尾（新横浜）まで更新し続ける
東京  ←  東京.品川
品川  ←  品川.新横浜
新横浜  ←  新横浜.「未定義」  // これは行わない。
//なぜなら３の「未定義」.「未定義」となり未定義"から"何かを取り出したり変更することはエラーだから
３．prev.next  ←  curr
新横浜.「未定義」  ←  小田原.「未定義」

結果リストの全体が
東京→品川→新横浜→小田原→「未定義」
となります。

>ということは、やっぱりcurrにはアドレスの情報も含んでる…ということになります？ 
一応記載しますとオブジェクト型の代入はすべてアドレスの参照と考えてよくて、またオブジェクト型や数値型に関わらずアドレス情報をもたない変数は無いです。
が
１つ前でも記載しましたがそこまで厳密に考えなくても良い要素だと思ってます。

科目Bサンプル問題 問3
https://www.fe-siken.com/kakomon/sample20220425/b3.html

と問題文に書かれていますから，
というプログラムコードに登場する ListElement型の変数3つ，
listHead, prev, curr の中身はすべて「クラスListElementのインスタンスの参照」です。

ちなみに「クラスListElementのインスタンス」を図で表現するとこうなります。
そして，上図の★で示しているのが「クラスListElementのインスタンスの参照」です。

ListElementのインスタンス（要素の実体）を参照するために，
要素番号として 0,1,2,3,… といった値を用いているのであれば，
★も listHeadも prevも currの中身は 0,1,2,3,… といった整数値でしょうし，

(88A0)16, (88B0)16, (88C0)16, (88D0)16 といったアドレス値を用いているのであれば，
★も listHeadも prevも currの中身は そのようなアドレス値でしょう。

の理解が間違っている点は，No.2で指摘があったとおりです。

変数qValは単なる文字型ですが，

ListElement(qVal)を実行することで，qValを元にしてクラスListElementの新たなインスタンスが生み出されます。そしてその新たなインスタンスの参照（それが要素番号なのかアドレス値なのかは分かりません）がcurrに格納されます。

以上より，
> 変数qVal（文字型）をcurrに入れているので，currは文字型の変数だと思った
という理解は間違っています。

ちなみに上図について補足するなら，curr.valは文字型です。currとcurr.nextはListElement型です。

No.3の次の発言も気になりました。
> ListElementというvalとprevとprev.nextの3つセットがいくつか並んでいるリストがあり

単方向リストですから，リストの先頭から末尾に向けて，進んでいくことはできても戻ることはできません。ですから，リスト要素が持っているのは.nextポインタだけです。このサイトの解説でもそのように図解されています。
単方向リストのデータ構造では進んでしまうと戻れないから，プログラム中で変数prevで1つ前の要素の参照を保持しておくようにしたわけです。

valとnextは，ListElementデータ構造自体が持っている変数ですが，
prevは今回のプログラムで使われた変数であり，データ構造自体はprevを持っていません。

単方向リストとしてアルファベットを順に並べていく処理を考えて見ます。
（abcdefghij・・・を作ります。）
ListElement(a)の代入をcurrではなくAと表記します。bcd以下も同じようにします。
(A,B,C,D,・・・はListElement型)
最初の処理
A←ListElement(a)
    A.val=a
    A.next=未定義
ListHeadが未定義なので、
ListHead←A
    ListHead.val=a
    ListHead.next=未定義

2つめ
B←ListElement(b)
    B.val=b
    B.next=未定義
ListHeadが未定義ではないので
prev←ListHead
prev.nextは、未定義なので
prev.next←B
    ListHead.val=a
    ListHead.next=B
    B.val=b
    B.next=未定義
・・・
abcまで終わり、dを追加します。
    ListHead.val=a
    ListHead.next=B
    B.val=b
    B.next=C
    C.val=c
    C.next=未定義
    の状態です。

D←ListElement(d)
    D.val=d
    D.next=未定義
prev←ListHead
prev.next=B

prev.nextが未定義でないので
prev←B
prev.next=C

prev.nextが未定義でないので
prev←C
prev.next=C.nextが未定義なので
prev.next←D

    ListHead.val=a
    ListHead.next=B
    B.val=b
    B.next=C
    C.val=c
    C.next=D
    D.val=d
    D.next=未定義
になります。

電タックさん、何度もありがとうございます。

＞currとセットになっているprevは未定義
の部分ですが、
定義した時にListElement：curr,prevと並べて書いてありますがこちらはそれぞれ
・ListElement：curr
・ListElement：prev
という２つの独立して変数でなんら関係を持たずセットで扱われることはありません。

この部分ですが、単方向リストなので、リストのデータを作成する際には
要素番号、要素、（ひとつ前の要素からの）ポインタ  の３つがそろっていないとリストを構成するデータとして認識されない（逆にポインタを書き換えれば追加や削除をすることができる）
要素番号がわかれば要素とポインタがわかるため、
prev（要素番号）とval（要素）とprev.next（ポインタ）をセットであり
currはそういった「３つセット」の中でも最新（処理中）の追加、のようなイメージでした。
No.6の例ですと

出発地（listHead）「①の駅から出発」
 ↓
「①番の駅（prev）
"東京駅"（val）
[次は②の駅へ]（prev.next）」
 ↓
「②番の駅（prev）
"品川駅"（val）
[次は③の駅へ]（prev.next）
  ↓
「③番の駅（prev）
"新横浜駅"（val）
[未定義]（prev.next）」

のように続いていて、新しい要素"小田原"をcurrとして追加するには"小田原"のひとつ前"新横浜"のポインタ（未定義）が"小田原"を指すように、
小田原の駅番号＝新横浜のポインタを設定する（この部分が[ b ]欄のある行）

私がひっかかっていたのは、上の駅の例でいうと
「currで追加する項目には新駅名"小田原"としか指示がないように見えるのに、
小田原の駅番号が入るべき新横浜のポインタ部分にcurr（＝"小田原"）と入れる？？」
という簡単に言うと  前後（順序）を示すところに文字を入れる？  という疑問でした。
curr、というよりすべてのオブジェクトがそれ自身の位置情報を持っている、ということなら
"小田原"が"小田原"の位置を「新横浜のポインタ」として渡すことができるのも納得です。
（currはいくつかのデータを持つが、currを代入することでその中の代入先が自分の型に合致するデータを受け取ることができ、
駅の例で言うといくつかある情報のうち、新横浜のポインタprev.nextの型と一致する位置情報の方をprev.nextは保持した……ということになるのでしょうか）

何度も丁寧にコメントいただきありがとうございました。

この投稿は投稿者により削除されました。(2024.07.28 22:39)

先に(No.5)で私が記述した所で1箇所大きな抜けが合ったので訂正させてください。
誤：ListElement型であって整数型ということは絶対と考えてＯＫです。
正：ListElement型であって整数型ということは絶対無いと考えてＯＫです。

>(No.11)
>（currはいくつかのデータを持つが、currを代入することでその中の代入先が自分の型に合致するデータを受け取ることができ、駅の例で言うといくつかある情報のうち、新横浜のポインタprev.nextの型と一致する位置情報の方をprev.nextは保持した……ということになるのでしょうか）
もともと私が初学者向け説明として代入と参照（ポインタ）を区別すると結果理解の妨げになると思いあえて区別せず理解しやすい代入で表現していました。

No.11の上記引用した箇所は実プログラムでの動作そのもので私は正しいと思ってます。

最初の質問にありました
ListElement型にポインタ（アドレス値＝数値型）を代入という所で、型の不一致に疑問をもっていたのがこの点だという事に気づかずかなり回り道させてしまったかもしれずすみません。

aenさんの理解の通りで、
オブジェクト型（ListElement等）への代入は、基本的に参照（ポインタ）となります。
またすべての変数はアドレス値を必ず持っています。

以下の様な操作
list  ←  curr
prev  ←  listHead
curr  ←  ListElement(qVal)
prev  ←  prev.next
prev.next  ←  curr

ただし1点覚えておいてほしいのが
参照（ポインタ）がいくらアドレス値（数値）と言えども
どんな型でも良いわけではなく、左辺と右辺の型は原則同一でないとエラーとなります。
>結果値だけを見れば代入と同じ様な動きとなる。
※上記操作は両辺ともListElement型なので正しいということになります。
※原則と書いたのはポリモーフィズムの関係やObject型への型変換という例外があるのですが擬似言語問題ではこの点はおそらく出題されないので深い追いは不要です。

> curr、というよりすべてのオブジェクトがそれ自身の位置情報を持っている、ということなら

とのことですが「すべての」といった極端な表現を持ち出す必要はないでしょう。

No.7で説明したとおり，
少なくとも listHead, prev, curr の3つについては「クラスListElementのインスタンスの参照」だから，そこに格納された値は「クラスListElementのインスタンス（すなわちvalとnextが組になったもの）を指す位置情報」です。

> 私がひっかかっていたのは、上の駅の例でいうと
> 「currで追加する項目には新駅名"小田原"としか指示がないように見えるのに、
> 小田原の駅番号が入るべき新横浜のポインタ部分にcurr（＝"小田原"）と入れる？？」

そうではないとNo.8で説明しました。
のようになりますから，curr.valが"小田原"です。
currは「クラスListElementのインスタンスの参照」です。そのインスタンスのメンバ変数valに"小田原"が格納されています。

boyonboyonさん，No.10 の解説に一つ誤りを見つけました。
とだけ問題文に説明されていますから，それ自体はクラスListElementのインスタンスではありません。ですから，listHeadはvalやnextを持っていません。

No.10の結論の表記に倣って書くならば次のようになります。

    listHead=A

    A.val='a'
    A.next=B

    B.val='b'
    B.next=C

    C.val='c'
    C.next=D

    D.val='d'
    D.next=未定義

jjon-comさん

ご指摘ありがとうございます。ListHeadの定義をうっかり見逃していました。
ListHeadは、Aの参照だけですね。
添削していただきありがとうございます。

電タックさん、jjon-comさん、boyonboyonさん
何度も丁寧にお教えくださりありがとうございます。

生成したインスタンスやオブジェクトの性質について、
特に、オブジェクトが要素のほかに自身の位置情報も代入することで渡せる、
オブジェクト型への代入は、基本的に参照（ポインタ）となる、など
ということを知らなかったことで、さまざま誤解していたようです。
皆さんの解説をじっくり拝読して、理解を深めたいと思います。


使用しているテキストやネットで調べても辿り着けなくて困っていたので、本当に助かりました。

皆様、本当にありがとうございました！