[ TOPへ戻る ]

データ構造とアルゴリズム 自習用デモプログラムおよびソースコード集 (C)

学習の仕方

このプログラムパッケージは、「データ構造とアルゴリズム」を学ぶための
教材として作成されています。

アルゴリズムを本当に身につけるには、ただ教科書を読んで理解しただけでは不十分で、
実際に自分で動くプログラムを書いてみることが絶対に必要です。
ただ、実際のプログラミング環境では、言語特有のルールを理解したり、
入力データを用意したりといった本質的でない部分に時間をとられてしまうことが多く、
学習の防げとなっています。

そこで、この学習用プログラムパッケージでは、なるべくアルゴリズムの本質的な部分だけに
集中してプログラミングの練習ができるような工夫をしました。

ダウンロードして解凍すると、
まず大きく分けて complete フォルダと exercise フォルダに分かれています。
complete の方には、完全に動作するプログラム例が入っています。
exercise の方には、自分でプログラムを書いてみるための練習用の
テンプレートとして、completeからのアルゴリズム本体部分だけを
取り除いたものが入っています。プログラミングしやすいように、
必要な関数などの使用例をダミーとして入れてありますので、これを参考にして
「正常に動作する」プログラムを書いてみてください。

complete, exercise ともに各ファイルとアルゴリズムの対応は以下のようになっています。


Makefile: Makefile (参照：Make)
datatypes.h: 各データ構造の定義
heap.c: ヒープアルゴリズムの実装　(アルゴリズム本体および入出力)
binarysearchtree.c: 二分探索木アルゴリズムの実装　(アルゴリズム本体および入出力)
meargefindset.c: 集合群の実装　(アルゴリズム本体および入出力)
bubblesort.c: バブルソートの実装　(アルゴリズム本体)
quicksort.c: クイックソートの実装　(アルゴリズム本体)
mergesort.c: マージソートの実装　(アルゴリズム本体)
heapsort.c: ヒープソートの実装　(アルゴリズム本体)
sort.c: ソートアルゴリズムの入出力の実装　(入出力)
print.h / print.c: データ構造可視化機構の実装
tools.h / tools.c: swap関数など共通のツールの定義


学習する際には入出力部分で宣言された関数についてはブラックボックスとして利用し、
アルゴリズム本体部分だけのソースコードだけを参照したり編集したり
すれば十分なように設計してあります。

推奨する学習の仕方は以下の通りです。
1) 教科書を読んでアルゴリズムの考え方、動作を頭で理解する。
2) complete フォルダにある対応するプログラムを動かしてみて、動作を理解する。
3) exercise フォルダにあるテンプレートプログラムを書き直して完全に動くようにする。
4) どうしてもわからなかったら complete フォルダにある正解プログラムを適宜参照する。
  (テンプレートプログラムの末尾にもコメントアウトして正解をつけてあります)

これで難しい人は3の前に2のソースコードも一度読んできちんと理解して、
（そのまますぐだと暗記しただけなので一晩くらい置いて）、
その上で3に取りかかるのでもよいと思います。

やってみるとわかると思いますが、おそらく
一回書いてみただけではうまく動かないと思うので、何度も試行錯誤
（デバッグ）することが必要になると思います。
デバッグの際には、print.h で宣言されている関数群をうまく利用してください。
なんどもデバッグ作業の経験をつむことで
実際に抽象的なアルゴリズムを実際のプログラムとして実現する実力をつけることが
できます。すべてのexerciseを終えたころにはかなりの力がついていると
思ってよいと思います。

実行の仕方

コンパイルおよび実行するにはC言語のコンパイラおよび (Make) がインストールされている
必要があります(無料)。

インストール後は、コンソールから以下のコマンドを入力することによりコンパイルできます。


make: 全ての実行ファイルを生成
make heap: ヒープの実行ファイルを生成
make binarysearchtree: 二分探索木の実行ファイルを生成
make mergefindset: 集合群の実行ファイルを生成
make sort: ソーティングの実行ファイルを生成(バブルソート、クイックソート、マージソート)
make clean: 全ての生成されたファイルを消去


実行は生成された実行ファイルをコンソールから実行してください。パラメータの指定が必要なものもあります。
各実行ファイルごとに定義されたコマンドを入力することにより、データの挿入、削除、ソートなどができます。
また、データ構造の表示もできます。
コマンドやパラメータの詳細は実行時に提示されます。
EOFを入力(Ctrl+D)することで実行を終了します。

例：
bash-3.2$ ./sort 1000
**********ソート**********
コマンド：
i [n] [m1] [m2] ... [mn]: n個の整数の列m1 .. mnをデータとして定義
b : データをバブルソートする
q : データをクイックソートする
m : データをマージソートする
h : データをヒープソートする
p : 集合群全体の内容を表示
*************************
i 10 3 89 2 49 3 278 50 3 2 1 (↓Enter)
p (↓Enter)
Data: : [3, 89, 2, 49, 3, 278, 50, 3, 2, 1]
h (↓Enter)
p (↓Enter)
Data: : [1, 2, 2, 3, 3, 3, 49, 50, 89, 278]

(↓Ctrl-D)　終了

コマンド列を他のファイルに定義しておいて、パイプなどを用いて入力することにより、一気に複数のコマンドの実行および
実行結果の表示が可能です。デバッグ時などに活用してください。

例：
./sort 1000 < input.txt

input.textの内容:

i 10 3 89 2 49 3 278 50 3 2 1
p
h
p

ソースコード(Cファイル)の編集は通常のメモ帳やワードパッドなどで可能です。
ただ、本格的にプログラムを書くには eclipse などの開発環境(IDE)を利用することを
薦めます。

Copyright (c) Takeo Igarashi