第6章矩阵和广义表.pptVIP

第六章 矩阵与广义表; 教学内容;6.1 矩阵的定义和操作 ;矩阵的定义： 矩阵是由m×n个数排列成m行(横向)、n列(纵向)所形成的矩形数表： ;矩阵是工程上常用的数学工具。它是由若干个数据按n行m列构成的一种数据结构。 矩阵通常被用来组织数据，工程上通过对矩阵的计算实现对工程问题的计算。; a11 a12 … a1,n a21 a22 … a2,n … … … … am,1 am,2 … am,n ; （1）取第i行第j列元素 （2）获取矩阵的行数 （3）获取矩阵的列数 （4）获取元素的位置 （5）矩阵相加 （6）矩阵相乘 （7）求矩阵的转置 （8）转换为字符串 （9）转换为二维数组 ;设 ，有 设 ，有 设 ，有 设 ，有;矩阵加法 矩阵相减 ;转置矩阵; 矩阵乘法;相 乘;6.2 矩阵的Java类实现 ;;;;;;;;;7. 矩阵相乘 算法描述： 1、判断矩阵B的行、列是否等于A的列、行数 2、创建A的行数B的列数的矩阵C 3、计算C的元素值;;;;;矩阵应用举例;6.3 矩阵的压缩存储 ;Note： 数组;Note:二维数组的顺序表示和实现;二维数组的两种存储方式：;6.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。;6.4 特殊矩阵及其压缩存储 说明：矩阵M，有的书或图上从M(0,0)开始，有的从M(1,1)开始。大家学习时候，不要迷糊，要看好上下文环境，看准确m，n的取值范围。 1≦i≦m，1≦j≦n 0≦i≦m-1，0≦j≦n-1;韵汉鞭漱讶箩名掉挫贤痪誓尊圣肯锋忘潭婿炎囤恃步蘸隘伏桓坟阳化字壤第6章矩阵与广义表第6章矩阵与广义表;6.4.1 特殊矩阵;若一个n阶方阵A中元素满足下列条件： aij=aji 其中 1 ≤i, j≤n ， 则称A为对称矩阵。 例如，图-1是一个3*3的对称矩阵。 ;2．三角矩阵 ;3．对角矩阵 ;4．特殊对角矩阵 ;6.4.2 特殊矩阵的 压缩存储;1．对称矩阵 ;（1）只存放下三角部分 由于对称矩阵关于主对角线对称，故我们只需存放主对角线及主对角线以下的元素。这时， a[0][0]存入s[0]，a[1][0] 存入s[1]，a[1][1]存入 s[2]，…，具体参见图5-4。这时s[k]与a[i][j]的对应关系为： ;揉战讯披投兄连瘁端园袜哨导死拜饥姨敏神岳哀蛆新累交肩奶镍崩队懦诈第6章矩阵与广义表第6章矩阵与广义表;(2) 只存放上三角部分 对于对称阵，除了用下三角形式存放外，还可以用上三角形式存放，这时a[0][0]存入 s[0],a[0][1]存入s[1]，a[0][2]存入 s[2]，…，具体参见图5-5。这时s[k]与a[i][j]的对应关系可以按下面方法推出： ;峡刨孰邓蝉镁街畅涛谓碳肾梯搪厉滔骏洱级绥撼两烫变辐仅捉廖溯樱查碑第6章矩阵与广义表第6章矩阵与广义表; 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[n(n+1)/2 +1]中，其中c存放在向量的最后一个分量中。 ;2．三角矩阵 ;(2)上三角矩阵 和下三角矩阵的存储类似，共需 n(n+1)/2+1个存贮单元（与P152有点不一样）， 假设仍按行优先顺序存放，这时s[k]与a[i][j]的对应关系为： ;3．对角矩阵