文档介绍：国家级精品课程—《数据结构与算法》
张铭、赵海燕、王腾蛟、宋国杰、高军
.cn/pkujpk/course/sjjg/
北京大学信息科学与技术学院
“数据结构与算法”教学小组
本章主笔:张铭
版权所有,转载或翻印必究
第12章高级数据结构
主要内容
多维数组
广义表和存储管理
Trie结构和Patricia树
改进的二叉搜索树
多维数组
基本概念
数组的空间结构
数组的存储
数组的声明
用数组表示特殊矩阵
稀疏矩阵
基本概念
数组(Array)是数量和元素类型固定的有序序列
静态数组必须在定义它的时候指定其大小和类型
动态数组可以在程序运行才分配内存空间
基本概念(续)
多维数组(Multi-array)是向量的扩充
向量的向量就组成了多维数组
可以表示为:
ELEM A[c1..d1][c2..d2]…[cn..dn]
ci和di是各维下标的下界和上界。所以其元素个数为:
数组的空间结构
二维数组三维数组
d1[1..3],d2[1..5],d3[1..5]分别为3个维
数组的存储
内存是一维的,所以数组的存储也只能是一维的
以行为主序(也称为“行优先”)
以列为主序(也称为“列优先”)
Pascal的行优先存储
a11
a12
a13
a14
a15
…
a1n
am1
am2
am3
am4
am5
…
amn
a21
a22
a23
a24
a25
…
a2n
a31
a32
a33
a34
a35
…
a3n
a41
a42
a43
a44
a45
…
a4n
…
…
…
…
…
…
…
FORTRAN的列优先存储
am2
am3
am4
am5
…
amn
…
a2n
a32
a33
a34
a35
…
a3n
a42
a43
a44
a45
…
a4n
am1
a31
a41
…
…
…
…
…
…
…
a12
a13
a14
a15
…
a1n
a11
a22
a23
a24
a25
a21
next
C/C++、 Pascal行优先
先排最右的下标
从右向左
最后最左的下标
例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列: