データ構造

アルゴリズム及び実習 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

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

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

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

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

二分探索法 二分探索法は ソートされた配列から探索キーを探す方法である 具体的には まず配列を二つに分け 探索キーが配列の前半にあるか後半にあるかを調べる もし前半にあるなら 前半をさらに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

二分探索法の手順 (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) ステップ 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

二分探索法のアルゴリズム 入力 : 昇順にソートされた配列 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

準備 1: 文字列のソート 2 分探索法を用いるためにはデータをまずソートしておく必要がある ということはプログラムはソート関数と探索関数からなる しかもソートはこれまでと違い 文字列のソートとなる 17

文字列のソート 以下の数値をソートする選択ソート関数 void SelectionSort(int n, int a[]) を文字列でソートする void SelectionSort(int n, char a[][64]) に修正すること void SelectionSort(int n, int a[]) { int i, j, tmp, min, 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;} } } 18

文字列の復習 名前は文字列として たとえばchar s[64]( 複数の文字列を扱う場合はchar s[100][64]) で宣言して使う また 文字列変数 s1とs2の大小比較は if(s1<s2) ではなく if(strcmp(s1,s2)<0) である 詳細は CPROのWebページの10 回目の講義資料を中心に復習するとよい http://www.math.ryukoku.ac.jp/~qma/education/c pro/index.html 19

準備 2: 文字列の探索 以下の数値を二分探索する関数 int BSearch(int n, int a[], int x) を 文字列を探索する関数 int BSearch(int n, char a[][64], char x[]) に修正すること int BSearch(int n, int a[], int x) { int i, j, m, p=-1; i=?; j=?; while(?){? } return p; } 20

準備 3 これまでファイルの読み込みは./a.out<meibo.dat というようにやってきたが キーボードからも同時に入力したいとき ( 今回は探索キーの入力 ) は難しい 21

ファイルの入出力 22

例 1 以下の ipt.dat ファイルを opt.dat ファイルに変換するプログラムを書きなさい ただし ipt.dat の中の空白は空白かタブであり opt.dat の中の名前と点数の間は 1 個のタブである 23

データ ipt.dat Tanaka 79 Nakata 73 Hashimoto 89 Nakahashi 67 Nakamoto 99 opt.dat Tanaka 79 Nakata 73 Hashimoto 89 Nakahashi 67 Nakamoto 99 24

従来 プログラム #include <stdio.h> #define N 64 main() { char s1[n], s2[n]; while(scanf( %s %s, s1, s2)!= EOF) printf("%s t%s n", s1, s2); } 25

従来 例 1 の実行./a.out<ipt.dat>opt.dat 入力ファイルや出力ファイルが複数の場合や 他の標準入力がある場合は対処できなくなる!! 26

NEW プログラム #include <stdio.h> #define N 64 main() { char s1[n], s2[n]; FILE *fp_ipt, *fp_opt; } 定義を調べると fscanf() の戻り値が EOF はエラーのみの意味 安全のため fgets と sscanf のペアにしたほうがよいかも ( こちらの環境では問題なく使えたのだが ) fp_ipt = fopen( ipt.dat, r ); fp_opt=fopen( opt.dat, w ); while(fscanf(fp_ipt, %s %s, s1, s2)!= EOF) fprintf(fp_opt, "%s t%s n", s1, s2); fclose(fp_ipt); fclose(fp_opt); 27

NEW 例 1 の実行./a.out<ipt.dat>opt.dat 28

例 2 以下の ipt1.dat ファイルと ipt2.dat を併合し opt.dat ファイルに書き出すプログラムを書きなさい 29

例 2 ipt1.dat Tanaka 79 Nakata 73 ipt2.dat hashimoto 89 Nakahashi 67 Nakamoto 99 opt.dat Tanaka 79 Nakata 73 Hashimoto 89 Nakahashi 67 Nakamoto 99 30

例 2 #include <stdio.h> #define N 64 main() { char line[n]; FILE *fp_ipt1, *fp_ipt2, *fp_opt; fp_ipt1=fopen( ipt1.dat, r ); fp_ipt2=fopen( ipt2.dat, r ); fp_opt=fopen( opt.dat, w ); while(fgets(line, N, fp_ipt1)!= NULL) fputs(line, fp_opt); while(fgets(line, N, fp_ipt2)!= NULL) fputs(line, fp_opt); fclose(fp_ipt1); fclose(fp_ipt2); fclose(fp_opt); } 31

ファイルのオープン / クローズ関数 ファイルは読み書きを行う前にオープンし 使い終わったらクローズする ファイルポインタ変数を宣言 ファイル名 関数名使い方返値機能 fopen FILE *fp; fp=fopen(file, mode); NULL: 成功 =NULL: エラー ファイルを mode の状態でオープンする fclose FILE *fp; int fclose(fp); =0: 成功 =EOF: エラー fp で示すファイルを mode の状態でクローズする 32

ファイルオープンの mode mode 動作 ファイルが 存在しない 場合 r ファイルから読み込み エラー ファイルが存在した場合 w ファイルへ書き出し 作成する 内容は失わ れる a ファイルへ追加書き出し 作成する ファイルの最後から追加 33

文字 ( バイト ) の入出力関数 関数名使い方機能 fgetc int c; FILE *fp; c=fgetc(fp); (EOF: エラーまたはEOF) fputc int c; FILE *fp; fputc(c, fp); fp が示す位置から 1 文字を読み込み ファイルポインタを 1 つ進める fp が示す位置に変数 c を書き出し ファイルポインタを 1 つ進める 34

文字列の入出力関数 関数名使い方 fgets #define N 64 char str[n]; FILE *fp; fgets(str, N, fp); (NULL: エラーまたはEOF) fputs char str[64]; FILE *fp; fputs(str, fp); 機能 fpが示す位置から文字列をstr[] に読み込む 文字は N 文字目まで 改行まで ファイルの終わりまでのいずれかの条件が満たされるまで読み込まれる fp が示す位置に文字列 str[] を書き出す 35

フォーマット化入出力関数 関数名使い方 機能 fscanf fprintf FILE *fp; fscanf(fp,...,...); (EOF: エラー ) FILE *fp; fprintf(fp,...,...); scanf と同じ ただし 標準入力からでなくファイルから printf と同じ ただし 標準出力でなくファイルに書き出す 36

その他の関数 関数名書式返値機能 feof int feof(fp); 0: ファイルの終わりでない 0: ファイルの終わり fflush int fflush(fp); 0: エラーなし EOF: エラー fseek int fseek(fp, offset, mode); 0: 実行終了 0: エラー rewind int rewind(fp); 0: 実行終了 0: エラー fp で示すファイルがエンドオブファイルかどうかを調べる fp で示すバッファをファイルに書き出す fpで示すファイルポインタをmode からoffsetバイト移動する 0: ファイルの始め 1: 現在のファイルポインタの位置 2: エンドオブファイル fpで示すファイルポインタをファイルの先頭に移動する 37

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

第 7 回実習課題 3. 文字列をソートする選択ソート関数 void SelectionSort(int n, char a[][64]) を作成し その動作を確認できるプログラム (ex07-ssort-str.c) を作成しなさい 4. 文字列を探索する二分探索関数 int BSearch(int n, char a[][64], char x[]) を作成し その動作を確認できるプログラム (ex07-bsearch-str.c) を作成しなさい ( 発展課題 ) 5. 演習問題 3 のプログラム (ex07-add.c) を作成しなさい ( 発展課題 ) 39

課題 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 40