第4章类数组、集合和矩阵4.1 数组4.2特殊矩阵4.3稀疏矩阵4.4集合
第4章 数组、集合和矩阵 4.1 数组 4.2 特殊矩阵 4.3 稀疏矩阵 4.4 集合
4.1数组4.1.1数组的定义数组是n（n≥1）个相同数据类型的数据元素a0,al,a2.an-1构成的占用一块地址连续的内存单元的有限集合
4.1 数组 4.1.1 数组的定义 数组是n（n≥1）个相同数据类型的数据元素 a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的 有限集合
问题：数组与线性表的区别与联系相同之处：它们都是若干个相同数据类型的数据元素ao,a1,a2，…，an-1构成的有限序列。不同之处：（1）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求：(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组：（3）数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操作不同
问题：数组与线性表的区别与联系 相同之处： 它们都是若干个相同数据类型的数据元素a0,a1,a2,.，an-1 构成的有限序列。 不同之处： (1)数组要求其元素占用一块地址连续的内存单元空间，而 线性表无此要求； (2)线性表的元素是逻辑意义上不可再分的元素，而数组中 的每个元素还可以是一个数组； (3)数组的操作主要是向某个下标的数组元素中存放数据和 取某个下标的数组元素，这与线性表的插入和删除操作不同
数组的实现机制4.1.21、一维数组（n个元素）中任一元素a；的内存单元地址LOC(ai)=LOC(a。)+i*k(0≤i<n)a的内存单元地址每个元素所需的字节个数2、一个m行n列的二维数组LOC(ai)=LOC(aoo)+(i*n+i)*k(0<i<m , 0j<n)aon的内存单元地址每个元素所需的字节个数ao,o ao,1ao,n-1一个m×n的二维数组可以a1,0 a1,1a1,n-1A看成是m行的一维数组，或·者n列的一维数组am-1,0 am-1,1 ... am-1,n-1
4.1.2 数组的实现机制 １、一维数组（n个元素）中任一元素ai的内存单元地址 LOC(ai)=LOC(a０)+i*k (0≤i <n) ２、一个m行n列的二维数组 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m， 0≤j<n) a０的内存单元地址 每个元素所需的字节个数 a０0的内存单元地址 每个元素所需的字节个数 一个m×n的二维数组可以 看成是m行的一维数组，或 者n列的一维数组。 a0,0 a0,1 . a0,n-1 a1,0 a1,1 . a1,n-1 . . . . am-1,0 am-1,1 . am-1,n-1 Amn =
下标下标1100241第1行1第1列72322323434565518第2行44第2列Q5658736687第3行76第3列8989(b)(c)(a）二维数组的逻辑结构行优先顺序存储结构列优先顺序存储结构二维数组的顺序存储结构
1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 (b) 行优先顺序存储结构 (c) 列优先顺序存储结构 1 2 3 4 5 6 7 8 9 第1行 第2行 第3行 第1列 第2列 第3列 (a) 二维数组的逻辑结构 下标 0 2 8 7 6 5 4 3 1 下标 0 2 8 7 6 5 4 3 1 二维数组的顺序存储结构