第五章数组和广义表 数组和广义表的定义 数组和广义表的基本运算 数组的存储结构 广义表的存储结构 5.1数组的概念 数 >数组:是一种线性数据结构,它是有 构限个相同类型数据元素的有序集合。 数组的数据元素是值和下标的偶对 对每个有定义的下标,都有一个相关 数连的值 a11812 ain n a21822…a2n 表 am1am2…amn
1 第五章 数组和广义表 数组和广义表的定义 数组和广义表的基本运算 数组的存储结构 广义表的存储结构 数 据 结 构 之 数 组 和 广 义 表 2 5. 1 数组的概念 ¾ 数组：是一种线性数据结构，它是有 限个相同类型数据元素的有序集合。 ¾ 数组的数据元素是值和下标的偶对， 对每个有定义的下标，都有一个相关 连的值。 a11 a12 … a1n Amxn＝ a21 a22 … a2n · · · · am1 am2 … amn
据>基本操作:两种主要的运算 (1)给定一组下标,读取相应的数据 元素; Getvalue(a, &e,i,j) (2)修改元素值。 Change value(A,e,i,j) >数组一般不作插入和删除操作。 5.2数组的顺序表示和实现 /撂逻辑多维到存储一维的映射,即寻找多维下标和 一维下标的关系 构>存储方式 >行序为主序的存储方式 之数组和广义表 以列序为主序的存储方式 Alll 以行为主 以列为主
2 数 据 结 构 之 数 组 和 广 义 表 3 ¾ 基本操作：两种主要的运算： （1）给定一组下标，读取相应的数据 元素； GetValue( A, &e, i, j ) （2）修改元素值。 ChangeValue(A, e , i , j ) ¾ 数组一般不作插入和删除操作。 数 据 结 构 之 数 组 和 广 义 表 4 5. 2 数组的顺序表示和实现 ¾ 逻辑多维到存储一维的映射，即寻找多维下标和 一维下标的关系。 ¾ 存储方式 ¾ 行序为主序的存储方式 ¾ 以列序为主序的存储方式 a11 : a1n a21 : a2n : amn A1[1] a11 : am1 a12 : am2 : amn A1[1] 以行为主 以列为主
数组元素的存储位置是其下标的线 据结构之数组和广义表 性函数,存取数组中任一元素的时 间相等,所以,数组是随机的存储 结构。 计算一维下标 >以二维数组Am为例,计算数组元素 数据结构之数组和广义 A[ij的存储空间下标w 以行序为主序的存储方式 以列序为主序的存储方式 w=jn十i >有三维数组A|345计算数组元素 A[2l33的存储空间下标:以行序为主 N=2*(45)+3*5+3=58
3 数 据 结 构 之 数 组 和 广 义 表 5 ¾ 数组元素的存储位置是其下标的线 性函数，存取数组中任一元素的时 间相等，所以，数组是随机的存储 结构。 数 据 结 构 之 数 组 和 广 义 表 6 ¾ 计算一维下标 ¾ 以二维数组A[n][m]为例，计算数组元素 A[i][j] 的存储空间下标 w: ¾ 以行序为主序的存储方式 w=i*m+j ¾ 以列序为主序的存储方式 w= j*n+i ¾ 有三维数组A[3][4][5],计算数组元素 A[2][3][3]的存储空间下标：以行序为主 w=2*(4*5)+3*5+3=58
数组的顺序存储表示和实现 数 typedef struct{ 据结构 Elem Type*base int dim nt* bounds;/数组维界基址 int* constants;/数组映象函数(Page93的式(5-2) 数Aray 常量C基址,Ca=L=1,C1=bi*C; 组 第一维界第二维界第三维界第四维界 bounds2(块)5(页)3(行)4(列) constants5*12=603*4=124*1=4 cl=b2*c2c2=b3*c3c3=b4*c4c4=1 数组的算法实现 数# include <stdarg. h> /* ypedef void *va list; #define va start(ap, parmN 2 #define va_arg(ap, type)(*(type "(ap)++) #define va end(ap) 数 fe va_list ap 和 va start(ap,dim:使ap指向dim后面的实参表; 又 va arg( (ap, int):取出ap所指向的int型数据后, 表 ap++。 va end(ap:空语句
4 数 据 结 构 之 数 组 和 广 义 表 7 ¾ 数组的顺序存储表示和实现 typedef struct{ ElemType *base; int dim ; int *bounds ; //数组维界基址 int *constants ;//数组映象函数(Page93的式(5-2)) }Array; 常量Ci基址，Cn=L=1,Ci -1 =bi*Ci; 第一维界 第二维界 第三维界 第四维界 bounds 2 (块) 5 (页) 3 (行) 4 (列) constants 5*12=60 3*4=12 4*1=4 1 c1=b2*c2 c2=b3*c3 c3=b4*c4 c4=1 数 据 结 构 之 数 组 和 广 义 表 8 ¾ 数组的算法实现 #include <stdarg.h> typedef void *va_list; #define va_start(ap, parmN) (ap = ...) #define va_arg(ap, type) (*((type *)(ap))++) #define va_end(ap) va_list ap; va_start(ap,dim):使ap 指向dim后面的实参表； va_arg(ap,int):取出ap所指向的int型数据后， ap++。 va_end(ap):空语句
数main( f Array A; int dim 据结构之数组和广义表 InitArray(A, dim, 2, 5, 3,4); Status InitArray(Array &A, int dim, .i 数if(dim<l‖lim>8) return ERROR 据A.dim=dim; A bounds=(int *)malloc( dim*sizeof(int) if(!A bounds)exit(OVERFLOW); elemtotall 数 a start(ap,dim); tr for(i=0; i<dim i++) A bounds]va arg(ap, int ) x if(A bounds<l)return UNDERFLOW; A elemtotal*=A bounds il:) va end(ap)
5 数 据 结 构 之 数 组 和 广 义 表 9 main( ) { Array A ; int dim=4; InitArray( A , dim , 2 , 5 , 3 , 4 ); …… } 数 据 结 构 之 数 组 和 广 义 表 10 Status InitArray(Array &A , int dim , ...){ if (dim<1 || dim>8 ) return ERROR ; A.dim=dim; A.bounds=(int*)malloc(dim*sizeof(int)); if( !A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); for(i=0 ; i<dim ; i++){ A.bounds[i]=va_arg(ap , int ); if(A.bounds[i]<1) return UNDERFLOW; elemtotal*=A.bounds[i]; } va_end(ap) ;