データ構造~アルゴリズムの基本(2024.05.20)
参考書
データ構造
データ
コンピュータが扱う情報のこと主記憶装置
コンピュータ内にある記憶装置
データが保存される場所データ構造
主記憶装置上のデータの並べ方のこと
データの並べ方によって、コンピュータの処理効率は大きく変わる
処理の内容やそのときの状況に応じて、様々な方式で並べられる。
データ構造の種類
スタック
キュー
配列
連結リスト
木構造
スタック
データを1列に並べて、最後に格納したデータを最初に取り出すデータ構造のこと
イメージとしては積み上げられた本
途中にあるデータを取り出すことはできない
行った処理を保存することで、コンピュータはいつでも元の処理に戻ることができる。
これがスタックというデータ構造の最大の特徴
スタックへのデータの出し入れ
push
スタックにデータを格納すること
例)「C」というデータをスタックに格納する場合 → pushCpop
スタックからデータを取り出すこと
データをスタックから取り出す場合は「pop」とだけ記述する。スタックのアルゴリズム
後入れ先出し(LIFO:Last In First Out)
後に入れたデータを先に出すアルゴリズムのこと
キュー
データを1列に並べて、最初に格納したデータを最初に取り出すデータ構造のこと
イメージとしては「レジの待ちの列」
待ち行列とも呼ばれる
命令を入力した順番どおりに処理可能
列の途中に割り込むことはできない
キューへのデータの出し入れ
enqueue
キューにデータを入れること
例)「D」というデータをキューにに入れる場合 → enqueue Ddequeue
データをキューから取り出すこと
データをキューから取り出す場合は「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個の子を持つ木構造 → n分木
分木とは、節が最大でいくつの子に分かれるかを表している
2分探索木
親子の値がすべて 左の子孫 < 親 < 右の子孫 となているもの
メリット
データを見つけるのに便利
根から葉までの階層の数だけを調べれば目的のデータを見つけ出せる
アルゴリズムの基本
アルゴリズムの表現方法は以下の4つ
文章(文字による表現)
流れ図(図による表現)
数式(関数による表現)
プログラム言語(コンピュータが理解できる言語による表現)
文章
数学記号と文字が読めれば、その他の知識がなくてもアルゴリズムを理解できる
流れ図(フローチャート)
アルゴリズムを視覚的にわかりやすく表した図のこと
流れ図で使用する記号
JIS(日本産業規格)によって企画化されている
基本情報で主に出題されるのは5つ
記号の名前が問われることはあまりない。形状と役割を覚える
端子
流れ図の開始と終了を表す。記号の中に「開始」または「終了」と書く。処理
計算や値の代入といった処理を表す。処理の中にある「→」は代入を表す。
例)AをBに代入する場合「A → B」または「B ← A」判断
処理を分岐するための条件を表す
出口に「Yes」と「No」などの判定結果を書く線
処理の順番を表す。処理が下から上へ戻る場合など、処理の流れがわかりづらい箇所では矢印線を使う。ループ端
ループ(繰り返し処理)の開始と終了を表す。
ループ端の中には、繰り返し処理の条件を記入する
「変数名:初期値, 増分, 終値」
流れ図の問題を確実に解答する方法
トレース表を作成する
トレース表
流れ図で示されている各処理を実行する際の「変数の値」を書きだした表のこと
数式
関数
複数の処理をひとまとめにしたもの
引数
関数に渡す値戻り値
関数が返す結果
数式と関数
fと()を使って表す
プログラム言語
基本情報では、C言語やJavaなどの特定のプログラム言語の書式は問われない
if
後ろに条件を書くthen
後ろに条件が正しいときの処理を書くelse
後ろに条件が正しくないときの処理を書くreturn
後ろに戻り値を書く
進捗
21 / 97 (21%)
1項目遅れを取り戻せていない。
予定がある日だと、なかなか取り戻すのが難しいので、明日予定がないため、取り戻す。
この記事が気に入ったらサポートをしてみませんか?