オペレーティングシステムJ/K (管理のためのデータ構造) 2005年10月27日酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/OS/2005/ 配列 1 • 添え字とデータが1対1で対応 • 添え字は連続 2 – 添え字が１から始まるとは限らない 3 • データの挿入や削除は面倒 4 … … 添え字を用いてアクセスする（例では３） n • ディレクトリエントリ • メモリ管理表(ページテーブルなど) 配列上の探索添え字を用いて直接アクセス先頭から順に調べる図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ページエッジノード末端ノードハッシュテーブルデータデータキー１データデータキー２データデータキー３データハッシュ関数データパスワードファイル、メイルのエイリアスデータベースなど構造とは？ • 全体を形づくっている種々の材料による各部分の組み合わせ。作りや仕組み。 • さまざまな要素が相互に関連し合って作り上げている総体。また、各要素の相互関係。 • 階層的な構造わかりやすい文書やプログラムデータ構造 • ひとつまたは複数のデータを編成し保持する構造のこと • データ構造どうしは関連している • 例：このｐｐｔ原稿 – 見出し • 箇条書きの内容アルゴリズム • アルゴリズムは必ず問題を解決するもの • ひとつまたは複数のデータを操作し目的の結果を得るための一連の処理手順 • 例: 交差点を渡りたい(＝問題) – 信号があるか？ – 信号がないならば、どうするか？