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

Presentation on theme: "情報数理Ⅱ 第11章　データ構造 平成29年1月18日."— Presentation transcript:

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

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

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

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

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

6 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セルのポインタ以外は変更していない！

7 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セルのポインタ以外は変更していない！

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

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

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

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

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

13 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

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

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

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

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

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

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

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

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

22 例題 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

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

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

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