用三元组表存储表示,求稀疏矩阵M转置函数T

稀疏矩阵三元组快速转置（转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 问题描述稀疏矩阵是指那些多数元素为零的矩阵。

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

求一个稀疏矩阵A的转置矩阵B。

1．2需求分析（1）以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现稀疏矩阵的转置运算。

（2）稀疏矩阵的输入形式采用三元组表示，运算结果则以通常的阵列形式列出。

（3）首先提示用户输入矩阵的行数、列数、非零元个数，再采用三元组表示方法输入矩阵，然后进行转置运算，该系统可以采用两种方法，一种为一般算法，另一种为快速转置算法。

（4）程序需要给出菜单项，用户按照菜单提示进行相应的操作。

二、概要设计2．1存储结构设计采用“带行逻辑链接信息”的三元组顺序表表示矩阵的存储结构。

三元组定义为：typedef struct{int i； //非零元的行下标int j； //非零元的列下标 ElemType e; //非零元素值}Triple; 矩阵定义为： Typedef struct{Triple data[MAXSIZE+1]; //非零元三元组表int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu,nu,tu; //矩阵的行数、列数和非零元个数 }RLSMatrix;例如有矩阵A，它与其三元组表的对应关系如图2．2 系统功能设计本系统通过菜单提示用户首先选择稀疏矩阵转置方法，然后提示用户采用三元组表示法输入数据创建一个稀疏矩阵，再进行矩阵的转置操作，并以通常的阵列形式输出结果。

主要实现以下功能。

（1）创建稀疏矩阵。

采用带行逻辑连接信息的三元组表表示法，提示用户输入矩阵的行数、列数、非零元个数以及各非零元所在的行、列、值。

（2）矩阵转置。

<1>采用一般算法进行矩阵的转置操作，再以阵列形式输出转置矩阵B。

<2>采用快速转置的方法完成此操作，并以阵列形式输出转置矩阵B。

稀疏矩阵的三元组顺序表存储表示及其转置算法目录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的情况下，只有少数非零元素的情况。

实验四、稀疏矩阵三元组下转置一、实验内容将稀疏矩阵中的每个非零元素aij表示为(i, j, v)，即(行号，列号，非零元素值).称为三元组表示法。

用结构类型来描述三元组。

将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。

在稀疏矩阵用三元组顺序表存储结构下，实现稀疏矩阵转置，得到其转置矩阵的三元组顺序表存储表示。

要求：1）采用转置算法Ⅰ：直接取，顺序存2）采用转置算法Ⅱ：顺序取，直接存。

要使用两个辅助一维数组，分别先计算出原矩阵每一列的非零元个数以及每一列的第一个非零元在转置矩阵的三元组顺序表中的存储位置。

二、实验目的1. 掌握稀疏矩阵的三元组顺序表存储结构；2. 掌握稀疏矩阵转置算法Ⅰ；3. 掌握稀疏矩阵转置算法Ⅱ三、实验代码//文件：SparseMatrix.htemplate <class T>struct element{int row, col; //行数、列数T item; //元素值};const int MaxTerm=100;template <class T>class SparseMatrix{ public:SparseMatrix(){};SparseMatrix(int intmu,int intnu,int inttu,element<T> datatemp[]);//有参构造函数，初始化稀疏矩阵~SparseMatrix(){}; //析构函数，释放存储空间element<T> GetMatrix(int intnumber);//输出下标对应的数组元素void Prt();//显示三元组顺序表void Trans1(SparseMatrix<T> &B);//直接取、顺序存的矩阵转置算法void Trans2(SparseMatrix<T> A, SparseMatrix<T> &B);//顺序取、直接存的矩阵转置算法private:element<T> data[MaxTerm]; //矩阵非零元素int mu, nu, tu; //行数、列数、非零元个数};// 文件：SparseMatrix.cpp#include "SparseMatrix.h" //引用三元组顺序表的头文件#include <string> //引用string库函数的头文件using namespace std;//指出后续的所有的程序语句都在名字空间std内/*前置条件：三元组顺序表不存在输入：三元组顺序表的行数(intmu)、列数(intnu)、非零元个数(inttu)、初始三元组(datatemp[])功能：三元组顺序表的初始化输出：无后置条件：建立一个三元组顺序表*/template <class T>SparseMatrix<T>::SparseMatrix(int intmu,int intnu,int inttu,element<T> datatemp[]){if (inttu >MaxTerm ) throw "构造函数的初始化参数不正确";mu = intmu;nu = intnu;tu = inttu;for(int i=0;i<inttu;i++){data[i] = datatemp[i];}}/*前置条件：三元组顺序表已存在输入：下标(intnumber)功能：读取这组下标对应的数组元素输出：对应元素后置条件：三元组顺序表不变*/template <class T>element<T> SparseMatrix<T>::GetMatrix(int intnumber){if(intnumber>=tu || intnumber < 0) throw "输入位置不正确";return data[i];}/*前置条件：无输入：无功能：显示三元组顺序表输出：无后置条件：建立一个三元组顺序表*/template <class T>void SparseMatrix<T>::Prt(){for(int i=0;i<tu;i++){cout<<data[i].row<<" "<<data[i].col<<" "<<data[i].item<<"\n";}}/*前置条件：无输入：待转置的源三元组顺序表(A)和目标三元组顺序表(B)的引用功能：对三元组顺序表进行转置输出：无后置条件：三元组顺序表A的转置结果放在了B中*/template <class T>void SparseMatrix<T>::Trans1(SparseMatrix<T> &B){int pb,pa;B.mu=this->nu; B.nu=this->mu; B.tu=this->tu;//设置行数、列数、非零元素个数 if (B.tu>0) //有非零元素则转换{pb = 0;for (int col=0; col<this->nu; col++) //依次考察每一列 for (pa=0; pa<this->tu; pa++) //在A中扫描整个三元组表if (this->data[pa].col==col ) //处理col列元素{B.data[pb].row= this->data[pa].col ;B.data[pb].col= this->data[pa].row ;B.data[pb].item= this->data[pa].item;pb++;}}}/*前置条件：无输入：待转置的源三元组顺序表(A)和目标三元组顺序表(B)的引用功能：对三元组顺序表进行转置输出：无后置条件：三元组顺序表A的转置结果放在了B中*/template <class T>void SparseMatrix<T>::Trans2(SparseMatrix<T> A, SparseMatrix<T> &B){int i,j,k,num[MaxTerm],cpot[MaxTerm];B.mu=A.nu; B.nu=A.mu; B.tu=A.tu;//设置行数、列数、元素个数if (B.tu>0) //有非零元素则转换{for (i=0; i<A.nu; i++) num[i]=0; //A中每一列非零元素的个数初始化为0 for (i=0; i<A.tu; i++)//求矩阵A中每一列非零元素的个数{ j= A.data[i].col; //取三元组的列号num[j]++;}cpot[0]=0; //A中第0列第一个非零元素在B中的位置为0for (i=1; i<A.nu; i++) //求A中每一列第一个非零元素在B中的下标cpot[i]= cpot[i-1]+num[i-1];for (i=0; i<A.tu; i++)//扫描三元组表A{j=A.data[i].col; //当前三元组的列号k=cpot[j]; //当前三元组在B中的下标B.data[k].row= A.data[i].col ;B.data[k].col= A.data[i].row ;B.data[k].item= A.data[i].item;cpot[j]++; //预置同一列的下一个三元组的下标}}}//文件：SparseMatrixMain.cpp#include <iostream> //引用输入输出流库函数的头文件#include "SparseMatrix.cpp" ////引用广义表的成员函数文件#include <string> //引用string库函数的头文件using namespace std; //指出后续的所有的程序语句都在名字空间std内int main(){try{//建立一个element<int>类型的数组(A)element<int> A[7]={{0,0,15},{0,3,22},{0,5,-15},{1,1,11},{1,2,3},{2,3,6},{4,0,91}};SparseMatrix<int> sparsematrixB;//构造三元组顺序表来存储转置后的三元组顺序表 SparseMatrix<int> sparsematrixA(5,6,7,A);//构造三元组顺序表cout<<"原三元组顺序表如下:"<<"\n";sparsematrixA.Prt();//显示三元组顺序表sparsematrixA.Trans1(sparsematrixB);cout<<"使用直接取、顺序存转置算法转置后的三元组顺序表如下:"<<"\n";sparsematrixB.Prt();//显示三元组顺序表sparsematrixA.Trans2(sparsematrixA,sparsematrixB);cout<<"使用顺序取、直接存转置算法转置后的三元组顺序表如下:"<<"\n";sparsematrixB.Prt();//显示三元组顺序表}catch(char* e){ cout<<e; }return 0;}四、调试和运行结果在完成算法的程序实现后，用任意的一组数据来加以测试运行，对运行结果加以分析，检查运行结果是否正确。

题目：假设稀疏矩阵A采用三元组表表示，编写程序实现该矩阵的快速转置要求：输入一个稀疏矩阵A，由程序将其转换成三元组表存储；转置后的三元组表，由程序将其转换成矩阵形式后输出。

一、需求分析1.用户可以根据自己的需求输入任意一个稀疏矩阵，通过程序将其转换成三元组存储方式；2.并且能够完成矩阵的转置功能，要求需要使用的方法是快速转置的方法。

3.最后要够显示原矩阵和转置后的矩阵让用户能进行比较。

4.程序执行的命令包括：（1）构造稀疏矩阵M （2）求转转矩阵T （3）显示（打印）矩阵二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT SparseMatrix {数据对象：D={aij :|aij∈TermSet,i=1…m,m≥0，j=1…n,n≥0 m和n分别成为矩阵的行数和列数 }数据关系：R={Row，Col}Row ={<ai，j ,ai，j+1>|1≤i≤m，1≤j≤n-1 }Col ={<ai，j ,ai+1，j>|1≤i≤m-1，1≤j≤n }基本操作:CreateSMtrix(& M)操作结果：创建稀疏矩阵M。

DestroySMaix(&M)初始条件：稀疏矩阵M已存在。

操作结果：销毁稀疏矩阵M。

PrintSMatrix(L)初始条件：稀疏矩阵M已经存在。

操作结果：输出稀疏矩阵M。

CopySMatrix（M，&T）初始条件：稀疏矩阵M已经存在。

操作结果：由稀疏矩阵M复制得到T。

TransposeSMatrix(M，&T)初始条件：稀疏矩阵M已经存在。

操作结果：求稀疏矩阵M的转转矩阵T。

}ADT SparseMatrix2. 本程序有三个模块：⑴主程序模块main(){初始化；{接受命令；显示结果；｝｝⑵矩阵压缩存储单元模块：实现链表抽象数据类型操作，即函数的定义模块；三、详细设计⒈元素类型，结点类型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 函数调用关系四、调试分析⒈在定义变量的时候，我运用动了整型的全局变量a和b。

计算机科学与技术、网络工程本科《数据结构》期末考试试卷一、选择题(单选题，每小题 3分，共33分)1. 已知某二叉树的中序、层序序列分别为DBAFCE 、FDEBCA ，则该二叉树的后序序列为 ______ 。

A . BCDEAFB . ABDCEFC . DBACEFD . DABECF2•在11个元素的有序表A[1…11]中进行折半查找((low high)/2 ),查找元素A[11]时，被比较的元素的下标依次是 _________ 。

A . 6, 8, 10, 11B . 6, 9, 10, 11C . 6, 7, 9, 11D . 6, 8, 9,113 •由元素序列(27, 16 , 75 , 38 , 51 )构造平衡二叉树，则首次出现的最小不平衡子 树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为 ________ 。

A . 27B . 38C. 51D . 754 .利用逐点插入法建立序列(50 , 72 , 43 , 85 , 75 , 20 , 35 , 45 , 65 , 30)对应的 二叉排序树以后，查找元素 30要进行 _______ 次元素间的比较。

A . 4B . 5C . 6D . 75 .循环链表的主要优点是 _____ 。

A .不再需要头指针了B .已知某个结点的位置后，很容易找到它的直接前驱结点C .在进行删除后，能保证链表不断开D .从表中任一结点出发都能遍历整个链表6 .已知一个线性表(38 , 25, 74 , 63 , 52 , 48),假定采用散列函数 h ( key ) =key%7 计算散列地址，并散列存储在散列表A[0…6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率查找时查找成功的平均查找长度为 ___________ 。

A . 1 . 5B . 1 . 7C . 2.0 D . 2.3 7 .由权值为 9 , 2 , 5 , 7 的四个叶子结点构造 棵哈夫曼树, 该树的带权路径长度&在最好和最坏情况下的时间复杂度均为A .基数排序B .快速排序C .堆排序9.无向图 G=(V , E),其中 V={a , b , c , d , e , e ),(c , f ), (f , d), (e , d)}。