实现稀疏矩阵(采用三元组表示)的基本运算实验报告

输出稀疏矩阵的三元组表的总结与反思
近年来，随着稀疏矩阵在计算机科学中的广泛应用，输出稀疏矩阵的三元组表成为了一种常见的数据结构。

三元组表是将稀疏矩阵以行、列、数值的形式存储在一个二维数组中，可以大大减少稀疏矩阵的存储空间，提高计算效率。

在输出稀疏矩阵的三元组表过程中，需要注意以下几点：
1. 三元组表的行数应为非零元素的个数加一，列数固定为3。

2. 需要按照行优先的顺序输出非零元素的行、列和数值。

3. 输出完所有的非零元素后，需要在三元组表的最后一行输出稀疏矩阵的行数、列数和非零元素的个数。

4. 三元组表的输出格式可以根据需要进行调整，可以使用空格或制表符进行分隔，也可以使用换行符进行换行。

在实际应用中，三元组表的输出结果往往需要进行存储或传输，因此需要考虑输出结果的压缩和解压缩。

其中，压缩方法包括利用行压缩法和列压缩法对三元组表进行压缩，以减小存储空间；解压缩方法则是将压缩后的数据进行还原，还原成原始的三元组表。

总之，输出稀疏矩阵的三元组表是一种重要的数据结构，能够大大提高稀疏矩阵的存储效率和计算效率。

在实际应用中，需要根据具体情况选择合适的输出格式和压缩方法，以达到最优的效果。

- 1 -。

1.稀疏矩阵运算器数据结构课程设计任务书针对本课程设计，完成以下课程设计任务：1、熟悉系统实现工具和上机环境。

2、根据课程设计任务，查阅相关资料。

3、针对所选课题完成以下工作：（1）需求分析（2）概要分析（3）详细设计（4）编写源程序（5）静态走查程序和上机调试程序4、书写上述文档和撰写课程设计报告。

3.课程设计报告目录4.正文（1）问题描述稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算频率。

实现一个能进行稀疏矩阵基本运算的运算器。

（2）需求分析本课程设计的稀疏矩阵运算器在visual studio 2013下运行调试成功，可以实现的功能有：1.矩阵运算方式选择2.根据提示输入相应数据3.显示最终结果使用的主要存储结构为三元组，并用三元组形式进行运算。

所有参与运算数据类型为整形，因此输入的数据应为整形数据。

为了节省存储空间使用三元组数据进行运算，可以通过多次扫描三元组数据来实现，即使用嵌套循环函数。

输出结果为通常的阵列形式，因此使用了右对齐，保证输出形式的整齐。

（3）概要分析本次课程设计中定义的结构体typedef struct {int i, j;//矩阵元素所在行列int v;//元素的值}triple;typedef struct {triple data[MAXSIZE];triple cop[MAXSIZE];//辅助数组int m, n, t;//矩阵的行列数}tripletable;Main函数调用子函数时输入1为调用int Push_juzhen(int m, int n, int count)函数，可以实现矩阵相加功能输入2为调用int Dec_juzhen(int m, int n, int count)函数，可实现矩阵相减功能输入3为调用int Mul_juzhen()函数，可以实现矩阵相乘功能（4）详细分析（流程图伪代码）加法函数int Push_juzhen(int m, int n, int count)//矩阵相加（行，列，矩阵数）{// p行，q列，s非零元素个数，v元素值//ucount对数组下标计数的变量，与变量x实现多个矩阵相加for (int c = 0; c < count; c++){int x = 0;cout << "请输入第" << c + 1 << "个矩阵的非零元素个数" << endl;cin >> s;cout << "请依次输入非零元素所在行和列以及该非零元素的值并以空格隔开" << endl;for (; x< s; x++)//传递行列及元素值{cin >> p >> q >> v;a.cop[x].i = p;//将p赋值给data[x].ia.cop[x].j = q;//将q赋值给data[x].ja.cop[x].v = v;//将v赋值给data[x].v}//g行//h列for (int g = 1; g <= m;g++)for (int h = 1; h <= n; h++){int l;//存储下标for (l = 0; l < s; l++)//对辅助存储中的三元组进行行逻辑排序，将数据存入a.data{if (a.cop[l].i == g&&a.cop[l].j == h){a.data[u].i = a.cop[l].i;a.data[u].j = a.cop[l].j;a.data[u].v = a.cop[l].v;u++;}}}}//矩阵相加//k为行数//h为列数for (int k = 0; k < u; k++){for (int h = 0; h <= ucount; h++){if (a.data[k].i == b.data[h].i&&a.data[k].j == b.data[h].j)//判断行列是否相等b.data[h].v += a.data[k].v;else{b.data[ucount].i = a.data[k].i;b.data[ucount].j = a.data[k].j;b.data[ucount].v = a.data[k].v;ucount++;//存储空间增加计数}break;//增加一组数据时跳出循环，避免重复计算}}return 0;}相减函数int Dec_juzhen(int m, int n, int count){for (int c = 0; c < count; c++){int x = 0;cout << "请输入第" << c + 1 << "个矩阵的非零元素个数" << endl;cin >> s;cout << "请依次输入非零元素所在行和列以及该非零元素的值并以空格隔开" << endl;for (; x< s; x++)//传递行列及元素值{cin >> p >> q >> v;a.cop[x].i = p;//将p赋值给data[x].ia.cop[x].j = q;//将q赋值给data[x].ja.cop[x].v = v;//将v赋值给data[x].v}//g行//h列if (c != 0){for (int g = 1; g <= m; g++)for (int h = 1; h <= n; h++){int l;//存储下标for (l = 0; l < s; l++)//行逻辑排列{if (a.cop[l].i == g&&a.cop[l].j == h){ a.data[u].i = a.cop[l].i;a.data[u].j = a.cop[l].j;a.data[u].v =- a.cop[l].v;//c>0时为减数矩阵u++;}}}}else{for (int g = 1; g <= m; g++)for (int h = 1; h <= n; h++){int l;//存储下标for (l = 0; l < s; l++){if (a.cop[l].i == g&&a.cop[l].j == h){a.data[u].i = a.cop[l].i;a.data[u].j = a.cop[l].j;a.data[u].v = a.cop[l].v;u++;}}}}}//矩阵减法计算for (int k = 0; k < u; k++){for (int h = 0; h <= ucount; h++){if (a.data[k].i == b.data[h].i&&a.data[k].j == b.data[h].j)//判断行列相等b.data[h].v += a.data[k].v;else{b.data[ucount].i = a.data[k].i;b.data[ucount].j = a.data[k].j;b.data[ucount].v = a.data[k].v;ucount++;}break;}}return 0;}相乘函数int Mul_juzhen(){cout << "请输入第一个矩阵的行列数" << endl;cin >> m >> n;cout << "请输入第一个矩阵的非零元素个数" << endl;cin >> t1;a.m = m;a.n = n;a.t = t1;cout << "请输入第一个矩阵的非零元素所在的行、列、数值并以空格间隔" << endl;for (i=0; i < t1; i++){cin >> p >> q >> v;a.data[i].i = p;//将p赋值给data[x].ia.data[i].j = q;//将q赋值给data[x].ja.data[i].v = v;//将v赋值给data[x].v}cout << "则第二个矩阵的行数为" << a.n << "行" << endl<<endl;cout << "请输入第二个矩阵的列数" << endl;cin >> n;cout << "请输入第二个矩阵的非零元素个数" << endl;cin >> t2;b.m = a.n;b.n = n;b.t = t2;cout << "请输入第二个矩阵的非零元素所在的行、列、数值并以空格间隔" << endl;for (i = 0; i < t2; i++){cin >> p >> q >> v;b.data[i].i = p;//将p赋值给data[x].ib.data[i].j = q;//将q赋值给data[x].jb.data[i].v = v;//将v赋值给data[x].v}i = 0;//i为a、b数组标记，另设k为矩阵相乘元素扫描标记//n为检测相加元素扫描标记，z为存储标记while (i < a.t){int k;for (k = 0; k < b.t; k++){if (a.data[i].j == b.data[k].i)if (i>0){for (n = 0; n < z; n++){if (a.data[i].i == c.data[n].i&&b.data[k].j == c.data[n].j)//判断是否符合相加条件c.data[n].v += a.data[i].v*b.data[k].v;else{c.data[z].i = a.data[i].i;c.data[z].j = b.data[k].j;c.data[z].v = a.data[i].v*b.data[k].v;z++;}}}else{c.data[z].i = a.data[i].i;c.data[z].j= b.data[k].j;c.data[z].v = a.data[i].v*b.data[k].v;z++;}}i++;}return 0;}（5）调试分析（遇到的问题，修改，解决办法，时空复杂度）刚开始，程序仅使用三元组存储，计算过程使用了二维数组，但矩阵相乘会出现错误，矩阵乘法时间复杂度为矩阵一的行数乘以矩阵二的列数（m1*n2）。

数据结构实验报告稀疏矩阵运算实验目的：1.学习并理解稀疏矩阵的概念、特点以及存储方式。

2.掌握稀疏矩阵加法、乘法运算的基本思想和算法。

3.实现稀疏矩阵加法、乘法的算法，并进行性能测试和分析。

实验原理：稀疏矩阵是指矩阵中绝大多数元素为0的矩阵。

在实际问题中，有许多矩阵具有稀疏性，例如文本矩阵、图像矩阵等。

由于存储稀疏矩阵时，对于大量的零元素进行存储是一种浪费空间的行为，因此需要采用一种特殊的存储方式。

常见的稀疏矩阵的存储方式有三元组顺序表、十字链表、行逻辑链接表等。

其中，三元组顺序表是最简单直观的一种方式，它是将非零元素按行优先的顺序存储起来，每个元素由三个参数组成：行号、列号和元素值。

此外，还需要记录稀疏矩阵的行数、列数和非零元素个数。

稀疏矩阵加法的原理是将两个稀疏矩阵按照相同的行、列顺序进行遍历，对于相同位置的元素进行相加，得到结果矩阵。

稀疏矩阵乘法的原理是将两个稀疏矩阵按照乘法的定义进行计算，即行乘以列的和。

实验步骤：1.实现稀疏矩阵的三元组顺序表存储方式，并完成稀疏矩阵的初始化、转置、打印等基本操作。

2.实现稀疏矩阵的加法运算，并进行性能测试和分析。

3.实现稀疏矩阵的乘法运算，并进行性能测试和分析。

4.编写实验报告。

实验结果：经过实验测试，稀疏矩阵的加法和乘法算法都能正确运行，并且在处理稀疏矩阵时能够有效节省存储空间。

性能测试结果表明，稀疏矩阵加法、乘法的运行时间与非零元素个数有关，当非零元素个数较少时，运算速度较快；当非零元素个数较多时，运算速度较慢。

实验分析：稀疏矩阵的运算相对于普通矩阵的运算有明显的优势，可以节省存储空间和运算时间。

在实际应用中，稀疏矩阵的存储方式和运算算法都可以进行优化。

例如，可以采用行逻辑链接表的方式存储稀疏矩阵，进一步减少存储空间的占用；可以采用并行计算的策略加快稀疏矩阵的运算速度。

总结：通过本次实验，我深入学习了稀疏矩阵的概念、特点和存储方式，掌握了稀疏矩阵加法、乘法的基本思想和算法，并通过实验实现了稀疏矩阵的加法、乘法运算。

实验五稀疏矩阵三元组表的操作科目：数据结构实验和课程设计班级： 10信管姓名：徐杨学号：2010110450 实验目的：会定义稀疏矩阵的三元组表。

熟悉C语言程序的基本结构，掌握程序中的用户头文件、文件之间的相互关系及各自的作用。

熟悉对稀疏矩阵的三元组表的一些基本操作和具体的函数定义。

熟悉C语言操作环境的使用以及多文件程序的输入、编辑、调试和运行的全过程。

实验要求：认真阅读和掌握本实验内容所给的全部程序。

保存和输出程序运行结果，并结合程序进行分析。

按照你对稀疏矩阵的三元组表操作的需要，编写程序代码然后运行，给出运行结果。

实验设备：每人一台安装VC6.0编写软件的计算机，公用打印机。

注意事项：要在硬盘上建立好自己的工作目录，专门用来存储自己所做的实验程序及相关数据，以后每次做实验最好仍采用这个目录。

认真编写算法及运行结果，针对本实验的具体算法，认真写出算法分析。

一、实验步骤：#include<iostream.h>//稀疏矩阵三元组表的操作#define maxsize 64#define M#define Ntypedef int elemtype;struct node{int r,c;elemtype d;};struct ts{int rows,cols,nums;node data[maxsize];};void create(ts &a);//稀疏矩阵三元组表的建立void disp(ts a);//显示稀疏矩阵三元组表的内容void trants(ts a,ts &at); //求稀疏矩阵的转置void add(ts a,ts b,ts &c);//求两稀疏矩阵的和void main(){ts a;create(a); //稀疏矩阵三元组表的建立disp(a); //显示稀疏矩阵三元组表的内容ts at;trants(a,at); //求稀疏矩阵的转置disp(at); //显示转置矩阵的内容ts b;create(b);disp(b); //稀疏矩阵三元组表的建立ts c;add(a,b,c); //求两稀疏矩阵的和disp(c); //显示两稀疏矩阵和的内容}void create(ts &a) //稀疏矩阵三元组表的建立{ cout<<"建立稀疏矩阵三元组表:"<<endl;cout<<"稀疏矩阵的行数为:";cin>>a.rows;cout<<"稀疏矩阵列的数为:";cin>>a.cols;cout<<"稀疏矩阵中非零的元素个数为:";cin>>a.nums;cout<<"稀疏矩阵的三元组表为:"<<endl;for(int i=0;i<a.nums;i++){cin>>a.data[i].r>>a.data[i].c>>a.data[i].d;}}void disp(ts a) //显示稀疏矩阵三元组表的内容{ int i;cout<<"显示稀疏矩阵三元组表:"<<endl;if(a.nums<=0) return;cout<<"行数为:"<<a.rows<<" "<<"列数为:"<<a.cols<<" "<<"元素个数为:"<<" "<<a.nums<<endl;cout<<"------------------------"<<endl;for(i=0;i<a.nums;i++)cout<<a.data[i].r<<" "<<a.data[i].c <<" "<<a.data[i].d <<endl;}void trants(ts a,ts &at)//求稀疏矩阵的转置{ int p,q=0,v;at.rows=a.cols;at.cols=a.rows;at.nums=a.nums;if(a.nums!=0){ for(v=0;v<a.cols;v++)for(p=0;p<a.nums;p++)if(a.data[p].c==v){at.data[q].r=a.data[p].c;at.data[q].c=a.data[p].r;at.data[q].d=a.data[p].d;q++;}}cout<<"转置后的稀疏矩阵:"<<endl;}void add(ts a,ts b,ts &c) //求两稀疏矩阵的和{int i=0,j=0,k=0;elemtype v;if (a.rows!=b.rows||a.cols!=b.cols)c.rows=a.rows;c.cols=a.cols;while (i<a.nums&&j<b.nums){if(a.data[i].r==b.data[j].r){if(c.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].d=a.data[i].d;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].d=b.data[j].d;k++;j++;}else{v=a.data[i].d+b.data[j].d;if(v!=0){c.data[k].r=a.data[i].r;c.data[k].c=a.data[i].c;c.data[k].d=v;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].d=a.data[i].d;k++;i++;}else{c.data[k].r=b.data[j].r;c.data[k].c=b.data[j].c;c.data[k].d=b.data[j].d;k++;j++;}c.nums=k;}cout<<"两个稀疏矩阵求和后元素的个数为:"<<c.nums<<endl; }二、运行结果：三、算法分析：。

一、实验目的1. 理解稀疏矩阵的概念及其存储方式。

2. 掌握稀疏矩阵的基本操作，包括转置、加法、减法和乘法。

3. 通过编程实践，提高对数据结构和算法的理解和应用能力。

二、实验环境1. 编程语言：C语言2. 开发环境：Visual Studio 20193. 操作系统：Windows 10三、实验内容1. 稀疏矩阵的三元组表示及其实现2. 稀疏矩阵的转置3. 稀疏矩阵的加法、减法和乘法四、实验步骤1. 稀疏矩阵的三元组表示及其实现（1）定义稀疏矩阵的三元组结构体：```ctypedef struct {int row; // 行号int col; // 列号double val; // 非零元素值} Triple;```（2）定义稀疏矩阵结构体：typedef struct {int rows; // 矩阵行数int cols; // 矩阵列数int nums; // 非零元素个数Triple data; // 非零元素的三元组数组} SparseMatrix;```（3）编写函数实现稀疏矩阵的创建：```cvoid createSparseMatrix(SparseMatrix sm, int rows, int cols, int nums) { sm->rows = rows;sm->cols = cols;sm->nums = nums;sm->data = (Triple )malloc(nums sizeof(Triple));}```（4）编写函数实现稀疏矩阵的销毁：```cvoid destroySparseMatrix(SparseMatrix sm) {free(sm->data);sm->data = NULL;}2. 稀疏矩阵的转置（1）编写函数实现稀疏矩阵的转置：```cvoid transposeSparseMatrix(SparseMatrix src, SparseMatrix dst) {dst->rows = src->cols;dst->cols = src->rows;dst->nums = src->nums;dst->data = (Triple )malloc(src->nums sizeof(Triple));for (int i = 0; i < src->nums; i++) {dst->data[i].row = src->data[i].col;dst->data[i].col = src->data[i].row;dst->data[i].val = src->data[i].val;}}```3. 稀疏矩阵的加法、减法和乘法（1）编写函数实现稀疏矩阵的加法：```cvoid addSparseMatrix(SparseMatrix sm1, SparseMatrix sm2, SparseMatrix result) {result->rows = sm1->rows;result->cols = sm1->cols;result->nums = 0;for (int i = 0; i < sm1->nums; i++) {for (int j = 0; j < sm2->nums; j++) {if (sm1->data[i].row == sm2->data[j].row && sm1->data[i].col == sm2->data[j].col) {if (sm1->data[i].val + sm2->data[j].val != 0) {result->data[result->nums++] = sm1->data[i];result->data[result->nums - 1].val += sm2->data[j].val;}}}}}```（2）编写函数实现稀疏矩阵的减法：```cvoid subSparseMatrix(SparseMatrix sm1, SparseMatrix sm2, SparseMatrix result) {result->rows = sm1->rows;result->cols = sm1->cols;result->nums = 0;for (int i = 0; i < sm1->nums; i++) {for (int j = 0; j < sm2->nums; j++) {if (sm1->data[i].row == sm2->data[j].row && sm1->data[i].col == sm2->data[j].col) {if (sm1->data[i].val - sm2->data[j].val != 0) {result->data[result->nums++] = sm1->data[i];result->data[result->nums - 1].val -= sm2->data[j].val;}}}}}```（3）编写函数实现稀疏矩阵的乘法：```cvoid mulSparseMatrix(SparseMatrix sm1, SparseMatrix sm2, SparseMatrix result) {result->rows = sm1->rows;result->cols = sm2->cols;result->nums = 0;for (int i = 0; i < sm1->nums; i++) {for (int j = 0; j < sm2->nums; j++) {if (sm1->data[i].col == sm2->data[j].row) {double sum = 0;for (int k = 0; k < sm1->nums; k++) {if (sm1->data[k].col == sm2->data[j].row) {sum += sm1->data[k].val sm2->data[j].val;}}if (sum != 0) {result->data[result->nums++] = sm1->data[i];result->data[result->nums - 1].val = sum;}}}}}```五、实验结果与分析1. 通过编程实现稀疏矩阵的基本操作，验证了算法的正确性。

教学单位计算机科学与技术学生学号************数据结构课程设计报告书题目稀疏矩阵运算器学生姓名秦豹专业名称软件工程指导教师李志敏实验目的：深入研究数组的存储表示和实现技术，熟悉广义表存储结构的特性。

需要分析：稀疏矩阵是指那些多数元素为零的矩阵。

利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。

实现一个能进行稀疏矩阵基本运算的运算器。

要求以带“行逻辑链接信息”的三元组顺序表存储稀疏矩阵，实现两矩阵的相加、相减、相乘等运算。

输入以三元组表示，输出以通常的阵列形式列出。

软件平台：Windows 2000，Visual C＋＋6.0或WINTC概要设计：ADT Array {数据对象:D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}数据关系:R = { ROW, COL }ROW = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1}COL = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤j≤b2-2}基本操作：CreateSMatrix(&M); //操作结果:创建稀疏矩阵M.Print SMatrix(M);//初始化条件: 稀疏矩阵M存在.//操作结果:输出稀疏矩阵M.AddSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的和Q=M+N.SubSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M与N的行数和列数对应相等.//操作结果:求稀疏矩阵的差Q=M-N.MultSMatrix(M,N,&Q);//初始化条件: 稀疏矩阵M的列数等于N的行数.//操作结果:求稀疏矩阵的乘积Q=M*N.} ADT Array调试测试：初始界面矩阵的加法矩阵的减法矩阵的转置矩阵的乘法程序源码：#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAXSIZE 40 //假设非零元素个数的最大值为40#define MAXRC 20 //假设矩阵的最大行数为20typedef int ElemType;typedef struct{int i,j; //非零元的行下标和列下标ElemType e; //非零元的值}Triple;typedef struct{Triple data[MAXSIZE+1];int rpos[MAXRC+1]; //各行第一个非零元在三元组的位置表int hs,ls,fls;}TSMatrix,*Matrix;void Creat(TSMatrix &M){int i,k;for(i=1;i<=MAXRC+1;i++)M.rpos[i]=0;printf("请输入矩阵的行数、列数和非零元个数(以空格隔开):");scanf("%d %d %d",&M.hs,&M.ls,&M.fls);for(i=1;i<=M.fls;i++){printf("请用三元组形式输入矩阵的元素(行列非零元素):");scanf("%d %d %d",&M.data[i].i,&M.data[i].j,&M.data[i].e);}for(i=1,k=1;i<=M.hs;i++){M.rpos[i]=k;while(M.data[k].i<=i && k<=M.fls)k++;}}void Xiangjia(TSMatrix A,TSMatrix B,TSMatrix &C,int n){int a,b,temp,l;C.hs=A.hs;C.ls=A.ls;a=b=l=1;while(a<=A.fls && b<=B.fls){if(A.data[a].i==B.data[b].i){if(A.data[a].j<B.data[b].j)C.data[l++]=A.data[a++];else if(A.data[a].j>B.data[b].j){C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;}else{temp=A.data[a].e+n*B.data[b].e;if(temp){C.data[l]=A.data[a];C.data[l].e=temp;l++;}a++;b++;}}else if(A.data[a].i<B.data[b].i)C.data[l++]=A.data[a++];else {C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;} }while(a<=A.fls)C.data[l++]=A.data[a++];while(b<=B.fls){C.data[l]=B.data[b]; C.data[l++].e=n*B.data[b++].e;}C.fls=l-1;}int Xiangcheng(TSMatrix A,TSMatrix B,TSMatrix &Q){int arow,brow,ccol,tp,p,q,t;int ctemp[MAXRC+1];if(A.ls!=B.hs) return 0;Q.hs=A.hs;Q.ls=B.ls;Q.fls=0;if(A.fls*B.fls){for(arow=1;arow<=A.hs;arow++){for(ccol=1;ccol<=Q.ls;ccol++)ctemp[ccol]=0;Q.rpos[arow]=Q.fls+1;if(arow<A.hs) tp=A.rpos[arow+1];else tp=A.fls+1;for(p=A.rpos[arow];p<tp;p++){brow=A.data[p].j;if(brow<B.hs) t=B.rpos[brow+1];else t=B.fls+1;for(q=B.rpos[brow];q<t;q++){ccol=B.data[q].j;ctemp[ccol]+=A.data[p].e*B.data[q].e;}}for(ccol=1;ccol<=Q.ls;ccol++){if(ctemp[ccol]){if(++Q.fls>MAXSIZE) return 0;Q.data[Q.fls].i=arow;Q.data[Q.fls].j=ccol;Q.data[Q.fls].e=ctemp[ccol];}}}}return 1;}void Print_SMatrix(TSMatrix M){int k,l,n;Matrix p;p=&M;for(k=1,n=1;k<=p->hs;k++){for(l=1;l<=p->ls;l++){if(p->data[n].i==k && p->data[n].j==l){printf("%5d",p->data[n].e);n++;}elseprintf("%5d",0);}printf("\n");}printf("\n");}void Zhuanzhi(TSMatrix *a,TSMatrix *b){int q,col,p;b->hs=a->ls;b->ls=a->hs;b->fls=a->fls;if(b->fls){q=1;for(col=1;col<=a->ls;col++)for(p=1;p<=a->fls;p++)if(a->data[p].j==col){b->data[q].i=a->data[p].j;b->data[q].j=a->data[p].i;b->data[q].e=a->data[p].e;++q;}}}void Destory_SMatrix(TSMatrix &M){M.hs=M.ls=M.fls=0;}void main(){TSMatrix A,B,C;TSMatrix *p=&A,*q=&B;int flag,n;while(1){system("cls");printf("\n\n\n");printf("\t┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("\t┃*** 稀疏矩阵的加、减、转、乘*** ┃\n");printf("\t┣━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");printf("\t┃1、稀疏矩阵的加法┃\n");printf("\t┃2、稀疏矩阵的减法┃\n");printf("\t┃3、稀疏矩阵的转置┃\n");printf("\t┃4、稀疏矩阵的乘法┃\n");printf("\t┃5、退出该应用程序┃\n");printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");printf("输入要进行的项目的编号:");scanf("%d",&flag);if(flag==5) break;Creat(A);printf("矩阵A:\n"); Print_SMatrix(A);switch(flag){case 1: Creat(B);n=1;printf("矩阵B:\n");Print_SMatrix(B);if(A.hs==B.hs && A.ls==B.ls){printf("A+B:\n");Xiangjia(A,B,C,n);Print_SMatrix(C);}else printf("错误!行列不一致\n");break;case 2: Creat(B);n=-1;printf("矩阵B:\n");Print_SMatrix(B);if(A.hs==B.hs && A.ls==B.ls){printf("A-B:\n");Xiangjia(A,B,C,n);Print_SMatrix(C);}else printf("错误!行列不一致\n");break;case 3: printf("A->B:\n");Zhuanzhi(p,q);Print_SMatrix(B);break;case 4: Creat(B);printf("矩阵B:\n");Print_SMatrix(B);printf("A*B:\n");n=Xiangcheng(A,B,C);if(!n) printf("错误!行列不匹配\n");else Print_SMatrix(C);break;default: printf("输入错误!\n");}Destory_SMatrix(A);Destory_SMatrix(B);Destory_SMatrix(C);getchar();getchar();}printf("\n\t\t\t ***程序已经退出***\n");getchar();}小结：。

#### 一、实训背景稀疏矩阵在计算机科学和工程领域中有着广泛的应用，特别是在处理大规模数据时，由于其数据压缩的特性，可以显著降低存储空间和计算时间。

稀疏矩阵的转置是稀疏矩阵处理中的一个基本操作，对于理解稀疏矩阵的性质和进行后续的矩阵运算至关重要。

本实训旨在通过实现稀疏矩阵的转置功能，加深对稀疏矩阵数据结构和操作的理解。

#### 二、实训目标1. 理解稀疏矩阵的概念和特点。

2. 掌握稀疏矩阵的三元组表示方法。

3. 实现稀疏矩阵的转置操作。

4. 分析转置操作的算法复杂度。

5. 对比不同转置算法的性能。

#### 三、实训内容1. 稀疏矩阵的三元组表示稀疏矩阵的三元组表示法通过三元组（i, j, e）来存储非零元素，其中i和j分别表示行和列的索引，e表示对应的元素值。

这种方法能够有效地压缩存储空间。

2. 稀疏矩阵的转置稀疏矩阵的转置操作涉及到交换行和列的索引。

具体步骤如下：- 遍历原稀疏矩阵中的所有非零元素。

- 对于每个非零元素（i, j, e），将其存储为（j, i, e）并添加到转置矩阵中。

3. 算法实现使用C++语言实现稀疏矩阵的转置，主要包括以下步骤：- 定义稀疏矩阵的数据结构。

- 实现转置函数。

- 测试转置函数的正确性和效率。

4. 性能分析分析不同转置算法的时间复杂度和空间复杂度，对比不同实现方式的性能。

#### 四、实训过程1. 数据结构设计使用结构体来定义稀疏矩阵的三元组，包括行索引、列索引和元素值。

同时，定义一个数组来存储所有的三元组。

2. 转置函数实现实现一个转置函数，该函数接收一个稀疏矩阵的三元组数组，返回一个新的三元组数组，表示转置后的稀疏矩阵。

3. 测试编写测试代码，创建一个稀疏矩阵实例，调用转置函数，并验证转置后的矩阵是否正确。

4. 性能测试使用不同的稀疏矩阵实例进行性能测试，比较不同实现方式的效率。

#### 五、实训结果与分析1. 结果通过实训，成功实现了稀疏矩阵的转置功能，并验证了其正确性。

数据结构课程设计实习报告题目：班级：学号：姓名：实习报告1．问题描述稀疏矩阵的操作基本功能要求：(1)稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C。

(2)求出A的转置矩阵D，输出D。

2．设计1）设计思想矩阵中如果多数的元素没有数据，则会造成存储器空间的浪费，为此，必须设计稀疏矩阵的阵列储存方式，利用较少的存储器空间储存完整的矩阵数据。

但是这些存储空间的大部分存放的是0元素,从而造成大量的空间浪费.为了节省存储空间,可以只存储其中的非0元素. 对于矩阵Amn的每个元素aij,知道其行号i 和列号j就可以确定其位置.因此对于稀疏矩阵可以用一个结点来存储一个非0元素.该结点可以定义成: [i,j,aij]创建一个矩阵A和矩阵B，这两个稀疏矩阵具有相同行列数，然后矩阵A与矩阵B相加得到矩阵C，并输出C，稀疏矩阵采用三元组表示。

并调用原矩阵A 转置得到矩阵D，输出D。

2) 设计表示法(1) 函数调用关系如图所示。

3）实现注释：实现了原题中要求的：两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；得到矩阵A的转置矩阵D，输出D；稀疏矩阵均采用三元组表示。

3．调试报告调试程序时，应注意矩阵的调用。

比如，开始的时候没有注意将程序调用，最后尽管实现了矩阵的转置和相加，但没有符合题意。

题目要求的是用创建好的矩阵A和矩阵B进行相加，并对矩阵A进行转置，所以要调用好矩阵。

4．程序清单#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100typedef struct{int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu; //mu、nu为稀疏矩阵的行列数，tu为稀疏矩阵的非零元素个数}TSMatrix;TSMatrix M,T,S,B,C;void CreateMatrix(TSMatrix &M){int i,elem,col,row,mu,nu,tu;printf("请输入稀疏矩阵的行数、列数和非零元素的个数:\n");scanf("%d%d%d",&mu,&nu,&tu);M.mu=mu;M.nu=nu;M.tu=tu;for (i=1;i<=tu;i++){printf("请输入非零元素的行号、列号和值:\n");scanf("%d%d%d",&col,&row,&elem);if ( mu<=1 || col>M.mu ||nu<=1 || row>M.nu){printf("error!");exit(0);}else{M.data[i].i=col; //输出这个三元组M.data[i].j=row;M.data[i].e=elem;}}}void FastTransposeSMatrix(TSMatrix M) /*求转置矩阵*/ {int num[100];int cpot[100];int p,q,t,col=0;T.mu=M.nu; // 给T的行、列数与非零元素个数赋值T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;col++){num[col]=0;}for(t=1;t<=M.tu;t++){num[M.data[t].j]++;}cpot[1]=1;for(col=2;col<=M.nu;col++){cpot[col]=cpot[col-1]+num[col-1];}for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;cpot[col]++;}} TSMatrix(T);}void TSMatrix_add(TSMatrix M,TSMatrix T,TSMatrix &ADD) /*求矩阵的和*/ {int a=1,b=1,c=1,x;ADD.mu=M.mu;ADD.nu=M.nu;ADD.tu=0;for(x=1;x<=M.mu;x++){while(M.data[a].i==x&&T.data[b].i==x){if(M.data[a].j==T.data[b].j){ADD.data[c].i=M.data[a].i;ADD.data[c].j=M.data[a].j;ADD.data[c].e=M.data[a].e+T.data[b].e;c++;a++;b++;}else if(M.data[a].j<T.data[b].j){ADD.data[c].i=M.data[a].i;ADD.data[c].j=M.data[a].j;ADD.data[c].e=M.data[a].e;c++;a++;}else{ADD.data[c].i=T.data[b].i;ADD.data[c].j=T.data[b].j;ADD.data[c].e=T.data[b].e;c++;b++;}}while(M.data[a].i==x){ADD.data[c].i=M.data[a].i;ADD.data[c].j=M.data[a].j;ADD.data[c].e=M.data[a].e;c++;a++;while(T.data[b].i==x){ADD.data[c].i=T.data[b].i;ADD.data[c].j=T.data[b].j;ADD.data[c].e=T.data[b].e;c++;b++;}}ADD.tu=c-1;}void ShowMatrix(TSMatrix &M) /*打印出矩阵*/ {int i=1,j=1,dir=1;//printf("稀疏矩阵为:\n");for(i=1;i<=M.mu;i++){for(j=1;j<=M.nu;j++){if(M.data[dir].i==i && M.data[dir].j==j) {printf("%d ",M.data[dir].e);dir++;}elseprintf("0 ");}printf("\n");}void main(){while(1){int c;M.mu=0;M.nu=0;M.tu=0;printf("1.创建一个稀疏矩阵A:\n");printf("2.求转置矩阵A:\n");printf("3.创建一个稀疏矩阵B:\n");printf("4.求转置矩阵B:\n");printf("5.求A与B原矩阵的和:\n"); while (1){printf("请按键选择:");scanf("%d",&c);switch(c){case 1:CreateMatrix(M) ;break;case 2:FastTransposeSMatrix(M);printf("原矩阵A为:\n");ShowMatrix(M);printf("转置矩阵为:\n"); ShowMatrix(T);break;case 3:CreateMatrix(B) ;break;case 4:FastTransposeSMatrix(B);printf("原矩阵B为:\n");ShowMatrix(B);printf("转置矩阵为:\n");ShowMatrix(T);break;case 5:FastTransposeSMatrix(M);TSMatrix_add(M,B,S);printf("A与B原矩阵的和为:\n");ShowMatrix(S);break;return 0;}}}}5．结果分析（1）选择选项1，创建矩阵A；选择选项2，转置矩阵A。