« ^ »
[WIP]

データ構造

所要時間: 約 2分

データ構造

配列


+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+

ヒープ


                       +---+
                       |   |
                       +-+-+
                         |
            +------------+-----------+
            |                        |
          +-+-+                    +-+-+
          |   |                    |   |
          +-+-+                    +-+-+
            |                        |
     +------+------+             +---+
     |             |             |
   +-+-+         +-+-+         +-+-+
   |   |         |   |         |   |
   +-+-+         +-+-+         +-+-+
     |             |             |
  +--+---+      +--+---+      +--+
  |      |      |      |      |
+-+-+  +-+-+  +-+-+  +-+-+  +-+-+
|   |  |   |  |   |  |   |  |   |
+---+  +---+  +---+  +---+  +---+

リングバッファ


            +---+       +---+
  +---------+   +-------+   +---------+
  |         +---+       +---+         |
  |                                   |
  |                                   |
+-+-+                               +-+-+
|   |                               |   |
+-+-+                               +-+-+
  |                                   |
  |                                   |
+-+-+                               +-+-+
|   |                               |   |
+-+-+                               +-+-+
  |                                   |
  |                                   |
  |         +---+       +---+         |
  +---------+   +-------+   +---------+
            +---+       +---+

ハッシュテーブル


+---+---+---+---+
|   |   |   |   |
+-+-+-+-+-+-+-+-+
  |   |   |   |
  |   |   |   +---------------------------------------+
  |   |   +-----------------------------------+       |
  |   +---------------------------+           |       |
  +-------------------+           |           |       |
                      |           |           |       |
                      v           v           v       v
        +---+---+---+-+-+---+---+-+-+---+---+-+-+---+-+-+
        |   |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+

連結リスト

+---+
|   |
+-+-+
  |
  v
+-+-+
|   |
+-+-+
  |
  v
+-+-+
|   |
+-+-+
  |
  v
+-+-+
|   |
+-+-+
  |
  v
+-+-+
|   |
+---+

双方向連結リスト

隣接する要素の情報を互いに保持し、隣り合っていれば辿れる状態になっているリスト。glibのGListは双方向リストとして実装されている。

+-----+
|     |
+-+-+-+
  | ^
  v |
+-+-+-+
|     |
+-+-+-+
  | ^
  v |
+-+-+-+
|     |
+-+-+-+
  | ^
  v |
+-+-+-+
|     |
+-+-+-+
  | ^
  v |
+-+-+-+
|     |
+-----+

グラフ



     +---+     +---+     +---+
     |   +--+  |   +-----+   |
     +-+-+  |  +---+     +-+-+
       |    |              |
       |    +--------------+
       |    |
     +-+-+  |  +---+     +---+
     |   |  +--+   |     |   |
     +-+-+  |  +---+     +---+
       |    |
       |    |
       |    |
     +-+-+  |  +---+     +---+
     |   +--+--+   +-----+   |
     +---+     +---+     +---+

2分木


                       +---+
                       |   |
                       +-+-+
                         |
            +------------+--------------+
            |                           |
          +-+-+                       +-+-+
          |   |                       |   |
          +-+-+                       +-+-+
            |                           |
     +------+------+             +------+------+
     |             |             |             |
   +-+-+         +-+-+         +-+-+         +-+-+
   |   |         |   |         |   |         |   |
   +-+-+         +-+-+         +-+-+         +-+-+
     |             |             |             |
  +--+---+      +--+---+      +--+---+      +--+---+
  |      |      |      |      |      |      |      |
+-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+  +-+-+
|   |  |   |  |   |  |   |  |   |  |   |  |   |  |   |
+---+  +---+  +---+  +---+  +---+  +---+  +---+  +---+

線形と非線形

線形データ構造

  • 配列
  • ヒープ
  • リングバッファ
  • ハッシュテーブル

非線形データ構造

  • 連結リスト
  • 2分木
  • グラフ

固定長か可変長か

固定長のデータ構造では、領域を確保すると長さを増やしたり減らしたりでき ない。コンパイル言語ではコンパイル時に必要なサイズを決定できるため、動 的に領域を確保する必要はない。可変長のデータ構造は、領域を確保した後で も長さを増やしたり減らしたりできる。可変長であるため、コンパイル時に必 要な長さを決定できず、実行時に領域を確保する必要がある。

固定長

  • 配列
  • ヒープ
  • リングバッファ
  • ハッシュテーブル

可変長

  • 連結リスト
  • 2分木
  • グラフ

データ構造ではないが構造を持つもの

ファンイン



+------+   +------+
|      |   |      |
|      |---|      +------+
|      |   |      |      |
+------+   +------+      |
                         |
+------+   +------+      |       +------+
|      |   |      |      v FanIn |      |
|      |---|      +----->+------>+      |
|      |   |      |      ^       |      |
+------+   +------+      |       +------+
                         |
+------+   +------+      |
|      |   |      |      |
|      |---|      +------+
|      |   |      |
+------+   +------+