15.15.2数组顺序表示.ppt
一、教学内容：1、数组的定义和顺序存储方式；2、特殊矩阵的压缩存储；3、稀疏矩阵4、广义表的概念、表示及基本操作；广义表存储结构的实现。二、教学要求：1、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；2、掌握对特殊矩阵进行压缩存储时的下标变换公式；3、了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；4、掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。,第五章 数组和广义表,知识结构图,知识结构图,数组与广义表,数 组,广义表,压缩存储,类型定义,顺序表示,稀疏矩阵,特殊矩阵,存储结构,类型定义,基本操作,基本操作,应用,递归算法,压缩存储,各种运算,第五章 数组和广义表,简介：线性表的扩展表中数据元素也是一种数据结构。数组的定义、顺序表示稀疏矩阵的压缩存储广义表的定义、存储结构和递归算法重点：数组的顺序表示稀疏矩阵的压缩存储结构和其上矩阵运算的实现广义表的递归算法难点：n维数组元素存储地址的计算稀疏矩阵的压缩存储结构及其上的运算的实现广义表的递归算法,第五章 数组和广义表,5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构,5.1 数组的定义,本章之前讨论的线性结构的数据元素都是非结构的原子类型，元素值不可再分。本章讨论的两种数据结构数组和广义表。作为线性表的扩展，表中的数据元素本身也是一种数据结构。抽象数据类型数组的定义数组的顺序表示n维数组的存储方式n维数组的数据元素存储位置的计算公式,5.1 数组的定义,n维数组是线性表的推广 当n=1，n维数组退化成顺序表当n1，n维数组可看成表中数据元素仍是线性表的线性表,A=(0,1,p)p=m-1或n-1,5.1数组的定义,C语言中二维数组的类型定义:typedef ElemType Array2mn;等价于typedef ElemType Array1n;typedef Array1 Array2m;因此定义二维数组A可如右：Array2 A;二维的数组=定长的线性表,Amxn=(a11,a12,a13,.a1n),(a21,a22,a23,.a2n),.,(am1,am2,am3,.amn),二维数组的二种理解方式：视作多个一维数组 视作一个一维数组,数组是n(n1)个相同类型数据元素a1,a2,an构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。由此可见,数组的定义类似于采用顺序存储结构的线性表。,数组具有以下性质：(1)数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。(2)数组中的数据元素具有相同的数据类型。(3)数组中的每个数据元素都和一组惟一的下标值对应。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。,数组的抽象数据类型,ADT Array 数据对象：D=aj1j2.jn|ji=0,.,bi-1,i=1,2,.,n n(0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2.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(/取数组元素值Assign(&A,e,index1,index2,.,indexn)/给数组元素赋值ADT Array,数组一旦定义后，其维数和维界不再改变，因此除了结构的初始化和销毁之外，只有存取和修改元素值的操作。,n维数组的特点,n维数组中含有bi个数据元素;每个数据元素都受着n个关系的约束；在每个关系中，元素aj1j2jn(0=ji=bi-2)都有一个直接后继;数据元素都必须属于同一数据类型;n=1时，退化为定长的线性表；n维数组可以看成是线性表的推广。数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。(一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动)数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）,补充：不讲！,类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是 一个一维的结构。,二维及以上数组有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。,5.2 数组的顺序表示和实现,在一维数组中,一旦a1的存储地址LOC(a1)确定,并假设每个数据元素占用k个存储单元,则任一数据元素ai的存储地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a1)+(i-1)*k(0in)上式说明,一维数组中任一数据元素的存储地址可直接计算得到,即一维数组中任一数据元素可直接存取,因此,一维数组是一种随机存储结构。同样,二维及多维数组也满足随机存储特性。,C,PASCAL,等,FORTRAN,二维数组的两种存储方式,5.2 数组的顺序表示,计算数组任一元素()的地址需要的三要素：数组的起始地址（即基地址）数组维数和各维的长度；数组中每个元素所占的存储单元已知二维数组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,设一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是0。,二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L,单个元素长度,aij之前的行数,数组基址,总列数，即第2维长度,aij本行前面的元素个数,则行优先存储时的地址公式为：LOC(aij)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+j-c2)*L,计算二维数组元素地址的通式,补充：不讲！,数组元素的存储位置是其下标的线性函数，由于计算各个元素存储位置的时间相等，所以存储数组中任一元素的时间也相等，我们称具有这一特点的存储结构为随机存储结构。,5.2 数组的顺序表示和实现,n维数组元素存储地址的计算公式-教材93页 设各维长度分别为b1,b2,b3,bn,每个元素占L个存储单元，起始地址是LOC(0,0,0)，求元素 的存储位置？,(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)*L,5.2 数组的顺序表示-小结,n维数组的特点:数据元素同属于一种数据类型；数组一旦被定义，则维数和各维长度不能改变；数组操作只有引用型操作，没有加工型操作；数组是多维结构，但存储空间是一维结构。数组顺序表示的特点存储单元地址连续（需要一段连续空间）存储规则（以行（列）为主序）决定元素实际存储位置随机存取存储密度最大（100%）,
