Cをさらに理解しながら学ぶデータ構造とアルゴリズム  

  • 森元 逞 
書籍情報
ISBN
978-4-320-12197-3
判型 B5
ページ数 176ページ
発行年月 2007年12月
本体価格 2,600円
見本を請求する
Cをさらに理解しながら学ぶデータ構造とアルゴリズム 書影
Cをさらに理解しながら学ぶデータ構造とアルゴリズム

 本書は「データ構造とアルゴリズム」に関する入門用のテキストである。本科目を学ぶ学生は,一応C言語などは履修していても,まだ十分に理解しているとは言い難い場合が多い。そこで本書では,基本的なアルゴリズムを理解させることは勿論であるが,本学習を通してC言語をさらに十分に理解させ,ある程度のプログラムを自ら書けるようにすること,さらにはコンピュータの動作原理も理解させること,などを目標としている。
 以上の目的のため,他の類似の教科書とはかなり異なった構成をとっている。最初の数章は,計算機構成の概要や,C言語で学んだ内容を再確認するためにデータ型や関数について説明している。その後初めて「データ構造とアルゴリズム」の学習に入る。また,学生にとってポインタを理解するのが,大きなハードルになっている場合が多い。そこで,最初はポインタなどをあまり使わないアルゴリズムを紹介し,ポインタについては後ろの章で,C言語の復習を兼ねて,その考え方などを説明しながら,徐々に理解できるようにした。一方,先にも述べたように,ある程度のプログラムを自ら書けるようにするため,他の教科書ではあまり記述されていないファイル入出力などの説明も行い,また実際に計算機を使ってコンパイルをしたり,実行する際に遭遇するであろうトラブルについても,コラムなどで対処方法を説明している。さらには,字句解析,分割統治法,動的計画法など,学生にとってはかなり高度な内容も記載している。これは,何度も繰り返すように,学生がある程度のレベルのプログラムが書けるようにしたいためである。本書の内容を十分理解すれば,卒業論文で必要となる程度のプログラミング能力は十分に身に付けることができる。

目次

1.アルゴリズムとは
1.1 アルゴリズムとは
1.2 アルゴリズムの表現

2.計算機とプログラム
2.2 C言語と機械語の関係
2.3 コンパイラとローダ
2.4 コンパイラを使用する際の注意すべきいくつかの機能

3.データ型,配列,構造体
3.1 データ型
3.2 型変換(キャスト)
3.3 配列
3.4 構造体

4.関数
4.1 プログラム構成と関数
4.2 関数による共通処理の実現
4.3 変数の有効範囲
4.4 関数の再帰呼び出し

5.表構造での探索
5.1 線形探索
5.2 2分探索

6.アルゴリズムと計算量
6.1 アルゴリズムの良否
6.2 計算量の表現方法
6.3 計算量の種類

7.ポインタの概念
7.1 ポインタの概念
7.2 配列とポインタ

8.ファイル入出力
8.1 標準入出力(端末との入出力)
8.2 パイプ,リダイレクト機能とファイルとの入出力
8.3 ファイル入出力

9.スタック

10.ソート(整列)
10.1 単純な方法によるソート
10.2 バブルソート
10.3 選択ソート
10.4 挿入ソート
10.5 シェルソート
10.6 ソートの一般的な計算量
10.7 クイックソート
10.8 マージソート
10.9 ソートアルゴリズムの安定性

11.リスト構造と待ち行列
11.1 記憶域の動的確保とポインタ
11.2 構造体データの動的確保とアクセス
11.3 関数間での構造体ポインタの受け渡し
11.4 リスト構造
11.5 待ち行列

12.種々のリスト構造
12.1 優先度付き待ち行列
12.2 双方向リスト
12.3 リスト構造を用いたスタック
12.4 リングバッファ

13.ハッシュ法
13.1 チェイン法
13.2 開番地(オープンハッシュ)法

14.木構造・2分探索木
14.1 木構造
14.2 2分探索木
14.3 木の巡回
14.4 ヒープ

15.種々の木構造
15.1 平衡木
15.2 B木
15.3 トライ
15.4 パトリシア

16.グラフ構造
16.1 グラフ
16.2 グラフの表現
16.3 グラフの探索
16.4 バックトラックによるパスの探索
16.5 最短路問題
16.6 グラフの最小スパニング木

17.文字列探索
17.1 文字列の探索
17.2 BM法

18.文字列(字句)解析
18.1 トークンの切り出し
18.2 多種類のトークンの処理
18.3 正規言語に属する表現の解析

19.種々のアルゴリズム
19.1 深さ優先探索と幅優先探索
19.2 分割統治法
19.3 動的計画法
19.4 欲張り法

付録A.JIS 8ビットコード表
付録B.Unix(Linux)の簡単な使い方
付録C.Windows上でのCプログラミング(Cygwin)

参考書
索引