第五章数组 一维数组 n多维数组 特殊矩阵的压缩存储
◼ 一维数组 ◼ 多维数组 ◼ 特殊矩阵的压缩存储
维数组 定义 相同类型的数据元素的集合。 一维数组的示例 0123456789 35274918605477834102 与顺序表的不同在于数组可以按元 素的下标直接存储和访问数组元素
一维数组 ◼ 定义 相同类型的数据元素的集合。 ◼ 一维数组的示例 ◼ 与顺序表的不同在于数组可以按元 素的下标直接存储和访问数组元素。 35 27 49 18 60 54 77 83 41 02 0 1 2 3 4 5 6 7 8 9
数组的定义和初始化 main(i int al[3]={3,5,7},*elem; for(inti=0;1<3;1++) printf(d3,alij,n”);/静态数组 elem =al; ior(inti=0;1<3;i++){ printf(%d, elem,n);1动态数组 elem++
数组的定义和初始化 main ( ) { int a1[3] = { 3, 5, 7 }, *elem; for ( int i = 0; i < 3; i++ ) printf ( “%d”, a1[i], “\n” ); //静态数组 elem = a1; for ( int i = 0; i < 3; i++ ) { printf ( “%d”, *elem, “\n” ); //动态数组 elem++; } }
数组溢出的处理 维数组的问题在于:如果其空间大小已 经分配,一旦空间占满,再加入新元素将 产生溢出。 已知一维数组的大小为 MaxSize,其定义 和分配如下: typedef int data Type; DataType s data= Data Type *)malloc MaxSize sizeof Data Type )) a现已产生溢出,那么处理溢出的方法为
数组溢出的处理 ◼ 一维数组的问题在于：如果其空间大小已 经分配，一旦空间占满，再加入新元素将 产生溢出。 ◼ 已知一维数组的大小为MaxSize，其定义 和分配如下： typedef int dataType; DataType * data = (DataType *) malloc ( MaxSize * sizeof ( DataType ) ); ◼ 现已产生溢出，那么处理溢出的方法为：
const int Newsize =100. Data Type newArray new Data Type NewSize; if( newArray - NULL) { stderr(“存储分配错Ⅷn”);exit(1);} int n=( NewSize < MaxSize)? NewSize: MaxSize Data Type *srcptr=data; Data Type *destptr=newArray; while(n--*destptr++=* srcptr++ delete data; data=newArrays
const int NewSize = 100; DataType * newArray = new DataType[NewSize]; if ( newArray == NULL ) { stderr (“存储分配错\n” ); exit(1); } int n = ( NewSize <= MaxSize ) ? NewSize : MaxSize; DataType *srcptr = data; DataType *destptr = newArray; while ( n-- ) * destptr++ = * srcptr++; delete [ ] data; data = newArray;
多维数组 多维数组是一维数组的推广 多维数组是一种非线性结构。其特 点是每一个数据元素可以有多个直 接前驱和多个直接后继 数组元素的下标一般具有固定的下 界和上界,因此它比其他复杂的非 线性结构简单
多维数组 ◼ 多维数组是一维数组的推广 ◼ 多维数组是一种非线性结构。其特 点是每一个数据元素可以有多个直 接前驱和多个直接后继。 ◼ 数组元素的下标一般具有固定的下 界和上界，因此它比其他复杂的非 线性结构简单
二维数组 三维数组 m1=5m2=4m3=6 m3 a[2][2] 3×4×6 2×6 2 m1 a[3][22] 行向量下标i 页向量下标i 列向量下标j行向量下标j 列向量下标k
二维数组 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k
二维数组 a0[0a01[1 a0[m-1 10]a1[1 1m-1 =a20J(2 a2[m-1 an-10a[n-11]…aln-1l[m-1 行优先存放: 设数组开始存放位置LOC(0,0)=a,每 个元素占用d个存储单元 LOC (,k=a+(*m+k)*d
− − − − − − − = [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] 1 0 1 1 1 1 2 0 2 1 2 1 1 0 1 1 1 1 0 0 0 1 0 1 a n a n a n m a a a m a a a m a a a m a ◼ 二维数组 行优先存放： 设数组开始存放位置LOC( 0, 0 ) = a, 每 个元素占用 d 个存储单元 LOC ( j, k ) = a + ( j * m + k ) * d
a010]a0[1 n0m-1 a[10]a[1[1 n[1[m-1 L=a(2]|0]a21 2][m-1 a{n-110]a[n-1[1…an-1m-1 列优先存放 设数组开始存放位置LOC(0,0)=a,每 个元素占用d个存储单元 LOC (,k)=a+(k*n+i)*d
− − − − − − − = [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] [ ][ ] 1 0 1 1 1 1 2 0 2 1 2 1 1 0 1 1 1 1 0 0 0 1 0 1 a n a n a n m a a a m a a a m a a a m a 列优先存放： 设数组开始存放位置LOC( 0, 0 ) = a, 每 个元素占用 d 个存储单元 LOC ( j, k ) = a + ( k * n + j ) * d
三维数组 G各维元素个数为m,m2,m3 下标为i,23的数组元素的存储地址: (按页行例存放) LOC (L i,)=a+ (i*,* m3+i2"m3+i3)d 前i页总第页的第行前 元素个数前2行总列元素个数 元素个数
◼ 三维数组 各维元素个数为 m1 , m2 , m3 下标为 i1 , i2 , i3的数组元素的存储地址： （按页/行/列存放） LOC ( i1 , i2 , i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * d 前 i1 页总 元素个数 第 i1 页的 前 i2 行总 元素个数 第 i2 行前 i3 列元素个数