网站建设制作公司知道万维科技,网站网站建设企业,国家信用信息公示系统山东,夏天做哪个网站能致富稀疏矩阵、矩阵压缩、稀疏矩阵的快速转置、十字链表 目录 稀疏矩阵、矩阵压缩、稀疏矩阵的快速转置、十字链表1.数组2.数组的顺序表示和实现3.特殊矩阵的压缩存储#xff08;1#xff09;. 上三角矩阵—列为主序压缩存储#xff08;2#xff09;. 下三角矩阵—**行为主序压…稀疏矩阵、矩阵压缩、稀疏矩阵的快速转置、十字链表 目录 稀疏矩阵、矩阵压缩、稀疏矩阵的快速转置、十字链表1.数组2.数组的顺序表示和实现3.特殊矩阵的压缩存储1. 上三角矩阵—列为主序压缩存储2. 下三角矩阵—**行为主序压缩存储**3. 对称矩阵4. 对角矩阵 4. 稀疏矩阵5. 稀疏矩阵的压缩1. 三元组顺序表2. 行逻辑联接的顺序表3. 十字链表 6. 稀疏矩阵的转置普通转置 和 快速转置方法一普通转置复杂度为O(T.mu×T.nu)方法二快速转置 复杂度O(S.nuS.tu) 前几期期链接
【数据结构】栈与队列的概念和基本操作代码实现【数据结构】树与二叉树的概念与基本操作代码实现
1.数组
k维数组的定义 k 维数组 D { a j 1 , j 2 , . . . , j k } k维数组D\{ a_{j_1, j_2, ..., j_k} \} k维数组D{aj1,j2,...,jk} k 0 称为数组的维数 b i 是数组第 i 维的长度 j i 是数组元素第 i 维的下标 k0称为数组的维数b_i是数组第i维的长度j_i是数组元素第 i维的下标 k0称为数组的维数bi是数组第i维的长度ji是数组元素第i维的下标 a j 1 , j 2 , . . . , j k 属于 E l e m S e t ( 元素的性质相同 ) Y i 0 , . . . , b i − 1 ( i 1 , 2 , … , k ) a_{j_1, j_2, ..., j_k}属于ElemSet(元素的性质相同)Y_{i}0, ..., b_i -1 ( i1, 2, …, k) aj1,j2,...,jk属于ElemSet(元素的性质相同)Yi0,...,bi−1(i1,2,…,k) 数组可以看作是一种特殊的线性表即线性表数据元素本身又是一个线性表 数组特点 数组结构固定每一维的大小不可变 数据元素同构(元素性质相同) 数组运算 给定一组下标存取、修改相应的数据元素一般不做插入、删除操作。
2.数组的顺序表示和实现
二维数组有两种顺序映象的方式 以行序为主序:从数组的第一行开始依次存放每一行的数组元素;存放第i行时从第一列开始顺次存放 特点有地址计算公式可以随机访问 二维数组任意元素的存储地址 L o c ( a i j ) L o c ( a 11 ) [ ( i − 1 ) n ( j − 1 ) ] ∗ L Loc( a_{ij})Loc(a_{11})[(i-1)n(j-1)]*L Loc(aij)Loc(a11)[(i−1)n(j−1)]∗L L o c ( a 11 ) 称为基地址或基址 Loc(a_{11})称为基地址或基址 Loc(a11)称为基地址或基址 以列序为主序: 二维数组任意元素的存储地址 L o c ( a i j ) L o c ( a 11 ) [ ( j − 1 ) m ( i − 1 ) ] ∗ L Loc( a_{ij})Loc(a_{11})[(j-1)m(i-1)]*L Loc(aij)Loc(a11)[(j−1)m(i−1)]∗L L o c ( a 11 ) 称为基地址或基址 Loc(a_{11})称为基地址或基址 Loc(a11)称为基地址或基址
可将二维数组的行为主序和列为主序的存储方式推广到一般情况可得到 n 维数组数据元素存储位置的映象关系
3.特殊矩阵的压缩存储 宗旨为值相同的矩阵元素只分配一个空间对零元不分配存储空间. (1) 特殊矩阵非零元在矩阵中的分布有一定规则 上下三角矩阵对称矩阵对角矩阵 (2.)稀疏阵零元多分布无规律
1. 上三角矩阵—列为主序压缩存储 存储方式列为主序压缩存储和行为主序压缩存储存储空间是一维的将二维数组以一维方式存储。 特点均可以随机访问数组元素。 上三角矩阵—列为主序压缩存储–数组sa[M]
(1)下三角为0时 当i≤j时aij为非0元存放地址Loc(aij)的计算公式 L o c ( a i j ) L o c ( a 11 ) ( ( j − 1 ) ⋅ j 2 i − 1 ) ⋅ L , ( c o n d i t i o n : i ≤ j ) Loc(a_{ij}) Loc(a_{11})(\frac{(j-1)\cdot j}{2}i-1)\cdot L , (condition:i≤j ) Loc(aij)Loc(a11)(2(j−1)⋅ji−1)⋅L,(condition:i≤j)
一维存储空间用一维数组sa[M]表示 Loc(aij)计算公式a11存于sa[0],地址为0 L o c ( a i j ) 0 ( ( j − 1 ) ⋅ j 2 i − 1 ) ⋅ 1 , ( c o n d i t i o n : i ≤ j ) Loc(a_{ij}) 0(\frac{(j-1)\cdot j}{2}i-1)\cdot 1, (condition:i≤j ) Loc(aij)0(2(j−1)⋅ji−1)⋅1,(condition:i≤j) 数组sa的大小: M ( n 1 ) ⋅ n 2 M\frac{(n1)\cdot n}{2} M2(n1)⋅n
aij(i≤j)存于下标为k的一维数组元素中: L o c ( a i j ) k ( j − 1 ) ⋅ j 2 i − 1 Loc(aij)k\frac{(j-1)\cdot j}{2}i-1 Loc(aij)k2(j−1)⋅ji−1
(2)下三角为常数时 常数的存放的位置为 ( n 1 ) ⋅ n 2 \frac{(n1)\cdot n}{2} 2(n1)⋅n 数组sa的大小: M ( n 1 ) ⋅ n 2 1 M\frac{(n1)\cdot n}{2}1 M2(n1)⋅n1
2. 下三角矩阵—行为主序压缩存储 存储方式列为主序压缩存储和行为主序压缩存储存储空间是一维的将二维数组以一维方式存储。 行为主序压缩存储从第一行开始依次存放每一行的“非0C元” 特点均可以随机访问数组元素。 下三角矩阵—行为主序压缩存储–数组sa[M]
(1)上三角为0时 当 j≤i时aij为非0元存放地址Loc(aij)的计算公式 L o c ( a i j ) L o c ( a 11 ) ( ( i − 1 ) ⋅ i 2 j − 1 ) ⋅ L , ( c o n d i t i o n : j ≤ i ) Loc(a_{ij}) Loc(a_{11})(\frac{(i-1)\cdot i}{2}j-1)\cdot L , (condition:j≤i ) Loc(aij)Loc(a11)(2(i−1)⋅ij−1)⋅L,(condition:j≤i)
一维存储空间用一维数组sa[M]表示 Loc(aij)计算公式a11存于sa[0],地址为0 L o c ( a i j ) 0 ( ( i − 1 ) ⋅ i 2 j − 1 ) ⋅ 1 , ( c o n d i t i o n : j ≤ i ) Loc(a_{ij}) 0(\frac{(i-1)\cdot i}{2}j-1)\cdot 1, (condition:j≤i ) Loc(aij)0(2(i−1)⋅ij−1)⋅1,(condition:j≤i) 数组sa的大小: M ( n 1 ) ⋅ n 2 M\frac{(n1)\cdot n}{2} M2(n1)⋅n
aij(i≤j)存于下标为k的一维数组元素中: L o c ( a i j ) k ( i − 1 ) ⋅ i 2 j − 1 Loc(aij)k\frac{(i-1)\cdot i}{2}j-1 Loc(aij)k2(i−1)⋅ij−1
上三角为常数时 常数的存放的位置为 ( n 1 ) ⋅ n 2 \frac{(n1)\cdot n}{2} 2(n1)⋅n 数组sa的大小: M ( n 1 ) ⋅ n 2 1 M\frac{(n1)\cdot n}{2}1 M2(n1)⋅n1
3. 对称矩阵
存放方式只存上三角阵或只存下三角阵都可以
地址计算公式 : 参考上三角和下三角矩阵的地址计算公式
4. 对角矩阵
对角矩阵 –2d1对角阵主对角线和主对角线上面d条对角线、主对角线下面d条对角线上的数据元素分布不规律非0C. 2d1 对角阵特点**第一行和最后一行每行有d1个数据元素**余下每行**最多**2d1个数据元素 压缩存储方法第一行和最后一行每行存 d1 个数据元素余下每行存 2d1 个数据元素
2d1-对角阵行为主序压缩存储地址计算公式 矩阵元素下标从0开始的地址计算公式 L o c ( a i j ) L o c ( a 00 ) ( 2 d 1 ) ∗ i − d j − ( i − d ) L o c ( a 00 ) ( 2 d 1 ) ∗ i j − i Loc(a_{ij})Loc(a_{00})(2d1)*i-dj-(i-d) Loc(a_{00})(2d1)*ij-i Loc(aij)Loc(a00)(2d1)∗i−dj−(i−d)Loc(a00)(2d1)∗ij−i 0 ≤ i , j n , ∣ i − j ∣ ≤ d 0≤i,jn, |i-j|≤d 0≤i,jn,∣i−j∣≤d
§矩阵元素下标从1开始的地址计算公式 L o c ( a i j ) L o c ( a 11 ) ( 2 d 1 ) ∗ ( i − 1 ) − d j − i d L o c ( a 11 ) ( 2 d 1 ) ∗ ( i − 1 ) j − i Loc(a_{ij})Loc(a_{11})(2d1)*(i-1)-dj-id Loc(a_{11})(2d1)*(i-1)j-i Loc(aij)Loc(a11)(2d1)∗(i−1)−dj−idLoc(a11)(2d1)∗(i−1)j−i 1 ≤ i , j ≤ n , ∣ i − j ∣ ≤ d 1≤i,j≤n, |i-j|≤d 1≤i,j≤n,∣i−j∣≤d
4. 稀疏矩阵
稀疏矩阵: 矩阵元素零元多在矩阵中随机出现 假设 m行 n列的矩阵含 t个非零元素,则稀疏因子 δ t m ⋅ n δ \frac{t}{m\cdot n} δm⋅nt 通常认为 δ ≤ 0.05 的矩阵为稀疏矩阵。 压缩存储原则只存储每个非零元的行、列下标及其值和矩阵的行列维数 常规存储方法缺点: (1) 零值元素占了很大空间; (2) 计算中进行了很多和零值的运算遇除法还需判别除数是否为零。 解决问题的原则: (1) 尽可能少存或不存零值元素 (2) 尽可能减少没有实际意义的运算 (3) 操作方便。 即尽可能快地找到与下标值(i,j)对应的元素尽可能快地找到同一行或同一列的非零值元。 5. 稀疏矩阵的压缩
稀疏矩阵的压缩存储方法: 1. 三元组顺序表 2. 行逻辑联接的顺序表 3. 十字链表 1. 三元组顺序表
三元表结构
//三元表结构
typedef struct{ int i, j; //非零元的行、列下标 int e; //非零元的值
} Triple;//稀疏矩阵的结构
#define MAXSIZE 100 //非零元最大个数
typedef struct{ Triple data[MAXSIZE 1]; //三元组表data[0]未用int mu, nu, tu; //矩阵行、列数、非零元个数
} TSMatrix; 特点 有序的双下标法行序有序存储 便于进行依行顺序处理的矩阵运算 若需存取某一行中的非零元需**从头开始查找**。 压缩存储后元素aij的存储位置与其下标无关而取决于之前的非零元个数 非零元以行为主序顺序存放
2. 行逻辑联接的顺序表 #define MAXRC 500
//行逻辑联接的顺序表
typedef struct {Triple data[MAXSIZE 1];int rpos[MAXRC 1]; // 每一行非0元存放的起始位置int mu, nu, tu;
} RLSMatrix; // 行逻辑链接顺序表类型 3. 十字链表
用三元组表存储稀疏矩阵在单纯的存储和做类似转置之类的运算时可以节约存储空间且运算速度较快; 但当进行矩阵相加等运算时稀疏矩阵的非零元位置和个数都会发生变化。使用三元组表必然会引起数组元素的大量移动。 采用链表存放稀疏矩阵的非0元将稀疏矩阵每行的非0元按照列升序的顺序放在一个单链表中将稀疏矩阵每列的非0元按照行升序的顺序放在一个单链表中 即 稀疏矩阵的每个非0元即位于一个行单链表也同时位于一个列单链表 用一维数组保存每行非0元的单链表的头指针 用一维数组保存每列非0元的单链表的头指针 十字链表 每个非零元用含有五个域的结点表示非零元的所在行、列、值及同行、同列的下一个非零元
//十字链表
typedef struct OLNode{ int row, col; //非零元所在行、列int val; //非零元的值struct OLNode*right, *down;//同行、同列的下一个非零元
}OLNode,* OLink;typedef struct{ OLink rhead[M],chead[N]; //行、列指针数组int mu, nu, tu; //行、列数及非零元个数
}CrossList;6. 稀疏矩阵的转置普通转置 和 快速转置
解决思路 将矩阵行、列维数互换非零元个数不变将每个三元组中的i和j相互调换非零元值不变重排次序使T.data中元素以T的行(M的列)为主序 方法一普通转置复杂度为O(T.mu×T.nu)
按矩阵T中三元组表T.data的次序依次在矩阵M的三元组表M.data中找到相应三元组进行转置 为找到M.data中第i列所有非零元素需对M.data扫描一遍 由于M.data以M行序为主序所以得到的恰是T.data中应有的顺序
//复杂度为O(T.mu×T.nu)
Status TransposeSMatrix(TSMatrix M, TSMatrix T){ int col, p, k;T.muM.nu; T.nuM.mu; T.tuM.tu; if(T.tu){ //有非零元转置k1;//k为T.data表下标for(col1;colM.nu;col)//查找M每一列的非零元for( p1;pM.tu;p)//扫描M的所有非零元if( M.data[p].jcol ){ T.data[k].iM.data[p].j;T.data[k].jM.data[p].i;T.data[k].eM.data[p].e; k;}return OK;}return ERROR;
}//T(n)O(M.nu×M.tu)
//若M.tu与M.mu×M.nu同数量级则 T(n)O(M.mu×M.nu^2)
方法二快速转置 复杂度O(S.nuS.tu)
//复杂度O(S.nuS.tu)
//若S.tu与S.mu×S.nu同数量级则 T(n)O(S.mu×S.nu)
void TransPose_F(TSMatrix S,TSMatrix Transpose_S){//S为原来矩阵//Transpose_S为转置后矩阵Transpose_S.muS.nu;Transpose_S.nuS.mu;Transpose_S.tuS.tu;if(S.tu){//判断是否为空int col;//列int num[MAXSIZE]{0};// 记录原三元组中列号为 col 的项的数目。 辅助数组int cpot[MAXSIZE]{0};// 记录原三元组中列号为 col 的项在新三元组中的首位置。 辅助数组//扫描第一次 记录元素矩阵S中列数为j的个数for(int i1;iS.tu;i){//记录元素矩阵S中列数为j的个数num[S.data[i].j];}cpot[1]1;//初始化第一个元素的地址//扫描第二次 记录原三元组中列号为 col 的项在新三元组中的首位置for(col2;colS.nu;col){//列号为 col 的项在新三元组中的首位置cpot[col]cpot[col-1]num[col-1];}//扫描第三次 转置for(int t1;tS.tu;t){colS.data[t].j;//列数int scpot[col];//地址 下标Transpose_S.data[s].eS.data[t].e;Transpose_S.data[s].iS.data[t].j;Transpose_S.data[s].jS.data[t].i;cpot[col];//下标 后移}}
}
感谢阅读 前几期期链接
【数据结构】栈与队列的概念和基本操作代码实现【数据结构】树与二叉树的概念与基本操作代码实现
