10/18 対象のモデル化とデータ構造(2)

前回までの補足

講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．

アンケート集計結果

期限までの提出は20名，いくつかの項目に答えたものの「未提出」になっている人(7名)．

家に自分の自由に使えるPCはありますか? 以下から選んでください．

自分専用のPCが1台ある 13
家族と共用のPCがある 4
自分専用のPCが2台以上ある 3

利用可能なPCが家にある人は，そのPCで利用可能なオペレーティングシステムを下から選んで下さい(複数回答可)．
```
Linux 2
Windows 20
```
10行以上のプログラムを作成したことがあるプログラミング言語があったら，下のなかから選んでください(複数選択可)．ない人は何も選択せずに進んでください．
```
なし 7
C 5
BASIC 5
C++ 4
Java 3
C# 2
Perl 2
FORTRAN 1
Lisp(Schemeも含む) 1
PHP 1
その他 4
```

この講義は期末試験と課題で評価をしていますが，このような評価法についてどう思いますか?

テストと課題は半々でいいと思います
課題やレポートの配点がもう少し大きい方がいいです。出席があってもいいと思います。
評価が偏ることなくいいと思います。
答える必要は無いッ！
適切だと思う。
異議なし
妥当ではあるが、出席を加味しないのか気になる。
期末試験の代わりにレポートでもいいかもしれません
妥当だと思う。
期末試験はいらないと思う。課題も多すぎないようにしてもらいたい。
学んだ内容が身に付いているかは課題の出来具合で分かると思うので、期末試験はない方がいいです。
基本的には試験と課題でいいと思います。
特に問題ないと思います
良いと思う。
計プロの流れを汲むのならもっと課題提出に重きを置いてもいいのではないか。
いいんじゃないすか
一般的な評価方法だと思う。

スライドの訂正

前回配布のスライドP.4「データ(内部表現)とデータ表現(外部表現)」で 2進数01011110の10進表現を96としているのは正しくは94．
前回配布のスライドP.18「配列を使ったデータモデル例」で，「1028x768の画素」はないわけではないが，おそらく「1024x768の画素」のつもり
前回配布のスライドP.28「レコード(Struct)の例(3)」で，Persoonとなっているのは，Personの誤り

スライドに使われたプログラム

ハッシュ

marks = {"山田" => 65, "鈴木" => 83, "田中" => 71, "山本" => 95}
marks["大田"] = 75
marks["井上"] = 48

# このようにどんどん定義域を広げていくことができる

marks["鈴木"] # 鈴木君の点を訊く

# 最初の行と同じことは以下のようにしても可能

marks = Hash.new(0)  # 登録されていない学生はとりあえず0点に
marks["山田"]=65
marks["鈴木"]=83
marks["田中"]=71
marks["山本"]=95

中身サイズ可変の配列

# Rubyではちょっと無理のある例だが
FillArray = Struct.new(:currentMax, :arrayBody)
# FillArrayと，先頭が大文字になっていることに注意
# とりあえずサイズ100の配列を用意
fillArray = FillArray.new(0, Array.new(100))

# 第0要素に"hello"，第1要素に"world"を入れてみる
fillArray.arrayBody[fillArray.currentMax] = "hello"
fillArray.currentMax += 1　# currentMaxを1増やす
　　
fillArray.arrayBody[fillArray.currentMax] = "world"
fillArray.currentMax += 1

再帰的データ構造定義の例

# 中置記法の数式に合わせて
Expr = Struct.new(:left, :operator, :right)

# 前のスライドの例を無理やり作ってみた

Expr.new(
  Expr.new(
    Expr.new(3, :*, Expr.new(:x, :**, 2)),
    :-,
    Expr.new(5, :*, :x)),
  :/,
  Expr.new(:y, :+, 1))

スタックの定義

class Stack
  def initialize(size)    # newのときの初期化
    @data = Array.new(size)
    @pos = -1             # @posがスタックのトップを表す．最初はボトムを指す -1．
  end

  def push(obj)               # objがプッシュされるデータ
    @pos += 1                # @pos = @pos + 1 と同じ意味
    @data[@pos] = obj   # 前頁の図では上のほうが番地が大きい
  end

  def pop
     @pos -= 1                # 先にトップへのポインタを減らす
     @data[@pos + 1]     # ∵ 最後の式が値となるため
  end

  def empty?() @pos == -1 end

end

キューのデータ構造(2)

MyQueue = Struct.new(:top, :tail, :length, :array)

def enqueue(q, data)
  q.array[q.tail] = data
  q.tail = (q.tail + 1) % q.array.size  # % は余りを求める演算 （循環するため）
  q.length += 1
end

def dequeue(q)
  value = q.array[q.top]
  q.top = (q.top + 1) % q.array.size
  q.length-= 1
  value
end

def empty?(q)
  q.length == 0
end

試してみよう

q = MyQueue.new(0, 0, 0, Array.new(100))

p empty?(q)
enqueue(q, :x)
p empty?(q)
enqueue(q, :y)
enqueue(q, :z)
p dequeue(q)
p dequeue(q)
p dequeue(q)
p empty?(q)