第三章非线性数据结构
3.1 数组
3.2 树
3.3 图目录计算机软件基础计算机软件基础
3,1 多维数组一．多维数组的定义二维以上的数组 。
注意,数组（ array） 在高级语言中是作为一种数据类型介绍的，而在本节中数组是作为一种常用数据结构来介绍的 。
计算机软件基础二,数组的逻辑结构 （ 以二维数组为例）
分析,二维数组中的每一个元素既受到行关系的制约，又受到列关系的制约。
若只考虑其中的一个关系，则对于任意元素，直接前驱和直接后继都是唯一的，
即行、列关系都是线性的。
结论,多维数组可看成是线性表的推广，
其逻辑关系是非线性的，实质上是多个线性关系的组合。
计算机软件基础三．多维数组的存储结构采用顺序存储结构实现 。
原因,多维数组一经定义，其元素个数就固定不变。
顺序存储的次序：
行优先,PASCAL,C语言列优先,FORTRAN语言
计算机软件基础四．矩阵的存储方法
1.普通矩阵的存储方法：
采用相应的二维数组实现 。
2.特殊矩阵的存储方法：
研究对象（两类特殊矩阵）
三角矩阵和稀疏矩阵采用压缩存储的方法实现 。
思考：两类特殊矩阵的共同特点是什么？
计算机软件基础
（ 1）三角矩阵的压缩存储分析,三角矩阵中非 0元素的分布有规律。
结论,可按照一定的顺序依次将三角矩阵中所有非 0元素存储在连续的存储空间中。
可行性,非 0元素在存储空间中的存放位置 k与其在原矩阵中的行、列位置间存在着一一对应的关系。
计算机软件基础例如：对下三角矩阵 A按行优先顺序对其进行压缩存储。
A =
nnn3n2n1
333231
2221
11
a,,,a a a
,,,,,,,,,,,,
a a a
a a
a
a11 a21 a22 a31 a32 a33 …,…,aij …,…,an1 an2 an3 …,…,ann
0 1 2 3 4 5 …,…,k …,…,m m+1 m+2 …,…,
m+n
计算机软件基础思考,
矩阵中第 i行第 j列的元素 aij存放在一维数组的哪个位置？
k=?
k= i? ( i - 1) / 2 + j-1
计算机软件基础
（ 2）稀疏矩阵的压缩存储分析,稀疏矩阵中非 0元素的分布 无 规律。
结论,可按照一定的顺序依次将稀疏矩阵中所有非 0元素存储在连续的存储空间中，
但必须在存储非 0元素值的同时设法记下其在矩阵中的位置。
可行的方法之一,三元组法存放每个非 0元素的值及其在原矩阵中的行、列位置三项信息。
计算机软件基础例如：对稀疏矩阵 A按行优先顺序对其采用三元组法进行压缩存储。
0 0 0 0 4 0
0 0 6- 0 0 0
0 0 0 0 0 2
0 1 0 3 0 0
A=
计算机软件基础行号 列号 元素值
4 6 5
1 3 3
1 5 1
2 1 2
3 4?6
4 2 4
结果：
注意：
通常可增加一个三元组，用于存放矩阵的整体信息！
计算机软件基础五,数组的应用迷宫问题
难点：
1,迷宫的表示（数字化）
2,回溯的实现（回退）
3,试探方向的控制
计算机软件基础
1.使用了一个 m行 n列的矩阵 maz表示迷宫，其中每个元素 maz[i,j]表示迷宫中的一个位置，其值为 1表示“此路不通”；其值为 0表示“可以通过”。
2.使用一个栈将所有走过的位置及进入该位置的方向记录下来 。 为了防止走重复的路，使用一个 mark矩阵存放每个位置是否走过的标志。
3.将方向数字化，并使用一个走步增量数组
move（ 二维数组）来描述向不同方向走步时将引起的 i和 j的增量。
解决办法：
计算机软件基础入口 0 0 0 0 0 1 1 0 0 0 0
1 0 0 0 1 1 0 1 1 1 1
0 1 1 0 0 0 0 1 1 1 1
1 1 0 0 1 1 1 0 1 1 0
1 1 0 1 0 0 1 0 1 0 1
0 0 0 0 0 1 1 0 0 1 1
0 1 0 1 0 0 0 0 0 1 1
0 0 1 1 1 0 1 1 0 0 0
1 0 0 0 0 0 1 1 0 1 1
1 0 0 1 1 0 0 0 0 1 1
1 1 1 1 0 1 0 1 0 0 0 出口迷宫的数字化矩阵说明,为避免每次检测是否走到边缘，可把 m行 n列的迷宫矩阵扩大为
m+2行 n+2列,且令增加的 0行,0列、
m+1行,n+1列的值均为 1。
计算机软件基础方位 行增量 列增量东 (0) 0 1
南 (1) 1 0
西 (2) 0?1
北 (3)?1 0
move =
0 1-
1- 1
0 1
1 0
走步增量数组 move
计算机软件基础
1,置当前位置的初始值为迷宫入口处,即
maz[1,1]处；
2,探测从当前位置向东 (k=0)开始,按 k值递增顺序依次探测各方位；
3,若所探测位置的 maz及 mark值均为 0,则进入该位置,并记下原位置的行,列坐标及进入该位置的方位 （ k的值 ）,即将这三个值入栈；
算法的基本步骤：
计算机软件基础
4,重复执行步骤 2和步骤 3；
5,若探测各方向均无通路,则从所在位置沿原路后退一步,即执行出栈操作,并改变探测方位 （ k的值 ）,再重复执行步骤 2和步骤 3，
寻找其它通路；
6．重复步骤 2到 5，直到走到迷宫出口（找到通路）或退回迷宫入口（无通路）。
3.1 数组
3.2 树
3.3 图目录计算机软件基础计算机软件基础
3,1 多维数组一．多维数组的定义二维以上的数组 。
注意,数组（ array） 在高级语言中是作为一种数据类型介绍的，而在本节中数组是作为一种常用数据结构来介绍的 。
计算机软件基础二,数组的逻辑结构 （ 以二维数组为例）
分析,二维数组中的每一个元素既受到行关系的制约，又受到列关系的制约。
若只考虑其中的一个关系，则对于任意元素，直接前驱和直接后继都是唯一的，
即行、列关系都是线性的。
结论,多维数组可看成是线性表的推广，
其逻辑关系是非线性的，实质上是多个线性关系的组合。
计算机软件基础三．多维数组的存储结构采用顺序存储结构实现 。
原因,多维数组一经定义，其元素个数就固定不变。
顺序存储的次序：
行优先,PASCAL,C语言列优先,FORTRAN语言
计算机软件基础四．矩阵的存储方法
1.普通矩阵的存储方法：
采用相应的二维数组实现 。
2.特殊矩阵的存储方法：
研究对象（两类特殊矩阵）
三角矩阵和稀疏矩阵采用压缩存储的方法实现 。
思考：两类特殊矩阵的共同特点是什么？
计算机软件基础
（ 1）三角矩阵的压缩存储分析,三角矩阵中非 0元素的分布有规律。
结论,可按照一定的顺序依次将三角矩阵中所有非 0元素存储在连续的存储空间中。
可行性,非 0元素在存储空间中的存放位置 k与其在原矩阵中的行、列位置间存在着一一对应的关系。
计算机软件基础例如：对下三角矩阵 A按行优先顺序对其进行压缩存储。
A =
nnn3n2n1
333231
2221
11
a,,,a a a
,,,,,,,,,,,,
a a a
a a
a
a11 a21 a22 a31 a32 a33 …,…,aij …,…,an1 an2 an3 …,…,ann
0 1 2 3 4 5 …,…,k …,…,m m+1 m+2 …,…,
m+n
计算机软件基础思考,
矩阵中第 i行第 j列的元素 aij存放在一维数组的哪个位置？
k=?
k= i? ( i - 1) / 2 + j-1
计算机软件基础
（ 2）稀疏矩阵的压缩存储分析,稀疏矩阵中非 0元素的分布 无 规律。
结论,可按照一定的顺序依次将稀疏矩阵中所有非 0元素存储在连续的存储空间中，
但必须在存储非 0元素值的同时设法记下其在矩阵中的位置。
可行的方法之一,三元组法存放每个非 0元素的值及其在原矩阵中的行、列位置三项信息。
计算机软件基础例如：对稀疏矩阵 A按行优先顺序对其采用三元组法进行压缩存储。
0 0 0 0 4 0
0 0 6- 0 0 0
0 0 0 0 0 2
0 1 0 3 0 0
A=
计算机软件基础行号 列号 元素值
4 6 5
1 3 3
1 5 1
2 1 2
3 4?6
4 2 4
结果：
注意：
通常可增加一个三元组，用于存放矩阵的整体信息！
计算机软件基础五,数组的应用迷宫问题
难点：
1,迷宫的表示（数字化）
2,回溯的实现（回退）
3,试探方向的控制
计算机软件基础
1.使用了一个 m行 n列的矩阵 maz表示迷宫，其中每个元素 maz[i,j]表示迷宫中的一个位置，其值为 1表示“此路不通”；其值为 0表示“可以通过”。
2.使用一个栈将所有走过的位置及进入该位置的方向记录下来 。 为了防止走重复的路，使用一个 mark矩阵存放每个位置是否走过的标志。
3.将方向数字化，并使用一个走步增量数组
move（ 二维数组）来描述向不同方向走步时将引起的 i和 j的增量。
解决办法：
计算机软件基础入口 0 0 0 0 0 1 1 0 0 0 0
1 0 0 0 1 1 0 1 1 1 1
0 1 1 0 0 0 0 1 1 1 1
1 1 0 0 1 1 1 0 1 1 0
1 1 0 1 0 0 1 0 1 0 1
0 0 0 0 0 1 1 0 0 1 1
0 1 0 1 0 0 0 0 0 1 1
0 0 1 1 1 0 1 1 0 0 0
1 0 0 0 0 0 1 1 0 1 1
1 0 0 1 1 0 0 0 0 1 1
1 1 1 1 0 1 0 1 0 0 0 出口迷宫的数字化矩阵说明,为避免每次检测是否走到边缘，可把 m行 n列的迷宫矩阵扩大为
m+2行 n+2列,且令增加的 0行,0列、
m+1行,n+1列的值均为 1。
计算机软件基础方位 行增量 列增量东 (0) 0 1
南 (1) 1 0
西 (2) 0?1
北 (3)?1 0
move =
0 1-
1- 1
0 1
1 0
走步增量数组 move
计算机软件基础
1,置当前位置的初始值为迷宫入口处,即
maz[1,1]处；
2,探测从当前位置向东 (k=0)开始,按 k值递增顺序依次探测各方位；
3,若所探测位置的 maz及 mark值均为 0,则进入该位置,并记下原位置的行,列坐标及进入该位置的方位 （ k的值 ）,即将这三个值入栈；
算法的基本步骤：
计算机软件基础
4,重复执行步骤 2和步骤 3；
5,若探测各方向均无通路,则从所在位置沿原路后退一步,即执行出栈操作,并改变探测方位 （ k的值 ）,再重复执行步骤 2和步骤 3，
寻找其它通路；
6．重复步骤 2到 5，直到走到迷宫出口（找到通路）或退回迷宫入口（无通路）。
