第6章数组与广义表 ◆数组的定义及其基本操作 ◆数组的顺序存储结构 ◆矩阵的压缩存储 ◆广义表的概念 ◆广义表的存储结构表示 ◆广义表的运算
第6章 数组与广义表 数组的定义及其基本操作 数组的顺序存储结构 矩阵的压缩存储 广义表的概念 广义表的存储结构表示 广义表的运算
数组的定义 ◆数组:由一组类型相同的数据元素构成的有限序列 且该有限序列存储在一块地址连续的内存单元中。 维数组:数组只有一个下标 ◆二维数组:数组元素都含有两个下标,形如: 12 lx 22 2
数组的定义 数组：由一组类型相同的数据元素构成的有限序列， 且该有限序列存储在一块地址连续的内存单元中。 一维数组 ：数组只有一个下标。 二维数组 ：数组元素都含有两个下标 ，形如：
◆二维数组与一维数组的关系:一个二维数组看成是每个 数据元素都是相同类型的一维数组的一维数组 实例:m行n列的二维数组,可以看成是一个线形表 A=(a1,a,…ap)(p=m或n)即 1 a11a12 a21a22 (a)矩阵形式表示 b)列向量的一維数组 11 22 】x (c)行向量的一维数组 图61二维数组示意图
二维数组与一维数组的关系：一个二维数组看成是每个 数据元素都是相同类型的一维数组的一维数组。 实例：m行n列的二维数组，可以看成是一个线形表 A=(a1 ,a2 ,…,ap ) (p=m 或 n) 即：
数组的性质 数组中的数据元素数目固定 数组中的数据元素具有相同的数据类型 数组中的每个数据元素都和一组唯一的下标值 对应。 ●数组是一种随机存储结构,可随机存取数组中 的任意数据元素
数组的性质： 数组中的数据元素数目固定。 数组中的数据元素具有相同的数据类型。 数组中的每个数据元素都和一组唯一的下标值 对应。 数组是一种随机存储结构，可随机存取数组中 的任意数据元素
数组的基本操作 ◆随机存:给定一组下标,存一个数据元素到该组下标对 应的内存单元中。 ◆随机取:从给定的一组下标所对应的内存单元中取出 个数据元素
随机存：给定一组下标，存一个数据元素到该组下标对 应的内存单元中。 随机取：从给定的一组下标所对应的内存单元中取出一 个数据元素。 数组的基本操作
数组的顺序存储结构 ◆数组的顺序存储结构:将数组元素顺序地存放在一片连 续的存储单元中。 ◆二维数组有两种存储方式:以列序为主序( column major order)的存储方式,如图6-2(a所示和以行序 为主序( row major order)的存储方式,如图6-2(b) 所示。 ◆地址计算:以行序为主序的存储方式为例: LOCij=LOC[0, 0+(b2xi+jxL LoC[U12…,d]Loc0.0,,0+(b2×,×如x×j+b3×.x×j2 ◆推广到n维数组 +…+如×+)xL 0C0.…,+∑∏+
数组的顺序存储结构 数组的顺序存储结构：将数组元素顺序地存放在一片连 续的存储单元中 。 二维数组有两种存储方式：以列序为主序（column major order）的存储方式，如图6-2(a)所示和以行序 为主序（row major order）的存储方式，如图6-2(b) 所示。 地址计算：以行序为主序的存储方式为例： 推广到n维数组: LOC[i,j]=LOC[0,0]+(b2i+j) L
LAon 1 LOCCAl(y=LOC(ao1) 10 A A,( Alc LOCKAm-1 (1)-LOC(aon-1)[AInI m.41) A(2=(Ao(1),A1(1),…,Ax1(1 A(2(A01),A11),…,Am1(1) A A21(a10 以列序为主序 以行序为主序
A0 (1) A1 (1) An-1 (1) 以列序为主序 以行序为主序
数组的顺序存储表示和实现的算法 typedef struct ElemType *base, /*数组元素初始地址,由初始 化操作实现* int dim /*数组的维数*/ int *bounds /*数组各维的长度,也由初始化 操作实现* int *const;/*数组的映象函数常量的初始 地址,由初始化操作实现*
数组的顺序存储表示和实现的算法： typedef struct { ElemType *base; /*数组元素初始地址，由初始 化操作实现*/ int dim; /*数组的维数*/ int *bounds; /*数组各维的长度，也由初始化 操作实现*/ int *const ; /*数组的映象函数常量的初始 地址，由初始化操作实现*/ } ;
◆数组的初始化算法: Status InitialArray array &A, int Adim) /*如果维数Adim和数组各维的长度 bounds合法,构造相应的数 组A,并返回OK值* {/*如果维数Adm不合法,返回值为 error*/ if (Adim MAXDIM) return error g A dim=Adim. A bounds=(int*)malloc(Adim*sizeof(int) if(lA bounds) exit(overflow) 如果各维长度合法,则存入 A bounds,并求出A的元素总 数 totanus totalnum=1 va_start(ap,Adim);/*ap为存放变长参数表信息的数组, 其类型为 va list*/
数组的初始化算法： Status InitialArray(Array &A, int Adim) /*如果维数Adim和数组各维的长度bounds合法，构造相应的数 组A，并返回OK值*/ { /*如果维数Adim不合法，返回值为error */ if (Adim MAXDIM) return error ; A.dim=Adim; A.bounds=(int* )malloc(Adim*sizeof(int)); if (!A.bounds) exit (overflow); /*如果各维长度合法，则存入A.bounds，并求出A的元素总 数totalnum*/ totalnum=1; va_start(ap, Adim); /*ap为存放变长参数表信息的数组， 其类型为va_list*/
for(i=0; i=0, i-) A const i]=A bounds i+1*A const i+1 return OK
for(i=0;i=0,i--) A.const [i]=A.bounds[i+1]*A.const [i+1]; return OK; }