当前位置：文档库 › 数据结构稀疏矩阵的表示和转置

数据结构稀疏矩阵的表示和转置

实验四稀疏矩阵的表示和转置

一、实验目的

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

#define MAXSIZE 5

#define MAXMN 200

typedef 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

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的转置矩阵T

T.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

++num[M.data[t].j];

T.rpos[0]=0;

for(column=1;column

T.rpos[column]=T.rpos[column-1]+num[column-1];

int p, q;

for(p=0;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及转置矩阵T

printf("\n矩阵T：\n");

printf("i j v\n");

for(i=0;i

printf("%d %d %d\n",T.data[i].i, T.data[i].j, T.data[i].e);

printf("\n");

return 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 模块设计程序包括两个模块：主程序模块、矩阵运算模块。 3．2 系统子程序及其功能设计系统共设置了8个子程序，各子程序的函数名及功能说明如下。（1）CreateSMatrix(RLSMatrix &M) //创建稀疏矩阵（2）void DestroySMatrix(RLSMatrix &M) //销毁稀疏矩阵（3）void PrinRLSMatrix(RLSMatrix M) //遍历稀疏矩阵（4）void print(RLSMatrix A) //打印矩阵函数，输出以阵列形式表示的矩阵（5）TransposeSMatrix(RLSMatrix M,RLSMatrix &T) //求稀疏矩阵的转置的一般算法（6）FastTransposeSMatrix(RLSMatrix M,RLSMatrix &T) //快速转置算法（7）void showtip() //工作区函数，显示程序菜单（8）void main() //主函数

数据结构与算法特殊矩阵和稀疏矩阵

常熟理工学院《数据结构与算法》实验指导与报告书 _2017-2018_____学年第__1__ 学期专业：物联网工程实验名称：特殊矩阵和稀疏矩阵实验地点： N6-210 指导教师：聂盼红计算机科学与工程学院 2017

实验五特殊矩阵和稀疏矩阵【实验目的】 1、掌握数组的结构类型（静态的内存空间配置）；通过数组的引用下标转换成该数据在内存中的地址； 2、掌握对称矩阵的压缩存储表示； 3、掌握稀疏矩阵的压缩存储-三元组表表示，以及稀疏矩阵的转置算法。【实验学时】 2学时【实验预习】回答以下问题： 1、什么是对称矩阵？写出对称矩阵压缩存储sa[k]与aij之间的对应关系。若n阶矩阵A中的元素满足下述性质：a ij=a ji，则称为n阶对称矩阵。 sa[k]与矩阵元素a ij之间存在着一一对应的关系：若i>=j，k=i*(i+1)/2+j; 若i=j。对称矩阵为3,9,1,4,7 9,5,2,5,8 1,2,5,2,4 4,5,2,1,7 7,8,4,7,9

数据结构稀疏矩阵基本运算实验报告

课程设计课程：数据结构题目：稀疏矩阵4 三元组单链表结构体(行数、列数、头) 矩阵运算重载运算符优班级：姓名：学号：设计时间：2010年1月17日——2010年5月XX日成绩：指导教师：楼建华

一、题目二、概要设计 1.存储结构 typedef struct{ int row,col;//行，列 datatype v;//非0数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行，n 列，t 非0数个数 … … 2.基本操作 ⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法 ⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆三、详细设计（1）存储要点 position[col]=position[col-1]+num[col-1]; 三元组表(row ，col ，v) 稀疏矩阵（（行数m ，列数n ，非零元素个数t ），三元组，...，三元组） 1 2 3 4 max-1

数据结构稀疏矩阵转置,加法

《数据结构》实验报告 ◎实验题目:稀疏矩阵的转置、加法（行逻辑链接表） ◎实验目的：学习使用三元组顺序表表示稀疏矩阵，并进行简单的运算 ◎实验内容：以三元组表表示稀疏矩阵，并进行稀疏矩阵的转置和加法运算。一、需求分析该程序目的是为了用三元组表实现稀疏矩阵的转置和加法运算。 1、输入时都是以三元组表的形式输入； 2、输出时包含两种输出形式：运算后得到的三元组表和运算后得到的矩阵； 3、测试数据：（1）转置运算时输入三元组表：1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 得到转置后的三元组表：1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 （2）进行加法运算时先输入矩阵A（以三元组表形式）：1 1 1 2 2 2 2 3 4 3 1 -4 输入矩阵B（以三元组表形式）：1 3 -2 2 3 -5 3 1 8 3 2 -6 A与B的和矩阵以矩阵形式输出为：1 0 -2 0 2 -1 4 -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中。 2.本程序包含了两个模块：（1）头文件模块；其中包括定义三元组表Triple和稀疏矩阵Matrix，以及创建矩阵void CreatMatrix(Matrix *m)和输出矩阵void PrintMatrix(Matrix m)两个函数；（2）主程序模块；包括主函数main()，快速转置函数void FastTransposeMatrix(Matrix a,Matrix *b)和实现矩阵相加函数void AddMatrix(Matrix a,Matrix b,Matrix *c) (三) 详细设计定义三元组和稀疏矩阵类型： typedef struct { int i,j; int e; }Triple; typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }Matrix; 创建头文件:“Matrix.h” void CreatMatrix(Matrix *m)//矩阵的初始化 { int p=1,a,b,c; printf("请输入矩阵的行数、列数、非零元的个数（数据用空格隔开）:"); scanf("%d %d %d",&(*m).mu,&(*m).nu,&(*m).tu);

稀疏矩阵三元组存储转置后矩阵输出

#include #include #define MAXSIZE 1000 typedef int ElementType; typedef struct { int row,col; ElementType e; }Triple; typedef struct { Triple data[MAXSIZE+1]; int m,n,len; }TSMatrix; void creatTSMatrix(TSMatrix *A) { int temp,row,col,k; printf("row,column:"); scanf("%d%d",&A->m,&A->n); printf("input data must be followed by above row and column :\n"); k=1; for(row=1;row<=A->m;row++) for(col=1;col<=A->n;col++) { scanf("%d",&temp); if(temp) { A->data[k].row=row; A->data[k].col=col; A->data[k].e=temp; k++; } } A->len=k-1; printf("the Matrix A translate into Triple is:\n\n"); for(row=1;row<=A->len;row++) printf("%3d%3d%3d\t",A->data[row].row,A->data[row].col,A->data[row].e); printf("\n"); }

稀疏矩阵的建立与转置

实验2 稀疏矩阵的建立与转置一、实验目的掌握特殊矩阵的存储和操作算法。二、实验内容及问题描述实现用三元组保存稀疏矩阵并实现矩阵转置的算法。三、实验步骤 1. 定义稀疏矩阵的三元组形式的存储结构。 2. 实现三元组矩阵的传统转置算法。 3. 实现三元组矩阵的快速转置算法。 4. 输入矩阵非零元素，测试自己完成的算法。四、程序流程图

五、概要设计矩阵是很多的科学与工程计算中研究的数学对象。在此，我们感兴趣的是，从数学结构这门学科着眼，如何存储矩阵的元从而使矩阵的各种运算有效的进行。本来，用二维数组存储矩阵，在逻辑上意义是很明确的，也很容易理解，操作也很容易和方便。但是在数值分析中经常出现一些阶数很高的矩阵，同时，在矩阵中又有很多值相同或者都为零的元素，可以对这种矩阵进行压缩存储：对多个值相同的元素只分配一个存储空间；对零元素不分配空间。稀疏矩阵的定义是一个模糊的定义：即非零元个数较零元个数较少的矩阵。例如下图所示的矩阵为一个稀疏矩阵。为了实现稀疏矩阵的这种存储结构，引入三元组这种数据结构。三元组的线性表顺存储形式如下图：六、详细设计 sanyuanzu.h 头文件 #define max 100 typedef struct { int row,col; int e; }Triple;//定义三元组 typedef struct { Triple data[max]; int mu,nu,tu; }TSMatrix;///*定义三元组的稀疏矩阵*/ void creat( TSMatrix &M) ; void fasttrans(TSMatrix A,TSMatrix &B);

数据结构实验稀疏矩阵计算器

‘ 实验报告题目：稀疏矩阵运算器班级：14电子商务平台建设班完成日期：2015.11.2 学号：姓名：孙少辉学号：姓名：杨德龙学号：姓名：柴益新一：需求分析稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏“特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。【基本要求】以“带行逻辑链接信息“的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘运算。稀疏矩阵的输入采用三元组表示，而运算结果的矩阵则以通常阵列形式列出。【项目约束】 1．首先应输入矩阵的行数和列数，并判断给出的两个矩阵行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20。 2．程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书5.3.2节中的算法，以便提高计算效率。

3.在用三元组稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可用二维数组存放。三：详细设计 1：数据结构的定义元素类型、变量、指针类型（1）项目数据表： 3.2子函数 3：函数调用关系无函数调用关系，只有一个主函数四：调试分析三元组顺序的输入规则。以0 0 0 作为输入的结束信号。完成实现稀疏矩阵的相加、相减、相乘的运算。五：用户使用说明 (1)首先运行文件系统 1.首先定义要运算的第一个稀疏矩阵的行列数

定义完成之后输入另一个要运算的稀疏矩阵的行列。 (2)输入信息：如下图所示输入两个矩阵的元素

所有输入信息以及运算方法输入完成之后。回车直接算出结果(3)输出信息：

六、源代码 /** ***项目名称：稀疏矩阵的运算 ***设计者：杨德龙，柴益新，孙少辉 ***时间：2015.11.02 ***实现目标：实现矩阵的加法，减法，乘法；***/ #include #include int main() { //定义二维数组及用到的各种变量 int a[20][20];

稀疏矩阵(算法与数据结构课程设计)

稀疏矩阵一、问题描述假若在n m ?阶中，有t 个元素不为零，令n m t ?=δ称为矩阵的稀疏因子。通常认为≤δ0.05时称为稀疏矩阵。稀疏矩阵的研究大大的减少了数据在计算机中存储所需的空间，然而，它们的运算却与普通矩阵有所差异。通过本次实验实现稀疏矩阵的转置、加法和乘法等多种运算。二、基本要求 1、稀疏矩阵采用三元组表示，建立稀疏矩阵，并能按矩阵和三元组方式输出; 2、编写算法，完成稀疏矩阵的转置操作； 3、编写算法，完成对两个具有相同行列数的稀疏矩阵进行求和操作； 4、编写算法，对前一矩阵行数与后一矩阵列数相等的两个矩阵,完成两个稀疏矩阵的相乘操作。三、测试数据 1、转置操作的测试数据： ??????? ? ?00200013000010020100 2、相加操作的测试数据： ??????? ? ?002000130000100 20100 ??????? ??00200010000210030300 3、相乘操作的测试数据： ?????? ? ??000000030040 0021 ??????? ??001002000021 四、算法思想 1、三元组结构类型为Triple ，用i 表示元素的行，j 表示元素的列，e 表示元素值。稀疏矩阵的结构类型为TSMatrix ，用数组data[]表示三元组，mu 表示行数，nu 表示列数，tu 表示非零元个数。 2、稀疏矩阵转置的算法思想将需要转置的矩阵a 所有元素存储在三元组表a.data 中，按照矩阵a 的列序来转置。

为了找到a的每一列中所有非零元素，需要对其三元组表a.data扫描一遍，由于a.data 是以a的行需序为主序来存放每个非零元的，由此得到的就是a的转置矩阵的三元组表，将其储存在b.data中。 3、稀疏矩阵相加的算法思想比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为0的元素的行数及列数（即i与j），将i与j都相等的前后两个元素值e相加，保持i,j不变储存在新的三元组中，不等的则分别储存在此新三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。 4、稀疏矩阵相乘的算法思想两个相乘的矩阵为M与N，对M中每个元素M.data[p](p=1,2,…,M.tu),找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].v和N.data[q].v 的乘积，又T(i,j)=∑M(i,k)×N(k,j),乘积矩阵T中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是T[i][j]中的一部分。为便于操作，应对每个元素设一累计和的变量，其初值是零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。由于T中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对T进行逐行处理，先求得累计求和的中间结果（T的一行），然后再压缩存储到Q.data中去。五、模块划分 1、Status CreateM(TSMatrix *M, int a[],int row, int col)，创立三元组； 2、void PrintM(TSMatrix M)，按数组方式输出； 3、void PrintM3(TSMatrix M)，按三元组方式输出； 4、Status TransposeSMatrix(TSMatrix M, TSMatrix *T)，稀疏矩阵的转置； 5、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵加法； 6、Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)，稀疏矩阵相乘； 7、main(),主函数。六、数据结构//(ADT) 1、三元组结构类型 typedef struct { int i,j; ElemType e; } Triple; 2、稀疏矩阵 typedef struct { Triple data[MAXSIZE+1];

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

数据结构---三元组顺序表------稀疏矩阵的转置和快速转置 #include<> #include<> #include<> #define TURE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INEEASLIBE -1 #define OVERFLOW -2 #define maxsize 100 typedef int status; typedef int elemtype; typedef struct { int i,j; elemtype e; }elem; typedef struct { elem data[maxsize+1]; int mu,mn,tu; }matrix; status showmatrix(matrix M) { int i,j,k=1; for(i=1;i<=;i++) { for(j=1;j<=;j++) { if(i==[k].i&&j==[k].j) { printf("%d\t",[k].e); k++; } else printf("0\t");

} printf("\n"); } return OK; } status trans(matrix M,matrix &T) { int i=1,j=1,k=1; =; =; =; while(i<= { for(;k<=;k++) if[k].j==i) { [j].e=[k].e; [j].i=[k].j; [j].j=[k].i; j++; } k=1; i++; } return OK; } status initmatrix(matrix &M) { printf("请输入该矩阵行数mu和列数mn和非零元个数tu\nmu="); scanf("%d",&; getchar(); printf("\nmn="); scanf("%d",&; getchar(); printf("\ntu="); scanf("%d",&; getchar(); if>maxsize) { printf("非零元个数已超过定义的值\n请重新输入tu="); scanf("%d",&; getchar();

数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现

数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现.txt对的时间遇见对的人是一生幸福；对的时间遇见错的人是一场心伤；错的时间遇见对的人是一段荒唐；错的时间遇见错的人是一声叹息。/* 数据结构C语言版稀疏矩阵的三元组顺序表存储表示和实现 P98 编译环境：Dev-C++ 4.9.9.2 日期：2011年2月8日 */ typedef int ElemType; // 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; // 创建稀疏矩阵M int CreateSMatrix(TSMatrix *M) { int i,m,n; ElemType e; int k; printf("请输入矩阵的行数,列数,非零元素个数：（逗号）\n"); scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu); (*M).data[0].i=0; // 为以下比较顺序做准备 for(i = 1; i <= (*M).tu; i++) { do { printf("请按行序顺序输入第%d个非零元素所在的行(1～%d)," "列(1～%d),元素值：(逗号)\n", i,(*M).mu,(*M).nu); scanf("%d,%d,%d",&m,&n,&e);

数据结构课后习题及解

数据结构课后习题及解析第五章

第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算：数组A共占用多少字节；数组A的最后一个元素的地址；按行存储时元素A 36 的地址；按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];

实习题若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。第五章答案 5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一） FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { position[1]=1; for(t=1;t<=A.len;t++) position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++) position[col]=position[col]+position[col-1]; for(p=1;p

基于三元组表表示的稀疏矩阵的快速转置算法及其改进

基于三元组表表示的稀疏矩阵的快速转置算法及其改进摘要:介绍基于三元组表表示的稀疏矩阵的快速转置算法,此算法在转置前需要先确定原矩阵中各列第一个非零元在转置矩阵中的位置,在此使用2个数组作为辅助空间,为了减少算法所需的辅助空间,通过引入2个简单变量提出一种改进算法。该改进算法在时间复杂度保持不变的情况下,空间复杂度比原算法节省一半。需求分析：矩阵作为许多科学与工程计算的数据对象,必然是计算机处理的数据对象之一。在实际应用中,常会遇到一些阶数很高,同时又有许多值相同的元素或零元素的矩阵,在这类矩阵中,如果值相同的元素或零元素在矩阵中的分配没有规律,则称之为稀疏矩阵。为了节省存储空间,常对稀疏矩阵进行压缩存储。压缩存储的基本思想就是:对多个值相同的元素只分配1个存储空间,对零元素不分配存储空间。换句话说,就是只存储稀疏矩阵中的非零元素。稀疏矩阵可以采取不同的压缩存储方法,对于不同的压缩存储方法,矩阵运算的实现也就不同。 1．稀疏矩阵的三元组表表示法根据压缩存储的基本思想,这里只存储稀疏矩阵中的非零元素,因此,除了存储非零元的值以外,还必须同时记下它所在行和列的位置(i,j),即矩阵中的1个非零元aij由1个三元组(i,j,aij)惟一确定。由此可知,稀疏矩阵可由表示非零元的三元组表及其行列数惟一确定。对于稀疏矩阵的三元组表采取不同的组织方法即可得到稀疏矩阵的不同压缩存储方法,用三元组数组(三元组顺序表)来表示稀疏矩阵即为稀疏矩阵的三元组表表示法。三元组数组中的元素按照三元组对应的矩阵元素在原矩阵中的位置,以行优先的顺序依次存放。三元组表的类型说明如下: # define MAXSIZE 1000 /*非零元素的个数最多为 1000*/ typedef struct { int row,col; /*该非零元素的行下标和列下标*/ ElementType e; /*该非零元素的值*/ }Triple; typedef struct { Triple data[MAXSIZE+1]; /*非零元素的三元组表, data[0]未用*/ int m,n,len; /*矩阵的行数、列数和非零元素的个数*/ }TSMatrix; 2．稀疏矩阵的快速转置算法待转置矩阵source和转置后矩阵dest分别用三元组表A和B表示,依次按三元组表A中三元组的次序进行转置,转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上,需要预先计算以下数据: 1)待转置矩阵source每一列中非零元素的个数(即转置后矩阵dest每一行中非零元素的个数)。

数据结构C语言版-稀疏矩阵的三元组顺序表存储表示和实现

typedef int ElemType; // 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 100 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; // 创建稀疏矩阵M int CreateSMatrix(TSMatrix *M) { int i,m,n; ElemType e; int k; printf("请输入矩阵的行数,列数,非零元素个数：（逗号）\n"); scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu); (*M).data[0].i=0; // 为以下比较顺序做准备 for(i = 1; i <= (*M).tu; i++) { do { printf("请按行序顺序输入第%d个非零元素所在的行(1～%d)," "列(1～%d),元素值：(逗号)\n", 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);

稀疏矩阵的运算(完美版)

专业课程设计I报告（2011 / 2012 学年第二学期）题目稀疏矩阵的转换专业软件工程学生姓名张鹏宇班级学号 09003018 指导教师张卫丰指导单位计算机学院软件工程系日期 2012年6月18号

指导教师成绩评定表

附件：稀疏矩阵的转换一、课题内容和要求 1．问题描述设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。二、设计思路分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。三、概要设计为了实现以上功能，可以从3个方面着手设计。 1．主界面设计为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主

控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。（1）稀疏矩阵的加法：此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。（2）稀疏矩阵的乘法：此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输

数据结构稀疏矩阵运算器课程设计

数据结构----稀疏矩阵运算器课程设计目录稀疏矩阵运算器设计............................................................................................ I 摘要................................................................................................................ ... II 第一章需求分析 (1) 第二章概要设计 (2) 第三章设计步骤 (6) 3.1 函数说明 (6) 3.2 设计步骤 (7) 第四章设计理论分析方法 (20) 4.1 算法一：矩阵转置.....................................................................

20 4.2 算法二：矩阵加法..................................................................... 20 4.3 算法三：矩阵乘法 (21) 第五章程序调试 (23) 第六章心得体会 (25) 参考文献 (26) 第一章需求分析 1．稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。

2．以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现矩阵转置，求逆，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。 3．演示程序以用户和计算机的对话方式执行，数组的建立方式为边输入边建立。 4．由题目要求可知：首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。 5．程序可以对三元组的输入顺序不加以限制；根据对矩阵的行列，三元组作直接插入排序，从而进行运算时,不会产生错误。 6．在用三元组表示稀疏矩阵时，相加、乘积和相减所得结果矩阵应该另生成；矩阵求逆时，为了算法方便，使用二维数组存放。 7．程序在VC6.0环境下设计。程序执行的命令为：1.稀疏矩阵转置; 2.稀疏矩阵加法; ;3. 稀疏矩阵乘法; 4.退出的工作。第二章概要设计 1．抽象数据类型稀疏矩阵的定义如下： ADT SparseMatrix{ 数据对象：D={a|i=1,2,…,m; j=1,2,…,n;