数据结构——矩阵

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】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-1k= 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。

数据结构矩阵加法
一、数据结构矩阵加法是什么呢？
嘿呀，宝子们！今天咱们来唠唠数据结构里的矩阵加法。

矩阵就像是一个方格阵，里面装着好多数字呢。

矩阵加法呢，可不是简单地把两个矩阵放在一块儿就完事儿啦。

它是要把对应的方格里面的数字相加哦。

比如说有矩阵A和矩阵B，A的第一行第一列的数字就要和B的第一行第一列的数字相加，得到新矩阵相应位置的数字。

二、怎么去做矩阵加法呢？
这就像是玩数字对对碰的游戏。

首先得保证两个矩阵的行数和列数是一样的。

要是不一样的话，就像两个人玩游戏，规则都不一样，那可没法玩加法这个游戏啦。

假设矩阵A是一个2行3列的矩阵，矩阵B也得是2行3列的。

然后就一个一个方格对着加呗。

就像给每个小方格里面的数字找个小伙伴，然后把它们凑一块儿。

三、矩阵加法在实际中有啥用呢？
这用处可大了去了。

在计算机图形学里，矩阵加法就像魔法一样。

比如说我们要把一个图形移动到另一个位置，就可以用矩阵来表示这个图形，然后通过矩阵加法来计算它移动后的新位置。

还有在物理学里，矩阵加法也能用来计算一些物理量的叠加呢。

就好比两个力作用在一个物体上，我们可以用矩阵来表示这两个力，然后用矩阵加法算出它们叠加后的效果。

概括来说呀，矩阵加法虽然看起来就是数字的相加，但是在很多领域都是超级重要的小能手呢。

它就像一把万能钥匙，能打开好
多不同领域的大门。

数据结构课程设计报告设计题目：图的邻接矩阵存储结构院系计算机学院年级x 级学生xxxx学号xxxxxxxxxx指导教师xxxxxxxxx起止时间10-6/10-102013年10月10日目录1 需求分析 (3)2 概要设计 (4)2.1 ADT描述 (4)2.2程序模块结构 (5)2.3各功能模块 (6)3详细设计 (7)3.1类的定义 (7)3.2 初始化 (8)3.3 图的构建操作 (8)3.4 输出操作 (9)3.5 get操作 (9)3.6 插入操作 (10)3.7 删除操作 (10)3.8 求顶点的度操作 (11)3.10 判断连通操作 (12)3.11 主函数 (13)4 调试分析 (16)4.1调试问题 (16)4.2 算法时间复杂度 (16)5用户手册 (16)5.1 主界面 (16)5.2 创建图 (17)5.3插入节点 (17)5.4 深度优先遍历 (17)5.5 求各顶点的度 (18)5.6 输出图 (18)5.7 判断是否连通 (19)5.8 求边的权值 (19)5.9 插入边 (19)5.10 删除边 (20)结论 (20)参考文献 (20)摘要随着计算机的普及，涉及计算机相关的科目也越来越普遍，其中数据结构是计算机专业重要的专业基础课程与核心课程之一，为适应我国计算机科学技术的发展和应用，学好数据结构非常必要，然而要掌握数据结构的知识非常难，所以对“数据结构”的课程设计比不可少。

本说明书是对“无向图的邻接矩阵存储结构”课程设计的说明。

首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。

其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。

然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。

再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。

然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。

数据结构矩阵转置
数据结构中的矩阵转置指的是矩阵中元素位置的改变。

当矩阵中原来
横纵坐标对应的数据发生变化，而元素位置不变时就是矩阵的转置。

在矩
阵转置的过程中，列变行，行变列，维度保持不变。

矩阵转置的概念：
矩阵的转置是指将一个m*n矩阵A的元素按照Aij=Aji的规律进行重
新排列而成为另一个n*m矩阵B，它就是矩阵A的转置矩阵，表示为BT。

由矩阵转置的定义可以得出，矩阵转置的过程会使矩阵的行列发生变化，而维度保持不变，即原来m*n矩阵转置之后仍为n*m矩阵，这其实就
是将二维l矩阵的行列颠倒，看起来像是把矩阵（腾空间）旋转了90度。

矩阵转置的特性：
1.交换性：(A^T)^T=A
2.矩阵乘法中，AB和BA相等时：(AB)^T=B^TA^T
矩阵转置的实现方式：
1.暴力法：
采用暴力法实现矩阵转置，其步骤如下：
（1）申请n*m的空间，用来存储转置后的矩阵
（2）以行为单位，读取第i行的元素，不断存入转置后的第i列中
（3）依次完成全部元素的赋值
2.零判断法：
此种方式可减小重复赋值的次数，其步骤如下：（1）申请n*m的空间，用来存储转置后的矩阵（2）以行为单位。

数据结构之特殊矩阵特殊矩阵：即指⾮零元素或零元素的分布有⼀定规律的矩阵，为了节省存储空间，我们可以对这类矩阵进⾏压缩存储；即为多个相同的⾮零元素只分配⼀个存储空间；对零元素不分配空间⼀、稀疏矩阵稀疏矩阵:设矩阵A中有s个⾮零元素，若s远远⼩于矩阵元素的总数，则称A为稀疏矩阵。

如果我们把整个数据存⼊内存，如果每个单元格⼀个字节则需要6*5个字节我们要对稀疏矩阵进⾏压缩存储：即只存储稀疏矩阵中的⾮零元素和矩阵的⼤⼩；采⽤三元组的表⽰⽅式例如：(6,5,30)矩阵⼤⼩、（0,3,34）、（1,1,1）、（1,3,3）、（1,4,59）、（2,0,23）、（2,2,12）、(3,1,45)、(3,3,51)、(3,4,46)、(4,2,34)、(5,0,78)、(5,2,56)、(5,4,2)稀疏矩阵占⽤空间⼤⼩：7*3个字节⼆、三⾓矩阵：上三⾓矩阵、下三⾓矩阵三⾓矩阵中的重复元素c(常量)可共享⼀个存储空间，其余的元素正好有n(n+1)/2个，因此，三⾓矩阵可压缩存储到向量s[0..n(n+1)/2]中，其中c存放在向量的最后⼀个分量中================上三⾓矩阵=================以主对⾓线划分，三⾓矩阵有上三⾓和下三⾓两种。

上三⾓矩阵，它的下三⾓（不包括主对⾓线）中的元素均为常数或者0，在⼤多数情况下，三⾓矩阵常数为零。

该图就是⼀个上三⾓矩阵a(m,n)=a(4,4)是⼀个4阶的⽅阵，将该矩阵压缩存储到⼀维数组S后下标012345678910数据12346781112160转换后⼀维数组的长度：S.length=1+n(n+1)/2最后⼀个位置：S[n(n+1)/2]=0其他上三⾓元素的位置在⼀维数组S的下标：S[i(2n-i+1)/2+j-i ]=a(i,j) ;例如 a(2,3)=S[2*(2*4-2+1)/2+3-2]=S[8]=12================下三⾓矩阵=================以主对⾓线划分，三⾓矩阵有上三⾓和下三⾓两种。

数据结构有向图矩阵/********* 所包含的库文件****************************/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <malloc.h>#include <iostream>using namespace std;/********** 宏定义**************************/typedef int ElemType ; /* 元素类型*/typedef int Status ; /* 逻辑形态*/typedef int VRType; /*顶点信息*/typedef int InfoType; /*弧信息*/typedef char VertexType ; /*顶点函数值*/#define OVERFLOW 2 /*益出标志*/#define OK 1 /*代表逻辑*/#define ERROR 0 /*代表逻辑假*//*******************邻接矩阵的存储定义**********************/#define INIFINITY 0 // 最大值#define MAX_VERTEX_NUM 20 //最大顶点数typedef enum {DG,DN,UDG,UDN} GraphKind; //{有向图，有向网，无向图，无向网}typedef struct{int adj; //顶点关系类型无权图1，0 VRType InfoType *info; //弧的相关信息}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //顶点数和弧的数目GraphKind kind; //图的种类}MGraph; // 图的定义/**********************具体实现**************************///坐落函数int LocateVex(MGraph G,char u){//给出vi求出G中的具体位置int i;for(i=0;i<G.vexnum;i++){ if(u==G.vexs[i]) return i;}if(i==G.vexnum) {printf("Error u!\n"); exit(1);}return 0;}//建无向图(邻接矩阵)Status CreateUDG(MGraph &G) //scanf("%c",&G.vexs[i]);{int w,i,j,k;char v1,v2;printf("请输入矩阵的定点个数和弧数\n");scanf("%d %d",&G.vexnum,&G.arcnum);for(i=0;i<G.vexnum;++i) {printf("请输入顶点字符(列:'v1'(or)'A')\n"); cin>>G.vexs[i]; }//建立顶点向量for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;j++){G.arcs[i][j].adj=INIFINITY;G.arcs[i][j].info=NULL;} //初始默认值for(k=0;k<G.arcnum;++k)//构造邻接矩阵进行{printf("请输入邻接矩阵的关联信息{eg:v1->v2=w(v~顶点w~权值)}\n");cin>>v1>>v2>>w;i=LocateVex(G,v1); j=LocateVex(G,v2); G.arcs[i][j].adj=w; //确定V1,V2在G中的位置//若弧有信息则输入if(IncInfo) Input(*G.arcs[i][j]);}//for kreturn OK;}//CreateUDN//选择建图的类型Status CreateGraph(MGraph &G){int i;printf("请输入你要建的图类型(1~DG~有向图2~DN~有向网3~UDG~无向图4~UDN~有向网)");scanf("%d",&i);G.kind=(GraphKind)(i-1);switch(G.kind){// case DG :return CreateDG(G); //构造有向图G// case DN :return CreateDN(G); //构造有向网Gcase UDG : return CreateUDG(G); //构造无向图G // case UDN :return CreateUDN(G); //构造有向网G default :return ERROR;}}//CreateGraph//图的显示void printf_adjmatrix(MGraph G){int i,j;printf("邻接矩阵:\nvertex\t");for(i=0;i<G.vexnum;i++)printf("%4c",G.vexs[i]);printf("\n");for(i=0;i<G.vexnum;i++){printf("%4c\t",G.vexs[i]);for(j=0;j<G.vexnum;j++){printf("%4d",G.arcs[i][j].adj);}printf("\n");}}//计算顶点的度void Du(MGraph G){int i,j,count1[10]={0},count2[10]={0};for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(G.arcs[i][j].adj) {count1[i]++; count2[j]++;} }}printf("a b c d 出度\n");for(i=0;i<4;i++)printf("%d ",count1[i]);printf("\na b c d 入度\n");for(j=0;j<4;j++)printf("%d ",count2[j]);printf("\n");}/***********************图主函数*************************/ void main(){MGraph G;CreateGraph(G);system("cls");printf_adjmatrix(G);Du(G);}。

矩阵及其基本算法矩阵是数学和计算机科学中常见的概念，它是由一组数按照固定的行数和列数排列成的矩形阵列。

矩阵在各个领域中具有重要的应用，如代数学、线性方程组的求解、图像处理、数据分析等。

本文将介绍矩阵的基本概念和常见的算法。

1.矩阵的基本概念：-矩阵的行数和列数被称为矩阵的维度。

一个mxn的矩阵有m行n列。

-矩阵元素指的是矩阵中的每个个体数值，可以用a[i][j]表示，其中i表示行数，j表示列数。

-方阵是指行数和列数相等的矩阵，即nxn的矩阵。

-零矩阵是所有元素都是0的矩阵，通常用0表示。

-单位矩阵是一个方阵，其对角线上的元素都是1，其余元素都是0。

2.矩阵的运算：-矩阵的加法：两个相同大小的矩阵相加，即对应位置的元素相加。

-矩阵的减法：两个相同大小的矩阵相减，即对应位置的元素相减。

-矩阵的乘法：两个矩阵相乘，要求左操作数矩阵的列数等于右操作数矩阵的行数。

结果矩阵的行数等于左操作数矩阵的行数，列数等于右操作数矩阵的列数。

乘法运算是对应位置的元素相乘再求和的过程。

-矩阵的转置：将mxn的矩阵转置为nxm的矩阵，即原矩阵的行列互换。

3.矩阵的基本算法：-矩阵的求逆：对于一个可逆矩阵A，存在一个矩阵B，使得A与B的乘积等于单位矩阵。

求逆矩阵的常用方法是高斯-约当消元法。

-矩阵的行列式：行列式是一个与方阵相关的标量，它可以通过递归计算进行求解。

行列式的值可以用于判断矩阵是否可逆，以及计算矩阵的特征值等。

-矩阵的特征值和特征向量：特征值是一个标量，特征向量是与特征值相关联的非零向量。

特征值和特征向量在矩阵的特征值分解、主成分分析等领域有着重要应用。

4.应用实例：-线性方程组的求解：线性方程组可以表示为一个矩阵乘以一个向量的形式，通过求解矩阵的逆，可以得到方程组的解。

-图像处理：图像可以表示为一个像素矩阵，通过对矩阵的像素进行运算，可以实现图像的旋转、缩放、滤波等操作。

-数据分析：矩阵在数据分析中广泛应用，如矩阵分解、矩阵乘法、矩阵求逆等操作可以用于数据降维、主要成分分析、聚类分析等。

数据结构25：矩阵转置算法（三元组顺序表）矩阵的转置实际上就是将数据元素的⾏标和列标互换，即 T(i,j) = M(j,i) 。

例如：图1 矩阵的转置相应地，三元组表转变为：图2 三元组表矩阵的转置，经历了三个步骤：矩阵的⾏数 n 和列数 m 的值交换；将三元组中的i和j调换；转换之后的表同样按照⾏序（置换前的列序）为主序，进⾏排序；实现三元组的转换，重点在第三步，实现算法有两种。

普通算法普通算法的实现过程为：1. 将矩阵的⾏数和列数进⾏调换；2. 遍历表 a 的 j 列（查找 j 的值，从 1 ⼀直到未转置之前的矩阵的列数 m ），遍历的过程，就可以⾃动存储为表 b 的形式。

因为在表 a 中 i 列的数值是从⼩到⼤的，在根据 j 列由上到下的遍历时， i 列同样也是有序的。

实现代码：TSMatrix transposeMatrix(TSMatrix M, TSMatrix T){ //⾏和列置换 T.m = M.n; T.n = M.m; T.num = M.num; if (T.num) { int q = 0; //依次遍历M矩阵的列（从1开始），的遍历的过程中将⾏标和列标置换，得到置换后的三元表T for (int col=1; col<=M.m; col++) { for (int p=0; p<M.num; 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].data = M.data[p].data; q++; } } } } return T;}此算法的时间复杂度关键在于嵌套的两个 for 循环，时间复杂度为O(m*num)，和矩阵的列数以及⾮ 0 元素的个数的乘积成正⽐，如果稀疏矩阵的⾮ 0 元素很多的情况，使⽤这个算法，虽然⼀定程度上节省了空间，但是时间复杂度会很⾼。