网站地址是什么,网页游戏开服表时间,网站里面的链接怎么做,项目建设管理费目录 一、多维数组#xff08;一#xff09;数组的定义#xff08;二#xff09;二维数组#xff08;三#xff09;多维数组的存储#xff08;四#xff09;多维数组的下标的相关计算 二、矩阵#xff08;一#xff09;特殊矩阵和稀疏矩阵#xff08;二#xff09;… 目录 一、多维数组一数组的定义二二维数组三多维数组的存储四多维数组的下标的相关计算 二、矩阵一特殊矩阵和稀疏矩阵二对称矩阵三对角矩阵四稀疏矩阵的压缩存储 三、广义表一广义表的定义二广义表的表头和表尾三广义表的深度和长度四广义表表示二叉树 一、多维数组
一数组的定义
数组是由nn≥1个相同数据类型的数据元素组成的有限序列在定义数组时会为数组分配一个固定大小的内存空间用来存储元素数组在被定义后其维度不可以被改变。 数组在确定其维度和维界后元素的个数是固定的所以不能进行插入和删除运算。数组中最常见的两种操作是查找和修改。 二二维数组
数组可分为一维数组和多维数组常见的有二维数组二维数组可以看作一维数组的一维数组。顺序表是一个一维数组所以它是线性结构与栈、队列、串的逻辑结构相同而多维数组则是典型的非线性结构也可以说它是嵌套的线性结构。
例如一个二维数组A[3][4]在内存中实际上是一个长度为3的一维数组每个元素是一个长度为4的一维数组即对应三行四列其中元素是从上到下、从左到右依次存储的如下
01230[00][01][02][03]1[10][11][12][13]2[20][21][22][23] 由于数组中是从下标0开始的所以一个m行n列的二维数组中最开始的元素是[00]最后的元素是[m-1n-1]上面三行四列的二维数组A[3][4]中的最后一个元素即为[23]。 三多维数组的存储
二维数组的存储较一维数组不一样有两种存储方式可分为行优先存储和列优先存储前者是先按每行存储满后再继续下一行后者相反先按每列存储满后再继续下一列。
例如定义一个二维数组A[3][3]在连续的内存空间里如下
若按照行优先存储以A[2][0]为例在存储A[2][0]之前是这样存储的 而按照列优先存储以A[1][1]为例在存储A[1][1]之前是这样存储的
四多维数组的下标的相关计算
设一个二维数组A[i][j]其中行下标和列下标的范围分别为[0a]和[0b]若每个数组元素在内存中占用L个存储单元且数组中第一个元素的存储位置为LOC[c1][c2]求该二维数组中任意一元素A[i][j]的存储位置
1、按行优先存储 【所求行乘列界限加1然后加所求列确定位置】 1先确定有多少行加上列数然后乘以存储单元最后加上第一个元素的存储位置得LOC[i][j]LOC[c1][c2][(i-c1)×(b-c21)(j-c2)]×L。 2若在编程语言中由于数组元素下标是从0开始的该式子改写为LOC[i][j]LOC[0][0][i×(b1)j]×L。 例、二维数组A[m][n]采用行序为主方式存储每个元素占L个存储单位。元素A[0][0]的存储地址是b求元素A[i][j]0 ≤ i ≤ m-10 ≤ j ≤ n-1的存储地址。 解析由于二维数组中行列元素都是从0开始的即LOC[i][j]b[i×(n-11)j]×Lb[i×nj]×L。 2、按列优先存储 【所求列乘行界限加1然后加所求行确定位置】 1先确定有多少列加上行数然后乘以存储单元最后加上第一个元素的存储位置得LOC[i][j]LOC[c1][c2][(j-c1)×(a-c21)(j-c1)]×L。 2若在编程语言中由于数组元素下标是从0开始的该式子改写为 LOC[i][j]LOC[0][0][j×(a1)i]×L。 例、设7行6列的数组a以列序为主序顺序存储基地址为1024每个元素占2个存储单元架设无第0行第0列求第4行第5列的元素的存储地址。 解析由于第一个元素为a[1][1]所以要减去后再代入计算即 LOC[4][5]1024[(5-1)×(7-11)(4-1)]×21024621086。
对于一个数组An×n方阵其元素aij按行优先与按列优先存储时地址之差为(n-1)(i-j)。
二、矩阵
一特殊矩阵和稀疏矩阵
相同的元素或零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵反之则为稀疏矩阵。简单的来说特殊矩阵既然特殊说明其中有很多相同或者有零元素且存在一定规律在矩阵中分布。
常见的特殊矩阵有对称矩阵、反对称矩阵、上/下三角矩阵、对角矩阵等等例如对角矩阵中只有对角线上有元素其余元素均为零
二对称矩阵
若一个方阵满足Ai×jAj×i则称为对称矩阵。由于对称矩阵中上三角部分和下三角部分的元素对应相同在存储对称矩阵时为了避免空间的浪费可以只存储上或下三角部分的元素将其存放在一个一维数组中该数组的大小为12……nn(1n)/2。
三对角矩阵
三对角矩阵就是一种对角矩阵其中非零元素都集中在以主对角线为中心的三条对角线的区域中其他区域均为零。
四稀疏矩阵的压缩存储
前面讲到稀疏矩阵中非零元素的分布与特殊矩阵相反是没有规律的。稀疏矩阵中大部分元素都为0且与非零元素的分布一样也是没有规律的。对矩阵压缩的目的是节省存储空间。 1、三元组表 为了压缩存储稀疏矩阵在存储时不仅要存储矩阵中非零元素的值同时还要存储该元素所在的行与列从而组成一个三元组表行、列、值依此减少了存储空间。由于是将稀疏矩阵中的非零元素以及其对应的行、列号以三元组的形式存储在一个数组中所以经过这种压缩存储后就无法通过数组的下标直接存取矩阵的元素失去了随机存取的特性。另外稀疏矩阵的三元组表也可以采用十字链表法存储。【稀疏矩阵的两种存储结构是三元组表数组和十字链表】
//以整型int为例可替换其他类型
typedef struct{int i,j; //行与列int x; //值
}Sparsematrix;例如一个稀疏矩阵A进行压缩存储 对应的三元组表如下
i行j列x值114132205 例如有一个100×90的稀疏矩阵非0元素有10个设每个整型数占2字节则用三元组表示矩阵时求所需的字节数。 解析三元组表包括行、列、值每个整型数占2字节所以10个非0元素占3×2×1060字节另外还有三元组表中行数、列数和总的非零元素个数共6个字节一共60666字节。
2、十字链表 十字链表法中稀疏矩阵的行和列都用一个带头结点的链表表示从而对应着五个分量行、列、数据域、指向下方结点的指针和指向右方结点的指针其结点的结构如下
三、广义表
一广义表的定义
广义表是线性表的进一步推广是由nn≥0个数据元素组成的有序序列。线性表中的数据元素只能是单个元素原子它是不可分割的而广义表中的数据元素既可以是原子也可以是一个广义表包括空表和非空表广义表通过圆括号“()”括起来通过逗号“,”隔开表中的各个数据元素。 一个n维数组可以看成元素是n-1维数组的广义表广义表的元素都是n-1维数组。另外若广义表中的所有元素都是原子时此时的广义表就是一个线性表。 二广义表的表头和表尾
广义表是可以递归的一个广义表也可以是其自身的子表广义表中的第一个元素称为广义表的表头而剩余数据元素组成的表称为广义表的表尾广义表的表头和表尾可以看作通过函数Head()和Tail()对广义表操作。任何一个非空广义表表头可能是单个元素原子或广义表但表尾只可能是广义表其原因是广义表的取表尾Tail()是非空广义表除去表头元素后剩余元素组成的表所以不可能是原子。 例如C(a,b,c,d,e,f,g)该广义表的表头是(a)表尾是(b,c,d,e,f,g) 例如D((a,b),((c,d,e),(f,g,h)))该广义表的表头是(a,b)表尾是((c,d,e),(f,g,h))。
另外若一个广义表为空则为一个空表。例如E( )F(( ))广义表E是一个空表只有非空广义表才能取表头广义表F的表头和表尾都是()。
三广义表的深度和长度
广义表的深度通过括号的层数求得而长度是广义表中所含元素的个数。
例如一个空广义表G()括号层数为1所以广义表的深度为1而由于是空表所以广义表的长度为0 例如一个广义表H((a,b),(c,(d,e)))括号层数为3所以广义表的深度为3最高层为(c,(d,e))逗号隔开了原子( c )和广义表( d,e )元素个数为2所以广义表的长度为2。 例如一个广义表I((),(a),(b,c,(d),((d,f))))由于括号的最大层数为4所以广义表的深度为4可知广义表有三个元素分别是()、(a)、(b,c,(d),((d,f)))元素个数为3所以广义表的长度为3。 例如设广义表J(( ),( ))对广义表Jhead(J)( )Tail(J)(( ))括号的最大层数为2所以广义表的深度为2广义表有两个元素分别是()、()元素个数为2所以广义表长度为2。 注这里的Tail(J)(( ))而不是( )。 四广义表表示二叉树
根据广义表中“ 数据元素既可以是原子也可以是一个广义表包括空表和非空表) ”这一点可以来表示二叉树即通过(根结点根结点的广义表)的形式来表示其中可以嵌套。 例如下面是一个满二叉树 通过广义表表示该二叉树 (A , ( B , ( D , E ) ) , ( C , ( F , G ) ) ) ) 这个二叉树的解释如下 根结点是A它的左孩子是BB的左孩子是DB的右孩子是E。 根结点A的右孩子是CC的左孩子是FC的右孩子是G。
