リスト構造について
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点 […]
前期中間テストの答案返却
前期中間試験の返却と解答の解説を行う。 今年の学生は、3年で私がプログラミング応用を担当していないので、私が例年3年に出題していた以下のような問題が苦手だろうということで、出題した問題。ポインタと構造体と配列が絡む問題は […]
様々なメモリ確保
前回の授業で説明していたような、必要に応じて確保するメモリは、動的メモリと呼ばれる。 動的メモリも、局所変数やalloca()を用いたスタック領域と、malloc()とfree()を使うヒープメモリ領域に分類される。 s […]
mallocとfree
前回の講義での、「長いかもしれない名前」を覚える処理は、最悪の場合をどう扱うかでメモリのムダが発生する。 ここで、前回講義で説明した、大きな配列を少しづつ分けて使う処理を考える。 大きな配列を少しづつ貸し出す処理 cha […]
メモリを効率よく使うには
メモリ利用の効率 次にメモリの利用効率の話について解説する。 例えば、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。 #define MEMBER_SIZE 50 #define NAME_LEN […]
マージソートのオーダー
マージソートの分析 マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。 こ […]
再帰処理の処理時間
再帰関数と再帰方程式 再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。 // 階乗 int fact( in […]
繰り返し処理とオーダ記法
先週に、単純繰り返し処理の時間分析をやったので、次のステップに。 2分探索法の処理時間 データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。 // 2分探索法 O(log N) […]
情報構造論ガイダンス
情報構造論のガイダンス プログラム作成でのポイント この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。 プログラムの速度 プログラ […]
mallocとfreelist
C言語では、動的メモリ領域をどのように管理していくのか解説する。 動的メモリ領域とフリーリスト 動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却す […]