More Related Content
Viewers also liked (20)
Similar to 第05章 数组和广义表(java版) (16)
More from Yan Li (7)
第05章 数组和广义表(java版)
- 1. 第 5 章 数组和广义表 ? 5.1 数组 ? 5.2 特殊矩阵的压缩存储 ? 5.3 广义表
- 2. 目的和要求 ? 目的：线性结构到非线性结构的过渡，了解包含子结 构 的线性结构，理解链式存储结构在表达非线性数据 结 构中的作用。 ? 内容：使用二维数组表示矩阵及运算；三角矩阵、对 称矩 阵、稀疏矩阵等各种压缩存储方法实现矩阵 运算；广 义表的概念、双链表示和实现。 ? 要求：理解多维数组的存储结构；熟悉特殊矩阵的压 缩存 储方法；掌握稀疏矩阵三元组从顺序表、行 的单链表 到十字链表等到多种存储结构的演变过程； 理解广义 表的概念，熟悉广义表的存储结构。 ? 重点：讨论多种由顺序存储结构和链式存储结构有机 结合 的存储结构，以矩阵为例，研究在相同的逻 辑结构 （矩阵）和操作要求（矩阵运算）情况下， 根据各种 矩阵的不同特性，采用多种存储结构实现矩 阵运算。 ? 难点：稀疏矩阵的多种存储和实现，广义表的存 储和 实现。
- 3. 《数据结构（ Java 版）（第 3 版）》 5.1 数组 5.1.1 一维数组 Loc(ai)= Loc(a0) ＋ i ×c 5.1.2 多维数组 （ 1 ）静态顺序存 储 ? 行主序 ? 列主序 cjniaLocaLoc ij ×+×+= )()()( 00 cimjaLocaLoc ij ×+×+= )()()( 00
- 4. 《数据结构（ Java 版）（第 3 版）》 （ 2 ）动态二维数组的存储结 构
- 5. 《数据结构（ Java 版）（第 3 版）》 【例 5.1 】 矩阵类。 设 ，有 设 ，有 设 ，有 设 ，有 00 01 0, 1 10 11 1, 1 1,0 1,1 1, 1 ?? ?? ?? ?? ?? ?? ?? n n m n m m m n a a a a a a a a a ? ? × ? ? ? ? ? ? ? ? ? ?= ? ? ? ? ? ?? ? A nmnmnm BAC ××× += ijijij bac += nmnmnm BAC ××× ?= ijijij bac ?= lnnmlm BAC ××× ×= ∑ ? = ×= 1 0 )( n k kjikij bac 的转置矩阵nmmn AT ×× = jiij at =
- 6. 《数据结构（ Java 版）（第 3 版）》 5.2 特殊矩阵的压缩存储 5.2.1 三角矩阵、对称矩阵和对角矩 阵的压缩存储 5.2.2 稀疏矩阵的压缩存储
- 7. 《数据结构（ Java 版）（第 3 版）》 5.2.1 三角矩阵、对称矩阵 和对角矩阵的压缩存储 1. 三角矩阵的压缩存储 （ 1 ）线性压缩存储三角矩阵 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?????? ???? × 1,12,11,10,1 2,21,20,2 1110 00 0 00 000 nnnnnn nnnn nn aaaa aaa aa a ? ? ????? ? ? A nijj ii a jiaaij <≤≤+ +× += +++++= 0 2 )1( )(Loc 21)(Loc)(Loc 00 00 ?
- 8. 《数据结构（ Java 版）（第 3 版）》 （ 1 ）线性压缩存储上三角矩 阵 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?? ???? ?? ?? × 1,1 1,22,2 1,12,111 1,02,00100 000 00 0 nn nnnn nn nn nn a aa aaa aaaa ? ? ????? ? ? A njij ini a ijinnnaaij <≤≤+ ??×× += ?++?++?++= 0 2 )12( )(Loc )1()1()(Loc)(Loc 00 00 ?
- 9. 《数据结构（ Java 版）（第 3 版）》 （ 2 ）使用三角形的二维数组 压缩存储三角矩阵
- 10. 《数据结构（ Java 版）（第 3 版）》 2. 对称矩阵的压缩存储 ? ? ? ? ? <<≤+ +× + <≤≤+ +× + = njii jj a nijj ii a aij 0 2 )1( )(Loc 0 2 )1( )(Loc )(Loc 00 00 jiij aa =
- 11. 《数据结构（ Java 版）（第 3 版）》 3. 对角矩阵的压缩存储 ? ? ? ? ? ? ? ? ? ? ? ? = ?? × 1,1 11 00 00 00 00 nn nn a a a ? ???? ? ? A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ???? ???? × 1,11,2 1,22,2 2221 121110 0100 000 000 000 00 000 nnnn nnnn nn aa aa aa aaa aa ? ? ?????? ? ? ? A
- 12. 《数据结构（ Java 版）（第 3 版）》 5.2.2 稀疏矩阵的压缩存 储 1. 表示稀疏矩阵的三元组 {(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
- 13. 《数据结构（ Java 版）（第 3 版）》 2. 稀疏矩阵三元组顺序表 （ 1 ）稀疏矩阵三元组顺序表类 public class SeqSparseMatrix { int rows, columns; // 矩阵行数、列数 SeqList<Triple> list; // 三元组顺序表 }
- 14. 《数据结构（ Java 版）（第 3 版）》 2. 稀疏矩阵三元组顺序表 （ 2 ）获得或设置稀疏矩阵元素值 （ 3 ）稀疏矩阵描述字符串 （ 4 ）稀疏矩阵相加 【例 5.2 】三元组顺序表表示的稀疏矩 阵及其加法运算。
- 15. 《数据结构（ Java 版）（第 3 版）》 3. 稀疏矩阵三元组单链表
- 16. 《数据结构（ Java 版）（第 3 版）》 4. 稀疏矩阵行的单链表 （ 1 ）稀疏矩阵三元组行的单链表类 public class LinkedSparseMatrix { int rows, columns; // 矩阵行数、列 数 SeqList<PolySLinkedList<Triple>> list; // 行指针顺序表，元素是多项式排序单
- 17. 《数据结构（ Java 版）（第 3 版）》 4. 稀疏矩阵行的单链表 （ 2 ）获得或设置稀疏矩阵元素值 （ 3 ）稀疏矩阵描述字符串 （ 4 ）稀疏矩阵相加 （ 5 ）深度拷贝及应用
- 18. 《数据结构（ Java 版）（第 3 版）》 （ 6 ）比较两个矩阵是否相 等
- 19. 《数据结构（ Java 版）（第 3 版）》 5. 十字链表
- 20. 《数据结构（ Java 版）（第 3 版）》 十字链表存储的稀疏矩阵类 public class CrossNode // 十字链表结点 类 { Triple data; // 数据域表示三 元组 CrossNode right, down; //right 指向行的 下一个结点， down 指向列的下一个结点 } public class CrossLinkedSparseMatrix { int rows, columns; // 矩阵行数、列 数
- 21. 《数据结构（ Java 版）（第 3 版）》 5.3 广义表 5.3.1 广义表抽象数据类型 5.3.2 广义表的存储结构 5.3.3 广义表双链表示的实现 5.3.4 m 元多项式的广义表表示
- 22. 《数据结构（ Java 版）（第 3 版）》 5.3.1 广义表抽象数据类 型 1. 广义表定义 GList = (a0, a1,…, an-1) 中国 ( 北京 , 上海 , 江苏 ( 南京 , 苏州 ), 浙江 ( 杭州 ), 广东 ( 广州 )) L ＝ (a, b) // 线性表，长度为 2 ，深度为 1 T ＝ (c, L) ＝ (c, (a,b)) //L 为 T 的子表， T 的长度为 2 ，深 度为 2 G ＝ (d, L, T) ＝ (d, (a, b), (c, (a, b))) //L 、 T 为 G 的子表， G 的长度为 3 ， 深度为 3
- 23. 《数据结构（ Java 版）（第 3 版）》 带表名的广义表表示 L(a,b) T(c, L(a,b)) G(d, L(a,b), T(c, L(a,b))) S() S1(()) Z(e, Z(e, Z(e, Z(…))))
- 24. 《数据结构（ Java 版）（第 3 版）》 2. 广义表的特性 （ 1 ）线性结构 （ 2 ）多层次结构，有深度 （ 3 ）可共享 （ 4 ）可递归
- 25. 《数据结构（ Java 版）（第 3 版）》 4. 广义表抽象数据类型 public interface GGenList<T> { boolean isEmpty(); // 判断广义表是否空 int length(); // 返回广义表长度 int depth(); // 返回广义表深度 GenListNode<T> insert(int i, T x); // 插入原子 x 作为第 i 个 元素 GenListNode<T> insert(int i, GenList<T> glist); // 插入子表作为第 i 个元素 void remove(int i); // 删除第 i 个元素 }
- 26. 《数据结构（ Java 版）（第 3 版）》 5.3.2 广义表的存储结构 1. 广义表的单链表示
- 27. 《数据结构（ Java 版）（第 3 版）》 2. 广义表的双链表示
- 28. 《数据结构（ Java 版）（第 3 版）》 共享子表 L 进行头删除操作产生 错误
- 29. 《数据结构（ Java 版）（第 3 版）》 5.3.3 广义表双链表示的实 现 1. 广义表双链表示的结点类 public class GenListNode<T> { T data; // 数据域 GenList<T> child; // 指向子表 GenListNode<T> next; // 指向后继结点 }
- 30. 《数据结构（ Java 版）（第 3 版）》 2. 双链表示的广义表类 public class GenList<T> implements GGenList<T> { GenListNode<T> head; // 头指针 } 例 5.3 广义表的双链表示及构造算法。 a. 由原子数组构造广义表 b. 由广义表表示创建广义表
- 31. 《数据结构（ Java 版）（第 3 版）》 由“ (d, (a,b), (c,(a,b)))” 创建 的广义表没有建立共享子表
- 32. 《数据结构（ Java 版）（第 3 版）》 5.3.4 m 元多项式的广义表表 示 53323204 53223334 8)26()26()315( 86622315),( yyxxyxxyx yyxyxyxyxxyxP ++?++?+?= +??++?=