最新数据结构课件数组和广义表教学讲义PPT.ppt

《最新数据结构课件数组和广义表教学讲义PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课件数组和广义表数组是由下标和值组成的序对集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。也可以说，数组中的每个数据元素都对应于一组下标（j1,j2,…,jn），每个下标取值范围是1≤ji≤bi，bi称为第i维的长度（i=1,2,…,n）。显然，当n=1时，n维数组就退化为定长的线性表。反之，n维数组也可以看成是线性表的推广。25.1.1数组的定义可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。Am×n=a11a21…am1a12a22…am2a13a23…am3…………a1.na2,n…am,n3例如

2、，下面是一个二维数组，且以m行n列的矩阵形式表示。75.1.2数组的抽象类型定义DestroyArray(A):销毁数组A。GetValue(A,e,index1,…,indexn):初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标合法，则用e返回数组Ａ中由由index1,…indexn所指定的元素的值.SetValue(A,e,index1,…,indexn);初始条件：A是n维数组，e为元素变量，随后是n个下标值。操作结果：若各下标合法，则将数组A中由index1,…indexn所指定的元素的值置为e.由于内存储器的结构是一维的。一

3、维数组可直接采用顺序存储。用一维的内存存储表示多维数组时，需按某种次序将数组中元素排成一线性序列，再将这个线性序列存放在一维的内存中，即数组的顺序存储结构表示。顺序存储的定位公式5.2数组的顺序存储结构8数组的顺序存储表示基本操作的算法描述用顺序存储结构来存储数组中的元素，一定要按照某种次序将元素排成一个线性序列。有两种存储方式：(1)以列为主序(columnmajororder)的存储方式，即按列优先，逐列顺序存储。(2)以行为主序(rowmajororder)的存储方式，即按行优先，逐行顺序存储。95.2.1顺序存储的定位公式a21a11…am,1a22a12…a

4、m,2a1,n…a2,n…am,na21a11…am,1a21a11…Am,1a21a11…am,1a22a12…am,2a22a12…am,2a22a12…am,2………a1,na2,n…am,na1,na2,n…am,na1,na2,n…amn10列主次序存放a12a11…a1.na22a21…a2,nam,1…am,2…am,na12a11…a1.na22a21…a2,n………am,1am,2…am,na12a11…a1,na12a11…a1,na22a21…a2,na22a21…a2,nam,1am,2…am,nam,1am,2…am,n11行主次序存放对于数

5、组，一旦规定了它的维数和各维的长度，便可以为它分配存储空间。反之，只要给出一组下标，便可以求得相应数组的存储位置。12（１）一维数组的地址计算：设一维数组为：Ａ=(a1,a2,…,ai,…,an),数组中每个元素占size个存储单元，则元素ai的存储地址为：Loc(A[i])=Loc(A[1])+(i-1)*size。数组的地址计算13⑵二维数组的地址计算假设每个数据元素占1个存储单元，且以行序为主序的进行存储，则二维数组A中任一元素aij的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+n*(i-1)+(j-1)其中：LOC(A

6、[i[,[j])是aij的存储位置；LOC(A[1],[1])是a11的存储位置，即二维数组A的起始存储位置，也称为基地址或基址；n是数组第二维的长度。14假设每个数据元素占size个存储单元，则二维数组A中任一元素aij的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+(n*(i-1)+(j-1))*size⑶三维数组的地址计算三维数组A(1:r,1:m,1:n)。假设每个数据元素占size个存储单元，且以行序为主序的进行存储，首元素a111的地址为Loc(A[1][1][1]),求任意元素aijk的地址。显然，ai11地址为Ｌ

7、oc(A[i][1][1])=Loc(A[1][1][1])+(i-1)*m*n,因为在该元素之前有i-1个m*n的二维数组。15不难得到三维数组任意元素aijk的地址：Loc(A[i][j][k])=Loc(A[1][1][1])+((i-1)*m*n+(j-1)*n+(k-1))*size,其中：１≤i≤r,１≤j≤m,１≤k≤n。矩阵(matrix)是很多科学与工程计算问题中研究的数学对象。在数据结构中，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元素而使矩阵的各种运算能够有效地进行。特殊矩阵包括两个部份：①元素分布有特殊规律的矩阵,找到规律对