数据结构-数组和广义表

CH5数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构教学内容本章先介绍数组的定义及基本运算，然后介绍数组的存储结构及特殊矩阵的压缩存储，之后讨论稀疏矩阵的三种存储方法，最后介绍广义表的概念、基本运算和存储结构。教学目标（1）了解数组的逻辑结构和存储表示；掌握数组在以行/列为主的存储结构中的地址计算方法；（2）掌握特殊矩阵的压缩存储方式及下标变换公式；（3）了解稀疏矩阵压缩存储方法的特点和适用范围，理解以三元组表示的稀疏矩阵进行矩阵运算采用的处理方法；（4）掌握广义表的结构特点极其存储表示方法，以及对非空广义表进行分解的两种分析方法。5.1数组的定义一、数组的基本概念数组的定义即数组是由n个具有相同数据类型的数据元素a1，a2，…，an组成的有限序列，且该有限序列必须存储在一块地址连续的存储单元中。数组的下标：数组元素的位置。一维数组二维数组多维数组注意：(1)C语言的数组定义下标从0开始。(2)数组的处理相比其它复杂的结构要简单。①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单。问题：数组与线性表的区别与联系？相同之处：它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1构成的有限序列。不同之处：(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同。5.1数组的定义二维数组在此:1.可以将二维数组A看成是由m个行向量[X0,X1,…,Xm-1]T组成，其中，Xi＝(ai0,ai1,….,ain-1)，0≤i≤m－1；2.可以将二维数组A看成是由n个列向量[y0,y1,……,yn-1]组成，其中，Yj＝(a0j,a1j,…..,am-1j)，0≤j≤n－1。由此可知:二维数组中的每一个元素最多可有二个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。00010-110111-1-1,0-1,1-1,-1nnmmmnaaaaaaAaaa5.1数组的定义二维数组的抽象数据类型定义ADTArray2{数据对象:D＝{aij|aij∈ElemSet,0≤i≤m－1,0≤j≤n－1}数据关系:S＝{R1,R2}R1＝{ai,j,ai,j+1|0≤i≤m－1,0≤j＜n－1}R2＝{ai,j,ai+1,j|0≤i＜m－1,0≤j≤n－1}基本操作:InitArray(&A,2,m,n)DestroyArray(&A)value(A,&e,i,j)Assign(&A,e,i,j)}ADTArray25.1数组的定义三维数组三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。5.1数组的定义n维数组的抽象数据类型定义ADTArrayn{数据对象:D={aj1j2…jn|aj1j2…jn∈ElemSet,其中ji=0,1,…,bi-1,i=1,…,n}数据关系:S={R1,R2,……,Rn}Ri={aj1…ji…jn,aj1…ji+1…jn|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1…jn∈D}基本操作:InitArray(&A,n,bound1,…，boundn)DestroyArray(&A)value(A,&e,index1,…,indexn)Assign(&A,e,index1,…,indexn)}ADTArrayn5.2数组的顺序表示和实现存储结构的选择:由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。5.2数组的顺序表示和实现1.一维数组……an-1ai+1ai……a1a0LOC(a0)LOC(ai)LOC(ai+1)L地址计算公式:LOC(ai)＝LOC(a0)＋i×LLOC(ai+1)＝LOC(ai)＋L5.2数组的顺序表示和实现2.二维数组及多维数组（1）行优先顺序存储地址计算公式:Loc(aij)＝Loc(a00)＋(i×n＋j)Lam-1,,n-1……am-1,0……ain-1……ai0……a0n-1……a00第0行第i行第m-1行LOC(a00)例1：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是()个字节。例2:设数组a[1…60,1…70]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,31]的存储地址为()。28864005.2数组的顺序表示和实现可以推广到多维数组的行优先顺序存储行优先顺序存储也称为低下标优先或左边下标优先于右边下标。多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。5.2数组的顺序表示和实现（2）列优先顺序存储am-1,n-1……a0,n-1……am-1,j……a0,j……am-1,0……a0,0第0列第j列第n-1列LOC(a00)地址计算公式:Loc(aij)＝Loc(a00)＋(j×m＋i)L5.2数组的顺序表示和实现可以推广到多维数组的列优先顺序存储列优先顺序存储也称为高下标优先或右边下标优先于左边下标。多维数组按列优先存放到内存的规律：最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。因此，在算法中，最右边下标可以看成是外循环，最左边下标可以看成是最内循环。5.2数组的顺序表示和实现优点只要知道以下三要素①开始结点的存放地址（即基地址）；②维数和每维的上、下界；③每个数组元素所占用的单元数就可以将数组元素的存放地址表示为其下标的线性函数。因此:数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。缺点为了在计算机内存中给数组开辟足够的内存空间，必须预先确定每个数组下标的上、下界，有时这是比较困难的。5.3矩阵的压缩存储问题提出：在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。两类矩阵的压缩存储特殊矩阵稀疏矩阵5.3.1特殊矩阵特殊矩阵元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵下（上）三角矩阵对角线矩阵等等。压缩存储方案：对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量；二是压缩后仍然可以比较容易地进行各项基本操作5.3.1特殊矩阵一、对称矩阵定义若一个n阶方阵A中元素满足下列条件：aij＝aji（其中1≤i,j≤n）则称A为对称矩阵。压缩存储方案只存下三角只存上三角nnnnnnnnaaaaaaaaaaaaaaaa321333323122322211131211（1）只存放下三角部分（行优先）k=jii2)1(ijj2)1(i≥ji＜ja11a21a22………ai1ai2…aii…………an1an2an3anna11a21a22a31…ai1…aii…an1…an,n1234…i(i-1)/2+1i(i-1)/2+in(n-1)/2+1n(n+1)/2k＝问题：若按列优先存储下三角的元素，aij---sak？答：(1)(22)(1)2(1)(22)(1)2jnjijijkinijiij（2）只存放上三角部分a11a12a13…a1na22a23…a2n………aii…ain……anna11…a1na22…a2n…aii…ain…an,n1…nn+1…2n-1n(n+1)/2k=k=12)22)(1(ijinii≤ji＞j12)22)(1(jijnj问题：若按列优先存储下三角的元素，aij---sak？答：k=(1)2jji(1)2iiji≤ji＞jk=jii2)1(i≥j0i＜ja11a21a22c………ai1ai2…aii…………an1an2an3ann二、三角矩阵（1）下三角矩阵注：数组元素sa[0]中存放的是常数c或0Ca11a21a22…ai1…aii…an1…an,n0123…i(i-1)/2+1i(i-1)/2+in(n-1)/2+1n(n+1)/2k=压缩存储方案（2）上三角矩阵注：数组元素sa[0]中存放的是常数c或0a11a12a13…a1na22a23…a2n………Caii…ain……anni≤jk=12)22)(1(ijini0i＞jk=ca11…a1na22a23…aii…ain…an,n01…nn+1n(n+1)/2压缩存储方案三、对角矩阵定义若n阶矩阵A的所有非0元集中在以住对角线为中心的带状区域内，称A为n阶对角矩阵。三、对角矩阵压缩方案：方案1：按行主序依次将矩阵非0元存入一维数组sa[0..3n-2]中。k=2221)1(3jiijii=1j=1,2或i=nj=n-1,n或1＜i＜nj=i-1,i,i+10其它注：数组元素sa[0]中存放的是常数c或0nnnnnnaaaaaaaaaa,1,,13332232221121100k=ca11a12a21a22a23…aii-1aiiaii+1…an,n-1an,n0123453n-33n-2练习：设有三对角矩阵(aij)n×n，将其三条对角线上的元素aij逐行地存在于数组b[3n－2]中，使得aij=b[k]，求：（1）用i,j表示k的下标变换公式：（2）用k表示i,j的下标变换公式。注：题目来源：山东科技大学2004年招收硕士学位研究生入学考试数据结构试卷三、对角矩阵压缩方案方案2：按列主序存储非0元素方案3：按对角线存储非0元素5.3.2稀疏矩阵什么是稀疏矩阵？在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，但非零元的排列没有一定规律，我们称这一类矩阵为稀疏矩阵。一般地：稀疏因子δ＝t／(m×n)≤0.05的矩阵称为稀疏矩阵。5.3.2稀疏矩阵抽象数据类型稀疏矩阵的定义ADTSparseMatrix{数据对象：D＝{aij|aij∈ElemSet,1≤i≤m,1≤j≤n}数据关系：S＝{Row,Col}Row＝{ai,j,ai,j+1|1≤i≤m,1≤j＜n}Col＝{ai,j,ai+1,j|1≤i＜m,1≤j≤n}基本操作：CreateSMatrix(&M)DestroySMatrix(&M)PrintSMatrix(M)CopySMatrix(M,&T)AddSMatrix(M,N,&Q)SubSMatrix(M,N,&Q