清华962数据结构 --- Ch5 数组和广义表
一、数组
1、定义
数组是由类型相同的数据元素构成的有序集合
数组一旦被定义,它的维数和维界就不再改变。因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操作。
2、顺序表示与实现
对二维数组有两种存储方式:以行序为主序 and 以列序为主序 这两个概念是比较好理解的,通过下面的图示可以一眼看出两者的区别所在,a 为列序,b 为行序
对于数组而言,一旦规定了它的维数和各维的长度,便可以为它分配存储空间;只要给出一组下标就可以求道相应数组元素的存储位置。
其中,LOC (0,0)是 的存储位置,也称为基地址; 是数组第二维的长度 由此我们可以将这个公式推广到 n 为维数组中 :
也可缩写为:
这个式子成为 n 为维数组的映像函数,其中 , ,
二、矩阵的压缩存储
什么是压缩存储: 为多个值相同的元只分配一个存储空间;对零不分配空间
假若值相同的元素或者零元素在矩阵中的分布有一定规律,我们就将他们成为特殊矩阵;反之称为稀疏矩阵
1、特殊矩阵
(1)对称矩阵
若一个 n 阶方阵 A 中的元满足 ,则称其为 n 阶对称矩阵 压缩策略:只存储主对角线+下三角区(或上三角区),可以将 个元压缩存储到 个元的空间中。
压缩矩阵与原矩阵的关系: 时, (矩阵为下三角矩阵时) 时, (矩阵为上三角矩阵时)
(2) 三角矩阵
压缩策略:按照行优先或列优先原则将主对角线和非常量区存储在一维数组中,并在此一维数组最后一个位置存储一个常量 他的存储与对称矩阵相类同,只存储上/下三角中的元,再加一个存储常数 c 的存储空间即可 时, (矩阵为下三角矩阵时) 时, (矩阵为上三角矩阵时)
(3)三对角矩阵
三对角矩阵是指对角线元素及其上下两条元素组成的带状矩阵,其所有非零元素都集中在主对角线为中心的3 条对角线的区域内,其他部分均为零元素
压缩策略:按照行优先或列优先原则,只存储带状部分到一个一维数组即可
2、稀疏矩阵
稀疏因子 :在 矩阵中,有 t 个非零元素,则 为矩阵的稀疏因子 当稀疏因子小于等于 0.05 时,我们称之为稀疏矩阵
(1)三元组顺序表
(2)行逻辑链接的顺序表
(3)十字链表法
二、广义表
暂且存疑,等之后回过头来再看