◎２分木
●２分探索木（中間順）
左の子≦親≦右の子
４
/ \
２ ８
/ \ / \
１ ３ ６ ９
/ \
５ ７
●ヒープ探索木（幅優先順）
親≦子
１
/ \
２ ３
/ \ / \
４ ５ ６ ７
/ \
８ ９
●Ｂ木（バランス木）
根から全ての葉までの深さが同じ。小さい側のレコード数と大きい側の
レコード数の比率がある許容範囲内に動的に再配置する。
１
/ \
２ ３
/ \ / \
４ ５ ６ ７
※ＡＶＬ木（バランス木）
任意の節点において左右の部分木の高さの差が１以下である木。
●半順序木
深さ＝√ノード数
１
/ \
２ ３
/ \ / \
４ ５ ６ ７
/ \
８ ９
◎リスト
データ要素の順序づけられた集合
┌─┐┌→┌─┐┌→┌─┐┌→┌─┐
│●├┘ │ ││ │ ││ │ │
└─┘ ├─┤│ ├─┤│ ├─┤
│●├┘ │●├┘ │×│
└─┘ └─┘ └─┘
◎スタック(LIFO:Last In First Out)
後入れ先だし方式。
──┐ ┌─→
│ │
│↓ ││
├───┤
├───┤
└───┘
※制御スタック
再帰処理の際自分自身を呼び出すごとに
・プログラムへの戻り番地
・引数
・局所変数
を退避させ、呼び出し側に戻ったときに取り出すスタック。
◎キュー(FIFO)
先入れ先だし方式。
──┬─┬─┬─
─→ │ │ │──→
──┴─┴─┴─
◎データ構造
●木(ツリー)構造
┌─┐
┌┴─┴┐
↓ ↓
┌─┐ ┌─┐
┌┴─┤ └┬┴─┐
↓ ↓ ↓ ↓
┌─┐┌─┐┌─┐┌─┐
└─┘└─┘└─┘└─┘
●網(ネットワーク)構造
┌─┐ ┌─┐ ┌─┐
│ ├─┤ ├─┤ │
└┬┘ └┬┘ └┬┘
┌┴┐ ┌┴┐ ┌┴┐
│ ├─┤ ├─┤ │
└┬┘ └┬┘ └┬┘
┌┴┐ ┌┴┐ ┌┴┐
│ ├─┤ ├─┤ │
└─┘ └─┘ └─┘
●関係(リレーショナル)モデル
┌─┬─┬─┬─┬─┬─┐
├─┼─┼─┼─┼─┼─┤
├─┼─┼─┼─┼─┼─┤
└─┴─┴─┴─┴─┴─┘
◎整列（ソート）
※ソート時間とデータ数の関係
探索時間
↑
│ ＊
│ ＊
│ ＊
│ ＊
│ ＊＊
│＊＊＊
└────────→データ数
●選択ソート（最大値選択法）
未整列の部分の端の要素と各要素を比べて、大小が逆ならば交換する。
５ ４ ３ ２ １ → １ ５ ４ ３ ２
↑ ↑ ↑ ↑ │
│ │ │ └─┤
│ │ └───┤
│ └─────┤
└───────┘
ｎ個の数字を降順にソートする際、ｉ番目の数字とその次移行の数字全てと比較し
一番大きいものをｉ番目の数字とする。その比較回数は、
ｉ＝１ のとき ｊ＝ ２～ｎ の ｎ－１回
ｉ＝２ のとき ｊ＝ ３～ｎ の ｎ－２回
ｉ＝３ のとき ｊ＝ ４～ｎ の ｎ－３回
： ： ： ：
： ： ： ：
ｉ＝ｎ－３のとき ｊ＝ｎ－２～ｎ の ３回
ｉ＝ｎ－２のとき ｊ＝ｎ－１～ｎ の ２回
ｉ＝ｎ－１のとき ｊ＝ｎ ～ｎ の １回
つまり比較回数は、
１＋２＋３＋・・・＋（ｎ－３）＋（ｎ－２）＋（ｎ－１）
│ │ │ ＋ │ │ │
│ │ └───────┘ ＋ │ │
│ └───────────────┘ ＋ │
└───────────────────────┘
両端の足し算（１＋（ｎ－１））を（ｎ－１）の半分回行うから、
＝（１＋（ｎ－１））×（ｎ－１）／２
＝ｎ（ｎ－１）／２
▲▲▲▲▲▲▲▲
●バブルソート（隣接交換法）
隣り合う要素の値が逆順だったら交換する。
５ ４ ３ ２ １
↑ ↑
└─┘
４ ５ ３ ２ １
↑ ↑
└─┘
ｎ個の数字をソートする際、ｉ番目の数字とｉ＋１番目の数字とをｎ－ｉ回比較
するから、
ｉ＝１ のとき ｎ－１回
ｉ＝２ のとき ｎ－２回
ｉ＝３ のとき ｎ－３回
： ： ：
： ： ：
ｉ＝ｎ－３のとき ３回
ｉ＝ｎ－２のとき ２回
ｉ＝ｎ－１のとき １回
つまり比較回数は、
１＋２＋３＋・・・＋（ｎ－３）＋（ｎ－２）＋（ｎ－１）
│ │ │ ＋ │ │ │
│ │ └───────┘ ＋ │ │
│ └───────────────┘ ＋ │
└───────────────────────┘
両端の足し算（１＋（ｎ－１））を（ｎ－１）の半分回行うから、
＝（１＋（ｎ－１））×（ｎ－１）／２
＝ｎ（ｎ－１）／２
▲▲▲▲▲▲▲▲
●挿入ソート
整列済みの配列中の適切な位置に新要素を入れる。
５ ４ ３ ２ １
↑ │
└─┘
４ ５ ３ ２ １
↑ │
└───┘
ｎ個の数字をソートする際、すでに整列済みの要素列の要素数がｉのとき、ｉ回の
比較が行われるから
ｉ＝１ のとき １回
ｉ＝２ のとき ２回
ｉ＝３ のとき ３回
： ： ：
： ： ：
ｉ＝ｎ－３のとき ｎ－３回
ｉ＝ｎ－２のとき ｎ－２回
ｉ＝ｎ－１のとき ｎ－１回
つまり比較回数は、
１＋２＋３＋・・・＋（ｎ－３）＋（ｎ－２）＋（ｎ－１）
│ │ │ ＋ │ │ │
│ │ └───────┘ ＋ │ │
│ └───────────────┘ ＋ │
└───────────────────────┘
両端の足し算（１＋（ｎ－１））を（ｎ－１）の半分回行うから、
＝（１＋（ｎ－１））×（ｎ－１）／２
＝ｎ（ｎ－１）／２
▲▲▲▲▲▲▲▲
●クイックソート
未整列の部分を、ある基準値より大きい要素のグループと小さい要素のグループ
とに分ける。
平均の計算量：o(nlog2(n))
最悪の計算量：o(n^2) ＜すでに整列済みの配列の場合
●ヒープソート
どの部分木も親が子より大きい完全２分木「ヒープ」の性質を利用。
動作が不安定。
平均の計算量：o(nlog2(n))
●マージソート
整列済みの複数の配列を作ってから一つの配列にまとめる。
データ数の半分程度の作業領域を必要とする。
平均の計算量：o(nlog2(n))
●シェルソート
挿入ソートを改良して要素の移動距離を大きくすることで整列を高速化する。
計算量＝n^1.25
◎探索（サーチ）
●線形（逐次）探索法
先頭から１要素ずつ探索キーに合致しているかどうかを調べる方法。
平均探索回数 Ｎ＋１／２
最大探索回数 Ｎ
探索時間
↑
│ ＊
│ ＊
│ ＊
│ ＊
│ ＊
│＊
└────────→データ数
●２分探索法（バイナリサーチ）
表の中央の要素のキー値と、検索すべきデータのキー値を順次比較し、表の下半分
か上半分を切り捨てていく方法。データがソートされている必要がある。
平均探索回数 [ｌｏｇ２(Ｎ)] （Ｎはデータ数）
最大探索回数 [ｌｏｇ２(Ｎ)]＋１ （[]は端数切捨て）
探索時間
↑ ＊＊＊＊
│ ＊＊
│ ＊
│＊
│
└────────→データ数
◎ＢＮＦ(Backus-Naur Form)
プログラム言語の構文表現。バッカス記法。
例）平成１０年 問１２
次に示すのは、ＢＮＦで記述されたあるプログラム言語の構文の一覧である。
＜パラメタ指定＞として正しいものはどれか。
＜パラメタ指定＞：：＝＜パラメタ＞｜（＜パラメタ指定＞，＜パラメタ＞）
＜パラメタ＞：：＝＜英字＞｜＜パラメタ＞＜英字＞
＜英字＞：：＝ａ｜ｂ｜ｃ｜・・・｜Ｘ｜Ｙ｜Ｚ
ア （ａｂｃ）
イ （（ａｂｃ，ｄｅｆ））
ウ （ａｂｃ，（ｄｅｆ））
エ （（ａｂｃ，ｄｅｆ），ｇｈｉ）
【正解】エ
例）平成１１年 問９
正規表現［Ａ－Ｚ］＋［０－９］＊が表現する文字列の集合の要素となるものは
どれか。ここで、
［Ａ－Ｚ］：英字１文字を表す。
［０－９］：数字１文字を表す。
＊ ：直前の正規表現の０回以上の繰返しを表す。
＋ ：直前の正規表現の１回以上の繰返しを表す。
ア ４５６７８９
イ ＡＢＣ９９＊
ウ ＡＢＣ＋９９
エ ＡＢＣＤＥＦ
【正解】エ
◎ポーランド表記法
演算子を被演算子の後ろに記述する記述法。
例）(a-b)*c+d → ab-c*d+
前置記法 ＋ａ＊－ｂｃｄ
中置記法 （ａ＋（ｂ－ｃ）＊ｄ）
後置記法 ａｂｃ－ｄ＊＋
◎言語処理系
●手続き型（構造化）プログラム言語
対象とする問題の解決手順を手続きによって記述する方式。順次・選択・繰り返し
例）COBOL、FORTRAN、PASCAL、C
●論理型プログラム言語
事実と推論規則を用いて、「論理」を記述する方式。
例）Prolog
●関数型プログラム言語
「関数」を記述する方式。
例）LISP
●オブジェクト指向プログラム言語
オブジェクトの状態とその振る舞いを記述する方式。
例）C++、Java、Smal Talk、Objective-C
◎コンパイル技法
●翻訳プログラム
原始プログラムを目的プログラムに翻訳するプログラム。
原始プログラムってなに？
＞プログラム言語で書かれたプログラム。
目的プログラムってなに？
＞コンピュータが理解できるプログラム（機械語）。
高速・低開発効率
↑
アセンブラ：低水準言語を機械語に翻訳。機械語と１対１対応でかなり機械語に近い。
コンパイラ：高水準・手続き型言語を機械語に翻訳。
クロスコンパイラ：原始プログラムを別の計算機（異なる命令形式）の
目的プログラムに翻訳。
コンパイラコンパイラ：コンパイラを作ってくれるコンパイラ。
インタプリタ：ＢＡＳＩＣなどを１行ずつ目的プログラムに翻訳。
ジェネレータ：高水準・非手続き型言語を目的プログラムに翻訳。
プリプロセッサ：特定言語の仕様拡張部分を許容された命令文に翻訳。
↓
低速・高開発効率
高水準言語・低水準言語ってなに？
＞高水準言語は多くの機種でそのまま実行でき、人にやさしいプログラム言語。
それに対して低水準言語はハードウェア寄り。アセンブラ言語など。
手続き型・非手続き型言語ってなに？
＞手続き型は処理の手順を主体にプログラムを組む言語。
ＣＯＢＯＬ、ＦＯＲＴＲＡＮ、ＰＡＳＣＡＬ、Ｃなど。
それに対し、非手続き型言語は「何をしたいか」に重点を置いてプログラムを組む言語。
ＲＰＧ、ＰＲＯＬＯＧ、ＬＩＰＳ、Ｓｍａｌｌｔａｌｋなど。
●高水準言語プログラムを実行するまで
原始プログラム（ＳＭ：ソースモジュール）
↓コンパイル
目的プログラム（ＯＭ：オブジェクトモジュール）
↓リンケージ
実行プログラム（ＬＭ：ロードモジュール）
※リンケージ
目的プログラムが参照している標準サブルーチンをライブラリから呼び出す。
●コンパイルの手順
コンパイルってなに？
＞詳しくは下記の通り段階に分かれて動作する。
簡単に言うと「プログラムの文法チェック」
①字句解析
字句ってなに？＞プログラム言語の最小単位
Ｃ言語だと、頭から順に読んでいってスペースやカンマなどの
区切り文字を見つけたら、その字句を切り出す作業をする。
②構文解析
構文ってなに？＞字句をプログラム文法に従って構造化したもの
ツリー構造になるので「構文木」と呼ばれる。
よく問題に出る「逆ポーランド記法」はこの「構文木」のひとつ。
逆ポーランド記法ってなに？
＞演算子を被演算子の後ろに記述する記述法。
例）(a-b)*c+d → ab-c*d+
③意味解析
構文木の構造が矛盾していないかをチェックする。
コンパイルエラーはこの段階で判定される。
④最適化
生成される目的プログラムの実行時間短縮、サイズの縮小を行う。
具体的には、定数が格納されている変数を追跡し、途中で値が変更されていない
ときは定数化する。この段階は省略可能であり、この段階で原始プログラムとの
対応が切れるため、デバッグするには省略したほうがやりやすい。
⑤コード生成
目的プログラムを生成する。
※レジスタへの変数割付けは、コードサイズ/実行速度ともに最適化できる。
◎プログラム構造
●記憶域管理
○プログラムそのものの記憶域（目的プログラムテキスト）
○変数の初期設定値や定数（１つの記憶域にまとめて確保される）
●ヒープとガーべジコレクション
ヒープ：動的変数のための記憶域。
ガーべジコレクション：定期的に行われるヒープの整理。
●ブロックとスコープ
スコープ：ある変数についてそれを参照できるプログラム上の範囲。
ブロック：スコープを区切るための単位。
※抽象データ型
データ定義とそのデータを操作する手続きをひとまとめにしたもの。
◎データ型
●静的データ構造
プログラム翻訳時にその大きさや構造が決定されるもの。スタックに割り当てる。
●動的データ構造
プログラムの実行時にその大きさや構造が決定されるもの。ヒープ領域に割り当
てる。
※抽象データ型
データ定義とそのデータを操作する手続きをひとまとめにしたもの。
◎言語の種類・特徴
●アセンブラ言語
コンピュータが直接解釈・実行できる言語(マシン語)と1対1に対応した言語。
最もコンピュータに近い低水準言語(低級言語)である。マイクロプロセッサの
種類(命令セットの種類)ごとに異なる。
●COBOL
事務処理計算用言語。英文に近い記述が可能で、汎用性が高い。企業の会計処理に
使われる大型計算機のプログラムに使われている。
●Visual Basic(VB)
Windows上で動作するプログラム言語。ウィンドウやボタンをフォームに配置して
おくことでＧＵＩを駆使したアプリケーションを簡単に作成できる。
●C
1972年にアメリカAT&T社のベル研究所でD. M. Ritchie氏とB. W. Kernighan氏
によって開発されたプログラミング言語。豊富な演算子やデータ型、制御構造を
持ち、構造化プログラミングに適している。
●C++
Ｃ言語を拡張したオブジェクト指向型プログラム言語。
●Java
C++をベースに開発したオブジェクト指向プログラム言語。特定のＯＳやパソコン
の機種に依存することなく、「仮想マシン(Java Virtual Machine)」の上で実行
できる。
Javaアプレット ：Webブラウザ上で実行させるJavaプログラム
Javaアプリケーション：Webブラウザなしに単独で実行するプログラム。
●PostScript
ページ記述言語(PDL:Page Description Language)で、ＤＴＰ(Desk Top Publishing)
の分野では事実上の世界標準。インタプリタ方式。
●ECMAScript
JavaScriptの標準規格。Netscape Communications社とMicrosoft社でJavaScriptの
仕様が微妙に異なっていたため、両社が参加の上、ECMAが標準化した。
●Perl(Practical Extranction and Report Language)
テキストファイルを処理するのに適した言語。コンパイル不要。
●Ruby
オブジェクト指向スクリプト言語。Rubyはシンプルな文法や、可読性の高い構文、
優れたテキスト処理などを特徴としている。本格的なオブジェクト指向を備えて
いるが、手続き型の処理を行うことも可能である。
●PHP
動的にWebページを生成するWebサーバの拡張機能の一つ。また、そこで使われる
スクリプト言語。
●Python（パイソン）
オープンソースのプログラミング言語。オブジェクト指向スクリプト言語の一種で
あり、Perlとともに欧米で広く普及している。
◎共通言語基盤（CLI）
NET Frameworkの基幹を構成する実行コードや実行環境などについてマイクロソフトが
策定した仕様。
◎マークアップ言語
●HTML
ウェブ上のドキュメントを記述するためのマークアップ言語である。
Web作成基本プログラミング用語。
●XML(eXtensible Markup Language)
ＨＴＭＬの後継言語であるとして標準化が進められている言語。ユーザ自身のタグ
を定義できる。
●SGML(Standard Generalized Markup Language)
文書の論理構造、意味構造を簡単なマークで記述する言語。
◎データ記述言語（DDL）
コンピュータ利用者あるいはアプリケーションソフトウェアが、コンピュータの
データを定義するコンピュータ言語もしくはコンピュータ言語要素。