数据结构5.数组和广义表ppt课件.ppt

《数据结构5.数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构5.1数组的定义a11a12…a1na21a22…a2n…………am1am2…amn可以将数组A看成长度为m的线性表BB=(b1,b2,…bm)其中，每个元素bi是长度为n的线性表,既数组A中的第i行。bi=ai1,ai2,…ainAmn=5.1数组的定义a11a12…a1na21a22…a2n…………am1am2…amn可以将数组A看成长度为n的线性表CC=(c1,c2,…cn)其中，每个元素cj是长度

2、为m的线性表,既数组A中的第j列。cj=a1j,a2j,…amjAmn=5.1数组的定义a11a12…a1na21a22…a2n…………am1am2…amn数组只有两个操作：（1）存取元素（2）修改元素值C描述：datatypea[m][n]Amn=5.2数组的顺序表示和实现数组有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列。a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列。a11,a21,…,am1,a12,a22,…am2,……

3、,a1n,a2n,…,amn二维数组理解例inta[3][4];20161720181920202120222320089201011201213201415200012002320045200067a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]每个元素a[i]由包含4个元素的一维数组组成二维数组a是由3个元素组成a[0]a[1]a[2]行名014523a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[0][0

4、]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]a[1][2]67101189a[0]a[1]a[2]例1：二维数组Amn按“行优先顺序”存储在内存中，且每个元素占用d个存储单元。求元素aij的存储地址。LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d例2：三维数组Amnp按“行优先顺序”存储在内存中，且每个元素占用d个存储单元。求元素aijk的存储地址。LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d5.3矩阵的压缩存储5.3.1特殊矩阵一、对称矩阵在一个n阶方阵A

5、中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。15137a0050800a10a1118926a20a21a2230251………………..70613an-10an-11an-12…an-1n-1在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：n(n+1)/2因此，我们可以将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。i(i+1)/2+j当i>=jj(j+1)/2+i当i

6、1k=K=0123……n(n+1)/2-1二、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，a00a01a10a11a12a21a22a23….…..….an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1k=需存储的元素个数为3n-2。a00a01a10a11a12a21……an-1n-2an-1n-1K=012345……3n-43n-35.3.2稀疏矩阵设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（

7、即s<

8、转置012900000000000-3000014000240000018000