第7回　組込みソフトウエア開発の基礎

　今回は，組込みソフトウエア開発の基礎に関する例題を2問とりあげます。例題は，いずれも基礎的な知識で解答できますので，第一区分となります。

例題1　テーマ：データ構造

【解説】
　データ構造とは，コンピュータの中でデータの集まりを効果的に扱うことができるように定めたデータの格納形式のことを表します。データ構造には様々な種類があり，それぞれに利点，欠点があります。コンピュータでデータを処理する際のデータ構造は，プログラムの速度，開発のしやすさ，保守性などに影響を及ぼすため，適切に選択することが非常に重要です。

---

　選択肢1のスタックは，後入れ先出し（LIFO：Last In First Out）方式のデータ構造で，箱に上から書類を入れる場合のように，最後に入れたものを先に取り出すことができるデータ構造です。スタックにデータを入れる操作のことをpush，スタックからデータを取り出す操作のことをpopと呼びます（図1）。スタックはプログラムにおける関数呼び出し時にプログラムカウンタなどの情報を保存し，関数の実行の終了時に保存した情報を取り出して元の状態に戻すといった用途で利用することができます。また，スタックを利用することで関数呼び出しの入れ子や再帰呼び出しを実現することが可能になります。従って，対応するデータは（イ）となります。

図1●スタック

---

　選択肢2の配列は，データの集合をインデックスと呼ばれる数値によって区別するデータ構造です。プログラミング言語の変数は通常一つのデータしか格納できませんが，配列を利用することで，同じ名前の変数に複数のデータを格納できるようになります。それぞれのデータはインデックスで区別します。このような変数のことを配列変数と呼びます。（エ）のように，重複しない連続した数値（出席番号）によって区別することができるデータは，配列を利用することで容易に表現することができます。例えば，C言語で出席番号が1～50までのクラスの生徒の成績を表すデータは

　int    score[51];

のような配列変数を定義して格納します。この場合それぞれの学生の成績は以下のように変数scoreのインデックス部分に出席番号を指定した配列変数に格納します（図2）。従って対応するデータは（エ）となります。

　score[出席番号]

図2●配列

---

　選択肢3のキューは，先入れ先出し（FIFO：First In First Out）方式のデータ構造で，駅の改札口で順番を待つ人のように，最初に入れたものを先に取り出すことができるデータ構造です（図3）。（ア）のプリンタの出力予定ファイルのように，先に印刷操作を行ったファイルから順番に印刷するような場合はキューを利用します。従って対応するデータは（ア）となります。

図3●キュー

---

　選択肢4のハッシュテーブルはハッシュ値と呼ばれる数値を使ってデータの挿入，削除，検索を高速に行うことができるようにするデータ構造です（図4）。ハッシュ値とは文字列などのデータを特定の計算によって数値に変換したもので，変換前のデータをキー，変換に使われる関数のことをハッシュ関数と呼びます。例えば文字列を数値に変換するハッシュ関数を利用することで，文字列をインデックスとした配列を実現するとこができます。Perlなどのプログラミング言語では連想配列によってハッシュテーブルのデータ構造を利用することができます。（ウ）の場合，顧客の名前を数値に変換するハッシュ関数を用いたハッシュテーブルを用意することで，顧客のデータを表現するデータ構造を作成することができます。従って対応するデータは（ウ）となります。

図4●ハッシュテーブル

===

　この例題では4つの代表的なデータ構造を題材にしていますが，これ以外にも木構造，リスト構造など様々なデータ構造があり，それぞれに利点，欠点があります。ソフトウエアを開発する際に，適切でないデータ構造を採用してしまうと，ソフトウエアの実行速度の低下，必要なメモリ容量の増大，ソフトウエアの開発効率や保守性の低下など様々な弊害の原因となってしまいます。そのようなことを避けるためにも，代表的なデータ構造についてはしっかりとした知識を身につけてください。