本記事の内容
本記事は、基本情報技術者試験におけるデータ構造について情報及びコンピュータの素人目線から説明する記事です。
本記事を読むに当たり、特別必要な知識はありません。
前回の記事(オートマトン)は以下をご覧ください！
イントロ
コンピュータは複雑な処理を行っています。
しかし、コンピュータが処理の途中で迷子になることはありません。
なぜならば、データの並べ方を工夫しているからなのです。
コンピュータが扱う情報のこと「データ」といいます。
データはコンピュータ内にある「主記憶装置」と呼ばれる記憶装置に保存されます。
(※主記憶装置については後の記事で述べます。)
コンピュータの処理効率はデータの並べ方で大きく変わります。
故に、主記憶装置に保存されているデータは、処理の内容はその時の状況に応じて、様々な方式で並べられます。
この主記憶装置上のデータの並べ方のことをデータ構造といいます。
データ構造
主記憶装置上のデータの並べ方のことをデータ構造という。データ構造の種類
データ構造の種類は、以下の5種類が存在します。
すなわち、主記憶装置上のデータの並べ方が5種類存在します。
- スタック：最後に格納したデータを最初に取り出す方式
- キュー：最初に格納したデータを最初に取り出す方式
- 配列
- 連結リスト
- 木構造
基本情報技術者試験では、「データの構造の種類」と「それぞれの特徴」が問われます。
※ちなみに、試験では「スタック」が最頻出のようです。
スタック
スタック
スタックとは、データを1列に並べて、最後に格納したデータを最初に取り出すデータ構造を指す。イメージとしては、積み上げられた本です。
1冊の本がデータに対応しています。
本を積み重ねるときは順々に上に上に積み重ねます(データを保存するとき)。
一方で、取り出すときは、1冊ずつ最上部から取り出します(データを取り出すとき)。
この構造がスタックです。
途中にある本を一気に取り出すことは出来ないことに注意です。
スタックの最大の特徴は
コンピュータがいつでも元の処理に戻ることでできる点
です。
なぜならば、保存されている処理の履歴を順々に1つずつ戻っていけば、元の処理にたどり着くからです。
ヘンゼルとグレーテルという童話で、ヘンゼルがパンくずを落としながら森の中を歩き、予め落としてきたパンくずを目印にして元の場所に戻るという描写がありますが、そんな感じです。
スタックへのデータの出し入れ
push、pop
- push スタックにデータを格納することをpush(プッシュ)という。
- pop スタックからデータを取り出すことをpop(ポップ)という。
例えば、「X」というデータをスタックに格納する場合は、「push X」と書きます。
しかし、取り出す場合は「push」のみです。
なぜならば、スタックは、最上部に格納されているデータ(つまり、一番最後に格納したデータ)しか取り出せないので、pushのようにデータを指定する必要がないからです。
つまり、「pop X」のような書き方はしません。
ちなみに、スタックのように、後に入れたデータを先に取り出すアルゴリズムを後入れ先出し(LIFO：Last In First Out)といいます。
キュー
キュー
キューとは、データを一列に並べて、最初に格納したデータを最初に取り出すデータ構造を指す。また、待ち行列とも呼ばれる。ところてんのような方式です。
もっと身近で言えば、レジ待ちのお客さんといったところです。
お客さんがデータです。
お客さんは列の最後に並び、最初に並んだ人が最初に会計をします。
列の途中に割り込むことは出来ません(データとデータの間にデータを格納することはできない)。
キューというデータ構造を使うメリットは
命令を入力した順番通りに処理できること
です。
キューへのデータの出し入れ
enqueue、dequeue
キューにデータを格納することをenqueue(えんきゅー)といい、キューからデータを取り出すことをdequeue(できゅー)という。例えば、「X」というデータをキューに格納する場合は、「enqueue X」と書きます。
しかし、スタックと同様に取り出すデータは決まっていますので、「dequeue X」とは書きません。
ちなみに、キューのように先に入れたデータを先に取り出すアルゴリズムを先入れ先出し(FIFO：First In First Out)といいます。
配列
配列、要素、添字
配列とは、データを表の形に並べたデータ構造を指す。また、配列において1つ1つのデータを要素と呼び、要素の位置を表す数字を添字という。ただし、プログラムの言語によっては、添字をインデックスと呼ぶこともある。
要するに、表の中にデータを入れたり取り出したりする事ができる構造を配列と呼ぶわけです。
一次元配列
一次元配列
配列の中でも、要素が一列にならぶ配列を一次元配列という。添字が「1」からでなく「0」から始まっている、と言うことに注意です。
コンピュータのデータ構造では、番号は通常0から始まります。
配列から1つの要素を取り出す
配列から1つの要素を取り出す場合は配列の後に( )をつけて、その中に添え字を書きます。
例えば、先程の図の中にある配列Aの先頭から3番目の要素である「鈴木」を取り出す場合は「A(2)」と書きます。
つまり、「A(2)=鈴木」です。
ちなみに、( )は[ ]の場合もあります。
C言語では[ ]を用います。
二次元配列
二次元配列
配列の中でも、要素が縦横に並ぶ配列を二次元配列という。二次元配列では要素の横の並びを「行」、縦の並びを「列」といいます。
数学における行列と同じです。
二次元配列から要素を取り出す場合は、添字を「行,列」で指定します。
例えば、上図の二次元配列Aの1行3列の要素である「東京都」を取り出す場合は「A(1,3)」と書きます。
つまり、「A(1,3)=東京都」です。
連結リスト
連結リスト
連結リストとは、データを数珠つなぎに並べたデータ構造を指す。連結リストも配列と同様に、個々のデータを要素と呼びます。
ただし、連結リストの要素は配列の要素とは異なり、データにポインタが付きます。
ポインタ
ポインタとは、次の要素のアドレス(主記憶装置上のデータの位置)を指し示す情報を指す。連結リストでは、ポインタを用いて、要素を数珠つなぎにします。
コンピュータでは、ポインタに格納されているアドレスぅをたどることで、目的のデータにアクセスします。
要するに、上図のように、1番地には「佐藤」と「7番地」というデータが格納されており、次にポインタである「7番地」にアクセスして「田中」と「3番地」というデータにアクセスします。
同様にその次は3番地にアクセスして…ということを繰り返して目的のデータにアクセスするのが連結リストです。
配列と連結リストは何が違うのか？
配列と連結リストは、データが順番に並んでいるという点において同じです。
しかしながら、「データにアクセスする方法」が異なります。
- 配列：データに直接アクセス
- 連結リスト：リストの先頭から順番に要素を辿ってアクセス
連結リストの場合、要素の数が多ければ多いほど目的のデータのアクセスには時間を要します。
となれば、「配列のほうが良くない？」と思うかも知れませんが、連結リストには連結リストのメリットがあります。
それは「データの挿入、削除をするとき」に現れます。
配列に要素を挿入、削除する場合は後ろの要素全てを1つずつずらさねばなりません。
そのため、要素数が多ければ多いほど処理に時間がかかります。
しかしながら、連結リストの場合はポインタを変更すればそれだけでデータの挿入、削除が可能なので処理が迅速です。
基本情報技術者試験では配列と連結リストの違いが出題されますので要注意です。
連結リストの分類
連結リストには
- 単方向リスト
先頭から末尾まで一方向にデータを繋げた連結リスト。
先頭から末尾の方向でしかデータをたどることが出来ない。 - 双方向リスト
双方向にデータを繋げた連結リスト。
先頭から末尾へ、末尾から先頭へデータをたどることができる。 - 線形リスト
先頭から末尾まで直線状に要素が繋がっている連結リスト。 - 環状リスト
末尾と先頭を繋げて環の形(環状)に要素が繋がっている連結リスト。
があります。
木構造
木構造
木構造とは、階層構造を持つデータ構造を指す。木構造の各部分の名称
上図の○で表された箇所(枝分かれする箇所)を「節」と言います。
木構造では、節がデータを保持します。
節の中でも最上位の節を「根」と言い、また末端の節を「葉」といいます。
木構造の親子関係
木構造の節同士には関係があります。
分岐元を「親」、分岐先を「子」といいます。
親は数に制限なく子を持つことが出来ます。
木構造の中でも、親が0~2個の子を持つ木構造を二分木、親が0~3個の子を持つ木構造を三分木と呼びます。
一般化すれば、親が0~\(n\)個の子を持つ木構造を\(n\)分木と言います。
すなわち、分木というのは、節が最大でいくつの子に分かれるのかを表しています。
二分木探索
二分木の中でも親子の値が
左の子孫 ＜ 親 ＜ 右の子孫
となっているものを「二分探索木」といいます。
ただし、ここでいう子孫とは、「親よりも下にあるデータ」を指します。
二分探索木のメリット
なぜ「左の子孫＜親＜右の子孫」の関係に並べるかというと、データを見つけるのに便利だからです。
二分探索木では、根から葉までの階層の数だけ値を調べれば、目的のデータを見つけ出すことが出来ます。
一方で、親子が無関係に繋がった木構造では、節を1つずつ調べる必要があります。
つまり、無関係な状態で勝手に木構造を作ってしまうと結局全探索しないといけなくなるので、某かの関係を入れる必要があり、その一例が先の関係ということなのです。
復習問題
実際に出題された問題を一緒に解いてみましょう！
データ構造の一つであるリストは、配列を用いて実現する場合と、ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで、配列を用いたリストは、配列に要素を連続して格納することによって構成し、ポインタを用いたリストは、要素から次の要素へポインタで連結することによって構成するものとする。
- 位置を指定して、任意のデータに直接アクセスすることができる。
- 並んでいるデータの先頭に任意のデータを効率的に挿入することができる。
- 任意のデータの参照は効率的ではないが、削除は挿入の操作を効率的に行える。
- 任意のデータを別の位置に0移動する場合、隣接するデータを移動せずにできる。
答え
1配列を用いたリストでは、添字を使うことでデータを直接参照できます。
一方で、ポインタを用いたリスト(連結リスト)では、リストｎ先頭から順番に要素をたどっていく必要があり、そのために要素数が多ければ多いほど参照に時間がかかります。
その他の選択肢は全て連結リストの特徴です
結
今回は、基本情報技術者試験におけるデータ構造、アルゴリズム、プログラムについて、情報及びコンピュータの素人目線から説明しました。
問題が解けるということに重きを置き説明しました。
データの構造には
- スタック：最後に格納したデータを最初に取り出す方式
- キュー：最初に格納したデータを最初に取り出す方式
- 配列
- 連結リスト
- 木構造
があるのでした。
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、この記事に限らず、「定理〇〇の△△が分からない！」などいただければお答えします！
Twitterでもリプ、DM問わず質問、コメントを大募集しております！
コメントをする