第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
- 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 ?
- 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 】三元组顺序表表示的稀疏矩
阵及其加法运算。
- 16. 《数据结构（ Java 版）（第 3 版）》
4. 稀疏矩阵行的单链表
（ 1 ）稀疏矩阵三元组行的单链表类
public class LinkedSparseMatrix
{ int rows, columns; // 矩阵行数、列
数
SeqList<PolySLinkedList<Triple>> list;
// 行指针顺序表，元素是多项式排序单
- 17. 《数据结构（ Java 版）（第 3 版）》
4. 稀疏矩阵行的单链表
（ 2 ）获得或设置稀疏矩阵元素值
（ 3 ）稀疏矩阵描述字符串
（ 4 ）稀疏矩阵相加
（ 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(…))))
- 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 个元素
}
- 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. 由广义表表示创建广义表
- 32. 《数据结构（ Java 版）（第 3 版）》
5.3.4 m 元多项式的广义表表
示
53323204
53223334
8)26()26()315(
86622315),(
yyxxyxxyx
yyxyxyxyxxyxP
++?++?+?=
+??++?=
