データ構造～アルゴリズムの基本（2024.05.20）

参考書

【令和６年度】 いちばんやさしい 基本情報技術者　絶対合格の教科書＋出る順問題集

---

データ構造

• データ
  コンピュータが扱う情報のこと

• 主記憶装置
  コンピュータ内にある記憶装置
  データが保存される場所

• データ構造
  主記憶装置上のデータの並べ方のこと
  データの並べ方によって、コンピュータの処理効率は大きく変わる
  処理の内容やそのときの状況に応じて、様々な方式で並べられる。

データ構造の種類

• スタック

• キュー

• 配列

• 連結リスト

• 木構造

スタック

• データを1列に並べて、最後に格納したデータを最初に取り出すデータ構造のこと

• イメージとしては積み上げられた本

• 途中にあるデータを取り出すことはできない

• 行った処理を保存することで、コンピュータはいつでも元の処理に戻ることができる。

• これがスタックというデータ構造の最大の特徴

スタックへのデータの出し入れ

• push
  スタックにデータを格納すること
  例）「C」というデータをスタックに格納する場合　→　pushC

• pop
  スタックからデータを取り出すこと
  データをスタックから取り出す場合は「pop」とだけ記述する。

• スタックのアルゴリズム
  後入れ先出し（LIFO：Last In First Out）
  　後に入れたデータを先に出すアルゴリズムのこと

キュー

• データを1列に並べて、最初に格納したデータを最初に取り出すデータ構造のこと

• イメージとしては「レジの待ちの列」

• 待ち行列とも呼ばれる

• 命令を入力した順番どおりに処理可能

• 列の途中に割り込むことはできない

キューへのデータの出し入れ

• enqueue
  キューにデータを入れること
  例）「D」というデータをキューにに入れる場合　→　enqueue D

• dequeue
  データをキューから取り出すこと
  データをキューから取り出す場合は「dequeue」とだけ記述する。

• キューのアルゴリズム
  先入れ先出し（FIFO：First In First Out）
  キューのような先に入れたデータを先に出すアルゴリズムのこと

配列

• データを表の形に並べたデータ構造

• 1つ1つのデータを要素という

• 要素の位置を表す数字を添字（インデックス（index））という

一次元配列

• 要素が1列に並ぶ配列のこと

• 配列から1つの要素を取り出す場合は、「配列名（添字）」と書く

• 例）配列Aの添字2を取り出す　→　A（2）

• 試験問題によっては、配列名の後ろの括弧が［］のときもあるが、（）と同じ

2次元配列

• 要素が縦横に並ぶ配列のこと

• 行
  要素の横の並びのこと

• 列
  要素の縦の並びのこと

• 2次元配列から1つの要素を取り出す場合「配列名（行,列）」と書く

• 例）2次元配列Aの1行3列のデータを取り出す場合　→　A（1,3）

連結リスト

• データを数珠つなぎに並べたデータ構造

• 個々のデータを要素と呼ぶ（全く同じ意味でセルと表記されることあり）

• 連結リストの要素はデータに「ポインタ」が付く。

• ポインタ
  次の要素のアドレス（主記憶装置上のデータの位置）を指し示すもの

• ポインタを用いて要素を数珠つなぎにする

• コンピュータはポインタに格納されているアドレスをたどることで、目的のデータにアクセスする。

連結リストの分類

• 単方向リスト
  先頭から末尾まで一方向にデータをつなげた連結リスト
  先頭から末尾の方向へしかデータをたどることができない

• 双方向リスト
  双方向にデータをつなげた連結リスト
  先頭から末尾へ、または末尾から先頭へ、データをたどることができる。
  ポインタが2つある

• 線形リスト
  先頭から末尾まで直線状に要素がつながっている連結リスト
  ほとんど単方向リストと同じ

• 環状リスト
  末尾と先頭をつなげて環の形（環状）に要素がつながっている連結リスト

配列と連結リストの違い

• データにアクセスする方法

  • 配列
    添字を使い、データに直接アクセス可能

  • 連結リスト
    先頭から順番に要素をたどって目的のデータにアクセス
    →要素数が多ければ多いほど、データのアクセスに時間がかかる

• データを挿入または削除する際の処理

  • 配列
    後ろの要素をすべて1つずつずらす必要がある
    →要素数が多ければ多いほど処理に時間がかかる

  • 連結リスト
    ポインタを変更するだけ
    →配列よりも、迅速に処理可能

• 試験に出る部分

  • 配列は、参照・更新が速い

  • 連結リストは、挿入・削除が速い

木構造

• 階層構造を持つデータ構造

• 節がデータを保持する

• 木構造の各部の名称

  • 節
    枝分かれする箇所のこと

  • 根
    節の中で最上位の節のこと

  • 葉
    節の中で末端の節のこと

木構造の親子関係

• 分岐元　→　親

• 分岐先　→　子

• 木構造の節同士には、親子関係がある

• 親が0～2個の子を持つ木構造　→　2分木

• 親が0～3個の子を持つ木構造　→　3分木

• 親が0～ｎ個の子を持つ木構造　→　n分木

• 分木とは、節が最大でいくつの子に分かれるかを表している

2分探索木

• 親子の値がすべて　左の子孫　＜　親　＜　右の子孫　となているもの

• メリット

  • データを見つけるのに便利

  • 根から葉までの階層の数だけを調べれば目的のデータを見つけ出せる

アルゴリズムの基本

• アルゴリズムの表現方法は以下の４つ

  • 文章（文字による表現）

  • 流れ図（図による表現）

  • 数式（関数による表現）

  • プログラム言語（コンピュータが理解できる言語による表現）

文章

• 数学記号と文字が読めれば、その他の知識がなくてもアルゴリズムを理解できる

流れ図（フローチャート）

• アルゴリズムを視覚的にわかりやすく表した図のこと

• 流れ図で使用する記号

  • JIS（日本産業規格）によって企画化されている

  • 基本情報で主に出題されるのは５つ

  • 記号の名前が問われることはあまりない。形状と役割を覚える

    • 端子
      流れ図の開始と終了を表す。記号の中に「開始」または「終了」と書く。

    • 処理
      計算や値の代入といった処理を表す。処理の中にある「→」は代入を表す。
      例）AをBに代入する場合「A　→　B」または「B　←　A」

    • 判断
      処理を分岐するための条件を表す
      出口に「Yes」と「No」などの判定結果を書く

    • 線
      処理の順番を表す。処理が下から上へ戻る場合など、処理の流れがわかりづらい箇所では矢印線を使う。

    • ループ端
      ループ（繰り返し処理）の開始と終了を表す。
      ループ端の中には、繰り返し処理の条件を記入する
      「変数名：初期値, 増分, 終値」

• 流れ図の問題を確実に解答する方法

  • トレース表を作成する

  • トレース表
    流れ図で示されている各処理を実行する際の「変数の値」を書きだした表のこと

数式

• 関数

  • 複数の処理をひとまとめにしたもの

  • 引数
    関数に渡す値

  • 戻り値
    関数が返す結果

• 数式と関数

  • fと()を使って表す

プログラム言語

• 基本情報では、C言語やJavaなどの特定のプログラム言語の書式は問われない

• if
  後ろに条件を書く

• then
  後ろに条件が正しいときの処理を書く

• else
  後ろに条件が正しくないときの処理を書く

• return
  後ろに戻り値を書く

進捗

２１　／　９７　（２１％）

1項目遅れを取り戻せていない。
予定がある日だと、なかなか取り戻すのが難しいので、明日予定がないため、取り戻す。