数据结构第5章.ppt

第五章数组和广义表普通数组的定义和表示特殊矩阵的压缩存储稀疏矩阵的存储广义表计算一维下标以二维数组A[m][n]为例，计算数组元素A[i][j]的存储空间下标w:以行序为主序的存储方式w=i*n+j以列序为主序的存储方式w=j*m+i有三维数组A[3][4][5],计算数组元素A[2][3][3]的存储空间下标：以行序为主w=2*(4*5)+3*5+3=58各维长度为d1=2,d2=5,d3=3,d4=4的4维数组A例：有如下数组定义floata[10][5][7];1、若数组a的首地址为1200，求数组元素a[3][4][5]在按行存储方式下的地址？2、其按列存储方式下的地址？注：sizeof(float)=4稀疏矩阵的三元组表存储方式typedefstruct{inti,j;ElemTypee;}Triple;Triple*data;data[0]的三元分别用于存放矩阵总的行数、列数和非零元个数；用三元组表示的非零元以行序为主序依次存放在data中。转置算法一aijvbijv由a求其转置矩阵b，需做以下事情：⑴矩阵的行列值互换，即若a为m×n,则b为n×m；⑵每个三元组的行列号互换，即aij对应于bji；⑶a中三元组以原矩阵的行号为序，而b中三元组是以原矩阵的列号为序。5.4广义表的定义广义表：是n(n=0)个元素的集合。LS=(d1,d2,d3,,dn)LS为表名di∈D0时，称di为单元素或原子(用小写字母表示)；di∈Lists时,称di为子表(用大写字母表示)；n为表的长度，当长度为0时称为空表；n0时,第一个元素d1为表头;n0时,(d2,…,dn)称为表尾。.广义表的长度和深度长度n:是广义表的元素个数；深度k:广义表的元素之间除了存在次序关系外，还存在层次关系。广义表中元素的最大层次为表的深度。提示：元素的层次就是包括该元素的括号对的数目。广义表举例：A=()n=0,k=1B=(e)n=1,k=1C=(a,(b,c,d))n=2,k=2D=(A,B,C)n=3,k=3{即D=((),(e),(a,(b,c,d)))}E=(a,E)n=2,k=?{定义一个无限的递归表(a,(a,(a,…)))}原子或列表:Gethead(C)=aGethead(D)=A列表:Gettail(C)=((b,c,d))Gettail(B)=()（）和（（））不同：（）为空表，长度n=0；后者长度n=1,可分解得到表头、表尾均为空表（）。5.5广义表的链式存储结构结点结构：typedefstructGLN{inttag;union{AtomTypeatom;structGLN*hp;};structGLN*tp;}*Glist;广义链表表头表尾结点表示法(Page110)例：画广义表的存储结构

C=(a,(b,c,(d)));n=2;k=3C例：用存储结构表示广义表达式A=()B=(e)C=(a，(b，c，d))D=(A，B，C)=(()，(e)，(a，(b，c，d)))E=(a，E)=(a，(a，(a，…)))本章重点一般多维数组的存储及