2010.05.06

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

WRCII~エクストリーム~ 公式コンプリートガイド

ハッシュ値の決め方
 第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」と同じ意味 */

リングバッファを用いたキューのソースコード
 リングバッファを用いたキューのソースコードに次のような誤りがありました。

  • C言語版 (p. 120,List 4-4):
    • 1行目:
       誤:#define QUEUE_MAX 5+1 /* キューのサイズ+1 */
       正:#define QUEUE_MAX (5+1) /* キューのサイズ+1 */

ハッシュマップのソースコード
 ハッシュマップのソースコードに次のような誤りがありました。

  • 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) {

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) {

B木の解説図 (p. 198,Fig. 6-34)
最下層の左端の葉ページ:
 誤:

 7   8   8     

 正:

 7   8         

コイン問題の解法の解説図 (p. 309,Table 11-3)
 誤:

渡すお金(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 

初出一覧 (p. 360,下から1行目)
 誤:「C MAGAZINE」2005年4月号
 正:「C MAGAZINE」2002年5月号

修正版のソースファイルは、Cマガジンの本書のページからダウンロードできます。どうぞご利用ください。