データ構造の実現 基本データ型 例、数値型(整数、文字、浮動小数点数) 基本データ型をベースにして、ポインタ、配列、構造体(stract)、共用体(union)、関数を組み合わせて任意のデータ型をつくれる 基本データ型は言語によって大差は無いが、C言語には文字…

今度はデータ構造だ。 用語 擬似コーディング 擬似プログラム 段階的詳細化(stepwise refinement) 擬似プログラムを細部をつめながらプログラミング言語に置き換えること 抽象データ型(abstract data type) データの型とその型に対する一連の操作の組 例、「…

線形探索法と2分探索法とハッシュ法の短所を比較 短所 線形探索法はデータを登録順に保存しているが、探索が遅い 2分探索法は探索が線形探索より早いが、あらかじめソートが必要だし、データの登録順を保存できない ハッシュ法はハッシュ関数が便利だが、デ…

ハッシュ法ですね。 hashing。 ハッシュ関数って何？ キーの値から添え字を得る関数をハッシュ関数という。 たとえば？ 例えば、大きさ100の配列を使って、整数のキーをもつデータを扱うには ハッシュ関数hash(key)を、h(key) = key % 100、などとして ハッ…

2-2-3はデータ挿入のコストの話。 そうか、検索だけじゃなくて挿入のコストを考えなきゃいけないときも多いよな。 リニアとバイナリのデータ挿入における違い。 リニアはソート不要なので、リストの最後にデータをくっつけるだけ。 一方、バイナリは常にリス…

2分探索法の肝をメモ ポイント 最初にデータをソートすることが必要 着目範囲の上限と下限を常に設定する 上限と下限から真ん中を算出し、目的のキーと真ん中を比較する キーと真ん中との大小をみることで、真ん中を上下に移動させる。 真ん中を移動するとき…

おっと、わすれてた。2-4は途中で力尽きて放棄してたんだ。 線形探索法の計算量 ループの中は各回に1回づつ実行される処理なので、ループ内はO(1)。 そしてwhileループの平均実行回数はO(n/2)となる。 これは、ちょっと回すと結局O(n)になってしまう。 あと…

ということで、今日はバイナリサーチこと、2分探索法をやる。 binary search。いい響き。 2分探索法って 前回の線形探索法との違いは、ほとんど以下の関数に集約される。 前回のsearch()を以下に置き換えればok。 int binary_search(int key){ int low, high…

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 線形計画法による探索の計算量 計算量について考える。使う例は、n個のデータを格納したリストから、ある特定のキーを持つデータを探索するもの。 単純な探索プログラムのデータ数…

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 基本操作の計算量を定義する 関数呼び出しを含む演算や代入処理 Oは処理系や扱うデータ構造中のデータ量に依存 データ量に関わらない処理 O(1) O(f(n))とO(g(n))を連続で実行して…

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 計算量(Complexity)という抽象的な尺度を使う。 O:オーダー n : 入力データの大きさ、回数 O() : nの関数として表現する計算量 計算量は抽象的な尺度。 同じ計算量でも1秒だったり…

定本 Cプログラマのためのアルゴリズムとデータ構造の第2章の読書メモです。 アルゴリズムの性能評価 計算機と同じように実行時間のベンチマークで測定するのが自然。 実行時間のベンチマークテスト 決められた課題プログラムを実行して処理時間を性能の尺度…

定本 Cプログラマのためのアルゴリズムとデータ構造の第1章の読書メモです。とても基本的な学習するうえでのモチベーションについて書いてあります。 なぜアルゴリズムとデータ構造を学ぶのか 問題分析能力向上 適切なアルゴリズムやデータ構造の選択眼を養…