稀疏矩陣基本操作實(shí)驗(yàn)報(bào)告

1、稀疏矩陣基本操作 實(shí)驗(yàn)報(bào)告 一、 實(shí)驗(yàn)內(nèi)容稀疏矩陣的壓縮儲(chǔ)存結(jié)構(gòu)，以及稀疏矩陣的三元組表表示方法下的轉(zhuǎn)置、相加、相乘等算法二、 實(shí)驗(yàn)?zāi)康?. 熟悉數(shù)組、矩陣的定義和基本操作2. 熟悉稀疏矩陣的儲(chǔ)存方式和基本運(yùn)算3. 理解稀疏矩陣的三元組表類(lèi)型定義，掌握稀疏矩陣的輸入、輸出和轉(zhuǎn)置算法三、 實(shí)驗(yàn)原理1. 使用三元組儲(chǔ)存矩陣中的非零元素（三元組分別儲(chǔ)存非零元素的行下標(biāo)，列下標(biāo)和元素值）。除了三元組表本身，儲(chǔ)存一個(gè)稀疏矩陣還需要額外的三個(gè)變量，分別儲(chǔ)存矩陣的非零元個(gè)數(shù)，矩陣的行數(shù)和矩陣的列數(shù)。2. 稀疏矩陣的創(chuàng)建算法：第一步：根據(jù)矩陣創(chuàng)建一個(gè)二維數(shù)組，表示原始矩陣第二步：取出二維數(shù)組中的元素（從第一個(gè)

2、元素開(kāi)始?。?，判斷取出元素是否為非零元素，如果為非零元素，把該非零元素的數(shù)值以及行下標(biāo)和列下表儲(chǔ)存到三元數(shù)組表里，否則取出下一個(gè)元素，重復(fù)該步驟。第三步：重復(fù)第二步，知道二維數(shù)組中所有的元素已經(jīng)取出。3. 稀疏矩陣倒置算法：第一步：判斷進(jìn)行倒置的矩陣是否為空矩陣，如果是，則直接返回錯(cuò)誤信息。第二步：計(jì)算要倒置的矩陣每列非零元素的數(shù)量，存入到num數(shù)組（其中numi 代表矩陣中第i列非零元素的個(gè)數(shù)）。以及倒置后矩陣每行首非零元的位置，存入cpot數(shù)組中（其中cpot表示倒置后矩陣每行非零元的位置，對(duì)應(yīng)表示原矩陣每列中第一個(gè)非零元的位置）。第三步：確定倒置后矩陣的行數(shù)和列數(shù)。第四步：取出表示要導(dǎo)致

3、矩陣中三元組表元素 e, i, j（第一次取出第一個(gè)，依次取出下一個(gè)元素），從第二步cpot數(shù)組中確定該元素倒置后存放的位置（cpotj），把該元素的行下標(biāo)和列下標(biāo)倒置以后放入新表的指定位置中。cpotj 變量加一。第五步：重復(fù)第四步，直到三元組表中所有的元素都完成倒置。第六步：把完成倒置運(yùn)算的三元組表輸出。4. 稀疏矩陣加法算法：第一步：檢查相加兩個(gè)矩陣的行數(shù)和列數(shù)是否相同，如果相同，則進(jìn)入第二步，否則輸出錯(cuò)誤信息。第二步：定義變量i和j，用于控制三元組表的遍歷。第三步：比較變量矩陣m中第i個(gè)元素和矩陣n中第j個(gè)元素，如果兩個(gè)元素是同一行元素，如果不是則進(jìn)入第四步，如果是，再繼續(xù)比較兩個(gè)元素

4、是否為同一列元素，如果是，把兩個(gè)元素值相加，放到三元組表中；否則把列下表小的元素依次放到三元組表中。進(jìn)入第五步第四步：如果矩陣m中第i個(gè)元素的行下標(biāo)大于矩陣n中第j個(gè)元素的行下標(biāo)，則把矩陣n中第j個(gè)元素所在行的所有非零元素添加到三元組表中；如果矩陣m中第i個(gè)元素的行下標(biāo)小于矩陣n中第j個(gè)元素的下標(biāo)，則把m中第i個(gè)元素所在行的所有非零元素依次添加到三元組表中。第五步：重復(fù)第三步，直到矩陣m和矩陣n中所有元素都非零元素添加到三元組表中。第六步：輸出運(yùn)算結(jié)果5. 稀疏矩陣乘法算法：第一步：檢查矩陣m和矩陣n能否參與乘法運(yùn)算（即矩陣m的列數(shù)等于矩陣n的行數(shù)），如果兩個(gè)矩陣可以參與乘法運(yùn)算，進(jìn)入下一步，

5、否則輸出錯(cuò)誤信息第二步：檢查兩個(gè)矩陣相乘以后是否為零矩陣，如果相乘結(jié)果是零矩陣，直接返回一個(gè)零矩陣。第三步：分別計(jì)算矩陣m和矩陣n中每行非零元的個(gè)數(shù)（分別存放到num_m和num_n數(shù)組中），并計(jì)算出每行首非零元的位置（分別存放到cpot_m和cpot_n中）。第四步：依次取矩陣m中的非零元（第一次取出矩陣m中的第一個(gè)非零元），求出該非零元所在行和所在列乘積的和，然后把值放到結(jié)果三元組表的特定位置。第五步：重復(fù)第四步，直到矩陣m中所有非零元都已經(jīng)參與運(yùn)算。第六步：輸出結(jié)果四、 程序流程圖五、 實(shí)驗(yàn)結(jié)果5.1 程序主菜單5.2 稀疏矩陣三元組的創(chuàng)建和倒置5.3 稀疏矩陣的加法運(yùn)算并以三元組輸出結(jié)

6、果5.4 稀疏矩陣的乘法運(yùn)算并以矩陣方式輸出結(jié)果六、 操作說(shuō)明1. 在創(chuàng)建稀疏矩陣的時(shí)候，可以每次輸入一個(gè)數(shù)據(jù)，也可以一次輸入多個(gè)數(shù)據(jù)，程序會(huì)自動(dòng)根據(jù)輸入元素的個(gè)數(shù)對(duì)矩陣數(shù)據(jù)進(jìn)行填充2. 每次矩陣運(yùn)算失敗時(shí)（無(wú)論是輸入的矩陣不符合矩陣運(yùn)算的條件，參與運(yùn)算其中一個(gè)矩陣為空矩陣，或者分配不到臨時(shí)空間），程序都會(huì)返回到主菜單。輸入的數(shù)據(jù)都會(huì)被清空。七、 附錄：代碼#include #include #include #define maxsize 1000#define ok 0#define malloc_fail -1/ 表示分配空間時(shí)發(fā)生錯(cuò)誤#define empty_matrix -2/ 表

7、示正嘗試對(duì)一個(gè)空矩陣進(jìn)行運(yùn)算操作#define matrix_not_match -3/ 表示嘗試對(duì)不符合運(yùn)算條件的矩陣進(jìn)行運(yùn)算操作（例如非相同行數(shù)列數(shù)矩陣相加）/* - 結(jié)構(gòu)體聲明部分 - */typedef structint row;/ 非零元的行下標(biāo)int col;/ 非零元的列下標(biāo)int e;/ 非零元的值 triple;typedef structtriple *data;/ 非零元素的元素表int rownum;/ 矩陣的行數(shù)int colnum;/ 矩陣的列數(shù)int num;/ 矩陣非零元的個(gè)數(shù) tsmatrix, *ptsmatrix;/* - 函數(shù)聲明部分 - */ 初始化

8、稀疏矩陣結(jié)構(gòu)int tsmatrix_init(tsmatrix *m);/ 以三元組的方式輸出稀疏矩陣void tsmatrix_printtriple(tsmatrix *m);/ 以矩陣的方式輸出稀疏矩陣void tsmartix_printmatrix(tsmatrix *m);/ 從一個(gè)二維數(shù)組（普通矩陣）創(chuàng)建一個(gè)稀疏矩陣tsmatrix *tsmatrix_create(int *a, int row, int col);/ 從鍵盤(pán)錄入數(shù)據(jù)創(chuàng)建一個(gè)稀疏矩陣tsmatrix *tsmatrix_createfrominput();/ 求稀疏矩陣 m 的轉(zhuǎn)置矩陣 tint tsmatr

9、ix_fasttranspose(tsmatrix m, tsmatrix *t);/ 如果稀疏矩陣 m 和 n 的行數(shù)的列數(shù)相同，計(jì)算 q = m + nint tsmatrix_add(tsmatrix m, tsmatrix n, tsmatrix *q);/ 如果稀疏矩陣 m 的列數(shù)等于 n 的行數(shù)，計(jì)算 q = m x n;int tsmatrix_multply(tsmatrix m, tsmatrix n, tsmatrix *q);/ 把光標(biāo)位置移動(dòng)到該行行首void resetcursor();/* - 程序主函數(shù) - */int main(void)int info;cha

10、r ch;/ 從一個(gè)二維數(shù)組創(chuàng)建一個(gè)系數(shù)矩陣tsmatrix *m;tsmatrix *n;/ 用來(lái)接收運(yù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. 矩陣的加法運(yùn)算并以三元組輸出結(jié)果n);printf(3. 矩陣的乘法運(yùn)算并以矩陣輸出結(jié)果n);printf(n);printf(q. 退出程序n);printf(n);printf( 請(qǐng)輸入選項(xiàng)：);sca

11、nf(%c, &ch);switch (ch)case 1:system(cls);m = tsmatrix_createfrominput();if (m != null)printf(nn以三元組輸出稀疏矩陣：n);tsmatrix_printtriple(m);printf(n倒置后稀疏矩陣的三元組輸出：n);tsmatrix_fasttranspose(*m, t);tsmatrix_printtriple(t);system(pause);elseprintf(創(chuàng)建矩陣過(guò)程發(fā)生錯(cuò)誤);system(pause);break;case 2:system(cls);m = tsmatri

12、x_createfrominput();n = tsmatrix_createfrominput();if (m = null | n = null)printf(創(chuàng)建矩陣過(guò)程中發(fā)生錯(cuò)誤！n);system(pause);break;info = tsmatrix_add(*m, *n, t);if (info = matrix_not_match)printf(這兩個(gè)矩陣不能運(yùn)算呢！ n);else if (info = ok)printf(n運(yùn)算結(jié)果：n);tsmatrix_printtriple(t);system(pause);break;case 3:system(cls);m =

13、tsmatrix_createfrominput();n = tsmatrix_createfrominput();if (m = null | n = null)printf(創(chuàng)建矩陣過(guò)程中發(fā)生錯(cuò)誤！n);system(pause);break;info = tsmatrix_multply(*m, *n, t);if (info = matrix_not_match)printf(這兩個(gè)矩陣不能運(yùn)算呢！ n);else if (info = ok)printf(n運(yùn)算結(jié)果：n);tsmartix_printmatrix(t);system(pause);break;case q:case

14、q:exit(0);return 0;/ 初始化稀疏矩陣結(jié)構(gòu)int tsmatrix_init(tsmatrix *m)m-data = (triple *)malloc(maxsize * sizeof(triple);if (!m-data)return malloc_fail;m-num = 0;m-colnum = 0;m-rownum = 0;return ok;/ 從一個(gè)二維數(shù)組創(chuàng)建一個(gè)稀疏矩陣tsmatrix *tsmatrix_create(int *a, int row, int col)int i, j;tsmatrix *p = (tsmatrix *)malloc(si

15、zeof(tsmatrix);tsmatrix_init(p);/ 設(shè)置稀疏矩陣的行數(shù)和列數(shù)p-rownum = row;p-colnum = col;for (i = 0; i row; i+)for (j = 0; j datap-num.e = *(a + i * col + j);p-datap-num.row = i + 1;p-datap-num.col = j + 1;/ 把稀疏矩陣中的非零元個(gè)數(shù)加一p-num+;return p;/ 以三元組的方式輸出稀疏矩陣void tsmatrix_printtriple(tsmatrix *m)int i;if (0 = m-num)pr

16、intf(稀疏矩陣為空！n);return;printf( i j v n);printf(=n);for (i = 0; i num; i+)printf(%3d %3d %3dn, m-datai.row, m-datai.col, m-datai.e);printf(=n);/ 求稀疏矩陣 m 的轉(zhuǎn)置矩陣 tint tsmatrix_fasttranspose(tsmatrix m, tsmatrix *t)int *num, *cpot, i, t;/ 如果矩陣 m 為空矩陣，返回錯(cuò)誤信息if (m.num = 0)return empty_matrix;/ 分配臨時(shí)的工作空間num

17、= (int *)malloc(m.colnum + 1) * sizeof(int);cpot = (int *)malloc(m.colnum + 1) * sizeof(int);/ 如果臨時(shí)的工作空間分配不成功if (num = null | cpot = null)return malloc_fail;/ 初始化臨時(shí)工作空間（把 num 數(shù)組用 0 填充）for (i = 1; i = m.rownum; i+)numi = 0;/ 統(tǒng)計(jì)倒置后每行的元素?cái)?shù)量（即統(tǒng)計(jì)倒置前矩陣每列元素的數(shù)量）for (i = 1; i = m.num; i+)numm.datai - 1.col+;/

18、 設(shè)置 t 矩陣每行首個(gè)非零元的位置cpot1 = 0;for (i = 2; i num = m.num;t-colnum = m.rownum;t-rownum = m.colnum;/ 對(duì) m 矩陣中每個(gè)非零元素進(jìn)行轉(zhuǎn)置操作for (i = 0; i datat.col = m.datai.row;t-datat.row = m.datai.col;t-datat.e = m.datai.e;+cpotm.datai.col;/ 轉(zhuǎn)置完成后釋放臨時(shí)工作空間free(num);free(cpot);return ok;/ 如果稀疏矩陣 m 和 n 的行數(shù)的列數(shù)相同，計(jì)算 q = m + n

19、int tsmatrix_add(tsmatrix m, tsmatrix n, tsmatrix *q)int i = 0, j = 0, k = 0;if (m.colnum != n.colnum | m.rownum != n.rownum)return matrix_not_match;/ 填充結(jié)果矩陣信息tsmatrix_init(q);q-colnum = m.colnum;q-rownum = m.rownum;q-num = 0;while (i m.num & j datak.row = m.datai.row;q-datak.col = m.datai.col;q-dat

20、ak.e = m.datai.e + n.dataj.e;q-num+;i+;j+;k+;/ 如果 i 指向元素的列下標(biāo)大于 j 指向元素的列下標(biāo)/ 把下標(biāo)?。╦ 指向的元素）的放入到 q 矩陣中else if (m.datai.col n.dataj.col)q-datak.row = n.dataj.row;q-datak.col = n.dataj.col;q-datak.e = n.dataj.e;q-num+;j+;k+;/ 如果 i 指向元素的列下標(biāo)小于 j 指向元素的列下標(biāo)/ 把下標(biāo)?。╥ 指向的元素）的放入到 q 矩陣中else if (m.datai.col datak.ro

21、w = m.datai.row;q-datak.col = m.datai.col;q-datak.e = m.datai.e;q-num+;i+;k+;/ 如果 i 指向的元素行下標(biāo)大于 j 指向元素的行下標(biāo)else if (m.datai.row n.dataj.row)q-datak.row = n.dataj.row;q-datak.col = n.dataj.col;q-datak.e = n.dataj.e;q-num+;k+;j+;/ 如果 i 指向元素行下標(biāo)小于 j 指向元素的行下標(biāo)else if (m.datai.row datak.row = m.datai.row;q-d

22、atak.col = m.datai.col;q-datak.e = m.datai.e;q-num+;i+;k+;/ 如果還有剩余元素，按順序把元素添加到結(jié)果矩陣中while (i datak.row = m.datai.row;q-datak.col = m.datai.col;q-datak.e = m.datai.e;q-num+;i+;k+;while (j datak.row = n.dataj.row;q-datak.col = n.dataj.col;q-datak.e = n.dataj.e;q-num+;j+;k+;return ok;/ 如果稀疏矩陣 m 的列數(shù)等于 n

23、的行數(shù)，計(jì)算 q = m x n;int tsmatrix_multply(tsmatrix m, tsmatrix n, tsmatrix *q)int *num_m, *cpot_m, *num_n, *cpot_n, i, j, k, s, col;int a, ri, rj;/ 如果兩個(gè)矩陣不滿(mǎn)足矩陣相乘的條件，返回錯(cuò)誤信息if (m.colnum != n.rownum)return matrix_not_match;/ 分配臨時(shí)空間num_m = (int *)malloc(m.rownum + 1) * sizeof(int);cpot_m = (int *)malloc(m.r

24、ownum + 1) * sizeof(int);num_n = (int *)malloc(n.rownum + 1) * sizeof(int);cpot_n = (int *)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)return ok;/ 初始化臨時(shí)空間for (i = 1; i = m.colnum; i+)num_mi = 0;

25、for (i = 1; i = n.colnum; i+)num_ni = 0;/ 計(jì)算矩陣每行非零元元素的數(shù)量for (i = 0; i m.num; i+)num_mm.datai.row+;for (i = 0; i n.num; i+)num_nn.datai.row+;cpot_m1 = cpot_n1 = 0;for (i = 2; i = m.rownum; i+)cpot_mi = cpot_mi - 1 + num_mi - 1;for (i = 2; i = n.rownum; i+)cpot_ni = cpot_ni - 1 + num_ni - 1;/ 計(jì)算過(guò)程for

26、(i = 1; i = m.rownum; i+)/ 表示相乘結(jié)果在矩陣中的行下標(biāo)ri = i;for (j = cpot_mi; j cpot_mi + num_mi; j+)/ 初始化累加器s = 0;/ 表示相乘結(jié)果在矩陣中的列下標(biāo)rj = m.dataj.col;/ 獲得第 i 行首個(gè)非零元素的位置k = cpot_mi;/ 對(duì)該行的每個(gè)元素進(jìn)行相乘操作并累加while (k - cpot_mi num_mi)col = m.datak.col;a = cpot_ncol;/ 如果 a 指向元素仍然屬于第 a 元素/ 遍歷，找到符合條件的元素相乘，并把相乘結(jié)果累加到累加器中while

27、(a - cpot_ncol dataq-num.row = ri;q-dataq-num.col = rj;q-dataq-num.e = s;q-num+;/ 處理完成后釋放臨時(shí)空間free(num_m);free(cpot_m);free(num_n);free(cpot_n);return ok;/ 以矩陣的方式輸出稀疏矩陣void tsmartix_printmatrix(tsmatrix *m)int count, i, k;/ 求出原矩陣的元素個(gè)數(shù)count = m-colnum * m-rownum;k = 0;for (i = 0; i datak.row = (i / m-colnum)