第5章数组 (数组的基本概念 动态数组 知特殊矩阵 识 点稀疏矩阵
第5章 数组 主 要 知 识 点 数组的基本概念 动态数组 特殊矩阵 稀疏矩阵
51数组的基本概念 1数组的定义 数组是n(n>1)个相同数据类型的数据元素aona1al2…,an1 构成的占用一块地址连续的内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示 数组元素的位置通常称作数组的下标
5.1 数组的基本概念 1.数组的定义 数组是n(n＞1)个相同数据类型的数据元素a0 ,a1 ,a2 ,...,an-1 构成的占用一块地址连续的内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示， 数组元素的位置通常称作数组的下标
数组符合线性结构的定义。数组和线性表相比 相同之处是它们都是若干个相同数据类型的数据元素 aoa1a2x…,aol构成的有限序列。 不同之处是: (1)数组要求其元素占用一块地址连续的内存单元空间,而 线性表无此要求 (2)线性表的元素是逻辑意义上不可再分的元素,而数组中 的每个元素还可以是一个数组 (3)数组的操作主要是向某个下标的数组元素中存数据和取 某个下标的数组元素,这和线性表的插入、删除操作不同。 线性结构(包括线性表、堆栈、队列、串)的顺序存储结构 实际就是使用数组来存储。可见,数组是其他数据结构实现顺 序存储结构的基础,是软件设计中最基础的数据结构
相同之处是它们都是若干个相同数据类型的数据元素 a0 ,a1 ,a2 ,...,a0-1构成的有限序列。 不同之处是： （1）数组要求其元素占用一块地址连续的内存单元空间，而 线性表无此要求； （2）线性表的元素是逻辑意义上不可再分的元素，而数组中 的每个元素还可以是一个数组； （3）数组的操作主要是向某个下标的数组元素中存数据和取 某个下标的数组元素，这和线性表的插入、删除操作不同。 数组符合线性结构的定义。数组和线性表相比， 线性结构（包括线性表、堆栈、队列、串）的顺序存储结构 实际就是使用数组来存储。可见，数组是其他数据结构实现顺 序存储结构的基础，是软件设计中最基础的数据结构
2数组的实现机制 (1)、一维数组(n个元素)中任一元素a的内存单元地址 Loc(a)=Loc(ao)+迷k(0≤i<n) ao的内存单元地址 每个元素所需的字节个数 (2)、一个n行列的二维数组 Loc(a)=Loc(0)+(n+小米k(0≤i<m,0≤j<n ao0的内存单元地址 每个元素所需的字节个数 注:c语言中数组元素采用行主序的存放方法,即行优先顺序
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) 注：C语言中数组元素采用行主序的存放方法，即行优先顺序。 a０的内存单元地址 每个元素所需的字节个数 a 每个元素所需的字节个数 ０0的内存单元地址
a0.0a0.1 a0,n-1 a1,0a1,1…a1,n-1 mn am-1,0am-1,1…alm-1,n-1 个mxn的二维数组可以看成是m行的一维数 组,或者列的一维数组
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 = 一个m×n的二维数组可以看成是m行的一维数 组，或者n列的一维数组