1062 2B Quiz#1: 稀疏矩陣 (Sparse Matrix) 類別設計

 
C++ 實習測試: 稀疏矩陣 (Sparse Matrix) 類別設計
時間: 110 分鐘 (13:10-15:00, 15:00 上傳時間截止)
 

如上圖,概念上稀疏矩陣是一個很大的矩陣 (很多列、很多行) 但是裡面絕大部份數值都是 0

  • 例如一個 10001000 行的整數矩陣,如果直接用一個二維陣列來表示的話,需要 1000*1000*4 = 4000000 個位元組,如果裡面只有 500 個不為 0 的數字,其它都是 0,基本上應該只需要 500*4 = 2000 個位元組 就足夠存放這個矩陣裡的所有資料,但是我們卻多紀錄了 999500 個 0,多用了 3998000 個位元組 的空間,這些空間也許是記憶體、也許是硬碟、也許是網路頻寬,以現在的技術來說,多用一點硬碟和頻寬也許比較不是問題了,但是記憶體還是比較不能浪費的東西,值得用比節儉的方式來紀錄一個稀疏矩陣

  • 以上圖的矩陣為例,我們可以只存放那 7 個非 0 的元素 {3,1,1,3,4,-2,2} (但是附帶地也需要紀錄每一個元素的行列位置),如下圖:

    這樣子可以少用很多記憶體,當然這樣子存放一個矩陣也是有缺點的,最明顯的就是矩陣的運算 (轉置、加法、乘法、...) 以及輸出/輸入,都變得比較麻煩了

  • 像前面的例子裡如果一個稀疏矩陣裡面非 0 元素的個數比列數還多的話,我們還可以如下圖右更進一步縮減一點存放資料的空間 (例如上圖中 7 個元素的「列號」{0, 0, 1, 1, 1, 2, 2} 可以看到不少重複的資料),下圖右側使用三個陣列 IA, JA, A 來存放一個稀疏矩陣裡面的資料,其中 IA 陣列只存放左圖中圈圈裡面的數字 {0, 2, 5, 7},代表稀疏矩陣的第 0 列是由 A[0] 開始,第 1 列是由 A[2] 開始, 第 2 列是由 A[5] 開始,最後一列的最後一個元素是 A[6] = A[7-1],所以如果稀疏矩陣有 M 列,N 行,IA 這個陣列固定有 M+1 個元素,這個表示方法我們稱它為 CSR (Compressed Sparse Row 或是 Yale 的表示方法)

  • 下面的 C 程式裡用結構 struct CSR 來表示一個稀疏矩陣
    struct CSR {
        int M;   // number of rows (有幾列)
        int N;   // number of columns (有幾行)
        int NNZ; // Number of Non-Zero elements (有幾個非 0 的數值)
        int *A;  // 動態配置的陣列依序紀錄非 0 元素的數值
        int *IA; // 每一列的起始元素位置
        int *JA; // 每一個非 0 元素的行號
    };
    其中動態配置的整數陣列 A 和陣列 JA 各有 NNZ 個元素,整數陣列 IA 有 M+1 個元素

  • 下一段的 C 程式裡,由鍵盤讀入上圖的稀疏矩陣範例,第一列有三個整數,分別代表稀疏矩陣的總列數 M, 總行數 N, 以及非 0 元素的個數 NNZ,接下去有 NNZ 列的資料分別代表稀疏矩陣中的 NNZ 個元素,每一列的資料包括 數值
    3 5 7
    0 1 3
    0 3 1
    1 0 1
    1 2 3
    1 3 4
    2 2 -2


  • 目前程式裡面主要有四個函式, main, printMatrixCSR, transposeMatrix, 和 multiplyMatrix, 其中 main 裡面

    1. 讀取兩個 M N 行 的矩陣 A 和矩陣 B
    2. 呼叫 printMatrixCSR 函式直接列印這兩個矩陣的內部表示資料
    3. 呼叫 transposeMatrix 函式計算 B 的轉置矩陣 BT
    4. 呼叫 multiplyMatrix 函式計算矩陣乘積 A BT
    5. 呼叫 printMatrixCSR 列印 A BT
    6. 呼叫 transposeMatrix 函式計算 A 的轉置矩陣 AT
    7. 呼叫 multiplyMatrix 函式計算矩陣乘積 AT B
    8. 呼叫 printMatrixCSR 列印 AT
    B

    其中 multiplyMatrix 函式將 M x N 的矩陣乘上 N x L 的矩陣,得到一個 M x L 的矩陣,演算法基本上做了 M * L 次「合併兩個數列 (類似 merge sort 裡面的數列合併)」的動作,細節你需要回憶一下先前的資料結構和演算法,不過今天要求你寫的部份應該不需要知道乘法演算法的細節 (除非你忙中有錯把對的程式改出問題來了!!)

就是下面這個 C 程式了 (希望你沒有什麼程式恐懼症, 它看起來有點討厭應該是實作比較有效率的資料結構的關係)

#include <stdio.h>
#include <malloc.h> // malloc(), free()
#include <string.h> // memcpy()

struct CSR
{
    int M;   // number of rows
    int N;   // number of columns
    int NNZ; // Number of Non-Zero elements
    int *A;
    int *IA;
    int *JA;
};

void printMatrixCSR(struct CSR matrix);
void transposeMatrix(const struct CSR A, struct CSR *B);
void multiplyMatrix(const struct CSR A, const struct CSR B, struct CSR *C);

int main()
{
    int i, row, prevRow;
    struct CSR A={0}, At={0}, B={0}, Bt={0}, C={0};

    scanf("%d%d%d", &(A.M), &(A.N), &(A.NNZ));
    A.A = (int *) malloc(A.NNZ*sizeof(int));
    A.IA = (int *) malloc((A.M+1)*sizeof(int));
    A.JA = (int *) malloc(A.NNZ*sizeof(int));
    for (prevRow=-1,i=0; i<A.NNZ; i++)
    {
        scanf("%d%d%d", &row, &(A.JA[i]), &(A.A[i]));
        if (row!=prevRow) 
        {
            A.IA[row] = i;
            while (++prevRow<row) 
                A.IA[prevRow] = A.IA[row];
        }
    }
    A.IA[A.M] = A.NNZ;

    scanf("%d%d%d", &(B.M), &(B.N), &(B.NNZ));
    B.A = (int *) malloc(B.NNZ*sizeof(int));
    B.IA = (int *) malloc((B.M+1)*sizeof(int));
    B.JA = (int *) malloc(B.NNZ*sizeof(int));
    for (prevRow=-1,i=0; i<B.NNZ; i++)
    {
        scanf("%d%d%d", &row, &(B.JA[i]), &(B.A[i]));
        if (row!=prevRow) 
        {
            B.IA[row] = i;
            while (++prevRow<row) 
                B.IA[prevRow] = B.IA[row];
        }
    }
    B.IA[B.M] = B.NNZ;

    if ((A.M != B.M)||(A.N != B.N))
    {
        printf("Matrix A and B are not of the same dimension!\n");
        return 1;
    }

    printf("\n");
    printf("Matrix A:\n");
    printMatrixCSR(A);

    printf("Matrix B:\n");
    printMatrixCSR(B);

    transposeMatrix(B, &Bt);
    printf("Transpose Matrix B:\n");
    printMatrixCSR(Bt);

    multiplyMatrix(A, Bt, &C);

    printf("Matrix A * Matrix B':\n");
    printMatrixCSR(C);

    transposeMatrix(A, &At);
    printf("Transpose Matrix A:\n");
    printMatrixCSR(At);

    multiplyMatrix(At, B, &C);

    printf("Matrix A' * Matrix B:\n");
    printMatrixCSR(C);

    if (A.A) free(A.A), free(A.IA), free(A.JA);
    if (At.A) free(At.A), free(At.IA), free(At.JA);
    if (B.A) free(B.A), free(B.IA), free(B.JA);
    if (Bt.A) free(Bt.A), free(Bt.IA), free(Bt.JA);
    if (C.A) free(C.A), free(C.IA), free(C.JA);

    getchar();getchar();
    return 0;
}

void printMatrixCSR(struct CSR matrix)
{
    int i, iRow=0;
    printf("%d * %d matrix with %d non-zero item:\n",
           matrix.M, matrix.N, matrix.NNZ);
    printf("A = ");
    for (i=0; i<matrix.NNZ; i++)
        printf("%d ", matrix.A[i]);
    printf("\nIA = ");
    for (i=0; i<=matrix.M; i++)
        printf("%d ", matrix.IA[i]);
    printf("\nJA = ");
    for (i=0; i<matrix.NNZ; i++)
        printf("%d ", matrix.JA[i]);
    printf("\n====================\n");
}

void transposeMatrix(const struct CSR A, struct CSR *B)
{
    int i, iB=0, row, *index;

    B->M = A.N, B->N = A.M, B->NNZ = A.NNZ;

    if (B->A) free(B->A), free(B->IA), free(B->JA);
    B->A = (int *) malloc(B->NNZ*sizeof(int));
    B->IA = (int *) malloc((B->M+1)*sizeof(int));
    index = (int *) malloc((B->M+1)*sizeof(int));
    B->JA = (int *) malloc(B->NNZ*sizeof(int));

    for (i=0; i<=A.N; i++)
        B->IA[i] = 0;
    for (i=0; i<A.NNZ; i++)
        B->IA[A.JA[i]+1]++; // counting element's in B's row
    for (i=1; i<=B->M; i++)
        index[i] = B->IA[i] += B->IA[i-1]; // accumulating
    index[0] = 0; 

    for (row=0,i=0; i<A.NNZ; i++)
    {
        while (i>=A.IA[row+1]) row++;
        iB = index[A.JA[i]]++;
        B->A[iB] = A.A[i];
        B->JA[iB] = row;
    }
    free(index);
}

void multiplyMatrix(const struct CSR A, const struct CSR B, struct CSR *C)
{
    int iA, iC, iA1, iB1, iArow, iCrow, iA1row, iB1row, sum, *tmp;
    struct CSR B1 = {0};
    transposeMatrix(B, &B1);

    if (C->A) free(C->A), free(C->IA), free(C->JA);
    C->M = A.M;
    C->N = B.N;
    C->A = (int *) malloc(C->M*C->N*sizeof(int)); // temporary
    C->IA = (int *) malloc((C->M+1)*sizeof(int));
    C->JA = (int *) malloc(C->M*C->N*sizeof(int)); // temporary

    iA = iC = iArow = iCrow = C->IA[0] = 0;
    while (iA < A.NNZ)
    {
        sum = 0;
        iA1 = iA; iA1row = iArow; 
        iB1 = iB1row = 0;
        while (iB1 < B1.NNZ)
        {
            if (A.JA[iA1] == B1.JA[iB1])
            {
                sum += A.A[iA1] * B1.A[iB1];
                iA1++; iB1++;
            }
            else if (A.JA[iA1] > B1.JA[iB1])
                iB1++;
            else // if (A.JA[iA1] < B1.JA[iB1])
                iA1++;
            if (iA1 >= A.IA[iA1row+1])
                while (iB1 < B1.IA[iB1row+1]) iB1++;
            if (iB1 >= B1.IA[iB1row+1])
            {
                if (iB1 < B1.NNZ)
                    iA1 = iA;
                else
                    iA1 = A.IA[iA1row+1];
                if (sum!=0)
                {
                    while (iA1row > iCrow) C->IA[++iCrow] = iC;
                    C->JA[iC] = iB1row;
                    C->A[iC++] = sum;
                    sum = 0;
                }
                while (iA1>=A.IA[iA1row+1]) iA1row++;
                while (iB1>=B1.IA[iB1row+1]) iB1row++;
            }
        }
        iA = iA1, iArow = iA1row;
    }
    C->NNZ = iC;
    C->IA[C->M] = iC;

    tmp = C->A;
    C->A = (int *) malloc(C->NNZ*sizeof(int));
    memcpy(C->A, tmp, C->NNZ*sizeof(int));
    free(tmp);

    tmp = C->JA;
    C->JA = (int *) malloc(C->NNZ*sizeof(int));
    memcpy(C->JA, tmp, C->NNZ*sizeof(int));
    free(tmp);

    free(B1.A), free(B1.IA), free(B1.JA);
}

輸入測試資料

3 5 7
0 1 3
0 3 1
1 0 1
1 2 3
1 3 4
2 2 -2
2 4 2
3 5 7
0 0 3
0 1 1
1 0 -1
1 3 2
2 0 5
2 1 2
2 4 -1

程式輸出結果

Matrix A:
3 * 5 matrix with 7 non-zero item:
A = 3 1 1 3 4 -2 2
IA = 0 2 5 7
JA = 1 3 0 2 3 2 4
====================
Matrix B:
3 * 5 matrix with 7 non-zero item:
A = 3 1 -1 2 5 2 -1
IA = 0 2 4 7
JA = 0 1 0 3 0 1 4
====================
Transpose Matrix B:
5 * 3 matrix with 7 non-zero item:
A = 3 -1 5 1 2 2 -1
IA = 0 3 5 5 6 7
JA = 0 1 2 0 2 1 2
====================
Matrix A * Matrix B':
3 * 3 matrix with 7 non-zero item:
A = 3 2 6 3 7 5 -2
IA = 0 3 6 7
JA = 0 1 2 0 1 2 2
====================
Transpose Matrix A:
5 * 3 matrix with 7 non-zero item:
A = 1 3 3 -2 1 4 2
IA = 0 1 2 4 6 7
JA = 1 0 1 2 0 1 2
====================
Matrix A' * Matrix B:
5 * 5 matrix with 14 non-zero item:
A = -1 2 9 3 -13 -4 6 2 -1 1 8 10 4 -2
IA = 0 2 4 8 11 14
JA = 0 3 0 1 0 1 3 4 0 1 3 0 1 4
=================

下面是這個考試的詳細要求

考試時間: 110分鐘 (15:00 截止上傳,為了避免截止時間系統以及網路的延遲,請提早 10 分鐘上傳,確保你已經上傳一個版本了)

  1. 請使用 Visual Studio 2010 新增專案,讓 Visual Studio 為方案建立目錄,設定方案名稱quiz1(專案)名稱C_Version,加入一個 C++ 程式檔案 main.cpp,將上述程式拷貝進去,編譯執行,拷貝上面的輸入資料,測試一下程式輸出是不是和上面一樣

  2. 請將 main 函式裡面輸入矩陣的程式段落寫成一個 readMatrix 函式,下面是輸入矩陣 A 的程式段落
        scanf("%d%d%d", &(A.M), &(A.N), &(A.NNZ));
        A.A = (int *) malloc(A.NNZ*sizeof(int));
        A.IA = (int *) malloc((A.M+1)*sizeof(int));
        A.JA = (int *) malloc(A.NNZ*sizeof(int));
        for (prevRow=-1,i=0; i<A.NNZ; i++)
        {
            scanf("%d%d%d", &row, &(A.JA[i]), &(A.A[i]));
            if (row!=prevRow) 
            {
                A.IA[row] = i;
                while (++prevRow<row) 
                    A.IA[prevRow] = A.IA[row];
            }
        }
        A.IA[A.M] = A.NNZ;
    
    請設計好函式的參數,將 main 函式裡面由鍵盤讀取矩陣 A 以及讀取矩陣 B 的程式段落用 readMatrix(&A); readMatrix(&B); 取代,請編譯並且測試

  3. 測試的時候用眼睛檢查輸出真的不是好辦法,請撰寫一個 int equalMatrix(struct CSR A, struct CSR B) 函式來比較兩個矩陣是不是完全相等,相等回傳 1,不等回傳 0;然後把 main 函式裡面 BT 和下面的 C0 矩陣比較,把 ABT 相乘得到的矩陣和下面這個 C1 矩陣比較,把 ATB 相乘得到的矩陣和下面這個 C2 矩陣比較,在呼叫 transposeMatrix 或是 multiplyMatrix 函式之後,運用 assert 以及 equalMatrix 確認相乘的結果是對的,請編譯並且測試
        int C0A[]={3,-1,5,1,2,2,-1},C0IA[]={0,3,5,5,6,7},C0JA[]={0,1,2,0,2,1,2};
        struct CSR C0={5,3,7,C0A,C0IA,C0JA};
    int C1A[]={3,2,6,3,7,5,-2},C1IA[]={0,3,6,7},C1JA[]={0,1,2,0,1,2,2}; struct CSR C1={3,3,7,C1A,C1IA,C1JA};
    int C2A[]={-1,2,9,3,-13,-4,6,2,-1,1,8,10,4,-2},C2IA[]={0,2,4,8,11,14},C2JA[]={0,3,0,1,0,1,3,4,0,1,3,0,1,4}; struct CSR C2={5,5,14,C2A,C2IA,C2JA};
  4. 你應該不會太喜歡上面的 printMatrixCSR 函式的輸出,根本就是直接輸出內部 CSR 資料而已,人很難看得懂,請你撰寫一個 void printMatrix(struct CSR matrix) 函式,以下面的格式輸出矩陣的內容 (下面是測試範例的 A 矩陣) ,請編譯並且測試

    [請注意:如果這一小題你覺得會需要比較多時間,跳過這一題先進行其它部份的要求]
    3 * 5 matrix with 7 non-zero item:
    <0,1:3>
    <0,3:1>
    <1,0:1>
    <1,2:3>
    <1,3:4>
    <2,2:-2>
    <2,4:2>
    ====================
    C 程式到此告一段落,接下來是 C++ 的部份

  5. 請點選方案總管,以滑鼠右鍵點選「方案 'quiz1' (1 專案)」,在右鍵選單中選擇「加入/新增專案」,在 quiz1 方案中新增一個專案,名稱是 CPP_Version,在方案總管或是類別總管中以右鍵點選 CPP_Version,選擇「設定為起始專案」(如下圖,你會看到起始專案的名字變成粗黑字,後面步驟裡建置和執行程式才是執行這個 CPP_Version 專案裡面的 main() 函式,如果起始專案還是 C_Version,建置和執行程式時就一直是執行 C_Version 裡面的 main() 函式)


  6. 請製作一個 CSRSparseMatrix 類別,參考上面的 struct CSR 的定義,類別裡需要有六個私有資料成員 m_M, m_N, m_NNZ, m_A, m_IA, m_JA,Visual Studio 還會替你多定義兩個 CSRSparseMatrix() 建構元函式和 ~CSRSparseMatrix() 解構元函式 (雖然我們還沒有解釋這兩個成員函式,但是它們很重要,先保留不要刪除它們)

  7. 接下來需要製作 read, equal, print, printCSR, transpose, 和 multiply 這些成員函式 (請注意 C 版本函式的名稱都是 xxxMatrix 來和其它功能的函式區分開來,但是 C++ 版本定義在 CSRSparseMatrix 類別裡,本來就不會和其它功能的函式混淆,所以名字裡的 Matrix 可以都拿掉了,例如 void printMatrix(struct CSR matrix) 函式改為 void print()),另外函式的參數也需要修改,因為成員函式執行時都有一個目標的稀疏矩陣物件,矩陣物件收到 print 訊息時就是列印自己,就不需要再傳入其它參數了,一開始這裡會有點混亂,程式一次改太多、改太急、又沒有逐步測試的話,很容易就把整個類別的機制改錯了,以下給你一些步驟提示,就當作重新設計這個類別的功能,逐步設計並且測試每一個實作出來的功能

  8. 首先請在 CSRSparseMatrix 類別裡製作一個 static 的 void unitTest() 成員函式,把剛才步驟 1,2,3,4 改好的 C_Version 版本的 main() 函式裡的內容拷貝進來,但是請先註解掉這些程式,另外新增一個 main.cpp,裡面有一個 main() 函式,函式裡呼叫這個 unitTest(),編譯、確定可以執行 (確定執行的是這個新的 main() 函式)

  9. 在 unitTest 函式裡面原本有初始化為 0 的 CSR 結構變數 A, At, B, Bt, C, 現在先改成 CSRSparseMatrix 類別的物件,但是因為類別裡有成員函式,已經沒有辦法用 C 風格的 = {0} 來初始化了,我們製作一個 CSRSparseMatrix 類別的成員函式 void setValue(int M, int N, int NNZ, int *A, int *IA, int *JA),函式裡將對應的成員設定為傳入的參數值,並且在定義完 A 物件後呼叫 A.setValue(0,0,0,0,0,0) 來初始化 A 物件,請定義並初始化其它幾個物件,接下來的 C0, C1 和 C2 物件也是類似的方法處理,請把 unitTest 後面還沒改到的程式註解起來,編譯並且測試

  10. readMatrix(&A); 需要改成傳送 read 訊息給物件 A,也就是 A.read();
    請在 CSRSparseMatrix 類別裡新增 read 成員函式,由 C 版本的函式 void readMatrix(struct CSR *matrix) 拷貝內容進來,沒有太多時間,我們還是維持用 scanf 來讀取資料,主要需要改的是沒有參數矩陣 matrix 了,你需要把資料讀進自己這個物件的資料成員 m_M, m_N, m_NNZ, ... 裡面,另外請把 malloc 換成 new[],請把 unitTest 後面還沒改到的程式註解起來,編譯並且測試

  11. unitTest 函式中接下來有個條件判斷敘述 if ((A.M != B.M)||(A.N != B.N))
    因為 unitTest 是 CSRSparseMatrix 類別的成員函式,所以可以直接存取類別的私有資料成員,這裡只需要改一下資料成員的名稱就可以了,請把 unitTest 後面還沒改到的程式註解起來,編譯並且測試

  12. unitTest 函式中接下來是 printMatrix(A) 和 printMatrix(B),請修改為傳送訊息 print 給物件 A 和物件 B
    請在 CSRSparseMatrix 類別裡新增 void print() const 成員函式,拷貝 printMatrix 函式的內容進來,修改方法類似 read 成員函式,完成後請把 unitTest 後面還沒改到的程式註解起來,編譯並且測試

  13. unitTest 函式中接下來是 transposeMatrix(B, &Bt),請修改為傳送訊息 transpose 給物件 Bt,以物件 B 為訊息的參數 (這個參數請用常數的參考變數),這樣設計的原因和前幾個函式製作時的原因是一致的
    請在 CSRSparseMatrix 類別裡新增 transpose 成員函式,拷貝 transposeMatrix 函式的內容進來,請注意轉置以後的矩陣要放在自己這個物件裡,原本配置的記憶體需要運用 delete[] 刪除 (因為每次刪除都是 m_A, m_IA, m_JA 三個一起,可以把這三個刪除的敘述放進一個輔助函式裡),其它部份的修改主要就是原本轉置矩陣的欄位 B->A, B->IA, B->JA 改為自己這個物件的成員 m_A, m_IA, m_JA,原本 A 矩陣的欄位 A.A, A.IA, A.JA 改為 A 矩陣的資料成員 A.m_A, A.m_IA, A.m_JA,注意在這個函式裡用 new[] 動態配置的記憶體,用完以後要用 delete[] 刪除,完成後請把 unitTest 後面還沒改到的程式註解起來,編譯並且測試

  14. unitTest 函式中接下來是自動測試矩陣轉置結果是否正確的 assert 敘述,需要在 CSRSparseMatrix 類別裡新增 bool equal(const CSRSparseMatrix &B) const 成員函式,拷貝 equalMatrix 函式的內容進來,修改方法類似 read 成員函式,完成後請把 unitTest 後面還沒改到的程式註解起來,編譯並且測試

  15. unitTest 函式中接下來是運用 multiplyMatrix(A, Bt, &C) 以及 multiplyMatrix(At, B, &C) 去計算 A BT 以及 AT B,並且和 C1, C2 兩個預設的矩陣比較,(請注意由於一個 CSRSparseMatrix 類別的物件中有動態配置的記憶體,使得我們不能夠運用 D = E; 這樣的語法來拷貝物件 E 的內容到物件 D,詳細原因以及解決的方法需要到學期中才說明),所以成員函式 multiply 需要設計配合 A.multiply(Bt) 的使用方法,也就是 void multiply(const CSRSparseMatrix &Bt),讓矩陣 A 乘上矩陣 Bt,乘積 A BT 直接放在矩陣 A 中,也就是矩陣 A 的內容在 A.multiply(Bt) 之後會改變,由於 unitTest 函式計算完 A BT 之後還需要計算 AT B,所以矩陣 A 如果在計算 A BT 時會改變的話,AT 就需要在計算 A BT 之前先呼叫 transpose 計算出來,如此就可以順利測試完兩個稀疏矩陣的相乘,修改的重點應該只是角色的改變: 原本的矩陣 A 變成「物件自己」,原本的矩陣 Bt 還在,原本的目標矩陣 C 先以暫時的 A[], IA[], JA[] 陣列存放,其中 A[] 和 JA[] 陣列有可能是 0 個、1 個、...、到 M * L 個元素,這樣不定個數的陣列其實運用 vector<int> 非常適合,最後再配置正確個數的陣列,拷貝回物件自己的資料成員中,另外需要修改的是欄位 M, N, NNZ, A, IA, JA 變成成員 m_M, m_N, m_NNZ, m_A, m_IA, m_JA,以及 malloc/free 變成 new[]/delete[], 注意修改時不要不小心改到演算法了,請編譯並且測試。

    [請注意:如果這一小題你覺得需要比較多時間,先完成其它部份的要求]
將所完成的 project (只需保留 .cpp, .h, .sln 以及 .vcxproj 檔案即可; 刪除掉 .suo, .sdf, .filters, .users, debug\ 資料匣, 以及 ipch\ 資料匣下的所有內容) 以 zip/rar/7zip 程式將整個資料匣壓縮起來, 在作業與實習繳交頁面中,選擇 2018-03-26 2B考試一 上傳

範例程式碼 (使用 iostream 和 vector 的版本)

不過你也知道其實光看這個程式碼沒有什麼用,就像爬山一樣,會爬山的人珍惜的是怎樣爬上去的方法和經驗,不是一張張踩著三角點的帥氣照片,這個課程需要你學一種構思的方法,瞭解撰寫和設計物件的過程,上面的步驟是這堂課到學期末的時候需要你能夠根據程式的需求擬出來的,目前在還不熟悉的狀況下,還不能要求那麼多,希望你能夠跟著上面的提示把缺少的步驟細節補上,那些操作細節在平常的實習網頁上是有的,但是怕你不瞭解目的而只是照做,所以上面的提示裡就省略了這些細節,希望你在進行的過程中看到哪裡會卡住,如果你對整個程序清楚也有想過的話,看到提示就知道該做什麼操作,希望你平常實習時能夠針對關鍵的步驟思考,不能應付應付了事只要求沒有那些紅色的毛毛虫就好

我把上傳的截止時間重設為 3/28 (三) 21:00 如果你覺得實習課時時間不夠,可以再點加油把它完成。

C++ 物件導向程式設計課程 首頁

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