教科書的な内容は疲れるな。でもコツコツやらねば。 ちょっと実装しようかなと思ったけど、今日はオシマイ。明日からは、「プログラミングの宝箱 アルゴリズムとデータ構造」も使ってみる。

データ構造の実現 基本データ型 例、数値型(整数、文字、浮動小数点数) 基本データ型をベースにして、ポインタ、配列、構造体(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…

なんか、前回の日記からずいぶんと間があいてしまったなー。 時間が空いた理由は、きっちりやろうとしすぎていたからかな。 ともかく手が伸びなかったのだから心の奥底で気が重かったんだと思う。改善策は、ここのところ考えていたので導けた。いままでは「…