大話數(shù)據(jù)結(jié)構(gòu)勘誤

1、盡管已經(jīng)很仔細(xì)的檢查和審核，但錯(cuò)誤還是沒有能避免。以下的錯(cuò)誤，有些是作者的筆誤或者表述不清，有些是編輯審稿時(shí)不理解造成的錯(cuò)誤，有些是美編改圖時(shí)的錯(cuò)誤，有些是印刷廠印刷時(shí)的錯(cuò)誤。雖然出錯(cuò)的原因很多，但總的來說都會(huì)給讀者閱讀時(shí)造成困擾，所以再次向讀者說一聲對(duì)不起！并請讀者時(shí)常關(guān)注本博文，以便可以獲得最新的勘誤信息?，F(xiàn)勘誤如下：注：、和為建議馬上修改，它們之間程度不同，沒有星為可改可不改，不影響閱讀。第一次印刷：1.01 P38，倒數(shù)第二行，“速度其實(shí)只提高了10”，后面增加一個(gè)“倍”字。1.02 P111，第三段，第二行，“打算了Reset時(shí)”，多了一個(gè)“了”字。目錄P15，同樣的問題。1.03

2、P268，P269，圖7-7-14，圖7-7-15，圖7-7-16橫豎條中都是有符號(hào)或數(shù)字的，目前因印刷問題沒有顯示。1.04 P377 “時(shí)間性能”這一段中 "事實(shí)上，移動(dòng)可以通過改為記錄的存儲(chǔ)方式來予以避免" ，其中“改為”應(yīng)該是“改變”1.05 P35，第一行，有一個(gè)“+”號(hào)應(yīng)該是“=”，見下圖第二次印刷：2.01 P383，代碼第6行，“ for(i=1;i<L->length && flag; i+)  /*若flag為true則退出循環(huán)*/” 其中注釋應(yīng)該改為“/* 若flag為true說明有過數(shù)據(jù)交換，否則停止循環(huán) */”

3、（ My Blogs 提供）2.02 P20，代碼中“int i,sum =0, n = 100;”中的"i,"是多余的，可以刪除，因?yàn)闆]有用到i變量。（ AGPSky 提供）2.03 P43，圖3-2-2，在天秤和射手之間，少了一個(gè)“天蝎座”。 ( 小老K 提供)2.04 P58，圖3-6-5，左側(cè)第三條，“頭指針均不為空”應(yīng)該改為“頭指針均存在” ( 小老K 提供)2.05 P58，圖3-6-4和圖3-6-6，兩圖中“頭指針”改為“后繼指針地址”。圖3-6-6，“0900”應(yīng)該改為“NULL” ( 小老K 提供)2.06 P60，

4、中間編號(hào)1后面，“聲明一個(gè)結(jié)點(diǎn)p”改為“聲明一指針p”。下方代碼中第6行，“/*聲明一結(jié)點(diǎn)p*/”應(yīng)該改為“/*聲明一指針p*/”。( 小老K 提供)2.07 P64，第一句：“用來存放e數(shù)據(jù)s結(jié)點(diǎn)?！?，將“e數(shù)據(jù)s結(jié)點(diǎn)"改成“數(shù)據(jù)e的s結(jié)點(diǎn)” ( 小老K 提供)2.08 P71，倒數(shù)第三段第三行，“而游標(biāo)cur相當(dāng)于單鏈表中的next指針，存放該元素的后繼在數(shù)組中的下標(biāo)?！?，將“游標(biāo)”兩字刪除，并在句子最后句號(hào)前增加一句:“，我們把cur叫做游標(biāo)?！?#160;( 小老K 提供)2.09 P105，第五段第二行，“只有碰到左括號(hào)”改為“只要碰到左括號(hào)”。 ( 小老K 提供

5、)2.10 P105，第五段最后一行，“最終再因全部匹配成功后成為空棧的結(jié)果?！?，將“的結(jié)果”刪除。( 小老K 提供)2.11 P109，第6條，將第一個(gè)句號(hào)前的句子與第二個(gè)句號(hào)前的句子對(duì)調(diào)。結(jié)果為“緊接著是符號(hào)"X"，因?yàn)榇藭r(shí)的棧頂符號(hào)因此不輸出，"*"進(jìn)棧。接著是數(shù)字3，輸出，總的表達(dá)式為931-3?！? 小老K 提供)2.12 P126，第三段倒數(shù)第二行，“表示216個(gè)字符”，“216”應(yīng)該改為“216”（strider 提供）2.13 P137，第四段第一行，“假設(shè)S="abcabcabc"，”，其中的字符串S應(yīng)該是

6、“abcababca”。圖5-7-4和圖5-7-5的第圖，都應(yīng)該改為下圖所示。（strider 提供）2.14 P138，倒數(shù)第二段第二行，“而圖5-7-4中，”改為“而圖5-7-5中，”。（strider  秦萌 提供）2.15 P144，5.7.5小節(jié)中第1號(hào)小標(biāo)題中：“先計(jì)算出next數(shù)組的值分別為001234223”，應(yīng)改為011234223”。（strider 提供）2.16 P145，9)"當(dāng)j=9時(shí)，next值為3，.因此nextval9=nextval3=1" 最后的“1”應(yīng)改為“0”。（strider 提供）2.17 P153

7、，6.2.3節(jié)第一段第三行，“而G、H、I、J也是?！?，應(yīng)該改為“而G、H、I與J也是堂兄弟?！?（康凱 提供）2.18 P155，6.4.1小節(jié)第二段第二行：“其雙親結(jié)點(diǎn)到鏈表中的位置”應(yīng)改為“其雙親結(jié)點(diǎn)在數(shù)組中的位置”。（strider 提供）2.19 P157，表6-4-3的數(shù)據(jù)第一行 A的firstchild 應(yīng)該是 1 不是 -1。( 小老K 提供)2.20 P169，6.6.2 二叉樹性質(zhì)2的第四段，“如果有一層，至多1=20-1個(gè)結(jié)點(diǎn)”，應(yīng)該是“21-1個(gè)結(jié)點(diǎn)”。（康凱 提供）2.21 P170，倒數(shù)第二段第二行，“倒推得到滿二叉樹的度數(shù)為”，其中“度數(shù)”改為“深度”，第三行，“

8、度為4”，應(yīng)該改為“深度為4”。( 小老K 提供)2.22 P171，第一行“等于同樣的度數(shù)”，“度數(shù)”改為“深度”；第四行，“而k作為度數(shù)也是整數(shù)”，“度數(shù)”改為“深度”；圖6-6-2上面一段，“這是一個(gè)完全二叉樹，度為4”，“度為4”改為“深度為4”。( 小老K 提供)2.23 P199，56行 “比如圖6-11-4中最右側(cè)的樹”，將“最右側(cè)”改為“右下方”。倒數(shù)34行 “比如圖6-11-5右側(cè)三棵樹的森林”，將“右側(cè)”改為“下面”。P200 第一行 “6-11-5右側(cè)三棵樹的森林”，“右側(cè)”改為“下面”。( 小老K 提供)2.24 P200，第二行，“我們對(duì)圖6-11-4的左側(cè)二叉樹”，

9、“6-11-4”改為“6-11-5”。( 小老K 提供)2.25 P203，第一行，“我們先把這兩棵二叉樹簡化成葉子結(jié)點(diǎn)帶權(quán)的二叉樹”，應(yīng)該加“注：樹結(jié)點(diǎn)間的邊相關(guān)的數(shù)叫做權(quán)（Weight）”。( 小老K 提供)2.26 P203，第三段第四行，“每個(gè)葉子的路徑長度為lk”,其中"lk"應(yīng)該改為“l(fā)k”，即k是下標(biāo)。( 小老K 提供)2.27 P218，倒數(shù)第二段第一行，“圖7-2-9中的左側(cè)”，其中“左側(cè)”改為“上方”，后面的“右側(cè)兩條路徑長度為3”，其中“右側(cè)”改為“下方”。( 小老K 提供)2.28 P219，中間一段第二行，“兩個(gè)頂點(diǎn)vi、vjE，”，這里“E”應(yīng)該

10、改成“V” (咖啡崽 提供)2.29 P220，倒數(shù)第二行，“在存在”，應(yīng)該改成“不存在”。(咖啡崽 提供)2.30 P220，圖7-2-13的圖1和圖2，頂點(diǎn)A與頂點(diǎn)B之間的箭頭都畫反了。(咖啡崽 提供)2.31 P338，圖8-7-10，圖中有小錯(cuò)誤，且圖形過于繁瑣，不利于讀者理解，因此做比較大的修改如下圖。（康凱 提供）2.32 P52，代碼中間部分，“for(k=L>length-1;k>=i-1;k-”后面少了一個(gè)“）”。（蕭蕭Leo 提供）2.33 P95，第二行 “另一個(gè)棧為棧的末端” 應(yīng)該改成“另一個(gè)棧為數(shù)組的末端”。（ AGPSky

11、提供）2.34 P248，倒數(shù)第六行，“arjvex”應(yīng)該為“adjvex”。（蕭蕭Leo 提供）2.35 P263，第8小節(jié)，“此時(shí)i=2?！备某伞按藭r(shí)v=2?！?。P264，第11小節(jié)，“此時(shí)i=3?！备某伞按藭r(shí)v=3?！保ㄊ捠扡eo 提供）2.36 P260-P261，書中代碼“matirx”都應(yīng)該改為“matrix”（一共有五處修改，分別是P260倒數(shù)第三行，P261，代碼1、8、27、29行）。在提供下載的代碼中，統(tǒng)一將matrix修改成了arc。（蕭蕭Leo 提供）2.37 P285，倒數(shù)第四行，公式中“minltvj+len”，中“+”應(yīng)該是“-”（蕭

12、蕭Leo 提供）2.38 P81，第一行代碼，“rearB->next=p; free(p);” 應(yīng)該在這兩句上方加一句“q=rearB->next; ”（即在四句代碼的中間增加一句），并修改最后的“free(p);"為“free(q); /*釋放q*/ ” (siatliuliu1 提供)2.39 P26，倒數(shù)第四行最后，“運(yùn)算100次是運(yùn)算10次的100”，應(yīng)該是“運(yùn)算10次的1000”。（laciqs 提供）2.40 P46，union代碼，有不少的問題，修正如下圖。union是C語言的關(guān)鍵字，因此函數(shù)名增加一個(gè)L。

13、具體實(shí)現(xiàn)代碼，請參見源代碼中的“01線性表順序存儲(chǔ)_List.c”文件（laciqs 提供）2.41 P59，倒數(shù)第五行，“結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域”后面加一個(gè)“和”字。以下2011-8-23更新2.42 P216，圖7-2-6，頂點(diǎn)B與頂點(diǎn)D缺少兩根互為反向的連線。因?yàn)橛邢蛲耆珗D的定義是任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條弧。（Zhangth 提供）2.43 P247。圖7-6-3中鄰接矩陣有些錯(cuò)誤。 arcv2v1應(yīng)該是18， arcv3v6和arcv6v3都應(yīng)該是24。 （Zhangth 提供）2.44 P330，圖8-7-2，圖1，刪除葉子結(jié)點(diǎn)35和

14、結(jié)點(diǎn)99。（黑洞熵 提供）以下2011-8-25更新2.45 P285  第6小節(jié)，“l(fā)tv相對(duì)應(yīng)的值為19、25、13”，三個(gè)數(shù)字的順序應(yīng)該是“19、13、25”。（黑洞熵 提供）2.46 P332，第一行，“平衡因子沒有發(fā)生改變”，改為“平衡因子沒有超出限定范圍（-1，0，1）”。 （黑洞熵 提供）2.47 P334，圖8-7-8中的圖15中結(jié)點(diǎn)7的BF值應(yīng)該是-2而不是-1。（黑洞熵 提供）2.48 P347 第二段，情形二的第二行，“此時(shí)刪除結(jié)點(diǎn)1”，修改為“此時(shí)刪除結(jié)點(diǎn)4”。（黑洞熵 提供）以下2011-8-30更新2.49

15、 P375，第二段第三行，“（非遞減或非遞增）關(guān)系”，是應(yīng)該寫成“非遞減（或非遞增）關(guān)系”。（黑洞熵 提供）以下2011-9-1更新2.50 P76，第一段第二行，“j=k999.cur=1",應(yīng)該將“k"修改為“L”。（Mark1940 提供）2.51 P387，第3條最后一行 “L.rj-1=L.rj ”應(yīng)該是“L.rj+1=L.rj” （蕭蕭Leo 提供） 以下2011-9-2更新2.52 P57，第6行,"元素ai的存儲(chǔ)映像,稱為節(jié)點(diǎn)"中的i應(yīng)該是a的下標(biāo).（Jeallyn 提供） 以下2011-

16、9-7更新2.53 P319，代碼下第一段第一行，"InsertBST(T,93)"應(yīng)該是"InsertBST(&T,93)"，第二行，"InsertBST(T,95)"應(yīng)該是"InsertBST(&T,95)" （ff22 提供）以下2011-9-21更新2.54 P398，中間一段，堆排序定義的倒數(shù)第二行，“這樣就會(huì)得到n個(gè)元素中的次小值”，其中“次小”應(yīng)該改為“次大”。（ff22 提供）以下2011-10-8更新2.55 P235，圖7-4-11，V1點(diǎn)的陰影應(yīng)該改為V2

17、，修改結(jié)果見下圖（盲劍客 提供）以下2011-10-18更新2.56 P339，代碼第22行，"if (taller)"，應(yīng)該改為"if (*taller)"。本書提供的源代碼也有相同錯(cuò)誤，已經(jīng)做了修改。（Jakson 提供）2.57 P158，圖6-4-2，每個(gè)結(jié)點(diǎn)末尾都多畫了一個(gè)指針域（即應(yīng)該有四個(gè)方格卻畫了五個(gè)），應(yīng)該要去掉，如下圖。（孟倩 提供）以下為第三次印刷還遺留的錯(cuò)誤以下2011-11-09更新3.01 P329，倒數(shù)第二行，“結(jié)點(diǎn)58的左子樹高度為2，”其中2應(yīng)該改為3。（ 小墨的童鞋 提供）3.0

18、2 P330，中間一段，“（即它的左子樹高度2減去右子樹高度0）”，應(yīng)該改為“（即它的左子樹高度3減去右子樹高度1）”。然后圖8-7-3在結(jié)點(diǎn)58的右側(cè)增加一個(gè)60的結(jié)點(diǎn)，如下圖。（ 小墨的童鞋 提供）以下2011-11-14更新3.03 P194，中間第3條，"第78行，whild(p!=T)"，其中"whild"應(yīng)該改為"while"。（小老k 提供）3.04 P251 第三行 “假設(shè) N=(P,E) .” 改為“假設(shè) N=(V,E) .” （小老k 提供）以下2011-11-23更新3.05 P126頁第三段

19、倒數(shù)第二行，“65萬”改為“6.5萬”（somebodysssss 提供）以下2011-12-05更新3.06 P351，中間一段，有四處的m/2都應(yīng)該是 m/2，見下圖。（ 給你改錯(cuò) 提供）以下2011-12-07更新3.07 P288，第二段第二行，“十字鏈表是鄰接矩陣的一種升級(jí)，而鄰接多重表則是鄰接表的升級(jí)。”，應(yīng)該改為“十字鏈表是針對(duì)有向圖鄰接表結(jié)構(gòu)的優(yōu)化，鄰接多重表是針對(duì)無向圖鄰接表結(jié)構(gòu)的優(yōu)化。”（韋歡 提供）以下2011-12-20更新3.08 （本次改動(dòng)僅限第三次印刷）P61，代碼第三行，"if (!p | j>=i)"，請

20、將“=”去掉。P63，代碼中間一行，"if (!p | j>=i)"，請將“=”去掉。P65，代碼中間一行，"if (!p | j>=i)"，請將“=”去掉。（kenly2007 提供）以下2012-01-09更新3.09 P68 最后一行，"那么應(yīng)該讓這個(gè)鏈表的指針域置空" ，其中“鏈表”應(yīng)該改為“節(jié)點(diǎn)”。（落崖驚風(fēng) 提供）3.10 P138 最下方的公式，“且p1k-1”，在“k-1”的左側(cè)少了一個(gè)"p". （落崖驚風(fēng) 提供）以下2012-02-07更新3.11 P108 倒數(shù)第

21、四行最后一句，“是右括號(hào)或優(yōu)先級(jí)低于”，其中“低于”改為“不高于”。（王天興 提供）3.12 在源代碼中棧與隊(duì)列的DoubleStack.c中的兩個(gè)問題（目前源代碼已經(jīng)修正，重新下載即可。書中講解并無錯(cuò)誤）：問題1：int StackLength(SqDoubleStack S) return (S.top1+1)+(MAXSIZE-1-S.top2);中的語句return (S.top1+1)+(MAXSIZE-1-S.top2); 應(yīng)該修改為 return (S.top1+1)+(MAXSIZE-S.top2);問題2：Status StackTraverse(SqDoubleStack

22、S)int i;i=0;while(i<=S.top1)visit(S.datai+);i=S.top2;while(i<MAXSIZE)visit(S.datai+);printf("n");return OK;中的語句 while(i<S.top1) 應(yīng)該修改為 while(i<=S.top1) （閆豐 提供）以下2012-02-13更新3.14 P234 圖7-4-10 右下角那句“V2后再無V0的入邊頂點(diǎn)，所以其taillink為空” taillink應(yīng)該是headlink （風(fēng)碎月 提供）以下2012-04-12更新4.01 P1

23、88，第二段整段刪除，即“當(dāng)然，你完全也可以#DB#CA”這一段。原因在于，由于中序遍歷不能首先建立根結(jié)點(diǎn)，用加“#”的方法是不可能創(chuàng)建一個(gè)二叉樹的，后序遍歷在特定規(guī)則下可以見 G-rated 提供）以下2012-06-04更新4.02 P52，代碼第8行，"if (i<1 | i>L->length+1)"當(dāng)中的“+1”不需要，應(yīng)該是"if (i<1 | i>L->length)"。（ csensix 提供）本處不需要修改，并沒有錯(cuò)，詳細(xì)說明請看我提供的源代碼的注釋“/* 當(dāng)i比第一位置小或者比最后一位置后一位置還要大時(shí) */”以下2012-06-25更新p70，圖3-11-1，時(shí)間性能最后一個(gè)，“線出”應(yīng)改為“找出” （ Darker 提供）以下2012-07-16更新p261 代碼第9行 “(*P)v=0 /*初始化路徑數(shù)組P為0 */” 將其中的0改為-1，即“(*P)v=-1 /*初始化