《 数据结构》课本堪误表

作者:王聪

<xiyou.wangcong@gmail.com>



你的计算机知识是由错误的人使用错误的资料教给你错误的知识。”

──匿名人士

. 忘记检查malloc()函数的返回值

malloc()并不总是返回你想要的指针,分配失败时它会返回NULL。即使99%的情况下它都运行正确,检查返回值是否为NULL仍然是*必须*的。不检查的确是很差的编程习惯,是国际新闻组comp.lang.c上经常谴责的地方之一。

此类错误见:

Page 27 函数fun3()Page 28 函数main()Page 44 函数InitList()Page 45 函数CreateFromHead()Page 47 函数CreateFromTail()Page 50 函数InsList()Page 60 函数polycreate()Page 68 函数BinAdd()Page 161 函数CreateBiTree()Page 190 函数CrtHuffmanCode()Page 256 函数InsertBST()Page 270函数ins_AVLtree()Page 278函数ins_mbtree()Page 279函数split()。作者似乎从第3章开始已经意识到这个错误,后面的一些地方知道弥补这个错误了。



. 关于健壮性

在第9页,我们的教材堂而皇之地提到:“(健壮性)即对非法输入的抵抗能力。它强调的是,如果输入非法数据,算法应能加以识别并做出处理,而不是产生误动作或陷入瘫痪。”但它真的做到了吗?答案是没有!具体分析如下。

比如:第73页函数InitStack():没有检查参数是否是空指针。你当然可以说我小心使用就对了:

assert(S!=NULL);

InitStack(S);

很好。那么请注明该函数的使用方法,如下:

InitStack函数会初始化堆栈,但是请千万小心:在任何情况下都务必要传递给它一个非空指针,否则程序必定会崩溃。对于该错误引起的任何事故,本人一概不负责任。

{判断这是否合适留给读者作为课下练习。;-) }

同类的错误还发生在:

Page 74 函数Push():仍然没有检查指针是否为空。Page 74 函数Pop(),函数GetTop()Page 75 函数InitStack(),函数Push()Page 77 函数Push(),函数Pop()Page 92 函数InitQueue(),函数EnterQueue()Page 93 函数DeleteQueue()Page 108 函数StrInsert()Page 109 函数StrDelete(),函数StrCopy()Page 110 函数StrCat()Page 111 函数SubString()Page 114 函数StrAssign()Page 115 函数StrInsert(),函数StrDelete()Page 143 函数CopyGList()Page 161 函数CreateBiTree()Page 172 函数InsNode()Page 256 函数InsertBST()Page 270函数ins_AVLtree()Page 278函数ins_mbtree(),函数insert()Page 279函数split()都有类似错误。作者似乎从第6章才开始注意到这个错误!但后面仍然有此类错误,可能作者认为一味检查这种错误有时会过于烦琐,但是假如在文件系统中有一个空指针没有被正确处理,后果可能就是整个文件系统崩溃!那时你就不会认为它太烦琐了!



. 定义之前使用

C不是解释执行的语言,变量使用之前必须要定义。而此书中出现许多未定义就使用的变量,如下:

48:在函数ListLength()中,j未定义就使用。

137:函数CreateCrossList()中,变量m,n,t,i,j,e,p,q

274:函数srch_mbtree()中: 变量pfpfoundi使用前均未定义!true/false大概是宏,却没有定义;否则就可以认定是在使用C++,但C++中的true/falsebool类型的常量,而不是int!函数search()中的i,n也未定义。

287:函数HashSearch()中:变量hi

326:函数Distribute()中的变量j,p。函数Collect()中的变量j。函数RadixSort()中的i,n,d

. 又是内存泄漏

很不幸,我们的教材存在低级的失误而导致内存泄漏!一种隐蔽的内存泄漏可以在第137页函数CreateCrossList()中见到,从第二次调用malloc()函数开始,如果返回NULL,一定要释放前面分配的内存,仅仅exit()是不够的。



. 糟糕的排版

作者编码的习惯实在是谈不上好,缩进还倒是注意得不错,但花括号的格式五花八门。

第一种格式见第25-28页,函数采用如下格式:

int foo(int a, int b)

{ /*statements begin from this line.*/

/*end here*/

}

if/for/while循环采用如下格式:

for( ... )

{

/*statements begin from this line*/

}

而在后面的代码中,我们至少可以见到3种排版,比如第39页的一种:

int InsList(SeqList *L,int i,ElemType e)

{

/*statements begin from this line.*/

if( ... )

{ /*also here*/

}

}

你说这是小事,可我从来不这么认为。你再这么说就罚你把Linux Kernel 2.6 的代码打乱再读一遍。 ;-|



. 其它错误

28:在main()函数中,xy定义为两个指向整型的一级指针,而malloc()分配空间时分给它们的内容竟是int*,也就是说,它们变成了二级指针int**!当然,程序可以运行,因为int*类型占的空间恰好和int一样大,都是4个字节。但这不是说它就是对的,在64位机上,int仍是32个比特,而指针类型会和机器字长一致,8个字节。

33:请仔细看看选择题第(3)题有没有答案!

40:显然是for循环漏掉了花括号,否则就会一直执行下去!

59gcc如是说:error: expected specifier-qualifier-list before 'Polynode'

拜托!应该是struct Polynode* next; !你以为是在使用C++吗?

83case '>=' 实在是让人费解,脱离编程语言也没有这种脱离的方法吧。首先,如果Compare()函数返回char类型,'>='也不会是一个chargcc如此抱怨:

warning: multi-character character constant

warning: overflow in implicit constant conversion

其次,比较函数一般都是返回int,比如库函数strcmp()

136*OLink前面应该是逗号,拜托。“我都不稀罕说你。”

137:天啊!居然如此虐待scanf()

scanf(&m,&n,&t);

难道作者真达到了脱离语言而描述算法的境界?可书的封皮上赫然写着几个大字:C语言描述!同一个函数中,M->row_head[ ]=M->col_head[ ]=NULL;同样也是一个低级错误。

164label和指针混用,不知所云!难道是作者在写Obfuscated C Code

165:神奇的错误!先是while{}后面不该有分号,却多了一个;接着,do{}while()后面应该有分号,却没有!转移了?!抑或是传说中的印刷错误?

186:哪有这样初始化的啊?你是在使用Perl吗?光盘中的此处代码又存在另一个问题,书中代码与光盘中的相差太多!

274search()函数中最后一句居然丢了分号!不可原谅!此书的代码真的“均在Turbo C 2.0 下调试通过”吗?



. 这不是错误,但是不推荐使用

1. 如果要返回int,请明确指出。虽然缺省情况下的确是返回int,但是在未来的C语言中标准中并不见的也是如此。更糟糕的是,书中把不返回任何值的函数也同样定义。此类函数可以在第108-109页中大量见到。

2. return是关键字,不是操作符,没有必要在return后面的表达式上添加圆括号。

3. C99说,main函数的原型最好是以下两者之一:

int main(void){}

int main(int argc, char *argv[]){}

其它虽然也对,但并不保证是可移植的。

4. malloc()成功时返回一个void * 指针,没有必要把一个void * 指针强制转化成其它指针,同样,也没有必要把其它指针强制转化为void *指针。

5. 60polycreate()函数中:scanf(“%d,%d”,&c,&e)是很糟糕的!在Windows上,或许还可以在输入时小心输入逗号来避免出错,但在linux/gcc上,这会导致很奇怪的错误!加逗号纯属画蛇添足!第205210页也有此类情况。