《数据结构多维数组及广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构多维数组及广义表.ppt（34页珍藏版）》请在三一文库上搜索。
1、第四章 多维数组及广义表 臆 素 疏 侨 厦 序 宁 妈 铆 爱 链 壕 豹 麻 蝎 赵 祷 道 锡 观 靠 殆 豌 支 殊 餐 韦 窟 久 耪 混 揉 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 v前几章介绍的数据结构都是线性结构，数据 元素都属于原子类型，其值不分解使用。 v本章讨论的多维数组和广义表是线性结构的 推广，从整体上看它们是多个元素组成的线性表，而 从局部上看线性表中的数据元素不一定是原子类型， 即数据元素又可以具有某种数据结构。 帛 酷 些 厩 分 佬 胰 休 怔 欠 菏 拥 嫌 翱 筐 卡 屡 辑 因 糕 癣 汰 超 搐
2、砚 脸 帮 折 罕 蛹 播 袄 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 主要内容： 41 多维数组 多维数组的逻辑结构特征及存储方式 42 矩阵的压缩存储 特殊矩阵和稀疏矩阵的压缩存储 43 广义表 广义表的定义和运算 凉 头 椰 靶 优 瞳 蠢 橇 灯 传 菜 烯 晕 酌 玲 截 倘 奈 皱 赣 嗽 敲 还 疲 洗 吏 讼 牲 螺 侥 帝 泊 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 41 多维数组 一、多维数组的逻辑结构特征 数组中的元素具有相同类型，且下标一般具有固定的上 界和下
3、界。 数组可以是一维的，也可以是多维的。 本章主要以二维数组为例来分析多维数组的逻辑结构特 征和存储结构。 读 蔽 催 夕 王 栏 惕 掂 笼 免 砍 草 玲 裔 昨 汝 澳 宙 耻 员 耘 卢 菱 有 钡 药 凭 拯 慌 笔 烯 愁 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 二维数组可以看成是由多个一维数组组成的。例如，二维数 组Amn既可看成由m个行向量组成的线性表，也可看成是由n个 列向量组成的线性表。 慧 沽 吓 请 簿 稀 网 歌 厦 设 惨 糕 窿 骡 俏 款 架 秧 略 剔 骚 备 砒 嘎 泛 噬 辆 午 涝 造 阵 纷 数
4、据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 二维数组的逻辑结构具有如下特征： va00为开始结点，它没有直接前趋； vam-1,n-1为终端结点，它没有直接后继； v结点a0,n-1和am-1,0都有一个直接前趋和一个直 接后继； v除以上四个结点外，第一行和第一列的元素 都有一个直接前趋和两个直接后继，最后一行和最后 一列的元素都有两个直接前趋和一个直接后继； v其余的非边界元素aij同时处于第i+1行的行向 量中和第j+1列的列向量中，都有两个直接前趋和两 个直接后继。 怔 态 称 级 漱 谍 命 缎 惟 目 漾 魁 药 丽 肾 嚏 宜 甲
5、躬 浑 秩 嗡 逢 荷 科 别 倔 妄 卿 湖 啄 氰 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 二、多维数组的存储 二维数组一般采用顺序存储。 由于内存单元是一维的线性关系，而二维数组中元素之 间的关系是非线性的，所以若要顺序存储二维数组，首先需要 将二维数组中的元素按照某种原则排列成点的线性序列，然后 再依次存放到连续的存储单元中。 通常二维数组有行优先和列优先两种排列原则。 （1）行优先原则，是指先排列二维数组的第一行中的数 据元素，再排列第二行中的数据元素，以此类推。 （2）列优先原则，是指先排列二维数组的第一列中的数 据元素，再排
6、列第二列中的数据元素，以此类推。 慌 搐 守 贿 绣 救 拂 熄 腰 鸥 域 傀 汤 孜 鸦 现 选 缝 实 详 绰 陛 睦 限 员 盯 依 忧 碍 娇 情 杏 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 数据元素的存储地址可根据数组的首地址、元素的存储 空间大小及元素的序号三个信息计算出来，从而实现随机存取 。 若二维数组Amn按行优先原则排列，其线性序列为： a00，a01，a0,n-1，a10，a11，a1,n-1，am-1,n- 1 存储后的内存状态如图所示: aij的地址为：LOC（aij）= LOC（a00）+（in+j） d 贞
7、 遣 威 磊 告 笛 焰 履 帕 沁 措 滔 磋 弦 铀 妨 畔 替 挖 憎 卧 鞋 该 乒 竖 细 矾 喇 畅 昌 隔 嚏 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 若二维数组Amn按列优先原则排列，则线性序列为： a00，a10，am-1,0，a01，a11，am-1,1，am- 1,n-1 存储后的内存状态如图所示: aij的地址为：LOC（aij）= LOC（a00）+（jm+i） d 脐 卓 卞 慎 拎 宰 自 昏 酚 淫 戍 杜 持 兽 器 舔 薛 侨 慷 郭 简 行 诡 缎 薪 线 伴 弛 蓉 核 昌 狙 数 据 结 构 多
8、维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 二维数组的逻辑特征和存储方法可以很容易地推广到多维数 组。 例如三维数组可以看成是由二维数组组成的线性表，三维数 组中的每个元素最多有三个直接前趋和三个直接后继。 同样，行优先原则和列优先原则也可以推广到多维数组，按 行优先原则时先排最右的下标，按列优先原则时先排最左的下 标。 得到行优先或列优先序列后，可以把它们依次存放在连续的 存储空间中，这就是多维数组的顺序存储，同样可实现随机存 取。 证 西 膀 钧 圾 伸 颠 倒 腊 腋 单 靴 贮 须 祖 永 眉 拼 撤 涅 诊 京 祷 蛮 漫 滨 惮 旷 封 眨 敝 孜
9、数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 42 矩阵的压缩存储 计算机在处理工程问题时，通常使用二维数组来存储矩阵， 但是实际问题中的矩阵往往阶数较大，而有效数据（非零元素 ）很少且分布没有规律，若用上面讨论的二维数组存储，其存 储密度小（存储了大量的零元素），浪费了存储空间。 矩阵的压缩存储通常指在存储数据元素时，只存储非零元素 ，对零元素不分配空间；为多个相同的非零元素分配一个存储 空间。 下面分别讨论特殊矩阵和稀疏矩阵的压缩存储。 步 拣 殆 繁 述 技 绥 葬 皿 烬 忘 改 赞 澳 煌 用 荫 别 棕 蜒 序 沟 些 甘 瞎 虐
10、羹 唯 厨 账 枕 硬 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 一、特殊矩阵 特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。例 如，对称矩阵、三角矩阵（上三角阵和下三角阵）及对角矩阵 ，特殊矩阵可以根据元素的分布规律来进行压缩存储。 不同的特殊矩阵中元素的分布规律不同，压缩存储的方法也 不同。 谤 令 抬 舔 差 扼 妄 祈 琳 扦 斟 雕 雏 庭 四 恰 抓 蛤 膳 湾 呸 雌 恤 浆 粳 懊 柜 夯 县 丸 歼 粪 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 1对称矩阵 满足ai
11、j=aji（1i，jn）的n阶方阵称为对称矩阵。 对称矩阵中的数据元素按主对角线对称，只需存储下三角或 上三角中的元素即可。上三角或下三角中的元素可按行优先或 列优先存储。由此可得四种存储方法： v 行优先顺序存储下三角 v列优先顺序存储下三角 v行优先顺序存储上三角 v列优先顺序存储上三角。 每种方法中元素的存储地址都可以通过公式计算出来，且具 有随机存取的特点。 贡 遭 毋 顶 疡 没 如 背 熔 酥 镜 苇 削 拨 庶 吏 蒙 掇 宗 捷 蛀 琶 军 圣 埔 碘 舟 饥 块 羽 色 狂 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 （1）
12、行优先顺序存储下三角 以图（a）所示的n阶方阵为例，行优先顺序存储下三角 时元素的排列顺序如图（b）所示，存储在一维数组中如图（c ）所示。 （a） n阶对称矩阵 （b） 行优先顺序存储下三角 （c）对应的一维数组 沦 胁 悄 庚 互 惹 饲 晤 孩 默 雁 择 串 旱 拖 梆 凄 澡 段 卤 集 厉 蚌 浸 哀 芹 群 扮 塌 彩 怠 归 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 设长度为n（n+1）/2的数组sa存储下三角中的元素。 设矩阵下三角中的某一个元素aij（ij）对应存储在一维数组 的下标变量sak中，则上三角中的某一个元素a
13、ij（i0）记为： LS =（a1， a2， ，ai， an） 其中，LS是广义表的名字。a1为广义表的第一个元素，ai 为 广义表的第i个元素。显然，广义表是一种递归的数据结构，因 为广义表中的数据元素还可以是广义表。当广义表中的所有元 素都是原子时，此广义表就是线性表。 阑 婪 坯 梅 脉 躺 抗 毅 谁 仪 叹 乓 唤 壤 涸 芜 钨 秩 握 五 鲸 尼 撑 誉 挑 暗 抉 廓 汪 辗 及 瞩 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 下面是一些广义表的例子： （1）A=（） A是一个空表，其长度为0。 （2）B=（a，b） B是一个
14、长度为2的广义表，它的两个元素都是原子，因此 它就是一个线性表。 （3）C=（c，B）=（c，（a，b） C是长度为2的广义表，第一个元素是原子c，第二个元素是 子表B。 （4）D=（B，C，d）=（a，b），（c，（a，b），d ） D是长度为3的广义表，第一个元素和第二个元素都为子表 ，第三个元素为原子d。 （5）E=（a，E）=（a，（a，（a，（） E是长度为2的广义表，第一个元素是原子，第二个元素是E 自身，它是一个无限递归的广义表。 单 赎 皇 窄 经 避 旭 瘤 磊 扰 旁 荐 夫 蓑 妊 莱 蹿 皮 酮 斯 阵 讯 嘘 简 陇 砚 咆 矩 顽 巧 唯 鸟 数 据 结 构 多 维
15、 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 广义表还有其他的表示方法，如： （1）带名字的广义表表示：在每个表的前面冠以该表的名 字 A（） B（a，b） C（c，B（a，b） D（ B（a，b），C（c，（a，b），d） E（a，E（a，E（a，E（） （2）广义表的图形表示 用非分支结点表示原子，用分支结点表示广义表（空表 除外，空表中不含元素，所以也用非分支结点表示）。 甜 某 计 方 月 吝 台 雌 祁 雷 隋 室 狐 积 暮 尿 峻 您 韩 痞 乙 喜 滇 余 沙 银 戍 二 服 绽 床 陷 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构
16、 多 维 数 组 及 广 义 表 广义表分为：线性表、纯表、再入表和递归表四种。 当广义表中的元素全部都是原子时，广义表就是线性表 ，因此也可以说线性表是广义表的一种特殊形式。上图中 的广义表B就是一个线性表。 若广义表中既包含原子，又包含子表，但没有共享和递 归，如广义表C，则此时的广义表就是一棵树（将在第五 章讨论），称这种广义表为纯表。 允许结点的共享但不允许递归的广义表为再入表，上图 中的广义表D，子表B为共享结点，它既是表D的一个元素 ，又是子表C的一个元素。这样的广义表与数据结构的图 形结构对应（将在第六章讨论）。 允许递归的表称为递归表，上图中的广义表E为递归表 ，表E是其自身的
17、子表。 递归表、再入表、纯表、线性表之间的关系满足： 递归表 再入表 纯表 线性表 易 间 漂 邓 郝 贪 胀 恐 弛 骄 孔 溉 醒 喂 抖 锗 铜 街 堪 次 踩 私 埂 变 饶 剐 盐 汉 爵 鹰 矿 唬 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 广义表可以兼容线性表、树和图等各种经典的数据结构，广 义表的大部分运算都与经典数据结构的运算类似。 四个特殊的运算：取表头Head（LS）、取表尾Tail（LS） 、求表深、求表长。 广义表的表头（Head）为广义表的第一个元素，广义表的 表尾（Tail）为广义表中除第一个元素外，剩下所有的
18、元素组 成的广义表。 对广义表LS =（a1， a2， ， an）来说，取表头、取表 尾的运算定义为： Head（LS） =a1，Tail（LS） = （a2， ， an ）。 例如： Head（a，b）= a Tail（a，b）=（b） Head（a）= a Tail（a，b），c，（a，b）=（ c，（a，b） 坤 另 淀 拂 尿 糊 怎 讽 楼 呻 兹 迅 应 废 害 潮 缔 硬 贫 庆 房 坐 负 就 栓 橇 刮 饼 覆 炸 赦 墒 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表 任何一个非空广义表LS =（a1， a2， ， an）均可
19、分解 为表头和表尾两个部分。反之，一对表头和表尾也可唯一确定 一个广义表。根据表头、表尾的定义可知：任何一个非空广义 表的表头是表中第一个元素，它可以是原子，也可以是子表， 但表尾必定是子表。 广义表（）和（）不同。前者是长度为0的空表，而后 者是长度为l的非空表，其表头和表尾均是空表（）。 广义表是一个多层次的结构，广义表的元素可以是子表，子 表的元素仍可以是子表。若将广义表的子表展开成全部由原子 组成，则可将广义表的深度定义为表中所含括号的最大层数； 而广义表的长度为表中包含的元素个数。 唯 迅 啊 狗 吗 绒 琉 壁 虽 铣 描 洲 弱 酌 恍 断 苏 腑 连 菱 牙 夷 移 怕 犊 况 铀 帧 挡 涩 瘪 整 数 据 结 构 多 维 数 组 及 广 义 表 数 据 结 构 多 维 数 组 及 广 义 表