Lab 1-2: Automatic Verification Environment:
assert() statement

請下載 statisticsAndSort.exe 程式, 這個程式基本上讀取一個資料檔案raw1.dat, 計算檔案內所有資料的平均值, 各種資料出現的中間值, 以及出現頻率最高的數值。 在 Lab 1-1 中我們完成了一個分開在多個 .cpp 檔案裡的 程式, 但是這個程式基本上還有很多的假設與很多的漏洞。

請下載資料檔案raw2.dat 以及 raw3.dat 執行, 你會發現一些問題。 例如輸入 raw2.dat 時好像資料量太多了, 輸入 raw3.dat 時有一些資料好像超過範圍 (1-9), 或是輸入一個不存在的檔案名稱 (例如 raw4.dat) 時程式都應該會出問題。 請依照下列的步驟在程式適當的地方加入 assert() 的敘述來確保我們在撰寫程式時的一些假設。

     gets(filename);
     
     fp = fopen(filename, "rt");
     fscanf(fp, "%d", dataSize);

int isDecending(int a[], int size)
{
    int i;
    for (i=1; i<size; i++)
        if (a[i]>a[i-1])
    	    return 0;
    return 1;
}

• 測試各種不同的資料組合, 你的排序程式應該都可以正確運作, 對自己實作的演算法應該可以很有信心, 演算法一開始也許沒有考慮許多特殊的資料組合, 但是在運作一段時間之後應該都可以慢慢地修補完全, 此時你也常需要把這些特殊的資料組合寫成 assert() 敘述
  
• 如果有一天你的排序程式效率不敷使用, 你想要修改程式的時候, 你可以放心地去修改, 然後自動地透過先前加入的 assert() 敘述驗證

#include <stdlib.h>
int compare(const void *elem1, const void *elem2);

void main()
{
    int a[] = {5, 3, 4, 1, 2};
    int numElements = 5;

    qsort(a, numElements, sizeof(int), compare);
    for (i=0; i<numElements; i++)
        printf("%d ", a[i]);
    printf("\n");
}

int compare(const void *elem1, const void *elem2)
{
    if (*(int *)elem1 < *(int *)elem2)
        return -1;
    else if (*(int *)elem1 == *(int *)elem2)
        return 0;
    else
        return 1;
}

或是簡化一下
int compare(const void *elem1, const void *elem2)
{
    return *(int *)elem1  - *(int *)elem2;
}

1. 需要排序的所有資料要放在塊連續的記憶體中
   
2. 每一筆資料的長度都是固定的
   
3. 需要寫一個函式來比對兩筆資料的大小

這才是你在練習過以後應該要知道的東西 (你花一些時間練習好英文打字以後, 這種程式片段需要直接思考, 直接寫出來, 不需要邊看編寫, 我們也會慢慢地把關鍵程式碼從網頁中移除)

也許你從來沒有看過上面範例的用法, 或是覺得這樣子的 C 程式的語法上有點生疏, 分成三部份解釋一下:

1. 指標型態的強制轉換
   
   int x;
   int *ptr = &x;
   
   上面的兩列程式中, 變數 ptr 裡面放的是整數變數 x 的記憶體位址 &x
   
   下面的敘述 *ptr + 1 因為 ptr 存放的是整數變數的記憶體位址, 所以編譯器知道 *ptr 需要由那個位址拿出連續的四個位元組, 然後用二的補數(整數)來解釋那四個位元組, 最後執行整數的加法來加 1
   
   如果程式改成 *(double *)ptr + 1.0, ptr 前面加上 (double *) 使得編譯器認為 (double *)ptr 是一個 double 變數的記憶體位址, *(double *)ptr 則要求由那個位址取出連續的八個位元組, 以 IEEE 754 浮點數格式解釋那八個位元組, 然後執行浮點數的加法來加上 1.0;
   
   請注意, (double *)ptr 這個型態的強制轉換敘述其實沒有更改位址的數值, 但是改變了後續的「間接資料存取運算子」 * 的運作方法
   
   
2. qsort 的第四個參數是一個函式指標變數 (請注意一個函式的參數如果是變數的話, 呼叫這個函式的時候可以藉由這個參數來調整函式處理的資料內容, 如果是一個函式指標變數的話, 可以直接調整函式的處理方法)
   
   

   void qsort(void* base, size_t num, size_t size, 
              int (*compare)(const void*,const void*));

   
   在運用 qsort 的時候需要撰寫函式 compare 來協助 qsort 分辨任意兩筆資料的大小 (回傳負值代表第一比資料比較小, 回傳 0 代表相等, 回傳正值代表第二筆資料比較小), qxort 在執行的過程中會不斷地呼叫這個函式來判斷兩筆資料的大小
   
   
3. 為什麼不直接寫一個比較兩個整數變數大小的函式 int compare(int *, int *) 或是 int compare(int, int) 呢?
   
   請注意這個 compare() 函式不是給你自己的程式使用的, 是給 qsort() 使用的, qsort() 是 stdlib 函式庫裡面別人在許多年前幫你寫好的一個工具，在設計的時候當然完全不知道你想用它來排序的每一筆資料到底是 float, int, double 還是其它的型態, 也不曉得每一筆資料用了幾個位元組, 所以只能夠運用 void *element1, void *element2 這兩個沒有特別型態的記憶體位址變數來傳入想要比對的兩筆資料 (qsort 演算法可以排序的不限於整數型態的資料), 來呼叫 compare 函式
   
   我們在運用 qsort 時當然知道是要比對整數還是浮點數還是其它的型態, 但是 compare 函式需要根據 qsort 的要求來寫, 也就是第四個參數是上面的 int (*compare)(const void *, const void *) 的函式指標
   
   那麼在撰寫 compare 這個函式內容的時候, 我們知道要比對的兩筆資料是什麼型態, 所以就可以強制由 const void * 型態轉換為你知道的型態, 例如上例的 int *, 然後再進行比對
   
   這是一個很有趣的程式重用機制, 其實就是一種多型的機制, qsort() 函式裡面在處理資料的時候其實完全不管實際想要排序的資料型態是什麼, 只知道每一個單位所佔用的記憶體是一樣的, 只知道運用 qsort 的人會提供給他判斷兩個單位誰大誰小的函式 compare() 就夠了, 在 C 程式裡面這種多型的運用不算太多, 但是到這學期後面你會看到 C++ 裡面的最常運用的多型機制就長這個樣子

qsort 的各種應用方法 (視訊)

• 求出 median 值時是否有一半以上的資料大於等於它, 有一半以下的資料小於等於它,
• 求出 freq[] 陣列後是否總和等於所有資料的總數
• 求出 mode 值以後其數值是否大於所有其它資料值
• ...

請注意, assert() 是程式開發人員用的工具, 在程式開發完成交給使用者的時候, 程式裡不應該有這樣子的敘述...

難道好不容易加進去的東西還要一列一列拿掉嗎? 不不不!!! 用下面的敘述可以讓某一個檔案裡所有的 assert() 敘述都不發生作用,

#define NDEBUG

需要在每一個檔案的開頭(#include <assert.h> 之前)都定義一次。 另外一種方法是使用編譯器的旗標來控制, 在選單中選取

專案 / lab1-2 屬性 / 組態屬性 / C/C++ / 前置處理器 => 在前置處理器定義最後加入

; NDEBUG

"建置 / 重建方案" 即可 (只需加入一次, 對所有的檔案都有效)

assert() 是 ANSI C 和 ISO C++ 都有提供的巨集

後續大家也許會嘗試運用不同的單元測試工具, 例如 CppUnit, Google Test, NUnit, 或是 MS 的 CppUnitTestFramework, 這些環境下都有自己定義的 assert 巨集, 例如 CppUnit 的 CPP_ASSERT_XXXXX 巨集