當佇列滿溢的解決範例

除非您寫的程式是個用過即棄的臨時性工具， 否則您應該要設法使這個程式可長久地工作。 此時，您最好要注意它是否足夠強韌 (robust)。 所謂強韌，就是不容易因為遇到一些很少發生的例外狀況而失效。 所謂失效，包括了造成當機、進入無窮迴圈、產生錯誤輸出，等等情況。 我們並沒有一套固定的方法，可以使您提高程式的強韌性。 這就好像，我們並沒有一套方法，可以使您知道如何證明任何數學命題。 因此，有些人，例如 Knuth 教授，就認為程式設計 (computer programming) 是一種藝術 (ART)、而不是科學 （SCIENCE) 也不是技術 (TECHNOLOGY)。

順便一提，凡是用過即棄的臨時性小工具，大概都不值得用 C 來寫。 像這種程式，通常是以腳本語言 (scripting language) 來寫。 我們不在這份教材中談它們。

使得程式強韌的主要前提，就是要邏輯完備。設計者的考慮，必須滴水不漏。 您要儘可能地預測各種可能出錯的狀況，並且做出有效的防範。 最常見的防範，就是在使用手冊中告訴別人，不要這樣、不要那樣， 然後就把維持程式之運行於不墜的責任，轉嫁個使用者了。

舉一個例子，像 getline() 函式， 它不負責佇列的宣告和長度，它只負責在它自己的工作範圍內， 絕不會漏掉任何字元，也不會讓佇列滿溢。 在這個意義下，getline() 應該算是強韌的。 它把問題留給原函式去負責。 例如，我們現在若要寫一個程式，列出輸入檔案最長的一列之列號 (line number、 從 1 算起) 和那一列的字元數 (不含 LF)。 如果有兩列同長，則以最先出現的為準。 因為終端機的寬度大多是 80 格，所以大部分文字檔的列長都不會超過 80 字元。 因此，為了節省記憶體，我們將佇列長度設定為 81。 以下是第一個版本。

#include <stdio.h>
#define BUFSIZE 81

int getline(char[], int);

/* maxline.c 第一版本 */
main() {
    char buf[BUFSIZE];
    int n, line=0, max=0, maxline=0;
    
    while ((n = getline(buf, BUFSIZE)) > 0) {
        ++line;
        if (n > max) {
            max = n;
            maxline = line;
        }    
    }
    printf("%d:%6d\n", maxline, max-1); /* 扣掉 LF 不算，所以 max-1 */
    return 0;
}

getline(char s[], int N) {
    int c, i;

    for (i=0; i<N-1 && (c=getchar()) != EOF && c != '\n'; ++i)
        s[i] = c;
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';
    return i;
}

這第一版本有兩個問題。第一個問題比較小：如果輸入空檔案 (連一個 LF 也沒有)，會輸出

0:    -1

0:     0

第二個問題就比較嚴重了。如果輸入檔案中的某一列有 81 個字元， 這一列會被拆成兩次讀進佇列。第一次讀入前 80 個字元， 第二次讀入最後一個字元和 LF。 如果這是最長的一列，則 max 得到了 80 卻不是 81。 因此，這個程式的輸出將是錯誤的。

要怎樣得知佇列中的確是一列文字呢？ 可以檢查 buf[n-1] 是否為 LF。 如果是，那就是一列；否則表示出現了超過 buffer size 的列，需要另外處理。 以下是修改後的程式，前述兩個問題都得以解決。

#include <stdio.h>
#define BUFSIZE 81

int getline(char[], int);

/* 找出最長的一列 (maxline.c) */
main() {
    char buf[BUFSIZE];
    int n, line=0, max=0, maxline=0, len=0;
    
    while ((n = getline(buf, BUFSIZE)) > 0) {    
        len += n;
        if (buf[n-1]=='\n') {     /* 檢查是否為一列的結束 */
	    ++line;               /* 如果是，將列數 +1 並檢查是否要更新 max */
	    if (--len > max) { /* LF 不算，所以 -- */
		max = len;
		maxline = line;
	    }    
            len = 0;              /* 將一列的長度歸零 */
        }
    }
    printf("%d:%6d\n", maxline, max);
    return 0;
}

getline(char s[], int N) {
    int c, i;

    for (i=0; i<N-1 && (c=getchar()) != EOF && c != '\n'; ++i)
        s[i] = c;
    if (c == '\n') {
        s[i] = c;
        ++i;
    }
    s[i] = '\0';
    return i;
}

習題

1. 寫一個程式，將輸入檔案中的所有跳格 (HT) 都換成適當多個空格 (SP)， 使得它輸出到 stdout 的時候，看起來是一樣的。 換句話說，就是要將跳格展開成空格。 假設每個跳格字元表示要跳到下一個定格，而第一個定格的位置是 0， 此後的定格位置都是 8 的倍數。

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]

注意：此處所有文件均為原著，個別的版權宣告日後會一一公布， 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片，以免觸犯著作權法。

Created: Apr 21, 2000
Last Revised: Apr 22, 2000
© Copyright 2000 Wei-Chang Shann 單維彰

• Back to the home page of Wei-Chang Shann.
• Connect to the home page of Department of Mathematics, National Central University, Taiwan.