《数组顺序表示》PPT课件

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

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

2、表数组广义表压缩存储类型定义顺序表示稀疏矩阵特殊矩阵存储结构类型定义基本操作基本操作应用递归算法压缩存储各种运算3第五章数组和广义表简介：线性表的扩展－表中数据元素也是一种数据结构。数组的定义、顺序表示稀疏矩阵的压缩存储广义表的定义、存储结构和递归算法重点：数组的顺序表示稀疏矩阵的压缩存储结构和其上矩阵运算的实现广义表的递归算法难点：n维数组元素存储地址的计算稀疏矩阵的压缩存储结构及其上的运算的实现广义表的递归算法4第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5

3、.4广义表的定义5.5广义表的存储结构55.1数组的定义本章之前讨论的线性结构的数据元素都是非结构的原子类型，元素值不可再分。本章讨论的两种数据结构——数组和广义表。作为线性表的扩展，表中的数据元素本身也是一种数据结构。抽象数据类型数组的定义数组的顺序表示n维数组的存储方式n维数组的数据元素存储位置的计算公式65.1数组的定义n维数组是线性表的推广当n=1，n维数组退化成顺序表当n>1，n维数组可看成表中数据元素仍是线性表的线性表a00a01…a0,n-1a10a11…a1,n-1…………am-1

4、,0am-1,1…am-1,n-1Am*n=二维数组a00a01…a0,n-1a10a11…a1,n-1…………am-1,0am-1,1…am-1,n-1Am*n=列向量的一维数组Am*n=((a00a01…a0,n-1),(a10a11…a1,n-1),…,(am-1,0am-1,1…am-1,n-1))行向量的一维数组A=(α0,α1,…αp)p=m-1或n-175.1数组的定义C语言中二维数组的类型定义:typedefElemTypeArray2[m][n];等价于typedefElemTy

5、peArray1[n];typedefArray1Array2[m];因此定义二维数组A可如右：Array2A;二维的数组=定长的线性表Amxn=((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(am1,am2,am3,...amn))a11a12a13...a1na21a22a23...a2nAmxn=......am1am2am3...amn二维数组的二种理解方式：视作多个一维数组视作一个一维数组数组是n(n＞1)个相同类型数据元素a1,a2,…,

6、an构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。由此可见,数组的定义类似于采用顺序存储结构的线性表。8数组具有以下性质：(1)数组中的数据元素数目固定。一旦定义了一个数组,其数据元素数目不再有增减变化。(2)数组中的数据元素具有相同的数据类型。(3)数组中的每个数据元素都和一组惟一的下标值对应。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。9数组的抽象数据类型ADTArray{数据对象：D={aj1j2...jn

7、ji=0,...,bi-1,i=1,2,..,nn

8、(>0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2...jnElemset}数据关系：R={R1,R2...Rn}Ri={＜aj1...ji...jn,aj1...ji+1...jn＞

9、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(

10、&A);//销毁数组AValue(A,&e,index1,index2,...,indexn);//取数组元素值Assign(&A,e,index1,index2,...,indexn)//给数组元素赋值}ADTArray数组一旦定义后，其维数和维界不再改变，因此除了结构的初始化和销毁之外，只有存取和修改元素值的操作。10n维数组的特点n维数组中含有bi个数据元素;每个数据元素都受着n个关系的约束；在每个关系中，元素aj1j2…jn(0<=ji<=bi-2)都有一个直接后继;数据