06第6章数组与广义表.ppt

第6章 数组与广义表 数组的定义及其基本操作 数组的顺序存储结构 矩阵的压缩存储 广义表的概念 广义表的存储结构表示 广义表的运算 数组的定义 数组：由一组类型相同的数据元素构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。 一维数组 ：数组只有一个下标。 二维数组 ：数组元素都含有两个下标 ，形如： 二维数组与一维数组的关系：一个二维数组看成是每个数据元素都是相同类型的一维数组的一维数组。 实例：m行n列的二维数组，可以看成是一个线形表 A=(a1,a2,…,ap) (p=m 或 n) 即： 数组的性质： 数组中的数据元素数目固定。 数组中的数据元素具有相同的数据类型。 数组中的每个数据元素都和一组唯一的下标值对应。 数组是一种随机存储结构，可随机存取数组中的任意数据元素。 数组的基本操作 随机存：给定一组下标，存一个数据元素到该组下标对应的内存单元中。 随机取：从给定的一组下标所对应的内存单元中取出一个数据元素。 数组的顺序存储结构 数组的顺序存储结构：将数组元素顺序地存放在一片连续的存储单元中 。 二维数组有两种存储方式：以列序为主序（column major order）的存储方式，如图6-2(a)所示和以行序为主序（row major order）的存储方式，如图6-2(b)所示。 地址计算：以行序为主序的存储方式为例： 推广到n维数组: 数组的顺序存储表示和实现的算法： typedef struct { ElemType *base; /*数组元素初始地址，由初始化操作实现*/ int dim; /*数组的维数*/ int *bounds; /*数组各维的长度，也由初始化操作实现*/ int *const ; /*数组的映象函数常量的初始地址，由初始化操作实现*/ } ; 数组的初始化算法： Status InitialArray(Array A, int Adim) /*如果维数Adim和数组各维的长度bounds合法，构造相应的数组A，并返回OK值*/ { /*如果维数Adim不合法，返回值为error */ if (Adim1||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;iAdim;++i) { A.bounds[i]=va_arg(ap,int); if(A.bounds[i]0) return (underflow); totalnum* = A.bounds[i]; } va_end(ap); A.base=(ElemType*)malloc(dim*sizeof(ElemType)); if(!A.base) exit(overflow); /*求映象函数的常，把结果存入A.const [i-1],i=1,…,Adim*/ A.const=(int*)malloc(dim*sizeof(int)); if(!A.const) exit(overflow); A.const [Adim-1]=1; /*指针的增减以元素的大小为单位*/ for(i=Adim-2;i=0,i--) A.const [i]=A.bounds[i+1]*A.const [i+1]; return OK; } 矩阵的压缩存储 特殊矩阵：具有许多相同的元素或者零元素且这些元素在矩阵中的分布有一定的规律的矩阵。 稀疏矩阵：一个矩阵中的非零元素远远少于零元素的矩阵。 压缩存储：是指为多个值相同的元素只分配一个存储空间，而对零元素不分配存储空间，必须能够体现矩阵的逻辑结构。 特殊矩阵的压缩存储 对称矩阵的压缩存储： 对称矩阵：若一个n阶矩阵A中的元素满足下述关系， aij=aji 1≤i,j≤n，形如： 对称矩阵存储方式（以行序为主序最为实例）： 以一维数组one[n(n+1)/2]作为n阶对称矩阵