数据结构——矩阵

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

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

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

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

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

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

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

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

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

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

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

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

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

矩阵转置的概念：
矩阵的转置是指将一个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);}。

#include<stdio.h>#include <conio.h>#define MAXSIZE 12500#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{int i,j;int e;}Triple;typedef struct{Triple data[MAXSIZE+1];int mu,nu,tu;}TSMatrix;Status CreateSMatrix(TSMatrix &M) {int w,m,n;while(1){printf("请输入行:");scanf("%d",&M.mu);if(M.mu>0){break;}if(M.mu<=0){printf("行不能为0\n");continue;}}while(1){printf("请输入列:");scanf("%d",&M.nu);if(M.nu>0){break;}if(M.nu<=0){printf("列不能为0\n");continue;}}printf("请输入非零元素:");scanf("%d",&M.tu);for(w=1;w<=M.tu;w++){printf("请输入元素所在行，列，元素值：\n");scanf("%d %d %d",&M.data[w].i,&M.data[w].j,&M.data[w].e);if(M.data[w].i<=0||M.data[w].j<=0||M.data[w].i>M.mu||M.data[w].j>M.nu) {printf("输入错误1！\n");w--;}for(m=1;m<=w;m++){for(n=0;n<m;n++){if(M.data[m].i<M.data[n].i){printf("输入错误2！\n");w--;break;}else if(M.data[m].i==M.data[n].i&&M.data[m].j<M.data[n].j){printf("输入错误3！\n");w--;break;}else if(M.data[m].i==M.data[n].i&&M.data[m].j==M.data[n].j){printf("输入重复！\n");w--;break;}}}}return OK;Status ShowSMatrix(TSMatrix M){int i,j,t=1;printf("矩阵为：\n");for(i=1;i<=M.mu;i++){for(j=1;j<=M.nu;j++){if(M.data[t].i==i&&M.data[t].j==j){printf("%d\t",M.data[t].e);t++;}else printf("0\t");}printf("\n");}return OK;}Status TransposeSMatrix(TSMatrix M,TSMatrix &T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu; int col; int p,q;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;}}}}printf("矩阵转置成功！\n");printf("转置后的");ShowSMatrix(T);return OK;}Status DestorySMatrix(TSMatrix &M)M.mu=0;M.nu=0;M.tu=0;return OK;}Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){ int num[100];int cpot[100];int col,i,p,q;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( i = 1; i <=M.tu; ++i) {col =M.data[ i ] .j ; ++num [col] ;}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");printf("转置后的");ShowSMatrix(T);return OK;}int main(){printf("******************************\n");printf("****** 1.创建矩阵********\n");printf("****** 2.销毁矩阵********\n");printf("****** 3.输出矩阵********\n");printf("****** 4.转置矩阵********\n");printf("****** 5.快速转置矩阵********\n");printf("****** 6.转置矩阵对比********\n");printf("****** 7.输入一个负数退出*****\n");printf("******************************\n");TSMatrix M,T; int num; M.mu=0;do{printf("Please input the operation you need:"); scanf("%d",&num);switch(num){case 1:CreateSMatrix(M);printf("矩阵初始化成功!\n");break;case 2:if(M.mu==0){printf("矩阵不存在！\n");}else{DestorySMatrix(M);printf("矩阵已销毁！\n");}break;case 3:if(M.mu==0){printf("矩阵不存在！\n");}elseShowSMatrix(M);break;case 4:if(M.mu==0){printf("矩阵不存在！\n");}elseTransposeSMatrix(M,T);break;case 5:if(M.mu==0){printf("矩阵不存在！\n");}elseFastTransposeSMatrix(M,T);break;}}while(num>0);return 0;}。

数据结构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 元素很多的情况，使⽤这个算法，虽然⼀定程度上节省了空间，但是时间复杂度会很⾼。

数据结构矩阵
矩阵是一种常见的数据结构，它由一组相同类型的元素按照一定的排列方式组成的矩形表格。

矩阵在数学、计算机科学、物理学、统计学等领域有着广泛的应用。

在计算机科学中，矩阵常用于表示图形、图像、网络、关系等数据结构，常见的操作包括矩阵加法、矩阵乘法、矩阵转置、矩阵求逆等。

其中矩阵乘法是最重要的操作之一，因为它在计算机图形学、机器学习、信号处理等领域有着广泛的应用。

矩阵的实现方式有多种，包括二维数组、链表、稀疏矩阵等。

在实际应用中，需要根据不同的应用场景选择不同的实现方式，以达到最优的性能和空间效率。

总之，矩阵是一种重要的数据结构，它在计算机科学和其他领域中有着广泛的应用。

掌握矩阵的基本操作和实现方式，对于提高计算机科学的能力和解决实际问题都有着重要的作用。

- 1 -。