プロデルで始める日本語プログラミング言語入門(#12) 「多彩なデータ構造を使いこなそう」


今回は、プロデルに用意された様々なデータ構造についてご紹介します。データ構造とは、データをどのように整理して持っておくか決めたものです。

ここでは有名なデータ構造として「辞書(ハッシュテーブル)」「キュー」「スタック」を実用例と共にご紹介します。また後半では「リンクリスト」というデータ構造を、種類を定義して作ってみます。

辞書(ハッシュテーブル)

「辞書」とは、値やオブジェクトに見出し(キー)を付けて出し入れするデータ構造です。配列では、添字として1から始まる番号で値を出し入れできますが、辞書では添字として文字列を指定して出し入れできます。

辞書のイメージ

辞書は、次のような書式で見出しと値を記憶したり取得したりできます。

// 辞書に見出しと値を設定する
[辞書型オブジェクト]([見出し])は、[値]
// 辞書から見出しに対応する値を取得する式
[辞書型オブジェクト]([見出し])

上の図の「値段表」のような辞書を作るには、次のようなプログラムを書きます。

// 辞書定数式で見出しと値を一度に設定する
値段表は、{りんご=「120」,バナナ=「80」,ぶどう=「130」}

// 辞書に見出しと値を設定する
値段表(「すいか」)は、500

// 辞書から見出しに合致する値を取得する
値段表(「りんご」)を表示する

// 辞書に保持された見出しの一覧を取得する
値段表の見出しを表示する

POSレジを作る

辞書を使って、買い物かごに入れた商品の値段を計算してレシートを作るプログラムを作ってみましょう。

「値段表」辞書を作り、スーパーマーケットすみれで取り扱っている商品の値段を入れておきます。また「買い物かご」配列に、商品名を入れておきます。

そして、「買い物かご」配列の要素を一つずつ順番に調べて、その商品名と見出しが一致する値段を値段表から取得します。その値段を「合計」変数に加えて合計を計算します。

また、レシートらしく、合計から消費税(軽減税率8%)やポイントも計算してみます。

値段表は、{りんご=120,バナナ=80,ぶどう=130,豚肉=300,牛乳=190}
買い物かごは、{「りんご」,「バナナ」,「牛乳」}

合計は、0
「---------------
スーパーすみれ
----領収書----
---------------」を報告する
買い物かごを商品にそれぞれ繰り返す
	合計は、合計+値段表(商品)
	「[商品][タブ][値段表(商品)]円」を報告する
繰り返し終わり
「---------------
小計[タブ][合計]円
消費税[タブ][合計*0.08]円
合計[タブ][合計*1.08]円
ポイント[タブ][(合計/200)の整数]pt
---------------
まいどありがとうございます」を報告する

セルフしりとりゲームを作る

次は、辞書を使って、コンピュータがいない、セルフしりとりゲームを作ってみます。

このゲームでは、画面に表示された単語(ひらがな)の末尾の文字で始まる単語を、テキストボックスに入力して[次へ]ボタンを押して、ルールに合う次の言葉を入力していきます。

[次へ]ボタンをクリックした時に次のしりとりのルールを判定します。

  1. 入力された単語が一つ前の単語の末尾の文字から始まっているかどうか
  2. 2文字以上の単語か
  3. 「ん」で終わらないか
  4. すでに言った単語を使っていないかどうか

1~3番目は、以前紹介した文字列の操作方法を活用します。

4番目のすでに言った単語を使っていないかどうかには、辞書を使います。ここでは「しりとり表」という辞書を用意して、判定でOKになった単語を「しりとり表」に設定していきます。[次へ]ボタンをクリックした時に「しりとり表」の見出しにその単語が存在しないかどうかを確認します。もし存在すれば「すでに言いました。」と表示してもう一度単語を入力してもらいます。辞書は、このようなチェック表のような用途でも使うこともできます。

しりとりを実装したプログラムは、次の通りです。
なお、セルフしりとりなので、自動では次の単語が表示されません。
(2人で順番に入力すると楽しいかも???)

また、別の辞書を作り、単語を設定することでコンピュータも作れるはずです。

// セルフしりとりゲーム //
メイン画面を表示する
待機する
メイン画面とは
	ウィンドウを継承する
	-しりとり表
	-現在単語=「しりとり」
はじめの手順
	初期化する
	ーー貼り付けた部品に対する操作をここに書きます
	しりとり表という辞書を作る
	現在単語ラベルの内容は、現在単語
終わり
初期化する手順
	ーー自動生成された手順です。ここにプログラムを書き加えても消える場合があります
		この実質大きさを{428,394}に変える
		この内容を「しりとり」に変える
		初期化開始する
		メッセージラベルというラベルを作る
			その位置と大きさを{38,87,91,28}に変える
			その内容を「末尾からはじまる単語を入れてね」に変える
			そのフォントを「MS UI Gothic,14」に変える
			その自動調整を○に変える
			その移動順を1に変える
		現在単語ラベルというラベルを作る
			その位置と大きさを{38,28,91,28}に変える
			その内容を「現在単語ラベル」に変える
			そのフォントを「MS UI Gothic,14」に変える
			その自動調整を○に変える
		単語テキストというテキストを作る
			その位置と大きさを{65,153,294,55}に変える
			その行間を48に変える
			その移動順を2に変える
			そのフォントを「MS UI Gothic,24」に変える
		次ボタンというボタンを作る
			その位置と大きさを{141,252,145,70}に変える
			その内容を「次へ」に変える
			その移動順を3に変える
			そのフォントを「MS UI Gothic,22」に変える
		初期化終了する
		この設計スケール比率を{144,144}に変える
		この決定ボタンを次ボタンに変える
終わり
	次ボタンがクリックされた時の手順
		単語は、単語テキストの内容
		もし単語の文字数が1以下なら
			メッセージラベルの内容は、「2文字以上です。」
			返す
		もし終わり
		もししりとり表に単語が存在するなら
			メッセージラベルの内容は、「すでに言いました。」
			返す
		もし終わり
		しりとり表(単語)は、○
		末尾文字は、現在単語の末尾から1文字取り出したもの
		もし末尾文字が「ん」なら
			メッセージラベルの内容は、「NG!」
			返す
		もし終わり
		もし末尾文字が(単語の先頭から1文字取り出したもの)なら
			現在単語は、単語
			現在単語ラベルの内容は、現在単語
			メッセージラベルの内容は、「OK」
			単語テキストの内容は、「」
		そうでなければ
			メッセージラベルの内容は、「[末尾文字] ではじまる言葉を言ってください」
		もし終わり
	終わり
終わり

キュー

「キュー」は、最初に入れた値から先に取り出すことができるデータ構造です。ラーメン屋やスーパーのレジの待ち行列のように、キューを取り出すときに最初にキューに入った値から出るような列のように値を記憶するトンネルのようなイメージの入れ物です。キューの最初や途中の値を先に取り出すことはできません。

  • 入れる・・・キューの末尾に値を入れる
  • 取り出す・・・キューの先頭にある値を取り出す(その値をキューから消す)

プロデルマニュアル – 「キュー」

キューを使った簡単なプログラムでキューの特徴を説明します。次のプログラムでは、「トンネル」というキューに「ねずみ」「うし」「とら」の順にキューへ入れていきます。その後トンネルの先頭を2回取り出します。そして「うさぎ」を入れます。

トンネルというキューを作る
トンネルに「ねずみ」を入れる
トンネルに「うし」を入れる
トンネルに「とら」を入れる
トンネルの全要素を表示する

「先頭は、[トンネルの先頭]です。」を表示する
「[トンネルから取り出したもの]を取り出しました」を表示する
「先頭は、[トンネルの先頭]です。」を表示する
「[トンネルから取り出したもの]を取り出しました」を表示する

トンネルに「うさぎ」を入れる
トンネルの全要素を表示する

キューの状態を順番にイメージにすると次のような図になります。

「とら」「うし」を入れると、キューの中にある「ねずみ」が先頭のまま、「とら」「うし」「ねずみ」の順にキューの中で値が並びます。

そして「取り出す」を2回を呼び出すと、まず「ねずみ」が取り出され、その次に「うし」と取り出されます。「とら」がキューの先頭になります。

プログラムを最後まで実行すると、キューの中は「うさぎ」「とら」の順に並びます。このように、常にキューの先頭にはキューの中で一番先に入った値が置かれていて、取り出す時には必ず先頭の値から出ていきます。

さて、この後にキューから「取り出す」と何が出てくるでしょうか?
どうなるか考えた後に、実際にプログラムを書き足して確かめてみましょう。

キューは、例えばプリンタの印刷処理の整理に使われています。プリンタでの印刷には時間がかかるため、アプリから次々の印刷命令が出されたときに、印刷内容を一度キューに格納しておきます。印刷中の印刷が終わり次第、キューから次の印刷内容を取り出してその印刷をはじめ、処理を進めていきます。

ファイル整理ツールを作る

キューを使って、大量のファイルのコピーを順番にこなすツールを作ってみます。このツールでは、まずコピー先のフォルダをエクスプローラからドラッグ&ドロップして、さらに、そのフォルダへコピーするファイルをドラッグ&ドロップでキューに登録することで、キューに入ったファイルを順番にコピーします。

画面設計

プロデルデザイナのウィンドウ設計で次のような部品を貼り付けます。

  • コピー先テキスト・・・コピー先のフォルダを指定します。ドラッグ&ドロップできるようにします。
  • 処理待ちリストビュー・・・処理待ちのコピーするファイルの一覧です。表示方法を「詳細」に変えて、見出しも設定します。またドラッグ&ドロップできるようにします。
  • 状態ラベル・・・コピー中のファイル名を表示します。ステータスバーの中にラベルを作ります。

ロジックを考える

ロジックとはコンピュータをどのように動かすのかを考えた指示の段取りのことです。またロジックや仕様をプログラムに書き起こすことを実装すると言います。プログラムを書く前にロジックを組み立てて仕様を決めてから実装するとプログラムが作りやすくなります。

ファイル整理ツールでは、「仕事キュー」というキューを作ります。このキューには、どのファイルをどこへコピーするのかの対象ファイルとコピー先フォルダを仕事として入れておきます。

キューに入れた仕事は、「仕事を開始する」手順でキューが空になるまで実行します。この手順では、仕事キューに仕事(移動先と対象ファイル名の配列)が入っている場合は、その内容に従ってファイルをコピーします。ファイルを別のフォルダへコピーするには、「コピーする」手順を使います。

プログラム例

このようなロジックを実装すると次のようなプログラムになります。実行画面にて、まずエクスプローラから移動先のフォルダをドラッグ&ドロップして指定して、次にそのフォルダへコピーさせたいファイルをドラッグ&ドロップします。そうすると、すぐにファイルのコピーが始まります。

なお、ファイルコピー中は、画面がフリーズしてしまいます。フリーズしないように仕事をするための「仕事スレッド」というスレッドを用意します。スレッドについての説明は割愛しますが、スレッドは、ボタンなどのGUI部品と同時平行してプログラムを実行するための機能です。

// ファイルコピーツール
メイン画面を表示する
待機する
メイン画面とは
	ウィンドウを継承する
	
	はじめの手順
		初期化する
		ーー貼り付けた部品に対する操作をここに書きます
		仕事キューというキューを作る
	終わり
	初期化する手順
	ーー自動生成された手順です。ここにプログラムを書き加えても消える場合があります
		この実質大きさを{689,370}に変える
		この内容を「ファイルコピーツール」に変える
		初期化開始する
		処理待ちリストビューというリストビューを作る
			その位置と大きさを{12,83,665,245}に変える
			その表示方法を「詳細」に変える
			その見出し一覧を{「対象ファイル」,「コピー先」}に変える
			その見出し幅を{335,289}に変える
			そのドラッグドロップを○に変える
			その位置固定方向を「上+下+左+右」に変える
		ステータスバー1というステータスバーを作る
			その位置と大きさを{0,348,689,22}に変える
			その内容を「ステータスバー1」に変える
			その移動順を1に変える
			状態ラベルという状況ラベル部品をステータスバー1へ作る
				その文字配置を「左」に変える
				その引き伸ばしを○に変える
				その表示を○に変える
				その大きさを{674,17}に変える
				その相対位置を「上+下+左+右」に変える
		ラベル1というラベルを作る
			その位置と大きさを{12,9,118,18}に変える
			その内容を「コピー先フォルダ」に変える
			その自動調整を○に変える
			その移動順を2に変える
		コピー先テキストというテキストを作る
			その位置と大きさを{12,41,665,25}に変える
			その移動順を3に変える
			そのドラッグドロップを○に変える
			その位置固定方向を「上+左+右」に変える
		初期化終了する
		この設計スケール比率を{144,144}に変える
終わり
	コピー先テキストがドラッグドロップされた時の手順
		一覧は、この時のファイル一覧
		コピー先テキストの内容は、一覧(1)
	終わり

	処理待ちリストビューがドラッグドロップされた時の手順
		もしコピー先テキストの内容が空なら
			「コピー先のフォルダを指定してください。」と警告する
			返す
		もし終わり
		一覧は、この時のファイル一覧
		一覧のすべてのファイル名についてそれぞれ繰り返す
			仕事キューに{ファイル名,コピー先テキストの内容}を入れる
		繰り返し終わり
		仕事リストを更新する
		仕事を開始する
	終わり

	仕事リストを更新する手順
		処理待ちリストビューをクリアする
		仕事キューの全要素のすべての仕事についてそれぞれ繰り返す
			処理待ちリストビューに{仕事(1)のファイル名だけ,仕事(2)}を追加する
		繰り返し終わり
	終わり

	-仕事スレッド
	仕事を開始する手順
		//すでに仕事スレッドが実行されていれば何もしない
		もし仕事スレッドが無でないなら返す
		//コピー中にGUI操作ができるようにスレッドを使う
		仕事スレッドというスレッドを作る
		仕事スレッドで『
			仕事キューの要素数が1以上の間繰り返す
				仕事は、仕事キューの先頭
				対象ファイルは、仕事(1)
				コピー先フォルダは、仕事(2)
				状態ラベルの内容は、「[対象ファイルのファイル名だけ]を[コピー先フォルダ]へコピー中...」
				対象ファイルをコピー先フォルダへコピーする
				//コピーが終わったらキューから取り出す
				仕事キューから取り出す
				仕事リストを更新する
			繰り返し終わり
			状態ラベルの内容は、「完了!」
			仕事スレッドは、無
		』を実行する
	終わり
終わり

スタック

「スタック」は、平積みした本のように値を記憶するデータ構造です。値を上に積み重ねて保管しておき、取り出すときは常に一番上に置いてある値から取り出します。スタックでは一番上以外の積み重ねられた値を先に取り出すことはできません。

  • 積む・・・スタックに値を入れる
  • 取り出す・・・スタックから最後に入れた値を取り出す(その値をスタックから消す)

プロデルマニュアル – スタック

スタックを使った簡単なプログラムで説明します。

次のプログラムでは、「箱」というスタックに「りんご」「みかん」「ぶどう」の順に値を積み上げていきます。そして、2回箱の一番上の値を取り出して、箱の一番上に「バナナ」を積み上げます。

箱というスタックを作る
箱に「りんご」を積む
箱に「みかん」を積む
箱に「ぶどう」を積む
箱から取り出して表示する
箱から取り出して表示する
箱に「バナナ」を積む
箱の全要素を表示する

スタックの中身をイメージにしたのが次の図です。スタックは、常にスタックの一番上に値を積まれて、一番上の値から取り出されます。まず「箱」には下から「りんご」「ぶどう」「みかん」の順に詰まれます。その後、2回取り出し、上部にある「みかん」,「ぶどう」の順に値が取り出されます。

そして、次に「バナナ」が積まれ、最後のスタックの中身は、下から「りんご」「バナナ」の順となります。

さて、この状態で箱から「取り出す」と何の値が取り出されるでしょうか?
どうなるか考えた後に、実際にプログラムを書き足して確かめてみましょう。

図形の置いた位置を覚えておく

スタックを使って応用例として、図形を置いた位置を記憶して「元に戻す」「やり直し」ができるキャンバスを作ってみます。キャンバスの話で紹介した図形を移動するプログラムを改良して、図形を移動した時に、その座標をスタックに記憶しておき、「元に戻す」「やり直し」ができるようにしてみましょう。

プロデルデザイナのウィンドウ設計で次のような配置で部品を作っておきます。

ロジックを考える

「元に戻す」と「やり直し」を実現するには、スタックを2つ用意します。

1つ目のスタック(履歴スタック)には、元に戻す時に使う図形の位置を記憶しておきます。図形を移動する直前に、移動する図形オブジェクトとその位置を入れます。扱いやすいようにスタックには、図形と座標とを1つの配列にまとめて入れておきます。

2つ目のスタック(やり直しスタック)は、元に戻す操作をした時に、やり直しができるように戻す前の位置を記憶しておきます。なお元に戻した後に図形を移動した際には、やり直しスタックをクリアします。

スタックは、最後に入れた座標から取り出せるので、「取り出す」手順を使うと常に直前の位置を調べることができます。

[戻す]ボタンをクリックした時には、その時の図形の座標をやり直しスタックに入れた後に、履歴スタックから1つ前の位置を取り出して、図形の位置をその位置に設定します。

逆に、[進む]ボタンを押した時には履歴スタックへ位置を入れて、やり直しスタックから位置を取り出します。

プログラム例

このようなロジックを実装すると次のようなプログラムになります。

キャンバス回のプログラムを改良しているためプログラムが長いですが、スタックを操作しているのは、次の手順です。

  • キャンバス1がマウスのボタンが押された時の手順
  • 戻るボタンがクリックされた時の手順
  • 進むボタンがクリックされた時の手順
// 図形の位置の元に戻す・やり直し //
メイン画面を表示する
待機する

メイン画面とは
	ウィンドウを継承する

	-移動中
	-開始横座標
	-開始縦座標
	-処理中
	-選択図形

	-履歴スタック
	-やり直しスタック

	はじめ手順
		初期化する
		選択図形は、無
		処理中は、×
		キャンバス1へ四角形を描く
			その位置と大きさは、{10,10,80,50}
			その背景色を白に変える
		キャンバス1を更新する
		履歴スタックというスタックを作る
		やり直しスタックというスタックを作る
	終わり

	初期化する手順
	ーー自動生成された手順です。ここにプログラムを書き加えても消える場合があります
		この実質大きさを{450,450}に変える
		この初期位置を「手動」に変える
		この内容を「図形移動を元に戻す」に変える
		この間隔を{4}に変える
		初期化開始する
		キャンバス1というキャンバスを作る
			その位置と大きさを{0,57,450,393}に変える
			その移動順を3に変える
			そのドッキング方向を「全体」に変える
			その間隔を{6}に変える
		パネル1というパネルを作る
			その位置と大きさを{0,0,450,57}に変える
			その移動順を2に変える
			そのドッキング方向を「上」に変える
			進むボタンというボタンをパネル1へ作る
				その位置と大きさを{130,11,112,34}に変える
				その内容を「進む」に変える
				その移動順を2に変える
			"戻るボタン"というボタンをパネル1へ作る
				その位置と大きさを{12,11,112,34}に変える
				その内容を「戻る」に変える
				その移動順を1に変える
		初期化終了する
		この設計スケール比率を{144,144}に変える
終わり

	キャンバス1がマウスのボタンが押された時の手順
		選択図形は、キャンバス1から{イベントの横座標,イベントの縦座標}を選択したもの
		やり直しスタックをクリアする
		履歴スタックに{選択図形,選択図形の位置}を積む
		//履歴スタックの全要素を報告する
		移動中は、○
		開始横座標は、選択図形の横-イベントの横座標
		開始縦座標は、選択図形の縦-イベントの縦座標
	終わり
	キャンバス1のマウスカーソルが移動した時の手順
		もし移動中でないなら、抜け出す
		もし処理中なら、抜け出す
		処理中は、○
		選択図形の位置は、{イベントの横座標+開始横座標,イベントの縦座標+開始縦座標}
		キャンバス1を更新する
		処理中は、×
	終わり
	キャンバス1がマウスのボタンが離された時の手順
		移動中は、×
	終わり

	戻るボタンがクリックされた時の手順
		もし履歴スタックの要素数が0なら
			「これ以上戻れません。」と警告する
			返す
		もし終わり
		履歴情報は、履歴スタックから取り出したもの
		選択図形は、履歴情報(1)
		元位置は、選択図形の位置
		選択図形の位置は、履歴情報(2)
		やり直しスタックへ{選択図形,元位置}を積む
		キャンバス1を更新する
	終わり
	進むボタンがクリックされた時の手順
		もしやり直しスタックの要素数が0なら
			「これ以上進めません。」と警告する
			返す
		もし終わり
		履歴情報は、やり直しスタックから取り出したもの
		選択図形は、履歴情報(1)
		元位置は、選択図形の位置
		選択図形の位置は、履歴情報(2)
		履歴スタックへ{選択図形,元位置}を積む
		キャンバス1を更新する
	終わり
終わり

自分でデータ構造を作ってみよう

最後は、自分でキューやスタックのようなデータ構造を定義して作ってみましょう。データ構造は「種類」を定義することで作れます。

ここでは「リンクリスト」という配列のようなデータ構造を作ってみます。リンクリストとは「リンク項目」というオブジェクトを数珠つなぎにした配列のようなデータ構造です。リンク項目には、「値」と次のリンク項目である「次」との2つの変数を持っています。

例えば、次のようなA,B,Cと繋がったリンクリストがあるとします。このリンクリストから「C」という値があるかどうかを調べるには、まず先頭のリンク項目(A)の値を確認します。値が違えば「次」に入っているリンク項目をたどり、その値を確認します。違えば同じ事をさらに続けていきます。「値」が「C」のリンク項目が見つかるまで、または「次」が無になるまで、この操作を続けていきます。

このリンクリストの利点は、配列のように添字が無いので、先頭さえ覚えておけば、カウント変数を宣言したりカウントを増やさなくても、リストの項目を順番に処理できます。

また、リンク項目とリンク項目の間に新しいリンク項目を挟み込む時は「次」が差すオブジェクトを変えるだけで実現できます(配列場合には差し込む操作に手間がかかります)。次の図のようなイメージです。

欠点としては、常に先頭から次の項目を辿るので、途中のリンク項目から調べることができないことです。また、「前」がないので逆に辿ることもできません。

ただ「リンク項目」は、自分で定義した種類ですので改良が自由です。例えば「前」という変数を用意することもできます。また最後のリンク項目を「末尾」変数に入れておけば、末尾から調べることもできます。

プロデルで予め用意された「スタック」種類や「キュー」種類は改良できませんが、必要に応じて自分で種類を定義することで、さらにプロデルで色々なデータ構造を取り扱うことができます。

リンク項目を実装したプログラムは、次の通りです。上の図と見比べてプログラムを読むと、リンク項目の操作が分かるはずです。

// リンクリスト(LinkedList)の実装例 //
先頭というリンク項目を作る

ーー追加する
新項目1というリンク項目を作る
新項目1の値を「A」とする
先頭へ新項目1を挟む

新項目2というリンク項目を作る
新項目2の値を「B」とする
先頭へ新項目2を挟む

ーー取得する
先頭から「A」を探して結果とする
もし結果が無なら
	「見つかりません」を警告アイコンで表示する
他なら
	結果の値を表示する
もし終わり

リンク項目とは
	+次
	+値

	自分から[値]を、探す手順
		対象を自分とする
		繰り返す
			もし対象の値が値なら、繰り返しから抜ける
			対象を対象の次とする
			もし対象が無なら、繰り返しから抜け出す
		繰り返し終わり
		対象を返す
	終わり

	自分へ[項目]を、挟む手順
		項目の次を自分の次とする
		自分の次を項目とする
	終わり

	自分を、消す手順
		項目を次とする
		自分の次を項目の次とする
		項目の次を無とする
	終わり
終わり

まとめ

今回は、プロデルに用意された多彩なデータ構造を実例とあわせて紹介しました。

特徴や使い方が異なる様々なデータ構造を知って駆使することで、より簡単に素早くアプリを作れるようになります。実用例もたくさん紹介したため長文となりましたが、ぜひ活用してください。

次回もお楽しみに。

※当ブログの記事の著作権はゆうとにあります。プロデルに関係が無い目的で、文章や図表,プログラムを複製したり改変して掲載することを堅く禁止します

  • 続きを読みたい (5)
  • いいね (5)

コメントを残す