HOME»基本情報技術者試験掲示板»サンプル問題科目B単方向リストの要素削除の質問
投稿する

[4775] サンプル問題科目B単方向リストの要素削除の質問

 くまさん(No.1) 
https://www.fe-siken.com/kakomon/sample/b10.html
要素を削除するために要素の次の値で上書きすることは理解できましたが、prevの単語自体がよくわかりません。

ListElement:prev
とは何を意味するのですか?listelementの要素がprevになるよってことですか?

prev <- listHead
なぜprevに入れる必要があるのですか?posが2以上であれば先頭をなにかする必要がないように思えます

prev.next
listHead.nextではダメなんでしょうか?

ほかにも大域変数の
ListElement:listHead
の意味も分からないです。
どっちも要素の先頭を意味してるよーということですか?
型の説明には次の要素の参照とかいてあるのに
ちんぷんかんぷんです。
アルゴリズムについてあまり理解していない新人なので
文系にもわかりやすく教えてくれると助かります。
2023.03.25 21:01
小福さん(No.2) 
くまさん、以下ご質問にお答えします。

①ListElement:prevとは何を意味するのですか?
  ListElement型の変数prevを定義しています。
  直ぐ下に「整数型:i」というstatementがありますが、これは整数型の変数iを定義していますよね。構文的には全く同じです。

②  prev <- listHead  なぜprevに入れる必要があるのですか?
    for loopではloopを抜けた後に、変数prevが引数posで指定された位置の要素の一つ前の要素を参照する様にプログラムされています。この位置を見つける為には、先頭要素つまりListHeadが参照している要素から順番に辿る必要があります。
    またloop内で、仮にprevを使わずに ListHead ← ListHead.nextとすると、大域変数である ListHeadを変更してしまいます。そうなるとこのリストの先頭要素を2度と参照する事ができなくなります。

③prev.next  listHead.nextではダメなんでしょうか?
    これはfor loop内の prev← prev.nextの代わりに、prev←ListHead.nextではダメか?という意味ですか?これでは変数prevに同じ値が代入されるだけですね。
ListHead ← ListHead.nextではダメか?という意味であれば②の説明を参照してください。

①大域変数のListElement:listHeadの意味も分からない
    ①と一緒です。ListElement型の大域変数ListHeadを定義しています。

上記説明で理解できますか?
2023.03.26 12:02
まきさん(No.3) 
ものすごく簡単に例を挙げると(イメージ)
駅リスト  恵比寿駅削除したい  
番号
1   東京  head
2   渋谷
3   恵比寿  ←削除したい
4   代々木
5   目黒
6   有楽町

削除後
駅リスト    
番号
1   東京
2   渋谷
4   代々木  
5   目黒
6   有楽町
といったことを問題では少し難しく聞いているのです

削除後渋谷の次は代々木ですよね。
でも渋谷からしたら削除前は代々木は渋谷、恵比寿の次のですよね

リスト  削除前      
2   渋谷
3   恵比寿  (渋谷の次)
4   代々木  (渋谷の次の次)

リスト  削除後      
2   渋谷
4   代々木(渋谷の次)
5   目黒(渋谷の次の次)


多分、主さんはこの問題をすべて理解しないといけないと思われているかもしれませんが、こんなことを言っているくらいで最初はいいです。
あとは英語の意味くらいは知っておくといいと思います
2023.03.26 13:49
まきさん(No.4) 
〉でも渋谷からしたら
これ無視してください
2023.03.26 14:26
 くまさん(No.5) 
小福さん、ありがとうございます。

整数型iというのが、変数iは整数だよという感じなのはわかります(?)が、listElement型のprevというのがどういう意味なのかよく分かっていません。
②③
ListHeadとprevの違いがわかりません。どちらも先頭要素を意味しているが、ListHeadは大域変数で、prevはリスト(?)ということでしょうか?大域変数はjavaでいうstaticみたいなものでprevはそのインスタンスなんでしょうか?全然違うのでしたら話をややこしくしてしまってすみません。
2023.03.26 22:26
 くまさん(No.6) 
まきさんありがとうございます。
そのイメージ的にはわかりました。
恵比寿を削除すると4番目の代々木が次に来るよみたいな感じですね。
英語の意味で言うとnextくらいしかわからないです
listElementでリストの要素なのになんで次の要素って意味なのーってなっちゃいます
2023.03.26 22:30
小福さん(No.7) 
くまさん

このプログラムは、リスト構造のデータを扱っています。
リスト構造は、データとポインタの組み合わせ(通常セルと呼びます)を
0個以上連結させたものです。
連結とは、あるセルのポインタが次のセルを指す事により順番に繋げています。

配列の様にn番目の要素を直接アクセスできず、1番最初のセルから順番に辿っていく必要があります。

まきさんの例をお借りすると
セルは、駅名と次の駅へのポインタで構成
されています。
つまり、「東京、(次の駅へのポインタである)2」、「渋谷、3」、「恵比寿、4」、「代々木、5」
という複数のセルでリストが構成しています。

3番目の駅をを見つける為には、最初の駅である東京からポインターを頼りに順番に探していく事になります。
3番目の恵比寿を削除する為には、その前の駅である「渋谷、3」の3を恵比寿の次の駅である4に書き換えるだけです。


このプログラムでは、「駅名、次の駅へのポインタ」という組み合わせをListElement型と定義しています。
つぎの駅へのポインタが、同じListElement型を自己参照している所が判り辛いのかもしれません。

ListElement型である変数ListHeadには、1番目の駅である「東京、2」というセルへのポインタが格納されています。
つまり、「  、1」がdelNodeを呼び出す前に格納されています。

このListHeadは1番目の駅へのポインターが格納されていますので、1番目の駅を削除する場合以外は変更してはいけません。
1番目の駅を削除する場合には、ListHeadに次の駅へのポインタであるListHead.nextを代入すればよいことになります。
(私の最初の返信は、最初の駅を削除する場合を考慮していませんでした。すみません)

1番目の駅以外を削除する場合には、for loopを"pos-2"回 回して、pos-1番目のセルを見つけます。
その上で、pos-1番目のセルの次の駅を指すポインタ(prev.next)に次の次の駅へのポインタ(prev.next.next)を代入すれば、
pos番目のセルが削除されます。

まきさんの例で、posを3とすると
prevが指しているpos-1番目のセルは、「渋谷、3」
prev.nextが指しているpos番目のセルは、「恵比寿、4」
prev.next.nextが指しているpos+1番目のセルは、「代々木、5」
prevが指している「渋谷、3」を「渋谷、4」に変更すればよいので、
prev.next = prev.next.nextとなります。


う~む 、分かり易く説明できないな~
すみません。
2023.03.27 12:30
しかさん(No.8) 
ながくなりそうなので、投稿を分けて順番に回答していきます。
>>①
>>ListElement:prev
>>とは何を意味するのですか?listelementの要素がprevになるよってことですか?

問題文に「クラス ListElement は,単方向リストの要素を表す。」とあるので、
「prev」は「単方向リストの中の要素の一つ」と定義されているということです。
なんで定義する必要があるかを完璧に説明するのは難しいですが、 無理やり短く説笑みするならば、ListElement クラスでないと「next」とかのメンバ変数が使えないからです。
2023.03.27 18:29
しかさん(No.9) 
>>②
>>prev <- listHead
>>なぜprevに入れる必要があるのですか?posが2以上であれば先頭をなにかする必要がないように思えます
そのあとのForのなかの処理を見ると、prevしか出てこないので、prevに入れる必要があります。
forのなかで次の要素次の要素と辿っていくためにprevに入れてます。
2023.03.27 18:39
しかさん(No.10) 
>>③
>>prev.next
>>listHead.nextではダメなんでしょうか?
listHeadは不変で、必ずリストの先頭の要素になります。
なのでlistHead.nextは必ずリストの2番目の要素のことを指します。
prev← prev.next
prev.next← □
のどちらの場合でも、必ずリストの2番目の要素のことを指してしまうのでは、せっかくForのなかで次の要素次の要素と辿った意味がなくなってしまうのでダメです。
2023.03.27 18:45
しかさん(No.11) 
>>ほかにも大域変数の
>>ListElement:listHead
>>の意味も分からないです。
>>どっちも要素の先頭を意味してるよーということですか?
>>型の説明には次の要素の参照とかいてあるのに
>>ちんぷんかんぷんです。
問題文の図にある説明はクラス(型)の説明ではなくメンバ変数の説明なので、そこを取り違えていると思います。
「ListElement:listHead」の意味は、横の「リストの先頭要素が格納されている」と、
問題文の「クラス ListElement は,単方向リストの要素を表す。」でわかると思います。
2023.03.27 18:50
しかさん(No.12) 
ちなみにprevはプレビューをもじって変数名にしてると思います。
全体としては「消したい要素の一つ手前になるまでForのなかでprevを次へ次へと移動していって、いざ消したい要素の一つ手前まできたら消したい要素を飛ばしてその次の要素で上書きする」という処理になります。
2023.03.27 18:59
まきさん(No.13) 
〉くまさん
とりあえずまずは、私の例にリストを削除するにはどうすればいいってことを考えましょう。というものがリスト構造ですって思ってくださいね
2023.03.27 21:24
 くまさん(No.14) 
この投稿は投稿者により削除されました。(2023.03.27 21:46)
2023.03.27 21:46
 くまさん(No.15) 
しかさん、ありがとうございます。
そもそもリスト構造のデータとポインタについて理解する必要があったのですね。
listHeadは先頭なので先頭以外を削除する場合、prevを使用しなければならない(使わないとlistHead.next.next.next~みたいになる?)ということですね。
親切にたくさん教えていただいたのに申し訳ないですが、他の説明で理解できたので、一応(ほかの人のため?自分のため?)に載せておきます。

まず、リストの要素を表すクラスListElementについて見てみましょう。このクラスは、valとnextという2つのメンバ変数を持っています。valは、要素の値を格納する文字型の変数です。nextは、次の要素への参照(ポインタ)を格納するListElement型の変数です。次の要素がないときは、nextの状態は未定義となります。
リストの先頭要素は、listHeadという大域変数に格納されています。listHeadは、ListElement型の変数で、先頭要素への参照を持っています。リストに要素がないときは、listHeadはnullとなります。
例えば、リストにA,B,Cという3つの要素がある場合は、以下のようになります。

listHead -> A -> B -> C

ここで、->は参照(ポインタ)を表します。listHeadはAへの参照を持ち、AはBへの参照を持ち、BはCへの参照を持ちます。Cは次の要素がないので、C.nextは未定義です。

このリストからBを削除するには、AとCをつなげる必要があります。つまり、A.nextにCを代入することで、BをスキップしてCに接続します。すると、以下のようになります。

listHead -> A -> C

このようにして、リストからBを削除できます。

手続delNodeは、このような操作を一般化したものです。引数posで指定された位置の要素を削除します。posは1から始まる整数で、リストの要素数以下であるとします。

手続きの中では、ListElement型の変数prevを用意しています。prevは、削除する要素の一つ前の要素を指すようになります。

ここで、prevが削除する要素の一つ前の要素を指すという意味は、以下のように理解できます。

posが1と等しい場合は、削除する要素がリストの先頭要素であることを意味します。この場合は、prevは存在しません。
posが2と等しい場合は、削除する要素がリストの2番目の要素であることを意味します。この場合は、prevはリストの先頭要素です。
posが3と等しい場合は、削除する要素がリストの3番目の要素であることを意味します。この場合は、prevはリストの2番目の要素です。
以降も同様に、posがnと等しい場合は、削除する要素がリストのn番目の要素であることを意味します。この場合は、prevはリストのn-1番目の要素です。
つまり、prevは常に削除する要素よりも一つ前に位置する要素です。

例えば、posが3と等しい場合は、以下のようになります。

listHead -> A -> B -> C

ここで、削除する要素はCです。prevはBです。B.nextに を代入することで、Cをスキップして に接続します。

以上がprevが削除する要素の一つ前の要素を指すという意味です。
2023.03.27 21:47
 くまさん(No.16) 
続き

手続きの中で、まずposが1と等しいかどうかを判定しています。posが1と等しい場合は、削除する要素がリストの先頭要素であることを意味します。この場合は、listHeadにlistHead.nextを代入することで、先頭要素を次の要素に置き換えて削除します。

posが1と等しくない場合は、削除する要素がリストの先頭以外の位置にあることを意味します。この場合は、prevにlistHeadを代入してから、for文でpos-1回だけprevにprev.nextを代入することで、prevを削除する要素の一つ前の要素に移動させます。そして、prev.nextに を代入することで、削除する要素をスキップして次の次の要素に接続します。

以上が手続delNodeの説明です。 に入れる正しい答えは カ prev.next.next です。
2023.03.27 21:49
 くまさん(No.17) 
これを理解した上でみなさんの説明がわかりました。
返信してくれた方、ありがとうございます。
2023.03.27 21:50
電タックさん(No.18) 
FE ブロンズマイスター
ちょっと細かいことになってしまい
混乱させてしまうかもしれませんが1点だけ補足をさせてください。

※伝えたいことは
  listHeadという特別に用意された領域があるわけではなく
  先頭要素に”わかりやすい別名”(ラベル)をつけている。  

A,B,Cの3要素を持つ配列(リスト)で考えた時次のようになります。
・配列 = [A, B, C]
・配列 = [先頭, A, B, C] ← こちらではない

> listHead -> A -> B -> C
> ここで、->は参照(ポインタ)を表します。listHeadはAへの参照を持ち、AはBへの参照を持ち、BはCへの参照を持ちます。Cは次の要素がないので、C.nextは未定義です。

なので最初の配列のイメージで正しく表すと
listHead(A) -> B -> C
となり
listHead=Aであって、「Aへの参照を持ち」でも理解できますが.nextで参照する形ではなく「一緒のもの」ということです

Javaをやっていらっしゃるようなので、オブジェクトの参照と一緒ですね
java.util.List l1 = new java.util.ArrayList<>();
java.util.List l2 = l1;
この時l2 == l1で一緒のものです。
2023.03.27 23:10
 くまさん(No.19) 
電タックさん、ありがとうございます。
なるほど、ABCでリストを考える際、listHeadというのはラベルのようなものでA(listHead).nextならBを参照するという意味になるのですね。Javaはまだ勉強中なので、わからないです。
2023.03.28 09:15

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop