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

- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
読めば読むほど味が出る。本当にいい本。
というのも、昔は別の本でアルゴリズムとデータ構造の勉強をしようとして、挫折したから。
この本は挫折しない。ありがとう。
感謝のプログラミング
今回で感謝のプログラミングは【605時間目】
10000時間まで、あと【9395時間】