第五章 数组
?5.1 数组的定义
?5.2 数组的顺序表示和实现
?5.3 矩阵的压缩存储
? 5.3.1 特殊矩阵
? 5.3.2 稀疏矩阵
5.1 数组的定义
? 维数和维界
? 二维数组的类型定义,
? 等价于
? typedef ElemType Array1[n];
? typedef Array1 Array2[m];
? typedef ElemType Array2[m][n];
? Array2 A;
? 二维的数组 = 定长的线性表
? a11 a12 a13,.,a1n
? a21 a22 a23,.,a2n
? Amxn=,.....
? am1 am2 am3,.,amn
? Amxn=
? ((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(am1,am2,am3,...amn))
数组的抽象数据类型
? ADT Array {
? 数据对象,D = {aj1j2...jn |
? n(>0)称为数组的维数,bi是数组第 i维的长度,
? ji是数组元素的第 i维下标,aj1j2...jn?Elemset}
? 数据关系,R={R1,R2,.,Rn}
? Ri = {＜ aj1...ji...jn,aj1...ji+1...jn ＞ |0 ? jk? bk-1,1 ? k ? n,
? aj1...ji...jn,aj1...ji+1...jn ?D}。
? 基本操作：
? InitArray(&A,n,bound1,bound2,...,boundn);
? DestroyArray (&A);
? Value(A,&e,index1,index2,...,indexn);
? Assign(&A,e,index1,index2,...,indexn)
? }ADT Array
5.2 数组的顺序表示和实现
? 除了初始化和销毁之外,
? 数组一般只有存取操作和修改元素值的操作,
? 通常不作删除和插入,
? 行序为主序,(C语言,PASCAL,BASIC等 )
? Amxn=
? (a11,a12,a13,...a1n,a21,a22,a23,...a2n,...am1,am2,am3,...amn)
? LOC[1,1] 为基地址,
? LOC[i,j] = LOC[1,1] + (n*(i-1)+j-1)*L
? (1<=i<=m,1<=j<=n,每个数据元素占 L个存储单元 )
例 5.1,若 L=2,LOC[1,1] = 1000
? LOC[3,4] = LOC[1,1] + (5*(3-1)+4-1)*L
? = 1000 + 13 * 2
? = 1026
? LOC[0,0] 为基地址,
? LOC[i,j] = LOC[0,0] + (n*i+j)*L
? (0<=i<m,0<=j<n,每个数据元素占 L个存储单元 )
? LOC[i,j,k] = LOC[0,0,0] + (n*h*i+ h*j + k)*L
? (0<=i<m,0<=j<n,0<=k<h,每个数据元素占 L个存储单元 )
a11 a12 a13 a14 a15
A4x5 = a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
一般 n维数组的列主元存储地址计算公式
? b1,b2,...,bn是 n维的维界,数组元素 A(j1,j2,...,jn)的存储位置为
? LOC[j1,j2,...jn]= LOC[0,0,...,0] + (b2?b3?...?bn?j1
? + b3?...?bn?j2
? +,.....
? + bn?jn-1
? + jn )?L
? n-1 n
? = LOC[0,0,...,0] + ( ? ji ? bk + jn)?L
? i=1 k=i+1
? 例, 在 C语言中,设 数组 A[5][6][7][8]的首地址为 2000,
? 每个元素占 2个字节 ; 求元素 A[3][4][5][4]的地址,
? LOC[3,4,5,4] = 2000 + (6*7*8*3 + 7*8*4 + 8*5 + 4)*2
? = 2000 + ( 336*3 + 56*4 + 8*5 + 1*4)*2
= 2000 + (1008 + 224 + 40 + 4)*2 = 4552
列序为主序, (FORTRAN)
? Amxn=
? ((a11,a21,a31,...am1),(a12,a22,a32,...am 2),...(a1n,a2n,a3n,...amn))
? LOC[1,1] 为基地址,
? LOC[i,j] = LOC[1,1] + (m*(j-1)+i-1)*L
? (1<=i<=m,1<=j<=n,每个数据元素占 L个存储单元 )
? 例 5.2,若 L=2,LOC[1,1] = 1000
? LOC[3,4] = LOC[1,1] + (4*(4-1)+3-1)*L
? = 1000 + 14 * 2 = 1028
? LOC[0,0] 为基地址,
? LOC[i,j] = LOC[0,0] + (m*j+i)*L
? (0<=i<=m,0<=j<=n,每个数据元素占 L个存储单元 )
? LOC[i,j,k] = LOC[0,0,0] + (m*((n*k)+j)+i) *L
a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
数组顺序存储的表示和实现
? InitArray(Array &A,int dim,...);
? // 若维数 dim和随后的维数合法,构造相应的数组,并返回 OK
? DestroyArray (Array &A);//销毁数组 A
? Value(Array A,ElemType &e,...);
? 若各下标不超界,则 e赋值为所指定的 A的元素值,并返回 OK
? Assign(Array &A,ElemType e,...)
? 若各下标不超界,则将 e的值赋给所指定的 A的元素,并返回 OK
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
#incluse <stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct {
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
? Status InitArray(Array &A,int dim,...)
? { va_list ap;
? if(dim<1 || dim > MAX_ARRAY_DIM) 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] < 0) return UNDERFLOW;
? elemtotal *= A.bounds[i];
? }
? va_end(ap);
? A.base=(ElemType *)malloc(elemtotal*
? sizeof(ElemType));
? if(!A.base) exit(OVERFLOW);
? A.constants = (int *)malloc(dim * sizeof(int));
? if(!A.constants) exit(OVERFLOW);
? A.constants[dim-1] = 1;
? for(i=dim-2; i >=0; --i)
? A.constants[i] = A.bounds[i+1] * A.constants[i+1];
? return OK;
? }
base
dim (4)
bounds
constants
elemtatol-1
7
0 1 2 3
8
65
336 1
Array A[5][6][7][8];
8
56
0
5x6x7x8
? Status DestroyArray(Array &A)
? { if (!A.base)
? return ERROR;
? free(A.base);
? A.base = NULL;
? if (!A.bounds)
? return ERROR;
? free(A.bounds);
? A.bounds = NULL;
? if (!A.constants)
? return ERROR;
? free(A.constants);
? A.constants = NULL;
? return OK;
? }
销毁数组 A
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
若 ap所指的各下标值合法,则求出该元素在A中的位置
? Status Locate(Array A,va_list ap,int &off)
? { off = 0;
? for(i=0; i<A.dim; ++i){
? ind = va_arg(ap,int);
? if(ind < 0 || ind >= a.bounds[i])
? return OVERFLOW;
? off += A.constants[i] * ind;
? }
? return OK;
? }
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
i
off
A是 n维数组,e为元素变量,随后是 n个下标值 ;
若各下标不超界,则 e赋值为所指定的 A的元素
值,并返回 OK
? Status Value(Array A,ElemType &e,...)
? { va_list ap;
? va_start(ap,e);
? if(result = Locate(A,ap,off)) <= 0)
? return result;
? e = *(A.base + off);
? return OK;
? }
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
i
off
e
A是 n维数组,e为元素变量,随后是 n个下标值 ;
若各下标不超界,则将 e的值赋给所指定的 A的
元素,并返回 OK
? Status Assign(Array &A,ElemType e,...)
? {
? va_start(ap,e);
? if(result = Locate(A,ap,off)) <= 0)
? return result;
? *(A.base + off) = e;
? return OK;
? }
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
i
off
e
主程序及例子
? main()
? { Array A; int i,j,e;
? InitArray(&A,2,3,4);
? for(i=0;i<3;i++)
? for(j=0;j<4;j++)
? Assign(&A,(i+1)*10+j,i,j);
? for(i=0;i<3;i++){
? printf(“\n”);
? for(j=0;j<4;j++){
? Value(A,&e,i,j);
? printf(“%4d”,e);
? }
? }
? }
base
dim
bounds
constants
10
11
20
33
13
......
0 1,.,dim-1
...
12
43
4 1
10 11 12 13
20 21 22 23
30 31 32 33
A =
实验与习题
?理论习题 5.1,5.2,5.3,5.6 5.8
?实验题,
? ① 写一个主程序来 上机验证数组的顺序存储
结构 的四个基本操作 ；并计算 A=B+C
? 3 4 5 6 9 7 5 3
? B = 7 8 9 10 C = 2 4 6 8
? 1 2 3 4 3 6 9 12
? ② 5.18
?5.1 数组的定义
?5.2 数组的顺序表示和实现
?5.3 矩阵的压缩存储
? 5.3.1 特殊矩阵
? 5.3.2 稀疏矩阵
5.1 数组的定义
? 维数和维界
? 二维数组的类型定义,
? 等价于
? typedef ElemType Array1[n];
? typedef Array1 Array2[m];
? typedef ElemType Array2[m][n];
? Array2 A;
? 二维的数组 = 定长的线性表
? a11 a12 a13,.,a1n
? a21 a22 a23,.,a2n
? Amxn=,.....
? am1 am2 am3,.,amn
? Amxn=
? ((a11,a12,a13,...a1n),(a21,a22,a23,...a2n),...,(am1,am2,am3,...amn))
数组的抽象数据类型
? ADT Array {
? 数据对象,D = {aj1j2...jn |
? n(>0)称为数组的维数,bi是数组第 i维的长度,
? ji是数组元素的第 i维下标,aj1j2...jn?Elemset}
? 数据关系,R={R1,R2,.,Rn}
? Ri = {＜ aj1...ji...jn,aj1...ji+1...jn ＞ |0 ? jk? bk-1,1 ? k ? n,
? aj1...ji...jn,aj1...ji+1...jn ?D}。
? 基本操作：
? InitArray(&A,n,bound1,bound2,...,boundn);
? DestroyArray (&A);
? Value(A,&e,index1,index2,...,indexn);
? Assign(&A,e,index1,index2,...,indexn)
? }ADT Array
5.2 数组的顺序表示和实现
? 除了初始化和销毁之外,
? 数组一般只有存取操作和修改元素值的操作,
? 通常不作删除和插入,
? 行序为主序,(C语言,PASCAL,BASIC等 )
? Amxn=
? (a11,a12,a13,...a1n,a21,a22,a23,...a2n,...am1,am2,am3,...amn)
? LOC[1,1] 为基地址,
? LOC[i,j] = LOC[1,1] + (n*(i-1)+j-1)*L
? (1<=i<=m,1<=j<=n,每个数据元素占 L个存储单元 )
例 5.1,若 L=2,LOC[1,1] = 1000
? LOC[3,4] = LOC[1,1] + (5*(3-1)+4-1)*L
? = 1000 + 13 * 2
? = 1026
? LOC[0,0] 为基地址,
? LOC[i,j] = LOC[0,0] + (n*i+j)*L
? (0<=i<m,0<=j<n,每个数据元素占 L个存储单元 )
? LOC[i,j,k] = LOC[0,0,0] + (n*h*i+ h*j + k)*L
? (0<=i<m,0<=j<n,0<=k<h,每个数据元素占 L个存储单元 )
a11 a12 a13 a14 a15
A4x5 = a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
一般 n维数组的列主元存储地址计算公式
? b1,b2,...,bn是 n维的维界,数组元素 A(j1,j2,...,jn)的存储位置为
? LOC[j1,j2,...jn]= LOC[0,0,...,0] + (b2?b3?...?bn?j1
? + b3?...?bn?j2
? +,.....
? + bn?jn-1
? + jn )?L
? n-1 n
? = LOC[0,0,...,0] + ( ? ji ? bk + jn)?L
? i=1 k=i+1
? 例, 在 C语言中,设 数组 A[5][6][7][8]的首地址为 2000,
? 每个元素占 2个字节 ; 求元素 A[3][4][5][4]的地址,
? LOC[3,4,5,4] = 2000 + (6*7*8*3 + 7*8*4 + 8*5 + 4)*2
? = 2000 + ( 336*3 + 56*4 + 8*5 + 1*4)*2
= 2000 + (1008 + 224 + 40 + 4)*2 = 4552
列序为主序, (FORTRAN)
? Amxn=
? ((a11,a21,a31,...am1),(a12,a22,a32,...am 2),...(a1n,a2n,a3n,...amn))
? LOC[1,1] 为基地址,
? LOC[i,j] = LOC[1,1] + (m*(j-1)+i-1)*L
? (1<=i<=m,1<=j<=n,每个数据元素占 L个存储单元 )
? 例 5.2,若 L=2,LOC[1,1] = 1000
? LOC[3,4] = LOC[1,1] + (4*(4-1)+3-1)*L
? = 1000 + 14 * 2 = 1028
? LOC[0,0] 为基地址,
? LOC[i,j] = LOC[0,0] + (m*j+i)*L
? (0<=i<=m,0<=j<=n,每个数据元素占 L个存储单元 )
? LOC[i,j,k] = LOC[0,0,0] + (m*((n*k)+j)+i) *L
a11 a12 a13 a14 a15
a21 a22 a23 a24 a25
a31 a32 a33 a34 a35
a41 a42 a43 a44 a45
数组顺序存储的表示和实现
? InitArray(Array &A,int dim,...);
? // 若维数 dim和随后的维数合法,构造相应的数组,并返回 OK
? DestroyArray (Array &A);//销毁数组 A
? Value(Array A,ElemType &e,...);
? 若各下标不超界,则 e赋值为所指定的 A的元素值,并返回 OK
? Assign(Array &A,ElemType e,...)
? 若各下标不超界,则将 e的值赋给所指定的 A的元素,并返回 OK
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
#incluse <stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct {
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
? Status InitArray(Array &A,int dim,...)
? { va_list ap;
? if(dim<1 || dim > MAX_ARRAY_DIM) 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] < 0) return UNDERFLOW;
? elemtotal *= A.bounds[i];
? }
? va_end(ap);
? A.base=(ElemType *)malloc(elemtotal*
? sizeof(ElemType));
? if(!A.base) exit(OVERFLOW);
? A.constants = (int *)malloc(dim * sizeof(int));
? if(!A.constants) exit(OVERFLOW);
? A.constants[dim-1] = 1;
? for(i=dim-2; i >=0; --i)
? A.constants[i] = A.bounds[i+1] * A.constants[i+1];
? return OK;
? }
base
dim (4)
bounds
constants
elemtatol-1
7
0 1 2 3
8
65
336 1
Array A[5][6][7][8];
8
56
0
5x6x7x8
? Status DestroyArray(Array &A)
? { if (!A.base)
? return ERROR;
? free(A.base);
? A.base = NULL;
? if (!A.bounds)
? return ERROR;
? free(A.bounds);
? A.bounds = NULL;
? if (!A.constants)
? return ERROR;
? free(A.constants);
? A.constants = NULL;
? return OK;
? }
销毁数组 A
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
若 ap所指的各下标值合法,则求出该元素在A中的位置
? Status Locate(Array A,va_list ap,int &off)
? { off = 0;
? for(i=0; i<A.dim; ++i){
? ind = va_arg(ap,int);
? if(ind < 0 || ind >= a.bounds[i])
? return OVERFLOW;
? off += A.constants[i] * ind;
? }
? return OK;
? }
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
i
off
A是 n维数组,e为元素变量,随后是 n个下标值 ;
若各下标不超界,则 e赋值为所指定的 A的元素
值,并返回 OK
? Status Value(Array A,ElemType &e,...)
? { va_list ap;
? va_start(ap,e);
? if(result = Locate(A,ap,off)) <= 0)
? return result;
? e = *(A.base + off);
? return OK;
? }
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
i
off
e
A是 n维数组,e为元素变量,随后是 n个下标值 ;
若各下标不超界,则将 e的值赋给所指定的 A的
元素,并返回 OK
? Status Assign(Array &A,ElemType e,...)
? {
? va_start(ap,e);
? if(result = Locate(A,ap,off)) <= 0)
? return result;
? *(A.base + off) = e;
? return OK;
? }
base
dim
bounds
constants
a0
a1
ai
at
...
......
0 1,.,dim-1
...
i
off
e
主程序及例子
? main()
? { Array A; int i,j,e;
? InitArray(&A,2,3,4);
? for(i=0;i<3;i++)
? for(j=0;j<4;j++)
? Assign(&A,(i+1)*10+j,i,j);
? for(i=0;i<3;i++){
? printf(“\n”);
? for(j=0;j<4;j++){
? Value(A,&e,i,j);
? printf(“%4d”,e);
? }
? }
? }
base
dim
bounds
constants
10
11
20
33
13
......
0 1,.,dim-1
...
12
43
4 1
10 11 12 13
20 21 22 23
30 31 32 33
A =
实验与习题
?理论习题 5.1,5.2,5.3,5.6 5.8
?实验题,
? ① 写一个主程序来 上机验证数组的顺序存储
结构 的四个基本操作 ；并计算 A=B+C
? 3 4 5 6 9 7 5 3
? B = 7 8 9 10 C = 2 4 6 8
? 1 2 3 4 3 6 9 12
? ② 5.18
