79数据结构

第五章数组广义表数据结构5.1数组的定义定义第5章数组和广义表mnmmnnnmAa....aa................a....aaa....aa212222111211=×nm×也可以看成是m个行向量可以看成是个列向量n可看成是一种特殊的线性表，其特殊在于表中的数据元素本身也是一个线性表。数组是一组有固定个数的元素的集合。数组性质元素个数固定一旦定义了一个数组，它的维数和维界就不能再改变只能对数组进行存取元素和修改元素的操作。元素具有相同的数据类型每个元素都和唯一的下标对应随机存储结构可随机存取数组中的任意数据元素。数据结构5.2数组的顺序存储类型特点:第5章数组和广义表1）不考虑插入和删除操作；2）数组是多维的结构，而存储空间是一个一维的结构。数据结构5.1数组的定义运算第5章数组和广义表获得特定位置的元素值；修改特定位置的元素值。主要操作是数据元素的定位，即给定元素的下标，得到该元素在计算机中的存放位置。其本质是地址计算问题。有两种顺序映象的方式:以行序为主序；以列序为主序。数据结构5.2数组的顺序存储和实现以行序为主序第5章数组和广义表例如：a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(n×i＋j)×称为基地址或基址。L数据结构5.2数组的顺序存储和实现以行序为主序第5章数组和广义表例如：a1,2a1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,3a2,1a2,2a2,3L二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(n×(i-1)＋(j-1))×称为基地址或基址。L数据结构5.2数组的顺序存储和实现以列序为主序第5章数组和广义表例如：L二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(0,0)+(m×j＋i)×称为基地址或基址。La0,1a0,0a0,2a1,0a1,1a1,2a1,0a0,0a0,1a1,1a0,2a1,2数据结构5.2数组的顺序存储和实现以列序为主序第5章数组和广义表例如：L二维数组Amxn中任一元素ai,j的存储位置LOC(i,j)=LOC(1,1)+(m×(j-1)＋(i-1))×称为基地址或基址。La1,2a1,1a1,3a2,1a2,2a2,3a2,1a1,1a1,2a2,2a1,3a2,3数据结构5.2数组的顺序表示和实现第5章数组和广义表例如：设有二维数组A[10][20]，其每个元素占2个字节，第一个元素A1,1的存储地址为100，则按行优先顺序存储时元素A6,6的存储地址为?若按列优先顺序存储时元素A6,6的存储地址为?A6,6=100+[(6-1)*20+(6-1)]*2=310按行优先按列优先A6,6=100+[((6-1)*10+(6-1)]*2=210二维数组的基本操作二维数组的显示读取二维数组中的元素二维数组的加法二维数组的减法二维数组的点乘二维数组的点除【算法】二维数组的加法（两个二维数组A+B）。思路：两个数组之间对应位置的元素值相加的结果再存储到结果数组的同一位置上。voidMatrixADD(intA[maximum][maximum],intB[maximum][maximum],intresult[maximum][maximum])/*两个二维数组相加*/{inti,j;for(i=0;imaximum;i++)for(j=0;jmaximum;j++)result[i][j]=A[i][j]+B[i][j];}两个数组必须是同样大小，否则无法完成操作，结果数组也是相同的大小。5.3矩阵的压缩存储定义在高级语言(C,C++)编程中，通常用二维数组来存储矩阵元素当矩阵里有很多0或者相同元素时，可以考虑这些相同元素或0元素共用一个存储单元，也就是要进行矩阵压缩。特殊矩阵对称矩阵、上三角阵、下三角阵和对角阵稀疏矩阵特殊矩阵对称矩阵15375498A39267861=对于这种矩阵，可以为每一对对称元素分配一个存储空间，n×n个元素的矩阵可以存储到n（n+1）/2个存储空间中。存在对应关系：k=i*(i+1)/2+j当i≧jk=j*(j+1)/2+i当ij令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为：k=I*(I+1)/2+J0≦kn(n+1)/2aij的地址可用下列式计算：LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储k=0123n(n-1)/2n(n-1)/2-1例如a21和a12均存储在sa[4]中，这是因为k=I*(I+1)/2+J=2*(2+1)/2+1=4a00a10a11a20……an-10……an-1,n-1【算法5-8】对称矩阵的压缩存储。思路：先定义一个一维数组，长度为n（n+1）/2，只存储二维数组上半部或者下半部（包括对角线元素）到一维数组中。voidMirrorMSave(intH[N][N],int*s)/*对称矩阵的存储*/{inti,j;intcount=0;/*记录存储的个数*/for(i=0;iN;i++)/*按行取值*/for(j=i;jN;j++){s[count]=H[i][j];count++;}}特殊矩阵上三角矩阵只有对角线以上的部分有数值，以下的部分是同一个常数。1537c498Acc26ccc1=上三角矩阵除了要存储上半部分的数据之外，还要额外存储一个常数项，需要用n（n+1）/2+1个存储单元。特殊矩阵下三角矩阵下三角矩阵与上三角矩阵相反，常数位于矩阵的上半部分。1ccc54ccA392c7261=下三角矩阵的压缩存储结构和上三角矩阵一样，区别在于存储的是矩阵的下三角和上三角的常数，实现方法和存储空间也和上三角矩阵一样。特殊矩阵对角矩阵只有对角线位置上的元素非0，其余位置的元素均为0。=9000020000400001A压缩存储时只需要存储对角线上的非0元素即可，实现最简单。系数矩阵定义非零元素的个数远远低于零元素的个数的矩阵1000004009000000稀疏矩阵压缩存储时，只存储稀疏矩阵中的非零元素。包含行下标、列下标和数值的三元数组(i,j,value)可以唯一确定非零元素。假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为0.05的矩阵为稀疏矩阵。nmt=何谓稀疏矩阵？系数矩阵的基本操作三元组的生成稀疏矩阵的加(减)法稀疏矩阵的转置三元组的乘法【算法】三元组的生成（矩阵为H[M][N]）。思路：对矩阵H的每个元素逐个进行判断，遇到非零元素，则在三元组中存储该元素的行号、列号和元素数值，另外还要保存数组的非零元素个数。voidCreateTArray(TMatrix&t,intH[M][N]){inti,j;t.rows=M;t.colums=N;t.number=0;/*非0个数初始为0*/for(i=0;iM;i++)for(j=0;jN;j++){if(H[i][j]!=0)/*非零值的三元数*/{t.d[t.number].data=H[i][j];t.d[t.number].r=i;t.d[t.number].c=j;t.number++;}}return;}广义表定义广义表是线性表的推广，也称为列表(Lists)，一般记作:LS=（a1,a2,a3,…,an）ai可以是单个元素(原子)，也可以是广义表(子表)。相关术语表头(Head):广义表中的第一个元素表尾(Tail):表中除了表头之外的所有元素深度(Depth)：广义表中括号嵌套的最大层数。lD=（）空表；其长度为零。lA=(a，(b，c))表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。lB=（A，A，D）长度为3的广义表，其前两个元素为表A，第三个元素为空表D。lC=（a，C）长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（…））））。例如：head(A)=a表A的表头是a。tail(A)=((b，c))表A的表尾是((b，c))，广义表的表尾一定是一个表。例如:D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()【试题】（中国地质大学）已知非空广义表L=（（（a,b）,c）,（d,（e,f））,g），用取表头head（L）和取表尾tail（L）函数，写出从L中取出元素a的运算____________。【试题】（南京林业大学）广义表（a,（b,c）,d,e,（（f,g）,h））的长度为________，深度为________。分析：广义表（a,（b,c）,d,e,（（f,g）,h）），最外层括号内有5项，故长度为5；括号最多有3层，故深度为3。分析：head（L）=（（a,b）,c）head（head（L））=（a,b）head（head（head（L）））=a从上面的例子可以看出：（1）广义表的元素可以是子表，而子表还可以是子表…，由此，广义表是一个多层的结构。（2）广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。（3）广义表具有递归性，如广义表C。广义表的存储结构常采用链式存储结构。需要两种结构的结点：一种是原子结点，另一种是表结点，用以表示列表。表结点原子结点广义表的基本运算广义表的建立统计广义表的长度统计广义表的深度递归运算返回广义表表头(尾)广义表遍历下课了。。。追求休息一会儿。。。