数式が読み込まれない場合は1回再読み込みしてみてください。基本情報-テクノロジ系-データ構造とアルゴリズムこんにちは、ももやまです。今回は基本情報にもよく出てくる配列とリストについて説明していきたいと思います。練習1練習2練習3練習4練習56.練習問題の答え解答1解答2解答3解答4解答57.さいごに1.配列とは配列は、下のように同じデータ型の要素を番号順に並べたものを表します。この番号は添字(インデックス)と呼ばれます。添字は0スタートの場合と1スタートの場合がありますが、C言語を含む多くの言語は0スタートです。配列の場合、指定したい要素を添字で指定します。上の図の配列で2番目を指定すると97の要素を得ることができます。ような数式で指定することもできます。番目を指定すると、8番目を計算してくれます。配列を2重に組み合わせて2次元配列をつくることができます。2次元配列のイメージは、下のような行と列からできた表です。他に2次元配列で表現できるものとして、行列やビンゴカードなどがあります。2.リストとはリストは、「要素」と「次のデータを指し示すポインタ(場所)」の2つからなるデータが数珠のようにつながっているデータ構造です。20番地のアドレスのデータには、要素である「75」と「次のデータのポインタ(40番地)」が入っています。リストの場合、要素を探すために先頭からポインタをたどる必要があります。上の図のリストで97の要素がある60番地のデータを探したい場合、「20番地→40番地→60番地」のように順番にたどることで目的の60番地のデータを見つけることができます。リストには次のデータのポインタだけを持つ単方向リスト以外にも、前のデータのポインタも持つ双方向リスト、末尾と先頭のデータを連結させることで環状線のようにぐるぐるできる環状リストがあります。単方向リスト以外にもこんなリストがあるんだな~ってことがわかればOKです。リストとだけ書いてあった場合は「単方向リスト」を表していると思ってください。配列とリストはともに同じ型のデータですが、どちらも一長一短で使い分けられます。データのアクセスデータのアクセスの場合、配列の方が優れています。配列は、添字(番号、インデックス)で要素を指定できるのでワンステップで要素を指定することができます。リストは先頭からリストをたどっていくことでしか要素を探せないため、最大で要素数ステップの時間がかかってしまいます。データの追加・削除データの追加、削除はリストが優れています。削除するために、後ろにあるデータを下のようにずらす必要があります。そのため、ずらすデータの数だけ余計に処理時間がかかります。配列の削除リストでは、次のデータを指し示すポインタを下のように少し書き換えるだけでデータの追加、削除を行うことができます。そのため、後ろのデータに関係なく数ステップで処理ができます。格納領域も、リストの方が優れています。ように格納領域を指定するため、使わない無駄な領域が発生してしまいます。リストはポインタだけで前後関係を表しているので、動的に拡張領域を変更することができ、無駄な領域が発生しません。頻繁にデータにアクセスするようであれば配列を、頻繁にデータを書き換える場合であれば連結リストのように使い分けると効率がよくなります。念のため、データのアクセス、データの書き換えをオーダー表記で表したものを下に示しておきます。配列リストデータアクセスデータ挿入/削除オーダー表記を用いた計算時間の表現方法については下の記事でわかりやすく説明しているので、下の記事をご覧ください。www.momoyama-usagi.com4.配列とリストの操作実装では、配列、リストの定義、要素の追加、要素の削除をC言語で実装したものを下に記します。配列・リストの中身は上で紹介した図と同じにしています。配列を定義し、要素を追加・削除する過程をプログラムで書くと下のようになります。forループの向きに気を付けましょう。0;}挿入、削除にforループを使うため、後ろにある要素数分だけ余計なステップ数がかかってしまいます。リストリストは、下のような構造体で定義することができます。次のデータがある「場所」が入るので、ポインタ変数*1で宣言します。忘れやすいので気をつけましょう。0;}for文を使わずにポインタだけで挿入、削除ができるので後ろにある要素数に関係なしに数ステップで処理ができます。問題で練習してみましょう。練習1データ構造の一つであるリストは、配列を用いて実現する場合と、ポインタを用いて実現する場合とがある。配列を用いて実現する場合の特徴はどれか。ここで、配列を用いたリストは、配列に要素を連続して格納することによって構成し、ポインタを用いたリストは、要素から次の要素へポインタで連結することによって構成するものとする。午前問4]ア:位置を指定して、任意のデータに直接アクセスすることができる。イ:並んでいるデータの先頭に任意のデータを効率的に挿入することができる。ウ:任意のデータの参照は効率的ではないが、削除や挿入の操作を効率的に行える。エ:任意のデータを別の位置に移動する場合、隣接するデータを移動せずにできる。練習2配列と比較した場合の連結リストの特徴に関する記述として、適切なものはどれか。午前問6]ア:要素を更新する場合、ポインタを順番にたどるだけなので、処理時間は短い。イ:要素を削除する場合、削除した要素から後ろにあるすべての要素を前に移動するので、処理時間は長い。ウ:要素を参照する場合、ランダムにアクセスできるので、処理時間は短い。エ:要素を挿入する場合、数個のポインタを書き換えるだけなので、処理時間は短い。