リスト追加処理
最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。 しかし、実際にはデータを入力しながらの処理となるであろう。 最も単純なリスト挿入 struct List* top = NULL ; […]
リスト構造でのプログラミング
前回説明した、リスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。 簡単なリスト処理の例 // 全要素を表示する関数 void print( struct List* p ) { for( ; […]
リスト構造について
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点 […]
前期中間テストの答案返却
前期中間試験の返却と解答の解説を行う。 今年の学生は、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) […]