データ構造の基本

データの型

すでに述べたとおり、データ構造とは大量のデータを効率よく管理する仕組みのことを言います。では、コンピュータにおけるデータとは、いったい何でしょうか?コンピュータには、一口にデータと言っても、非常に様々なものがあります。そのようなデータのグループ分けのことを、データ型と言います。データ型は、使用するコンピュータにより多少の違いはあります。また、そのデータを具体的に表したものを値(あたい)と言います。

主なデータ型

よく利用されるものを大別すると、以下のようなものがあります。(表3-1.)記述方法や名前などは、使用する言語により多少の違いはありますが、現在主流の言語はほぼこれらのデータ型をカバーしています。

表3-1.主なデータ型
型名内容
整数型整数値(小数を含まない数値)を扱うためのデータ型0,1,-4,999,-512
実数型実数値(小数を含む数値)を扱うデータ型3.14,4.2,-12.3,0.1
文字型1文字を扱うためのデータ型a,b,A,B
文字列型文字列を扱うためのデータ型ABC,Japan,あいうえお
論理型論理演算の「真」および「偽」を扱うデータ型true,false

変数

アルゴリズムにおいて、データを扱う際、そのデータをメモリ上に保存しておく必要があります。その領域のことを、変数(へんすう)と言います。イメージとしては、変数はデータを入れるための箱のようなものです。

変数は必要に応じて、メモリ空間の許す限りいくらでも定義できますが、それらのものを区別するために、名前を付けることができます。これを、変数名と言います。使用する言語により規定は異なりますが、多くの場合、アルファベットと数値および一部の記号の組み合わせで構成されています。

また、変数には、データ型と同じ型があり、同一のデータ型を持つデータを保存することができます。変数にデータ(値)を入れることを、代入(だいにゅう)と言います。代入は、多くの言語で「変数名=値」のような形で定義するのが一般的です。(図3-1.)

図3-1.変数
変数

様々なデータ構造

主なデータ構造

すでに説明してあるとおり、データ構造とアルゴリズムは、切っても切り離せない関係にあります。多くのアルゴリズムは、このデータ構造を使うことを前提として作られています。つまり、アルゴリズムの理解には、データ構造の知識が不可欠なのです。そこで、ここでは主なデータ構造について説明します。主なデータ構造は、以下のようになります。(表3-2.)

表3-2.主なデータ構造
名前内容
配列(はいれつ)同じ種類のデータを、複数ならべたデータ構造を、配列と言います。一直線上の並べた1次元配列、長方形のように縦横にならべた二次元配列、さらに高次元の3次元配列などがあります。大きさなどはあらかじめ固定されています。
リスト同じ種類のデータに順序付けして並べたデータ構造をリストと言います。配列との大きな違いは、順序付けができるほかに、配列がサイズが固定的であるのに対し、データの挿入・削除などが容易にできる点にあります。
スタック机に本を積み重ねていくように、データを管理するほうほうです。データを入れた順序と、逆順にデータを取り出すことができるのが特徴です。
キュースタックとは逆に、データを入れた順に取り出すことができるデータ構造です。
ツリー木(ツリー)を逆さにしたような構造を持ち、枝先にデータを持ち、さらにそこからまた枝分かれしていく構造をツリー構造と言います。

多くのアルゴリズムは、これらを1つ、もしくは複数用いることを前提にしています。したがって、アルゴリズムとセットで学習する必要があります。入門編では、一番基本となるアルゴリズムである、配列について説明します。

配列

配列とは

アルゴリズムにおいて、大量のデータを扱う際に保持しておくために使用されるのが、配列です。たとえば、次のようなデータを扱う場合、配列を利用すると大変便利です。

こういった配列で扱うデータには必ず同種のデータでなければならないという原則があります。つまり、大量にあるからといって、「テストの点数」と「顧客の名前」という、性質の違うデータを同一の配列で扱うことはできません。

一次元配列

配列の扱い方は、変数の場合と同様、配列変数と呼ばれる変数で取り扱います。この変数の名前を配列名と言います。配列には大きく分けて、一次元配列と、多次元配列がありますが、ここでは、基本である一次元配列のケースについて説明します。

あたかも複数の箱を一直線に並べたものが、一次元配列です。配列の箱一つのことを配列要素と言い、その数のことを配列要素数と言います。配列要素は、それぞれ先頭から連番の番号がついています。この番号のことを、要素番号と言います。一般的に、要素数Nの配列は、番号0からN-1までの要素番号が割り振られます。(図3-2.)

具体的にいうと、配列変数aの要素数が6だったとします。こんとき、a[0]、a[1]、・・・ 、a[5]という6個の独立した配列要素が使用可能になります。なお、この要素番号のことを、通常、配列の添え字(そえじ)と呼びます。

図3-2.配列(一次元配列)
配列(一次元配列)

多次元配列

一次元配列が、変数を一直線上に並べたものであるのに対し、二次元配列は、変数と縦と横に長方形の形に隙間なくならべたものになります。またさらに、これに上方向なども加われば、三次元配列と言われるものになります。同様に、理論上は四次元、五次元といった配列を作ることができます。このような、2次元以上の配列を、多次元配列と言います。

このように、二次元以上の配列の総称を、多次元配列と言います。このうち、最も使用頻度が高いものが、二次元配列です。二次元配列のイメージは、表計算ソフトの表のような使い方がなされます。そのため、年度を縦軸、月を横軸として各年・月の売り上げを管理する表などといった利用ができます。また、オセロゲームのような、ゲーム版におく白黒ピースの状態の管理といった使い方も可能です。

図3-3.二次元配列
二次元配列