| トップ->C言語入門 |
|
あなたは 人目のC(C++)言語入門受講生です。 |
C言語入門〜トップ
C++言語入門〜トップ
0. はじめに
1. 基本的な決まり
1. 書式
2. 予約語
3. 構成
4. データの形と宣言
5. 定数と変数
6. 簡単な演算
2. 入出力
1. printf
2. scanf
3. 練習問題1
4. 1文字入出力
5. エスケープシーケンス
3. 制御文
1. 順次構造
2. 単一分岐
3. 多重分岐
4. ケース構造
5. 反復構造(while)
6. 反復構造(do)
7. 反復構造(for)
8. 補助制御文
9. 練習問題
10.練習問題
4. 配列
1. 配列とは
2. 配列の宣言と初期化
3. 配列の使用法
4. 練習問題
5. 文字列
6. ２次配列と多次元配列
7. 練習問題
5. 演算子
1. 演算子の種類
2. インクリメント演算子とデクリメント演算子
3. 複合代入演算子
4. ビット演算子
5. シフト演算子
6. キャスト演算子
7. 順次演算子
8. 条件演算子(三項演算子)
9. sizeof演算子
10.演算子の優先順位
11.式と値
12.条件式と値
13.練習問題
6. ポインタ
1. ポインタとは
2. 配列とポインタ
3. 文字列とポインタ
4. ポインタのメリット
7. 関数
1. 関数の作り方
2. プロトタイプ宣言
3. 配列とポインタ
4. 値渡しとアドレス渡し
5. main関数の引数
6. 練習問題
7. 標準関数
8. 再帰関数
8. プリプロセッサ
1. プリプロセッサとは
2. #define, #undef
3. #include
4. #if
5. #error、#warning
6. マクロ
7. 定義済みマクロ
9. 変数の有効範囲
1. 変数の種類
2. グローバル変数の有効範囲
3. オート変数の有効範囲
4. スタティック変数の有効範囲
10. 構造体
1. 構造体とは
2. 構造体の宣言
3. 構造体の使用法
4. 構造体のポインタ
5. 構造体の構造体
6. 構造体と関数
7. 練習問題
11. 共用体
1. 共用体とは
2. 共用体の宣言
3. 共用体の使用法
12. ファイル
1. ファイル
2. ファイル構造体
3. ファイル作成・オープン
4. ファイル読み込み
5. ファイル書き込み
6. ファイルクローズ
7. ファイルエラー
8. ランダムアクセス
9. 標準入出力
10. 練習問題
11. ファイルの検索
12. ファイルの削除
13. ファイル名変更
14. ディレクトリ操作
13. 低水準入出力関数
1. 高水準入出力関数との違い
2. ファイル作成
3. ファイルオープン
4. ファイル読み込み
5. ファイル書き込み
6. ファイルクローズ
7. 標準入出力
8. ランダムアクセス
9. ファイルポインタとファイルディスクリプタ
10. 練習問題
14. データ構造
1. データ構造とは
2. データ構造の種類
3. 線形リスト
4. 単方向リスト
5. 双方向リスト
6. 環状リスト
7. ベクター
8. 木
9. 二分検索木
10. スタック
11. キュー
15 標準関数
1. 文字分類・文字変換
2. 文字列操作
3. データ変換
4. メモリー操作
5. 数値演算
6. ファイル操作(高水準入出力関数)
7. ファイル操作(低水準入出力関数)
8. プロセス関係
16 関数ポインタ
1. 関数ポインタとは
2. 関数ポインタ
3. 関数ポインタと引数・戻り値
4. 関数ポインタの配列
17. そしてその後は (PR)
1. ヒューマンアカデミー C言語講座
2. el school C言語講座
3. C++入門
このページの先頭に戻る
トップページに戻る
|
前ページへ :
トップへ :
次ページへ
- 14-9.二分検索木
-
二分検索木とは検索に用いる二分木で、節の左は必ずその節よりも小さい。
節の右側は必ずその節よりも大きい節があるようにした二分木をいう。その形は
バランス木に近い形(根から葉までの距離がほぼ等しい木)の方が検索時間が短くて済む。
要素の追加は比較的短時間で終了するが、要素の削除を行う場合、節や葉のつなぎ換えを
しなければならない場合もあるため時間がかかる場合もある。このような理由から、
検索を多く行うデータベースなどに使用され、就業時間が終わるなどして、データーベースへの
追加や検索が行われなくなったときに、メンテナンスとして、バランス木に近い形に
つなぎ換えを行う作業を実行する。- 要素の追加
-
要素の追加は、追加する要素が根よりも小さければ左へ、大きければ右へ進む。
この作業は再帰的に呼び出され、追加すべき葉もしくは節を探す。そしてその葉(節)
の左もしくは右に新しい要素を追加する。
注意点として、昇順(もしくは降順)にデータを追加してはいけない ということです。というのは昇順(降順)に追加すると、バランス木からはずれて、 線形リストと同じ形になってしまい、データの追加、検索の効率が悪くなってしまい ます。
- 要素の削除
-
要素の削除は、追加ほど単純ではない。それは場合によっては節のつなぎ換え作業を
伴う必要があるからである。
削除する節の枝が０本の場合は、何も考えずにその節を削除すればよい。
削除する節の枝が１本の場合は、その下の節を削除する節と置き換えればよい。
削除する節の枝が２本の場合は、少し面倒くさい。何度も書いたことだが、節の つなぎ換えが必要になるからだ。例えば下図のように「8」を削除したい場合、 その右に伸びる節(12)を、削除したい節(8)に置き換える。削除したい節(8)の 左に伸びる節(7)を、削除したい節(8)の代わりに置き換えた節(12)から左に 降りていき、左の一番最後の節(10)の左につなげる。
しかしこのようなアルゴリズムで削除するとバランス木の形から離れて、 線形リストに近い木になることも多く、検索効率に影響するため、追加や 削除を何度か行ったら、整理してバランス木に近い形に戻す必要がある。
以下に、二分検索木の成長の過程シミュレーションプログラムを示します。 Java Appletが表示できる環境でご覧ください。テキストフィールドのところに 数字を入力して、リターンキーもしくは「Insert」ボタンを押すと数字が木に追加されます。 同じくテキストフィールドに数字を入力して「Delete」を押すと、その節が削除されます。 (操作性が悪いですが、ご了承ください)
前ページへ :
トップへ :
次ページへ