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

指定された座席に座り、出
席メールを送信して下さい。
 講義開始後30分以上経
過した出席メールは欠席
扱いになります。
データ構造とアルゴリズム論
第2章 配列(構造)を
使った処理
平成16年10月5日
森田 彦
配列(構造)とは?(復習)
 A[1],A[2],・・・,のように、カッコ内の数字(添
え字)で変数の値を指定できるデータ構造
例 1,5,3,9,7を配列変数に保存
5 3 9 7
[1] [2] [3] [4] [5]
A 1
大きさが「5」の配列変数Aを
1個用意。
※一般の変数の場合
1 5 3 9 7
A1 A2 A3 A4 A5
5個の変数を用意する。
本章(本日)の学習のねらい
① 配列を使った(典型的な)処理を学習す
る。
② 処理内容(アルゴリズム)に応じて配列
を利用できるようになる。
注意:配列を理解できなければ、次回以降
の講義内容を理解できません。
2-1 配列の利点
 例 5個の数値を順に表示させる。
<5個の変数>
<1個の配列変数>
開始
開始
A1を表示
i←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.92~
93)で学習した内容です。
2-3 配列の応用-最大・最小
 4つの正の整数が変数A1~A4に入って
いる。この中の最大値を求める。
例:1,5,3,8の場合
1.A1とMAXの比較
2.A2とMAXの比較
3.A3とMAXの比較
4.A4とMAXの比較
終了!MAXに最大値が入っている。
1
A1
5
A2
3
A3
勝ち抜き戦方式
8
A4
8
1
0
5
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
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]
挿
入
完
了
!
流れ図で表すと・・・
開始
mの入力
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】(p.24)
【基礎課題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]に2を挿入する。
スタート
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]に2を代入
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/2に第1回目のテストを実施します。
 要領は前期と同じペーパーテスト形式で
す。
 試験欠席の場合は、単位を取得できませ
ん。→十分注意してください。
 詳細は、追ってアナウンスします。
 成績=2回のテストの平均点+応用課題
数