オペレーティングシステムJ/K (管理のためのデータ構造) 2005年10月27日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2005/
配列 添え字とデータが1対1で対応 添え字は連続 データの挿入や削除は面倒 ディレクトリエントリ メモリ管理表(ページテーブルなど) 2 3 4 n … 添え字とデータが1対1で対応 添え字は連続 添え字が１から始まるとは限らない データの挿入や削除は面倒 ディレクトリエントリ メモリ管理表(ページテーブルなど) 添え字を用いてアクセスする（例では３）
配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる 図2.1.4 図2.1.5 教科書30ページ 直接探索 線形探索
配列上の探索 半分ずつ調べます 1)半分に分ける 2)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要 図2.1.6 教科書31ページ 二分探索
※仮想記憶を説明するときに詳細を説明します。 [Intel, ``Software Developer Manual’’] ※仮想記憶を説明するときに詳細を説明します。
[Intel, ``Software Developer Manual’’]
The IA-32 Intel Architecture Software Developer’s Manual, Volume3: System Programming Guide 目に付くところに存在するCPUの一例。 [Intel, ``Software Developer Manual’’]
メモリと配列 計算機のメモリは一種の配列である プログラミング言語による多彩な要素をもつ配列 プロセッサの命令が扱える単位を要素としている byte, word, dwordのような整数 float, double, long doubleのような不動小数点数 qword, dqwordのようなショートベクタ整数 プログラミング言語による多彩な要素をもつ配列 プログラミング言語のコンパイラが変換してくれます 気にしなくてもいいんですが、場合によります…
待ち行列（FIFO） データ挿入 データ取得 図2.3.1・2.3.2・2.3.3 教科書38・39ページ 待ち行列（データの挿入・取得）
データを動かすことなく、要素の挿入・削除ができる 連結リスト データをそれぞれの要素に格納 要素どおし、つながってリストを形成 先頭 次 データ データを動かすことなく、要素の挿入・削除ができる
双方向連結リスト 連結リストを双方にリンクしたもの 先頭 次 データ 最後 前 両方向から探索できる
リングバッファ 配列の最初と最後を接続して環にしたもの ２つのポインタでデータの出し入れを管理 データの先頭を指すポインタ head, front データの最後尾を指すポインタ tail, rear ２つのポインタが重なったらデータは空 領域の大きさをnとしたらポインタの位置はnとおり データの数が0からnまでn+1とおりある ポインタが重なったら、空か満杯の状態が重なる…
スタック（LIFO） プッシュ ポップ スタックポインタ スタックポインタ スタックポインタ 一時変数、レジスタのセーブ先など
木構造 ルートとそれ以外の ルートノード ノードにちょうど１つだけ の経路しか存在しない エッジ ノード 図2.5.1 教科書46ページ 末端ノード エッジ ノード 図2.5.1 教科書46ページ
ハッシュテーブル データ キー１ キー２ キー３ ハッシュ関数 パスワードファイル、メイルのエイリアスデータベースなど
構造とは？ 全体を形づくっている種々の材料による各部分の組み合わせ。作りや仕組み。 さまざまな要素が相互に関連し合って作り上げている総体。また、各要素の相互関係。 階層的な構造 わかりやすい文書やプログラム
データ構造 ひとつまたは複数のデータを編成し保持する構造のこと データ構造どうしは関連している 例：このｐｐｔ原稿 見出し 箇条書きの内容
アルゴリズム アルゴリズムは必ず問題を解決するもの ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 例: 交差点を渡りたい(＝問題) 信号があるか？ 信号がないならば、どうするか？