takahiro_itazuriの公倍数的ブログ

本やWebを通して学習したことをまとめるブログです。最大公約数(つまり、共通部分)的なという表現と対比して、「なるべく包括的にカバーしつつ、更に+αの要素も加えられたらいいな」という意味で公倍数的ブログと名付けました。

データ型

データ構造の第1回目です。
データ構造とアルゴリズムの目次ページはこちら

データ型

データ型とは「プログラミングを書く際のデータの管理の仕方を決めるもの」です。
、、、と言われましても、わかりにくいと思いますので、もう少し詳しく掘り下げていきます。

データ型は基本型抽象データ型の大きく二つに分類されると言われています。
では、これらを説明していきましょう。

基本型

基本型とは「各プログラミング言語でサポートされている型」のことを指します(改めて言うほどのものでもないのですが)。
大抵の言語には次のような型が用意されていると考えられます。

などなど他にもたくさんあるかもしれませんが、とくかく各言語で予め用意してくれているものを基本型と言います。

抽象データ型

抽象データ型とは「データ構造とそれを直接操作する手続き(関数)をまとめてデータ型の定義とするもの」のことを指します。
なんだか突然表現が難しくなりましたね(笑)
先程の基本型と対比した形で述べると、「自分自身で定義した型」とも言うことができます。
これなら理解できますね。
これはC/C++などでいうところの構造体やクラスなどに当たります。

f:id:takahiro_itazuri:20170706230429p:plain:w250 f:id:takahiro_itazuri:20170706230439p:plain:w250

作ったことのない人にもわかるように説明します。
データとは時にまとめて扱った方が良い場合が存在します。
例えば、あなたが学校の先生だったとして、生徒の名前、学年、クラス、身長、体重などのデータを保持していた場合を考えましょう。
これら全てを全て別々に保存しておいた場合、大変なことになるのは目に見えています。
そこで生徒ごとにファイルを作成し、そのファイルに先程の名前や学年などをまとめて保持しておく方が効率が良いことが直観的にわかるでしょう。
またそれらの情報をどのように扱えば良いかを一緒にまとめてあげるとなおよいでしょう。
このような考え方が抽象データ型と言われます。
英語では、abstract data typeと書くことからADTと省略されることもあります。

データ構造

データの保持の仕方は、その時々で最適化ものは異なります。
そこで本ブログでは、いくつか有名なデータ構造を数回に分けて紹介します。
先程、抽象データ型はデータをまとめる構造だけでなく、それを操作する手続き(関数)を用意すると述べました。

抽象データ構造の操作は一般的に「アクセス(Access)」「挿入(Insert)」「削除(Delete)」「探索(Find, Search)」の4種類があります。
アクセスとは、特定の要素を参照する。
挿入とは、新たなデータを特定の場所に挿入する。
探索とは、指定されたデータを探索する。
削除とは、指定されたデータを特定の要素を削除する。

本ブログでは線形データ構造とグラフデータ構造を紹介すると同時に、それぞれのデータ構造におけるそれらの操作の仕方や得意、不得意についても説明できればと思っています。
データ構造は大きく「線形データ構造」「グラフデータ構造」の二つに分けることができます。

線形データ構造

線形データ構造とは、データの集合を一列に順番に格納したものです。
しかし、メモリの確保の仕方や要素の追加・削除方法の違いからいくつか種類があります。

f:id:takahiro_itazuri:20170707075655p:plain:w500

グラフデータ構造

一方でグラフデータ構造とは、データの集合を任意の数のリンクによって管理するものです。
こちらもグラフ構造のリンクの向きやリンクの個数などによっていくつか種類が存在します。
f:id:takahiro_itazuri:20170707080316p:plain:w300