1062 2B Quiz#1: 稀疏矩陣 (Sparse Matrix) 類別設計
| C++ 實習測試: 稀疏矩陣 (Sparse Matrix) 類別設計 |
| 時間: 110 分鐘 (13:10-15:00, 15:00 上傳時間截止) |
|
如上圖，概念上稀疏矩陣是一個很大的矩陣 (很多列、很多行) 但是裡面絕大部份數值都是 0
|
| 就是下面這個 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 分鐘上傳，確保你已經上傳一個版本了)
|
| 將所完成的 project (只需保留 .cpp, .h, .sln 以及 .vcxproj 檔案即可; 刪除掉 .suo, .sdf, .filters, .users, debug\ 資料匣, 以及 ipch\ 資料匣下的所有內容) 以 zip/rar/7zip 程式將整個資料匣壓縮起來, 在作業與實習繳交頁面中，選擇 「2018-03-26 2B考試一」 上傳 |
範例程式碼 (使用 iostream 和 vector 的版本) 不過你也知道其實光看這個程式碼沒有什麼用，就像爬山一樣，會爬山的人珍惜的是怎樣爬上去的方法和經驗，不是一張張踩著三角點的帥氣照片，這個課程需要你學一種構思的方法，瞭解撰寫和設計物件的過程，上面的步驟是這堂課到學期末的時候需要你能夠根據程式的需求擬出來的，目前在還不熟悉的狀況下，還不能要求那麼多，希望你能夠跟著上面的提示把缺少的步驟細節補上，那些操作細節在平常的實習網頁上是有的，但是怕你不瞭解目的而只是照做，所以上面的提示裡就省略了這些細節，希望你在進行的過程中看到哪裡會卡住，如果你對整個程序清楚也有想過的話，看到提示就知道該做什麼操作，希望你平常實習時能夠針對關鍵的步驟思考，不能應付應付了事，只要求沒有那些紅色的毛毛虫就好。 我把上傳的截止時間重設為 3/28 (三) 21:00 如果你覺得實習課時時間不夠，可以再點加油把它完成。 |
