前面我们学习的 线性表 栈 队列 和 串 都是 线性结构 本章起学习的是非线性结构它们的逻辑特征是一个数据元素可能有多个直接前趋和多个直接后继
本章 重点 是熟悉 多维数组 的 存储方式 矩阵的 压缩存储方式 广义表 的定义及其求表头和表尾的运算 难点 是 稀疏矩阵 的压缩存储表示下实现的算法
多维数组( 领会 )
多维数组 的 逻辑结构特征 一个m维数组 An n n m的每个元素都属于m个向量最多可以有m个直接前趋和m个直接后继
多维数组 的 顺序存储结构 及其 地址计算方式 :计算机的内存结构是一维的因此将数组元素排成线性序列然后将这个线性序列存放在存储器中排列的方式有两种一是 行优先顺序 也就是把数组按一行一行的顺序依次排列二是 列优先顺序 就是把数组按一列列的顺序依次排列
地址的计算方法我们按行优先顺序排列的数组是这样计算的假设每个元素占用d个存储单元某个元素的地址就是它前面所有行所占的单元加上它所在行前面所有列元素所占的单元数之和不必去死记公式
数组是一种 随机存储结构 的原因因为在顺序存储的情况下每一个元素都有与其下标相对应的地址因此可以对数组中的元素进行随机存储
矩阵的压缩存储( 领会 )
特殊矩阵 的概念所谓特殊矩阵是指非零元素或零元素分布 有一定规律 的矩阵
稀疏矩阵 的概念一个矩阵中若其非零元素的个数 远远小于 零元素的个数则该矩阵称为稀疏矩阵
我们在本章学习了对称矩阵三角矩阵对角矩阵这三种特殊矩阵这三种特殊矩阵可以进行压缩存储主要要理解的是其下标变换方法
稀疏矩阵 的压缩存储方式 三元组表 就是把非零元素的值和它所在的行号列号做为一个结点存放在一起用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵但是这种压缩存储方式将失去随机存储功能
相关算法的理解要建立在对三元组表的结构的全面掌握的基础上但是本章的算法考试应不作要求
广义表的概念( 领会 )
广义表 又称列表(Lists)是线性表的推广就是说广义表中的元素不仅可以是数或一个结构而且推广到可以是一个表(这个表又可以是广义表)所以广义表是n(n≥)个元素aaaan的有限序列其中的ai或者是原子或者是一个广义表(为什么叫原子?因为原子是作为结构上不可分割的成分)
广义表 表头 和 表尾 的概念若广义表LS非空(n≥ )则这个广义表的 第一个 元素就是表头(这个表头可以是原子也可以是该广义表的子表)而 其余的元素 组成的表称为LS的表尾(要注意不是最后一个元素这和队列的队尾是不同的)所以表尾必是一个子表
广义表有两种表示法一种是 括号表示 法一种是 图形表示 法括号表示时一般以大写字母表示广义表以小写字母表示原子如A(xL(ab))用图形表示时图形中的分支结点对应广义表非分支结点一般表示原子如果一个广义表与树(形结构)相对应这个广义表就是纯表如果一个广义表的结点又可以被其他结点所共享则这个表称为再入表允许递归的表称为递归表
有一个关系式 递归表(包含)再入表(包含)纯表(树)(包含)线性表 可见 广义表是对线性表和树的推广
广义表有两个特殊的基本运算 取表头head(LS) 和 取表尾tail(LS) (我们看到tail这个词就是尾巴是一条尾巴而不是末尾它可能是一个原子但这个原子是作为子表来看待的)
取表头和表尾的运算要在 广义表非空 的情况下进行注意广义表()表示是空表(())则表示有一个元素的广义表这个元素是一个空表
这两个运算很容易理解也应该掌握
第五章 多维数组和广义表 复习要点
本章复习要点是
多维数组和广义表的逻辑结构特征它们是复杂的非线性结构一个数据元素可能有多个直接前趋和多个直接后继
多维数组的两种顺序存储方式行优先顺序和列优先顺序这两种存储方式下的地址计算方法
几种特殊矩阵的特征及其压缩存储地址对应关系
稀疏矩阵的三元组表示(画图形表示)
广义表是线性表的推广也是树的推广
能画出广义表的图形表示法
广义表的取表头运算与取表尾运算要注意表头是广义表的第一个元素它不一定是原子表尾则必是子表
本章可能出选择题填空题和应用题
