AVL木と2分ヒープ
2分探索木へのデータ追加と不均一な木の成長 先週の講義で説明していた、entry() では、データを追加すべき末端を探し、追加する処理であった。 しかし、前回のプログラムで、以下のような順序でデータを与えたら、どのような […]
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]
双方向リストとdeque
番兵と双方向循環リスト 前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか？ bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか？ 同じく、 […]
ランダムアクセス・シーケンシャルアクセスから双方向リスト
ランダムアクセスO(1)とシーケンシャルアクセスO(N)の説明を踏まえ、リスト構造のO(N)の改善にむけた解説を行う。 リスト構造の利点と欠点 リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リ […]
集合とリスト処理
リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。集合処理の記述には、2進数を使った方式やリストを用いた方法が一般的である。 […]
スタックと待ち行列
前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。 計算処理中に一時的なデータの保存として、スタック(stack)と待ち行列・キュー(queue)がよく […]
リストへの追加処理
最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。 しかし、実際にはデータを入力しながらの処理となるであろう。今回は、前回のリスト操作のプログラムの確認などと合わせ、リストへのデータの追 […]
リスト処理
リスト構造 リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にでき […]
リスト構造の導入
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点 […]
fgetsではみ出たら
C言語で長い一行を読み込むのであれば、通常は”それなりに”大きい配列に読み込んでから、strdup() などでデータに応じた大きさで保存する。しかし、それ以上に長い1行を扱いたいのならどうするか& […]