数组与广义表ppt课件.ppt

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

1、本章主要内容：1．数组的定义与表示2．矩阵的压缩存储3．广义表的定义与存储结构本章目的和要求：1．掌握数组的定义和表示2．掌握稀疏矩阵的存储本章重点：稀疏矩阵的存储：三元组和十字链表。第五章   数组和广义表第五章   数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表5.1数组的定义一、数组抽象数据类型的定义二、关于二维数组和n维数组的另一种定义三、数组的操作ADTarray{数据对象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn

2、n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维

3、下标，aj1j2…jn∈elemset}数据关系：R={R1,R2,…,Rn}Ri={

4、0≤jk≤bk-1,1≤k≤n且k≠i0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…,n}一、数组抽象数据类型的定义5.1数组的定义基本操作：initarray(&A,n,bound1,…,boundn)destroyarray(&A)Value(A,&e,index1,…indexn)Assign(&A,e,index1,…indexn)}一、数组抽象数据类型的定义5.1数组的定义由定义可知：(1

5、)n维数组中含bi个数据元素，每个数据元素受n个关系的约束。(2)每个关系中元素都有一个直接后继元素。(3)数据元素必须属于同一数据类型。(5)当n=1时，n维数组就退化为定长的线性表。反之，n维数组可以看成是线性表的推广。一、数组抽象数据类型的定义5.1数组的定义二、关于二维数组和n维数组的另一种定义1.二维数组(矩阵)：若把它的每个数据元素看成是一个定长的线性表，则它也是一个定长的线性表。Amn=a11a12a13a1na21a22a23a2n……………..am1am2am3amnA看成一个线性表A=(a1,a2,…,ap)（p=m或n）其中每个数据元素a

6、j是一个列向量形式的线性表:aj=(a1j,a2j,…,amj)或者ai是一个行向量形式的线性表:ai=(ai1,ai2,…,ain)5.1数组的定义二、关于二维数组和n维数组的另一种定义因此：一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型。同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。如：inta[m][n]相当于有一个a[m]数组，其元素为a[0]…a[i]…a[m-1]，其中每一元素a[i]又是一维数组a[i][0],a[i][1]……a[i][n-1]。5.1数组的定义数组一旦被定义，它的维数和维界就不再改

7、变。因此所能进行的操作只有：初始化销毁数据元素的存取和修改三、数组的操作5.1数组的定义5.2数组的顺序表示和实现一、数组元素的地址对于数组的存储都是采用顺序存储结构。用一组连续的存储单元存储。由于存储单元是一维结构，而数组是个多维结构，确定数组元素的地址，则应有一个次序约定问题。这里以二维数组为例说明。对于二维数组有两种存储方式：(1)以行序为主的存储方式(常用)(2)以列序为主的存储方式a00a01a02a03a10a11a12a13a20a21a22a23a00a01a02a03a10a11a12a13a20a21a22a23第7个位置第8个位置5.2数组

8、的顺序表示和实现以行序为主序的存储结构的元素位置确定设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置：LOC[i，j]=LOC[0，0]+(b2i+j)L其中：LOC[0，0]是a00的存储位置，二维数组的起始地址，称为基址。n维数组的数据元素存储位置：LOC(j1,j2,…jn)=LOC(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)L5.2数组的顺序表示和实现例：设有一二维数组A57每个元素占2字节，已知A的起始存储位置是1000。(1)若按行存储，a24的地址：LOC（2，4）=1000

9、+（72+4）2(2)若按列存储，a24的地址：LOC（2，4）=1000+（54+2）2a00a01a02a03a04a05a06a10a11a12a13a14a15a16a20a21a22a23a24a25a26a30a31a32a33a34a35a36a40a41a42a43a44a45a46a00a01a02a03a04a05a06a10a11a12a13a14a15a16a20a21a22a23a00a01a02a03a04a10a11a12a13a14a20a21a22a23a30a31a32a33a40a41a42a43例：按行存储的a24

10、的地址与按列存储的哪一个