データ構造

(1)

アルゴリズム及び実習⑦

馬青

(2)

表探索

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

(3)

表探索

龍谷太郎

_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

ソニー

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

(4)

表探索

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

(5)

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

力

任せ法

や

KMP法

、

BM法

など

文字列探索法があ

る。

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

深さ

優先探索

、

幅優先探索

などグラフ探索がある。

表探索のほか

(6)

線形探索法

(7)

線形探索法

アルゴリズム

入力：

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

探索キーx

出力：

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

補助：i

？

計算量：O(n)

(8)

２分探索法

２分探索法は、

大きさの順にソートされた配列

から探索キーを探す方法

である。

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

キーが配列の

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

を調べ

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

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

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

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

(9)

演習問題１

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

をそれぞれ前半、後半と

見なす。

(10)

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

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

（例）

_{1 2 3 4 5 6 7 8}

i(0)

j(7)

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

（例）

_{1 2 3 4 5 6 7 8}

(11)

ステップ３：探索キーと中央データとを比較する。 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/2）

(12)

計算量

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

の上限はlog

₂

n（n/2

k

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

2

n）

(13)

演習問題２

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

し、整数データ

_x

がその部分配列中央デー

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

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

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

位置を返す関数

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

(14)

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

入力：_{昇順にソートされた配列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の値

(15)

演習問題３（総合問題）

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

(16)

実行例

$

./a.out

Data is sorted ...

Input the name to search:

Kimura

Search Result: Kimura 100

Input the name to search:

Yamada

(17)

その前に（ウオーミングアップ）

• 以下のようなデータファイルがあったとして、２分探索法を用いて探索プログラムを作成しなさい。 meibo.dat ・・・・ファイル名 Taka Nakata Kobayashi Kimura Murata Koyama Akiba Abe

(18)

実行例

$

./a.out

Data is sorted ...

Input the name to search:

Kimura

Search Result: Kimura

Input the name to search:

Yamada

(19)

ヒント①

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

./a.out<meibo.dat

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

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

しい。これは、プログラムの中を以下のように書く

ことで解決できる。

FILE *fp; fp=fopen(“meibo.dat”, “r”); fscanf(fp, “...”, ...); fclose(fp);

このような場合、実行は

_のみでOK

(20)

ヒント②

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

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

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

(21)

ヒント③

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

char s[64]

（複数の

文字列を扱う場合は

_{char s[100][64]}

）、で宣言し

て使う。また、文字列変数s1とs2の大小比較は

if(s1<s2)

ではなく、

if(strcmp(s1,s2)<0)

である。

• ウオーミングアップ問題は複数の文字列を扱う

ので、たとえば

_{char s[100][64]}

のように宣言する。

• 演習問題３は以下のような構造体を導入すると

便利。

typedef struct data{ char name[NCHAR];

(22)

この授業内でやること①

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

(23)

この授業内でやること②

以下の選択ソート関数void SelectionSort(int n, int a[])をヒント

③の構造体の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){

(24)

第７回実習課題

１．線形探索を実現する関数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[]はデータ配列である。

また、探索過程に

(25)

課題２の実行結果

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

データ構造

アルゴリズム及び実習⑦

馬 青

表探索

表探索

龍谷太郎

1980.8.8

トヨタ

瀬田花子

1990.1.1

キャノン

大津次郎

1976.5.5

日立

滋賀三郎

1983.10.2

富士通

京都四郎

1954.11.7

ソニー

表探索

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

力

任せ法

や

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

を

、存在していなければ

馬青

_1980.8.8

_1990.1.1

_1976.5.5

_1983.10.2

_1954.11.7

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

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

_x

_a

_{int pos1(int n, int}

_-1

_(0,m)

_{(m+1, n-1)}

_{1 2 3 4 5 6 7 8}

_{1 2 3 4 5 6 7 8}

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

_x

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

_のみでOK