数据结构(第五章-数组和广义表).ppt

数据结构引言主要内容5.1数组的定义二维数组的特点：5.1数组的定义5.1数组的定义a00a01…a0,n-1a10a11…a1,n-1……………am-1,0am-1,1…am-1,n-15.2数组的顺序表示和实现5.2数组的顺序表示和实现5.2数组的顺序表示和实现5.2数组的顺序表示和实现5.2数组的顺序表示和实现推而广之，对n维数组A=(aj1j2…jn)，若每个元素占用的存储单元数为l(个)，LOC[a00…0]表示元素a00…0的首地址。则以“行优先顺序”存储在内存中。#defineMAX_ARRAY_DIM8//假设最大维数为8typedefstruct{ELemType*base;//数组元素基址intdim;//数组维数int*bound;//数组各维长度信息保存区基址int*constants;//数组映像函数常量的基址}Array;StatusInitArray(Array&A,intdim,…){//若维数dim和各维长度合法，则构造相应的数组A并返回OKif(dim<1||dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*sizeof(int));if(!a.bounds)exit(OVERFLOW);//若各维长度合法，则存入A.bounds,并求出A的元素总数elemtotalelemtotal=1;数组的基本操作数组的基本操作数组的基本操作数组的基本操作数组的基本操作5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储上图所示三对角矩阵的压缩存储形式。数组sa中的元素sa[k]与三对角矩阵中的元素aij存在一一对应关系，在aij之前有i-1行,共有3(i-1)-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：LOC[aij]=LOC[a11]+[3(i-1)-1+(j-i+1)]l=LOC[a11]+(2i+j-3)l上例中，a34对应着sa[7],k=2i+j-3=23+4-3=7称sa[0…3n-3]是n阶三对角矩阵A的压缩存储。上述各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储M=如果能先求得M各列第一个非零元在三元组T.data中的位置，就能在对M.data一次扫描的过程中，完成M到T的转置：对M.data一次扫描时，首先遇到各列的第一个非零元三元组，可按先前求出的位置，将其放至T.data中，当再次遇到各列的非零元三元组时，只须顺序放到对应列元素的后面。5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储5.3矩阵的压缩存储对于下图中的稀疏矩阵A，对应的十字交叉链表如右图所示，结点的描述如下：5.4广义表的定义5.4广义表的定义5.4广义表的定义5.4广义表的定义5.4广义表的定义5.4广义表的定义广义表的重要结论：(1)广义表的元素可以是原子，也可以是子表，子表的元素又可以是子表，…。即广义表是一个多层次的结构。(2)广义表可以被其它广义表所共享，也可以共享其它广义表。广义表共享其它广义表时通过表名引用(例如D=(A,B,C)，其中A，B，C分别是三个广义表)。(3)广义表本身可以是一个递归表。(4)根据对表头、表尾的定义，任何一个非空广义表的表头可以是原子，也可以是子表，而表尾必定是广义表。5.4广义表的存储结构5.4广义表的存储结构5.4广义表的存储结构5.4广义表的存储结构5.4广义表的存储结构本章学习要点