数据结构_数组.ppt

数据结构 数组4.1 数组的定义数组是我们最熟悉的数据类型，在早期的高级语言 中，数组是唯一可供使用的数据类型由于数组中 各元素具有统一的类型，并且数组元素的下标一般 具有固定的上界和下界，因此，数组的处理比其它 复杂的结构更为简单4.1 数组的定义多维数组是向量的推广例如，二维数组：a00 a01 … … … a0n-1a10 a11 … … … a1n-1… … … … … … … …am-10 am-11 … am-1n-1 Amn=可以看成是由m个行向量组成的向量，也可以看成是 n个列向量组成的向量4.1 数组的定义4.2 数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维 内存来表示多维数组，就必须按某种次序将数组元 素排成一列序列，然后将这个线性序列存放在存储 器中又由于对数组一般不做插入和删除操作，也就 是说，数组一旦建立，结构中的元素个数和元素间 的关系就不再发生变化因此，一般都是采用顺序 存储的方法来表示数组4.2 数组的顺序表示和实现⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接 在第i个行向量后面以二维数组为例，按行优先顺序存储的 线性序列为：⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量 紧接在第j个列向量之后，按列优先顺序存储的线性序列为：a0,1a0,0a0,2 a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2da1,0a0,0a2,0a2,1a0,1 a1,1a1,0a0,0a2,0a0,1a1,1a2,1d例如，二维数组Amn按“行优先顺序”存储在内存中，假设 每个元素占用d个存储单元。

元素aij的存储地址应是数组的基地址加上排在aij前面的元 素所占用的单元数因为aij位于第i行、第j列，前面i-1行一 共有i×n个元素，第i行上aij前面又有j个元素，故它前面一共 有(i×n+j）个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a00)+[i*n+j]*d (0≤i1时，元素aij=0由此可知，一个k对角矩阵(k为奇数)A是满足下 述条件的矩阵：若∣i-j∣>(k-1)/2 ，则元素 aij=0对角矩阵可按行优先顺序或对角线的顺序，将其压 缩存储到一个向量中，并且也能找到每个非零元素 和向量下标的对应关系5.3 数组的压缩存储对这种矩阵，我们也可按行优序为主序来存储除第0行和第n -1行是2个元素外，每行的非零元素都要是3个，因此，需存储 的元素个数为3n-2a00a01 a10a11a12a21 …… a n-1 n-2a n-1 n-1K=0 1 2 3 4 5 … … 3n-2 3n-1 数组sa中的元素sa[k]与三对角带状矩阵中的元素aij存在一一对 应关系，在aij之前有i行,共有3×i-1个非零元素，在第i行，有j -i+1个非零元素，这样，非零元素aij的地址为： 5.3 数组的压缩存储LOC(i,j) = LOC(0,0)+[3i-1+(j-i+1)]d= LOC(0,0)+(2i+j)d上例中，a34对应着 a21对应着sa[10]k=2×i+j=2×3+4=10 sa[5]k=2×2+1=5由此，我们称sa[03×n-1]是n阶三对角阵的压缩存储 表示。

5.3 数组的压缩存储5.3 数组的压缩存储5.3.2 稀疏矩阵5.3 数组的压缩存储5.3.2 稀疏矩阵三元组顺序表行逻辑链接顺序表十字链表5.3 数组的压缩存储1、三元组顺序表5.3 数组的压缩存储1、三元组顺序表5.3 数组的压缩存储1、三元组顺序表(1, 2, 12) (1, 3, 9 ) (3, 1, -3) (3, 6, 14) (4, 3, 24) (5, 2, 18) (6, 1, 15) (6, 4, -7)(1, 3, -3) (1, 6, 15) (2, 1, 12) (2, 5, 18) (3, 1, 9) (3, 4, 24) (4, 6, -7) (5, 3, 14)已知 三 元 组 表 A求 三 元 组 表 B5.3 数组的压缩存储1、三元组顺序表5.3 数组的压缩存储2、十字链表。