基本情報技術概論（第４回） 埼玉大学 理工学研究科 堀山 貴史 2008/5/15 基本情報技術概論 (第４回) データ構造 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

前回までの復習 （計算の仕組みの基礎） 数値、文字 の表現方法 四則演算 (＋, －, ×, ÷) 論理素子 論理回路 ハードウェアの基礎 前回までの復習 （計算の仕組みの基礎） 数値、文字 の表現方法 四則演算 (＋, －, ×, ÷) 10進法での筆算と同じようにできる ２進数では、０, １ を操作すれば実現できる 論理素子 ０, １ の「入力」から、０, １ の「出力」を得る仕組み 論理回路 論理素子を用いて、 計算を実現する仕組み 組合せ回路、順序回路 ハードウェアの基礎

ハードウェア (hardware) … 装置 ソフトウェア (software) … 装置を動かすための情報 ソフトウェアの基礎 ハードウェア (hardware) … 装置 ソフトウェア (software) … 装置を動かすための情報

データ構造 データ構造 データをどのように記憶するか 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree) ___________ ___________

データ構造： 配列 データを順番にならべて、 添字 でアクセスできるようにしたもの 操作： 参照、探索、更新、削除、挿入 配列 A データ構造： 配列 ________________ データを順番にならべて、 添字 でアクセスできるようにしたもの 操作： 参照、探索、更新、削除、挿入 ________ 配列 A A [1] 30 A [2] 50 A [3] 20 A [4] 70 A [5] 10 …

コンピュータ上での配列 配列 A 二次元配列 A [1] 30 … … A [2] 50 A [3] 20 … … … A [4] 70 メモリ （主記憶装置） A [1] 30 A [1, 1] A [1, 2] … … … A [2, 1] A [2, 2] … A [2] 50 番地 （アドレス） 2000 30 A [3, 1] A [3, 2] … A [3] 20 2001 50 … … … A [4] 70 2002 20 A [5] 10 一次元に変換して メモリに配置する 2003 70 2004 10 … … …

配列の操作 参照 探索 探索キー 70 A [1] 30 A [1] 30 配列Aの 4番は？ A [2] 50 A [2] 50 （探索データ） 70 配列の操作 参照 探索 A [1] 30 A [1] 30 配列Aの 4番は？ A [2] 50 A [2] 50 A [3] 20 A [3] 20 A [4] 70 A [4] 70 A [5] 10 A [5] 10 … … 添字を使って指定 … A[4] 先頭 A[1] から順番に 一致するか調べる

更新 挿入 70 を 更新 A[4] の位置に 35 を 挿入 A [1] 30 A [1] 30 35 A [2] 50 A [2] 50 20 A [3] 20 A [4] 70 35 A [4] 70 A [5] 10 A [5] 10 … … 70 を探索 + 更新 A[4] の場所を空けるため、 後ろに１つずつずらす

削除 削除 （その２） A[4] の位置の データ を 削除 A[4] の位置の データ を 削除 A [1] 30 A [1] 30 50 A [2] 50 A [3] 20 A [3] 20 A [4] 70 A [4] 70 A [5] 10 A [5] 10 … … A[4] が空いたため、 １つずつつめる A[4] に削除マークをつけて、 無いものとして扱う

データ構造： リスト となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ 単方向リスト 双方向リスト 環状リスト データ構造： リスト ________________ となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ ________ 単方向リスト 双方向リスト 環状リスト head (リストの 先頭を指す) 30 30 30 50 50 50 20 20 20 逆方向の探索が容易

コンピュータ上でのリスト 20 となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ 50 2030 … … メモリ （主記憶装置） 2000 2010 30 番地 （アドレス） 2010 30 50 2070 2030 20 20 となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ 2070 50 2030 … …

リストの操作 探索 更新 探索キー 20 を 更新 20 （探索データ） 30 30 50 50 20 20 35 70 70 先頭から順番に ポインタをたどって調べる 20 を探索 + 更新

リストの操作 50 の次に 35 を挿入 挿入 削除 20 を 削除 30 30 50 50 35 20 20 70 70 前のデータのポインタを、自分に 自分のポインタを、次のデータに 前のデータのポインタを、 次のデータに

表は、配列を用いたリストの実現を示しており、 リスト [ 東京、品川、名古屋、新大阪 ] を表している。 練習：　配列を用いたリストの実現 表は、配列を用いたリストの実現を示しており、 リスト [ 東京、品川、名古屋、新大阪 ] を表している。 このリストを、[ 東京、新横浜、名古屋、新大阪 ] に 変化させる操作はどれか。 ここで、A ( i, j ) は、表の第 i 行 第 j 列の要素を表す。 また、→ は代入を表す。 A 列 1 2 行 1 “東京” 2 2 “品川” 3 3 “名古屋” 4 4 “新大阪” 5 “新横浜”

第１の操作 第２の操作 ア 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) イ 5 → A(1, 2) 練習：　配列を用いたリストの実現 第１の操作 第２の操作 ア 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) イ 5 → A(1, 2) A(A(2, 2), 2) → A(5, 2) ウ A(A(1, 2), 2) → A(5, 2) 5 → A(1, 2) エ A(A(2, 2), 2) → A(5, 2) 5 → A(1, 2)

データ構造 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree)

データ構造： スタック push と pop による Last-In First-Out (L I FO) イメージ） 積み上げた書類や本 データ構造： スタック ________________ push と pop による Last-In First-Out (L I FO) イメージ） 積み上げた書類や本 生協の入口の トレイ ___________ 5 push pop 30 50 20

スタックの実現法 配列 リスト … 20 50 30 A [1] A [2] A [3] スタック ポインタ 30 50 20 5 push pop 30 50 20

データ構造： 待ち行列 （キュー） enqueue と dequeue による First-In First-Out (F I FO) データ構造： 待ち行列 （キュー） ________________ enqueue と dequeue による First-In First-Out (F I FO) イメージ） レジの前の行列 ___________ 5 enqueue 30 50 20 dequeue

キューの実現法 配列 リスト … 進行方向 front 5 A [1] 20 enqueue A [2] 50 rear A [3] 30 dequeue front 20 rear 50 30

ポーランド記法 と 逆ポーランド記法 演算 a + b を以下のように記す方法 ポーランド記法 + a b 逆ポーランド記法 a b + ( ) を使う必要がない 例) ( a + b ) x ( c - d ) 逆ポーランド記法 a b + c d - x スタック マシン での実行が容易

逆ポーランド記法 と スタック マシン 例) ( 2 + 8 ) x ( 5 - 1 ) 逆ポーランド記法 スタック マシン での実行 10 1 5 10 5 10 4 10 40

補足説明：　 ２ ｎ と ｌｏｇ 2 ｎ （次回、必要です） 0 回 1 0 回 1 回 2 回 3 回 4 回 5 回 6 回 log 2 n 回 … 1 2 4 8 16 32 64 2 倍 n 2 倍 1 回 2 2 倍 2 回 4 2 倍 3 回 8 2 倍 4 回 16 2 倍 5 回 32 2 倍 6 回 64 2 倍 … … 2 倍 n 回 2 n

１つのスタックだけを用いて出力可能なデータ列はどれか ア. A, D, B, C イ. B, D, A, C ウ. C, B, D, A 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか ア. A, D, B, C イ. B, D, A, C ウ. C, B, D, A エ. D, C, A, B (H16年度 春) ウ

A 列 1 2 行 1 “東京” 2 2 “品川” 3 3 “名古屋” 4 4 “新大阪” 5 “新横浜” 第１の操作 第２の操作 ア 練習：　配列を用いたリストの実現 [ 東京、品川、名古屋、新大阪 ] [ 東京、新横浜、名古屋、新大阪 ] A 列 1 2 行 1 “東京” 2 2 “品川” 3 3 “名古屋” 4 4 “新大阪” 5 “新横浜” 第１の操作 第２の操作 ア 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) イ 5 → A(1, 2) A(A(2, 2), 2) → A(5, 2) ウ A(A(1, 2), 2) → A(5, 2) 5 → A(1, 2) ウ エ A(A(2, 2), 2) → A(5, 2) 5 → A(1, 2)

この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史　2007-2009 horiyama@al.ics.saitama-u.ac.jp 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 2, 5 ～ 9, 11 ～ 15, 17, 19, 25, 27 クリップアート : Microsoft Office Online / クリップアート p. 6, 11 メモリ : http://webweb.s92.xrea.com/ その他 堀山 貴史