java数据结构数组和广义表.ppt

如何只存储非零元素？ 注意：稀疏矩阵中的非零元素的分布没有规律。 0 12 9 0 0 0 0 0 0 0 0 0 -3 0 0 0 14 0 0 0 24 0 0 0 0 18 0 0 0 0 15 0 0 -7 0 0 二、稀疏矩阵 １、稀疏矩阵的压缩存储 问题： 如果只存储稀疏矩阵中的非零元素，那这些元 素的 位置信息 该如何表示？ 解决思路： 对每个非零元素 增开 若干存储单元，例如存放 其所在的 行号 和 列号 ，便可 准确 反映该元素所在 位 置 。 实现方法： 1) 三元组法 2) 十字链表法 如 : 将每个非零元素用一个三元组（ i ， j ， a ij ）来表 示，则每个稀疏矩阵可用一个 三元组表 来表示。 方法一 : 三元组 将稀疏矩阵中的每个非零元素表示为： ( 行号，列号，非零元素值 ) —— 三元组 {(0,2,11) ， (0,4,17) ， (1,1,20) ， (3,0,19) ， (3,5,28) ， (4,4,50)} 5 6 0 0 11 0 17 0 0 20 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 28 0 0 0 0 50 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? A 行号 列号 元素值 row column value 可还原吗？ 不可以，须 再加一 行“总体”信息： 即 总行数、总列数、 非零元素总个数。 – 三元组单链表 – 行 / 列的单链表 方法二： 用 三元组链表 表示 方法三： 用 十字链表 表示 用途： 方便 稀疏矩阵的加减 运算； 方法： 每个 非 0 元素 占用 5 个域 。 row ：存储非零元素的行号 col ：存储非零元素的列号 item ：存储非零元素的值 right ：指针域，指向同一行中的下一个三元组 down ：指针域，指向同一列中的下一个三元组 right down item col row 十字链表的特点： ① 每行非零元素链接 成带表头结点的链表 ( 或循 环链表 ) ； ② 每列非零元素也链接 成带表头结点的链表 ( 或 循环链表 ) 。 则每个非零元素既是行链表中的一个结点；又是 列链表中的一个结点，即 呈十字链状 。 2 0 2 ∧ M= 3 0 0 5 0 1 0 0 2 0 0 0 0 0 3 0 3 5 ∧ ∧ 1 1 1 ∧ ∧ ∧ 稀疏矩阵的压缩存储 —— 十字链表 ( 实例 ) ∧ rhead chead ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ 广义线性表 多维数组 广义表 逻辑结构 存储结构 逻辑结构 存储结构 ⑴数组的定义 (2)ADT 定义 (3) 基本操作 顺 序 存 储 压 缩 存 储 特殊矩阵 · 对称矩阵 · 三角矩阵 · 对角矩阵 稀疏矩阵 按 行 优 先 按 列 优 先 寻址的计算方法 ⑴基本概念 · 广义表定义 · 表头、表尾 · 长度、深度 ⑵ ADT 定义 链 接 存 储 头尾表示法 转置算法 线性表 —— 具有相同类型的数据元素的有限序列。 限制插入、删除位置 线性表 —— 具有相同类型的数据元素的有限序列。 限制元素类型为字符 栈 —— 仅在表尾进行插入和删除操作的线性表。 队列 —— 在一端进行插入操作，而另一端进行 删除操作的线性表。 串 —— 零个或多个字符组成的有限序列 。 特 殊 线 性 表 线性表 —— 具有相同类型的数据元素的有限序列。 将元素的类型进行扩充 广 义 线 性 表 （多维）数组 —— 线性表中的 数据元素 可以 是 线性表 ，但 所有元素的类型相同 。 广义表 —— 线性表中的 数据元素 可以 是线性表 ， 且 元素的类型可以不相同 。 4.2 数组 数组（ array ）： 是 n(n=0) 个 相同数据类型 的数据元素 （ a 1 ,a 2 ,a 3 , … ,a n ）构成的 有限线性序列 。 n 为 数组长度 或 数组大小。 n=0 为空数组。 多维 数组：一个 m(m=2) 维数组，其 每个数据元素 是一 个 m-1 维的数组 。且每个元素都对应于一组下标 （ j 1 ,j 2 , … ,j m ） , 每个 下标 的 取值范围 是 c i ≤ j i ≤ d i , d i -c i +1 称 为 第 i 维 的 长度 (i=1,2, … ,n),m 为数组的维数。 数组的 特点 ： ① 数组中各元素具有 统一的类型 ； ② 数组元素的下标一般具有 固定的上界和下界 。 ③数组的 基本操作比