一维数组n个元素.PPT

第5章 数组 5.1 数组的基本概念 (１)、一维数组（n个元素）中任一元素ai的内存单元地址 　　 Loc(ai)=LOC(a０)+i*k (0≤i n) (２)、一个m行n列的二维数组 　　LOC(aij)=LOC(a00)+(i*n+j)*k (0≤im，0≤jn) 注：C语言中数组元素采用行主序的存放方法，即行优先顺序。 5.2 动态数组 5.3 特殊矩阵 5.4 稀疏矩阵 2. 三元组顺序表 指用顺序表存储的三元组线性表。 typedef struct { int i; int j; elemtype d; } DataType; typedef struct { int md; int nd; int td; }TriType; 作业 1)习题5-1，5-2 ，5-3 ，5-4 习题5-10，5-11 * * 主要知识点 数组的基本概念 动态数组 特殊矩阵 稀疏矩阵 1.数组的定义 数组是n(n＞1)个相同数据类型的数据元素a0,a1,a2,...,an-1构成的占用一块地址连续的内存单元的有限序列。 数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组的下标。 相同之处是它们都是若干个相同数据类型的数据元素a0,a1,a2,...,a0-1构成的有限序列。 不同之处是： （1）数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求； （2）线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组； （3）数组的操作主要是向某个下标的数组元素中存数据和取某个下标的数组元素，这和线性表的插入、删除操作不同。 数组符合线性结构的定义。数组和线性表相比， 线性结构（包括线性表、堆栈、队列、串）的顺序存储结构实际就是使用数组来存储。可见，数组是其他数据结构实现顺序存储结构的基础，是软件设计中最基础的数据结构。 2.数组的实现机制 a０的内存单元地址 每个元素所需的字节个数 每个元素所需的字节个数 a０0的内存单元地址 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.数组抽象数据类型 数据集合： 数组的数据集合可以表示为a0, a1, a2, ..., an-1，每个数据元素的数据类型为抽象数据元素类型DataType。 操作集合： (1)求数组元素个数ArrayLength(D) (2)取数组元素Get(D, i) (3)存数组元素Storage(D, i, x) 例如， int a[10]; a[3] = a[4]; //赋值号右边的a[4]是取操作，取值 //赋值号左边的a[3]是存操作，取地址 数组有静态存储结构的数组和动态存储结构的数组两种，它们的区别在于： 静态数组在定义时就必须给出数组个数； 动态数组是在具体申请存储单元空间时才给出数组元素的个数。 例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 **a, int row) { int i; for(i = 0; i row; i++) free(a[i]);