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

陳 娜 ，付 沛

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

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

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

圖1

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

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

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

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