総合情報論 (環境情報学科1年次後期配当 金曜日３限) 大城クラス
■６．10/29 （シラバス：７．データ構造1：配列とリスト）
【目的】ここから一旦，データ構造とアルゴリズムの話しに入る。処理の
３要素（順次，条件分岐，繰り返し）の話しと，流れ図の書き方，および，
基礎的なデータ構造として配列とリストを学習。
配 列→同じ大きさの要素が隙間なくメモリ上に詰められているので，各要素
のメモリアドレスは瞬時に計算できる(ランダムアクセス)。ランダム
アクセスによりアクセスは高速だが，要素が隙間無くつめられている
がゆえに，要素の挿入や削除は要素のずらしコピーが発生して効率が
悪くなる。また，格納できる要素数が固定されている。そのため，ず
らしコピーの起こらない「要素の交換」が基本操作となる。
リスト→メモリ上に散在している各要素がポインタによって数珠繋ぎになって
いる。そのため，ランダムアクセスができず，目的の要素にアクセス
するために要素をたぐっていかなければならない(順次アクセス)。
そのかわり，要素の挿入や削除は効率よく行うことが出来る。また，
格納できる要素数は可変であり，メモリに十分な空き領域がある限り，
要素数を増やすことが出来る。
あたりがポイント。
【他科目との関連】同時に行われている１年必修科目「情報処理概論演習」でC言
語に慣れはじめてる頃。データ構造とアルゴリズムについては，２年生前期の選択
必修科目「ソフトウェア基礎a」のC言語によるプログラミング学習で，簡単なソー
トアルゴリズムなどを実際に学習する。なお，３年生後期に選択科目「アルゴリズ
ム論」でより詳しく学習する。
★以降，第10回までは，「手順を考える」という思考訓練を兼ねて，教養として，
データ構造とアルゴリズム論の基礎を学習。思考訓練の目的がある。
●テキスト１での対応部分
1-7 アルゴリズムとデータ構造
1-7-1 アルゴリズムとは
1-7-2 流れ図
1-8 基本データ構造
1-8-1 リスト構造
●テキスト２での対応部分
無し
●アルゴリズムとデータ構造 (テキスト1：p48)
・データ構造とは
「複数のデータの格納場所とその格納方式」のことを，
データ構造(data structure)
と呼ぶ。
※特に断らない限り，データ構造がメモリ上にあることを前提とする。
データ構造には
・
配列 (array, 線形リスト)
・
リスト (linked list, 連結リスト)
などの種類があり，それぞれに特徴があるので，用途に合わせて使い分ける。
・アルゴリズムとは
「データを処理する手順」のことを，
アルゴリズム(algorithm)
と呼ぶ。日本語
では，算法と呼ぶこともある。同じことを実現するにも，効率の良いアルゴリズ
ムもあれば，効率の悪いアルゴリズムもある。
・アルゴリズムとデータ構造
データ構造は，その種類ごとにそれぞれ特徴があるので，同じ操作を実現する
にも，
それぞれのデータ構造に相性の良いアルゴリズムがある
。
また，ある操作を実現するために必要とされるデータ構造もある。
データ構造への操作の代表的なものに
・新しい要素の
挿入 (Insert)
・特定の要素の
削除 (delete)
・特定の要素の
検索 (search, 探索)
・特定の基準に従って要素を並べ替える
整列 (sort, ソート)
などがある。
・流れ図
アルゴリズム(処理の手順)を分かりやすく視覚化したものに，
流れ図(flow chart, フローチ
ャート)
がある。
・コンピュータで実行可能なアルゴリズムなら，
(1)順次処理 (テキスト1では，「直線型」，「連続型」)
(2)条件分岐処理 (テキスト1では，「分岐型」，「選択型」)
(3)繰り返し処理 (テキスト1では，「繰り返し型」，「反復型」)
の３つの処理で構成できることが証明されている。
●配列とリストを理解することの重要性
配列とリストという2つのデータ構造の特徴を理解することで，データ構造とアルゴリズムの
基本的な関係が把握できる
。まずは，配列から見ていこう。
戻る
