アルゴリズムとデータ構造 補足資料4-2 「線形探索」

Presentation on theme: "アルゴリズムとデータ構造 補足資料4-2 「線形探索」"— Presentation transcript:

1 アルゴリズムとデータ構造 補足資料4-2 「線形探索」
横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

2 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 void search( int x ) 仮引数 int x （自動）変数 int i i != 10 && a[i] != x false true i++; true false i != 10 有 無 戻り値なし（void）

3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 3 ) 仮引数 int x 3 （自動）変数 int i i != 10 && a[i] != x false true i++; true false i != 10 有 無 戻り値なし（void）

4 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 3 ) != → false 仮引数 int x 3 （自動）変数 int i 0 != 10 && a[0] != x false true i++; true false i != 10 有 無 戻り値なし（void）

5 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 3 ) != → false 仮引数 int x 3 （自動）変数 int i 0 != 10 && a[0] != x true false false true i++; true false i != 10 有 無 戻り値なし（void）

6 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 3 ) != → false 仮引数 int x 3 （自動）変数 int i 0 != 10 && a[0] != x true false false true i++; true false 0 != 10 有 無 戻り値なし（void）

7 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 5 ) 仮引数 int x 5 （自動）変数 int i i != 10 && a[i] != x false true i++; true false i != 10 有 無 戻り値なし（void）

8 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 5 ) != → true 仮引数 int x 5 （自動）変数 int i 0 != 10 && a[0] != x false true i++; true false i != 10 有 無 戻り値なし（void）

9 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 3 ) != → true 仮引数 int x 5 （自動）変数 int i 0 != 10 && a[0] != x true false true true i++; true false i != 10 有 無 戻り値なし（void）

10 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 3 ) 仮引数 int x 5 （自動）変数 int i 1 i != 10 && a[i] != x false true i++; true false i != 10 有 無 戻り値なし（void）

11 i=1 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 5 ) != → true 仮引数 int x 5 （自動）変数 int i 1 1 != 10 && a[1] != x false true i++; true false i != 10 有 無 戻り値なし（void）

12 i=1 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 5

13 i=2 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 5

14 i=3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 5

15 i=4 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 5

16 i=5 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 5

17 i=6 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 == 仮引数 int x 5

18 i==6 にあった！ 「5: みつかりました」 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
54 16 8 9 1 5 22 19 60 == 仮引数 int x 5 i==6 にあった！ 「5: みつかりました」

19 i=0 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 search( 30 ) 仮引数 int x 30 （自動）変数 int i i != 10 && a[i] != x false true i++; true false i != 10 有 無 戻り値なし（void）

20 i=1 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

21 i=2 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

22 i=3 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

23 i=4 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

24 i=5 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

25 i=6 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

26 i=7 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

27 i=8 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

28 i=9 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 3 54 16 8 9 1 5 22 19 60 仮引数 int x 30

29 i==10 （参照データなし！） →「30: みつかりませんでした」 a[0] a[1] a[2] a[3] a[4] a[5] a[6]
54 16 8 9 1 5 22 19 60 仮引数 int x 30 i==10 （参照データなし！） →「30: みつかりませんでした」