求單詞個(gè)數(shù)的三種算法分析

陳 娜 ，付 沛

1.武漢軟件工程職業(yè)學(xué)院軟件系，湖北武漢 430205

2.中冶南方（武漢）威仕軟件公司，湖北武漢 430223

1）由圖1圓圈處可知，當(dāng)遍歷字符串時(shí)，當(dāng)滿(mǎn)足條件前一個(gè)字符為空格，后一個(gè)字符不為空，就可以認(rèn)定為一個(gè)單詞的開(kāi)始，單詞個(gè)數(shù)可以加1（特殊情況需要考慮：如果字符串的首字符為空格，則計(jì)算出來(lái)的字符串的單詞個(gè)數(shù)是正確的；如果首字符不為空，則字符串包含的單詞的總個(gè)數(shù)需要加1，細(xì)節(jié)見(jiàn)圖1的菱形框處）。代碼如下。這種算法是找每個(gè)單詞的頭，也可以改變一下思維方式再派生出另外一種寫(xiě)法：找每個(gè)單詞的尾。當(dāng)滿(mǎn)足條件前一個(gè)字符不為空，后一個(gè)字符為空，就可以認(rèn)定為一個(gè)單詞的結(jié)束，單詞個(gè)數(shù)可以加1（特殊情況需要考慮：如果字符串的末字符為空格，則計(jì)算出來(lái)的字符串的單詞個(gè)數(shù)是正確的；如果末字符不為空，則字符串包含的單詞的總個(gè)數(shù)需要加1）。

圖1

2）由圖1可知，遍歷字符串時(shí)單詞個(gè)數(shù)是否正確取決于首字符，如果首字符不為空，單詞個(gè)數(shù)需要加1，可以不管字符串首字符是否為空，默認(rèn)給字符串開(kāi)始加一個(gè)空格，引入一個(gè)變量c來(lái)保存前一個(gè)位置的字符，讓它的初始值為空格，相當(dāng)于默認(rèn)所有的字符串的首字符都為空。這樣一來(lái)遍歷數(shù)組后count的值肯定是單詞個(gè)數(shù)。代碼如下：

3）遍歷數(shù)組，如果第一個(gè)字符遇見(jiàn)非空格，說(shuō)明這是一個(gè)單詞的開(kāi)頭 ，count值加 1，通過(guò)語(yǔ)句“while（i＜ch.length && ch[i]!=' '）i++;”找到下一個(gè)空格的下標(biāo)i，如果遇見(jiàn)空格，什么事情都不做，繼續(xù)查看下一個(gè)字符（特別是碰到連續(xù)的空格，語(yǔ)句“if（ch[i]==' '）continue;”用來(lái)跳過(guò)連續(xù)的空格，直到找到一個(gè)非空格為止）。通過(guò)執(zhí)行循環(huán)遍歷數(shù)組，count的值就是單詞的個(gè)數(shù)。其中while語(yǔ)句的條件中使用短路與“&&”很有技巧，使用了短路運(yùn)算符，一旦字符串的最后一個(gè)字符不是空格，執(zhí)行i++后i= ch.length時(shí)條件“i＜ch.length”不成立時(shí)直接將第二個(gè)條件“ch[i]!=' '”短路，否則如果使用“&”不短路第二個(gè)條件，會(huì)產(chǎn)生數(shù)組越界異常。代碼如下：

[1]王路群主編.Java高級(jí)程序設(shè)計(jì)中國(guó)水利水電出版社，2006，8.

[2]王路群主編.數(shù)據(jù)結(jié)構(gòu)中國(guó)水利水電出版社，2007，2.