情報数理Ⅱ 第11章　データ構造 平成29年1月18日

本日の学習内容と目的 ＜学習内容＞ ＜目的＞ リスト構造 スタックとキュー 木構造 プログラミングの世界で使われる代表的なデータ構造の性質 とその活用方法を理解する。

１．リスト構造 1-1　アドレスとポインタ 1-2　線形リスト 1-3　セルの挿入・削除 1-4　双方向リスト・環状リスト　

1-1 アドレスとポインタ アドレス ポインタ → コンピュータ・メモリ データの保管場所 メモリ上の記憶位置 ↓ アドレスを指定する変数 1-1　アドレスとポインタ データの保管場所 →　コンピュータ・メモリ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２ １３ １４ １５ １６ 25 15.5 true メモリ上の記憶位置 ↓ アドレス 変数A 変数B 変数C アドレスを指定する変数 ↓ ポインタ １ ポインタA 例）ポインタの値が１→変数A（25）を指す

1-2 線形リスト 線形リスト データ部とポインタから構成されるデータのセットを考える。 →セルと呼ばれる 要素（セル）の 挿入・削除が容易 1-2　線形リスト データ部とポインタから構成されるデータのセットを考える。 →セルと呼ばれる データ ポインタ ポインタは他のセルのアドレスを指定できる。 データ１ データ３ データ２ 要素（セル）の 挿入・削除が容易 線形リスト ポインタによってつながれたリスト　→　

1-3 セルの挿入・削除 ＜セルの挿入＞ 配列の場合 ※「データ１」はD1と略記 D3の入ったセルの次にDXの入ったセルを挿入。 1-3　セルの挿入・削除 ＜セルの挿入＞ 配列の場合 D1 D2 D3 D4 D5 ※「データ１」はD1と略記 D3の入ったセルの次にDXの入ったセルを挿入。 １．「データX」の入ったセルを生成する。 ３．D3セルのポインタがDXセルを指すようにする。 ２．DXセルのポインタがD4セルを指すようにする。 D1 D2 D3 D4 D5 DX D3セルのポインタ以外は変更していない！

1-3 セルの挿入・削除 ＜セルの削除＞ 【基礎課題12-1】 ※「データ１」はD1と略記 D4の入ったセルを削除する。 1-3　セルの挿入・削除 ＜セルの削除＞ 【基礎課題12-1】 D1 D2 D3 D4 D5 ※「データ１」はD1と略記 D4の入ったセルを削除する。 ３．D3セルのポインタがD5セルを指すようにする。 D1 D2 D3 D4 D5 D4セルはリストから外れる！ D3セルのポインタ以外は変更していない！

例題 花形→伊達→轟→鮎原 5 3 轟次郎 5 3 次は、就職面接の順番を線形リストで表したものです。空欄を埋めて下さい。 先頭へのポインタ アドレス データ ポインタ 1 花形満 3 2 鮎原こずえ 伊達直人 4 轟次郎 5 矢吹丈 1 5 3 轟次郎 ①　3番目の面接者は（　　　　　　　　　　　）さんです。 ②　花形さんの次に矢吹さんを入れるには、花形さんのポインタを（　　　）に、矢吹さんのポインタを（　　　　）にします。 5 3

1-4 双方向リスト・環状リスト 双方向リスト 環状リスト 【基礎課題12-2】 1-4　双方向リスト・環状リスト 【基礎課題12-2】 双方向リスト 次のデータへのポインタに加えて、前のデータへのポインタも持ってい るリスト構造 環状リスト 　全てのデータが環状につながっているリスト構造 D1 D2 D3 D4 D5 D1 D2 D3 D4 D5

２．スタックとキュー 2-1　スタック構造 スタックとは？ 用語の説明 例題 2-2　キュー構造 キューとは？

2-1 スタック構造 スタックとは？ 挿入と削除がリスト（データの並び）の先頭に限って行われるデータ構造 挿入 削除（取り出し） 2-1　スタック構造 スタックとは？ 挿入と削除がリスト（データの並び）の先頭に限って行われるデータ構造 挿入 上から順に入れて行く。 削除（取り出し） 上から順に取り出す。 新聞ラック

用語の説明 push pop 【基礎課題12-3】 データを加える操作 データを取り出す操作 頂上（top） 底（bottom） データ２ データ１ データ３ データ４ データ４ 頂上（top） データ３ データ２ データ１ 底（bottom） データ１→データ２→データ３→データ４の順にpush データ４→データ３→データ２→データ１の順にpop

C 例題 スタックに、文字A、B、C、Dを順にpushした場合、2回目のpopで取り出せる文字は何ですか？ D C B A 【基礎課題12-4】、【基礎課題12-5】 スタックに、文字A、B、C、Dを順にpushした場合、2回目のpopで取り出せる文字は何ですか？ C D C B A

2-2 キュー構造 キューとは？ 挿入 削除（取り出し） 2-2　キュー構造 キューとは？ 挿入は末尾、そして削除は先頭のデータに対してのみ行われるデータ構造→待ち行列とも言う 先頭 末尾 挿入 末尾から順に加わる。 削除（取り出し） 先頭から順に出て行く。

用語の説明 加列（enqueue：エンキュー） 除列（dequeue：デキュー） 【基礎課題12-6】 データを加える操作 データを取り出す操作 加列（enqueue：エンキュー） 除列（dequeue：デキュー） データ１ 先頭（front） 用語の説明 データ２ データ３ データ４ データ３ データ２ データ１ 末尾（rear） データ４ データ１→データ２→データ３→データ４の順に加列 データ１→データ２→データ３→データ４の順に除列

B 例題 キューに、文字A、B、C、Dがこの順で保管されています。このとき、2回目に取り出せる文字は何ですか？ A B C D 【基礎課題12-7】、【基礎課題12-8】 キューに、文字A、B、C、Dがこの順で保管されています。このとき、2回目に取り出せる文字は何ですか？ B A B C D

３．木構造 3-1　木構造とは？ 3-2　用語の説明 3-3　2分木 3-4　2分木の走査方法

3-1　木構造とは？ 線形リストは順序（のみ）を表現するデータ構造 木構造は、階層構造を表現できるデータ構造

3-2 用語の説明 2分木：ノードから分岐する枝が2本以下の木構造 枝 根 葉 ①～⑦：ノード（節） １ 2 4 5 6 7 3 部分木 3-2　用語の説明 枝 根 ①～⑦：ノード（節） １ 2 4 5 6 7 3 部分木 親ノード 子ノード 葉 2分木：ノードから分岐する枝が2本以下の木構造

3-3 2分探索木 左の子ノード＜親ノード＜右の子ノード ＜例＞ データの探索に便利→ 2分探索が容易にできる。 【基礎課題12-9】 3-3　2分探索木 【基礎課題12-9】 ノードに入っているデータの値が次の関係を満たしている2分木 　　左の子ノード＜親ノード＜右の子ノード ＜例＞ ※　数字はノードが持つ値 4 1 3 ２ 5 6 7 データの探索に便利→ 2分探索が容易にできる。

3-4 2分木の走査方法 行きがけ順（前順） 通りがけ順（間順） 帰りがけ順（後順） 根に立ち寄る。 左部分木をなぞる。 右部分木をなぞる。 3-4　2分木の走査方法 行きがけ順（前順） 通りがけ順（間順） 帰りがけ順（後順） 根に立ち寄る。 左部分木をなぞる。 右部分木をなぞる。 ②→①→③ ①→②→③ ①→③→② 2 1 3

例題 d →b →a →c →e →f a→b→c→d→e→f a→c→b→f→e→d 【基礎課題12-10】 （１）行きがけ順になぞった時の順番は？ d a c b e f d →b →a →c →e →f （２）通りがけ順になぞった時の順番は？ a→b→c→d→e→f （３）帰りがけ順になぞった時の順番は？ a→c→b→f→e→d

配列の挿入 Ａ A[4]にデータXを挿入する。 １．A[6]を用意する。 ２．「データ５」をA[6]へ移動。 [１] [２] [３] [４] [５] Ａ データ１ データ２ データ３ データ４ データ５ A[4]にデータXを挿入する。 １．A[6]を用意する。 ２．「データ５」をA[6]へ移動。 ３．「データ４」をA[５]へ移動。 ４．「データX」をA[４]へ代入。 [１] [２] [３] [４] [５] データ１ データ２ データ３ データ４ データ５ [５] データ４ [４] [６] データ５ [５] [６] Ａ データX 挿入位置以降の要素をずらす必要がある！

学生成績簿の場合 S04001 花形満 55 ・・・ S04002 轟次郎 68 ・・・ S04003 早川みどり 85 ・・・ 学籍番号順に連なる線形リスト（あるいは配列）として表現できる。

Windowsフォルダ構成 ローカルディスク（C:） Documents and Settings Drivers VIDEO MODEM NETWORK Administrator hiko HXFSETUP.EXE ONBOARD My Documents Cookies デスクトップ ProgJava マイピクチャ 木構造：データの検索が容易になる。