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

データ構造とアルゴリズム論
第２章配列（構造）を
使った処理
平成15年10月7日
森田彦
配列（構造）とは？
 A[1]，A[2]，・・・，のように、カッコ内の数字（添
え字）で変数の値を指定できるデータ構造
例 1,5,3,9,7を配列変数に保存
５３９７
[1] [2] [3] [4] [5]
A 1
大きさが「５」の配列変数Aを
1個用意。
※一般の変数の場合
１５３９７
A1 A2 A3 A4 A5
5個の変数を用意する。
本章（本日）の学習のねらい
① 配列を使った（典型的な）処理を学習す
る。
② 処理内容（アルゴリズム）に応じて配列
を利用できるようになる。
注意：配列を理解できなければ、次回以降
の講義内容を理解できません。
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を熟読して下さい。
 プリントの訂正（p.14）
double B[] = new double[]
double B[] = new double[20]
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】
開始
配列A[1]～A[4]を用いて表すと・・・
MAX←0
ループ
i:1,1,4
A[i]>MAX
Yes
MAX←A[i]
ループ
MAX の表示
終了
No
 拡張が容易：整数の数
が増えてもループの終値を
変更するだけで良い。
記述がコンパクトに：繰り
返し処理をループ内に一つ
だけ記述するだけで済む。
理解度チェック→【基礎課題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]
a1
a2
A[1]
A[2]
・・・
aN
A[N]
am以降を右にずらす
・・・
am
am+1
・・・
A[m] A[m+1] A[m+2]
・・・
X
am
am+1
A[m] A[m+1] A[m+2]
aN
A[N+1]
・・・
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
am+1
A[m] A[m+1] A[m+2]
・・・
aN
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】
2-5 添え字の参照
開始
Gusu←0
Kisu←0
 例：配列Data[1]～Data[N]にデータ
（整数）が入っている。この中で、
偶数および奇数の個数を数える。
ループ
i:1,1,N
Kosu[1]：偶数の個数
Kosu[2]：奇数の個数
Y ←Data[i] % 2
Y=0
Yes
Gusu←Gusu+1
ループ
終了
No
を導入すると・・・
Kisu←Kisu+1
開始
Kosu[ ]内には、何が入る？
初期化ループ
i:1,1,2
Y=0： Kosu[1]←Kosu[1]+1
Kosu[i]←0
Y=1： Kosu[2]←Kosu[2]+1
初期化ループ
となることに注目すると・・・
ループ
i:1,1,N
Y ←Data[i] % 2
Kosu[Y+1]←Kosu[Y+1]+1
Kosu[ ]←Kosu[ ]+1
ループ
終了
選択構造が不要になっ
た！
データ構造の変更→アルゴ
リズムの変更！
p.28～p.29を熟読して【基礎課題2-7】へ
テストのアナウンス
 11/4に第１回目のテストを実施します。
 要領は前期と同じペーパーテスト形式で
す。
 試験欠席の場合は、単位を取得できませ
ん。→十分注意してください。
 詳細は、追ってアナウンスします。
 成績＝２回のテストの平均点＋応用課題
数

Download Report