2002 Spring C++ 程式作業一:
資料結構與記憶體配置練習

作業說明:

這學期的作業中, 假設我們替一間 VCD/DVD/Game 及漫畫圖書的出租店設計一套管理系統, 我們希望這套管理系統可以記錄所有店內可供出租的媒體資料, 記錄所有客戶的個人靜態資料, 記錄所有媒體的租借資料、到期資料等等, 記錄所有客戶的帳款資料、預約資料等等動態資料。 我們希望這個管理系統有一個媒體資料登錄與刪除異動的界面, 希望在櫃台的地方有一個可以在客戶想要租借媒體時可以迅速登錄的界面, 希望有一個界面可以每個月整理客戶的帳單以便寄出。

在第一次的作業裡希望大家先複習一下 C 的語法基本的資料結構的設計與運用, 希望大家能夠清楚單元測試的基本方法。 在上述的系統中想要把媒體的相關資料和客戶的相關資料記錄在程式裡的話, 程式中需要有適當的資料結構來存放, 對於這些資料的基本需求如下:

  1. 資料筆數不能設限
  2. 資料需要隨時加入及刪除
  3. 搜尋資料時速度要快
為了簡化這一次的作業, 我們暫時不要考量資料搜尋的速度, 前面兩個要求則希望你製作一個動態配置記憶體的串列來達到。

串列的每一個節點需要依序記錄的欄位內容如下:(以 VCD 為例)

  1. 標題: char *
  2. 創作者: char *
  3. 表演者: char *
  4. 片長: short int
  5. 發行年: short int
  6. 發行月: short int
  7. 發行廠商: char *
  8. 庫存量: short int
  9. 價格: short int

程式需要提供一些文字選單界面, 讓操作的人可以更改串列中每一筆 VCD 的資料如下:

    1) Insert Head
    2) Append Tail
    3) Insert After
    4) Delete Head
    5) Delete Tail
    6) Delete Title
    7) Calculate and Print CRC32 Check Sum
    8) Delete All
    9) Print Title
   10) Print All
   11) Quit
請輸入你的選項 (1-11) ?
上面的這些功能實際上和串列的架構是密不可分的, 最主要是要讓大家的作業能夠很快地通過自動測試而設計的, 當然如果這些界面是要給真證的使用者來用的話, 必須把串列相關的結構隱藏起來, 只能提供類似 "加入" "刪除" "修改" "列印" "尋找" 等等功能。

基本測試資料如下:

1                ; first command, insert head
title 1
artist 1
performer 1
64
1999
10
EMI
1
300
2                ; second command, append tail
title 2
artist 2
performer 2
64
1999
10
EMI
1
300
3                ; third command, insert after
title 1
title 3
artist 3
performer 3
64
1999
10
EMI
1
300
7                ; 7-th command, print check sum, should see [[6e94b237]]
4                ; fourth command, delete head
5                ; fifth command, delete tail 
6                ; sixth command, delete title 
title 3
7                ; 7-th command, print check sum should see [[ffffffff]]
8                ; 8-th command, delete all record
9                ; 9-th command, print a title
title 2
10               ; 10-th command, print all titles
11               : quit the program
測試資料 程式執行後印出之 CRC32 checksum 為 f6d72415
範例程式 [程式執行時會印出更新日期]
發展時的版本
測試方法:list < list02.dat

作業要求:

這個作業中有不少的要求, 基本上都是和要求你設計一個大一點的軟體系統相關的, 請你一定要了解並且逐步完成。

  1. 請用 ANSI C 語法完成, (目的是讓你自己清楚自己目前會的 語法哪些是 ANSI C 的, 哪些是 K&R C 的, 哪些是 C++ 增加的)

  2. 變數、自定資料型態、函式的名稱請使用有意義的英文, 勿隨便縮寫

  3. 請用函式將邏輯上相關的部份獨立起來, 這個程式允許你用單一的檔案製作

  4. 程式編排及列印的格式請遵照上課時說明的要求

  5. 請使用 VC 完成, 並且使用 MFC DLL 中提供的自動記憶體偵測來確定程式沒有未釋放的記憶體。 (此部份功能需要使用 C++ compiler 才能夠完成, 因此檔案的副檔名只能用 .cpp)

  6. 對你所寫的功能請撰寫固定的測試程式, 例如你可以呼叫你自己的 insertAtHead 函式多次, 刪除某些節點, 然後以 assert() 函式檢查串列是否如你所預期的: 例如:

  7. 計算 CRC 32 的檢查碼片段如下 呼叫上面函式時請先準備一個 unsigned long 變數 crc32, 初始化為 0xFFFFFFFFL, 例如: 列印時請以十六進位輸出到螢幕,前後並加方括號如下:

ps:

這個作業有很多的規定, 希望大家一定要符合要求, 相對地很多同學也可能覺得好像沒有什麼可以發揮的地方, 會有這樣子狀況發生的原因, 最主要是因為物件導向的程式製作, 基本上是希望你把撰寫程式當成是工程領域中很單純一個模組的製作, 有很清楚的規格與程式功能的定義, 有很清楚的完成步驟與方法, 寫程式不能是很藝術的東西, 否則沒有辦法讓很多人一起合作來製作比較大的軟體系統, 製作好的軟體系統也沒有辦法持續地修改及維護下去。

如果你實在很難耐住去製作特殊功能的衝動的話, 其實你還是有很多的選擇的, 比方說你可以製作排序的功能, 自己在程式裡加好所有的單元測試, 在交作業的時候特別地說明相關的設計... 不過請特別注意不管你加入什麼東西, 不能不滿足作業基本的要求, 否則自動的測試就沒有辦法通過了。 另外其實單元測試是很不容易做的, 你自己寫的一組函式該怎樣測試才能夠佐證它們是可靠的呢? 這裡每個人的想法會不一樣, 如果你抄別人的話也很容易看得出來。

注意:

  1. gets(buf), scanf("%s",buf), strcpy(dest, src), strcat(dest, src), sprintf(outbuf, "%s", buf) 這些函式都是軟體安全上危險等級極高的函式 (尤其是前兩個直接處理輸入的函式), 操作程式的人很容易讓你的程式出現 Buffer Overflow 的現象, 不管你知不知道怎樣產生 buffer overflow, 如果你不去用它們的話, 駭客就沒有機會可利用。 你可以用 fgets 取代 gets, 用 strncpy 取代 scanf("%s",buf), strcpy, 或是 sprintf(outbuf, "%s", buf), 用 strncat 取代 strcat。

  2. scanf() 函式對於輸入字串中的換行字元不做任何處理, 只把它當成 white space, fgets() 函式則將輸入串流以換行字元斷開, 另外要使用 fflush(stdin) 這種特別的功能之前請完全了解其功能, 否則出現錯誤概不負責。

  3. short int x;
    scanf("%d", &x);
    
    是會產生記憶體存取錯誤的用法, 請小心

  4. 發展時的版本, 包括許多單元測試的程式碼可以用前處理器的指令
    #ifdef NDEBUG
        release version of codes
    #else
        debug version of codes
    #endif
    
    編譯時指定 cl /DNDEBUG list.cpp 則可以產生 release 版本, 所有的 assert() 敘述會自動地跳過去, 如果用 cl list.cpp 編譯則可以產生 debug 版本。

  5. 有同學遇見這樣子的錯誤:
    char *fun1()
    {
        char *ptr, buf[100];
        gets(buf);
        ptr = (char *)malloc(sizeof(buf)+1);
        ptr = buf;
        printf("1: %s\n", ptr);
        return ptr;
    }
    
    void fun2(char *ptr)
    {
        printf("3: %s\n", ptr);
    }
    
    void main()
    {
        char *ptr;
        ptr = fun1();
        printf("2: %s\n", ptr);
        fun2(ptr);
    }
    
    你知道為什麼 printf("1 和 printf("2 都會對, 而 printf("3 會錯嗎? 請注意我的問題在於為什麼 printf("1 和 printf("2 會對?

  6. 要去除記憶體使用上的錯誤, 必須使你自己使用記憶體的模型和程式使用記憶體的模型一致才行, 記憶體使用的錯誤會讓你的程式有不合程式邏輯的錯誤, 例如:
              ...
          int x;
              ...
          x = 10;
              .
              .
              .
          assert(x==10);
    
    假設上面的程式從 x = 10 這個敘述開始 到 assert(x==10) 之間都沒有使用到 x 這個變數也都沒有任何地方間接或是直接 用到 x 這個變數的位址, 你覺得上面的程式一定是對的嗎?

    邏輯上看起來應該不會錯, 但是如果中間的程式或是所呼叫的函式中有記憶體操作的錯誤 (指標的誤用, 未配置足夠的記憶體,字串的拷貝...) 的話, 那正確性就很值得懷疑了。

C++ 程式設計課程 首頁

製作日期: 3/10/2002 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@cs.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 理工學院 資訊科學系