トップページへ戻る プログラミングの宝箱 アルゴリズムとデータ構造

『プログラミングの宝箱 アルゴリズムとデータ構造』について


プログラミングの宝箱 アルゴリズムとデータ構造 プログラミングの宝箱
アルゴリズムとデータ構造

紀平拓男・春日伸弥　著
376ページ
本体価格2,800円
2003年6月発行
ISBN 4-7973-2419-8


プログラミングの定石を理解して，もっとエレガントなプログラムを作成しよう

　ソート，サーチ，再帰，リスト，ツリーなど，プログラミングの定石となるアルゴリズムとデータ構造の基礎知識を解説します。C/C++，Javaのプログラムを，これまで以上にエレガントに記述しましょう。



ニュース

  • 本書で取り上げたアルゴリズムのRubyによる実装例
    　とみくらまさやさんが本書で取り上げているアルゴリズムをRubyに移植されています。



サポート情報



正誤表

　本書の内容に次のような誤りがありました。お詫びして訂正します。
［2005/4/1］
  • ハッシュ値の決め方
    　第7章「ハッシュ値の決め方」に次のような誤りがありました。

    • p. 219　14行目：
      　誤：与えられた文字列の各文字に256のべき乗の……
      　正：与えられた文字列の各文字に16のべき乗の……

    • p. 219　17行目：
      　誤：ハッシュ値=(x1×2560+x2×2561+x3×2562+…)%ハッシュ表のサイズ
      　正：ハッシュ値=(x1×160+x2×161+x3×162+…)%ハッシュ表のサイズ

    • p. 219　20行目：
      　誤：重率が2567に到達したら（8文字目），2560に戻して……
      　正：重率が167に到達したら（8文字目），160に戻して……

    • p. 220　List 7-2の8行目：
      　誤：/* 重率が256^7に到達したら（8文字目），一巡して再び元に戻す */
      　正：/* 重率が16^7に到達したら（8文字目），一巡して再び元に戻す */

    • p. 220　List 7-2の12行目：
      　誤：/* 「<<(4*weight)」は「256^weight」と同じ意味 */
      　正：/* 「<<(4*weight)」は「16^weight」と同じ意味 */

    • p. 225　List 7-3の17行目：
      　誤：/* 重率が256^7に到達したら（8文字目），一巡して再び元に戻す */
      　正：/* 重率が16^7に到達したら（8文字目），一巡して再び元に戻す */

    • p. 220　List 7-3の21行目：
      　誤：/* 「<<(4*weight)」は「256^weight」と同じ意味 */
      　正：/* 「<<(4*weight)」は「16^weight」と同じ意味 */

［2004/2/16］
  • リングバッファを用いたキューのソースコード
    　リングバッファを用いたキューのソースコード

    • C言語版　（p. 120）：
      • 1行目：
        　誤：#define QUEUE_MAX 5+1 /* キューのサイズ+1 */
        　正：#define QUEUE_MAX (5+1) /* キューのサイズ+1 */
［2003/10/27］
  • コイン問題の解法の解説図
    　コイン問題の解法の解説図に誤りがありました。

    • Tabel. 11-3「1p, 5p, 12pコインを交ぜて渡す場合」　（p. 309）：
      • 　誤：
        渡すお金(p) 1  2  ...   12  13  14   15  16 
        コインの枚数(枚) 1  2  ...   4  5   6   3  4 

        　正：
        渡すお金(p) 1  2  ...   12  13  14   15  16 
        コインの枚数(枚) 1  2  ...   1  2   3   3  4 

［2003/10/20］
  • ハッシュマップのソースコード
    　ハッシュマップのソースコードに次のような誤りがありました。

    • C言語版　（p. 225）：
      • 下から8行目：
        　誤：hashval=(firstshash+k*k)%k;
        　正：hashval=(firstshash+k*k)%hashtable->size;
      • 下から7行目：
        　誤：if(hashtable->data[hashval]!=NULL)
        　正：if(hashtable->data[hashval]==NULL)
    • Java版　（p. 231）：
      • 21行目：
        　誤：hashValue = (firstHash + k * k) % k;
        　正：hashValue = (firstHash + k * k) % hashTable.size;
      • 22行目：
        　誤：if (hashtable.data[hashValue]!=null) {
        　正：if (hashtable.data[hashValue]==null) {
  • B木の解説図
    　B木の解説図に誤りがありました。

    • Fig. 6-34「1〜64までを連続挿入したB木」　（p. 198）：
      • 最下層の左端の葉ページ：
        　誤：
         7  8  8    

        　正：
         7  8       

［2003/8/14］
  • 2分挿入ソートのソースコード
    　2分挿入ソートのソースコードに次のような誤りがありました。

    • C言語版　（p. 23）：
      • 11行目：
        　誤：for(sorted=0; sorted<N-1; ++sorted)
        　正：for(sorted=1; sorted<N; ++sorted)
      • 14行目：
        　誤：insert=sort[sorted+1];
        　正：insert=sort[sorted];
      • 18行目：
        　誤：while(left!=right)
        　正：while(left<right)
      • 21行目：
        　誤：if(sort[mid]<=insert)
        　正：if(sort[mid]<insert)
      • 29行目：
        　誤：while(i<=sorted+1)
        　正：while(i<=sorted)


    • Java版　（p. 33）
      • 8行目：
        　誤：for (int sorted = 0; sorted < N - 1; ++sorted) {
        　正：for (int sorted = 1; sorted < N; ++sorted) {
      • 10行目：
        　誤：int insert = sort[sorted + 1];
        　正：int insert = sort[sorted];
      • 17行目：
        　誤：if (sort[mid] <= insert) {
        　正：if (sort[mid] < insert) {
      • 25行目：
        　誤：while (i <= sorted + 1) {
        　正：while (i <= sorted) {


  • 初出一覧　（p. 360，下から1行目）
    　誤：「C MAGAZINE」2005年4月号
    　正：「C MAGAZINE」2002年5月号


目次内容

第1章　ソート
大量のデータを整理する
バブルソート
クイックソート
マージソート
ソートの「安定性」
そのほかのソート方法
最適なソートは?
第2章　サーチ
リニアサーチ
バイナリサーチ
数値配列以外への応用
超整理法?
第3章　リスト
データ構造?
いくつあるかわからないデータ
リスト登場
リストのサーチ
応用例――自己組織化探索
第4章　スタック&キュー
スタックとは?
スタックの実装
リストとスタック
スタックの利用例1――カッコの対応
スタック利用例2――簡単な数式の計算
キューとは?
キューとリスト
キューの利用例
第5章　再帰呼び出し
再帰呼び出しとは
再帰のしくみ
最大公約数を求める
開き直り数
第6章　ツリー構造
樹形図のように枝分かれ
ツリー構造
2分木（binary tree）
多数の子ノードをもつツリー
第7章　マップとハッシュ
キーから値をサーチする
2分木を使ったツリーマップ
スマートなハッシュマップ
ハッシュ値の決め方
第8章　浮動小数点型と数値計算
たかがfloat，されどfloat
誤差は油断大敵
複雑な方程式を解く
第9章　文字列検索
文字列を検索する
最も単純な文字列検索
検索のムダを省く（KMP法）
現実的に優れた方法（BM法）
文字列以外への応用
第10章　バックトラック法と幅優先探索
開き直って試行錯誤
バックトラック法
堂々めぐりと遠回り
幅優先探索法
第11章　動的計画法
分割統治法（トップダウン的な問題解決）
コイン問題の解法
ナップザック問題を動的計画法で解く
動的計画法に適している問題
バックトラック法と動的計画法の比較
第12章　アルゴリズムで遊ぶ〜テンパズルに挑戦
4つの数字で10を作る
どのように解くか方針を立てる
逆ポーランド記法について
逆ポーランド記法を用いたアプローチ
まとめ


C MAGAZINE編集部