TOP >> 一般知識 >> アルゴリズムとデータ構造
FutureMedia.jp

アルゴリズムとデータ構造

 プログラムを作成する上で重要になるアルゴリズムとデータ構造について学んでみましょう。

計算量

 ある仮想的なコンピュータを使ってアルゴリズムを実行した時、 どれくらいの時間がかかるかを、入力した大きさ『n』の関数として表現したものが計算量Oです。

線形探索法

 線形探索法(リニアサーチ)とは、配列を端から順番にスキャンしながらキーの比較を行う方法です。

二分探索法

 二分探索法(バイナリサーチ)とは、あらかじめキーの昇順(または降順)に 整列されている配列に対して、ある特定のキーを持つデータを探し出す探索法です。

ハッシュ法

 ハッシュ法は、キーの値から配列の添え字を得る関数(ハッシュ関数)を使って 高速に探索を行う方法で、データの個数によらずに挿入、探索、削除の操作を 実質的にO(1)(つまり一定時間)で行える優れたデータ構造です。

チェイン法

同じハッシュ値を持つデータを連結リストにつなぐという方式です。 チェイン法では、連結リストへのポインタをハッシュ表に登録します。

オープンアドレス法

衝突が発生した時に、ある手順に従って別のバケットにデータを格納します。 この手順のことを『再ハッシュ』と呼びます。 オープンアドレス法では、ハッシュ表のバケットにはデータそのものがセットされます。

ハッシュ関数

ハッシュ関数は、できる限りキーのすべてのビットがハッシュ値に影響を与えるようにします。 また、「キーの値を2乗してその中央をとる(平方採中法)」という方法によって、 かなり良好な結果が得られることが知られています。

データ構造

データ構造とは、抽象データ型に含まれるデータを具体的に表現したものです。

基本データ型

例えばC言語では、基本的なデータ型として、数値型(整数、文字、浮動小数点数)があります。 これらの基本データ型をベースにして、ポインタ、配列、構造体、共用体、関数を組み合わせて 任意のデータ型をプログラマが定義できます。

列挙型

列挙型は、あらかじめ取り得る値が限定されている型です。

配列と構造体

配列は、同じ型を持った要素を集めたものです。 配列の要素は、添え字によって識別します。 構造体は、異なる型を持つデータをひとまとめにしたものです。 一般的にはレコード構造と呼ばれる型になります。

ポインタ

ポインタは、他のデータへの参照を示すデータ型です。

配列

リスト

リストは、n個の要素を順番に並べたものです。 つまり、リストに含まれる要素は、順序付けされているということになります。 これを強調するために線形リストと呼ばれる事もあります。

スタック

スタックは、挿入と削除がともにリストの先頭でのみ行われるものです。

待ち行列

待ち行列(キュー)は、挿入が一方の端でのみ行われ、削除が反対の端でのみ行われるものです。

リスト

連結リスト

連結リストとは、リストに含まれる各要素をポインタによってつなぎ合わせたものです。

循環リスト

連結リストでは、それぞれの要素は、次の要素へのポインタを持っています。 最後の要素の場合には、次に来る要素がないので、NULLがセットされています。 ここで、NULLを最初の要素へのポインタへ変更したものが『循環リスト』です。

双方向リスト

次のセルへのポインタの他に、前のセルへのポインタを持たせて、 前後に自由にリストをたどることが出来るリストを『双方向リスト』といいます。

木構造

『木』または『木構造』とは、階層関係を表現するためのデータ構造です。

順序木と無順序木

「同じ親をもつ節は兄弟である」と定義すると、兄弟間で順序付けを行った木を『順序木』と呼びます。 また、あえて兄弟の間に順序をつけない木を『無順序木』と呼びます。

二分木

木構造の一種に『二分木』というものがあります。 二分木の定義は以下の通りです。

@空の木は二分木である
A次のいずれかを満足する節のみからなる木は、二分木である
 ・子を持たない
 ・左の子のみを持つ
 ・右の子のみを持つ
 ・左右2つの子を持つ

整列

整列(ソート)とは、レコードの集まりをキーの値の大小関係に従って並び換える操作です。 単調増加になるように並び換える事を『昇順』への整列、反対にキーが大きなものから小さなものへと 単調減少になるように並び換える事を『降順』への整列といいます。

整列アルゴリズム

バブルソート

バブルソートは、配列の後ろから先頭に向かってスキャンしていき、 もし隣り合う2つの要素の大小関係が逆であった場合にはそれを入れ替えるという単純なものです。

選択ソート

選択ソートは、整列されていない部分から最小の要素を選び出して それを先頭に持ってくるという手順を繰り返す方法です。

挿入ソート

挿入ソートは、配列のうち、一部分を整列済みの状態にしておき、 残りの要素を1つずつそのなかの適切な位置に挿入していく方法です。

copyright (C) 2009 FutureMedia.jp All Rights reserved. | 免責事項 | お問合せ | リンク