DS05_数组与广义表01_数组与特殊矩阵.pptVIP

学习要点 （1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 （2）掌握对特殊矩阵进行压缩存储时的下标变换公式。 重点放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。 （3）了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 （4）掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。 特殊线性表 广义线性表 n维数组类型同理，可以定义为其数据元素为n-1维数组类型的一维数组类型。 (b) 推广到一般情况，可得到n维数组的数据元素存储位置的计算公式： LOC[j1,j2,…,jn] = LOC[0,0,…,0] + (b2×…×bn×j1 + b3×…×bn×j2 + … + bn×jn-1 + jn ) × L = LOC[0,0,…,0] + ( + jn ) × L LOC[j1,j2,…,jn ] = LOC[0,0,…,0] + 其中 cn = L ， ci-1 = bi × ci , 1 i ≤ n 上式称为 n 维数组的映象函数。 i 第ai行元素个数 0 1 1 2 2 3 3 4 n-1 n 总的元素个数：1+2+3+…+n = n(n+1)/2 所以，对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将 n2个元素压缩存储到n(n+1)/2个元的空间中 假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系： 假设以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系： 如果下标从1开始 2. 下三角矩阵 所谓下（上）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元均为常数c或零的n阶矩阵。则除了和对称矩阵一样只存储其下（上）三角中的元之外，再加一个存储常数c的存储空间即可。 对角矩阵 本章的习题分为五类： 如何判断一个单链表是否对称。 a1,a2,a3,....an 思路 1. 利用求链表中间结点的方法，p每次走一步，q每次走两步，并且在走的过程中p将每个结点推入栈，那么q走到表尾时，栈中为单链表的前半子表。 2. p继续走，每走一步将栈顶元素弹出，并与对称元素比较。 5.3.1 特殊矩阵 对称矩阵 三角矩阵 对角矩阵 3　6　4　7　8 6　2　8　4　2 4　8　1　6　9 7　4　6　0　5 8　2　9　5　7 A＝ 对称矩阵特点：aij=aji Q: 如何压缩存储？ 只存储下三角部分的元素。 1.对称矩阵 A= 对称矩阵的压缩存储 ……………………… a10 a11 …….. a1,n-1 a00 a01 …….. a0,n-1 an-1,0 an-1,1 …….. an-1,n-1 对称矩阵的地址计算公式 第1行 第n-1行 第0行 a00 a10 a11 a20 a21 a22 aij … a n-10 an-11 … an-1n-1 … 第2行 0 1 2 3 4 5 k n(n+1)/2-1 A= ……………………… a10 a11 …….. a1,n-1 a00 a01 …….. a0,n-1 an-1,0 an-1,1 …….. an-1,n-1 对称矩阵的地址计算公式 对于下三角中的元素aij（i≥j），在数组sa中的下标k等于aij前面的元素数，则k与i、j的关系为： k＝i×(i＋1)/2＋j 上三角中的元素aij（i＜j），因为aij＝aji，则aij相当于存储在aj