こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

単方向リストの解釈

 多数のデータが単方向リスト構造で格納されている。このリスト構造には、先頭ポインタとは別に、末尾のデータを指し示す末尾ポインタがある。次の操作のうち、ポインタを参照する回数が最も多いものはどれか。

ア リストの先頭にデータを挿入する。
イ リストの先頭のデータを削除する。
ウ リストの末尾にデータを挿入する。
エ リストの末尾のデータを削除する。     (平成24年度春期 問7)

各選択肢の参照ポインタ数はいくつになるのでしょうか。
解説書によって必要なポインタ参照数が異なっていて、理解できずにいます。

とある解説書では、
ア 2回のポインタの参照が必要
イ 1回のポインタの参照が必要
ウ 2回のポインタの参照が必要

と記述してあり、またある解説書では

ア 0回のポインタの参照が必要
イ 2回のポインタの参照が必要
ウ 1回のポインタの参照が必要
エ 3回のポインタの参照が必要

と記述されていました。

先頭から末尾の一つ手前のデータまで順にたどって参照する必要のあるエが一番ポインタを参照する回数が多そうだな、と想像はできるのですが、実際の参照回数までは理解の外です。。

ご教授お願いします。

投稿日時 - 2013-03-18 19:46:15

QNo.7999907

すぐに回答ほしいです

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(4)

ANo.4

「ポインタの参照」をどう捉えるかで、数が変わってきますね。
例えば、新規の要素を確保してそのポインタをどこかに設定する場合、既存のポインタは見ていないので参照回数に加えないのか、新規確保したポインタも数に入れて+1とするかは解釈が分かれるかと。
まあ、答えがエで有ることは変わらないですが。(要素が多数で、末尾の要素を指しているもの以外の全てのポインタを参照する必要が有る為)

個人的には「ポインタの参照」を「既存のポインタの値を取得すること」と捉えるのが妥当だと思いますので、下記のページの解説が分かりやすくて良いと思います。
http://itpro.nikkeibp.co.jp/article/COLUMN/20120529/399361/?ST=selfup

だたし、このページも間違っている箇所は有ります。
エの場合、末尾のデータを指しているポインタは(書き換える必要は有っても)参照する必要は無いので図の最後の青矢印は不要です。(解説の文章の方は間違っていませんが)

投稿日時 - 2013-04-13 14:36:52

ANo.3

ア)を実現するためには次の2つの処理を実行すればよい。
・挿入要素の次ポインタ部←先頭ポインタの中身
・先頭ポインタの中身←挿入要素のアドレス

--------
イ)を実現するためには次の処理を実行すればよい。
・先頭ポインタの中身←先頭ポインタが指す要素の次ポインタ部の中身

【補足】
回答No.2では次のように解説されていますけれど,
> イは、先頭のポインタの参照を殺して2番目のポインタに
> すればいいので、1回です。先頭を見る必要はありません。
先頭ポインタを起点にリストを一歩進まないと2番目の要素のアドレスは得られません。

私なら,上記の イ)の処理は,実質的に次の2つの処理だと見なします。
・変数X←先頭ポインタの中身
・先頭ポインタの中身←変数Xが指す要素の次ポインタ部の中身

--------
ウ)を実現するためには次の処理を実行すればよい。
・末尾ポインタが指す要素の次ポインタ部の中身←挿入要素のアドレス
・末尾ポインタの中身←挿入要素のアドレス

前述と同様,私はこれを実質的に次の3つの処理だと見なします。
・変数X←先頭ポインタの中身
・変数Xが指す要素の次ポインタ部の中身←挿入要素のアドレス
・末尾ポインタの中身←挿入要素のアドレス

--------
そして最後の エ)ですが。

単方向リストにおける要素の削除とは,
削除対象要素を書き換えることではなく,
「削除対象要素の1つ前の要素の次ポインタ部」を書き換えることです。

末尾要素に達するだけなら,末尾ポインタから一発で到着することができますが,
そこから「末尾要素の1つ前の要素」に移動しようとしても,単方向リストなので末尾要素から1つ前に遡ることは不可能です。
したがって,回答No.2で解説されているとおり,
先頭ポインタから単方向リストを一歩一歩 順にたどることによってでしか「末尾要素の1つ前の要素」に達することはできません。

そこに達した後は次の処理を実行します。
・末尾要素の1つ前の要素の次ポインタ部の中身←リスト終端を表す特別な値
・末尾ポインタの中身←末尾要素の1つ前の要素のアドレス

投稿日時 - 2013-03-19 00:57:08

ANo.2

2つの解説書とも、説明が違います。
答えがエであることはおわかりですね。

順に解説します。簡単です。

単方向リストですから、ずらりとデータが並んでいます。
アの場合は、先頭にあるポインタを2番目にして新しく確保したポインタを先頭にするだけですから2回です。
イは、先頭のポインタの参照を殺して2番目のポインタにすればいいので、1回です。先頭を見る必要はありません。
ウは、最後のポインタを更新することになりますから、1回です。
エは、最後のポインタを最後から2番目のポインタにしなければいけません。
イの場合は最初+1が2番目のポインタになりますけど、エは最後ー1のポインタを確保しなければならないのです。

だったら、エ、は最初からずっと最後になるまで全部を調べてはじめて、最後ー1がわかります。
仮にリストが2個しかなくても2回は必要です。n個あったらn回参照です。

投稿日時 - 2013-03-18 23:06:57

ANo.1

> 実際の参照回数までは理解の外です。。
要素数を定義しないと難しいかも。

投稿日時 - 2013-03-18 20:18:29

お礼

>ある解説書では、
ア 2回のポインタの参照が必要
イ 1回のポインタの参照が必要
ウ 2回のポインタの参照が必要

この解説では要素数の定義はされていませんでした。
なので、要素数を定義しなくてもこの参照回数になるのではないかと考えています。

投稿日時 - 2013-03-18 20:51:52

あなたにオススメの質問