数据结构与算法-东北林业大学 第五章数组和广义表.ppt

《数据结构与算法-东北林业大学 第五章数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG主讲：王阿川数据结构第五章　数组和广义表§5.1数组的定义§5.2数组的顺序表示和实现§5.3矩阵的压缩存储§5.4广义表的定义§5.5广义表的存储结构§小结§习题第五章数组和广义表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表§5.1数组的定义类型相同的有限个元素的序列，叫数组。可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。返回§5.2数组的顺序表示和实现（1）   按行优先顺序存放（2）   按列优先顺序存放返回amn……..am2am1……….a2n…

2、…..a22a21a1n…….a12a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(i-1)n+(j-1)]S按行优先顺序存放amn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….loc(aij)=loc(a11)+[(j-1)m+(i-1)]S按列优先顺序存放5.3矩阵的压缩存储1.压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。2.特殊矩阵假若值相

3、同的元素或者0元素在矩阵中的分布有一定的规律，既为特殊矩阵。反之，称为稀疏矩阵。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。5.3矩阵的压缩存储5.3.1特殊矩阵若所有元素都保存，则需要n2个存储空间。若采用压缩存储只需n(n+1)/2个元素的存储空间。15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1图5.1对称矩阵an-10an-11an-12…an-1n-1480963lastn=8n(n-1)/2…..n(n+1)/2a0

4、0a10a11a20a21a22a30…0123456在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：1+2+3+…+(i+1)+…+n=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦k

5、/2an-10an-11an-12…an-1n-1480963lastn=8n(n-1)/2…..n(n+1)/2a00a10a11a20a21a22a30…0123456在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为：1+2+3+…+(i+1)+…+n=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]之间找一个对应关系。若i≧j，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，ai

6、j之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦k

7、定一组下标(i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(I,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，例如a21和a12均存储在sa[4]中，这是因为k=I*(I+1)/2+J=2*(2+1)/2+1=42、三角矩阵

8、a00a01…a0n-1

9、

10、a00c…c

11、

12、ca11…a1n-1

13、

14、a10a11…c

15、

16、…………………..

17、

18、……………