データ構造

◆基本データ構造
　基本データ型

　構造型

　　・配列型

　　・レコード型

　抽象データ型
　　データ構造とデータ操作を一体化したもの。


◆リスト構造

　単方向リスト：次のデータのポインタだけもつ

　双方向リスト：前と次のデータのポインタを持つ

　環状リスト：環状につながっている


◆スタック
　LIFO（ｌａｓｔ-ｉｎ　ｆｉｒｓｔ-ｏｕｔ）型
　再帰呼び出し、サブルーチン呼び出し、データ退避などに使われる

◆キュー
　FIFO（ｆｉｒｓｔ-ｉｎ　ｆｉｒｓｔ-ｏｕｔ）型
　ジョブ待ち、タクス待ち行列に使われる

◆木構造
　データ項目間の関係を木（ツリー）に例えて表現した　

　　　 　　 ○　→節、根
　　　　　／＼　→枝
　　　　○　　○　→節
　　　／＼　 　＼
　　○ 　 ○　　 ○　→節、葉

◆ニ分木
　　子が二つ以下の木構造

◆完全ニ分木
　　木構造で左右の枝の数が同じもの

★★★宿題：二種向け★（2000/2/7）

　FIFO（First-In First-Out）の処理に適したデータ構造はどれか。

　ア　２分木

　イ　キュー

　ウ　スタック

　エ　ヒープ

■解答■
　　二種午前平成１１年秋問１３

> 前にキューの問題がこの宿題メールででたとき、どなたか
> 「キューはところてんをきゅーっと押して、先から出るイメージ」
> とおっしゃっていたのを覚えています。

　どうもありがとうございました。

>メッセージキューイング：
>処理のメッセージ(電文)を到着順に蓄積し、処理する

　どうもありがとうございました。

> 先入れ先出し=>順番に処理。
> プリンタの印刷処理=プリントキュ−

　どうもありがとうございました。

>FIFO：先入れ先出し。
>      サービスや処理を受けるために、待ち行列（queue）があるとき、最初に
>      入ってきたものから処理する方法。
>FILO：先入れ後出し。
>      後入れ先出し。
>      サービスや処理を受けるためにスタックがあるとき、最も後から入った
>      ものからサービスや処理をする方法。
>
>ア ２分木：木構造のひとつ。
>           根（ルート）と呼ばれる根幹となる端点から二つ以下の枝が出る
>           もの。
>           各端点は節と呼ばれ、枝が０の端点は葉と呼ばれる。
>イ キュー：フィルム・磁気テープなどのある部分にいれておく信号。
>ウ スタック：後入れ先出し（LIFO）のデータ構造。
>エ ヒープ：ツリー構造を持ったデータ構造の一種。
>           ヒープを利用した並べ替えのアルゴリズムは「ヒープ・ソート」と
>           呼ばれる。
>
>参考：「合格情報処理２月号付録 情報システム辞典」
>      「五反田コレクション（ http://www.imagica.com/dic/ ）」
>      「MioCity コンピュータ用語小辞典
>       （ http://www.big.or.jp/%7Emio/ga/index.html ）」

　どうもありがとうございました。

★★★宿題：二種向け★(2000/5/19)

　2 分木を入力するためのテキスト表現を，次のように規定した。図のように節
に番号をつけたとき，テキスト表現として正しいものはどれか。

(テキスト表現)
　(1) (左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテ
　　　キスト表現)と表す。
　(2) 部分木が空のときは x を書く。

　　　　　　　 3
　　　　　　　●
　　　　　　／　＼
　　　　　／　　　＼
　　　 2●　　　　　●5
　　　／　　　　　／　＼
　　／　　　　　／　　　＼
 1●　　　　 4●　　　　　●6

　ア　((1，2)，3，(4，5，6))

　イ　((1，2，3)，x，(4，5，6))

　ウ　((1，2，x)，3，(4，5，6))

　エ　((1，2，x)，3，(6，5，4)

(解答例）

問題を素直に読めば解けます。

(左部分木の節番号又はテキスト表現，節番号，右部分木の節番号又はテ
　　　キスト表現)と表す。だから、まず、左の部分を見ます。
　　（1，2，ｘ)
　　　　　　↑
部分木が空のときは x を書く

次ぎに、右の部分
　　（4，5，6)

そして、全体を見る。

(1，2，ｘ)，3，（4，5，6)

■解答■（宿題メールより）
　　二種午前平成１２年春問１４

>　　　 3
>　　　●
>　　／　＼
>　／　　　＼
>2●　　　　●5
>まず、この部分だけを取り出して考えます。
>このテキスト表現は（２，３，５）です。
>
>◎（２，３，５）
>　　￣
>　　 2●
>　　／
>  ／
>1●
>この部分は左部分木に１番の節があって右部分木が空の状態です。
>よってテキスト表現は（１，２、ｘ）となります。
>
>◎（２，３，５）
>　　　　　　￣
>　　　●5
>　　／　＼
>　／　　　＼
>4●　　　　●6
>この部分は左部分木に４番の節があって右部分木に６番の節があります。
>よってテキスト表現は（４，５，６）となります。
>
>まとめると
>（（１，２，ｘ），３，（４，５，６））
>となります。

　どうもありがとうございました。

★★★宿題：二種(基本情報技術者)向け★（2000/9/7）

　次の式を逆ポーランド表記法で表現したものはどれか。

(A ＋ B)×(C ＋ D)
────────
　　　A − D

　ア　AB ＋ CD ＋× AD −÷

　イ　AB ＋ CD ＋ AD −×÷

　ウ　ABCD ＋＋× AD −÷

　エ　ABCD ＋＋÷ AD −×

上の式を逆ポーランド表記法に直しやすく括弧でくくります。

((A＋B)×(C＋D))÷(A−D)
=((AB＋)×(CD＋))÷(AD−)
=(AB＋CD＋×)÷(AD−)
=AB＋CD＋×AD−÷

という形になるかな？
中の括弧から処理していくことが鉄則ですね。

次ぎに元に戻して見ましょう。

AB＋CD＋×AD−÷
＝（（A＋B）（C＋D）×）（（A−D）÷）
＝（（A＋B）×（C＋D））（（A−D）÷）
＝（（A＋B）×（C＋D））（÷（A−D））
＝（（A＋B）×（C＋D））÷（A−D）

となります。

■解答■（宿題メールより）
　　ネットワークスペシャリスト午前平成１１年問４２

>  （逆）ポーランド表記法って，このような情報処理の試験ではよく見ますが，
> 実際に役立つとは思えぬのだが．そんなこと聞くのは，禁句？

　どんどん質問して下さい。禁句ではないですよ。
　これは，基本的な処理ですからね。勉強しておきましょう。

>こういう表記方で、どういったメリットがあるのですか？

　コンピュータが内部で使ってます。HPなどの関数電卓で，人間が手で入れて
計算することもありますよ。

>逆ポーランド表記法( reverse Polish notation )：
>　FortranやCOBOLなどのソースプログラムをコンパイルする際に行う算術式
>を機械語に変換する過程では，加減算より乗除算を優先するなどの演算子の
>優先順位を考慮して，構文を明らかにする。スタックを利用した簡明な算術
>式の内部表現法を逆ポーランド表記法という。この表記法では，加減乗除な
>どの演算子をオペランドの後に置く。例えば，
> (1)AとBを加え，その和にCを乗じることを，AB + C * と書く。
> (2)括弧のある場合には，次のように書く。
>　　　　X = ( A + B ) * ( C - D ) は XAB + CD -* =
>　この表記法は，ポーランドの論理学者 J.Lukasiewicz が使用したもので，
>括弧なしで数式を表現できる。そのため，算術式の評価が単純に行える。後
>置表記法ともいう。
>
>学研「合格情報処理」付録　「情報システム辞典」(p50)より　一部抜粋

　どうもありがとうございました。

>逆ポーランド表記法（後置表記法）〜
>普通の式では、演算子は被演算子と被演算子の間に書くが、逆ポーランド表記法
>では、演算子を最後に書くことにより、括弧が不要になり、コンパイラ等で演算
>処理する場合にスタックを使って簡単に計算が可能になる。
>http://www002.tokai.or.jp/k-sakamoto/kiso.htm

　どうもありがとうございました。カッコが要らなくなるのは，画期的なテクニック
であると感動しました。（20年ほど前）（＾＾）；

> http://www.abplus.com/palmware/ksan_rpn.html

　どうもありがとうございました。