080325 - genshiken @ ウィキ

080325

いつも更新が火曜ですみません。開き直って日付を火曜にしました。
バイトが金曜から月曜まであるから…

データ構造の特徴を知る

データ構造の特徴を勉強してください。

• 配列
• 連結リスト
• ハッシュテーブル

それぞれどういった用途で用いられるかを調べて提出してください。
どういった処理に強いか、どういった処理に弱いか等もあるといいです。

解説

解説長いです。重要なことなので頑張って読んでね。
データ構造には得意な処理と苦手な処理というものがあります。
例えば配列に要素を挿入する場合を考えてみましょう。
もし配列の任意の位置に値を挿入したい場合、コードは下のようになります。

int *array; /* ある程度のメモリを確保した配列（を指すポインタ） */
int length; /* 配列の長さ */
int n; /* 入れたい位置 */
for (int i = length - 1; i >= n ; i--){
  array[i+1] = array[i];
}
array[n] = value;

要素の入れ替えが何度も発生します。コピーにコストのかかる値が配列に入っていた場合、これは問題になります。そうでなくとも配列の長さが大きければ、当然問題になります。
一方、連結リストの場合は挿入位置の一つ前の要素がさしているポインタをいじるだけですみます。

List *head; /* リストの先頭要素を指すポインタ */
List *list = head;
List *elem; /* リストの要素のポインタ */
elem = (List*)malloc(sizeof(List));
int n; /* 入れたい位置 */
for (int i = 0; i < n - 1; i--){
  list = list->next;
}
elem->next = list->next;
list->next = elem;

ちなみにこのコードは色々嘘で、例えば先頭に挿入できません。困りましたね！知りません！
ハッシュテーブルには順番というものが存在しないので比較はできません。
このように、データ構造に対する操作にはある程度のコストがかかるわけですが、どの程度のコストがかかるのかを表す記法が存在します。それがO-記法です。
例えばN個の要素を持つ配列からある値を探す処理は、値を一つずつ見ていく必要があるため、大体N回の操作が必要になります。
これをO-記法で表すと「O(N)」となります。アルゴリズムの計算量がO(N)とあった場合、そのアルゴリズムは要素数に比例する計算量を持つという意味になります。（あんまり正確な言い方じゃないですがわかりやすさを優先します）
一方、N個の要素を持つ「ソート済み」の配列からある値を探す場合、二分探査と呼ばれるアルゴリズムが使えます。これは任意の位置（大抵真ん中）より大きいか小さいかを調べ、分かった範囲でまた同じ操作を繰り返し要素を探索するアルゴリズムです。
詳細は省きますが、この場合大体logN回の操作が必要になります。（何故そうなるのか自分で考えてみましょう。ちなみにlogの底は2です。）
これをO-記法で表すと「O(logN)」になります。大体分かってもらえたでしょうか。
そんなわけでこの記法を用いて各データ構造に対する操作にかかるコストを並べてみました。

配列

• 要素を追加 O(N)
• 要素のアクセス O(1)
• 要素の探索 O(N)

リスト

• 要素を追加　O(1)
• 要素のアクセス O(N)
• 要素の探索 O(N)

ハッシュテーブル

• 要素を追加 O(1)
• 要素のアクセス O(1)

並べてみたけどあんまり何も分かりませんね！
データ構造の特性を理解して、目的にあったデータ構造とアルゴリズムを選びましょう、という話でした。