《数组顺序表示》PPT课件.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,设一般的二维数组是Ac1d1, c2d2，这里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%）,