第五章数组(Array).ppt

《第五章数组(Array).ppt》由会员分享，可在线阅读，更多相关《第五章数组(Array).ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 数组数组（Array）数组的定义及其基本操作数组的定义及其基本操作数组的存储结构数组的存储结构矩阵的压缩存储矩阵的压缩存储数据结构（数据结构（Data Structure）定义及其操作定义：是是n(n1)个个相同类型相同类型数据元素数据元素a0,a1,an-1构成的构成的有限有限序列，且该有限序列存储在一块序列，且该有限序列存储在一块地址连续地址连续的内存单元的内存单元中。中。在一维数组中，任一数据元素在一维数组中，任一数据元素ai的存储地址的存储地址Loc(ai)可以通可以通过过a0的地址的地址Loc(a0)以及每个数据元素存储单元以及每个数据元素存储单元k由下式确由下式确定：

2、定：数组满足随机存储特性数组满足随机存储特性可以证明可以证明：数组具有以下性质：（1 1）数组中的数据元素数目）数组中的数据元素数目固定固定。（2 2）数组中的数据元素具有）数组中的数据元素具有相同相同的数据类型。的数据类型。（3 3）数组中的每个数据元素都和一组）数组中的每个数据元素都和一组唯一唯一的下标值的下标值对应。对应。（4 4）数组是一种）数组是一种随机存储随机存储结构。结构。.数组的基本操作:一般地，不对数组进行插入和删除操作1.随机存。随机存。2.2.随机取随机取。（基本操作）3.数组列表。4.矩阵运算。（部分高级语言支持）存储结构一维数组：存储结构关系式为：二维及多维数组：通常

3、有两种排序方式：通常有两种排序方式：1、行优先序列：将多维数组元素按行排列、行优先序列：将多维数组元素按行排列在PASCAL、C语言中，数组就是按行优先顺序存储的。2、列优先序列：将多维数组元素按列排列、列优先序列：将多维数组元素按列排列在FORTRAN语言中，数组就是按列优先顺序存储的。数组的静态存储分配和动态存储分配（p102）例，二维数组二维数组Amn按按“行优先顺序行优先顺序”存储在内存中，假设每个元素占用存储在内存中，假设每个元素占用d个存储单元。则元素个存储单元。则元素aij的存储地址为：的存储地址为：LOC(aij)=LOC(a00)+i*n+j*d如果按如果按“列优先顺序列优先

4、顺序”，则为：，则为：LOC(aij)=LOC(a00)+j*m+i*d同样，三维数组同样，三维数组Amnp按按“行优先顺序行优先顺序”存储，则存储，则Aijk地址计算函数为：地址计算函数为：LOC(aijk)=LOC(a000)+i*n*p+j*p+k*d矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进

5、行随机存取，各种矩阵运算也非常简单，并且存储的密度为进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为量的零元素的情况下，看起来存储密度仍为1 1，但实际上占用，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，造成极大的浪费，为了节省存储空间，我们可以对这类矩阵我们可以对这类矩阵进行进行压缩存储压缩存储：即为多个相同的非零元素只分配一个存储

6、空间；：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。对零元素不分配空间。1、对称矩阵 在一个在一个n阶方阵阶方阵A中，若元素满足下述性质：中，若元素满足下述性质：aij=aji 0i,jn-1 则称则称A为对称矩阵。为对称矩阵。压缩原理压缩原理：对称矩阵中的元素关于主对角线对称，：对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。节约近一半的存储空间。5.3 矩阵的压缩存储不失一般性，我们按不失一般性，我

7、们按“行优先顺序行优先顺序”存储主对角线（包括对存储主对角线（包括对角线）以下的元素，其存储形式如图所示：角线）以下的元素，其存储形式如图所示：1 5 1 3 7 a1 5 1 3 7 a0000 5 0 8 0 0 a 5 0 8 0 0 a10 10 a a 11 11 1 8 9 2 6 a 1 8 9 2 6 a2020 a a2121 a a2323 3 0 2 5 1 .3 0 2 5 1 .7 0 6 1 3 a 7 0 6 1 3 an-1 0n-1 0 a a n-1 1 n-1 1 a a n-1 2n-1 2 a a n-1 n-1n-1 n-1 对称矩阵对称矩阵 a00

8、a10a11a20an-1 0 an-1,n-1sa：1、当 ij，则aij在下三角形中，其在顺序存储表中元素sak的关系按下式计算：k=i*(i+1)/2+j 0kn(n+1)/22、当 ij，则aij在上三角形中，其在顺序存储表中sak的关系按下式计算：k=j*(j+1)/2+i 0kn(n+1)/2令 I=max(i,j)，J=min(i,j)，则k和 i,j的对应关系可统一为：k=I*(I+1)/2+J 0 kmd=sa.nd;sb-nd=sa.md;sb-td=sa.td;if(sb-td!=0)q=0;/q为sb.data的下标for(v=0;v sa.nd;v+)for(p=0;

9、pdataq,i=sa.datap.j;sb-dataq.j=sa.datap.i;sb-dataq.d=sa.datap.d;三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t n?m:n;/s为m，n中的较大值 Head=(clinktype*)malloc();Head-m=m;/行数Head-n=n;/列数 for(k=0;kpck=(cross2type*)malloc();Head-pck-i=0;Head-pck-j=0;Head-pck-Down=NULL;Head-pck-Right=NULL;sca

10、nf(“%d”,&t);/t为非零元素的个数for(k=0;k i=i;p-j=j;p-Value=Value;q=Head-pci;/找到对应行的行列头节点while(q-Right!=NULL&q-Right-j Right;/由q-Right指针构成对应行的行链p-Right=q-Right;q-Right=p;/完成行插入q=Head-pcj;/找到对应列的行列头结点/由 q-Down指针构成对应列的列表链while(q-Down!=NULL&q-Down-i Down;/寻找在该列中行数i应插入的位置p-Down=q-Down;q-Down=p;/完成列插入/结束for循环return(Head);指针p始终指向新输入的三元组结点指针q始终指示十字链表中相应的行列结点