解説 5月10日A

今回の学習項目です。


ポインタの効用

教科書の2.1節(13ページ目から16ページ目まで)を読んでください。

教科書の2.1節の内容としては以下が重要です。

ポインタというのはあまりなじみのない概念かもしれませんが、とても重要なものです。プログラミング言語Rubyでは表には出てきませんが、Cのような言語ではその理解が必須になっているものです。

変数を例にして説明します。変数には値をセットできます。 たとえば、x = 3という命令を実行すると、xという変数は3という値を持つのでした。 つまり、xという変数を手がかりにすれば、3という数が取り出せる関係にあります。

ここで、(Rubyではできないのですが)変数の値として別な変数の場所を与えることができるとしましょう。つまりyという変数の値には、変数xの場所が書いてある、というものです。 これが「ポインタ」の概念です。そしてこの場合「ポインタyがxを指す(さす)」と言います。

変数と値との関係を、「場所」と「その場所にすむ人」の関係とみなすと、次のようにいえます。 普通は「場所」である変数xをコンピュータに与えると、その場所にある「3」が取り出せます。 ポインタとは、このような場合とは異なり、「場所」である変数yをコンピュータに与えると別な変数xの場所への情報がある、というしかけです。 この「別な場所への情報」がポインタです(ポインタはその『別な場所」を指しているのです)。

教科書2.1節では、名簿を例に説明していました。名簿の項目が「値」に相当します。「場所」は名簿の「アドレス」(番号)です。 そして、名簿でアドレスを指定すれば、その値が取り出される、という仕組みになっていました。

Fig 2.1 図2.1(このページの右図)では、配列を使って名簿を表しています。 アドレスとして配列の指標(インデックス)が使われます。配列で表す場合、指標がnの項目の次の項目は、指標がn+1のものと考えます。また前の項目は、指標がn-1のものです。このように、配列を使うと、ある項目の前や後ろの項目は指標によって簡単に取り出せます。

これはこれでよいのですが、一つ問題があります。 それは、図2.2のように、途中に項目を追加したり、削除したりすることが大変、ということです。 名簿がアイウエオ順になっていることに留意してください。 項目はアイウエオ順で並んでいますから、「今井」を追加しようとすれば、 3番目の上田から後ろにある項目を順に後ろにずらして「今井」をいれなければなりません。 このように、n番目の項目の後ろに項目を追加しようとすれば、もともとn+1番目の項目だけではなく、n+1番目、n+2番目、...の項目を後ろにずらさなければなりません。また逆にn番目の項目を削除するときも、n+1番目、n+2番目、...の項目を(今度は)前にずらさなければなりません。これはちょっと大変な作業のように思えます。

Fig 2.3 図 2.3(a) (このページの左図)では next という欄を増やしています。この欄に書かれるものを「ポインタ」として扱っています。この欄の数字は名簿のアドレスで、これを手がかりにすると、名簿の項目が取り出される、という仕組みです。 たとえば一番先頭の「青木」の項目のnextには2が書かれています。 これは「青木」の次の項目はアドレスが2のもの、つまり「石川」であることを意味します。

この方式では、項目を追加するのは常に配列の最後で行われます。 すると、「今井」のように、項目として途中にはいるべきものであっても、。 配列の最後に「今井」の項目を付け加え、「今井」の前の項目である「石川」のnextの値を付け加えるだけでよくなります。 また、図2.3(a)から「上田」を削除する場合は(項目の挿入は不要なので)もっと簡単になり、「上田」の前の項目である「石川」のnextの値を書き換えればよい、ということになります。



課題1-1

図2.3(a)では、先頭の項目はいつも1番目ですが、2番目の項目が2番目にあり、3番目の項目が3番目に書いてあるとは限りません。図2.3(b)をみると、3番目の項目はn+1番目においてあります。 このようにある項目の次の項目を取り出すにはnextの値を見なければなりません。また最後の項目のnextの値はスラッシュがかかれています。これはRubyのような言語の場合は nil という値を書くのが通例です。

  1. 図2.3(b)において、「青木」の次の項目はどれでしょう。またその項目の次の項目はどれでしょうか。またその理由を述べなさい。
  2. 図2.3(c)において、「青木」の次の項目はどれでしょう。またその項目の次の項目はどれでしょうか。またその理由を述べなさい。

課題1-2

図2.3(a)の名簿に「井上」と「内田」の二つの項目をこの順に付け加えたとします。 そのときの名簿の様子を説明しなさい(どこが図2.3(a)と比べてどのように変わったか、を言葉で説明すればよい)。

課題1-3

図2.3(a)の名簿から「石川」と「上田」の二つの項目をこの順に削除したとします。 そのときの名簿の様子を説明しなさい(どこが図2.3(a)と比べてどのように変わったか、を言葉で説明すればよい)。

課題1-4 発展問題(やらなくともよい)

次の2つの問題を考えて、図2.3の形式で名簿を表すことの問題点を考えてみよう。
  1. 図2.3(a)の名簿から「青木」を削除することを考えよう。 そもそもこれは可能だろうか?可能だとすれば、名簿の様子はどのようになるだろうか。説明しなさい。
  2. 図2.3(a)の名簿に「相田」(あいだ)を登録することを考えよう。 そもそもこれは可能だろうか?可能だとすれば、名簿の様子はどのようになるだろうか。説明しなさい。

リスト構造

ポインタをデータの一部として取り込んだ構造を、「リスト構造」といいます。 この条件で特徴付けられるリスト構造には、いろいろたくさんの種類があります。 本講義「アルゴリズムとデータ構造」で学ぶ多くのデータ構造ではポインタを用いています。 つまり、本講義で出てくるほとんどのデータ構造は「リスト構造」であるといえます。

Fig 2.4

リスト構造を抽象的にあらわした(重要なところだけを取り出して図示した)ものが図2.4 (上図)です。矢印で示されているのが「ポインタ」です。 ポインタは「次のデータへの場所の情報」なので、矢印によって「次のデータ」がどれであるかを表しています。 またリスト構造ではポインタも含めたデータの集合体(名簿の例でいえば、名簿の項目)を「セル」と呼びます。このセルは図2.4に示すように箱の形で書かれることが多いです。 ただ注意してほしいのは、図2.4には名簿の「名前」しか書かれていないようにみえますが、実際には「名前」以外の「住所」や「電話番号」などの情報も入れられるようになっています。ここではわかり易さのために「名前」しか書いていないと思ってください。

課題2-1

セルをRubyのクラスで表してみましょう。そのための試みが以下です:

   class Cell    # クラスの定義の始まり
        def initialize(item, p = nil)   # インスタンスを作るためのメソッドです
            @name = item      # nameという「要素」を定義
            @next = p         # nextという「要素」を定義
        end  # of def
        attr_accessor :name,:next   # インスタンス変数へのアクセスを可能にする
   end  # of Class
ここで、initializeメソッドの2番目の引数が p = nil となっているのは、 2番目の引数が省略可能であること、また省略された時にはnilが値として与えられたものと考えることを表しています。

次を実行してみましょう。

aoki = Cell.new("青木")
ishikawa = Cell.new("石川")
これにより、aokiとishikawa変数には、それぞれ「青木」の名簿項目と「石川」の名簿項目がセルとして入ります。 ここで、aokiセルのnextがishikawaセルを「指す」にはどのようにしたらよいでしょうか。 これを実現するコードを答えなさい。
[ヒント]
この例ではaokiもishikawaもそれぞれ「セル」に対応します。 「aokiセルのnextがishikawaセルを指す」には、 aokiセルのnextの値がishikawaセルになるようにすればよいのです。 ここで aokiセルのnextは aoki.next で取り出せるのでした。 それに変数ishikawaの値を代入すればよいのです。

[参考]
最初からリスト構造を作る場合、 次のようにやれば、最初から青木セルと石川セルをつないだリスト構造が作れました。 ただし、この例のように後ろに続くセルを最初に作る必要があります。
ishikawa = Cell.new("石川")
aoki = Cell.new("青木", ishikawa)   # 第2引数に注目
なお、これは問題の答えではありません。この問題は、すでに作ってしまった aokiセルとishikawaセルをつなぐ(aokiセルのnextがishikawaセルを指すようにする) にはどうすればよいか、を質問しています。

課題2-2

課題2-1で定義したCellクラスを用いて、図2.4(a)のようなリスト構造を作ることを考えましょう。
(1)課題2-1にならって、「青木」「石川」「上田」「遠藤」「山田」 の5つのセルをこの順に並べたリスト構造を作るためにはどのようなプログラムを書いたらよいでしょうか、答えなさい。
(2) (1)のリスト構造に、図2.4(b)のように「今井」セルを「石川」セルと「上田」セルの間に入るよう付け加えるためのプログラムはどのようになるでしょうか、答えなさい。
(3) (1)のリスト構造から、図2.4(c)のように「上田」セルを削除するためのプログラムはどのようになるでしょうか、答えなさい。

「アルゴリズムとデータ構造」のホームに戻る