《数组顺序表示》PPT课件.ppt

《《数组顺序表示》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数组顺序表示》PPT课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、教学内容：1、数组的定义和顺序存储方式；数组的定义和顺序存储方式；2、特殊矩阵的压缩存储；特殊矩阵的压缩存储；3、稀疏矩阵稀疏矩阵4、广义表的概念、表示及基本操作；广义表存储结构的实现。广义表的概念、表示及基本操作；广义表存储结构的实现。二、教学要求：1、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；地址计算方法；2、掌握对特殊矩阵进行压缩存储时的下标变换公式；掌握对特殊矩阵进行压缩存储时的下标变换公式；3、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表了解稀疏矩阵的两种压缩存储方法

2、的特点和适用范围，理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；示稀疏矩阵时进行矩阵运算采用的处理方法；4、掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。第五章第五章 数组和广义表数组和广义表1知识结构图2知识结构图数组与广义表数组与广义表 数数 组组广义表广义表压压缩缩存存储储类类型型定定义义顺顺序序表表示示稀稀疏疏矩矩阵阵特特殊殊矩矩阵阵存存储储结结构构类类型型定定义义基基本本操操作作基基本本操操作作 应应用用递递归归算算法法压压缩缩存存储储各各种种运运算算3第五章 数组和广义表n简介：简介：线性表的扩展

3、表中数据元素也是一种数据结线性表的扩展表中数据元素也是一种数据结构。构。n数组的定义、顺序表示数组的定义、顺序表示n稀疏矩阵的压缩存储稀疏矩阵的压缩存储n广义表的定义、存储结构和递归算法广义表的定义、存储结构和递归算法n重点：重点：n数组的顺序表示数组的顺序表示n稀疏矩阵的压缩存储结构和其上矩阵运算的实现稀疏矩阵的压缩存储结构和其上矩阵运算的实现n广义表的递归算法广义表的递归算法n难点难点：nn维数组元素存储地址的计算维数组元素存储地址的计算n稀疏矩阵的压缩存储结构及其上的运算的实现稀疏矩阵的压缩存储结构及其上的运算的实现n广义表的递归算法广义表的递归算法4第五章第五章 数组和广义表数组和广义

4、表n5.1数组的定义n5.2数组的顺序表示和实现n5.3矩阵的压缩存储n5.4广义表的定义n5.5广义表的存储结构55.1 数组的定义n本章之前讨论的线性结构的数据元素都是非结构的原子类型，元素值不可再分。本章讨论的两种数据结构数组数组和广义表广义表。作为线性表的扩展，表中的数据元素本身也是一种数据结构。n抽象数据类型数组的定义抽象数据类型数组的定义n数组的顺序表示数组的顺序表示nn维数组的存储方式维数组的存储方式nn维数组的数据元素存储位置的计算公式维数组的数据元素存储位置的计算公式65.1 数组的定义nn维数组是线性表的推广维数组是线性表的推广 n当当n=1，n维数组退化成顺序表维数组退化

5、成顺序表n当当n1，n维维数数组组可可看看成成表表中中数数据据元元素素仍仍是是线线性性表表的的线线性表性表 a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1Am*n=二维数组二维数组 a00 a01 a0,n-1 a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1Am*n=列向量的一维数组列向量的一维数组Am*n=(a00a01a0,n-1),(a10a11a1,n-1),(am-1,0am-1,1am-1,n-1)行向量的一维数组行向量的一维数组A=(0,1,p)p=m-1或或n-1 75.15.1数组的定义数组

6、的定义 C语言中二维数组的类型定义:typedef ElemType Array2mn;等价于typedef ElemType Array1n;typedef ElemType Array1n;typedef Array1 Array2m;typedef Array1 Array2m;因此定义二维数组因此定义二维数组A A可如右：可如右：Array2 A;Array2 A;二维的数组=定长的线性表 Amxn=(a11,a12,a13,.a1n),(a21,a22,a23,.a2n),.,(am1,am2,am3,.amn)a a11 a a12 a a13.a.a1n a a21 a a22

7、a a23.a.a2n A Amxnmxn=.=.a am1 a am2 a am3.a.amnn二维数组的二种理解方式：二维数组的二种理解方式：n视作多个一维数组视作多个一维数组 n视作一个一维数组视作一个一维数组 数组数组是是n(n1)个相同类型数个相同类型数据元素据元素a1,a2,an构成的有限序构成的有限序列列,且该有限序列存储在一块地址连且该有限序列存储在一块地址连续的内存单元中。续的内存单元中。由此可见由此可见,数组的定义类似于采数组的定义类似于采用顺序存储结构的线性表。用顺序存储结构的线性表。8数组具有以下性质：数组具有以下性质：(1)数数组组中中的的数数据据元元素素数数目目固固

8、定定。一一旦旦定定义义了了一一个数组个数组,其数据元素数目不再有增减变化。其数据元素数目不再有增减变化。(2)数组中的数据元素具有数组中的数据元素具有相同相同的数据类型。的数据类型。(3)数数组组中中的的每每个个数数据据元元素素都都和和一一组组惟惟一一的的下下标标值对应。值对应。(4)数数组组是是一一种种随随机机存存储储结结构构。可可随随机机存存取取数数组组中的任意数据元素。中的任意数据元素。9数组的抽象数据类型ADT Array 数据对象：D=aj1j2.jn|ji=0,.,bi-1,i=1,2,.,n n(0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2.

9、jnElemset数据关系：R=R1,R2.Rn Ri=aj1.ji.jn,aj1.ji+1.jn|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n,aj1.ji.jn,aj1.ji+1.jn D。基本操作：InitArray(&A,n,bound1,bound2,.,boundn);/构造数组ADestroyArray(&A);/销毁数组AValue(A,&e,index1,index2,.,indexn);/取数组元素值Assign(&A,e,index1,index2,.,indexn)/给数组元素赋值ADT Array数组一旦定义后，其维数和维界不再改变，因

10、此除了结构的初始化和销毁之外，只有存取和修改元素值的操作。10n维数组的特点nn维数组中含有bi个数据元素;n每个数据元素都受着n个关系的约束；n在每个关系中，元素aj1j2jn(0=ji=bi-2)都有一个直接后继;n数据元素都必须属于同一数据类型;nn=1时，退化为定长的线性表；nn维数组可以看成是线性表的推广。n数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动)n数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）i=1n补充：不讲！11类型特点类型特点:1)只有只有引用型引用型操作，没

11、有操作，没有加工型加工型操作；操作；2)数组是多维的结构，而存储空间是数组是多维的结构，而存储空间是 一个一维的结构。一个一维的结构。二维及以上数组二维及以上数组有两种顺序映象的方式有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现在一维数组中在一维数组中,一旦一旦a1的存储地址的存储地址LOC(a1)确定确定,并假设每个数据并假设每个数据元素占用元素占用k个存储单元个存储单元,则任一数据元素则任一数据元素ai的存储地址的存储地址LOC(ai)就可就可由以下公式求出：由以下公式求出：LOC(ai)=LO

12、C(a1)+(i-1)*k(0in)上式说明上式说明,一维数组中任一数据元素的存储地址可直接计算得一维数组中任一数据元素的存储地址可直接计算得到到,即一维数组中任一数据元素可直接存取即一维数组中任一数据元素可直接存取,因此因此,一维数组是一种一维数组是一种随机存储结构。同样随机存储结构。同样,二维及多维数组也满足随机存储特性。二维及多维数组也满足随机存储特性。C,PASCAL,等FORTRAN12二维数组的两种存储方式二维数组的两种存储方式135.2 数组的顺序表示n计算数组任一元素计算数组任一元素()的地址需要的三要素：的地址需要的三要素：数组的起始地址（即基地址）数组的起始地址（即基地址）

13、数组维数和各维的长度；数组维数和各维的长度；数组中每个元素所占的存储单元数组中每个元素所占的存储单元n已知二维数组已知二维数组Ab1*b2，每个元素占，每个元素占L个存储单元，个存储单元，LOC(0,0)是数组第一个元素的起始地址，以行序为主存储，是数组第一个元素的起始地址，以行序为主存储，求求LOC(i,j)。行主序行主序：LOC(i,j)=LOC(0,0)+(b2*i+j)*L列主序：列主序：LOC(i,j)=LOC(0,0)+(b1*j+i)*L a00 a01 a0,n-1 a10 a11 a1,n-1 aij am-1,0 am-1,1 am-1,n-1Am*n=14设一般的二维数组

14、是Ac1.d1,c2.d2，这里c1,c2不一定是0。二维数组二维数组列优先列优先存储的通式为：存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=单个元素单个元素长度长度aijaij之前的之前的行数行数数组基址数组基址总列数，即总列数，即第第2 2维长度维长度aijaij本行前面本行前面的元素个数的元素个数则则行优先行优先存储时的地址公式为：存储时的地址公式为：LOC(aij)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+j-c2)*L计算二维数组元素地

15、址的通式补充：不讲！15l数数组组元元素素的的存存储储位位置置是是其其下下标标的的线线性性函函数数，由由于于计计算算各各个个元元素素存存储储位位置置的的时时间间相相等等，所所以以存存储储数数组组中中任任一一元元素素的的时时间间也也相相等，我们称具有这一特点的存储结构为等，我们称具有这一特点的存储结构为随机存储结构。随机存储结构。5.2 数组的顺序表示和实现n n维数组元素存储地址的计算公式维数组元素存储地址的计算公式-教材教材93页页 设各维长度分别为设各维长度分别为b1,b2,b3,bn,每个元素占每个元素占L个存储个存储单元，单元，起始地址是起始地址是LOC(0,0,0)，求元素，求元素

16、的存储的存储位置？位置？(Cn=L,ci-1=bi*ci,1in)LOC(j1,j2,jn)=LOC(0,0,0)+(b2*b3*bn*j1+b3*b4*bn*j2+bn*jn-1+jn)*L165.2 数组的顺序表示-小结nn维数组的特点维数组的特点:n数据元素同属于一种数据类型；数据元素同属于一种数据类型；n数组一旦被定义，则维数和各维长度不能改变；数组一旦被定义，则维数和各维长度不能改变；n数组操作只有引用型操作，没有加工型操作；数组操作只有引用型操作，没有加工型操作；n数组是多维结构，但存储空间是一维结构。数组是多维结构，但存储空间是一维结构。n数组顺序表示的特点数组顺序表示的特点n存储单元地址连续（需要一段连续空间）存储单元地址连续（需要一段连续空间）n存储规则（以行（列）为主序）决定元素实际存储存储规则（以行（列）为主序）决定元素实际存储位置位置n随机存取随机存取n存储密度最大（存储密度最大（100%100%）17