講義録に動くサンプルコードを併記
長男からプログラミングの授業の質問が LINE で流れてきて、大学の先生の資料を覗き見。その大学の課題ではサンプルコードの配布がしっかりしている。私の講義録でもサンプルコードは掲載しているけど、プロジェクタで掲示しながら […]
B木とデータベース
2分探索木の考え方を拡張したもので、B木がある。 B木の構造 2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデー […]
ポインタの先には何がある？
学生さんから「ポインタの先には何があるの？」との質問があった。 私が「そのポインタの型のデータ」と答えると、さらに「ポインタはメモリの場所。でもメモリには int や char や double といった色んなデータがあ […]
演算子と2分木による式の表現
2分木の応用として、式の表現を行うけどその前に… 逆ポーランド記法 一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような […]
const char*s, char* const sの違い
専攻科実験のサンプルコードで、警告がでたことについて質問があったので説明。 (( サンプルコード sample.cxx )) #include <stdio.h> void foo( char* s ) { […]
意思決定木と構文解析
前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。 意思決定木 意思決定木の説明ということで、yes/noクイズの例を示す。これは2分木 […]
Visual Studio Code で印刷
実験や授業課題のレポート提出で、プログラムを印刷したものを提出してくれるけど、行を移動しながら何度もスクリーンキャプチャで保存した画像ファイルをWordに貼り付けて提出している人が多い。 いままでなら、「秀丸エディタで印 […]
AVL木と2分ヒープ
前回、2分木へのデータ追加の説明と、演習課題を行っていたが、演習時間としては短いので、今日も前半講義で残り時間は演習とする。 2分木へのデータ追加と不均一な木の成長 先週の講義で説明していた、entry() では、データ […]
2分探索木にデータ追加と演習
2分探索木にデータを追加 前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになる […]
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり) // […]