2 はじめに

現在、諸君はC言語の文法の勉強をしている。実際プログラムの勉強は、文法の勉強だけ では全く不十分である。そのため、この講義では文法の学習が住むと、「アルゴリズムと データ構造」の学習を進める。アルゴリズムとは問題を解く手順のことである。コンピュー タープログラムでは、入力データから目的のデータを作成する手順を言う。プログラマー はアルゴリズムを考え、それをプログラミング言語で表現しなくてはならない。アルゴリ ズムが大事であることは、万人が認めることである。これは、コンピュータープロ グラム作成のみならず、数学や電気の問題を解く場合も同じである。科学の問題を解く場 合は手順が重要で、それが分かれば、問題が解けたのも同様である。

一方、データ構造となると、少し様子が異なってくる。数学や電気の問題のデータ構造と なると、想像がつかない。科学の問題では、データ構造は重要視されないので、それも仕 方ないことである。データ構造を気にするのは、なんと言ってもビジネスの分野である。 たとえば、私の場合、成績処理のデータ構造を考えなくてはならない。それには、年度と 学年、学籍番号、学生氏名、教科名、試験名、点数、レポート提出状況、出欠などのデー タを分かり易くまとめなくてはならない。実際には図表計算の Excelを使っているが、データ構造という意味では同じである。この例のように、データ の集まりのまとめ方をデータ構造という。

プログラムを作成する場合、そのアルゴリズムとデータ構造を考えなくてはならない。ア ルゴリズムは重要でそれの善し悪しでプログラムの性能が決まるのは、理解できるであろ う。しかし、データ構造については、結構無頓着になってしまいがちである。先 の成績処理のように単純な問題であれば誰でも同じようなデータ構造を考え、大した問題 は生じない。しかし、大量のデータがあるような場合には、いろいろなデータ構造が考え られる。大企業の顧客データなどがそれに当たる。住所や氏名、年齢、何時、どこで、購 入した商品のデータがある。これらに加えて、アンケートに答えていれば、それこを数十 の項目で、数百万人分のデータがあることも容易に想像できる。このデータをまとめ方 、すなわち構造は重要で、その後の処理の方法にも大きく影響するであろう。この構造に 従うということは、プログラマーの頭の中に、それがインプットされるので、それを用い た処理のプログラムを書くことになるからである。

また、データ構造が悪いと、効率の悪いプログラムになってしまう。たとえば、ファイル に100個の整数が書かれており、その合計を求めるプログラムでは配列を使うべきであろ う。変数を使ったプログラムでは、効率が悪くなるのはすぐに分かるであろう。

表 1: データ構造の種類

データ構造	基本データ構造	基本データ型	単純型	整数型
				実数型
				文字型
				論理型
				数え上げ型
			ポインタ型
		構造型	配列型
			レコード型
		抽象データ型
	問題向きデータ構造	線形リスト	単純リスト
			双リスト
			環状リスト
		木	二分木	完全二分木
				二分探索木
				バランス木
			多分木
			バランス木	AVL木
				B木
		スタック
		キュー

ホームページ: Yamamoto's laboratory
著者: 山本昌志