探索についての復習 ・逐次探索法 番兵を用いない場合 番兵を用いる場合 ・２分探索法 プログラムはホームページに

Presentation on theme: "探索についての復習 ・逐次探索法 番兵を用いない場合 番兵を用いる場合 ・２分探索法 プログラムはホームページに"— Presentation transcript:

1 探索についての復習 ・逐次探索法 番兵を用いない場合 番兵を用いる場合 ・２分探索法 プログラムはホームページに
記載されているものに従うこととする。

2 逐次探索法 Key: keyにkintetsuが入力されたとき， 2 1 i= a[]
1 i= a[] Seibu 1 Kintetsu 2 Daiei 3 Ham 4 Lotte 5 Orix 6 Kintetsu Kintetsu Kintetsu 一致しない　　―＞　　i++ ( i<Nを常にチェック ) 一致しない　　―＞　　i++ ( i<Nを常にチェック ) 一致した！　　―＞　　探索終了 i=2のときに終了したので２番目の レコードの名前（a[2].name）を表示

3 逐次探索法 Key: keyにkintetsuが入力されたとき， 1 2 i= a[]
char key[20]; printf("Search Data ? "); scanf("%s",key); 1 2 i= a[] Seibu 1 Kintetsu 2 Daiei 3 Ham 4 Lotte 5 Orix 6 Kintetsu Kintetsu Kintetsu while(i<N && strcmp(key,a[i].name)!=0) 一致しない　　―＞　　i++ ( i<Nを常にチェック ) 一致しない　　―＞　　i++ ( i<Nを常にチェック ) 一致した！　　―＞　　探索終了 printf("%s %d",a[i].name,a[i].order); i=2のときに終了したので２番目の レコードの名前（a[2].name）を表示

4 逐次探索法(番兵) Key: keyにkintetsuが入力されたとき， 1 2 i= a[]
1 2 i= a[] Seibu 1 Kintetsu 2 Daiei 3 Ham 4 Lotte 5 Orix 6 Kintetsu 6 終了判定の 見張り役 Kintetsu Kintetsu Kintetsu 一致しない　　―＞　　i++ ( i<Nは確認しない ) 一致した！　　―＞　　探索終了 一致しない　　―＞　　i++ ( i<Nは確認しない ) i=2のときに終了したので２番目の レコードの名前（a[2].name）を表示

5 逐次探索法(番兵) Key: keyにkintetsuが入力されたとき， 2 1 i= a[]
char key[20]; printf("Search Data ? "); scanf("%s",key); 2 1 i= a[N].name=key; a[] Seibu 1 Kintetsu 2 Daiei 3 Ham 4 Lotte 5 Orix 6 Kintetsu 6 終了判定の 見張り役 Kintetsu Kintetsu Kintetsu while(strcmp(key,a[i].name)!=0) 一致しない　　―＞　　i++ ( i<Nは確認しない ) 一致しない　　―＞　　i++ ( i<Nは確認しない ) 一致した！　　―＞　　探索終了 printf("%s %d",a[i].name,a[i].order); i=2のときに終了したので２番目の レコードの名前（a[2].name）を表示

6 2分探索法 mid=(low+high)/2=(5+6)/2=11/2=5 mid=(low+high)/2=(5+9)/2=14/2=7
初期データ a[]:　東海地区のテレビチャンネル 2分探索法 low Key:31 low low high high 1 3 5 9 11 25 31 33 2 4 6 7 35 8 37 1 flag flag a[] mid=(low+high)/2=(5+6)/2=11/2=5 mid=(low+high)/2=(5+9)/2=14/2=7 mid=(low+high)/2=(0+9)/2=9/2=4 mid=(low+high)/2=(6+6)/2=12/2=6 a[mid]=a[7]=33 a[mid]=a[5]=25 < key=31 > key=31 low=mid+1=6 high=mid-1=6 a[mid]=a[4]=11 < key=31 low=mid+1=5 a[mid]=a[6]=31 =key=31 一致したのでFlagを1にして終了