データ構造

アルゴリズム及び実習 7 馬青 1

表探索 定義表探索とは 表の形で格納されているデータの中から条件に合ったデータを取り出してくる操作である 但し 表は配列 ( 連結 ) リストなどで実現できるので 以降 表 の代わりに直接 配列 や リスト などの表現を用いる場合が多い 表探索をただ 探索 と呼ぶ場合が多い 用語レコード : 表の中にある個々のデータをレコード (record) と呼ぶ フィールド : レコードが名前と生年月日などで構成されているとすれば 名前と生年月日などはそれぞれフィールド あるいは項目と呼ぶ キー : 探索しようとするフィールドをキーと呼ぶ 探索キー : 探索しようとするキーを探索キー あるいは目的キーと呼ぶ 2

探索キー キー ( 注目しているフィールド ) 表探索 龍谷太郎 1980.8.8 077-111-1111 トヨタ 瀬田花子 1990.1.1 077-222-2222 キャノン レコード 大津次郎 1976.5.5 077-333-3333 日立 フィールド ( 項目 ) 滋賀三郎 1983.10.2 077-444-444 富士通 京都四郎 1954.11.7 075-111-1111 ソニー 3

表探索 一般的に 探索方法はそのデータ構造により異なる 数値データがランダムに並んでいる表構造のデータでは これを素朴にデータのはじめから順に探索する線形探索法がある 一方 数値データや文字データは データそのものに大小関係があり データを大小の順に並べ替えることのできる場合の表探索には 比較的効率のよい 2 分探索法がある さらに 探索キーそのものによって保存場所を決めるハッシュ法がある 4

表探索のほか テキストの中から文字列を探索するには 力任せ法や KMP 法 BM 法など文字列探索法がある グラフや木構造をもつデータの探索には 深さ優先探索 幅優先探索などグラフ探索がある 5

線形探索法 データを 1 つ 1 つ順にはしから調べていく方法である 6

線形探索法 アルゴリズム入力 : 配列 a:a[0],,a[n-1] 探索キー x 出力 : 探索キー x が a の中の位置 p( ない場合 -1) 補助 :i? 計算量 :O(n) 7

2 分探索法 2 分探索法は 大きさの順にソートされた配列から探索キーを探す方法である 具体的には まず配列を二つに分け 探索キーが配列の前半にあるか後半にあるかを調べる もし前半にあるなら 前半をさらに2つに分け そのどちらにキーがあるかを調べる 後半にある場合も同様である このような探索を繰り返して探索キーの位置を求める 8

演習問題 1 n 個の整数データが格納されている配列 a に対し 整数データ x が配列 a の前半にあるか後半にあるか または存在しないかの関数 int pos1(int n, int a[], int x) を作成しなさい ただし 前半にあれば値 0 を 後半にあれば 1 を 存在していなければ -1 を返す また 中央位置 m を [0+(n-1)]/2 で計算するとして (0,m) と (m+1, n-1) をそれぞれ前半 後半と見なす 9

2 分探索法の手順 (1/2) ステップ 1: データ範囲の初期化 ( 例 ) 1 2 3 4 5 6 7 8 i(0) j(7) ステップ2: 中央データの位置を決める ( 例 ) 1 2 3 4 5 6 7 8 i(0) m(3) j(7) 10

2 分探索法の手順 (2/2) ステップ 3: 探索キーと中央データとを比較する 3.1 等しければ中央位置を出力し 処理終了 3.2 探索キーの方が小さければ データ範囲を前半に絞る ( 例 ) 1 2 3 4 5 6 7 8 i j 3.3 探索キーの方が大きければ データ範囲を後半に絞る ( 例 ) 1 2 3 4 5 6 7 8 i j ステップ 2,3 を i j が成立しなくなるまで繰り返す 11

計算量 ステップ 2,3 の繰り返し回数 ( 分割回数 ) の上限は log 2 n(n/2 k =1 なので k= log 2 n) なので 計算量は log 2 n となる 12

演習問題 2 整数配列 a の部分配列 a[f],...,a[t](f<t) に対し 整数データ x がその部分配列中央データと一致すれば中央位置を 中央データより小さければ中央より一つ左の位置を 中央データより大きければ中央より一つ右の位置を返す関数 int pos2(int f, int t, int a[], int x) を作成しなさい 13

2 分探索法のアルゴリズム 入力 : 昇順にソートされた配列 a:a[0],...,a[n-1] 探索キー x 出力 : 探索キー x が a の中の位置 p( ない場合 -1) 補助 :i,j,m( 中央位置用 ) 1 { 初期設定 }i=?, j=?, p=-1 とおく 2 条件? が満たされる間 次の操作を繰り返す 2-1 { 中央位置を求める }? 2-2 {x と中央データと比較し 等しければ p にその位置を与え 処理 2 を抜け出す そうでなければ i か j の値を変更することによってデータ範囲を絞る }? 14

演習問題 3( 総合問題 ) 以下のようなデータファイルがあったとして 2 分探索法を用いて探索プログラムを作成しなさい meibo.dat ファイル名 Taka 60 Nakata 70 Kobayashi 65 Kimura 100 Murata 30 Koyama 98 Akiba 55 Abe 100 15

実行例 $./a.out Data is sorted... Input the name to search: Kimura Search Result: Kimura 100 Input the name to search: Yamada Search Result: Not found!!! Input the name to search: Ctrl-D $ 16

その前に ( ウオーミングアップ ) 以下のようなデータファイルがあったとして 2 分探索法を用いて探索プログラムを作成しなさい meibo.dat ファイル名 Taka Nakata Kobayashi Kimura Murata Koyama Akiba Abe 17

実行例 $./a.out Data is sorted... Input the name to search: Kimura Search Result: Kimura Input the name to search: Yamada Search Result: Not found!!! Input the name to search: Ctrl-D $ 18

ヒント 1 これまでファイルの読み込みは./a.out<meibo.dat というようにやってきたが キーボードからも同時に入力したいとき ( 今回は探索キーの入力 ) は難しい これは プログラムの中を以下のように書くことで解決できる FILE *fp; fp=fopen( meibo.dat, r ); fscanf(fp,...,...); fclose(fp); このような場合 実行は./a.out のみで OK 19

ヒント 2 2 分探索法を用いるためにはデータをまずソートしておく必要がある ということはプログラムはソート関数と探索関数からなる 20

ヒント 3 名前は文字列として たとえば char s[64]( 複数の文字列を扱う場合は char s[100][64]) で宣言して使う また 文字列変数 s1 と s2 の大小比較は if(s1<s2) ではなく if(strcmp(s1,s2)<0) である ウオーミングアップ問題は複数の文字列を扱うので たとえばchar s[100][64] のように宣言する 演習問題 3は以下のような構造体を導入すると便利 typedef struct data{ char name[nchar]; int score; }DATA; 21

この授業内でやること 1 以下の数値をソートする選択ソート関数 void SelectionSort(int n, int a[]) を名前 ( 文字列 ) でソートするvoid SelectionSort(int n, char a[][64]) に修正すること void SelectionSort(int n, int a[]) { int min, tmp; int i, j, no; for(i=0; i<n-1; i++){ min=a[i]; no=i; for(j=i+1; j<n; j++) if(min>a[j]) {min=a[j]; no=j;} if(no!= i){ tmp=a[i]; a[i]=a[no]; a[no]=tmp;} } } 22

この授業内でやること 2 以下の選択ソート関数 void SelectionSort(int n, int a[]) をヒント 3の構造体のnameメンバーでソートするvoid SelectionSort(int n, DATA a[]) に修正すること void SelectionSort(int n, int a[]) { int min, tmp; int i, j, no; for(i=0; i<n-1; i++){ min=a[i]; no=i; for(j=i+1; j<n; j++) if(min>a[j]) {min=a[j]; no=j;} if(no!= i){ tmp=a[i]; a[i]=a[no]; a[no]=tmp;} } } 23

第 7 回実習課題 1. 線形探索を実現する関数 int LSearch(int n, int a[], int x) を作成し その動作を確認できるプログラム (ex07-lsearch.c) を作成しなさい ただし n はデータの個数 a[] はデータ配列である 2.2 分探索を実現する関数 int BSearch(int n, int a[], int x) を作成し その動作を確認できるプログラム (ex07-bsearch.c) を作成しなさい ただし n はデータの個数 a[] はデータ配列である また 探索過程において 探索範囲内のデータを示しなさい 3. 演習問題 3のプログラム (ex07-add.c) を作成しなさい ( 発展課題 ) 24

課題 2 の実行結果./a.out Input the data (end with Ctrl-D) 1 2 3 4 5 6 7 8 9 Input the search key: 8 the data to be searched 1 2 3 4 5 6 7 8 9 the data to be searched 6 7 8 9 the data to be searched 8 9 Search result: 7./a.out Input the data (end with Ctrl-D) 1 2 3 4 5 6 7 8 9 Input the search key: 10 the data to be searched 1 2 3 4 5 6 7 8 9 the data to be searched 6 7 8 9 the data to be searched 8 9 the data to be searched 9 Search result: -1 25