计算机软件基础第五讲.pptVIP

* * * * * * * * * * * * * * * * 简化算法 * * 矩阵相乘 * * 数据结构与数据库技术 王康元 EMAIL：wangkangyuan@ 第五讲：数组 时间：2009年10月23日 讲述的主要内容 数组定义 数组的顺序表现及实现 稀疏矩阵的定义 稀疏矩阵的各种表现形式及实现 数组定义 ADT Array { 数据对象：ji=0, ．．．,bi-1, i=1,2, ．．．,n, 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 且 k≠i, 0≤ji≤bi-2, aj... ji...jn ,aj1...ji+1...jn∈ D,i=2 ,...,n } 基本操作： InitArray(A,n,bound1,...,boundn) DestroyArray(A) Value(A,e,index1,...,indexn) Assign(A,e,index1,...,indexn) }ADT Array 二维数组定义 ADT Array { 数据对象： i=0,…m ,j=0, ．．．,n D= { aij | m是数组第1维长度 , n是数组第2维长度, i是数组元素的第1维下标， j是数组元素的第2维下标， aij∈ ElemSet } 数据关系：R={R1，R2} R1={ai,j,ai,j+1 ︱ 0≤j≤n-1, 1≤i≤m } R2={ai,j,ai+1,j ︱ 0≤i≤m-1, 1≤j≤n} 基本操作： InitArray(A,n,bound1,bound2) DestroyArray(A) Value(A,e,index1,index2) Assign(A,e,index1,index2) }ADT Array 数组的顺序表现与实现 以行序为主序 以列序为主序 数组的顺序表现与实现 以行序为主序 Loc(aij) = Loc(a11)+[(i-1)*n+(j-1)]*d 以列序为主序 Loc(aij) = Loc(a11)+[(j-1)*m+(i-1)]*d 数组的顺序存储表示 # includestarg.h //标准头文件，提供宏va_start ,va_arg和va_end //用于存取变长参数表 #define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8 typedef struct { ElemType *base ; //数组元素基址，由InitArray分配 int dim ; //数组维数 int *bounds; //数组维界基址，由InitArray分配 int *constants ; //数组映象函数常量基址，由InitArray分配 }Array; 数组的顺序表示实现 Status InitArray(Array A, int m,int n){ A.dim = 2; A.bounds = (int*)malloc(2*sizeof(int)); if(!A.bounds) exit(OVERFLOW); elmtotal = 1; A.bounds[0] = m; A.bounds[1] = n; If((m0) ||(n0))return UNDERFLOW; elemtotal = m*n; 数组的顺序表示实现 A.base = (ElemType*)malloc(elemtotal*sizeof(ElemType)); if(!A.base) exit(OVERFLOW); A.cons