26年秋午後問3マージソート

PTさん  
(No.1)
https://www.ap-siken.com/kakomon/26_aki/pm03.html
この問題文の図に示されているソース(擬似言語ですが)に疑問があります。
javaで単方向連結リストを実現しとうと工夫しているんですがうまくいっていません。素人の発想で次のような疑問が浮かびましたが、分かる方いらっしゃいませんか?
(1)ポインタは参照では?
(2)連結リスト(とセル)は呼び出しのたびにコピー?
(3)[aはNULLではない かつ bはNULLではない]で、残りの要素数(セルの数)が1?

(1)と(2)の疑問は根っこが繋がっているので先に(3)から。
この問題では、マージのときに2つの昇順に整列された連結リストを、それぞれの先頭にあるセルのvalueが小さい方を選んで、新しい連結リストのheadの後ろに繋げていきます。
a{1,2},b{7,8}だったら、a[最初のセル]が新しいリストにhead->nextに代入されます。
※head->nextに代入すると、headのnextに代入されるのではなく、headの次のセルのvalueに代入されます。ここら辺の考察はjavaしか知らないのが原因だと思いますが、問題でのオブジェクトの構造がどうなってるのかさっぱり分かりません。
そして、問題のオに該当する部分では、「要素が残っている連結リストを連結する」とあります。単純にaもしくはbを代入しているので、要素は1つだと思っていましたが、ここで書いているうちに、もしかして後続のセル全てを代入しているのかも?と気づきましたが、それはまた複雑な問題でもあります。これが残り全部なら、たぶん(1)と(2)の場所に帰結しますが、残り1個という意味だった場合、javaでいう「a != null && b != null」では説明が付きません。a{1,2},b{7,8}だったら、先にaが無くなってbは2個以上残っているので。

既に長くなり過ぎたのでサラッと書こうと思います。
(1)については、ソートの過程で半分に分割するとき、セルの順番で指定します。b=2a+1です。その時にa->nextをnullにして(valueじゃなくてa->nullに代入している(?))います。そうすることで、a以前のセル範囲の参照を指定して再帰的に呼び出しているように"思えます(フィーリングで)"。しかしそうすれば、2+2されたリストが4+4のとき、真ん中の参照値がnullになってソートできないはずです。再帰処理で渡したものが参照なら。
つまり擬似言語では新しくコピーしたっぽい?んですが、じゃあnext値はリストが持ってるの?セルが持ってるの?セルなら全てのセルをコピーして、そのnextにある参照値はどうなってるの?とか、そう思ったときに(2)も疑問に思いました。->nextに代入する行為が次のセルのvalueだったりあるいはそのセルのnextにだったりするのも、そこに代入する値としてaとかbとか、オブジェクトっぽい変数をそのまま指定していたり、->next=aでaのセルのnextがnullに当たるまで自動代入される(かも)とか、もう意味がわかりません。
どなたかヒントを頂けませんか?
2019.03.19 12:05
助け人さん 
AP ゴールドマイスター
(No.2)
この問題のプログラムをjavaで実現するときの疑問なのか、この問題のどこかが疑問なのか、どちらなのでしょうか?

前者なら、私の出番はありませんので、どなたかお願いします。

後者なら、ご質問の内容が失礼ながら理解できませんので、java固有のことや、参照とかコピーとか、この問題に関係ない用語を使わず、どの設問についてどのようなことを尋ねたいか、再度、質問してください。
2019.03.19 17:47
danchoさん 
(No.3)
ポインタと呼んでるので混乱しているようですが、要はポインタと呼んでいるただの変数です。
2019.03.20 10:27
PTさん  
(No.4)
言語やマージソートそのものは関係ありません。どうやって問題文にある擬似言語のソースを使ってマージソートを実現するか、と考えた時の疑問です。
->nextという値がどういうものかで、答え方が全く違ってきませんか?このセルというものがオブジェクトだと思ったので、ならデータ構造はそのセルのリストだろう→あれ?ここはどうなってるんだろう?……という疑問です。ここというのは参照云々の話ですが、私は関係ないどころか根幹だと思うので分かる方よろしくお願いします。
変数ということは、再帰的に呼び出す度に連結リストとその中身(セル)は全部コピーしているんでしょうか?ということはそれもまた全部上の処理に返していることに……
2019.03.20 16:50
助け人さん 
AP ゴールドマイスター
(No.5)
何が疑問なのかわかりませんので、お役に立てるかわかりませんが、断片的に手さぐりで書いてみます。

->nextについて
図4で説明します。listは、一つ目のセル(valueが44)へのポインタですが、このセルのアドレスと考えてください。一つ目のセルのnextは、二つ目のセル(valueが10)へのポインタ(アドレス)です。

a{1,2},b{7,8}について
図7の(aがNULLと等しくない,かつ,bがNULLと等しくない)を抜けた後、要素が残っている連結リストは{7,8}の2個です。

「再帰的」について
図2の(1)~(4)がソートマージです。(2)が図5のdivide、(4)が図7のmergeです。(3)の中でソートマージを再帰的に呼び出しますが、(3)のプログラムは載っていません。つまり、図5と図7では、再帰処理はありません。
2019.03.20 19:56
メタルスネークさん 
(No.6)
C言語で言う、自己参照構造体がどういったものか調べて理解してください。
JAVA言語だとどういうのかわかりませんが自己参照クラスとでもいうのでしょうか?
以下のようなコードになります。

class list {
public int value;
public list next;
}
2019.03.21 01:28
メタルスネークさん 
(No.7)
JAVAで言う参照と呼ばれる変数がポインタです。
変数の内容をコピーするのと違って、指定した変数のアドレスを格納してアクセスする方法です。
2019.03.21 01:37

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop