檔案內搜尋字串

簡介

GREP 是 UNIX 作業系統下一個由檔案中搜尋指定字串的工具程式, 讓我們用兩種方法來設計這樣子功能的程式, 你將會學到:

  1. 處理基本的命令列參數

  2. 檔案開啟、字元讀取、與檔案關閉

  3. 字串函式使用

  4. 程式如何記憶比對的狀態 - 狀態圖的使用

  5. 命令列參數 *.* 或是 ???.?pp 的處理

範例執行程式

基本的命令列參數處理

C 程式的進入點是 main() 函式, 作業系統呼叫 main() 函式並將 CPU 的控制權交給以 C 語言撰寫的應用程式, 作業系統在處理操作者的命令, 例如: copy file1.dat file2.dat 時, 通常 copy 是一個可執行的工具程式, file1.dat 及 file2.dat 則是操作者希望交給 copy.exe 這個執行程式去處理的資料, 作業系統的命令列解譯程式於是將 copy.exe 檔案內的程式載入記憶體, 呼叫其中的 main() 函式, 並將 "copy" "file1.dat" 及 "file2.dat" 這三個字串的位址記錄於指標陣列 char *argv[] 內傳入 main() 函式內處理, 在 int argc 參數內記錄 3, main() 函式的參數宣告如下:

以上例而言, 下列敘述

將列印出 我們要撰寫的 grep 程式的操作方式範例如下: 因此我們需要以下列程式觀察一下上面這幾種狀況下程式內究竟看到 argv[] 指標陣列內有什麼樣子的字串?

檔案開啟、字元讀取、與檔案關閉

  1. 檔案開啟

  2. 字元讀取

  3. 檔案結束測試

    EOF 為 stdio 函式庫中定義的常數, 其數值為 -1

  4. 檔案關閉

字串比對方法

假設操作者希望比對的字串是七個字元的 "xstring", 在程式內當然需要準備至少容納八個字元的字元陣列來存放此字串, 另一方面, 檔案內欲比對的資料在程式內則可以有兩種方法來表示:

在程式內保留相同字元數目的暫存區

此暫存區內儲存最後由檔案內讀出的 8 個字元, 並可利用一迴圈比對兩個字串的內容, 在這樣子的前提之下, 如果一次由檔案內讀出多一點的字元, 例如 128 個位元組, 至記憶體內的字元陣列, 也許處理上比較方便, 例如:

注意

  1. 上面這個方法在比對時, 檔案中連續兩段資料之間會有幾個字元 (strlen(cTargetStr)-1) 沒有比對完全, 必須保留下來, 如下:

  2. 上面這種方法如果仔細分析的話, 會覺得有一點浪費, 因為在檔案中的每一個字元都可能被上述兩層的迴圈拿出來比較 strlen(cTargetStr) 這麼多次, 實際上檔案中每個字元應該都只需要和最多兩個字元比對就足夠了, 我們用下面的狀態圖來說明這個方法:

程式如何記錄比對的狀態

以搜尋字串 "xstring" 為例, 我們在檔案內衣個字元一個字元往後比對時, 如果出現 'x' 字元的話, 下一個字元只有兩種狀況是我們需要注意的: 一是 's' 字元, 二是 'x' 字元, 若是 'x' 字元的話, 表示前面一次出現的 'x' 字元不是屬於要搜尋字串的一部分, 現在的這個 'x' 字元則可能是我們要搜尋字串的第一個字元, 若是 's' 字元的話, 再下一個字元我們感興趣的是 't' 字元或是 'x' 字元, 以下類推, 我們可以用一個狀態圖來表示:

狀態 (States):

上圖中有八個狀態, 分別代表:

  1. NULL 代表到目前為止看都沒有看到一個相關的字元,開始狀態

  2. 前一個字元是 x

  3. 前兩個字元是 xs

  4. 前三個字元是 xst

  5. 前四個字元是 xstr

  6. 前五個字元是 xstri

  7. 前六個字元是 xstrin

  8. 前七個字元是 xstring,結束狀態, 也就是已經找到該字串了。

狀態變換 (State Transitions):

程式運作的狀態會根據檔案下一個字元的內容來改變, 假設目前狀態為 xst, 表示前三個字元分別為 t、s、及 x, 更前面的字元是什麼就不得而知了, (這當然也說明了為什麼這種狀態圖成為有限狀態的狀態圖了。) 此時檔案中下一個字元可以是任何字元, 其中我們最有興趣的字元是 'r', 若是檔案中的下一個字元真的是 'r' 的話, 則狀態變為 xstr, 愈來愈接近比對成功之路了; 若檔案中的下一個字元不是 'r' 的話, 表示辛辛苦苦才等到的 xst 部分字串又沒用了; 若是檔案中的下一個字元是 'x' 的話, 那還差強人意, 至少可能是另一個開始的機會, 此時狀態變為 x, 現在如果在檔案中出現任何 'r' 或是 'x' 之外的字元的話, 狀態完全重設為 NULL, 一切過去全部一筆勾消, 重新再來。

製作依據狀態圖運作的 GREP 程式

如何以程式表達此狀態圖及狀態的變化呢?

注意

命令列參數 *.* 或是 ???.?pp 的處理

以下面這段程式 testArg 來說, 如果你用 testArg *.* 這個命令來測試的話, 在不同的 shell 環境下會有不同的結果: 例如在 UNIX csh 下, *.* 會先被轉換為所有在此目錄下的檔名, 以空格分隔, 直接以 argc, argv 的形式傳入程式中, 但是在 DOS 下則是完全不處理, 直接傳入字串 *.*, 因此必須在程式中處理。

讓我們借助於 VC 中 io.h 函式庫中的 _findfirst(), _findnext() 函式、 以及 struct _finddata_t 結構來處理 * 與 ? 字元, 例如:

請自行嘗試此函式庫中其他的函式。

另外一個處理某一資料夾中檔案的函式庫 dirent.h 則可以在 UNIX 環境下使用, 這個函式庫中包括 opendir, closedir, readdir, 及 rewinddir 等等函式, 請參考 MSDN 線上說明之範例。

程式設計課程 首頁

製作日期: 09/13/2008 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 電機資訊學院 資訊工程學系 Lagoon