《稀疏矩陣基本操作 實驗資料報告材料》由會員分享，可在線閱讀，更多相關(guān)《稀疏矩陣基本操作 實驗資料報告材料（29頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、word
稀疏矩陣根本操作 實驗報告
一、 實驗容
稀疏矩陣的壓縮儲存結(jié)構(gòu)，以與稀疏矩陣的三元組表表示方法下的轉(zhuǎn)置、相加、相乘等算法
二、 實驗?zāi)康?
1. 熟悉數(shù)組、矩陣的定義和根本操作
2. 熟悉稀疏矩陣的儲存方式和根本運算
3. 理解稀疏矩陣的三元組表類型定義，掌握稀疏矩陣的輸入、輸出和轉(zhuǎn)置算法
三、 實驗原理
1. 使用三元組儲存矩陣中的非零元素〔三元組分別儲存非零元素的行下標，列下標和元素值〕。除了三元組表本身，儲存一個稀疏矩陣還需要額外的三個變量，分別儲存矩陣的非零元個數(shù)，矩陣的行數(shù)和矩陣的列數(shù)。
2. 稀疏矩陣的創(chuàng)建算法：
第一步：根據(jù)矩陣創(chuàng)建一個二維
2、數(shù)組，表示原始矩陣
第二步：取出二維數(shù)組中的元素〔從第一個元素開始取〕，判斷取出元素是否為非零元素，如果為非零元素，把該非零元素的數(shù)值以與行下標和列下表儲存到三元數(shù)組表里，否如此取出下一個元素，重復(fù)該步驟。
第三步：重復(fù)第二步，知道二維數(shù)組中所有的元素已經(jīng)取出。
3. 稀疏矩陣倒置算法：
第一步：判斷進展倒置的矩陣是否為空矩陣，如果是，如此直接返回錯誤信息。
第二步：計算要倒置的矩陣每列非零元素的數(shù)量，存入到num數(shù)組〔其中num[i] 代表矩陣中第i列非零元素的個數(shù)〕。以與倒置后矩陣每行首非零元的位置，存入cpot數(shù)組中〔其中cpot表示倒置后矩陣每行非零元的位置，對應(yīng)表示原矩
3、陣每列中第一個非零元的位置〕。
第三步：確定倒置后矩陣的行數(shù)和列數(shù)。
第四步：取出表示要導(dǎo)致矩陣中三元組表元素 {e, I, j}〔第一次取出第一個，依次取出下一個元素〕，從第二步cpot數(shù)組中確定該元素倒置后存放的位置〔cpot[j]〕，把該元素的行下標和列下標倒置以后放入新表的指定位置中。cpot[j] 變量加一。
第五步：重復(fù)第四步，直到三元組表中所有的元素都完成倒置。
第六步：把完成倒置運算的三元組表輸出。
4. 稀疏矩陣加法算法：
第一步：檢查相加兩個矩陣的行數(shù)和列數(shù)是否一樣，如果一樣，如此進入第二步，否如此輸出錯誤信息。
第二步：定義變量i和j，用于控制三元組表的
4、遍歷。
第三步：比擬變量矩陣M中第i個元素和矩陣N中第j個元素，如果兩個元素是同一行元素，如果不是如此進入第四步，如果是，再繼續(xù)比擬兩個元素是否為同一列元素，如果是，把兩個元素值相加，放到三元組表中；否如此把列下表小的元素依次放到三元組表中。進入第五步
第四步：如果矩陣M中第i個元素的行下標大于矩陣N中第j個元素的行下標，如此把矩陣N中第j個元素所在行的所有非零元素添加到三元組表中；如果矩陣M中第i個元素的行下標小于矩陣N中第j個元素的下標，如此把M中第i個元素所在行的所有非零元素依次添加到三元組表中。
第五步：重復(fù)第三步，直到矩陣M和矩陣N中所有元素都非零元素添加到三元組表中。
第六
5、步：輸出運算結(jié)果
5. 稀疏矩陣乘法算法：
第一步：檢查矩陣M和矩陣N能否參與乘法運算〔即矩陣M的列數(shù)等于矩陣N的行數(shù)〕，如果兩個矩陣可以參與乘法運算，進入下一步，否如此輸出錯誤信息
第二步：檢查兩個矩陣相乘以后是否為零矩陣，如果相乘結(jié)果是零矩陣，直接返回一個零矩陣。
第三步：分別計算矩陣M和矩陣N中每行非零元的個數(shù)〔分別存放到num_m和num_n數(shù)組中〕，并計算出每行首非零元的位置〔分別存放到cpot_m和cpot_n中〕。
第四步：依次取矩陣M中的非零元〔第一次取出矩陣M中的第一個非零元〕，求出該非零元所在行和所在列乘積的和，然后把值放到結(jié)果三元組表的特定位置。
第五步：
6、重復(fù)第四步，直到矩陣M中所有非零元都已經(jīng)參與運算。
第六步：輸出結(jié)果
四、 程序流程圖
五、 實驗結(jié)果
5.1 程序主菜單
5.2 稀疏矩陣三元組的創(chuàng)建和倒置
5.3 稀疏矩陣的加法運算并以三元組輸出結(jié)果
5.4 稀疏矩陣的乘法運算并以矩陣方式輸出結(jié)果
六、 操作說明
1. 在創(chuàng)建稀疏矩陣的時候，可以每次輸入一個數(shù)據(jù)，也可以一次輸入多個數(shù)據(jù)，程序會自動根據(jù)輸入元素的個數(shù)對矩陣數(shù)據(jù)進展填充
2. 每次矩陣運算失敗時〔無論是輸入的矩陣不符合矩陣運算的條件，參與運算其中一個矩陣為空矩陣，或者分配不到臨時空間〕，程序都會返回到主菜單。輸入的數(shù)據(jù)都會被清空。
7、
七、 附錄：代碼
#include
#include
#include
#defineMAXSIZE 1000
#defineOK 0
#defineMALLOC_FAIL -1// 表示分配空間時發(fā)生錯誤
#defineEMPTY_MATRIX -2// 表示正嘗試對一個空矩陣進展運算操作
#defineMATRIX_NOT_MATCH -3// 表示嘗試對不符合運算條件的矩陣進展運算操作〔例如非一樣行數(shù)列數(shù)矩陣相加〕
/* ----------- 結(jié)構(gòu)體聲明局部 ---------------- *
8、/
typedefstruct
{
int row;// 非零元的行下標
int col;// 非零元的列下標
int e;// 非零元的值
} Triple;
typedefstruct
{
Triple *data;// 非零元素的元素表
int rownum;// 矩陣的行數(shù)
int colnum;// 矩陣的列數(shù)
int num;// 矩陣非零元的個數(shù)
} TSMatrix, *PTSMatrix;
/* ----------- 函數(shù)聲明局部 ------------------ */
// 初始化稀疏矩陣結(jié)構(gòu)
int TSMatrix_Init
9、(TSMatrix *M);
// 以三元組的方式輸出稀疏矩陣
void TSMatrix_PrintTriple(TSMatrix *M);
// 以矩陣的方式輸出稀疏矩陣
void TSMartix_PrintMatrix(TSMatrix *M);
// 從一個二維數(shù)組〔普通矩陣〕創(chuàng)建一個稀疏矩陣
TSMatrix *TSMatrix_Create(int *a, int row, int col);
// 從鍵盤錄入數(shù)據(jù)創(chuàng)建一個稀疏矩陣
TSMatrix *TSMatrix_CreateFromInput();
// 求稀疏矩陣 M 的轉(zhuǎn)置矩陣 T
int TSMa
10、trix_FastTranspose(TSMatrix M, TSMatrix *T);
// 如果稀疏矩陣 M 和 N 的行數(shù)的列數(shù)一樣，計算 Q = M + N
int TSMatrix_Add(TSMatrix M, TSMatrix N, TSMatrix *Q);
// 如果稀疏矩陣 M 的列數(shù)等于 N 的行數(shù)，計算 Q = M x N;
int TSMatrix_Multply(TSMatrix M, TSMatrix N, TSMatrix *Q);
// 把光標位置移動到該行行首
void ResetCursor();
/* ----------- 程序主函數(shù)
11、 -------------------- */
int main(void)
{
int info;
char ch;
// 從一個二維數(shù)組創(chuàng)建一個系數(shù)矩陣
TSMatrix *M;
TSMatrix *N;
// 用來接收運算結(jié)果的空間
TSMatrix *T = (TSMatrix *)malloc(sizeof(TSMatrix));
while (1)
{
fflush(stdin);
system("cls");
printf(" 稀疏矩陣根本操作演示 \n");
printf("1. 矩陣的創(chuàng)建和轉(zhuǎn)置\n");
printf("2.
12、 矩陣的加法運算并以三元組輸出結(jié)果\n");
printf("3. 矩陣的乘法運算并以矩陣輸出結(jié)果\n");
printf("\n");
printf("Q. 退出程序\n");
printf("\n");
printf(" 請輸入選項：");
scanf("%c", &ch);
switch (ch)
{
case'1':
system("cls");
M = TSMatrix_CreateFromInput();
if (M != NULL)
{
printf("\n\n以三元組輸出稀疏矩陣：\n");
TSMatrix_PrintTripl
13、e(M);
printf("\n倒置后稀疏矩陣的三元組輸出：\n");
TSMatrix_FastTranspose(*M, T);
TSMatrix_PrintTriple(T);
system("pause");
}
else
{
printf("創(chuàng)建矩陣過程發(fā)生錯誤");
system("pause");
}
break;
case'2':
system("cls");
M = TSMatrix_CreateFromInput();
N = TSMatrix_CreateFromInput();
if (M == NULL || N ==
14、NULL)
{
printf("創(chuàng)建矩陣過程中發(fā)生錯誤！\n");
system("pause");
break;
}
info = TSMatrix_Add(*M, *N, T);
if (info == MATRIX_NOT_MATCH)
{
printf("這兩個矩陣不能運算呢?。? ⊙﹏⊙\n");
}
elseif (info == OK)
{
printf("\n運算結(jié)果：\n");
TSMatrix_PrintTriple(T);
}
system("pause");
break;
case'3':
system("cls")
15、;
M = TSMatrix_CreateFromInput();
N = TSMatrix_CreateFromInput();
if (M == NULL || N == NULL)
{
printf("創(chuàng)建矩陣過程中發(fā)生錯誤！\n");
system("pause");
break;
}
info = TSMatrix_Multply(*M, *N, T);
if (info == MATRIX_NOT_MATCH)
{
printf("這兩個矩陣不能運算呢??！ ⊙﹏⊙\n");
}
elseif (info == OK)
{
print
16、f("\n運算結(jié)果：\n");
TSMartix_PrintMatrix(T);
}
system("pause");
break;
case'q':
case'Q':
exit(0);
}
}
return 0;
}
// 初始化稀疏矩陣結(jié)構(gòu)
int TSMatrix_Init(TSMatrix *M)
{
M->data = (Triple *)malloc(MAXSIZE * sizeof(Triple));
if (!M->data)
returnMALLOC_FAIL;
M->num = 0;
M->colnum = 0;
17、
M->rownum = 0;
returnOK;
}
// 從一個二維數(shù)組創(chuàng)建一個稀疏矩陣
TSMatrix *TSMatrix_Create(int *a, introw, intcol)
{
int i, j;
TSMatrix *P = (TSMatrix *)malloc(sizeof(TSMatrix));
TSMatrix_Init(P);
// 設(shè)置稀疏矩陣的行數(shù)和列數(shù)
P->rownum = row;
P->colnum = col;
for (i = 0; i < row; i++)
{
for (j = 0; j < col;
18、 j++)
{
// 如果第 i+1 行第 i+1 列元素是非零元素
if (0 != *(a + i * col + j))
{
// 把非零元的元素和位置信息保存到稀疏矩陣中
P->data[P->num].e = *(a + i * col + j);
P->data[P->num].row = i + 1;
P->data[P->num].col = j + 1;
// 把稀疏矩陣中的非零元個數(shù)加一
P->num++;
}
}
}
return P;
}
// 以三元組的方式輸出稀疏矩陣
void TSMatrix_PrintTriple(
19、TSMatrix *M)
{
int i;
if (0 == M->num)
{
printf("稀疏矩陣為空！\n");
return;
}
printf(" i j v \n");
printf("===============\n");
for (i = 0; i < M->num; i++)
{
printf("%3d %3d %3d\n", M->data[i].row, M->data[i].col, M->data[i].e);
}
printf("===============\n");
}
// 求稀疏矩
20、陣 M 的轉(zhuǎn)置矩陣 T
int TSMatrix_FastTranspose(TSMatrixM, TSMatrix *T)
{
int *num, *cpot, i, t;
// 如果矩陣 M 為空矩陣，返回錯誤信息
if (M.num == 0)
returnEMPTY_MATRIX;
// 分配臨時的工作空間
num = (int *)malloc((M.colnum + 1) * sizeof(int));
cpot = (int *)malloc((M.colnum + 1) * sizeof(int));
// 如果臨時的工作空間分配不成功
if
21、(num == NULL || cpot == NULL)
returnMALLOC_FAIL;
// 初始化臨時工作空間〔把 num 數(shù)組用 0 填充〕
for (i = 1; i <= M.rownum; i++)
num[i] = 0;
// 統(tǒng)計倒置后每行的元素數(shù)量〔即統(tǒng)計倒置前矩陣每列元素的數(shù)量〕
for (i = 1; i <= M.num; i++)
num[M.data[i - 1].col]++;
// 設(shè)置 T 矩陣每行首個非零元的位置
cpot[1] = 0;
for (i = 2; i <= M.colnum; i++)
cpot[i]
22、 = cpot[i - 1] + num[i - 1];
// 把 T 矩陣的信息清空
TSMatrix_Init(T);
// 把矩陣 M 的信息填充到 T 中。
// 矩陣倒置以后，T 的行數(shù)等于 M 的列數(shù)，T 的列數(shù)等于 M 的行數(shù)
T->num = M.num;
T->colnum = M.rownum;
T->rownum = M.colnum;
// 對 M 矩陣中每個非零元素進展轉(zhuǎn)置操作
for (i = 0; i < M.num; i++)
{
t = cpot[M.data[i].col];
T->data[t].col = M.da
23、ta[i].row;
T->data[t].row = M.data[i].col;
T->data[t].e = M.data[i].e;
++cpot[M.data[i].col];
}
// 轉(zhuǎn)置完成后釋放臨時工作空間
free(num);
free(cpot);
returnOK;
}
// 如果稀疏矩陣 M 和 N 的行數(shù)的列數(shù)一樣，計算 Q = M + N
int TSMatrix_Add(TSMatrixM, TSMatrixN, TSMatrix *Q)
{
int i = 0, j = 0, k = 0;
if (M.colnu
24、m != N.colnum || M.rownum != N.rownum)
returnMATRIX_NOT_MATCH;
// 填充結(jié)果矩陣信息
TSMatrix_Init(Q);
Q->colnum = M.colnum;
Q->rownum = M.rownum;
Q->num = 0;
while (i < M.num && j < N.num)
{
// 如果 i j 指向元素是同一行的元素
if (M.data[i].row == N.data[j].row)
{
// 如果 i 和 j 指向的元素指向的是同一個元素
if (M.data[i].
25、col == N.data[j].col)
{
Q->data[k].row = M.data[i].row;
Q->data[k].col = M.data[i].col;
Q->data[k].e = M.data[i].e + N.data[j].e;
Q->num++;
i++;
j++;
k++;
}
// 如果 i 指向元素的列下標大于 j 指向元素的列下標
// 把下標小〔j 指向的元素〕的放入到 Q 矩陣中
elseif (M.data[i].col > N.data[j].col)
{
Q->data[k].row = N.data[j].ro
26、w;
Q->data[k].col = N.data[j].col;
Q->data[k].e = N.data[j].e;
Q->num++;
j++;
k++;
}
// 如果 i 指向元素的列下標小于 j 指向元素的列下標
// 把下標小〔i 指向的元素〕的放入到 Q 矩陣中
elseif (M.data[i].col < N.data[j].col)
{
Q->data[k].row = M.data[i].row;
Q->data[k].col = M.data[i].col;
Q->data[k].e = M.data[i].e;
Q->num++;
27、
i++;
k++;
}
}
// 如果 i 指向的元素行下標大于 j 指向元素的行下標
elseif (M.data[i].row > N.data[j].row)
{
Q->data[k].row = N.data[j].row;
Q->data[k].col = N.data[j].col;
Q->data[k].e = N.data[j].e;
Q->num++;
k++;
j++;
}
// 如果 i 指向元素行下標小于 j 指向元素的行下標
elseif (M.data[i].row < N.data[j].row)
{
Q->data[
28、k].row = M.data[i].row;
Q->data[k].col = M.data[i].col;
Q->data[k].e = M.data[i].e;
Q->num++;
i++;
k++;
}
}
// 如果還有剩余元素，按順序把元素添加到結(jié)果矩陣中
while (i < M.num)
{
Q->data[k].row = M.data[i].row;
Q->data[k].col = M.data[i].col;
Q->data[k].e = M.data[i].e;
Q->num++;
i++;
k++;
}
while
29、 (j < N.num)
{
Q->data[k].row = N.data[j].row;
Q->data[k].col = N.data[j].col;
Q->data[k].e = N.data[j].e;
Q->num++;
j++;
k++;
}
returnOK;
}
// 如果稀疏矩陣 M 的列數(shù)等于 N 的行數(shù)，計算 Q = M x N;
int TSMatrix_Multply(TSMatrixM, TSMatrixN, TSMatrix *Q)
{
int *num_m, *cpot_m, *num_n, *cpot_n, i,
30、j, k, s, col;
int a, ri, rj;
// 如果兩個矩陣不滿足矩陣相乘的條件，返回錯誤信息
if (M.colnum != N.rownum)
returnMATRIX_NOT_MATCH;
// 分配臨時空間
num_m = (int *)malloc((M.rownum + 1) * sizeof(int));
cpot_m = (int *)malloc((M.rownum + 1) * sizeof(int));
num_n = (int *)malloc((N.rownum + 1) * sizeof(int));
cpot_n = (i
31、nt *)malloc((N.rownum + 1) * sizeof(int));
// 填充結(jié)果矩陣的信息
TSMatrix_Init(Q);
Q->rownum = M.rownum;
Q->colnum = N.colnum;
Q->num = 0;
// 如果相乘為零矩陣，直接返回
if (0 == M.num * N.num)
returnOK;
// 初始化臨時空間
for (i = 1; i <= M.colnum; i++)
num_m[i] = 0;
for (i = 1; i <= N.colnum; i++)
num_n[i
32、] = 0;
// 計算矩陣每行非零元元素的數(shù)量
for (i = 0; i < M.num; i++)
num_m[M.data[i].row]++;
for (i = 0; i < N.num; i++)
num_n[N.data[i].row]++;
cpot_m[1] = cpot_n[1] = 0;
for (i = 2; i <= M.rownum; i++)
cpot_m[i] = cpot_m[i - 1] + num_m[i - 1];
for (i = 2; i <= N.rownum; i++)
cpot_n[i] = cpot_n
33、[i - 1] + num_n[i - 1];
// 計算過程
for (i = 1; i <= M.rownum; i++)
{
// 表示相乘結(jié)果在矩陣中的行下標
ri = i;
for (j = cpot_m[i]; j < cpot_m[i] + num_m[i]; j++)
{
// 初始化累加器
s = 0;
// 表示相乘結(jié)果在矩陣中的列下標
rj = M.data[j].col;
// 獲得第 i 行首個非零元素的位置
k = cpot_m[i];
// 對該行的每個元素進展相乘操作并累加
while (k - cpot_m[i
34、] < num_m[i])
{
col = M.data[k].col;
a = cpot_n[col];
// 如果 a 指向元素仍然屬于第 a 元素
// 遍歷，找到符合條件的元素相乘，并把相乘結(jié)果累加到累加器中
while (a - cpot_n[col] < num_n[col])
{
if (N.data[a].row == M.data[j].col)
{
s = s + (M.data[j].e * N.data[a].e);
}
a++;
}
k++;
}
if (s != 0)
{
Q->data[Q->num].row
35、 = ri;
Q->data[Q->num].col = rj;
Q->data[Q->num].e = s;
Q->num++;
}
}
}
// 處理完成后釋放臨時空間
free(num_m);
free(cpot_m);
free(num_n);
free(cpot_n);
returnOK;
}
// 以矩陣的方式輸出稀疏矩陣
void TSMartix_PrintMatrix(TSMatrix *M)
{
int count, i, k;
// 求出原矩陣的元素個數(shù)
count = M->colnum * M->rownum;
36、
k = 0;
for (i = 0; i < count; i++)
{
// 如果發(fā)現(xiàn)對應(yīng)位置的非零元
if (M->data[k].row == ((i / M->colnum) + 1) &&
M->data[k].col == ((i % M->colnum) + 1))
{
printf("%3d", M->data[k].e);
k++;
}
else
{
printf("%3d", 0);
}
if ((i % M->colnum) + 1 == M->colnum)
printf("\n");
}
}
TSMatrix *T
37、SMatrix_CreateFromInput()
{
int *a, i, j, k;
TSMatrix *T;
ResetCursor();
printf("請輸入新創(chuàng)建的矩陣的行數(shù)和列數(shù)，分別輸入并利用空格間開：");
// 輸入的同時對數(shù)據(jù)的有效性進展檢查
while (2 != scanf("%d%d", &i, &j))
printf("無效輸入，請重新輸入！\n");
// 分配臨時儲存輸入數(shù)據(jù)的空間
a = (int *)malloc(i * j * sizeof(int));
// 如果分配失敗，如此返回一個空指針
if (a == N
38、ULL)
returnNULL;
// 開始從鍵盤中讀入元素
for (k = 0; k < i * j; k++)
{
ResetCursor();
printf("請從鍵盤輸入第 %d 行第 %d 列元素：", (k / j) + 1, (k % j) + 1);
while (1 != scanf("%d", (a + k)))
{
printf("無效輸入，請重新輸入！\n");
}
}
T = TSMatrix_Create(a, i, j);
// 釋放用于臨時儲存輸入的空間
free(a);
return T;
}
/
39、/ 把光標位置移動到該行行首
void ResetCursor()
{
HANDLE hOut;
COORD cTarget;
CONSOLE_SCREEN_BUFFER_INFO info;
int y = 0;
hOut = GetStdHandle(STD_OUTPUT_HANDLE);
GetConsoleScreenBufferInfo(hOut, &info);
y = info.dwCursorPosition.Y;
cTarget.X = 0;
cTarget.Y = y;
SetConsoleCursorPosition(hOut, cTarget);
}
29 / 29
稀疏矩陣基本操作 實驗資料報告材料
