２章　データ構造.

Presentation on theme: "２章　データ構造."— Presentation transcript:

1 ２章　データ構造

2 データ構造 本章では基本的なデータ構造を紹介する 本章で紹介する基本的なデータ構造 ２．１ リスト ２．２ スタックとキュー ２．３ グラフ
２．１　リスト ２．２　スタックとキュー ２．３　グラフ ２．４　木 ２．５　ヒープ

3 ２．１　リスト ３，５，２，１，４の順でデータを保存 リスト構造 ３ ５ ２ １ ４ ポインタ ３ ５ ２ １ ４ 配列 ３ ５ ２ １ ４

4 リストの基本操作 初期化 探索 挿入 削除

5 データへのアクセス 場面をサーチ データを検索 ３ ５ ２ １ ４ ビデオテープ ３ ５ ２ １ ４ DVD

6 データの挿入 ６ ポインタ ３ ５ ２ １ ４ ６ 配列 ３ ５ ２ １ ４

7 データの削除 ポインタ ３ ５ ２ １ ４ 配列 ３ ５ ２ １ ４

8 データの検索（違いはあるか？） ・ ２はあるか？ ６はあるか？ ３ １ ６ ７ ４ ３ １ ６ ７ ４
・　２はあるか？　６はあるか？ ポインタ ３ １ ６ ７ ４ 配列 ３ １ ６ ７ ４ ・　データが小さい順に並んでいたらどうか？ ポインタ １ ３ ４ ６ ７ 配列 １ ３ ４ ６ ７

9 ２．２ スタックとキュー スタック ：後入れ先出し （LIFO） キュー ：先入れ先出し （FIFO)
２．２　スタックとキュー スタック ：後入れ先出し　（LIFO） 木構造、入れ子構造、括弧対応、ディレクトリ構造 深さ優先探索 キュー ：先入れ先出し　（FIFO) 最短路、辞書式順序 幅優先探索

10 スタック C B A C B A

11 キュー C B A

12 スタック ･全てのディレクトリを探査せよ / home local etc home user etc user local

13 スタック、入れ子構造、括弧対応 ( ( ( ) ), ( ) ) / home home etc user etc user local
( ( ( ) ), ( ) )

14 キュー ･各頂点に対しAからの距離を求めよ A B C G F B C E I A D H D E F G H I ２ ０ ３ １ ３ ２
４