配列と連結リスト

配列


array

・要素を削除する場合:削除した要素から後ろにあるすべての要素を前に移動する必要がある。
・要素を挿入する場合:要素から後ろにあるすべての要素を後ろに移動する必要がある。
・要素を参照する場合:ランダムにアクセスできる。

連結リスト


r_list

・要素を削除する場合:削除した要素に関係したポインタの更新だけで済む。
・要素を挿入する場合:数個のポインタを置き換えるだけである。
・要素を参照する場合:ポインタを順番にたどる必要がある。
 


関数とデータ構造

関数


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

データ構造


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

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

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

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




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

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








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

文字列の圧縮方法

ランレングス符号化


同一符号が連続する部分を、符号と連続する符号の個数に置き換えて符号化する可逆圧縮方式。
RLE(Run Length Encoding、連長圧縮)、数値データや画像データなどで、同一ビットが連続しているデータを圧縮するのに適している。
RLE:ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮する方式。

EBCDIC符号


Extended Binary Coded Decimal Interchange Code(拡張2進化10進数変換符号)の略で、IBM社の汎用コンピュータで使用されていた文字コード。

巡回符号


データを多項式で表し、先生多項式を用いて符号化を行う方式。
Cyclic Redundancy Code、誤り検出符号の一つである。通信エラーチェックCRC(Cyclic Redundancy Check)で使われている。

ハフマン符号


各文字の生起確率をもとにハフマン木と呼ばれる木構造グラフを作成し、ハフマン木をもとに生起確率の高い文字に短い符号を、生起確率の低い文字に長い符号を割り当てることにより生成される符号。
符号の頻度が多いものほど少ないビットで表す圧縮方式(ハフマン法)で使われる符号である。 
月別アーカイブ
アクセスカウンター
  • 今日:
  • 昨日:
  • 累計:

PVグラフ

    UUグラフ

      QRコード
      QRコード