独学で資格は取れる

資格を独学で勉強してみた記録です。

【応用情報・高度共通】1章 基礎理論 1.3データ構造

å¿ç¨æå ±ã»é«åº¦å±éä¸é¨ç»å

目次

この文章は以下の本を参考にしています。


 

 

データ構造は、プログラムがデータをどう扱っていくかを決める構造のことです。

この構造によって処理速度や負荷が大きく変わってくるため、非常に重要です。

 

ここでは試験でよく出題されるリスト、スタック、キュー、木を紹介していきます。

 

リスト(list)

  • リンクをつけて、それを辿ってデータを取り出しにいくデータ構造
  • 辿っていくので最初に箱を用意する必要がないのがメリット
  • ただし、取り出す時に、リンクを順番に辿っていかないといけないので効率が悪い
  • 前後にポインタがあるのを「双方向リスト」
  • 最後のポインタが最初のポインタにリンクしているのを「環状リスト」

 

スタック(stack)

  • データ構造はLIFO(Last-In First-Out;後入れ先出し法)
  • データの箱に入れる時は、プッシュ(PUSH)
  • データの箱から出す時は、ポップ(POP)
  • 実際の箱に入れていくのと同じように箱に積み重ねていくので、出す時は最後に入れたものから取り出す事になる
  • 後に入れたものが最初に取りだされるので「後入れ先出し法」

 

キュー(queue)

  • データ構造はFIFO(First-In First-Out;先入れ先出し法)
  • データの箱に入れる時は、エンキュー(enqueue)
  • データの箱から出す時は、デキュー(dequeue)
  • OSの待ち行列の管理などに用いられる
  • 箱に入口とは別に取りだし口があるイメージ
  • 先に入れたものから先に取りだすので「先入れ先出し法」

 

木(tree)

  • 上述のリストは、順番にデータがつながっていきましたが、木構造では、途中で分岐したりします
  • 2分木、ヒープ、B木などがあります
  • 木はデータを持つ「ノード」で構成されている
  • 一番最初のノードを「ルート」と呼ぶ
  • 元なるノードを「親」、下にくるノードを「子」と呼ぶ
  • 親は1つしかないが、子は複数あることがある

 

①2分木

データの探索法

  • 幅優先順…同じ深さを左から右へ探す方法
  • 深さ優先順
    (1)先行順→親、左側、右の順に探す方法
    (2)中間順→左、親、右の順に探す方法
    (3)後行順→左、右、親の順に探す方法

 

②ヒープ(heap)

  • どの親子を見ても、必ず値が「親<子(又は子<親)」となっているデータ構造
  • つまり、一番小さい(又は大きい)値はルートということになる
  • 親子の関係が必ず大(又は小)の関係を満たす

 

③B木(B-tree)

  • 要素の追加や削除のたびに木構造のバランスを調整
  • 全ての葉までの深さが一定
  • データベースのインデックスなどで利用されている

 

 

参考文献: iTEC社 「2019応用情報・高度共通 午前試験対策書」

 

ブログランキングに参加しております。
よろしければポチっとお願いします!

にほんブログ村 資格ブログへにほんブログ村

資格受験ランキング

プライバシーポリシー