求單詞個數的三種算法分析

陳 娜 ，付 沛

1.武漢軟件工程職業學院軟件系，湖北武漢 430205

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

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

圖1

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

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

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

[2]王路群主編.數據結構中國水利水電出版社，2007，2.