リストのサーチ(探索)は基本的にリニアサーチのみ。

データ構造「リスト」の検索

リストは配列のように添字を使ってデータを扱うことができない。
そのため、先頭から順に後ろにたどっていくか、反対に末尾から前にたどっていくかしかない。
だから、リストはデータを飛び飛びにアクセスするには向いていない。全てにおいてリストが配列より優れているということは無いのである。
前後に行ったり来たりする場合は、配列が向いている。
リストのなかに格納されているデータをサーチする方法はリニアサーチのみとなる。
リニアサーチというのは、先頭から順番に力尽くで探していく探索方法のこと。
以下に、リストの数値を探索するサンプルを示す。言語はRuby.

class ListNodeForList
  attr_accessor :data
  attr_accessor :prev
  attr_accessor :next
  def initialize(val)
    @data = val
  end

  @prev
  @next
  @data
end

## Main ##
first_node = nil
last_node = nil
begin
  print("整数を入力してください！(0を入力すると終了)：")
  buf = gets.to_i
  if buf != 0
    new_node = ListNodeForList.new(buf)
    new_node.next = nil;
    if (last_node != nil)
      last_node.next = new_node
      new_node.prev = last_node
      last_node = new_node
    else
      first_node = last_node = new_node
      new_node.prev = nil
    end
  end
end until buf == 0


begin
  print("検索する値を入力してください(0を入力すると終了):")
  buf = gets.to_i
  if buf != 0
    puts "検索を開始します！"
    this_node = first_node
    lookup_flg = 0
    until this_node == nil
      puts "Nodeを走査中・・・"
      if (this_node.data == buf)
        puts("入力された配列の中に#{buf}が見つかりました!")
        lookup_flg = 1
        break
      end
      this_node = this_node.next
    end

    if lookup_flg == 0
      puts("残念ながら、#{buf}はありませんでした・・・")
    end
  end
end until buf == 0

実行結果はこうなる。

整数を入力してください！(0を入力すると終了)：3
整数を入力してください！(0を入力すると終了)：4
整数を入力してください！(0を入力すると終了)：5
整数を入力してください！(0を入力すると終了)：6
整数を入力してください！(0を入力すると終了)：7
整数を入力してください！(0を入力すると終了)：2
整数を入力してください！(0を入力すると終了)：0
検索する値を入力してください(0を入力すると終了):3
検索を開始します！
Nodeを走査中・・・
入力された配列の中に3が見つかりました!
検索する値を入力してください(0を入力すると終了):10
検索を開始します！
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
残念ながら、10はありませんでした・・・
検索する値を入力してください(0を入力すると終了):55
検索を開始します！
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
Nodeを走査中・・・
残念ながら、55はありませんでした・・・
検索する値を入力してください(0を入力すると終了):0

Rubyの基礎文法

Rubyでクラスを作る方法

class クラス名
  #処理
end

クラス定義式に渡すクラス名は、大文字のアルファベットで始める必要がある。基本的にキャメルケースで命名する。
クラスのインスタンスを生成するには、newメソッドを使う。

class MyClass
	def initialize
		puts 'Initialize!'
	end
end
my_obj = MyClass.new

インスタンス変数

インスタンスの中でだけ参照できる変数をインスタンス変数という。
インスタンス変数によって、オブジェクトの状態を保持することができる。
インスタンス変数は@hogeのように、@で始まる名前で表記する。
外部からインスタンス変数にアクセスするにはメソッドが必要で、「attr_accessor :インスタンス変数」と記述すると、内部でセッターとゲッターを定義してくれる。

class ListNodeForList
  attr_accessor :data
  def initialize(val)
    @data = val
  end
end

勉強した本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

読めば読むほど味が出る。本当にいい本。
というのも、昔は別の本でアルゴリズムとデータ構造の勉強をしようとして、挫折したから。
この本は挫折しない。ありがとう。

感謝のプログラミング

今回で感謝のプログラミングは【605時間目】
10000時間まで、あと【9395時間】