|
就是下面這個 C 程式了 (希望你沒有什麼程式恐懼症，它看起來比較長、有點討厭的原因應該是為了實作比較有效率的資料結構的關係，不過是程式而已，程式做的工作多，人需要做的工作就少，生活就愉快一點!)
#include <stdio.h>
#include <malloc.h> // malloc(), free()
struct Entry
{
int row;
int col;
int value;
};
void printMatrix(struct Entry matrix[]);
void transposeMatrix(const struct Entry A[], struct Entry B[]);
void multiplyMatrix(const struct Entry A[], const struct Entry B[], struct Entry C[]);
int main()
{
int i;
struct Entry A[100]={0}, At[100]={0}, B[100]={0}, Bt[100]={0}, C[100]={0};
scanf("%d%d%d", &(A[0].row), &(A[0].col), &(A[0].value));
for (i=1; i<=A[0].value; i++)
scanf("%d%d%d", &(A[i].row), &(A[i].col), &(A[i].value));
A[i].row = -1; // extra entry for multiplyMatrix()
scanf("%d%d%d", &(B[0].row), &(B[0].col), &(B[0].value));
for (i=1; i<=B[0].value; i++)
scanf("%d%d%d", &(B[i].row), &(B[i].col), &(B[i].value));
B[i].row = -1; // extra entry for multiplyMatrix()
if ((A[0].row != B[0].row)||(A[0].col != B[0].col))
{
printf("Matrix A and B are not of the same dimension!\n");
return 1;
}
printf("\n");
printf("Matrix A:\n");
printMatrix(A);
printf("Matrix B:\n");
printMatrix(B);
transposeMatrix(B, Bt);
printf("Transpose Matrix B:\n");
printMatrix(Bt);
multiplyMatrix(A, Bt, C);
printf("Matrix A * Matrix B':\n");
printMatrix(C);
transposeMatrix(A, At);
printf("Transpose Matrix A:\n");
printMatrix(At);
multiplyMatrix(At, B, C);
printf("Matrix A' * Matrix B:\n");
printMatrix(C);
getchar(); getchar();
return 0;
}
void printMatrix(struct Entry matrix[])
{
int i;
printf("%d * %d matrix with %d non-zero item:\n",
matrix[0].row, matrix[0].col, matrix[0].value);
for (i=1; i<=matrix[0].value; i++)
printf("<%d,%d:%d>\n", matrix[i].row, matrix[i].col, matrix[i].value);
printf("====================\n");
}
void transposeMatrix(const struct Entry A[], struct Entry B[])
{
int i, iB=0, *start = (int *) malloc(sizeof(int)*(A[0].col+1));
B[iB].row = A[0].col; B[iB].col = A[0].row; B[iB++].value = A[0].value;
for (start[0]=1, i=1; i<=A[0].col; i++)
start[i] = 0;
for (i=1; i<=A[0].value; i++)
start[A[i].col+1]++; // counting element's in a row
for (i=1; i<=A[0].col; i++)
start[i] += start[i-1]; // accumulating
for (i=1; i<=A[0].value; i++)
{
iB = start[A[i].col]++;
B[iB].row = A[i].col;
B[iB].col = A[i].row;
B[iB].value = A[i].value;
}
free(start);
B[B[0].value+1].row = -1; // extra entry for multiply to test end of B1's row
}
void multiplyMatrix(const struct Entry A[], const struct Entry B[],
struct Entry C[])
{
int iA, iC, iA1, iB1, iA1row, iB1row, sum;
struct Entry *B1 = (struct Entry *)
malloc(sizeof(struct Entry)*(B[0].value+2));
transposeMatrix(B, B1);
C[0].row = A[0].row;
C[0].col = B[0].col;
C[0].value = 0;
iA = iC = 1;
while (iA <= A[0].value)
{
sum = 0;
iA1 = iA; iB1 = 1;
iA1row = A[iA1].row; iB1row = B1[iB1].row;
while (iB1 <= B1[0].value)
{
if (A[iA1].col == B1[iB1].col)
{
sum += A[iA1].value * B1[iB1].value;
iA1++; iB1++;
}
else if (A[iA1].col > B1[iB1].col)
iB1++;
else // if (A[iA1].col < B1[iB1].col)
iA1++;
if (A[iA1].row != iA1row)
while (B1[iB1].row == iB1row) iB1++;
if (B1[iB1].row != iB1row)
{
if (iB1 <= B1[0].value)
iA1 = iA;
else
while (A[iA1].row == iA1row) iA1++;
if (sum!=0)
{
C[0].value++;
C[iC].row = iA1row;
C[iC].col = iB1row;
C[iC++].value = sum;
sum = 0;
}
iB1row = B1[iB1].row;
}
}
iA = iA1;
}
free(B1);
}
|
輸入測試資料
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:
<0,1:3>
<0,3:1>
<1,0:1>
<1,2:3>
<1,3:4>
<2,2:-2>
<2,4:2>
====================
Matrix B:
3 * 5 matrix with 7 non-zero item:
<0,0:3>
<0,1:1>
<1,0:-1>
<1,3:2>
<2,0:5>
<2,1:2>
<2,4:-1>
====================
Transpose Matrix B:
5 * 3 matrix with 7 non-zero item:
<0,0:3>
<0,1:-1>
<0,2:5>
<1,0:1>
<1,2:2>
<3,1:2>
<4,2:-1>
====================
Matrix A * Matrix B':
3 * 3 matrix with 7 non-zero item:
<0,0:3>
<0,1:2>
<0,2:6>
<1,0:3>
<1,1:7>
<1,2:5>
<2,2:-2>
====================
Transpose Matrix A:
5 * 3 matrix with 7 non-zero item:
<0,1:1>
<1,0:3>
<2,1:3>
<2,2:-2>
<3,0:1>
<3,1:4>
<4,2:2>
====================
Matrix A' * Matrix B:
5 * 5 matrix with 14 non-zero item:
<0,0:-1>
<0,3:2>
<1,0:9>
<1,1:3>
<2,0:-13>
<2,1:-4>
<2,3:6>
<2,4:2>
<3,0:-1>
<3,1:1>
<3,3:8>
<4,0:10>
<4,1:4>
<4,4:-2>
====================
下面是這次考試的詳細要求 |
|
考試時間:
110分鐘 (11:10
截止上傳，為了避免截止時間系統以及網路的延遲，請提早 10 分鐘上傳，確保你已經上傳一個版本了)
- 請使用 Visual
Studio 2010 新增專案，讓 Visual Studio 為方案建立目錄，設定方案名稱是
quiz1，(專案)名稱為
C_Version，加入一個
C++ 程式檔案 main.cpp，將上述程式拷貝進去，編譯執行，複製貼上前面的輸入資料，測試一下程式輸出是不是和上面一樣
- 請將 main 函式裡面讀取矩陣的程式段落寫成一個
readMatrix 函式，下面是 main 函式裡讀取矩陣
A 的程式段落
scanf("%d%d%d", &(A[0].row), &(A[0].col), &(A[0].value));
for (i=1; i<=A[0].value; i++)
scanf("%d%d%d", &(A[i].row), &(A[i].col), &(A[i].value));
請設計好函式的參數，將 main 函式裡面由鍵盤讀取矩陣 A 以及讀取矩陣 B 的程式段落用 readMatrix(A); readMatrix(B);
取代，請使用 iostream 函式庫取代 stdio 函式庫，請編譯並且測試
請注意 A[i].row = -1; // extra entry for multiplyMatrix() 不要放進 readMatrix
裡面，這一列是額外為了配合 multiplyMatrix 演算法的，但是 i 需要改成什麼呢? 你稍微看一下讀資料的程式碼就知道應該是
A[0].value+1
- 測試的時候用眼睛檢查輸出真的不是好辦法，請撰寫一個 int
equalMatrix(const struct Entry A[], const struct Entry B)
函式來比較兩個矩陣是不是完全相等，相等回傳 1，不等回傳 0；然後把
main 函式裡面運用 transposeMatrix 計算的結果 BT
和下面的 C0 代表的稀疏矩陣比較，把運用
multiplyMatrix 計算 A
和 BT 相乘的矩陣和下面這個
C1 代表的稀疏矩陣比較，把運用 multiplyMatrix
計算AT
和 B 相乘的矩陣和下面這個 C2
代表的稀疏矩陣比較，運用 assert
以及 equalMatrix 確認相乘的結果是對的，請編譯並且測試
struct Entry C0[] = {{5,3,7},{0,0,3},{0,1,-1},{0,2,5},{1,0,1},{1,2,2},{3,1,2},{4,2,-1}};
struct Entry C1[] = {{3,3,7},{0,0,3},{0,1,2},{0,2,6},{1,0,3},{1,1,7},{1,2,5},{2,2,-2}};
struct Entry C2[] = {{5,5,14}, {0,0,-1},{0,3,2},{1,0,9},{1,1,3},{2,0,-13},
{2,1,-4},{2,3,6},{2,4,2},{3,0,-1},{3,1,1},
{3,3,8},{4,0,10},{4,1,4},{4,4,-2}};
- 在 transposeMatrix 函式裡有一個動態配置的 start 陣列，這個陣列用來暫時存放原本矩陣每一行有幾個元素，也就是轉置過的矩陣每一列有幾個元素，在最後面執行轉置動作的迴圈裡，直接把每一個元素放到新矩陣中正確的位置去，用完以後就釋放掉了，請使用
vector 類別的物件來取代這個陣列，請編譯並且測試
- 在 multiplyMatrix 函式裡有一個動態配置的陣列 B1，這個陣列是暫時存放轉置的矩陣
BT 的，請運用
new[]/delete[] 的語法取代 malloc/free
(其實這裡也可以和上一步驟一樣用 vector 來取代)，請編譯並且測試
C 程式的部份到此告一段落，接下來是 C++ 的部份
- 請點選方案總管，以滑鼠右鍵點選「方案 'quiz1' (1 專案)」，在右鍵選單中選擇「加入/新增專案」，在
quiz1 方案中新增一個專案，名稱是 CPP_Version，在方案總管或是類別總管中以右鍵點選
CPP_Version，選擇「設定為起始專案」(如下圖，你會看到起始專案的名字變成粗黑字，後面步驟裡建置和執行程式才是執行這個 CPP_Version
專案裡面的 main() 函式，如果起始專案還是 C_Version，建置和執行程式時就一直是執行 C_Version 裡面的 main()
函式)
- 上面的 C 程式裡用一個陣列來存放稀疏矩陣的所有資料，但是單看這些資料也可能是描述 N
個城市的座標，並不能夠明確代表一個稀疏矩陣，接下來請製作一個 SparseMatrix
類別，這個類別的物件需要能夠描述一個稀疏矩陣，上面的 struct Entry
的定義還是需要的，在類別裡需要有四個私有資料成員
， m_nRows, m_nCols, m_nElems 是三個整數分別存放稀疏矩陣有幾列、有幾行、有幾個非 0 的元素，struct
Entry 指標 m_A 裡面運用 new[] 動態配置的 m_nElems+2 個 struct Entry 元素 (多出兩個元素，第一個元素
m_A[0] 是完全沒有用到的，只是因為原本程式的陣列侍從 A[1] 開始放資料，考試時間不夠，多一個元素的話可以不要修改原本的程式裡陣列使用時的註標，另外最後多一個元素也是配合原來的
multiplyMatrix 裡面的演算法的)，Visual Studio 會替你多定義兩個 SparseMatrix() 建構元函式和
~SparseMatrix() 解構元函式 (我們還沒有解釋這兩個成員函式，但是它們很重要，先保留不要刪除它們)
- 接下來需要製作 read,
equal, print,
transpose, 和 multiply
這五個成員函式 (請注意 C 版本函式的名稱都是 xxxMatrix 來和其它功能的函式區分開來，但是
C++ 版本定義在 SparseMatrix 類別裡，本來就不會和其它功能的函式混淆，所以名字裡的 Matrix 可以都拿掉了，例如
void printMatrix(struct Entry matrix[]) 函式改為 void print())，另外函式的參數也需要修改，因為成員函式執行時都有一個目標的稀疏矩陣物件，矩陣物件收到
print 訊息時就是列印自己這個物件，不需要再傳入其它參數了，一開始這裡會有點混亂，程式一次改太多、改太急、又沒有逐步測試的話，很容易就把原本程式的機制改錯了，以下給你一些步驟提示，就當作重新設計這個類別的功能，逐步設計並且測試每一個實作出來的功能
- 首先請在 SparseMatrix 類別裡製作一個 static 的 void unitTest()
成員函式，把剛才步驟 1,2,3,4,5 改好的 C_Version 版本的 main() 函式裡的內容拷貝進來，但是請先註解掉這些程式，另外新增一個
main.cpp，裡面有一個 main() 函式，函式裡呼叫這個 unitTest()，編譯、確定可以執行 (確定執行的是這個新的
main() 函式)
- 在 unitTest 函式裡面原本有存放稀疏矩陣的 Entry 結構陣列 A, At,
B, Bt, C，初始化為 0，現在先改成 SparseMatrix 類別的物件，但是因為類別裡有成員函式，已經沒有辦法用 C 風格的
= {0} 來初始化了，請製作一個 SparseMatrix 類別的成員函式 void setValue(int
nRows, int nCols, int nElems, struct Entry *A)，函式裡將對應的成員設定為傳入的參數值，並且在定義完稀疏矩陣
A 物件後呼叫 A.setValue(0,0,0,0) 來初始化 A 物件，請定義並初始化其它 At, B, Bt 幾個物件，接下來的
C0, C1 和 C2 物件也是類似的方法處理，請把 unitTest 後面還沒改到的程式註解起來，編譯並且測試
- readMatrix(A); 需要改成傳送 read
訊息給物件 A，也就是 A.read();
請在 SparseMatrix 類別裡新增 void read() 成員函式，由
C 版本的函式 void readMatrix(struct Entry matrix[]) 的內容拷貝進來，主要需要改的是沒有參數矩陣
matrix 了，你需要把資料讀進自己這個物件的資料成員 m_nRows, m_nCols, m_nElems, ... 裡面，另外請運用
new[] 配置 m_A 陣列，配置前請先刪除原本的 m_A 陣列，請把 unitTest 後面還沒改到的程式註解起來，編譯並且測試
- unitTest 函式中接下來有個條件判斷敘述 if ((A[0].row != B[0].row)||(A[0].col
!= B[0].col)
因為 unitTest 是 SparseMatrix 類別的成員函式，所以可以直接存取類別的私有資料成員，這裡只需要改一下資料成員的名稱就可以了，請把
unitTest 後面還沒改到的程式註解起來，編譯並且測試
- unitTest 函式中接下來是 printMatrix(A) 和 printMatrix(B)，請修改為傳送訊息
print 給物件 A 和物件 B
請在 SparseMatrix 類別裡新增 void print() const
成員函式，拷貝 printMatrix 函式的內容進來，修改方法類似 read 成員函式，修改完成後請把
unitTest 後面還沒改到的程式註解起來，編譯並且測試
- unitTest 函式中接下來是 transposeMatrix(B, Bt)，請修改為傳送訊息
transpose 給物件 Bt，以物件 B 為訊息的參數 (因為物件裡面有很大的陣列，為了避免拷貝，這個參數請用常數的參考變數)，這樣設計的原因和前幾個函式製作時的原因是一致的
請在 SparseMatrix 類別裡新增 transpose 成員函式，拷貝 transposeMatrix 函式的內容進來，請注意轉置以後的矩陣要放在自己這個物件裡，其它部份的修改主要就是配置正確大小的
m_A 陣列，原本轉置矩陣的欄位 B[i].row, B[i].col, B[i].value 改為自己這個物件的成員 m_A[i].row,
m_A[i].col, m_A[i].value，原本 B[0].row, B[0].col, B[0].value 改為 m_nRows,
m_nCols, m_nElems，原本 A 矩陣的 A[i].row, A[i].col, A[i].value 改為 A 矩陣的資料成員
A.m_A[i].row, A.m_A[i].col, A.m_A[i].value，原本 A[0].row, A[0].col,
A[0].value 改為 A.m_nRows, A.m_nCols, A.m_nElems，在這個函式裡用的 vector，用完以後不需要特別去刪除，會自動完成清除的動作，修改完成後請把
unitTest 後面還沒改到的程式註解起來，編譯並且測試
- unitTest 函式中接下來是自動測試矩陣轉置結果是否正確的 assert 敘述，需要在
SparseMatrix 類別裡新增 bool equal(const
SparseMatrix &B) const 成員函式，拷貝 equalMatrix 函式的內容進來，修改方法類似
read 成員函式，修改完成後請把 unitTest 後面還沒改到的程式註解起來，編譯並且測試
- unitTest 函式中接下來是運用 multiplyMatrix(A, Bt, C)
以及 multiplyMatrix(At, B, C) 去計算 A
BT 以及 AT
B，並且和 C1,
C2 兩個預設的矩陣比較，(請注意由於一個
SparseMatrix 類別的物件中有動態配置的記憶體，使得我們不能夠運用 D = E; 這樣的語法來拷貝物件 E 的內容到物件
D，詳細原因以及解決的方法需要再過幾個星期才會講到)，所以成員函式 multiply
需要設計配合 A.multiply(Bt) 的使用方法，也就是 void multiply(const
SparseMatrix &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 裡面，在這個版本裡並不需要 C，但是乘出來的矩陣元素還是需要放在一個暫存的陣列中，這個陣列有可能是
0 個元素也有可能是 M * L 個元素，其實運用 vector<Entry> 非常適合，最後再將內容拷貝回物件自己的成員
m_A 中，然後是陣列元素 A[0].row, A[0].col, A[0].value, A[i].row, A[i].col,
A[i].value 變成成員 m_nRows, m_nCols, m_nElems, m_A[i].row, m_A[i].col,
m_A[i].value，不要更動演算法的話，程式比較不會出錯，請編譯並且測試。
[請注意：如果這一小題你覺得需要比較多時間，先完成其它部份的要求]
|
