関数とデータ構造

関数

関数はプログラム実行中に次々と呼び出され、処理が終わると呼び出し側に戻って来る。
このとき、スタックを使って戻り先のアドレス情報を記憶させておく。実際のプログラムでは、呼び出した関数で別の関数を呼ぶこともある。こうした場合、まず一番最初に記憶したアドレス情報を取り出してそのアドレスへ戻り、次に最後から2番目に記憶したアドレス情報を取り出してそのアドレスに戻る必要がある。
このようなデータの取り出し方はスタックが適している。

データ構造

nibungi2分木：節から分岐する枝が2本以下の木構造のこと

完全2分木：根からすべての歯までの深さが等しい2分木

ヒープ：すべての節で親と子の間に一定の大小関係が成立する完全2分木、親≧子または親≦子

2分探索木：節のデータを昇順または降順に並べておくことで、効率的に探索できる2分木のこと。省昇順に並んだものを保管するのに適したデータ構造である。

連結リスト：散在する複数のデータを数珠つなぎにするデータ構造。データを呼び出すときは、次に呼び出すデータのⅰが格納されているポインタを指定する。
線形リスト、双方向連結リスト、環状リスト

r_list
双方向連結リスト：次に呼び出すデータだけでなく、前のデータも呼び出すことができるリスト。次ポインタと前ポインタを持っている。路線の駅名のように順番があり、挿入、削除ができ、前後を調べる必要があるときに適したデータ構造である。
sr_list
kyuキュー：リストの最後にデータを挿入し、最初に挿入したデータを削除（取り出し）する方法のこと。
キーボードからの入力の保存など、入力処理をするのに適したデータ構造である。

stackスタック：LIFO（Last in First out）、リストの最後にデータを挿入し、最後に挿入したデータを削除（取り出し）する方法のこと。最後に入れたものを最初に処理するのに適したデータ構造である。
スタックは、後入先出のデータ構造で、再帰呼び出しなどの関数呼び出しにおいて、戻り番地や処理途中のレジスタの値を退避しておくのに利用される。