第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列的一维数组
3数组抽象数据类型 数据集合: 数组的数据集合可以表示为an,a1,a2,…,an1,每个数据元素的 数据类型为抽象数据元素类型 Datatype 操作集合: (1)求数组元素个数 Arraylength(D) (2)取数组元素Ge(D,i 3)存数组元素 Storage(D,,x)
3.数组抽象数据类型 数据集合： 数组的数据集合可以表示为a0 , a1 , a2 , ..., an-1，每个数据元素的 数据类型为抽象数据元素类型DataType。 操作集合： (1)求数组元素个数ArrayLength(D) (2)取数组元素Get(D, i) (3)存数组元素Storage(D, i, x)
例如,inta[10; a|3]=a|4;/赋值号右边的a4是取操作 取值 赋值号左边的a3是存操作 取地址
例如， int a[10]; a[3] = a[4]; //赋值号右边的a[4]是取操作， 取值 //赋值号左边的a[3]是存操作， 取地址
52动态数组 数组有静态存储结构的数组和动态存储结构的数组两种,它们 的区别在于: 静态数组在定义时就必须给出数组个数; 动态数组是在具体申请存储单元空间时才给出数组元素的个数
5.2 动态数组 数组有静态存储结构的数组和动态存储结构的数组两种，它们 的区别在于： 静态数组在定义时就必须给出数组个数； 动态数组是在具体申请存储单元空间时才给出数组元素的个数
例5-2定义有3行、4列整数类型的二维数组a,先逐行分 别给数组元素赋数据1,2,…12,然后显示数组中的数 值。要求分别把申请二维动态数组的过程和释放二维动态 数组的过程编写成函数。 int *x Make2Darray(int row, int col) t int**a, i; a =(int**)malloc(row sizeof(int *)); for(i=0;i< row; i++) a=(int *)malloc(col* sizeof(int)); return a
例5-2 定义有3行、4列整数类型的二维数组a，先逐行分 别给数组元素赋数据1，2，...，12，然后显示数组中的数 值。要求分别把申请二维动态数组的过程和释放二维动态 数组的过程编写成函数。 int **Make2DArray(int row, int col) { int **a, i; a = (int **)malloc(row * sizeof(int *)); for (i = 0; i < row; i++) a[i] = (int *)malloc(col * sizeof(int)); return a; }
void Diliver2DArray(int **, int row) t int fori=0;i #include #include include“ Array. h
void Diliver2DArray(int **a, int row) { int i; for(i = 0; i #include #include #include “Array.h