二维数组的压缩存储矩阵

数据结构实验报告

学号：2015111898姓名：许明华专业：计算机科学与技术

知识范畴：数组与广义表完成日期：2017年04月21日

实验题目：基于压缩存储的半三角矩阵乘法运算的实现

实验内容及要求：

已知两个n阶下半三角矩阵的乘积仍为n阶下半三角矩阵。编程输入两个n阶下半三角矩阵，输出这两个矩阵的乘积。要求n阶下半三角矩阵采用一维数组压缩存储（即只存储下半三角）。

程序先从键盘(或字符文件)输入n值，建立三个矩阵的一维数组动态存储结构，然后从键盘(或字符文件)输入两个半三角矩阵，最后输出计算结果到屏幕上(或另一个字符文件中)。

例如：键盘输入为：

3

1

2 3

4 5 6

-1

-2 -3

-4 -5 -6

则输出为：

-1

-8 -9

-38 -45 -36

实验目的：掌握半三角矩阵的顺序存储结构。

数据结构设计简要描述：

序言：

这是本学期第五个实验，本实验是要求我们将两个二维半三角矩阵压缩存储为一维矩阵，并对其进行乘法操作，得到一个一维的压缩存储矩阵，并将其打印输出；

数据结构简单设计：

本实验主要可分为两个大的模块（压缩存储矩阵、压缩矩阵相乘）。第一，我们通过键盘键入一个数组的阶数，然后输入两个半三角矩阵，，但是这两个半三角矩阵要进行压缩存储为一维矩阵，关键操作即（m = （i*（i+1））/2 + j），即可将二维下标转化为一维下标；第二，

运用公式 i]][[*]][[

j

j

k

b

k

i

a来进行相乘操作，求得两个下三角矩阵的乘积。算法设计简要描述：

1，通过（m = （i*（i+1））/2 + j）将二维下标转化为一维下标进行输入，得到压缩存储矩阵；

2，运用公式 i]][[*]][[

j

j

k

b

k

i

a进行乘积操作，但是乘数矩阵下标和结果矩阵的下标并没有同步，所以运用三个公式来进行分离操作，m1 = （i*（i+1））/2 + k；

m2 = (k*（k+1））/2 + j；

m = （i*（i+1））/2 + j；

c [m] += a[m1]*b[m2];

这样即能实现相乘的操作，但是每一次的c[m]没有进行初始化，所以在每一次得到m值后，进行操作c[m] = 0;

输入/输出设计简要描述：

输入：1，输入下三角存储矩阵的阶数n；

2，输入第一个下三角矩阵，如1 2 3 4 5 6；

3，输入第二个下三角矩阵，如-1 -2 -3 -4 -5 -6；

输出：1，输入2操作后，按存储矩阵格式输出打印第一个下三角矩阵；

2，输入3操作后，按存储矩阵格式输出打印第二个下三角矩阵，并输出打印两个矩阵的乘积矩阵

编程语言说明：

1，编程软件，CodeBlocks 16.0；

2，代码均用C语言实现；

3，输入输出采用C语言的printf和scanf函数；

4，程序注释采用C/C++规范；

主要函数说明：

void input_Arr( int, int );//输入半三角矩阵声明

void print( int, int );//输出打印半三角矩阵声明

int print_Array( int, int, int, int);//两个半三角矩阵的乘法运算声明

程序测试简要报告：

见截图：

源程序代码：

#include

//函数声明部分

void input_Arr( int, int );//输入半三角矩阵声明

void print( int, int );//输出打印半三角矩阵声明

int print_Array( int, int, int, int);//两个半三角矩阵的乘法运算声明

//输入半三角矩阵

void input_Arr(int a[], int n)

{

int m;

printf("请输入数组：\n");

for(int i = 0 ; i < n ; i ++)

{

for(int j = 0 ; j <= i ; j ++)//这里在存储时我只存储了下三角对应的数组元素，，所以是j<=i,而不是j

{

m = (i*(i + 1))/2 + j;//这一步操作是关键所在，因为要将二维数组压缩存储为一维数组的话，我们来看，

//二维数组的下标为i和j，但是一维数组的下标只有一个，怎么办呢，

//这时候我们就可以根据公式来将二维数组的下标转化为对应的一维数组的下标，所得到的就是对应位置的对应下标

scanf("%d",&a[m]); //输入对应的下三角矩阵

}

}

}

//输出打印半三角矩阵

void print(int a[], int n)

{

int m = 0;

for(int i = 0 ; i < n ; i ++)

{

for(int j = 0 ; j <= i ; j ++)

{

m = (i*(i + 1))/2 + j;//打印操作，同上面

printf("%d ",a[m]);

}

printf("\n");

}

}

//两个半三角矩阵的乘法运算

int print_Array(int a[], int b[], int c[], int n)

{

int i = 0, j = 0;

int k, m, m1, m2 ;//k为进行乘法操作过程的中间变量，m为乘积过后的一维压缩数组的下标，m1为第一个数组的压缩存储的下标，m2为第二个数组的压缩存储的下标

for( i = 0; i < n ; i ++)

{

for( j = 0; j <= i ; j ++)//限定在下三角元素中进行

{

m = (i*(i + 1))/2 + j;//将二维下标转化为压缩存储的一维下标

c[m] = 0; //这一步很重要，我想了很久才想到这一步的，就是每一次将c[m]的初值赋为0，因为后面要执行c[m] +=操作，如果不仅赋初值的话，每次的第一个c[m]就是没有进行初始化，

//那它就是一个无穷大的数，得出来的乘积之和就是一个无穷大的数

for(k = j ; k <= i ; k ++)//由于是下三角进行相乘，所以所有的上三角元素都为零，不需要再进行乘积操作，

{

m1 = (i*(i + 1))/2 + k;//第一个压缩存储的数组的一维下标

m2 = (k*(k + 1))/2 + j;//第二个压缩存储的数组的一维下标

c[m] += a[m1]*b[m2];//进行乘积操作

}

}

}

return 0;

}

int main()

{

int n ;//数组长度n

int a[100],b[100],c[100];//定义三个一维数组

printf("请输入数组大小n：\n");

scanf("%d",&n);

input_Arr(a,n);//调用输入下三角矩阵函数

printf("数组一为：\n");

print(a,n);//输出下三角矩阵

input_Arr(b,n);//同上

printf("数组二为：\n");

print(b,n);//同上

print_Array(a,b,c,n);//调用下三角矩阵相乘函数

printf("数组的乘积为：\n");

print(c,n);//输出相乘之后的下三角矩阵

return 0; }

数据结构实验五矩阵的压缩存储与运算学习资料

数据结构实验五矩阵的压缩存储与运算

第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1

k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵 在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。 图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系： 公式中采用了C语言的符号，int()表示取整，‘%’表示求余。

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

专业课程设计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( )实现。当用户选择该功能，系统提示输

数据结构实验五矩阵的压缩存储与运算

第五章矩阵的压缩存储与运算 【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。 第一节知识准备 矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。 一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若n阶矩阵A中的元素满足 = （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。 问题已经转化为：已知二维矩阵A[i，j]，如图5-1， 我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。 任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 … n(n-1)/2 … n(n+1)/2-1 图5-2下三角矩阵的压缩存储 反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵

三角矩阵在压缩存储下的转置矩阵源代码

#include #include #define max 20 #define zero 0 typedef struct{ int i,j,v; }node; typedef struct{ node data[max]; int m; }TSmatrix; TSmatrix *Setmatrix(){ //建三对角矩阵TSmatrix *T; T=(TSmatrix *)malloc(sizeof(TSmatrix)); printf("请输入矩阵行数或列数:\n"); scanf("%d",&T->m); printf("建立三对角矩阵:\n"); for(int n=0;n<3*T->m-2;n++) scanf("%d%d%d",&T->data[n].i,&T->dat a[n].j,&T->data[n].v); return T; } TSmatrix *Trabsmatrix(TSmatrix *T){ //三对角矩阵转置 int n,k,temp; TSmatrix *F; F=(TSmatrix *)malloc(sizeof(TSmatrix)); F->m=T->m; for(n=0;n<3*T->m-2;n++){ //将结点信息存入新三元组表中 temp=2*T->data[n].j+T->data[n].i; //计算待存入三元数组下标 F->data[temp].i=T->data[n].j; F->data[temp].j=T->data[n].i; F->data[temp].v=T->data[n].v; } return F; } void TSmatrixout(TSmatrix *T){ //三对角矩阵输出 int a,b,n; n=0; for(a=0;am;a++){ for(b=0;bm;b++){ if(T->data[n].i==a&&T->data[n].j==b){ printf("%-5d",T->data[n].v); n++; } else printf("%-5d",zero); } printf("\n"); } } void main(){ TSmatrix *T; T=Setmatrix(); printf("三对角矩阵:\n"); TSmatrixout(T); T=Trabsmatrix(T); printf("转置后三对角矩阵:\n"); TSmatrixout(T); } 问题分析： 本程序要求实现对压缩存储下的三对角矩阵进行转置，为实现上述功能，需要解决的关键问题是三对角矩阵压缩存储及转置过程。 概要设计： 利用三元组表以行序为主序压缩存储三对角矩阵。转置时，先利用三元数组中的行标i 和列标j计算出待放入新三元数组的下标temp。由于转置时需要将行标和列标交换，所以temp=2*j+i。找出待存入的下标后，将相应的信息存入下标为temp的三元数组中。 详细设计：

稀疏矩阵及其压缩存储方法

稀疏矩阵及其压缩存储方法 1.基本概念 稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。 设m行n列的矩阵含t个非零元素，则称 以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。 特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。如下三角阵、三对角阵、稀疏矩阵。 压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。目的是节省大量存储空间。 n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。 2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构） 三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。 （1）稀疏矩阵的三元组顺序表存储表示方法 #define MAXSIZE 12500 // 假设非零元个数的最大值为12500 typedef struct { int i, j; // 该非零元的行下标和列下标 ElemType e; //非零元素的值 } Triple; // 三元组类型 typedef union { //共用体 Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } TSMatrix; // 稀疏矩阵类型 （2）求转置矩阵的操作 ◆用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu) ◆用三元组顺序表表示时的快速转置算法 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T T.mu = M.nu; 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];// 求M 中每一列所含非零元的个数

矩阵压缩1

为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。 一、相关概念 ㈠特殊矩阵：矩阵中存在大多数值相同的元,或非0元，且在矩阵中的分布有一定规律。 ⒈对称矩阵：矩阵中的元素满足 a ij=a ji 1≤i,j≤n ⒉三角矩阵：上（下）三角矩阵指矩阵的下（上）三角（不包括对角线）中的元素均为常数c或0的n阶矩阵。 ⒊对角矩阵（带状矩阵）：矩阵中所有非0元素集中在主对角线为中心的区域中。 ㈡稀疏矩阵：非0元素很少（≤ 5%）且分布无规律。 二、存储结构及算法思想 1、对称矩阵 存储分配策略：每一对对称元只分配一个存储单元,即只存储下三角（包括对角线）的元, 所需空间数为: n(n+1)/2。 存储分配方法：用一维数组sa[n(n+1)/2]作为存储结构。 sa[k]与a ij之间的对应关系为: 2、三角矩阵 也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素b i,j和sb[k]之间仍然有如上的对应关系，只是还需要再加一个存储常数c的存储空间即可。如在下三角矩阵中，用n(n+1)/2的位置来存储常数。

对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案 2、稀疏矩阵 常见的有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。 1）、三元组表示法 三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i,j,a ij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。

稀疏矩阵基本操作 实验报告

稀疏矩阵基本操作实验报告 一、实验内容 稀疏矩阵的压缩储存结构，以及稀疏矩阵的三元组表表示方法下的转置、相加、相乘等算法 二、实验目的 1.熟悉数组、矩阵的定义和基本操作 2.熟悉稀疏矩阵的储存方式和基本运算 3.理解稀疏矩阵的三元组表类型定义，掌握稀疏矩阵的输入、输出和转置算法 三、实验原理 1.使用三元组储存矩阵中的非零元素（三元组分别储存非零元素的行下标，列下标和 元素值）。除了三元组表本身，储存一个稀疏矩阵还需要额外的三个变量，分别储存矩阵的非零元个数，矩阵的行数和矩阵的列数。 2.稀疏矩阵的创建算法： 第一步：根据矩阵创建一个二维数组，表示原始矩阵 第二步：取出二维数组中的元素（从第一个元素开始取），判断取出元素是否为非零元素，如果为非零元素，把该非零元素的数值以及行下标和列下表储存到三元数组表里，否则取出下一个元素，重复该步骤。 第三步：重复第二步，知道二维数组中所有的元素已经取出。 3.稀疏矩阵倒置算法： 第一步：判断进行倒置的矩阵是否为空矩阵，如果是，则直接返回错误信息。 第二步：计算要倒置的矩阵每列非零元素的数量，存入到num数组（其中num[i] 代表矩阵中第i列非零元素的个数）。以及倒置后矩阵每行首非零元的位置，存入cpot 数组中（其中cpot表示倒置后矩阵每行非零元的位置，对应表示原矩阵每列中第一个非零元的位置）。 第三步：确定倒置后矩阵的行数和列数。 第四步：取出表示要导致矩阵中三元组表元素{e, I, j}（第一次取出第一个，依次取出下一个元素），从第二步cpot数组中确定该元素倒置后存放的位置（cpot[j]），把该元素的行下标和列下标倒置以后放入新表的指定位置中。cpot[j] 变量加一。 第五步：重复第四步，直到三元组表中所有的元素都完成倒置。 第六步：把完成倒置运算的三元组表输出。 4.稀疏矩阵加法算法： 第一步：检查相加两个矩阵的行数和列数是否相同，如果相同，则进入第二步，否则输出错误信息。 第二步：定义变量i和j，用于控制三元组表的遍历。 第三步：比较变量矩阵M中第i个元素和矩阵N中第j个元素，如果两个元素是同一行元素，如果不是则进入第四步，如果是，再继续比较两个元素是否为同一列元素，如果是，把两个元素值相加，放到三元组表中；否则把列下表小的元素依次放到三元组表中。进入第五步 第四步：如果矩阵M中第i个元素的行下标大于矩阵N中第j个元素的行下标，则把矩阵N中第j个元素所在行的所有非零元素添加到三元组表中；如果矩阵M中第

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

专业课程设计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( )实现。当用户选择该功能，系统提示输入要进行相乘的两个矩阵的详细信息。然后进行相乘，最后得到结果。 （3）稀疏矩阵的转置： 此功能由函数void Zhuanzhi( )实现。当用户选择该功能，系统提示用户初始

压缩矩阵的运算

实验四数组的运算 实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。 实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵；⑹求一个矩阵的逆矩阵（选做）。 实验代码： Rect.h #define MAXSIZE100 typedef struct { int h_num; int v_num; int elem; }Triple; typedef struct { Triple *arry; int h_i; int v_j; int elem_num; }TSMatrix; void Init_TS(TSMatrix *T ); void creat(TSMatrix *T); void Print_TS(TSMatrix *); void sum_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T); void mul_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T); void transpose_TS(TSMatrix *T); void equal_Triple(Triple *t1,Triple *t2); Rect.cpp #include #include #include"rect.h"

void Init_TS(TSMatrix *T) { T->arry=(Triple *)malloc(MAXSIZE*sizeof(Triple)); if(!T->arry) printf("error\n") ; T->elem_num=0; T->h_i=0; T->v_j=0; } void Init_Tr(Triple *t) { t->elem=0; t->h_num=0; t->v_num=0; } void creat(TSMatrix *T) { printf("要输入的数组的行数和列数\n"); scanf("%d,%d",&T->h_i,&T->v_j); printf("要输入稀疏数组的元素个数\n"); scanf("%d",&T->elem_num); printf("输入要输入的稀疏数组的信息\n"); printf("行值列值元素值\n"); for(int i=0;ielem_num;i++) { scanf("%d %d %d",&T->arry[i].h_num,&T->arry[i].v_num,&T->arry[i].elem); } }; void Print_TS(TSMatrix *T) { printf("输出稀疏数组的信息\n"); printf("行下标列下标元素值\n"); for(int i=0;ielem_num;i++) { printf("%d %d %d\n",T->arry[i].h_num,T->arry[i].v_num,T->arry[i].elem); } }; void sum_TS(TSMatrix *T1,TSMatrix *T2,TSMatrix *T) { T->h_i=T1->h_i;T->v_j=T1->v_j;

稀疏矩阵的运算

数据结构课程设计稀疏矩阵的运算 学生姓名： 学号： 指导教师： 完成日期：

目录： 1、分析问题和确定解决方案 (3) 1.1问题描述 (3) 1.2 输入的形式和输入值的范围 (3) 1.3 输出的形式 (3) 1.4 程序所能达到的功能 (3) 1.5 测试数据 (3) 1.6 确定解决方案 (4) 1.7所有抽象数据类型的定义 (4) 2、详细设计 (5) 2.1稀疏矩阵加法运算思路 (5) 2.2稀疏矩阵减法运算思路 (7) 2.3稀疏矩阵转置运算思路 (9) 2.4创建稀疏矩阵 (11) 3、系统调试与测试 (12) 3.1程序的菜单界面 (12) 3.2 实现加法运算 (12) 3.3 实现减法运算 (13) 3.4实现转置运算 (14) 4、结果分析 (15) 4.1、算法的时空分析 (15) 4.2、经验和体会 (15) 5、参考文献 (15)

1、分析问题和确定解决方案 1.1问题描述 稀疏矩阵是指那些多数元素为零的矩阵。利用“稀疏”特点进行存储和计 算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。用三元组实现稀疏矩阵的相加、相减，转置； 1.2输入的形式和输入值的范围 以三元组的形式输入，首先应输入矩阵的行数和列数，并判别给出的两个 矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过20； 例如：输入的三元组为：((1,1,10),(2,3,9),(3,1,-1))其对应的稀疏矩阵为： ???? ??????-0019000010 1.3 输出的形式 运算结果的矩阵以通常的阵列形式输出； 1.4程序所能达到的功能 该程序可以实现以三元组形式输入两个矩阵，求出两个矩阵的和、差、转置； 并可根据输入的矩阵的行列数不同判别是否可以进行相加、减、转置，并重新输 入正确的矩阵； 1.5测试数据 测试的数据及其结果如下： 矩阵M 矩阵N 矩阵Q 加法： ???? ??????-0019000010 + ????? ?????--301100000 = ????? ?????-3008000010 减法： ???? ? ?????-0190010 - ???? ? ?????--311000 = ???? ??????-32100010 转置：

稀疏矩阵的压缩存储上

第3讲 稀疏矩阵压缩存储上——教学讲义 稀疏矩阵是指矩阵中大多数元素为零的矩阵。从直观上讲，当非零元素个数低于总元素的30 %时,这样的矩阵为稀疏矩阵。如下图所示的矩阵M 、 N 中,非零元素个数均为8个,矩阵元素总数均为6 ×7 =42 ,显然8 /42 <30 %,所以M 、 N 都是稀疏矩阵。 1 稀疏矩阵的三元组表表示法 ( 1 ) 稀疏矩阵的三元组存储表示 对于稀疏矩阵的压缩存储,采取只存储非零元素的方法。由于稀疏矩阵中非零元素aij 的分布没有规律 ,因此,要求在存储非零元素值的同时还必须存储该非零元素在矩阵中所处的行号和列号的位置信息,这就是稀疏矩阵的三元组表表示法。 每个非零元素在一维数组中的表示形式如下图所示。 说明:为处理方便,将稀疏矩阵中非零元素对应的三元组按“行序为主序”用一维结构体数组进行存放,将矩阵的每一行(行由小到大)的全部非零元素的三元组按列号递增存放。由此得到矩阵M 、 N 的三元组表A 和B 。如下图所示。 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 M= 6×7 0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 7×6 N= 稀疏矩阵M 和N 三元组的结构

( 2 )稀疏矩阵三元组表的类型定义 稀疏矩阵三元组表类型定义如下: #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 ； 在稀疏矩阵情况下，采用三元组表表示法大量节约了存储空间,以图5.10中的M 6*7矩阵为例，需要6*7=42个存储单元，但M 采用三元组表A 存放，共有8个非零元素,每个非零元按占3个单元计算，需要3*8=24个单元，显然比矩阵常规存储来讲还是大大节省存储。 ( 3 )三元组表实现稀疏矩阵的转置运算 需要强调的是，矩阵常规存储是二维的，而三元组存储是一维的，由于矩阵存储结构的变化也带来了运算方法的不同，必需认真分析。下面给出稀疏矩阵的转置运算问题，希望从中体会实现算法的处理思路和改进算法的技术。 矩阵转置指变换元素的位置,把位于( row,col)位置上的元素换到( col,row)位置上,把元素的行列互换。如图5 .10的6 ×7矩阵M,它的转置矩阵就是7×6的矩阵N,并且N( row,col)= M( col,row),其中,1 ≤ row ≤ 7 ,1 ≤ col ≤ 6 。 ①矩阵转置的经典算法 采用矩阵的正常存储方式(二维数组)实现矩阵转置。 稀疏矩阵转置经典算法 void TransMatrix （ElementType source[m][n], ElementType dest[n][m]） {/*source 和dest 分别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/ int i, j; for(i=0;i

数据结构压缩矩阵

1.课程设计的目的 (1) 熟练使用 C ++语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和 设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试 等基本方法和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能 力; 2.需求分析 问题描述：对于特殊矩阵可以通过压缩存储减少存储空间。 基本要求： 1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值。 2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值。 特殊矩阵：具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。最常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。 特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的

分布规律，把那些呈现规律性分布的值相同的多个矩阵元素压缩存储到一个存储空间中。 3.矩阵的压缩与解压缩问题的设计 图1-1 4.调试分析

图1-2程序运行界面

图1-3 程序运行界面 5.小结

经过矩阵的压缩与解压缩的实验，让我了解到计算机是怎么为了减少承储空间的，存储矩阵的。以及特殊矩阵式在计算机中存储，以及把这些矩阵的压缩后怎么解压出来，恢复原来的样子！我觉得像这样的课程设计，一定要先想好有哪些板块，以及那些板块之间的关系这么样！谁调谁！

6、参考文献 [1] 严蔚敏，吴伟民编著. 数据结构(C 语言版)--北京: 清华大学出版社，2007.2 [2]严蔚敏，吴伟民米宁编著. 数据结构题集(C 语言版)--北京: 清华大学出版社，2007.3 [3]网上搜索相关程序作为参考

稀疏矩阵的压缩存储方法及主要运算的实现

1.实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。 2.实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵；⑶执行两个矩阵相加；⑷执行两个矩阵相乘；⑸求一个矩阵的转置矩阵。 3.数据结构设计 逻辑结构：线性结构 存储结构：顺序存储结构 4.算法设计 #include #define MAXSIZE 100 typedef int datatype; typedef struct { int i,j; datatype v; }Triple; typedef struct { Triple data[MAXSIZE+1]; int rpos[MAXSIZE+1]; int mu,nu,tu; }RLSMatrix; int main() { void AddSMatrix(RLSMatrix M); void MultSMatrix(RLSMatrix M); void FastTransposeSMatrix(RLSMatrix M); RLSMatrix M; int k; printf("请输入稀疏矩阵M的行数、列数和非零元素个数:"); scanf("%d%d%d",&M.mu,&M.nu,&M.tu); printf("请输入稀疏矩阵M中非零元素的行号、列号和元素的值:\n"); for(k=1;k<=M.tu;k++) scanf("%d%d%d",&M.data[k].i,&M.data[k].j,&M.data[k].v); printf("请输出稀疏矩阵M中非零元素的行号、列号和元素的值:\n"); for(k=1;k<=M.tu;k++) { printf("%d%3d%3d",M.data[k].i,M.data[k].j,M.data[k].v); printf("\n"); } AddSMatrix(M); MultSMatrix(M); FastTransposeSMatrix(M); return 0; } void AddSMatrix(RLSMatrix M) { RLSMatrix N,R;

矩阵

特殊矩阵的压缩存储 对称矩阵中的元素关于主对角线对称，因此，让每一对对称元素a ij和a ji(i≠j)分配一个存储空间，则n2个元素压缩存储到n(n+1)/2个存储空间，能节约近一半的存储空间。 不失一般性，假设按“行优先顺序”存储下三角形(包括对角线)中的元素。 设用一维数组(向量)sa[0…n(n+1)/2]存储n阶对称矩阵，如图5-4所示。为了便于访问，必须找出矩阵A中的元素的下标值（i,j）和向量sa[k]的下标值k之间的对应关系。 若i≧j：a i j在下三角形中，直接保存在sa中。a i j之前的i-1行共有元素个数：1+2+…+(i-1)=i?(i-1)/2 而在第i行上，a i j之前恰有j-1个元素，因此，元素a i j保存在向量sa中时的下标值k之间的对应关系是： k=i?(i-1)/2+j-1 i≧j 若i

以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵的下三角（不包括主对角线）中的元素均为常数c(一般为0)。下三角矩阵正好相反，它的主对角线上方均为常数，如图5-5所示。 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0…n(n+1)/2]中，其中c存放在向量的第1个分量中。 上三角矩阵元素a i j保存在向量sa中时的下标值k与（i,j）之间的对应关系是：下三角矩阵元素a i j保存在向量sa中时的下标值k与（i,j）之间的对应关系是： 3 对角矩阵 矩阵中，除了主对角线和主对角线上或下方若干条对角线上的元素之外，其余元素皆为零。即所有的非零元素集中在以主对角线为了中心的带状区域中，如图5-6所示。 如上图三对角矩阵，非零元素仅出现在主对角(a i i,1≦i≦n)上、主对角线上的那条对角线(a i i+1,1≦i≦n-1) 、主对角线下的那条对角线上(a i+1 i,1≦i≦n-1)。显然，当| i-j |>1时，元素a ij=0。

第五章习题 数据结构

第五章习题 1.填空题 ⑴ 数组通常只有两种运算：和，这决定了数组通常采 用结构来实现存储。 存取，修改，顺序存储 ⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每 个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是。 数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。 ⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其 存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址 为。d+41 ⑷ 稀疏矩阵一般压缩存储方法有两种，分别是和。 三元组顺序表，十字链表 ⑸ 广义表((a), (((b),c)),(d))的长度是，深度是， 表头是，表尾是。 3，4，(a)，((((b),c)),(d)) ⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原 子b的运算是。 Head(Head(Tail(LS))) 2. 选择题 ⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的 范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] D，E，K ⑵ 将数组称为随机存取结构是因为（） A 数组元素是随机的 B 对数组任一元素的存取时间是相等的 C 随时可以对数组进行访问 D 数组的存储结构是不定 B

特殊矩阵的压缩存储算法的实现

软件综合课程设计 特殊矩阵的压缩存储算法的实现二叉排序树的实现 二〇一四年六月

一、特殊矩阵的压缩存储算法的实现 1.问题陈述 对于特殊矩阵可以通过压缩存储减少存储空间。 基本要求： 1.针对多种特殊矩阵进行压缩存储，并能显示压缩后的相关地址和值； 2.输入在原来特殊矩阵中的地址，要求能从压缩后的矩阵中读出相应的值； 2.程序代码 #include #include #include static shangsanjiao(int n) { int i,j,k,z,g; int L[100][100],SA[100]; cout<<"请输入您要压缩矩阵的行列数"<>n; cout<<"请输入您的矩阵内元素："<>L[i][j]; if(i<=j) k=j*(j-1)/2+i-1; else k=n*(n+1)/2; SA[k]=L[i][j]; } cout<<"您输入的矩阵为："<>z; for(g=0;g<1000;g++) { while(z==100)

数据结构稀疏矩阵应用

实验五数组的运算 实验目的： 掌握稀疏矩阵的压缩存储方法及主要运算的实现。 实验内容与要求： 设计一个稀疏矩阵计算器，要求能够：⑴输入并建立稀疏矩阵；⑵输出稀疏矩阵； ⑶执行两个矩阵相加；⑷求一个矩阵的转置矩阵。 程序代码： #include #define smax 20 typedef int datatype; typedef struct { int i,j; datatype v; }node; typedef struct { node data[smax]; int m,n,t; }spmatrix; void creat(spmatrix a)\\创建输出稀疏矩阵 { int k=0; printf("请输入稀疏矩阵：\n"); scanf("%d,%d,%d",&a.m,&a.n,&a.t); scanf("%d,%d,%d",&a.data[0].i,&a.data[0].j,&a.data[0].v); while(a.data[k].v!=0)\\以0元素作为结束标志，因为稀疏矩阵不包含0元素 {k++; scanf("%d,%d,%d",&a.data[k].i,&a.data[k].j,&a.data[k].v); } printf("输出的稀疏矩阵是：\n"); printf("%d,%d,%d\n",a.m,a.n,a.t); for(k=0;k

稀疏矩阵的压缩存储及运算

稀疏矩阵的压缩存储及运算 一、实验内容 实现稀疏矩阵的压缩存储方法以及在特定存储方法下的基本运算 二、实验母的 掌握数组的应用，包括稀疏矩阵、特殊矩阵的压缩存储方法。矩阵的基本运算的实现，包括矩阵相加、转置、乘法等。 三、问题描述 1）用行逻辑链接顺序表和十字链表分别实现稀疏矩阵的压缩存储 2）编程实现矩阵的转置运算和乘法运算（运用行逻辑链接顺序表或十字链表作为存储结构） 四、问题的实现 稀疏矩阵的抽象数据类型定义： ADT SpareseMatrix{ 数据对象：;,,2,1;,,2,1|{n j m i D a ij === },,列数分别称为矩阵的行数和和n m ElemSet a j i ∈ 数据关系： ：}1,11|,{} 11,1|,{} ,{,1,1,,n j m i Col n j m i Row Col Row R a a a a j i j i j i j i ≤≤-≤≤><=-≤≤≤≤><==++ 基本操作： CreateSMatrix(&M)； 操作结果：创建稀疏矩阵M 。 PrintSMatrix(M)； 初始条件：稀疏矩阵M 存在。 操作结果：输出稀疏矩阵M 。 AddSMatrix(M ，N ，&Q)； 初始条件：稀疏矩阵M 和N 的行数和列数对应相等。 操作结果：求稀疏矩阵的和Q=M+N 。 MultSMatrix(M ，N ，&Q)； 初始条件：稀疏矩阵M 的列数等于N 的行数。 操作结果：求稀疏矩阵乘积Q=M*N 。 TransposeSMatrix(M,&T)； 初始条件：稀疏矩阵M 存在。 操作结果：求稀疏矩阵M 的转置矩阵T 。 }ADT SpareseMatrix 五、主要源程序代码 #include using namespace std; #define MAXSIZE 100;