数据结构--数组和广义表(全)

1第5章数组和广义表（Arrays&Lists）①元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。②所有数据元素仍属同一数据类型。5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构数组和广义表的特点：一种特殊的线性表25.1数组的定义数组：由一组名字相同、下标不同的变量构成注意：本章所讨论的数组与高级语言中的数组有所区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。答：对的。因为：①数组中各元素具有统一的类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。讨论：“数组的处理比其它复杂的结构要简单”，对吗？3二维数组的特点：一维数组的特点：1个下标，ai是ai+1的直接前驱2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。N维数组的特点：n个下标，每个元素受到n个关系约束一个n维数组可以看成是由若干个n－1维数组组成的线性表。a11a12…a1na21a22…a2n…………am1am2…amnAmn=4N维数组的数据类型定义n_ARRAY=(D,R)其中：Ri={aj1,j2,…ji…jn,aj1,j2,…ji+1…jn|aj1,j2,…ji…jn,aj1,j2,…ji+1…jnD,i=2,…n}数据关系：R={R1,R2，….Rn}数据对象：D={aj1,j2…jn|ji为数组元素的第i维下标，aj1,j2…jnElemset}数组的抽象数据类型定义略，参见教材P90构造数组、销毁数组、读数组元素、写数组元素基本操作：55.2数组的顺序存储表示和实现问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一列序列，然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。注意：•若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；•约定的次序不同，则计算元素地址的公式也有所不同；•C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。6补充：计算二维数组元素地址的通式设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0。无论规定行优先或列优先，只要知道以下三要素便可随时求出任一元素的地址（这样数组中的任一元素便可以随机存取！）：二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…ad1,c2…ad1,d2Amn=单个元素长度aij之前的行数数组基址总列数，即第2维长度aij本行前面的元素个数①开始结点的存放地址（即基地址）②维数和每维的上、下界；③每个数组元素所占用的单元数则行优先存储时的地址公式为：LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L7例2：已知二维数组Am,m按行存储的元素地址公式是：Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存储的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（尽管是方阵，但公式仍不同）例1〖软考题〗：一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是个字节。288例3：〖00年计算机系考研题〗设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：请注意审题！利用列优先通式：答：Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2888Loc(j1,j2,…jn)=LOC(0,0,…0)＋若是N维数组，其中任一元素的地址该如何计算？niii1jC其中Cn=L,Ci-1=bi×Ci，1i≤n一个元素长度数组基址前面若干元素占用的地址字节总数第i维长度与所存元素个数有关的系数，可用递推法求出教材已给出低维优先的地址计算公式，见P93（5-2）式该式称为n维数组的映像函数：9#defineMAX_ARRAY_DIM8//假设最大维数为8typedefstruct{ELemType*base;//数组元素基址intdim;//数组维数int*bound;//数组各维长度信息保存区基址int*constants;//数组映像函数常量的基址}Array;即Ci信息保存区数组的基本操作函数说明（有5个）（请阅读教材P93-95）N维数组的顺序存储表示（见教材P93）以销毁数组函数为例10StatusInitArray(Array&A,intdim,…){//若维数dim和各维长度合法，则构造相应的数组A并返回OKif(dim1||dimMAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!a.bounds)exit(OVERFLOW);//若各维长度合法，则存入A.bounds,并求出A的元素总数elemtotalelemtotal=1;va_start(ap.dim);//ap为va_list类型，是存放变长参数表信息的类型数组的基本操作函数说明（5个）（见教材P93-95）11for(i=0;idim;++i){A.bounds[i]=va_arg(ap,int);if(A.bounds[i]0)returnUNDERFLOW;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.constans)exit(OVERFLOW);A.constans[dim-1]=1;for(i=dim-2;i=0;--i)A.constants[i]=A.bounds[i+1]*A.constants[i+1];returnOK;}12数组基址指针各维长度保存区指针映像函数Ci保存区指针StatusDestroyArray(Array&A){//销毁数组Aif(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants);A.constants=NULL;returnOK;}13StatusLocate(ArrayA,va_listap,int&off){//若ap指示的各下标值合法，则求出该元素在A中，相对地址offoff=0;for(i=0;iA.dim;++i){ind=va_arg(ap,int);if(ind0||indA.bounds[i])returnOVERFLOW;off+=A.constants[i]*ind;}returnOK;}14StatusValue(ArrayA,ElemType&e,…){//A是n维数组，e为元素变量，随后是n个下标值，若各下标不超界，则e赋值为所指定的A的元素值，即将指定元素值读到e变量中。va_start(ap,e);if((result=Locate(A,ap,off))=0)returnresult;e=*(A.base+off);returnOK;}15StatusAssign(Array&A,ElemTypee,…){//A是n维数组，e为元素变量，随后是n个下标值，若各下标不超界，则e的值赋为所指定的A的元素值，即：将e值写入指定数组单元。va_start(ap,e);if((result=Locate(A,ap,off))=0)returnresult;*(A.base+off)=e;returnOK;}16顺序存储方式：按低地址优先（或高地址优先）顺序存入一维数组。^……行指针向量a11a12…^a1nam1am2…^amn补充：链式存储方式：用带行指针向量的单链表来表示。注：数组的运算参见下一节实例（稀疏矩阵的转置）（难点是多维数组与一维数组的地址映射关系）175.3矩阵的压缩存储讨论：1.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.所有二维数组（矩阵）都能压缩吗？未必，要看矩阵是否具备以上压缩条件。3.什么样的矩阵具备以上压缩条件？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。4.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）重点介绍稀疏矩阵的压缩和相应的操作。18一、稀疏矩阵的压缩存储问题：如果只存储稀疏矩阵中的非零元素，那这些元素的位置信息该如何表示？解决思路：对每个非零元素增开若干存储单元，例如存放其所在的行号和列号，便可准确反映该元素所在位置。实现方法：将每个非零元素用一个三元组（i，j，aij）来表示，则每个稀疏矩阵可用一个三元组表来表示。二、稀疏矩阵的操作19例1：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。行下标列下标元素值例2：写出右图所示稀疏矩阵的压缩存储形式。0129000000000-3000140002400001800001500-700((1,2,12)，(1,3,9)，(3,1,-3)，(3,5,14)，(4,3,24)，(5,2,18)，(6,1,15)，(6,4,-7))法1：用线性表表示：0129000000000-3000140002400001800001500-70020法2：用三元组矩阵表示：0129000000000-3000140002400001800001500-700121213931-3351443245218611564-7注意：为更可靠描述，通常再加一行“总体”信息：即总行数、总列数、非零元素总个数668ijvalue稀疏矩阵压缩存储的缺点：将失去随机存取功能:-(01234567821法三：用带辅助向量的三元组表示。方法：增加2个辅助向量：①记录每行非0元素个数，用NUM（i）表示；②记录稀疏矩阵中每行第一个非0元素在三元组中的行号，用POS（i）表示。76531211202NUM(i)6543POS(i)21i0129000000000-3000140002400001800001500-700-7461516182524341453-3139311221866vji0123456783用途：通过三元组高效访问稀疏矩阵中任一非零元素。规律：POS(1)＝1POS(i)＝POS(i-1)+NUM(i-1)22法四：用十字链表表示用途：方便稀疏矩阵的加减运算；方法：每个非0元素占用5个域。rightdownvji同一列中下一非零元素的指针同一行中下一非零元素的指针十字链表的特点：①每行非零元素链接成带表头结点的循环链表；②每列非零元素也链接成带表头结点的循环链表。则每个非零元素既是行循环链表中的一个结点；又是列循环链表中的一个结点，即呈十字链状。以刚才