[化学]数据结构CH5 数组和广义表.pptVIP

CH5 数组和广义表 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 存储结构的选择: 由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 1.一维数组 数组的存储 (a) 以行为主序 (b) 以列为主序 2.二维数组及多维数组 （1）行优先顺序存储 5.2 数组的顺序表示和实现 可以推广到多维数组的行优先顺序存储 行优先顺序存储也称为低下标优先或左边下标优先于右边下标。 多维数组按行优先存放到内存的规律： 最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。 因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。 （2）列优先顺序存储 5.2 数组的顺序表示和实现 可以推广到多维数组的列优先顺序存储 列优先顺序存储也称为高下标优先或右边下标优先于左边下标。 多维数组按列优先存放到内存的规律： 最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。 因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。 5.3矩阵的压缩存储 给多个值相同的元素只分配一个存储单元， 或者对值为零的元素不分配存储单元。 5.3.1 特殊矩阵 一、对称矩阵 定义 若一个n阶方阵A中元素满足下列条件： aij＝aji （其中 1 ≤i, j≤n） 则称A为对称矩阵。 压缩存储方案 只存下三角 只存上三角 （1）只存放下三角部分（行优先） （2）只存放上三角部分（行优先） 二、三角矩阵 （1）下三角矩阵（行优先） （2）上三角矩阵（行优先） 三、对角矩阵 定义 若n阶矩阵A的所有非0元集中在以住对角线为中心的带状区域内，称A为n阶对角矩阵。（如图为三对角矩阵） 三、对角矩阵 压缩方案： 方案1：按行主序依次将矩阵非0元存入一维数组sa[0..3n-2]中。 三、对角矩阵 压缩方案 方案2：按列主序存储非0元素 例1 ：稀疏矩阵的压缩存储 由a求其转置矩阵b，需做以下事情： ⑴ 矩阵的行列值互换，即若a为 m×n,则 b为 n×m ⑵ 每个三元组的行列号互换，即aij对应于 bji ⑵ 以原阵的行序产生转置后的三元组，并置入b中的恰当位置---快速矩阵转置算法 算法思想： ⑴ 设置num[l..M.nu]和cpot[l..M.nu]两个辅助向量； ⑵ 在M.data中求矩阵的每一列中非零元素个数，存于辅助向量num的对应列中； ⑶ 用递推公式算出每一列第一个非零元素在T.data中的位置，存于辅助向量cpot的对应列中，递推公式为： cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1], col=2..a.nu ⑷ 依次对M.data中的三元组进行转置，并按三元组的列号，从cpot的对应列取出该三元组应存放在T.data中的位置，然后将cpot该列中的值加1，使其记载该列下一非零元素在T.data中的位置。 2.行逻辑链接的顺序表 typedef struct{ Triple data[MAXSIZE+1]; //非0元三元组表 int rpos[MAXC+1]; //各行第一个非0元的位置表 int mu,nu,tu; //矩阵的行数、列数、非0元个数 }RLSMatrix 说明： M.rpos[1]＝1 M.rpos[row]＝M.rpos[row－1]＋num[row－1] (2≤row≤M.mu) M.rpos[row＋1]－1:第row行最后一个非0元在M.data中的位置。（ 1≤row≤M.mu－1) M.tu:最后一行的最后一个非0元在