データ構造とアルゴリズム論 第９章　木構造 平成30年6月27日 森田　彦.

Presentation on theme: "データ構造とアルゴリズム論 第９章　木構造 平成30年6月27日 森田　彦."— Presentation transcript:

1 データ構造とアルゴリズム論 第９章　木構造 平成30年6月27日 森田　彦

2 理解度チェック1（問題１） Java言語における「参照」に関する説明として最も適切なものを一つ選択して下さい。
１．参照とは、コンピュータメモリ上のアドレスのことである。 ２．参照とは、変数の値のことである。 ３．参照とは、変数名のことである。 ４．参照とは、連結リストというデータ構造を指す用語である。

3 理解度チェック1 解答 3B Java言語における「参照」に関する説明として最も適切なものを一つ選択して下さい。
１．参照とは、コンピュータメモリ上のアドレスのことである。 ２．参照とは、変数の値のことである。 ３．参照とは、変数名のことである。 ４．参照とは、連結リストというデータ構造を指す用語である。 青色の位置 3B アドレス（参照）

4 理解度チェック2（問題２） この連結リストの構造を表しているものは次のどれですか？ １ ２ ３ ４

5 理解度チェック2 解答 この連結リストの構造を表しているものは次のどれですか？ １ ２ ３ ４ Header=Cell1;
理解度チェック2　解答 この連結リストの構造を表しているものは次のどれですか？ １ ２ ３ ４ Header=Cell1; Cell1.Next=Cell4; Cell4.Next=Cell2; Cell2.Next=Cell3; Cell3.Next=null; H C1 C4 C2 C3

6 理解度チェック3（問題３） 空欄に入る適切な式は次のいずれですか？ １．Pos=Temp; ２．Pos=Temp.Next;
３．Pos.Next=Temp; ４． Pos.Next=Temp.Next;

7 理解度チェック3 解答 Pos: while文を抜けたあとはセルの終端を指している。 空欄に入る適切な式は次のいずれですか？
１．Pos=Temp;　　　　　　　 ２．Pos=Temp.Next; ３．Pos.Next=Temp;　　 ４． Pos.Next=Temp.Next; Pos:　while文を抜けたあとはセルの終端を指している。 終端セルの次にTempセルをくっつけるためには・・・ Pos.Next=Temp;

8 木構造とは？ 連結リストは順序（のみ）を表現するデータ構造 木構造は、階層構造を表現できるデータ構造

9 木構造の表現 階層を表現できるデータ構造 ＜メリット＞ 根 葉 ①～⑦：ノード １ 2 4 5 6 7 3 部分木
データ間の階層関係を表現できる。 検索時に威力を発揮する。

10 学習のポイント 木構造の作成の仕方（プログラミングによる）を学習する。 木構造中のデータ走査の仕方を学習する。 ここでは基礎を学習
幅広い応用→市販のテキストで

11 本章の学習の流れ 9-1節 木構造とは？ 9-2節 プログラムによる2分木の表現 9-3節 木のなぞり方（データ走査の仕方）
9-1節　木構造とは？ 　　木構造の定義（概念）の学習 9-2節　プログラムによる2分木の表現 　＊2分木の作成→【基礎課題9-1】で理解。 　＊NodeクラスからTreeクラスへの発展→【基礎課題9-2】で理解。 9-3節　木のなぞり方（データ走査の仕方） 　＊行きがけ順、通りがけ順、帰りがけ順の３つの走査方法→【応用課題9-A】で理解。 　＊【応用課題9-B】でプログラミング

12 今後の予定 7/ 4 第１０章 スタックとキュー 7/11 第２回テスト & 課題チェック 7/18 課題最終チェック（力試しの課題を含む）
7/ 4 第１０章　スタックとキュー 7/11　第２回テスト &　課題チェック 7/18　課題最終チェック（力試しの課題を含む） プリントをどれだけじっくり読んで理解しているかがポイント→理解度確認テストでチェック

13 学生成績簿の場合 学籍番号 氏名 データ構造とアルゴリズム論成績 ・・・ S04001 花形満 55 ・・・
学籍番号　氏名　データ構造とアルゴリズム論成績　・・・ S04001 　花形満　55　・・・ S04002 　轟次郎　68　・・・ S04003 　早川みどり　85　・・・ S04004 　伊達直人　45　・・・ ・・・ 学籍番号順に連なる連結リスト（あるいは配列）として表現できる。

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