数据结构---三元组顺序表------稀疏矩阵的转置和快速转置

稀疏矩阵三元组快速转置（转poklau123写的很清楚）关于稀疏矩阵的快速转置法，⾸先得明⽩其是通过对三元表进⾏转置。

如果误以为是对矩阵进⾏转置，毫⽆疑问就算你想破脑袋也想不出个所以然，别陷⼊死胡同了！对于⼀个三元表，⾏为i，列为j，值为v。

需将其i与j的值对调才能得到新的三元表，但是如果直接进⾏转换，得到的新的三元表的顺序是混乱的，不符合三元表的规则。

所以，课本⾸先介绍了⼀个⽤扫描来转置的算法（这个算法⽐较容易，在这⾥我就不说了），但是这个转置算法的时间复杂度太⾼，于是就有了接下来的快速转置算法。

要你对⼀个三元表进⾏步骤最少的转置，你可能会想，如果知道三元表中每⼀项在转置后的新的三元表中的位置，然后直接放进去，岂不是极⼤的缩⼩了时间复杂度？没错！快速转置法正是基于这种思想⽽设计的。

那么如何知道三元表中某⼀项的位置呢？在课本98页的a.data这个三元表可以看到，j为列号，在转置后即为新的三元表的⾏号，三元表正是按照⾏序进⾏排列的，⽽j=1有2个、j=2有2个、j=3有2个、j=4有1个、j=6有1个。

根据这些数据按照从⼩到⼤排列，j=1的项在新的三元表中应占据第1、2位，j=2的项在新的三元表中应占据第3、4位，j=3的项在新的三元表中应占据第5、6位，j=4应占据第7位，j=6应占据第8位。

接下来就轻松多了，转置的时候直接从第⼀项读起，读取其j值，⽐如课本中a.data这个三元表的第⼀项的j值为2,因为j=2占据第3、4位，所以应该从第三位开始放，接下来如果读取的某⼀项的j值也是2,就放在第4位。

因为j=2的项只有两个，所以第5位绝对不会被j=2的项占据，第5、6项本来就是留给j=3的。

再⽐如当读到j=6的那项时，第8位是留给它的，就可以直接放进第8位了。

这样，读取每⼀项，都能在三元表中找到相应的位置，这就是稀疏矩阵快速转置的原理。

当然，上⾯只是快速转置的原理，要实现它，就要设计算法来实现了。

稀疏矩阵的三元组顺序表存储表示及其转置算法目录1. 引言1.1 背景和意义1.2 结构概述1.3 目的2. 稀疏矩阵的三元组顺序表存储表示2.1 稀疏矩阵的定义与特点2.2 三元组顺序表的数据结构和实现方式2.3 存储表示的优缺点分析3. 稀疏矩阵转置算法3.1 转置操作的意义与应用场景3.2 基于三元组顺序表的转置算法设计思路3.3 转置算法的具体实现步骤与复杂度分析4. 实验与结果分析4.1 实验设置和数据样本介绍4.2 转置算法在不同稀疏矩阵上的性能评估和结果比较4.3 分析结果及启示与讨论5. 结论与展望5.1 结论总结5.2 存在问题及后续工作展望1. 引言1.1 背景和意义稀疏矩阵是一种在实际问题中经常遇到的特殊矩阵结构，其绝大部分元素为零。

与稠密矩阵相比，稀疏矩阵的存储和计算效率更高。

稀疏矩阵可以应用于图像处理、网络分析、线性代数等领域。

三元组顺序表是一种存储稀疏矩阵的数据结构，通过记录非零元素的行索引、列索引和数值，有效地减少了存储空间。

同时，三元组顺序表也提供了便捷的转置操作方式。

因此，深入掌握稀疏矩阵的三元组顺序表存储表示及其转置算法对于提高稀疏矩阵相关问题的解决效率具有重要意义。

1.2 结构概述本文将从两个方面进行论述。

首先，介绍稀疏矩阵的定义与特点，以及三元组顺序表在存储表示中所采用的数据结构和实现方式。

其次，详细描述了基于三元组顺序表的稀疏矩阵转置算法的设计思路、具体实现步骤和复杂度分析。

1.3 目的本文旨在探究稀疏矩阵的三元组顺序表存储表示及其转置算法，在理论层面上深入分析其原理和优劣，并在实验中验证其性能表现。

通过本文的研究，我们希望能够提供一种高效、灵活且易于实现的方法来处理稀疏矩阵，并为进一步的相关应用提供有价值的启示和参考。

2. 稀疏矩阵的三元组顺序表存储表示2.1 稀疏矩阵的定义与特点稀疏矩阵是指在一个二维矩阵中，大部分元素都为0的情况下，只有少数非零元素的情况。

实验2 稀疏矩阵的建立与转置(一)实验目的掌握特殊矩阵的存储和操作算法。

(二)问题描述实现用三元组保存稀疏矩阵并实现矩阵转置的算法。

(三)实验步骤1. 定义稀疏矩阵的三元组形式的存储结构。

2. 实现三元组矩阵的传统转置算法(pp99 的算法5.1)。

3. 实现三元组矩阵的快速转置算法。

4. 输入矩阵非零元素，测试自己完成的算法。

(四)程序流程图(五)参考代码#include <malloc.h>#include <stdio.h>#define MAXLEN 40typedef struct{ int i, j;int v;}NODE;typedef struct{ int m, n, t;NODE data[MAXLEN];}SPMA TRIX;SPMA TRIX transpose(SPMA TRIX a){/*稀疏矩阵(三元组存储结构)转置算法*/int p, q, col;SPMA TRIX b;b.m=a.n; b.n=a.m; b.t=a.t;if(a.t!=0){q = 1;for (col=1; col<=a.n; col++) //访问b三元组的每一行for (p=1; p<=a.t; p++) //访问a三元组的每一行if(a.data[p].j==col) //如果b三元组的行对应a数组的列，就进行转置{ b.data[q].j=a.data[p].i;b.data[q].i=a.data[p].j;b.data[q].v=a.data[p].v;q++;}}return b;}void printmatrix(SPMA TRIX c){/*稀疏矩阵(三元组存储结构)显示*/int n,i;n=c.t;for(i=1;i<=n;i++)printf("[%d]行号=%d 列号=%d 元素值=%d\n",i,c.data[i].i,c.data[i].j,c.data[i].v);}void main(){ SPMA TRIX a;SPMA TRIX b;int i,j,r,c,t,n;n=1;printf("\n\n输入矩阵行号数: ");scanf("%d",&r);printf("\n\n输入矩阵列号数: ");scanf("%d",&c);a.m=r; a.n=c;printf("\n\n");for(i=0;i<r;i++) /*输入矩阵元素值*/for(j=0;j<c;j++){printf("输入元素[%d,%d]值: ",i+1,j+1);scanf("%d",&t);if(t!=0) {a.data[n].i=i+1; /*非零元素存入稀疏矩阵三元组存储结构中*/a.data[n].j=j+1; a.data[n].v=t; n=n+1;}}n=n-1; a.t=n; /*a.t中为稀疏矩阵非零元素个数*/printf("\n\n稀疏矩阵三元组表示: \n\n");printmatrix(a); /*稀疏矩阵(三元组存储结构)转置*/b=transpose(a);printf("\n\n转置后稀疏矩阵三元组表示: \n\n");printmatrix(b);printf("\n\n");}(六)运行结果(七)心得体会掌握了特殊矩阵的存储和操作原理，编写了用三元组保存稀疏矩阵并实现矩阵转置的算法。

数据结构稀疏矩阵转置,加法《数据结构》实验报告◎实验题⽬:稀疏矩阵的转置、加法（⾏逻辑链接表）◎实验⽬的：学习使⽤三元组顺序表表⽰稀疏矩阵，并进⾏简单的运算◎实验内容：以三元组表表⽰稀疏矩阵，并进⾏稀疏矩阵的转置和加法运算。

⼀、需求分析该程序⽬的是为了⽤三元组表实现稀疏矩阵的转置和加法运算。

1、输⼊时都是以三元组表的形式输⼊；2、输出时包含两种输出形式：运算后得到的三元组表和运算后得到的矩阵；3、测试数据：（1）转置运算时输⼊三元组表：1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7得到转置后的三元组表：1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14（2）进⾏加法运算时先输⼊矩阵A（以三元组表形式）：1 1 12 2 22 3 43 1 -4输⼊矩阵B（以三元组表形式）：1 3 -22 3 -53 1 83 2 -6A与B的和矩阵以矩阵形式输出为：1 0 -20 2 -14 -6 0(⼆) 概要设计为了实现上述操作⾸先要定义三元组表，稀疏矩阵：typedef struct{int i,j;int e;}Triple;//三元组typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;}Matrix;//稀疏矩阵1.基本操作void CreatMatrix(Matrix *m)操作结果：创建⼀个稀疏矩阵。

void PrintMatrix(Matrix m)初始条件：矩阵m已存在。

操作结果：将矩阵m以矩阵的形式输出。

void FastTransposeMatrix(Matrix a,Matrix *b)初始条件：稀疏矩阵a已存在；操作结果：将矩阵a进⾏快速转置后存⼊b中。

void AddMatrix(Matrix a,Matrix b,Matrix *c)初始条件：稀疏矩阵a和b都已存在；操作结果：将矩阵a和b的和矩阵存⼊c中。

稀疏矩阵——三元组顺序表⽬录稀疏矩阵假设m*n的矩阵中，有t的⾮零元，令s=t/m * n,当，s<=0.05时，称此矩阵为稀疏矩阵，简单理解就是⾮零元特别少的矩阵//⼀般矩阵a1 2 3a= 4 5 67 8 9//稀疏矩阵s0 0 0 0 00 2 0 0 5s= 0 0 3 0 00 0 0 0 4矩阵的转置⼀个m * n的矩阵转置后变为 n * m的矩阵//3*2的矩阵-转置前1 24 57 8//转置后变为2*31 4 72 5 8转置后的矩阵每个元素的下表与原来的下表刚好相反，例如上⾯4转置前的下标为（2，1），转置后变为（1，2）；矩阵压缩存储-三元组顺序表之所以引⼊三元组顺序表，是因为，对于稀疏矩阵⽽⾔，⽤传统的存储⽅法会造成存储空间的浪费0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 0M= 0 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0//上⾯矩阵⽤三元组表⽰i j v1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7typedef struct{int i,j; //⾏坐标、列坐标ElemType e; //元素}Triple;typedef struct{Triple date[MAXSIZE+1]; //0不存储元素int mu,nu,tu; //⾏数、列数、⾮零元个数}TSMatrix;稀疏矩阵的转置传统⽅法的转置算法时遍历矩阵的每⼀项，交换其下标值即可for(col=1;col<=nu;col++){for(row=1;row<=mu;row++){T[col][row]=M[row][col]}}//时间复杂度 : O(nu*mu)利⽤三元组顺序表进⾏存储的稀疏矩阵要想实现转置显然不能⽤上⾯的算法，下⾯介绍两种⽅法：第⼀种：以列序为主序的转置//置换前存储位置i j v1 2 12 -> M.date[1]1 3 9 -> M.date[2]3 1 -3 -> M.date[3]3 6 14 -> M.date[4]4 3 24 -> M.date[5]5 2 18 -> M.date[6]6 1 15 -> M.date[7]6 4 -7 -> M.date[8]//置换后存储位置i j v1 3 -3 -> T.date[1]1 6 15 -> T.date[2]2 1 12 -> T.date[3]2 5 18 -> T.date[4]3 1 9 -> T.date[5]3 4 24 -> T.date[6]4 6 -7 -> T.date[7]6 3 14 -> T.date[8]void TransposeSMatrix(TSMatrix *T1,TSMatrix *T2){T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){int q=1,col,p;for(col=1;col<=T1->nu;col++) //矩阵列循环{for(p=1;p<=T1->tu;p++) //遍历所有元素{if(T1->date[p].j==col) //当元素在col列时{T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;q++;}}}}}//上述代码，当矩阵运算为满时，即tu=mu*nu,其时间复杂度为O(nu*nu*mu)//这种情况与经典算法相⽐，虽节省了存储空间，但是效率较低第⼆种：快速转置第⼀种算法是通过遍历所有元素的下标，从⽽确定其在转置后数组中的位置，快速转置的思想就是，预先确定每⼀列第⼀个⾮零元在对应转置后的数组date中的位置；因此需要两个辅助数组num[]:⽤来存放每⼀列的⾮零元个数cpot[]:存放第⼀个⾮零元在转置后数组date中的位置num[]数组的值很好求，只需要遍历⼀次所有元素即可for(t=1;t<=T1->tu;t++)++num[T1->date[t].j];对于cpot[]，有⼀个规律col 1 2 3 4 5 6 7num[col] 2 2 2 1 0 1 0cpot[col] 1 3 5 7 8 8 9//规律copt[1]=1copt[col]=copt[col-1]+num[col-1]代码：void FastTransposeSMatrix(TSMatrix *T1,TSMatrix *T2){int num[T1->nu],cpot[T1->nu];int col,p,q,t;T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){//初始化每列⾮零元个数为0for(col=1;col<=T1->nu;col++){num[col]=0;}//求每列⾮零元个数for(t=1;t<=T1->tu;t++){++num[T1->date[t].j];}//求每列第⼀个⾮零元转置后的位置cpot[1]=1;for(col=2;col<=T1->nu;col++){cpot[col]=num[col-1]+cpot[col-1];}//遍历所有元素for(p=1;p<=T1->tu;p++){col=T1->date[p].j; //获取列坐标q=cpot[col]; //获取新位置T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;++cpot[col]; //之所以这个地⽅要++，因为每列⾮零元可能不⽌⼀个 }}}完整代码：#include <stdio.h>#include <stdlib.h>#define MAXSIZE 12500 //⾮零元个数的最⼤值typedef int ElemType;typedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple date[MAXSIZE+1];int mu,nu,tu;}TSMatrix;//输⼊元素void Insert(TSMatrix *T){printf("请依次输⼊⾏数i、列数j、⾮零元个数sum:\n");int sum ;scanf("%d%d%d",&T->mu,&T->nu,&sum);T->tu=sum;int x,y,num;printf("请依次输⼊矩阵⾮零元的⾏坐标i、列坐标j、元素值x:\n");printf("i j v\n");for(int i=1 ;i<=sum;i++){scanf("%d%d%d",&x,&y,&num);T->date[i].i=x;T->date[i].j=y;T->date[i].e=num;}}//第⼀种转置⽅法void TransposeSMatrix(TSMatrix *T1,TSMatrix *T2)T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){int q=1,col,p;for(col=1;col<=T1->nu;col++){for(p=1;p<=T1->tu;p++){if(T1->date[p].j==col){T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;q++;}}}}}//输出矩阵⾮零元void Show(TSMatrix *T){printf("转置后的矩阵：\n");printf("i j v\n");for(int i=1;i<=T->tu;i++){printf("%d %d %d\n",T->date[i].i,T->date[i].j,T->date[i].e); }}//快速转置void FastTransposeSMatrix(TSMatrix *T1,TSMatrix *T2){int num[T1->nu],cpot[T1->nu];int col,p,q,t;T2->mu=T1->nu;T2->nu=T1->mu;T2->tu=T1->tu;if(T1->tu){//初始化每列⾮零元个数为0for(col=1;col<=T1->nu;col++){num[col]=0;}//求每列⾮零元个数for(t=1;t<=T1->tu;t++){++num[T1->date[t].j];}cpot[1]=1;for(col=2;col<=T1->nu;col++){cpot[col]=num[col-1]+cpot[col-1];}for(p=1;p<=T1->tu;p++){col=T1->date[p].j;q=cpot[col];T2->date[q].i=T1->date[p].j;T2->date[q].j=T1->date[p].i;T2->date[q].e=T1->date[p].e;++cpot[col];}}}int main(){TSMatrix T,T1,*q,*p;p=&T;q=&T1;Insert(p);//测试第⼀种转置⽅法TransposeSMatrix(p, q);Show(q);//测试快速转置FastTransposeSMatrix(p, q);Show(q);}/* 测试请依次输⼊⾏数i、列数j、⾮零元个数sum:6 7 8请依次输⼊矩阵⾮零元的⾏坐标i、列坐标j、元素值x:1 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7转置后的矩阵：i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14转置后的矩阵：i j v1 3 -31 6 152 1 122 5 183 1 93 4 244 6 -76 3 14Program ended with exit code: 0*/我不⽣产代码，我只是代码的搬运⼯。

数据结构稀疏矩阵运算器引言：稀疏矩阵是指在一个二维矩阵中，绝大多数元素为0或者没有意义的元素。

与之相对，稠密矩阵则是指大部分元素都有意义且不为0的矩阵。

稀疏矩阵在很多实际问题中经常出现，例如图论、网络分析、自然语言处理等领域。

为了高效地处理稀疏矩阵的运算，我们可以使用稀疏矩阵运算器。

一、稀疏矩阵的表示方法对于一个m×n的稀疏矩阵，我们可以使用三元组(Triplet)的方式进行表示。

三元组表示法包括三个数组：行数组row、列数组col 和值数组value。

其中，row[i]和col[i]分别表示第i个非零元素的行和列，value[i]表示第i个非零元素的值。

通过这种方式，我们可以用较少的空间来表示一个稀疏矩阵，从而提高运算效率。

二、稀疏矩阵的加法运算稀疏矩阵的加法运算可以通过遍历两个稀疏矩阵的非零元素，并将相同位置的元素相加得到结果。

具体步骤如下：1. 初始化一个新的稀疏矩阵result，其行数和列数与原始稀疏矩阵相同。

2. 遍历两个稀疏矩阵的非零元素，将相同位置的元素相加，并将结果存储在result中。

3. 返回result作为加法运算的结果。

三、稀疏矩阵的乘法运算稀疏矩阵的乘法运算可以通过矩阵的数学定义来实现。

具体步骤如下：1. 初始化一个新的稀疏矩阵result，其行数等于第一个稀疏矩阵的行数，列数等于第二个稀疏矩阵的列数。

2. 遍历第一个稀疏矩阵的每个非零元素，将其与第二个稀疏矩阵相应位置的元素相乘，并将结果累加到result中。

3. 返回result作为乘法运算的结果。

四、稀疏矩阵的转置运算稀疏矩阵的转置运算可以通过交换行数组row和列数组col来实现。

具体步骤如下：1. 初始化一个新的稀疏矩阵result，其行数等于原始稀疏矩阵的列数，列数等于原始稀疏矩阵的行数。

2. 将原始稀疏矩阵的行数组row赋值给result的列数组col，将原始稀疏矩阵的列数组col赋值给result的行数组row。

数据结构实验报告实验四稀疏矩阵的表示和转置一、实验目的1. 掌握稀疏矩阵的三元组顺序表存储结构2. 掌握稀疏矩阵的转置算法。

二、实验内容采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。

（算法5.1）三、实验步骤：1. 构建稀疏矩阵M。

2. 求稀疏矩阵M的转置矩阵T。

3. 输出稀疏矩阵M和稀疏矩阵T。

四、算法说明首先要创建稀疏矩阵的三元组顺序表存储表示，定义mu,nu,tu分别表示矩阵的行数、列数和非零元个数。

在进行稀疏矩阵的转置时要做到(1)：将矩阵的行列值相互交换；（2）：将每个三元组的i，j相互调换；（3）：重排三元组之间的次序便可实现矩阵的转置。

五、测试结果六、分析与探讨在此次程序中转置的方法称为快速转置，在转置前，应先求得M的每一列中非零元的个数，进而求得每一列的第一个非零元的位置。

七、附录：源代码数据结构实验报告源代码列在附录中，要求程序风格清晰易理解，有充分的注释。

有意义的注释行不少于30%。

#include <stdio.h>#define MAXSIZE 5#define MAXMN 200typedef struct{int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE];int rpos[MAXMN];int mu,nu,tu;//矩阵的行数、列数和非零元个数}TSMatrix; //行逻辑连接的顺序表int main(){printf("矩阵M\n");TSMatrix M,T;printf("i j v\n");int i;for(i=0;i<MAXSIZE;i++)scanf("%d %d %d",&M.data[i].i, &M.data[i].j, &M.data[i].e); printf("请输入矩阵M的行数mu,列数nu,及非零元的个数tu\n"); scanf("%d %d %d",&M.mu, &M.nu, &M.tu);//求稀疏矩阵M的转置矩阵TT.mu=M.nu; T.nu=M.mu; T.tu=M.tu;if(T.tu){int t, column, num[MAXMN]={0}; //用来统计M中每列非零元的个数for(t=0;t<M.tu;t++)++num[M.data[t].j];T.rpos[0]=0; for(column=1;column<T.mu;column++)T.rpos[column]=T.rpos[column-1]+num[column-1]; int p, q;for(p=0;p<M.tu;p++){column=M.data[p].j;q=T.rpos[column];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;数据结构实验报告T.data[q].e=M.data[p].e;T.rpos[column]++; //转置矩阵T中同一行的非零元的起始位置自增1 } }//输出矩阵M及转置矩阵Tprintf("\n矩阵T：\n");printf("i j v\n");for(i=0;i<T.tu;i++)printf("%d %d %d\n",T.data[i].i, T.data[i].j, T.data[i].e); printf("\n");return 0;}欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求。

稀疏矩阵应用摘要本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。

在程序设计中，考虑到方法的难易程度，采用了先用三元组实现稀疏矩阵的输入，输出，及其转置，相加，相乘操作的方法，再在十字链表下实现。

程序通过调试运行，结果与预期一样，初步实现了设计目标。

关键词程序设计；稀疏矩阵；三元组；十字链表1 引言1.1课程设计任务本课程设计主要实现在三元组存储结构与十字链表存储结构下输入稀疏矩阵，并对稀疏矩阵进行转置，相加，相乘操作，最后输出运算后的结果。

稀疏矩阵采用三元组和十字链表表示，并在两种不同的存储结构下，求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；求出A的转置矩阵D，输出D；求两个稀疏矩阵A和B的相乘矩阵E，并输出E。

1.2课程设计性质数据结构课程设计是重要地实践性教学环节。

在进行了程序设计语言课和《数据结构》课程教学的基础上，设计实现相关的数据结构经典问题，有助于加深对数据结构课程的认识。

本课程设计是数据结构中的一个关于稀疏矩阵的算法的实现，包括在三元组和十字链表下存储稀疏矩阵，并对输入的稀疏矩阵进行转置，相加，相乘等操作，最后把运算结果输出。

此课程设计要求对数组存储结构和链表存储结构非常熟悉，并能熟练使用它们。

1.3课程设计目的其目的是让我们在学习完C、数据结构等课程基础上，掌握多维数组的逻辑结构和存储结构、掌握稀疏矩阵的压缩存储及转置，相加，相乘等基本操作，并用不同的方法输出结果，进一步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

2需求分析2.1设计函数建立稀疏矩阵及初始化值和输出稀疏矩阵的值本模块要求设计函数建立稀疏矩阵并初始化，包括在三元组结构下和十字链表结构下。

首先要定义两种不同的结构体类型，在创建稀疏矩阵时，需要设计两个不同的函数分别在三元组和十字链表下创建稀疏矩阵，在输入出现错误时，能够对错误进行判别处理，初始化稀疏矩阵都为空值，特别注意在十字链表下，对变量进行动态的地址分配。

福建工程学院课程设计课程：数据结构题目：稀疏矩阵的快速转置专业：运算机类班级：座号：姓名：2021年6月25日实验题目：稀疏矩阵的快速转置一、要解决的问题利用三元组表存储稀疏矩阵，利用快速转置算法进行转置，并输出转置之前和以后的三元组表和矩阵。

二、算法大体思想描述：由于稀疏矩阵的非零元素较少，零元素较多，因此只需存储其非零元素。

因此能够成立一个三元组表，别离保存稀疏矩阵的非零元素的行号、列号和元素值。

对稀疏矩阵进行快速转置是能够引入两个向量num[n+1],cpot[n+1],别离标记矩阵中第col列的非零元素个数和第一个非零元素在转置后的矩阵的位置；再扫描三元组表，找到非零元素，直接对其在转置后的矩阵所在的位置上进行修改，以节省时刻。

三、详细设计⒈元素类型，结点类型typedef struct {int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;} Tsmatrix;2.对抽象数据类型中的部份大体操作的伪码算法如下：Tsmatrix * creatarray(Tsmatrix *M){ int m,n,p=1;int c;printf("please input the array A:\n");for(m=1;m<=a;m++)for(n=1;n<=b;n++){ scanf("%d",&c);if(c!=0){ M->data[p].e=c;M->data[p].i=m;M->data[p].j=n;p++;}}M->tu=p; M->mu=a; M->nu=b;printf("yuan lai san yuan zu de biao shi wei :\n\n");for(m=1;m<=M->tu;m++)printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e);printf("\n");return M;}/*三元组快速转置*/Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T){ int p,col,q,t,m;int num[100];int cpot[100];T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;if(T->tu!=0){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];}}printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n");for(m=1;m<=T->tu;m++)printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e);printf("\n");return T;}/*输出三元组函数*/void print(Tsmatrix *T,int x,int y){ int m,n,p=1;int d;for(m=1;m<=x;m++){ printf("\n");for(n=1;n<=y;n++){ if(T->data[p].i==m&&T->data[p].j==n){ d=T->data[p].e;p++;}else d=0;printf("%6d",d);}}}}3.主函数和其他函数的伪码算法void main(){ Tsmatrix *M,*T;M=(Tsmatrix *)malloc(sizeof(Tsmatrix));T=(Tsmatrix *)malloc(sizeof(Tsmatrix));printf("please input array's row and col:\n");scanf("%d%d",&a,&b); /*输入行列数*/ M=creatarray(M); /*创建稀疏矩阵*/printf("you had creat the array:\n");print(M,a,b); /*输出创建好的三元组*/T=fasttrans(M,T); /*将三元组转置*/printf("the trans array is:\n");print(T,b,a);getch();}4、模块结构及功能}四、源程序清单：#include<>#define MAXSIZE 100typedef struct {int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;} Tsmatrix;int a,b; /*概念全局变量数组的行数a和列数b*//*用数组创建三元组*/Tsmatrix * creatarray(Tsmatrix *M){ int m,n,p=1;int c;printf("please input the array A:\n");for(m=1;m<=a;m++)for(n=1;n<=b;n++){ scanf("%d",&c);if(c!=0){ M->data[p].e=c;M->data[p].i=m;M->data[p].j=n;p++;}}M->tu=p; M->mu=a; M->nu=b;printf("yuan lai san yuan zu de biao shi wei :\n\n");for(m=1;m<M->tu;m++)printf("%3d%3d%3d\t",M->data[m].i,M->data[m].j,M->data[m].e);printf("\n");return M;}/*三元组快速转置*/Tsmatrix * fasttrans(Tsmatrix *M,Tsmatrix *T){ int p,col,q,t,m;int num[100];int cpot[100];T->mu=M->nu; T->nu=M->mu; T->tu=M->tu;if(T->tu!=0){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];}}printf("\n\nzhuan zhi hou de san yuan zu biao shi wei :\n\n");for(m=1;m<T->tu;m++)printf("%3d%3d%3d\t",T->data[m].i,T->data[m].j,T->data[m].e);printf("\n");return T;}/*输出三元组函数*/void print(Tsmatrix *T,int x,int y){ int m,n,p=1;int d;for(m=1;m<=x;m++){ printf("\n");for(n=1;n<=y;n++){ if(T->data[p].i==m&&T->data[p].j==n){ d=T->data[p].e;p++;}else d=0;printf("%6d",d);}}}void main(){ Tsmatrix *M,*T;M=(Tsmatrix *)malloc(sizeof(Tsmatrix));T=(Tsmatrix *)malloc(sizeof(Tsmatrix));printf("please input array's row and col:\n");scanf("%d%d",&a,&b); /*输入行列数*/M=creatarray(M);printf("you had creat the array:\n");print(M,a,b);T=fasttrans(M,T);printf("the trans array is:\n");print(T,b,a);getch();}五、测试数据及测试结果：（1）我输入的稀疏矩阵为：（2）回车显示的结果是：六、课程设计总结及心得体会：通过本次课程设计，我对有关稀疏矩阵及其三元组表的知识做了温习和巩固。