193
稀疏矩陣的加，減，乘，轉置
1 需求分析
稀疏矩陣是指哪些多元素為零的矩陣。利用“稀疏的特點”進行儲存和計算可以打打節省儲存空間，提高計算效率。實現一個能進行稀疏矩陣基本運算的運算器。
以“帶行邏輯鏈接信息”的三元組標表示稀疏矩陣，實現矩陣的轉置，實現兩個矩陣相加，相減和相乘的運算。稀疏矩陣的輸入形勢采用三元組表示，而運算結果的矩陣則以通常的陣列形勢列出。
演示程序以用戶和計算機的對話法師執行，數組的建立方式為邊輸入邊建立。
由題目要求可知：首先應該輸入矩陣的行數和列數，並判別給出的兩個矩陣的行數，列數對於所要求作的運算是否相互匹配。
程序可以對三元組的輸入順序不加以限製；根據對矩陣的行列，三元組作直接插入排序，從而進行運算時，不會產生錯誤。
程序在vc6.0環境下設計。程序執行命令為：1.稀疏矩陣的轉置；2.稀疏矩陣的乘法；3.稀疏矩陣的加法；4.稀疏矩陣的減法；5.退出；的工作。
1.1 用戶角度
（1）從界麵選擇一種算法並輸入一個或兩個稀疏矩陣，輸出運算的正確結果。
（2）界麵簡潔，操作方便。
1.2 開發工具的特點
Visual C++ 6.0版本：
（1）具有程序框架自動生成、靈活方便的類管理、代碼編寫和界麵設計集成交互操作、可開發多種程序等優點。
（2）界麵簡潔，占用資源少，操作方便。
（3）擁有“語法高亮”，自動編譯功能以及高級除錯功能而著稱。比如，它允許用戶進行遠程調試，單步執行等。還有允許用戶在調試期間重新編譯被修改的代碼，而不必重新啟動正在調試的程序。其編譯及創建預編譯頭文件(stdafx.h)、最小重建功能及累加連結(link)著稱。這些特征明顯縮短程序編輯、編譯及連結的時間花費，在大型軟件計劃上尤其顯著。
2 概要設計
圖2.1
1ï¼ 基本操作：
InputTSMatrix
操作結果：輸入三元組矩陣
OutputSMatrix
初始條件：矩陣已經存在
操作結果：輸出矩陣
TranSMatrix()
初始條件：矩陣已經存在
操作結果：轉置輸入的矩陣
FastTranMat()
初始條件：矩陣已經存在
操作結果：快速轉置輸入的矩陣
MultSMatrix()
初始條件：矩陣A和矩陣B已經存在
操作結果：求矩陣A和矩陣B的積
AddMatrix()
初始條件：矩陣A和矩陣B已經存在
操作結果：求矩陣A和矩陣B的和
SubMatrix()
初始條件：矩陣A和矩陣B已經存在
操作結果：求矩陣A和矩陣B的減
3 詳細設計
3.1定義儲存矩陣三元組結構
#include <stdio.h>
#include <iomanip>
const int MAXSIZE = 100; //定義非零元素的最多個數
const int MAXROW = 10; //定義數組行數的最大值
const int SIZENUM = 10;
typedef struct //定義三元組元素
{
int r, c; //矩陣的行號和列號
int v; //矩陣元素值
}Triple;
typedef struct //定義普通三元組對象
{
Triple data[MAXSIZE+1];
int rpos[MAXROW+1];
int rows, cols, nzeroNums; //行數、列數、非零元素個數
}TSMatrix;
稀疏矩陣的三元組順序表：為了節省存儲空間，同樣對稀疏矩陣進行壓縮存儲，即隻存儲稀疏矩陣的非零元素。但是為了實現矩陣的各種運算，還要必須同時記下他的行號和列號。這樣，一個三元組（i，j，Aij）便唯一的確定了矩陣中的非零元素，其中i，j分別表示非零元素的行號和列號，Aij則表示非零元素的值。
3.2主要模塊的詳細分析
3.2.1 矩陣的主程序模塊
Main函數主控調用其他模塊並描述了以下界麵：
3.2.1 矩陣的構造模塊
void InputTSMatrix(TSMatrix *M)
{
printf("輸入矩陣的行數、列數和非零元素個數: ");
scanf("%d%d%d",&M->rows,&M->cols,&M->nzeroNums);
printf("請輸入非零元素對應的行號、列號和相應的元素值:\n ");
for (int i = 1; i <= M->nzeroNums; i++)
{
scanf("%d%d%d",&M->data[i].r,&M->data[i].c,&M->data[i].v);
}
}
3.2.1 矩陣的運算模塊
1）矩陣的轉置
void TranSMatrix()
{
TSMatrix M, T;
InputTSMatrix(&M);
int col, p, q = 1;
T.rows = M.cols;
T.cols = M.rows;
T.nzeroNums = M.nzeroNums;
if (T.nzeroNums)
{
for (col = 1; col <= M.cols; col++)
{
for (p = 1; p <= M.nzeroNums; p++)
{
if (M.data[p].c == col)
{
T.data[q].r = M.data[p].c;
T.data[q].c = M.data[p].r;
T.data[q].v = M.data[p].v;
++q;
}
}
}
}
printf("運用普通轉置算法, 輸入矩陣的轉置矩陣為:\n ");
OutputSMatrix(T);
稀疏矩陣的轉置的實現規則：
1.將矩陣的行列值相互交換。2.每個三元組的i、j相互交換。3.重新排列三元組之間的次序便可實現轉置
2）矩陣的快速轉置
void FastTranMat()
{
TSMatrix M, T;
int num[MAXROW+1]; //表示矩陣M中第col列非零元素的個數
int cpot[MAXROW+1]; //表示矩陣M中第col列第一個非0元素在b.data中的位置
int p, q, col, t;
InputTSMatrix(&M); //輸入稀疏矩陣
T.rows = M.cols;
T.cols = M.rows;
T.nzeroNums = M.nzeroNums;
if (T.nzeroNums)
{
for (col = 1; col <= M.cols; col++)//M中各列元素初始化
{
num[col] = 0;
}
for (t = 1; t <= M.nzeroNums; t++)
{
++num[M.data[t].c]; //求M中每一列非零元個數
}
//求第col列第一個非零元在b.data中的序號
cpot[1] = 1;
for (col = 2; col <= M.cols; col++)
{
cpot[col] = cpot[col-1] + num[col-1];
}
for (p = 1; p <= M.nzeroNums; p++)
{
col = M.data[p].c; //稀疏矩陣M中每個元素對應的列號
q = cpot[col]; //稀疏矩陣M中第一個非零元素位置
T.data[q].r = M.data[p].c;
T.data[q].c = M.data[p].r;
T.data[q].v = M.data[p].v;
++cpot[col];
}//end_for
}//end_if
printf("運用快速算法，輸入矩陣的轉置為:\n ");
OutputSMatrix(T);
}
快速轉置的思想是開辟兩個數組用來存放每一行有效值的個數，另一個用來存轉置後順序表vector的起始位置。使得數組可以快速找到有效順序在轉置後順序表裏的位置。也就是說快速轉置與普通轉置比較來說快速轉置更為有效計算機運算相對比較簡單。
4）矩陣的加法
//兩個稀疏矩陣的加法
int AddMatrix()
{
TSMatrix A, B, C;
int i = 1, j = 1, k = 1; //i, j, k分別用以保存A、B、C非零元素個數
int value = 0;
InputTSMatrix(&A);
InputTSMatrix(&B);
if (A.rows != B.rows || A.cols != B.cols)
{
printf("兩個稀疏矩陣的大小不等,不能相加!\n" );
return 0;
}
if (A.rows == B.rows && A.cols == B.cols)
{
while (i <= A.nzeroNums && j <= B.nzeroNums)
{
if (A.data[i].r == B.data[j].r)
{
if (A.data[i].c < B.data[j].c)
{
C.data[k].r = A.data[i].r;
C.data[k].c = A.data[i].c;
C.data[k].v = A.data[i].v;
k++;
i++;
}
else if (A.data[i].c > B.data[j].c)
{
C.data[k].r = B.data[j].r;
C.data[k].c = B.data[j].c;
C.data[k].v = B.data[j].v;
k++;
j++;
}
else
{
value = A.data[i].v + B.data[j].v;
if (value != 0)
{
C.data[k].r = A.data[i].r;
C.data[k].c = A.data[i].c;
C.data[k].v = value;
k++;
}
i++;
j++;
}
}
else if (A.data[i].r < B.data[j].r)
{
C.data[k].r = A.data[i].r;
C.data[k].c = A.data[i].c;
C.data[k].v = A.data[i].v;
k++;
i++;
}
else
{
C.data[k].r = B.data[j].r;
C.data[k].c = B.data[j].c;
C.data[k].v = B.data[j].v;
k++;
j++;
}//把剩餘部分元素存入C中
if (i > A.nzeroNums && j <= B.nzeroNums)
{
for (; j <= B.nzeroNums; j++)
{
C.data[k].r = B.data[j].r;
C.data[k].c = B.data[j].c;
C.data[k].v = B.data[j].v;
k++;
}
}
if (i <= A.nzeroNums && j > B.nzeroNums)
{
for (; i <= A.nzeroNums; i++)
{
C.data[k].r = A.data[i].r;
C.data[k].c = A.data[i].c;
C.data[k].v = A.data[i].v;
k++;
}
}
}
C.rows = A.rows;
C.cols = A.cols;
C.nzeroNums = k-1;
printf("輸出兩個稀疏矩陣的和:\n ");
OutputSMatrix(C);
return 1;
}
else
return 0;
}
稀疏矩陣的加法：稀疏矩陣的加法與普通矩陣的加法一樣，遵循普通矩陣的加法運算規則，也就是當矩陣A和矩陣B行數和列數必須相同才可以進行計算。
5）矩陣的減法
//兩個稀疏矩陣的減法
int SubMatrix()
{
TSMatrix A, B, C;
int m = 1, n = 1, k = 1, temp;
InputTSMatrix(&A);
InputTSMatrix(&B);
C.rows = A.rows;
C.cols = A.cols;
C.nzeroNums = 0;
if (A.rows == B.rows && A.cols == B.cols)
{
while (m <= A.nzeroNums && n <= B.nzeroNums)
{
if (A.data[m].r == B.data[n].r)
{
if (A.data[m].c == B.data[n].c)
{
temp = A.data[m].v - B.data[n].v;
if (temp != 0)
{
C.data[k].r = A.data[m].r;
C.data[k].c = A.data[m].c;
C.data[k].v = temp;
k++;
}
m++;
n++;
}
else if (A.data[m].c < B.data[n].c)
{
C.data[k].r = A.data[m].r;
C.data[k].c = A.data[m].c;
C.data[k].v = A.data[m].v;
k++;
m++;
}
else
{
C.data[k].r = B.data[n].r;
C.data[k].c = B.data[n].c;
C.data[k].v = -B.data[n].v;
k++;
n++;
}
}
else if (A.data[m].r < B.data[n].r)
{
C.data[k].r = A.data[m].r;
C.data[k].c = A.data[m].c;;
C.data[k].v = A.data[m].v;
k++;
m++;
}
else
{
C.data[k].r = B.data[n].r;
C.data[k].c = B.data[n].c;
C.data[k].v = -B.data[n].v;
k++;
n++;
}
}//end_while
if (m <= A.nzeroNums)
{
for (; m <= A.nzeroNums; m++)
{
C.data[k].r = A.data[m].r;
C.data[k].c = A.data[m].c;
C.data[k].v = A.data[m].v;
k++;
}
}
if (n <= B.nzeroNums)
{
for (; n <= B.nzeroNums; n++)
{
C.data[k].r = B.data[n].r;
C.data[k].c = B.data[n].c;
C.data[k].v = -B.data[n].v;
k++;
}
}
C.nzeroNums = k-1;
printf("兩個稀疏矩陣的差為:\n");
OutputSMatrix(C);
return 1;
} //end_if
else
{
printf("兩個稀疏矩陣的大小不同，不能相減!\n");
return 0;
}
}
//得到矩陣元素M[i][j]的值
int value(TSMatrix M, int i, int j)
{
int k;
for (k = 1; k <= M.nzeroNums; k++)
{
if (M.data[k].r == i && M.data[k].c == j)
{
return M.data[k].v;
}
}
return 0;
}
稀疏矩陣的減法：規則同加法一樣，矩陣A和矩陣B的行數和列數相等時才可以進行計算。
6）矩陣的乘法
//矩陣乘法的算法
int MultMat()
{
TSMatrix A, B, C;
InputTSMatrix(&A);
InputTSMatrix(&B);
int i, j, k, temp = 0, p = 1;
if (A.cols != B.rows)
{
printf("矩陣A的列數不等於矩陣B的行數不能相乘!\n");
return 0;
}
else
{
for (i = 1; i <= A.rows; i++)
{
for (j = 1; j <= B.cols; j++)
{
temp = 0;
for (k = 1; k <= A.cols; k++)
{
temp += value(A, i, k) * value(B, k, j);
}
if (temp != 0)
{
C.data[p].r = i;
C.data[p].c = j;
C.data[p].v = temp;
p++;
}
}
}
C.rows = A.rows;
C.cols = B.cols;
C.nzeroNums = p-1;
OutputSMatrix(C);
return 1;
}
}
稀疏矩陣的乘法：同樣遵循普通矩陣的乘法運算，當矩陣A與矩陣B相乘時則隻有前者的列數等於後者的行數時該運算才有意義。
（4）矩陣的輸出模塊
//輸出矩陣，按標準格式輸出
void OutputSMatrix(TSMatrix M)
{
int i, j, k = 1;
for (i = 0; i < M.rows; i++)
{
for (j = 0; j < M.cols; j++)
{
if ((M.data[k].r-1) == i && (M.data[k].c-1) == j)
{
printf("%4d",M.data[k].v);
k++;
}
else
printf("%4d",0);
}//end_j
printf("\n");
}//end_i
}
|
Main（） |
|
Input（） |
|
Transpose（） |
|
Add（） |
|
Sub（） |
|
Mul（） |
|
Output（） |
|
3.3 主程序流程圖
4 測試
稀疏矩陣的定義：矩陣中非零元素遠遠小於矩陣元素的個數，並且非零元素的分布沒有一定的規律，則稱該矩陣為稀疏矩陣。
該程序測試所使用的矩陣A、B和矩陣C分別如下：
5 0 0 12 0 0 0 0 0 0 15 3 1 0 4 0 0
0 0 16 0 0 0 4 0 0 0 0 0 0 1 0 0 0
8 0 11 0 27 0 0 0 0 8 0 0 8 0 0 0 0
0 0 0 0 0 0 1 13 0 0 0 0 0 0 7 0 0
矩陣A 矩陣B 5 1 0 0 0
0Â Â Â 0 0 0 3
矩陣C
最後更新：2017-05-19 10:25:06