データ構造

アルゴリズム及び実習⑦

表探索

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

表探索

龍谷太郎

_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

ソニー

レコード フィールド （項目） キー （注目してい るフィールド） 探索キー

表探索

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

テキストの中から文字列を探索するには、

力任

せ法

や

KMP法

、

BM法

など

文字列探索

法がある。

グラフや木構造をもつデータの探索には、

深さ

優先探索

、

幅優先探索

など

グラフ探索

がある。

線形探索法

線形探索法

アルゴリズム

入力：

_{配列a：a[0],…,a[n-1]}

探索キーx

出力：

_{探索キーxがaの中の位置p（ない場合-1）}

補助：i

？

計算量：O(n)

二分探索法

二分探索法は、

ソートされた配列から探索

キーを探す方法

である。

具体的には、まず配列を二つに分け、探索

キーが配列の

前半にあるか後半にあるか

を調べ

る。もし前半にあるなら、前半をさらに２つに分け、

そのどちらにキーがあるかを調べる。後半にある

場合も同様である。このような探索を繰り返して

探索キーの位置を求める。

演習問題１

• 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)}

をそれぞれ前半、後半と

する。

二分探索法の手順（1/2）

ステップ１: データ範囲の初期化

（例）

_{1 2 3 4 5 6 7 8}

i

(0)

j

(7)

ステップ２：中央データの位置を決める

（例）

_{1 2 3 4 5 6 7 8}

i(0)

m

(3) j(7)

ステップ３：探索キーと中央データとを比較する。 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 ステップ２，３を_i≦jが成立しなくなるまで繰り返す。

二分探索法の手順（2/2）

計算量

• ステップ２，３の繰り返し回数（分割回数）

の上限はlog

₂

n（n/2

k

_{=1なので、k= log}

2

n）

演習問題２

• 整数配列aの部分配列a[f],...,a[t](f<t)に対

し、整数データ

_x

がその部分配列中央デー

タと一致すれば中央位置を、中央データよ

り小さければ中央より一つ左の位置を、中

央データより大きければ中央より一つ右の

位置を返す関数

_{int pos2(int f, int t, int a[],}

二分探索法のアルゴリズム

入力：_{昇順にソートされた配列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の値 を変更することによってデータ範囲を絞る}

演習問題３

• 以下のような人名と数値のペアで構成されるデータファイ ルがあったとして、２分探索法を用いて、人名をキーとす る探索プログラムを作成しなさい。 meibo.dat ・・・・ファイル名 Taka 60 Nakata 70 Kobayashi 65 Kimura 100 Murata 30 Koyama 98 Akiba 55 Abe 100

実行例

$

./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

準備①：文字列のソート

• ２分探索法を用いるためにはデータをまず

ソートしておく必要がある。ということはプロ

グラムはソート関数と探索関数からなる。

• しかもソートはこれまでと違い、文字列の

ソートとなる。

文字列のソート

• 以下の数値をソートする選択ソート関数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){

文字列の復習

• 名前は文字列として、たとえば

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

準備②：文字列の探索

• 以下の数値を二分探索する関数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;

準備③

• これまでファイルの読み込みは

./a.out<meibo.dat

というようにやってきたが、キーボードからも同時

に入力したいとき（今回は探索キーの入力）は難

しい。

例１

• 以下のipt.datファイルをopt.datファイルに

変換するプログラムを書きなさい。ただし、

ipt.datの中の空白は空白かタブであり、

opt.datの中の名前と点数の間は1個のタブ

である。

データ

opt.dat

Tanaka 79

Nakata 73

Hashimoto 89

Nakahashi 67

Nakamoto 99

ipt.dat

Tanaka 79

Nakata

73

Hashimoto 89

Nakahashi

67

Nakamoto

99

プログラム

#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); } 従来

例1の実行

./a.out<ipt.dat>opt.dat

入力ファイルや出力ファイルが複数の場合や、

他の標準入力がある場合は対処できなくなる！！

プログラム

#include <stdio.h> #define N 64 main() { char s1[N], s2[N];

FILE *fp_ipt, *fp_opt;

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); } NEW 定義を調べると、fscanf()の戻 り値がEOFはエラーのみの意 味。安全のため、fgetsと sscanfのペアにしたほうがよ いかも。（こちらの環境では問 題なく使えたのだが）

例1の実行

./a.out<ipt.dat>opt.dat

例２

• 以下のipt1.datファイルとipt2.datを併合し、

opt.datファイルに書き出すプログラムを書

きなさい。

例２

opt.dat

Tanaka 79 Nakata 73 Hashimoto 89 Nakahashi 67 Nakamoto 99

ipt1.dat

Tanaka 79

Nakata 73

ipt2.dat

hashimoto 89

Nakahashi 67

Nakamoto 99

例２

#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);

ファイルのオープン／クローズ関数

ファイルは読み書きを行う前にオープンし、使い

終わったらクローズする。

関数名 使い方 返値 機能 fopen FILE *fp; fp=fopen(file, mode); ≠NULL：成功 =NULL:エラー ファイルをmodeの 状態でオープンす る fclose FILE *fp; =0: 成功 fpで示すファイル をmodeの状態で ファイル名 ファイルポインタ変数を宣言

ファイルオープンのmode

mode 動作

ファイルが

存在しない

場合

ファイルが存

在した場合

“r”

ファイルから読み込

み

エラー

“w”

ファイルへ書き出し 作成する

内容は失わ

れる

“a”

ファイルへ追加書き

出し

作成する

ファイルの最

後から追加

文字（バイト）の入出力関数

関数名

使い方

機能

fgetc int c; FILE *fp; c=fgetc(fp); (EOF:エラーまたはEOF) fpが示す位置から１ 文字を読み込み、 ファイルポインタを１ つ進める。 fputc int c; FILE *fp; fputc(c, fp); fpが示す位置に変 数cを書き出し、ファ イルポインタを１つ 進める。

文字列の入出力関数

関数名 使い方

機能

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

フォーマット化入出力関数

関数名 使い方

機能

fscanf FILE *fp; fscanf(fp, “...”, ...); （EOF：エラー） scanfと同じ。ただし、標準 入力からでなくファイルから。 fprintf FILE *fp; fprintf(fp, “...”,...); printfと同じ。ただし、標準 出力でなくファイルに書き 出す。

その他の関数

関数名 書式

返値

機能

feof int feof(fp); 0:ファイルの 終わりでない ≠0:ファイルの 終わり

fpで示すファイルがエンドオブファ イルかどうかを調べる。

fflush int fflush(fp); 0:エラーなし EOF:エラー

fpで示すバッファをファイルに書き 出す。

fseek int fseek(fp, offset, mode); 0:実行終了 ≠0:エラー fpで示すファイルポインタをmode からoffsetバイト移動する。 0:ファイルの始め 1:現在のファイルポインタの位置 2:エンドオブファイル

rewind int rewind(fp); 0:実行終了 ≠0:エラー

fpで示すファイルポインタをファイ ルの先頭に移動する。

第７回実習課題

１．線形探索を実現する関数int LSearch(int n, int a[],

int x)を作成し、その動作を確認できるプログラム

（

_{ex07-lsearch.c}

_{）を作成しなさい。ただし、nはデータ}

の個数、a[]はデータ配列である。

２．二分探索を実現する関数int BSearch(int n, int a[],

int x)を作成し、その動作を確認できるプログラム

（

_{ex07-bsearch.c}

_{）を作成しなさい。ただし、nはデータ}

の個数、a[]はデータ配列である。

また、探索過程に

おいて、探索範囲内のデータを示しなさい。

第７回実習課題

３．文字列をソートする選択ソート関数void

SelectionSort(int n, char a[][64])を作成し、その動作

を確認できるプログラム（

_{ex07-ssort-str.c}

）を作成しな

さい。

４．文字列を探索する二分探索関数int BSearch(int n,

char a[][64], char x[])を作成し、その動作を確認でき

るプログラム(

ex07-bsearch-str.c

)を作成しなさい（

発

展課題

）。

５．演習問題３のプログラム（

_ex07-add.c

）を作成しなさ

い（

発展課題

）。

課題２の実行結果

./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