1、計算機學院（軟件學院）實驗報告學生姓名學號實驗成績專業19計科班級2班實驗日期年 月 日課程名稱數據結構與算法任課教師實驗名稱稀疏矩陣基本操作實驗序號實驗地點S510實驗臺號指導教師一、實驗目的及要求宋體，五號字體，行間距：固定值20磅同上實驗目的1. 深入了解數組的存儲表示和實現。2掌握稀疏矩陣的特點(三元組存儲方法)。實驗要求1.課下完成實驗程序的編寫，實驗室調試驗證；2.實驗完成后填寫實驗報告。二、實驗內容（或實驗原理、實驗拓撲）1. 稀疏矩陣的存儲及轉置運算，完成教材實驗題6.1。 三、實驗設備與環境WindowsDEV-C+四、實驗設計方案（包括實驗步驟、設計思想、算法描述或開發流程

2、等）定義一個三元組：typedef struct int r; / 行號 int c; / 列號 ElemType d; / 元素值TupNode; / 三元組定義typedef struct int rows; / 行數值 int cols; / 列數值 int nums; / 非零元素個數 TupNode dataMAX_SIZE;TSMatrix; / 三元組順序表定義算法思路（過程）：/*-產生稀疏矩陣A的三元組表示t-*/static void create_matrix(TSMatrix &t, ElemType ANN) int i, j; t.rows = N; / 行數值 t

3、.cols = N; / 列數值 t.nums = 0; / 非零元素個數 for(i = 0; i N; i+) for(j = 0; j N; j+) if(Aij != 0) t.datat.nums.r = i; / 行號 t.datat.nums.c = j; / 列號 t.datat.nums.d = Aij; / 元素值 t.nums+; / 非零元素個數增1 /*-輸出三元組表示t-*/static void disp_matrix(TSMatrix t) int i; if(t.nums = 0) return; printf(t%dt%dt%dn, t.rows, t.co

4、ls, t.nums); printf(t-n); for(i = 0; i t.nums; i+) printf(t%dt%dt%dn, t.datai.r, t.datai.c, t.datai.d);/*-求三元組表示t的轉置矩陣tb-*/* 轉置矩陣:* 把矩陣A的行換成相應的列，得到的新矩陣稱為A的轉置矩陣。*/static void tran_matrix(TSMatrix t, TSMatrix &tb) int p, v; int q = 0; / q為tb.data的下標 tb.rows = t.cols; / 轉置矩陣行數值 tb.cols = t.rows; / 轉置矩陣

5、列數值 tb.nums = t.nums; / 轉置矩陣非零元素個數 if(t.nums != 0) for(v = 0; v t.cols; v+) / tb.dataq中的記錄以c域的次序排列 for(p = 0; p t.nums; p+) / p為t.data的下標 if(t.datap.c = v) tb.dataq.r = t.datap.c; / 轉置矩陣的行號 tb.dataq.c = t.datap.r; / 轉置矩陣的列號 tb.dataq.d = t.datap.d; / 轉置矩陣的元素值 q+; /*-求c=a+b-*/static bool matrix_add(TS

6、Matrix a, TSMatrix b, TSMatrix &c) / 引用類型形參c int i = 0; / a中非零元素個數索引 int j = 0; / b中非零元素個數索引 int k = 0; / c中非零元素個數 ElemType v; if(a.rows != b.rows | a.cols != b.cols) / 行數或列數不等時不能進行相加運算 return false; / c的行列數與a的相同 c.rows = a.rows; c.cols = a.cols; while(i a.nums & j b.nums) / 處理a和b中的元素(假設 a.nums = 6,

7、 b.nums = 4) if(a.datai.r = b.dataj.r) / a元素的行號等于b元素的行號 if(a.datai.c b.dataj.c) / a元素的列號大于b元素的列號 / 將b元素添加到c中 c.datak.r = b.dataj.r; c.datak.c = b.dataj.c; c.datak.d = b.dataj.d; k+; j+; else / a元素的列號等于b元素的列號 v = a.datai.d + b.dataj.d; if(v != 0) / 只將不為0的結果添加到c中 c.datak.r = a.datai.r; c.datak.c = a.d

8、atai.c; c.datak.d = v; k+; i+; j+; else if(a.datai.r b.dataj.r) / a元素的行號小于b元素的行號 / 將a元素添加到c中 c.datak.r = a.datai.r; c.datak.c = a.datai.c; c.datak.d = a.datai.d; k+; i+; else / a元素的行號大于b元素的行號 / 將b元素添加到c中 c.datak.r = b.dataj.r; c.datak.c = b.dataj.c; c.datak.d = b.dataj.d; k+; j+; c.nums = k; return

9、true;/*-返回三元組t表示的Aij值-*/static int get_value(TSMatrix t, int i, int j) int k = 0; while(k t.nums & (t.datak.r != i | t.datak.c != j) k+; if(k t.nums) return t.datak.d; else return 0;/*-求c=a*b-*/static bool matrix_mul(TSMatrix a, TSMatrix b, TSMatrix &c) / 引用類型形參c int i; int j; int k; int p = 0; / 矩陣

10、c的非零元素個數 ElemType s; if(a.cols != b.rows) / a的列數不等于b的行數時不能進行乘法運算 return false; for(i = 0; i a.rows; i+) / 矩陣c的行數 for(j = 0; j b.cols; j+) / 矩陣c的列數 s = 0; for(k = 0; k a.cols; k+) s = s + get_value(a, i, k) * get_value(b, k, j); / 求三元組元素 if(s != 0) / 產生一個三元組元素 c.datap.r = i; / 三元組元素的行號 c.datap.c = j;

11、 / 三元組元素的列號 c.datap.d = s; / 三元組元素的元素值 p+; c.rows = a.rows; c.cols = b.cols; c.nums = p; / 矩陣c的非零元素個數 return true;五、實驗結果（包括設計效果、測試數據、運行結果等）1.6.1可以截取運行效果圖。圖片大小要適中，放置圖片時，不要撐大表格。六、實驗小結（包括收獲、心得體會、注意事項、存在問題及解決辦法、建議等） 通過這節的上機學習，理解了數組和一般線性表的異同，掌握稀疏矩陣的各種存儲結構及其特點。深入了解數組的存儲表示和實現。，掌握稀疏矩陣的特點(三元組存儲方法)。整體上實現程序的運行

12、上掌握的還是不好，還需要繼續努力，繼續學習。七、附錄（包括作品、流程圖、源程序及命令清單等）此處可以放置完成實驗內容的核心代碼，字體用：Times New Roman，行間距20磅#include #include #define N 4#define MAX_SIZE 100 / 矩陣中非零元素最多個數typedef int ElemType;typedef struct int r; / 行號 int c; / 列號 ElemType d; / 元素值TupNode; / 三元組定義typedef struct int rows; / 行數值 int cols; / 列數值 int num

13、s; / 非零元素個數 TupNode dataMAX_SIZE;TSMatrix; / 三元組順序表定義/*-產生稀疏矩陣A的三元組表示t-*/static void create_matrix(TSMatrix &t, ElemType ANN) int i, j; t.rows = N; / 行數值 t.cols = N; / 列數值 t.nums = 0; / 非零元素個數 for(i = 0; i N; i+) for(j = 0; j N; j+) if(Aij != 0) t.datat.nums.r = i; / 行號 t.datat.nums.c = j; / 列號 t.da

14、tat.nums.d = Aij; / 元素值 t.nums+; / 非零元素個數增1 /*-輸出三元組表示t-*/static void disp_matrix(TSMatrix t) int i; if(t.nums = 0) return; printf(t%dt%dt%dn, t.rows, t.cols, t.nums); printf(t-n); for(i = 0; i t.nums; i+) printf(t%dt%dt%dn, t.datai.r, t.datai.c, t.datai.d);/*-求三元組表示t的轉置矩陣tb-*/* 轉置矩陣:* 把矩陣A的行換成相應的列，

15、得到的新矩陣稱為A的轉置矩陣。*/static void tran_matrix(TSMatrix t, TSMatrix &tb) int p, v; int q = 0; / q為tb.data的下標 tb.rows = t.cols; / 轉置矩陣行數值 tb.cols = t.rows; / 轉置矩陣列數值 tb.nums = t.nums; / 轉置矩陣非零元素個數 if(t.nums != 0) for(v = 0; v t.cols; v+) / tb.dataq中的記錄以c域的次序排列 for(p = 0; p t.nums; p+) / p為t.data的下標 if(t.da

16、tap.c = v) tb.dataq.r = t.datap.c; / 轉置矩陣的行號 tb.dataq.c = t.datap.r; / 轉置矩陣的列號 tb.dataq.d = t.datap.d; / 轉置矩陣的元素值 q+; /*-求c=a+b-*/static bool matrix_add(TSMatrix a, TSMatrix b, TSMatrix &c) / 引用類型形參c int i = 0; / a中非零元素個數索引 int j = 0; / b中非零元素個數索引 int k = 0; / c中非零元素個數 ElemType v; if(a.rows != b.row

17、s | a.cols != b.cols) / 行數或列數不等時不能進行相加運算 return false; / c的行列數與a的相同 c.rows = a.rows; c.cols = a.cols; while(i a.nums & j b.nums) / 處理a和b中的元素(假設 a.nums = 6, b.nums = 4) if(a.datai.r = b.dataj.r) / a元素的行號等于b元素的行號 if(a.datai.c b.dataj.c) / a元素的列號大于b元素的列號 / 將b元素添加到c中 c.datak.r = b.dataj.r; c.datak.c = b

18、.dataj.c; c.datak.d = b.dataj.d; k+; j+; else / a元素的列號等于b元素的列號 v = a.datai.d + b.dataj.d; if(v != 0) / 只將不為0的結果添加到c中 c.datak.r = a.datai.r; c.datak.c = a.datai.c; c.datak.d = v; k+; i+; j+; else if(a.datai.r b.dataj.r) / a元素的行號小于b元素的行號 / 將a元素添加到c中 c.datak.r = a.datai.r; c.datak.c = a.datai.c; c.data

19、k.d = a.datai.d; k+; i+; else / a元素的行號大于b元素的行號 / 將b元素添加到c中 c.datak.r = b.dataj.r; c.datak.c = b.dataj.c; c.datak.d = b.dataj.d; k+; j+; c.nums = k; return true;/*-返回三元組t表示的Aij值-*/static int get_value(TSMatrix t, int i, int j) int k = 0; while(k t.nums & (t.datak.r != i | t.datak.c != j) k+; if(k t.n

20、ums) return t.datak.d; else return 0;/*-求c=a*b-*/static bool matrix_mul(TSMatrix a, TSMatrix b, TSMatrix &c) / 引用類型形參c int i; int j; int k; int p = 0; / 矩陣c的非零元素個數 ElemType s; if(a.cols != b.rows) / a的列數不等于b的行數時不能進行乘法運算 return false; for(i = 0; i a.rows; i+) / 矩陣c的行數 for(j = 0; j b.cols; j+) / 矩陣c的列數 s = 0; for(k = 0; k a.cols; k+) s = s + get_value(a, i, k) * get_value(b, k, j); /