湖北工业大学：《数据结构》第5章 数组

第5章数组 51数组 52动态数组 53特殊矩阵的压缩存储 54稀疏矩阵的压缩存储

1 第5章 数组 5.1 数组 5.2 动态数组 5.3 特殊矩阵的压缩存储 5.4 稀疏矩阵的压缩存储

5.1数组 数组的定义 数组:它是n(n>1个相同数据类型的数据元素a,a1a2yan1 构成的占用一块地址连续的内存单元的有限序列 数组的下标:数组元素的位置。 注意: (1)C语言的数组定义下标从0开始 (2)数组的处理相比其它复杂的结构要简单。 ①数组中各元素具有统一的类型; ②数组元素的下标一般具有固定的上界和下界,即数组一旦被 定义,它的维数和维界就不再改变。 ③数组的基本操作比较简单,除了结构的初始化和销毁之外, 只有存取元素和修改元素值的操作。 (3)一个二维数组可以看作每个数据元素是一个一维数组的一维数 组。二维数组是两维的,内存单元是一维的,存在向内存存储时 二维数组中数据元素的存储方法问题,C语言采用以行序为主序的 方法存储

2 5.1 数组 一、数组的定义 数组：它是n（n>1)个相同数据类型的数据元素a0,a1,a2,…an-1 构成的占用一块地址连续的内存单元的有限序列。 数组的下标：数组元素的位置。 注意： (1)C语言的数组定义下标从0开始。 (2) 数组的处理相比其它复杂的结构要简单。 ① 数组中各元素具有统一的类型； ② 数组元素的下标一般具有固定的上界和下界，即数组一旦被 定义，它的维数和维界就不再改变。 ③数组的基本操作比较简单，除了结构的初始化和销毁之外， 只有存取元素和修改元素值的操作。 (3)一个二维数组可以看作每个数据元素是一个一维数组的一维数 组。二维数组是两维的，内存单元是一维的，存在向内存存储时 二维数组中数据元素的存储方法问题，C语言采用以行序为主序的 方法存储

问题:数组与线性表的区别与联系 相同之处: 它们都是若干个相同数据类型的数据元素ao,a1,a2,…,an-1 构成的有限序列 不同之处: (1)数组要求其元素占用一块地址连续的内存单元空间,而 线性表无此要求; (2)线性表的元素是逻辑意义上不可再分的元素,而数组中 的每个元素还可以是一个数组; (3)数组的操作主要是向某个下标的数组元素中存放数据和 取某个下标的数组元素,这与线性表的插入和删除操作不同

3 问题：数组与线性表的区别与联系 相同之处： 它们都是若干个相同数据类型的数据元素a0,a1,a2,…，an-1 构成的有限序列。 不同之处： (1)数组要求其元素占用一块地址连续的内存单元空间，而 线性表无此要求； (2)线性表的元素是逻辑意义上不可再分的元素，而数组中 的每个元素还可以是一个数组； (3)数组的操作主要是向某个下标的数组元素中存放数据和 取某个下标的数组元素，这与线性表的插入和删除操作不同

二、数组的实现机制 1、一维数组(n个元素)中任一元素a的内存单元地址 LOC(ai=LoC(ao)+i*k (0si<n) 每个元素所需的字节个数 0 的内存单元地址 2、一个m行n列的二维数组 LOC(ai=LOC(a00)+(i*n+j)*k(0<K<m 0<<n) a0的内存单元地址 每个元素所需的字节个数 注:C语言中数组元素采用行主序的存放方法,即行优先顺序。 a 0,0a0,1 0,n-1 a1,0a1,1 1,n-1 个mxn的二维数组可以 mn 看成是m行的一维数组,或 am-1,0am-1,1…am-1,n-1 者n列的一维数组

4 二、数组的实现机制 １、一维数组（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的内存单元地址 一个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 =

注:只要知道以下三要素便可随时求出任一元素的地址(意 义:数组中的任一元素可随机存取) ①开始结点的存放地址(即基地址); ②维数和每维的上、下界; ③每个数组元素所占用的单元数 例1〖软考题〗 二维数组A,行下标的范围是1到6,列下标的范围是0到 7,每个数组元素用相的6个字节存储,存储器按字节编址。那么,这个 数组的体积是288个字节。 答: Volume=m*n米=(6-1+1)*(7-0+1)米6=48*6=288 例2设数组a[0.60,0…70]的基地址为2048,每个元素占2个存储单元, 若以行序为主序顺序存储,则元素a[32,58】的存储地址 为 6644 答:根据行优先公式L0C(a1)L0C(a0).+(it+)*(0≤i<m,0≤jn) 得:L0C(a325)=2048+(32*70+58)*2=6644

5 注：只要知道以下三要素便可随时求出任一元素的地址（意 义：数组中的任一元素可随机存取） ①开始结点的存放地址（即基地址）； ②维数和每维的上、下界； ③每个数组元素所占用的单元数 例１〖软考题〗：一个二维数组A，行下标的范围是1到6，列下标的范围是0到 7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个 数组的体积是 个字节。 答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 例２ 设数组a[０…60, ０…70]的基地址为2048，每个元素占2个存储单元， 若以行序为主序顺序存储，则元素a[32,58]的存储地址 为 。 答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0≤i<m，0≤j<n) 得：LOC(a32,58)=2048+(32*70+58)*2＝6644 288 6644

数组抽象数据类型 数据集合:{a,a,;a2yan1}每个数据类型为抽象数据元素类型 操作集合:(1)求数组元素个数 ArrayLength(D) (2)存数组元素 Storage(D,,x) (3)取数组元素Get(Di1x)

6 三、数组抽象数据类型 数据集合：｛a0,a1,a2,…an-1 } 每个数据类型为抽象数据元素类型 操作集合:(1)求数组元素个数 ArrayLength(D) (2)存数组元素 Storage(D,i,x) (3)取数组元素 Get(D,i,x)

5.2动态数组 动态数组的设计方法 1、动态数组的概念 动态数组:它是在需要存储单元空间时才给出数组的具体个 数 C语言提供的支持函数有 malloc()、 calloc(、 freed 例:编写一个定义和使用二维3行4列动态数组的一个完整程序

7 5.2 动态数组 一、动态数组的设计方法 1、动态数组的概念 动态数组：它是在需要存储单元空间时才给出数组的具体个 数。 C语言提供的支持函数有： malloc( )、calloc( )、free( ) 例：编写一个定义和使用二维3行4列动态数组的一个完整程序

#inc lude #inc lude #include vold main(vo1 d t int 1, j, row=3, co1=4, **a a=(int*米)ma110c(r0W米 sizeof(in米); for(i=0;i<row; i++) ali]=(int *)malloc(col*sizeof (int)) for(i=0;i<row i++) for(j=0; j<col; j++) a printf( %d ali]lil); printf(“\n”);}

8 #include #include #include void main(void) { int i,j,row=3，col=4,**a; a=(int **) malloc(row*sizeof(int *))； for (i=0;i<row;i++) a[i]=(int *)malloc(col*sizeof(int)); for(i=0;i<row;i++) { for(j=0;j<col;j++) { a[i][j]=i+j; printf("%d ",a[i][j]); } printf(“\n”);} }

例:编写一个使用两维动态数组的函数。 int * Make2DArray (int row, int co1) int akka. 1 a=(int **)malloc (rowksizeof (int *) for (i=0 i<row; i++) ali]=(int *)malloc(col*sizeof (int)) return a

9 例：编写一个使用两维动态数组的函数。 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; }

#include #include # include/*函数已经定义,同前米/ void main(void) int i,j, c, row=3, col=4, **a; a=Make2DArray(row, col); for(i=0; i<row; i++) i for(j=0; j<co; j ++ anll=itj; printi(%d”,a[jljD);} printf(“Ⅶn”);

10 #include #include #include /*函数已经定义，同前*/ void main(void) { int i,j,c,row=3,col=4,**a; a=Make2DArray(row, col); for(i=0;i<row;i++) { for(j=0;j<col;j++) { a[i][j]=i+j; printf(“%d”,a[i][j]);} printf(“\n”); } }