データ構造とアルゴリズム論

データ構造とアルゴリズム論
第２章配列（構造）を
使った処理
平成27年4月24日
森田彦
配列（構造）とは？（復習）
 A[1]，A[2]，・・・，のように、カッコ内の数字（添
え字）で変数の値を指定できるデータ構造
例 1,5,3,9,7を配列変数に保存
５３９７
[1] [2] [3] [4] [5]
A 1
大きさが「５」の配列変数Aを
1個用意。
※一般の変数の場合
１５３９７
A1 A2 A3 A4 A5
5個の変数を用意する。
本章（本日）の学習のねらい
① 配列を使った（典型的な）処理を学習す
る。
② 処理内容（アルゴリズム）に応じて配列
を利用できるようになる。
注意：配列を理解できなければ、次回以降
の講義内容を理解できません。
今週の課題提出率が重要
80
75
70
65
60
55
50
45
40
73.96
第2章までの提出状況
2012年度第1回テスト vs 応用提出状況
61.20
全課題
未提出あり
テスト平均点
テスト平均点
2012年度第1回テスト vs 基礎提出状況
80
75
70
65
60
55
50
45
40
74.76
第2章までの提出状況
51.83
9割以上
8割未満
今週の課題提出率が成績に大きく影響！
2-1 配列の利点
 例 5個の数値を順に表示させる。
＜5個の変数＞
＜１個の配列変数＞
開始
開始
A1を表示
ｉ←1
A2を表示
A3を表示
A4を表示
A5を表示
終了
i≦100
i≦5
Yes
A[i] を表示
No
終了
i←i+1
繰り返し処理の場合 → 配列を利用す
ると便利！
配列（利用）の利点
 拡張が容易。上の例の場合、データ数が
100になっても「5→100」に変えるだけで良
い。
 処理内容をコンパクトに記述できるので、
見通しが良くなる。→アルゴリズムの構造
がはっきりとする。
2-2 Java言語による配列の宣言
 p.14～15を熟読して下さい。
 ここは「プログラミング」テキスト「4-12 配
列」（p.97～100、2012年度版：p.95～98）で
学習した内容です。
0から始まる事に注意！
配列の添え字が
int[] A=new int[10];
と配列Aを宣言した場合・・・
A[0], A[1], A[2], ･･･, A[9]が確保される。
2-3 配列の応用－最大・最小
 4つの正の整数が変数A1～A4に入って
いる。この中の最大値を求める。
例：1,5,3,8の場合
１．A1とMAXの比較
２．A2とMAXの比較
３．A3とMAXの比較
４．A4とMAXの比較
終了！MAXに最大値が入っている。
１
A1
５
A2
３
A3
勝ち抜き戦方式
８
A4
８
１
０
５
MAX
流れ図で表すと・・・
開始
A3＞MAX
MAX←0
A1＞MAX
No
No
Yes
MAX←A3
Yes
MAX←A1
A2＞MAX
A4＞MAX
No
Yes
MAX←A4
Yes
MAX←A2
MAX の表示
終了
No
【基礎課題2-1】
開始
プリントp.17
配列A[i](i=1～4）を用いて表すと・・・
MAX←0
ループ
i:1,1,4
No
A[i]>MAX
Yes
MAX←A[i]
ループ
MAX の表示
終了
 拡張が容易：整数の数
が増えてもループの終値を
変更するだけで良い。
記述がコンパクトに：繰り
返し処理をループ内に一つ
だけ記述するだけで済む。
理解度チェック→【基礎課題2-2 】、
【基礎課題2-3 】、【基礎課題2-4】
プログラムの作成
2-4 配列要素の挿入・削除
 例：配列A[1]～A[N]にデータa1～aNが入ってい
る。→配列要素のm番目にデータXを挿入する。
a1
a2
A[1]
A[2]
・・・
am
am+1
A[m] A[m+1]
X
a1
a2
A[1]
A[2]
・・・
・・・
aN
A[N]
am以降を右にずらす
am
aam+1
m
･･･
A[m] A[m+1]
aaN-1
N
aN
A[N]
A[N+1]
一つ追加
a1
a2
A[1]
A[2]
・・・
X
am
am+1
A[m] A[m+1] A[m+2]
・・・
aN
A[N+1]
挿
入
完
了
！
流れ図で表すと・・・
開始
ｍの入力
a1
a2
A[1]
A[2]
A[i+1] ←A[i]
ループ
A[m] ←X
終了
am
am+1 ・・・
A[m] A[m+1]
aN
A[N]
X
・・・
a1
a2
A[1]
A[2]
ループ
i:N,-1,m
・・・
右
に
ず
ら
す
。
am
aam+1
m
A[m] A[m+1]
・・・
・・・
aaN-1
N
aN
A[N]
A[N+1]
A[N]→A[N+1]
A[N-1]→A[N]
・・・
A[m]→A[m+1]
A[m]→A[m+1]から始める
と、どうなるか？
【基礎課題2-5】（p.25）
【基礎課題2-5】具体例で考えると・・・
1
5
3
9
7
A[1]
A[2]
A[3]
A[4]
A[5]
1
5
3
2
9
7
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[4]に２を挿入する
場合を考える。
スタート
1
5
3
9
7
A[1]
A[2]
A[3]
A[4]
A[5]
1
5
3
9
9
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
1
5
3
9
9
9
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
1
5
3
2
9
9
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]
A[6]
A[4]→A[5]
A[5]→A[6]
A[4]に２を代入
A[m+1]以降の全ての配列要素にA[m]の値が入ってしまう
2-5 添え字の参照
開始
Gusu←0
Kisu←0
ループ
i:1,1,N
Y ←Data[i] % 2
Y=0
Yes
Gusu←Gusu+1
ループ
終了
 例：配列Data[1]～Data[N]にデータ
（整数）が入っている。この中で、
偶数および奇数の個数を数える。
Gusu
Kisu
No
Kosu[0]：偶数の個数
Kosu[1]：奇数の個数
を導入すると・・・
Kisu←Kisu+1
開始
Kosu[ ]内には、何が入る？
初期化ループ
i:0,1,1
Y=0： Kosu[0]←Kosu[0]+1
Y=1： Kosu[1]←Kosu[1]+1
Kosu[i]←0
となることに注目すると・・・
初期化ループ
ループ
i:1,1,N
Y ←Data[i] % 2
Kosu[
]←Kosu[ ]+1
Kosu[Y]←Kosu[Y]+1
ループ
終了
選択構造が不要になった！
データ構造の変更→アルゴ
リズムの変更！
p.29～p.30を熟読して【基礎課題2-7】へ
 演習にとりかかってください。
 少なくとも、基礎課題のチェックは終えること。
 演習の時間内に基礎課題を終了できなかった
場合は、必ず次回までに課題を終えて
おいて下さい。基礎課題を翌週に持ち越すと、
本科目の修学が困難になります。
 応用課題まで含めて全ての課題のチェックを終
えた人は退出して結構です。

Download Report