基本情報技術概論 (第４回) データ構造埼玉大学理工学研究科堀山貴史 1 前回までの復習（計算の仕組みの基礎）  数値、文字の表現方法  四則演算 (＋, －, ×, ÷)   10進法での筆算と同じようにできる２進数では、０, １を操作すれば実現できるハ  論理素子ー  ０, １の「入力」から、０, １の「出力」を得る仕組みドウェ  論理回路ア  論理素子を用いて、の計算を実現する仕組み基礎  組合せ回路、順序回路 2 ソフトウェアの基礎ハードウェア (hardware) … 装置ソフトウェア (software) … 装置を動かすための情報 3 データ構造  データ構造  データをどのように記憶するか  基本的なデータ構造  配列 (array)  リスト (list) ___________  その他のデータ構造  スタック (stack)  待ち行列 (queue, キュー)  木 (tree) ___________ 4 データ構造： ________________ 配列  データを順番にならべて、添字でアクセスできるようにしたもの ________  操作：参照、探索、更新、削除、挿入配列 A A [1] 30 A [2] 50 A [3] 20 A [4] 70 A [5] 10 … 5 コンピュータ上での配列配列 A A [2] 50 A [4] 70 A [5] 10 … 70 10 … 20 30 50 20 A [1, 1] A [1, 2] … A [2, 1] A [2, 2] … A [3, 1] A [3, 2] … … A [3] 番地 2000 （アドレス） 2001 2002 2003 2004 … 30 … A [1] 二次元配列メモリ（主記憶装置）一次元に変換してメモリに配置する … … 6 探索キー配列の操作（探索データ） 70  参照  探索 A [1] 30 A [2] 50 A [3] 20 70 A [4] 70 10 A [5] 10 A [1] 30 A [2] 50 A [3] 20 A [4] A [5] 配列Aの 4番は？ … … 添字を使って指定 … A[4] 先頭 A[1] から順番に一致するか調べる 7 A[4] の位置に 35 を挿入 70 を更新  更新  挿入 A [1] 30 A [1] 30 A [2] 50 A [2] 50 A [3] 20 A [3] 20 A [4] 35 70 A [4] 70 A [5] 10 A [5] 10 … … 70 を探索 + 更新 35 A[4] の場所を空けるため、後ろに１つずつずらす 8 A[4] の位置のデータを削除  削除 A[4] の位置のデータを削除  削除（その２） A [1] 30 A [1] 30 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[4] に削除マークをつけて、無いものとして扱う 9 データ構造： ________________ リスト  となりの要素の位置（アドレス）を、ポインタとして明示的に持つ ________ 単方向リスト双方向リスト環状リスト head (リストの先頭を指す) 30 30 30 50 50 50 20 20 20 逆方向の探索が容易 10 コンピュータ上でのリストメモリ（主記憶装置） 2000 2010 50 番地 2010 （アドレス） 30 2070 20 2030 20 0 2070 50 2030 … … 30 となりの要素の位置（アドレス）を、ポインタとして明示的に持つ 11 リストの操作  探索探索キー（探索データ）  更新 20 を更新 20 30 30 50 50 20 35 20 70 70 先頭から順番にポインタをたどって調べる 20 を探索 + 更新 12 リストの操作  挿入 50 の次に 35 を挿入  削除 20 を削除 30 30 50 50 35 20 20 70 70 前のデータのポインタを、自分に自分のポインタを、次のデータに前のデータのポインタを、次のデータに 13 練習：    配列を用いたリストの実現表は、配列を用いたリストの実現を示しており、リスト [ 東京、品川、名古屋、新大阪 ] を表している。このリストを、[ 東京、新横浜、名古屋、新大阪 ] に変化させる操作はどれか。ここで、A ( i, j ) は、表の第 i 行第 j 列の要素を表す。また、→ は代入を表す。 A 列 1 行 1 “東京” 2 “品川” 3 “名古屋” 4 “新大阪” 5 “新横浜” 2 2 3 4 0 14 練習：アイウエ配列を用いたリストの実現第１の操作 5 → A(1, 2) 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) A(A(2, 2), 2) → A(5, 2) 第２の操作 A(A(1, 2), 2) → A(5, 2) A(A(2, 2), 2) → A(5, 2) 5 → A(1, 2) 5 → A(1, 2) 15 データ構造  基本的なデータ構造  配列 (array)  リスト (list)  その他のデータ構造  スタック (stack)  待ち行列 (queue, キュー)  木 (tree) 16 データ構造： ________________ スタック  push と pop による Last-In First-Out (LIFO) ___________ イメージ）積み上げた書類や本生協の入口のトレイ 5 push pop 30 50 20 17 スタックの実現法 5 push pop  A [1] A [2] A [3] 20 50 30 … 30 50 20 配列スタックポインタ  リスト 30 50 20 18 データ構造：待ち行列（キュー） ________________  enqueue と dequeue による First-In First-Out (FIFO) ___________  イメージ）レジの前の行列 5 enqueue 30 50 20 dequeue 19 キューの実現法 5  enqueue front A [1] A [2] A [3] 20 50 30 rear … 30 50 20 配列 dequeue  リスト front 20 rear 50 30 20 ポーランド記法  と逆ポーランド記法演算 a + b を以下のように記す方法   ポーランド記法逆ポーランド記法 + a b a b + … 日本語で「a に b を加える」  ( ) を使う必要がない  例) ( a + b ) x ( c - d ) 逆ポーランド記法 a b + c d - x  スタックマシンでの実行が容易 21 逆ポーランド記法とスタックマシン  例) ( 2 + 8 ) x ( 5 - 1 ) 2 8 + 5 1 - x 逆ポーランド記法  スタックマシンでの実行 5 10 2 8 2 10 1 5 10 4 10 40 22 23 補足説明： 1 2 4 8 16 32 64 … … n回 2n 2倍 2倍 2倍 2倍 2倍 2倍 2倍 2倍ｌｏｇ 2 ｎ 0 1 2 3 4 5 6 （次回、必要です）回回回回回回回 1 2 4 8 16 32 64 … 回回回回回回回と … 0 1 2 3 4 5 6 ｎ２ log 2 n 回 n 2倍 2倍 2倍 2倍 2倍 2倍 2倍 2倍 24 練習：  スタック A, B, C, D の順に到着するデータに対して、１つのスタックだけを用いて出力可能なデータ列はどれか (H16年度春) ア. イ. ウ. エ. A, D, B, C B, D, A, C C, B, D, A D, C, A, B 25 26 練習：配列を用いたリストの実現 [ 東京、品川、名古屋、新大阪 ] [ 東京、新横浜、名古屋、新大阪 ] アイウエ第１の操作 5 → A(1, 2) 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) A(A(2, 2), 2) → A(5, 2) A 列 1 行 1 “東京” 2 “品川” 3 “名古屋” 4 “新大阪” 5 “新横浜” 2 2 3 4 0 第２の操作 A(A(1, 2), 2) → A(5, 2) A(A(2, 2), 2) → A(5, 2) 5 → A(1, 2) 5 → A(1, 2) 27 28 29 この教材のご利用について     この文面は、TOKYO TECH OCW の利用条件を参考にしましたこの教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。非商業利用に限定  この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。著作権の帰属  この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。同一条件での頒布・再頒布  この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件30 この教材のご利用について  配布場所  http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/  この powerpoint ファイルの著作者  堀山貴史 2007-2009 [email protected]  改変等を加えられた場合は、お名前等を追加してください図の著作者  p. 2, 5 ～ 9, 11 ～ 15, 17, 19, 25, 27  クリップアート : Microsoft Office Online / クリップアート  p. 6, 11  メモリ : http://webweb.s92.xrea.com/  その他  堀山貴史  31