4.3.2 稀疏矩阵-两种转置算法

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

数据结构之稀疏矩阵稀疏矩阵的存储方式和操作分析稀疏矩阵是指矩阵中大部分元素为零的特殊矩阵。

在实际应用中，稀疏矩阵经常出现，如图像处理、网络分析和科学计算等领域。

对于稀疏矩阵的存储和操作是数据结构中的重要内容。

本文将介绍稀疏矩阵的存储方式和相关操作的分析。

一、稀疏矩阵存储方式稀疏矩阵的存储方式有多种，其中三元组顺序表和二维数组是比较常用的方法。

1. 三元组顺序表三元组顺序表是一种基于行优先存储的方式，可以将稀疏矩阵以非零元素的形式存储起来。

主要包括行号、列号和元素值三个信息。

以一个4x5的稀疏矩阵为例，其中有三个非零元素分别为A[1][2]=3, A[2][3]=4, A[3][4]=5。

可以使用三元组顺序表来存储：```行号列号元素值1 2 32 3 43 4 5```三元组顺序表的优点是可以节省存储空间，同时也方便进行矩阵的操作。

但是在进行元素的查找和修改时，效率较低。

2. 二维数组二维数组是一种常见的矩阵表示方法，可以直接使用二维数组来表示稀疏矩阵。

其中非零元素的位置用实际的值表示，其余位置用零值表示。

以同样的4x5的稀疏矩阵为例，使用二维数组存储如下：```0 0 0 0 00 0 3 0 00 0 0 4 00 0 0 0 5```二维数组的优点是简单直观，并且可以快速进行元素的查找和修改。

但当稀疏矩阵的规模较大时，会造成较高的存储资源浪费。

二、稀疏矩阵的操作分析对于稀疏矩阵的操作，主要包括矩阵的转置、相加、相乘等。

1. 转置操作稀疏矩阵的转置是指将原始矩阵的行与列对调。

对于三元组顺序表来说，转置操作主要涉及到行号和列号的交换。

而对于二维数组来说，可以直接在取值的时候将行号和列号对调即可。

2. 相加操作稀疏矩阵的相加操作是指将两个矩阵对应位置的元素相加。

对于三元组顺序表来说，可以通过遍历两个矩阵的非零元素，并将其对应位置的元素相加。

而对于二维数组来说，可以直接将对应位置的元素相加即可。

3. 相乘操作稀疏矩阵的相乘操作是指将两个矩阵相乘得到一个新的矩阵。

实验2稀疏矩阵的表示和转置实验人：杜国胜学号:Xb14680103时间：11.91、实验目的1.掌握稀疏矩阵的三元组顺序表存储结构2.掌握稀疏矩阵的转置算法。

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

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

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

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

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

在进行稀疏矩阵的转置时要做到1.将矩阵的行列值相互交换2.将每个三元组的I,j相互调换3.重排三元组之间的次序5、测试结果6、分析讨论在此次程序中转置的方法称为快速转置，在转置前，应先求的M的每一列中非零元的个数，进而求得每一列的第一个非零元的位置7、附录：源代码#include<stdio.h>#define MAXSIZE 100typedef struct{int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;}TSMatrix;//创建稀疏矩阵Mvoid CreateSMatrix (TSMatrix *M){int i,m,n,e,k;printf("输入矩阵M的行数、列数、非零元的个数（中间用逗号隔开）：");scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);(*M).data[0].i=0;printf("\n");for(i=1;i<=(*M).tu;i++){do{printf("输入第%d个非零元素所在的行(1~%d)列(1~%d)值以及该数值：",i,(*M).mu,(*M).nu);scanf("%d,%d,%d",&m,&n,&e);k=0;if(m<1||m>(*M).mu||n<1||n>(*M).nu)k=1;if(m<(*M).data[i-1].i||m==(*M).data[i-1].i&&n<(*M).data[i-1].j)k=1;}while(k);(*M).data[i].i=m;(*M).data[i].j=n;(*M).data[i].e=e;}printf("\n");}//输出稀疏矩阵Mvoid PrintSMatrix(TSMatrix M){int i;printf("**************************************\n");for(i=1;i<=M.tu;i++)printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e); printf("**************************************\n");printf("\n");}//求稀疏矩阵M的转置矩阵Tvoid TransposeSMatrix(TSMatrix M,TSMatrix *T){int p,q,col;(*T).mu=M.nu;(*T).nu=M.mu;(*T).tu=M.tu;if((*T).tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==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;++q;}}}void print(TSMatrix A){int k=1,a,b;int M[MAXSIZE][MAXSIZE];printf("非零元素所对应的位置：\n");printf("**************************************\n"); for(a=0;a<A.mu;a++){for(b=0;b<A.nu;b++)M[a][b]=0;}while(k<=A.tu){M[A.data[k].i-1][A.data[k].j-1]=A.data[k].e;k++;}for(a=0;a<A.mu;a++){printf(" | ");for(b=0;b<A.nu;b++)printf("%d ",M[a][b]);printf(" | \n");}printf("**************************************\n"); printf("\n");}//主函数int main(){TSMatrix M,T;printf("创建矩阵M：");CreateSMatrix(&M);printf("矩阵M的三元组表为:\n");PrintSMatrix(M);print(M);TransposeSMatrix(M,&T);printf("稀疏矩阵M的转换矩阵T的三元组表为:\n");PrintSMatrix(T);print(T);printf("\n\n");getchar();return 0;}。

稀疏矩阵稀疏矩阵的定义 对于那些零元素数⽬远远多于⾮零元素数⽬，并且⾮零元素的分布没有规律的矩阵称为稀疏矩阵（sparse）。

⼈们⽆法给出稀疏矩阵的确切定义，⼀般都只是凭个⼈的直觉来理解这个概念，即矩阵中⾮零元素的个数远远⼩于矩阵元素的总数，并且⾮零元素没有分布规律。

稀疏矩阵的压缩存储 由于稀疏矩阵中⾮零元素较少，零元素较多，因此可以采⽤只存储⾮零元素的⽅法来进⾏压缩存储。

由于⾮零元素分布没有任何规律，所以在进⾏压缩存储的时侯需要存储⾮零元素值的同时还要存储⾮零元素在矩阵中的位置，即⾮零元素所在的⾏号和列号，也就是在存储某个元素⽐如aij的值的同时，还需要存储该元素所在的⾏号i和它的列号j，这样就构成了⼀个三元组(i,j,a[i][j])的线性表。

三元组可以采⽤顺序表⽰⽅法，也可以采⽤链式表⽰⽅法，这样就产⽣了对稀疏矩阵的不同压缩存储⽅式。

稀疏矩阵的存储⽅式 1.稀疏矩阵的三元组表⽰ 若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。

顺序表中除了存储三元组外，还应该存储矩阵⾏数、列数和总的⾮零元素数⽬，这样才能唯⼀的确定⼀个矩阵。

typedef struct Triple{int row,col,e;}Triple;typedef struct TSMarix{Triple data[max+1];//data是⾮零元素三元组表，data[0]未⽤int m,n,len;//m:矩阵的⾏数，n:矩阵的列数，len：⾮零元素的个数}TSMarix; 稀疏矩阵的转置 ⾏列递增转置法---算法思想： 采⽤按照被转置矩阵三元组表A的序列（即转置后三元组表B中的⾏序）递增的顺序进⾏转置，并以此送⼊转置后矩阵的三元组表B中，这样⼀来，转置矩阵的三元组表B恰好是以“⾏序为主序”的 这种⽅法中，转置后的三元组表B仍按⾏序递增存放，必须多次扫描被转置矩阵的三元组表A，以保证被转置矩阵递增形式进⾏转置，因此要通过双重循环来完成#include <stdio.h>#include <stdlib.h>#define max 3typedef struct Triple{int row,col,e;}Triple;typedef struct TSMarix{Triple data[max+1];//data是⾮零元素三元组表，data[0]未⽤int m,n,len;//m:矩阵的⾏数，n:矩阵的列数，len：⾮零元素的个数}TSMarix;void CreateTSMarix(TSMarix *T){int i;printf("请输⼊矩阵的⾏数，列数，⾮零元素个数：\n") ;scanf("%d%d%d",&T->m,&T->n,&T->len);if(T->m<1||T->n<1||T->len<1||T->len>=max){printf("输⼊的数据有误!\n");exit(1);}printf("请输⼊⾮零元素的⾏下标，列下标，值(空格分开输⼊):\n");for(i=1;i<T->len+1;i++)scanf("%d%d%d",&T->data[i].row,&T->data[i].col,&T->data[i].e);}void TransposeTSMarix(TSMarix T,TSMarix *B)//B保存转置后的矩阵{B->n=T.m;//转置后B的列存储的T的⾏B->m=T.n;//转置后B的⾏存储的T的列B->len=T.len;//B的元素的个数和T的元素的个数⼀样不变int i,j,k;if(B->len>0){j=1;//转置后B元素中的下标for(k=1;k<=T.m;k++)//采⽤被转置矩阵的列序即转置后矩阵的⾏序增序排列{for(i=1;i<=T.len;i++){if(T.data[i].col==k)//从头到尾扫描表A,寻找col值为k的三元组进⾏转置{B->data[j].row=T.data[i].col;B->data[j].col=T.data[i].row;B->data[j].e=T.data[i].e;j++;}}}}}void Print(TSMarix T){int i;printf("元素的⾏下标，列下标，值为:\n");for(i=1;i<=T.len;i++){printf("\t%d\t%d\t%d\n",T.data[i].row,T.data[i].col,T.data[i].e);}}int main(){TSMarix T,B;printf("创建三元组表:\n");CreateTSMarix(&T);printf("输出三元组表:\n");Print(T);TransposeTSMarix(T,&B);printf("转置后的矩阵B为:\n");Print(B);return0;} ⼀次快速定位转置法---算法思想 1.待转置矩阵三元组表A每⼀列⾮零元素的总个数，即转置后矩阵三元组表B的每⼀⾏中⾮零元素的总个数 2.待转置矩阵每⼀列中第⼀个⾮零元素在三元组表B中的正确位置，即转置后矩阵每⼀⾏中的第⼀个⾮零元素在三元组表B 中的正确位置，需要增设两个数组，num[col]⽤来存放三元组表A第col列⾮零元素总个数（三元组表第col⾏⾮零元素总个数），position[col]⽤来存放转置前三元组表A中第col列（转置后三元组表B中第col⾏）中第⼀个⾮零元素在三元组表B中的存储位置（下标值）。

// DataStructT est.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream.h>#include <malloc.h>const int maxnum=10;struct NODE{int rowNO; //行号int colNO; //列号int v;};struct SpMatrixTp{int mu; //行数int nu; //列数int tu; //非0元素个数NODE data[maxnum+1]; //书上说假定三元组下标从1开始};void ShowArray2(int * p,int row,int col){int index=0;for(int i=0;i<row;i++){for(int j=0;j<col;j++){if (j==0)cout<<p[index++];elsecout<<" "<<p[index++];}cout<<endl;}cout<<endl;}//通过二维数组建立三元组void Creat eMatrix(int * p,int row,int col,SpMatrixTp & matrix){matrix.mu=0;matrix.nu=0;matrix.tu=0;int index=1;matrix.mu=row;matrix.nu=col;matrix.tu=0;for(int i=0;i<row;i++){for(int j=0;j<col;j++){if (p[i*col+j]!=0){matrix.tu++;matrix.dat a[index].rowNO=i+1;matrix.dat a[index].colNO=j+1;matrix.dat a[index].v=p[i*col+j];index++;}}cout<<endl;}cout<<endl;}//显示三元组void DisplayMatrix(SpMat rixTp & matrix){for(int i=0;i<matrix.tu;i++){cout<<matrix.data[i+1].rowNO<<","<<matrix.data[i+1].colNO<<","<<mat rix.dat a[i+1].v<< endl;}}//按列序转置(非快速方法)void trans_Sparmat(SpMatrixTp a,SpMatrixTp & b){b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if (a.tu>0){int index=1;for(int col=1;col<=a.nu;col++){for(int i=1;i<=a.tu;i++){if (a.dat a[i].colNO==col){b.dat a[index].colNO=a.data[i].rowNO;b.dat a[index].rowNO=a.data[i].colNO;b.dat a[index].v=a.data[i].v;index++;}}}}}//快速转置算法void Fast_Trans_Sparmat(SpMatrixTp a,SpMat rixTp & b){b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;//记录每列的非零元素个数申动动态空数用作数组,因为数组的维数不可以使用变量,a.nu+1是多申请了一个元素的空间,//目的是使它与矩阵结构中下标向量以1起始相同,减少逻辑上的混乱int * num=(int *)malloc(sizeof(int)*(a.nu+1));//记录每列中第一个非零元素在转置后的三元组中的位置int * cpot=(int *)malloc(sizeof(int)*(a.nu+1));if (a.tu>0){int col=0;//初始化该数组,使所有元素都置0for(col=1;col<=a.nu;col++){num[col]=0;}//记录矩阵中每一列的非零元素数for(col=1;col<=a.nu;col++){num[a.data[col].colNO]++;}//记录原矩阵中第一个非0元素在转置后的三元组中位置cpot[1]=1;for(col=2;col<=a.nu;col++){cpot[col]=cpot[col-1]+num[col-1];}//进行转置操作//因为向量num记录了每列的非零元素的个数,cpot记录了每列中第1个非零元素在转置后的三元组中的位置,那么就可以//使cpot[col]在每次循环中递增1,使得记录了当前col的下一个元素在转置三元组中的位置for(int p=1;p<=a.tu;p++){int q=cpot[a.data[p].colNO];b.dat a[q].colNO=a.dat a[p].rowNO;b.dat a[q].rowNO=a.dat a[p].colNO;b.dat a[q].v=a.dat a[p].v;//记录第col列的下一个非零元素在转置后的三元组中的相应位置cpot[a.data[p].colNO]++;}}free(num);free(cpot);}int main(int argc, char* argv[]){const int row=5,col=6;int Array2[row][col]={{0,3,0,0,0,1},{0,0,0,0,0,0},{5,-1,0,0,0,0},{0,0,0,0,4,0},{-3,0,0,0,0,0}};//建立三元组SpMatrixTp matrix;Creat eMatrix(&Array2[0][0],row,col,matrix);DisplayMatrix(matrix);//使用转置算法1SpMatrixTp transMatrix1;trans_Sparmat(mat rix,t ransMatrix1);cout<<"以下是使用第一种转置算法生成的转置后的三元组,其时间复杂度为O(行数*列数)"<<endl;DisplayMatrix(transMatrix1);//使用转置算法2(快速转置算法)cout<<"以下是使用第二种快速转置算法生成的转置后的三元组,其时间复杂度为O(列数+非零元素数)"<<endl;SpMatrixTp transMatrix2;Fast_T rans_Sparmat(mat rix,transMatrix2);DisplayMatrix(transMatrix2);return 0;}。

稀疏矩阵的基本原理稀疏矩阵是指矩阵中绝大多数的元素都是零的矩阵。

由于稀疏矩阵的元素数量很少，所以进行矩阵运算时，需要采用特殊的算法，以提高计算速度和效率。

本文将简单介绍稀疏矩阵的基本原理。

一、稀疏矩阵的表示方法在计算机中，稀疏矩阵的存储方式有三种：1. COO格式：也称为三元组格式，该格式将矩阵的每一个元素都用一个三元组表示，分别为其行、列和数值，如{(0, 0, 2), (0, 3,1), (1, 1, 3)}。

2. CSR格式：也称为压缩行格式，该格式将矩阵的非零元素按行存储，并通过两个数组（值向量和列指针）表示，如{2, 1, 3, 4, 5}和{0, 2, 4}。

3. CSC格式：也称为压缩列格式，该格式将矩阵的非零元素按列存储，并通过两个数组（值向量和行指针）表示，如{2, 3, 1, 4, 5}和{0, 1, 3, 3, 4}。

二、稀疏矩阵的基本运算稀疏矩阵的基本运算包括加、减、乘和转置等，下面分别介绍：1. 矩阵加法：对于两个矩阵A和B，若其行列相等，则可以进行加法运算。

对于稀疏矩阵的加法，首先需要找到两个矩阵中非零元素的位置，在这些位置上进行加法运算即可。

2. 矩阵减法：与矩阵加法类似，稀疏矩阵的减法也需要找到两个矩阵中非零元素的位置，在这些位置上进行减法运算即可。

3. 矩阵乘法：对于两个矩阵A和B，若A的列数等于B的行数，则可以进行乘法运算，结果为一个新的矩阵C。

稀疏矩阵的乘法运算比较复杂，需要对数组进行操作，具体实现方法可以参考CSR或CSC格式。

4. 转置：对于一个矩阵A，其转置矩阵为AT，即A的列变为AT 的行，AT的列变为A的行。

转置操作可以直接在CSR或CSC格式中进行操作。

三、稀疏矩阵的应用稀疏矩阵广泛应用于科学计算和工程计算等领域，如图像处理、搜索引擎、网络分析等。

由于稀疏矩阵的存储方式和运算均比较特殊，因此对于稀疏矩阵的计算需要采用特殊的算法，如迭代法、预处理法等。

数据结构课程设计题目稀疏矩阵的转置专业网络工程班级姓名指导教师2013 年 6 月27 日课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 题 目: 稀疏矩阵的转置 初始条件：（1）稀疏矩阵采用三元组表示，输入一个稀疏矩阵A 。

（2）求出A 的转置矩阵D ，输出D 。

测试数据：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=300020001A 要求完成的主要任务:课程设计报告按学校规定格式用A4纸打印，并应包含如下内容： 1. 问题描述简述题目要解决的问题是什么。

2. 设计存储结构设计、主要算法设计（用C 语言或用框图描述）、测试用例设计。

3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4. 程序运行结果（包括对算法改进的设想）5. 经验与体会6. 参考文献说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

时间安排：1、第17周完成。

2、2011年6月28号提交打印版课程设计，源程序刻录光盘。

指导教师签名： 年 月 日目录1．问题分析与任务定义 (1)2.结构设计 (1)3.算法思想 (1)4.模块划分 (2)5.算法实现 (2)5.1对矩阵进行定义 (2)5.2创建稀疏矩阵 (2)5.3求矩阵的快速转置 (3)6.系统运行结果 (5)7.经验与体会 (5)8.参考文献 (5)稀疏矩阵的转置1．问题分析与任务定义稀疏矩阵是指那些多数元素为零的矩阵。

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

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

以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现稀疏矩阵的转置。

求出稀疏矩阵A 的转置矩阵D ，输出D 。

1.1稀疏矩阵采用三元组表示，输入一个稀疏矩阵A 。

1.2求出A 的转置矩阵D ，输出D 。

测试数据：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=300020001A 2.结构设计2.1.以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。

稀疏矩阵数据结构与算法§1转置算法稀疏矩阵在数据结构中不是重点，但是稀疏矩阵既是数据处理的大范围内，又具有一般程序设计与算法结构的基本特征。

大学阶段遇到的科学计算类程序不多，稀疏矩阵运算（转置、乘法）的算法是应掌握的起步阶段算法对运算数据关联范围的设置不同，导致稀疏矩阵的转置算法的效率不同。

一．稀疏矩阵转置程序1的分析1.什么是转置M mn-->T nm，其中a ij=b ji(1≤i≤m, 1≤j≤n。

i,j可看作与M,T无关的表示，也可以看作矩阵M为主动的下标表示方法)，而且a ij∈M, b ji∈T。

矩阵M已知，矩阵T未知。

因此在编程时，应考虑以哪个矩阵为算法主序，这是一个出发点。

(1)M，T的行列互换à两个矩阵的行数mu列数nu互换，T.mu=M.nu=n ，T.nu=M.mu=m，以T为主动。

(2)矩阵元素T(i,j)=M(j,i)，矩阵T的第i行第j列元素与矩阵M的第j 行第i列元素相等。

以T的元素为驱动，因为能从M的元素得到T的元素，所以建立表达式就能得到T元素的值。

（在程序中，是否用矩阵T的顺序为算法线索？）转置矩阵的非0元个数相同，T.tu=M.tu(3)对0元素多的稀疏矩阵的转置而言，与一般矩阵的转置不同。

稀疏矩阵的非0元素a ij，在程序中用三元组(i,j,a ij)表示，i,j表示行数列数。

因为不再按照矩阵的结构m行n列转置，不使用二维数组作为存储，所以必须记录每一个非0元素所在行列的位置。

在规则的二维数组中，矩阵的行列通过元素的下标识别，元素在矩阵中的位置通过下标得到。

因此一般矩阵用二维数组为存储结构。

二维数组是物理存储结构的逻辑形式，可称为逻辑存储结构。

2.稀疏矩阵的一维数组存储结构从操作系统可知，数据的存储方式有三种：连续（顺序）方式，链接方式，索引方式。

矩阵不能直接用在计算机中，应选择顺序存储结构二维数组，存放元素。

稀疏矩阵的非0元以矩阵行序为序存储在一维数组中，每一行元素的数目不同，可称为非规则数组。

一、设计要求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。

三、模块设计3．1 模块设计程序包括两个模块：主程序模块、矩阵运算模块。