????
关于多维数据的存储有一些公式需要记忆,其实可以很容易推理出来,但是感觉有时候脑子不知道怎么那么笨,容易一下子就走神,记录一下.
?
特殊矩阵
???
所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。
②元素aij的存放位置
???
aij元素前有i行(从第0行到第i-1行),一共有:
????????
1+2+…+i=i?(i+1)/2个元素;
???
在第i行上,aij之前恰有j个元素(即ai0,ail,…,ai,j-1),因此有:
??????????
sa[i?(i+1)/2+j]= aij?
③aij和sa[k]之间的对应关系:
???
若i≥j,k=i?(i+1)/2+j??
0≤k<n(n+1)/2<br>
???
若i<j,k=j?(j+1)/2+i??
0≤k<n(n+1)/2<br>
???
令I=max(i,j),J=min(i,j),则k和i,j的对应关系可统一为:
????????
k=i?(i+1)/2+j 0≤k<n(n+1)/2?<br>
(3)对称矩阵的地址计算公式
? LOC(aij)=LOC(sa[k])
?????????
=LOC(sa[0])+k?d=LOC(sa[0])+[I?(I+1)/2+J]?d
???
通过下标变换公式,能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。
?
【例】a21和a12均存储在sa[4]中,这是因为
??????????
k=I?(I+1)/2+J=2?(2+1)/2+1=4
2、三角矩阵??
(1)三角矩阵的划分
???
以主对角线划分,三角矩阵有上三角矩阵和下三角矩阵两种。
①上三角矩阵
???
如下图(a)所示,它的下三角(不包括主角线)中的元素均为常数c。
②下三角矩阵
???
与上三角矩阵相反,它的主对角线上方均为常数c,如下图(b)所示。
? 注意:
???
在多数情况下,三角矩阵的常数c为零。
(2)三角矩阵的压缩存储
???
三角矩阵中的重复元素c可共享一个存储空间,其余的元素正好有n?(n+1)/2个,因此,三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中,其中c存放在向量的最后一个分量中。
??
① 上三角矩阵中aij和sa[k]之间的对应关系
???
上三角矩阵中,主对角线之上的第p行(0≤p<n)恰有n-p个元素,按行优先顺序存放上三角矩阵中的元素a<sub>ij时:
????
aij元素前有i行(从第0行到第i-1行),一共有:
???????
(n-0)+(n-1)+(n-2)+…+(n-i)=i?(2n-i+1)/2个元素;
???
在第i行上,aij之前恰有j-i个元素(即aij,ai,j+l,…,ai,j-1),因此有:
?????????
sa[i?(2n-i+1)/2+j-i]= aij?
所以:
?
? ?┌i?(2n-i+1)/2+j-i 当i≤j
?? k=│
?????
└n?(n+1)/2 当i>j
②下三角矩阵中aij和sa[k]之间的对应关系
?? ?
┌i?(i+1)/2+j 当i≥j
?? k=│
??? └n?(n+1)/2
当i<j
? 注意:
???
三角矩阵的压缩存储结构是随机存取结构。
3.对角矩阵
???
所有的非零元素集中在以主对角线为中心的带状区域中,即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外,其余元素皆为零的矩阵为对角矩阵。
【例】下图给出了一个三对角矩阵。
???????????
????
其中:
???
非零元素仅出现在主对角上(aii,0≤i≤n-1),紧邻主对角线上面的那条对角线上(ai,i+1
,0≤i≤n-2)和紧邻主对角线下面的那条对角线上(a
i+1,i,0≤i≤n-2)。当|i-j|>1时,元素aij=0。
???
由此可知,一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵:
???????????
若|i-j|>(k-1)/2,则元素aij=0。
???
对角矩阵可按行优先顺序或对角线的顺序,将其压缩存储到一个向量中,并且也能找到每个非零元素和向量下标的对应关系。具体【参见练习】
分享到:
相关推荐
本资源关于数据结构中的多维数组的设计与使用
严蔚敏习题集上的课程设计,比较容易理解的
数据结构源码:多维数组,这是一个关于多维数组是数据结构源码
多维数组是一维数组的推广 多维数组是一种非线性结构。其特点是每一个数据元素可以有多个直接前驱和多个直接后继 数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性结构简单
数据结构课程设计多维数组.docx
基于c语言的数据结构程序设计 附有报告
数据结构课程设计 设计并模拟实现整型多维数组类型
主要概念字符串和数组的概念性知识:二者的逻辑结构、存储结构。
如何计算多维数组的地址----数据结构.pdf
自考数据结构第五章 多维数组 多维数组和广义表是一种复杂的非线性结构,它们的逻辑特征是:一个数据元素可能有多个直接前驱和多个直接后继。
数据结构与算法多维数组与广义表PPT学习教案.pptx
数据结构 1-9章课程笔记 word版 详细介绍数据结构基础知识和相关实验 数据结构 C++版 电子笔记 线性表 栈、队 列 串 多维数组 广义表 树 二叉树 图 查找技术 排序技术 索引技术
数据结构实验内容:线性表(顺序表实现)、线性表(单链表实现)、栈、字符串、多维数组(三元组表存矩阵)、二叉树(二叉链表和顺序表存储)、邻接表存图以及图的遍历、排序 实验报告部分只要求了线性表、栈、多维...
数据结构及算法导论 详细介绍线性表,栈和队列,串,多维数组及广义表,树,图,排序,查找等数据结构及算法描述,PDF格式,很清晰……
数据结构算法,线性表、栈和队列、字符串和多维数组、树和二叉树、图、查找技术、排序技术、索引技术
数据结构课程设计 用户定义的多维数组 代码 C++
C++数据结构(第2版)课件第4章字符串和多维数组.ppt
(2)掌握线数组和广义表储存结构的定义及C语言实现; (3)掌握数组和广义表的各种基本操作; (4)学会利用数组和广义表的基本知识解决实际问题。 三、实验内容: 若矩阵中的某个元素是第i行中的最小值,同时又是...
数据结构中的多维数组实验,简单易懂,希望有帮助
本资源为《数据结构(严蔚敏_吴伟民)》一书的【课程代码】(敲黑板,并不是电子书),共有45个实验的代码,所有代码均可执行(并含有20%代码注释),代码风格和教材保持统一。 例如排序算法、字符串、链表、树、图...