[C/C++] Word Separating

• Word Separating

word separating是筆者我在兩年前製作程式語言講義裡的其中一個範例，其中的演算規則不難，主要是善用字串處理，只是整個程式使用了linked-list的結構來撰寫，所以程式碼會長一點。

Download:sepWord.c

雖然這只是一個不到兩百行的小程式，但是其中還有一些重要的環節要介紹一下。

函式的原型如下：

output():將分離好的單字儲存到文字檔裡。

delDuplicate():刪除重複以及長度不及的單字。

initNode():初始化linked-list的node。

sort():使用改良後的bubble sort來排序linked-list。

separate():整個程式的核心函式，裡面實做如何分離單字。

freeList():清除linked-list。

定義了一個叫做word的structue，裡面包含了兩個變數，keyword是用來儲存單字用的，而next則是結構體指標，指向word這個結構體型態。


在main()程式碼裡有一行程式（如下圖），這個宣告是特別用在head,tail這兩個word結構體的變數初始化用的，為了要讓後面的sort程式能夠正常排序且不會調動到head,tail這兩個結構體裡的keyword(也就是不要讓任何單字跟這兩個變數內的keyword做交換，否則我們想要留下的單字可能會被放在tail的keyword裡。)這只是筆者我比較習慣的處理方式，處理這類的方法還可以在排序的演算法其他函式上動手腳。


下圖是改良後的bubble sort，但是有別於一般的bubble sort，這個版本不會有任何for loop，因為linked-list本身就是以指標的型態做串連，所以沒有index可以使用，所以這個時候要善用head,tail這兩個node。（如果看不懂這個sort怎麼寫，姑且可以先跳過。）

接下來的就是整個程式的核心，separate()，程式碼不長，佔用了30行而已，

在separate()函式一開始就宣告了一個叫做token的陣列，裡面已經預先定義好要去除哪些字元，但是其中有兩個數字可能會讓讀者困惑，那就是10跟13，這兩個數字轉換成ascii之後分別代表著new line, carriage return，其中以10最需要被過濾掉，否則分離後會有一堆不需要的空白字元。

宣告完token之後，還要做一些資訊的讀取，例如程式碼157~159是在讀取檔案的byte數，162~163是在動態宣告一個char 陣列，並一次將所有要處理的文字讀取到buffer，這樣的作法會比筆者原先以一個一個字元讀取的方法來得更有效率。



終於我們要進入最核心的演算部份，我使用了兩個迴圈，外部迴圈（程式碼171）是一直做到整個buffer的最後一個字元，而內部迴圈（程式碼173）是不斷對每個字元去比對我們設定的token，如果比對成功（程式碼174），會接著去比對是否是空白字元或者是跳行字元（程式碼175），如果很幸運的又成功了，這時候我們可以確定程式已經讀到了一個單字，我們要為這個單字做收尾的工作（程式碼176），並且再新增一個node(程式碼178)給下一個單字儲存使用，只是這一個過程式linked-list的型態，所以程式碼177~180之間我們要將現有的單字跟新的node串接起來，否則list 就斷掉了。

而程式碼183~186是一個特殊處理的環節，程式碼183是在判斷是否已經處理到最後一個字元了，如果是個化同樣也要做收尾的動作，比且跳開這個內部while loop，如果還有字元要做處理，就遞增buffIndex的值，並且將tokenIndex給歸零（程式碼187），如此一來我們就可以繼續從程式碼173繼續做判斷，而不需要離開內部迴圈在繞一大圈進來。

如果目前要比對的字元跟我們設定好的token字元不符合（例如'a'），那程式碼就會執行到190行，並將'a'這個字元儲存起來，繼續再往下一個字元做判斷，不斷地重複上述的動作直到所有buffer裡的字元都已經分離完畢程式碼就會執行到192行做最後的收尾動作，也許這個時候你會有疑問為什麼程式碼176跟184都已經做了收尾的動作，程式碼192為什麼還要再寫一遍，原因是因為我們文字的結尾很有可能不是要過濾的符號，例如來源文件檔裡就只有一句話"this is a simple program"，他最後一個字元是m完全不會進入到程式碼174裡的判斷，所以這個時候我們還要為這種情況額外收尾。

依照所要分析的文字結構不同，視情況去決定碰到什麼字元要做收尾並且產生新node的動作。


所以整個文字分離程式概念雖簡單，但是要仔細去設想各種狀況，否則一有缺失就會出錯。

• Demo

  測試用的短文（article.txt），特別加了許多符號來將句子給複雜化



執行使用的指令：

• ./sepWord article.txt sepWords.txt 5

其中5代表著小於5個字母的單字都刪除掉。


輸出的結果（sepWords.txt）



輸出結果很理想的把我們所要的單字給分離出來，並且依造大小寫與字母給排序好，重複的單字以及不要的字元也已經消除。

本程式已由筆者重新校正過，我想程式應該是不會有錯誤了，除非讀者您使用了一些違反我程式所設定的token字元結構才有可能分析出不正常的單字。