南开大学数据结构课件4.ppt

第4章数组和矩阵
学习内容
多维数组:行主描述、列主描述
更强大的数组:类Array1D、Array2D
矩阵类:Matrix
特殊结构矩阵
稀疏矩阵
数组
抽象数据类型
抽象数据类型Array{
实例
形如(index,value)的数据对集合,其中任意两对数据的index值都各不相同
操作
Create():创建一个空的数组
Store(index,value):添加数据(index,value),并删除具有相同index值的数据对(若存在)
Retrieve(index):返回索引值为index的数据对
}

上个星期每天的高温(华氏度数):
high={(sunday, 82), (monday, 79), (tuesday, 85), (wednesday, 92), (thursday, 88), (friday, 89), (saturday,91)}
数据对:(日期名—索引,当天温度—值)
将monday的温度改为83:Store(monday, 83)
获得friday的温度:Retrieve(friday)
另一种描述:high={(0,82), (1,79), (2,85), (3,92), (4,88), (5,89), (6,91)}日期名数值
C++中的数组
索引(下标)形式:
[i1][i2][i3]...[ik]
ij——非负整数
k=1——一维数组,k=2——二维数组…
数组的声明
int score[u1][u2][u3]...[uk]
ui——ij的取值范围,0≤ij<uj,1≤j≤k。
数组最多可以容纳n=u1u2u3...uk个值
C++编译器预留sizeof(score)=n*sizeof(int)个字节
start~start+size(score)-1——连续空间
多维数组的保存方式
计算机内存——一维,多维数组?
多维数组元素start~start+size(score)-1
实现映射[i1][i2][i3]...[ik][0, n-1]map(i1, i2, i3, ..., ik)存储位置:start+map(i1, i2, i3, ..., ik)*sizeof(int)
一维数组:map(i1) = i1
多维数组的保存方式
二维数组就有些难度
第一维下标:行
第二维下标:列
到底按什么顺序来存储?
行主映射
行主映射:存储顺序为
第一行、第二行、…
每行内:位于第一列的那个元素、第二列、…
列主映射
列主映射:编号顺序为
第一列、第二列、…
每列内:位于第一行的那个元素、第二行