矩阵与广义表.ppt

教学内容 6.1 矩阵的定义和操作 6.2 矩阵的Java类实现 6.3 矩阵的压缩存储 6.4 特殊矩阵的压缩存储 6.5 稀疏矩阵及其存储结构 6.6 广义表 矩阵是工程上常用的数学工具。它是由若干个数据按n行m列构成的一种数据结构。 矩阵通常被用来组织数据，工程上通过对矩阵的计算实现对工程问题的计算。 设 ，有 设 ，有 设 ，有 设 ，有 矩阵加法 矩阵相减 相 乘 7. 矩阵相乘 算法描述： 1、判断矩阵B的行、列是否等于A的列、行数 2、创建A的行数B的列数的矩阵C 3、计算C的元素值 矩阵应用举例 P147 Note： 数组 一维数组 Loc(ai)= Loc(a0)＋i ×c 多维数组 （1）静态顺序存储 行主序 列主序 Note:二维数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 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.4.1 特殊矩阵 特殊矩阵:指非零元素或零元素的分布有一定规律的矩阵,下面我们讨论几种特殊矩阵的压缩存储。 方阵 6.4.2 特殊矩阵的 压缩存储 6.5 稀疏矩阵及其存储结构 例子： 6.6 广义表 当广义表非空时，称第一个元素a1为LS的表头（表头可能是原子，也可能是列表），其余元素组成的表（a2,a3,…,an）是LS的表尾（表尾一定是列表）。 例如: 若 C=(a, (b, c, d)) D=(A, B, C) 则：Head(D)=A Tail(D)=(B, C) Head(C)=a Tail(C)=((b, c, d)) 以上是广义表的两个操作： 取表头 Head 、取表尾Tail 这些操作还可以嵌套调用：  Head（ Tail(D) ）＝ Head((B,C)) = B 注意： 广义表（）和广义表(( ))不同。 （）为空表，长度 n＝0 ，不能分解成表头和表尾。 (( )) 不是空表，其长度 n = 1 ，可以分解得到表头是空表( ) , 表尾是空表( ) . 补充 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素 A[5,8]的首地址为（?? ）。　A．BA+141? B．BA+180??? C．BA+222?????? D．BA+225 补充 2. 对稀疏矩阵进行压缩的目的是（ ）。 A. 便于进行矩阵运算 B. 便于输入和输出 C. 节省存储空间 D. 降低运算的时间复杂度 补充 3. 已知广义表L=（e,((f,g),e),(c,d)），则表达式tail(head(tail(L)))的值为（ ）。 A．（d） B．(e) C．g D．e 本章小结 课后作业 the end 2.1 带行指针的链表 把具有相同行号的非零元用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，合起来称为带行指针的链表。 实现方法多种： P158描述及Java实现。 其它：如图5-6 的稀疏矩阵M的带行指针的链表描述形式见图5-9。 2.1 带行指针的链表 优缺点：部分解决了三元组方式的缺点（查找矩阵元素费时遍历），它可以很轻易的遍历同一行中的所有元素，但却很难遍历同一列中的所有数据。 为了解决这个缺点，出现了十字链表存储方式。 2.2 十字链表 十字链表为稀疏矩阵中的链接存储中的一种较好的存储方法，在该方法中，每一个非零元用一个结点表示，结点中除了表示非零元所在的行、列和值的三元组(i,j,v)外，还需增加两个链域：行指针域(rptr)，用来指向本行中下一个非零元素；列指针域(cptr) ，用来指向本列中下一个非零元素。 i j v cptr rptr 2.2 十字链表 稀