【樣本】

　　　　——陳良喬 ，《C程序設(shè)計(jì)伴侶》，人民郵電出版社，2012年10月，p241~242

【評析】

　　這段代碼的基本能算及格。在鏈表中查找，無非是從頭到尾一個(gè)一個(gè)的比較。

　　代碼中的node是一個(gè)多余的變量。寫鏈表操作代碼時(shí)很多人都有這種惡習(xí)。實(shí)際上對于鏈表的操作者來說，由于鏈表是一種遞歸結(jié)構(gòu)，所以只要是單調(diào)的從前到后的操作，任何一個(gè)結(jié)點(diǎn)的next成員都可以視為一個(gè)head。除非在操作過程中需要“回頭”，沒有任何必要保留初始的head值。

　　此外，代碼中的break語句不如改成return node;。最后一句的return node;不如寫成return NULL;。這樣代碼的意義更加明確。?

student* find(student* node,char* key) {while( node != NULL ){if(strcmp( node->name , key )==0){return node ;}node = node->nex t;}return NULL ; }

?

?【樣本】

??　　　——陳良喬 ，《C程序設(shè)計(jì)伴侶》，人民郵電出版社，2012年10月，p242

【評析】

　　這段議論實(shí)在能把人雷得外焦里嫩。順序查找效率確實(shí)不算高，但對于鏈表來說實(shí)在是無奈之舉，因?yàn)檫@是鏈表本身的結(jié)構(gòu)特性所決定的，除此之外別無他法也是無可奈何的事情。二分查找效率確實(shí)不錯(cuò)，但是那是有前提條件的，第一數(shù)據(jù)要有序，第二通常只能用于數(shù)組，因?yàn)閿?shù)組的中間元素可以直接訪問。但是對于鏈表來說，由于只能順序訪問各個(gè)結(jié)點(diǎn)而且根本無法回頭，所以尋找鏈表的終點(diǎn)幾乎是一件和順序查找同樣費(fèi)勁的事情，這還沒算上為鏈表排序的巨大成本。所以用二分法對鏈表查找就好像是說，剃須刀刮胡子有些慢，買把鋒利的王麻子菜刀刮胡子會更有效。
下面就欣賞一下如何用菜刀刮胡子。

【樣本】

?

?　　　——陳良喬 ，《C程序設(shè)計(jì)伴侶》，人民郵電出版社，2012年10月，p244

【評析】

　　首先這里的head=sort(head.cmpname);的成本比順序查找還要高，因?yàn)槊芭菖判蛐枰容^的次數(shù)是N平方量級的，而順序查找需要比較的次數(shù)是N的一次方量級的。
　　其次這里的tail=gettail(head);找到鏈表的結(jié)尾同樣需要比較N次。鏈表的尾巴一向是深藏不露的，為揪出鏈表的尾巴而專門寫了一個(gè)函數(shù)，歷史上這還是首次。

　　再看一下midfind()函數(shù)：

【樣本】

?　　　——陳良喬 ，《C程序設(shè)計(jì)伴侶》，人民郵電出版社，2012年10月，p243
【評析】

　　這里明顯有個(gè)漏洞，就是當(dāng)head、tail都為NULL時(shí)，亦即鏈表為空時(shí)，代碼是錯(cuò)誤的，程序很可能因此而崩潰。

　　二分法的關(guān)鍵在于確定中間結(jié)點(diǎn)，這里的student* mid =getmid(head,tail);又是如何得到的呢？再來看一下getmid()函數(shù)：

【樣本】

　　　——陳良喬 ，《C程序設(shè)計(jì)伴侶》，人民郵電出版社，2012年10月，p242~243

?【評析】

　　天哪！先從頭走到尾，數(shù)出鏈表一共有多少個(gè)結(jié)點(diǎn)，然后再從頭走到中間，一共需要移動3/2N次。問題在于這樣的過程不是一回而是多次。
　　通俗地講一下。假如有一隊(duì)人，你要從中找一個(gè)人，你本可以從前走到隊(duì)尾挨個(gè)問一下。但是這里的樣本代碼卻嫌這種方法太慢。他“采用了一種更加有效的查找算法”：首先，用兩兩交換的辦法讓隊(duì)伍排好隊(duì)（注意這本身就比從前走到尾費(fèi)事、費(fèi)時(shí)）；然后從開頭走到隊(duì)尾數(shù)一共有多少人；然后再按照人數(shù)從開頭走到隊(duì)伍中間，了解一下要找的人在前面還是在后面；如果在前面就再從前走到中間數(shù)人數(shù)然后再從前面走到隊(duì)伍前部的中間……
　　試問，天下還有比這更愚蠢的“更加有效的查找算法”嗎？

【重構(gòu)】

　　這次還是免了吧。用二分法對鏈表查找，俺實(shí)在丟不起那人。

總結(jié)

以上是生活随笔為你收集整理的垃圾代码评析——关于《C程序设计伴侣》9.4——链表（四）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。