第4章-数组和广义表-2

第四章数组和广义表★数组的逻辑结构一个二维数组的类型定义如下：其中c,d设为1，数组可表示为：A:array[c..m][d..n]ofElemTypeA=a11a12…a1na21a22…a2n…………am1am2…amn它可以看成是由m个行向量或n个列向量组成的线性表。即，二维数组可以看成是一种推广的线性表，这种线性表的每一个数据元素本身也是一个线性表。类似地，一个三维数组可以看成是数据元素为二维数组的线性表一个n维数组可视为其数据元素为n-1维数组的线性表。★数组的顺序存储分配a1a2a3…an-1anLoc(ai)=Loc(a1)+(i-1)kA[1:n]=(a1,a2,a3,…,an)若已知每个元素占k个存储单元，并且知道第一个元素的存储地址Loc(a1),则一.一维数组A[1:n]a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn行序为主序分配方式列序为主序分配方式二.二维数组A[1:m][1:n]a11...a1na21...a2na31...aij...amn第1行第2行……a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn1.行序为主序分配方式a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:m][1:n]=…………aij……am1am2am3……amni-1行若已知每个元素占k个存储单元，并且知道第一个元素的存储地址LOC(a11),则Loc(aij)=Loc(a11)+(i1)nk+(j1)k=Loc(a11)+[(i1)n+(j1)]ka11...am1a12...am2a13...aij...amn第1列第2列……a11a12a13……a1na21a22a23……a2nA[1:m][1:n]=…………am1am2am3……amn2.列序为主序分配方式a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:m][1:n]=…………aij……am1am2am3……amnj-1列若已知每个元素占k个存储单元，并且知道第一个元素的存储地址LOC(a11),则Loc(aij)=Loc(a11)+(j1)mk+(i1)k=Loc(a11)+[(j1)m+(i1)]k9•数组A[0…5][0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则A[5][5]的地址是（）。Ａ.1175Ｂ.1180Ｃ.1205Ｄ.1210课堂练习A•已知二维数组A[m][n]采用行序为主的方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0]),则A[i][j]的地址是。LOC(A[0][0])+(i*n+j)*ka11a12a13……a1na21a22a23……a2nm=…………am1am2am3……amnA[1:m][1:n]所谓压缩存储是指为多个值相同的元素,或者位置分布有规律的那些元素分配尽可能少的存储空间，而对0元素一般情况下不分配存储空间。传统做法★矩阵的压缩存储a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:n][1:n]=…………an1an2an3……ann传统做法：定义一个二维数组A[1:n,1:n]一.对称矩阵的压缩存储一个n阶矩阵A的元素满足性质aij=aji1≤i,j≤n则称矩阵A为n阶对称矩阵。a11a21a22......aij......ann123......n*(n+1)/2a11a12a13……a1na21a22a23……a2na31a32a33……a3nA[1:n][1:n]=…………an1an2an3……annV只存储下三角元素时寻址公式为：loc(A[i][j])=loc(A[1][1])+[i(i-1)/2+j-1]*k传统做法：定义一个二维数组B[1:n][1:n]0元素0元素二.对角矩阵的压缩存储若一个矩阵中，值非0的元素对称地集中在主对角线两旁的一个带状区域中(该区域之外的元素都为0元素)，称这样的矩阵为对角矩阵。例.三对角矩阵的压缩存储b11b12b21b22b23b32b33b34bn-1nbnn-1bnn0元素0元素非零元素的个数为3（n-2）+4B[1:n][1:n]=b11b12b21bij......b22......1234......3n-2bnnb11b12b21b22b23b32b33b34bn-1nbnn-1bnn0元素0元素B[1:n][1:n]=对角线数组中某元素寻址公式为：loc(A[i][j])=loc(A[1][1])+[2(i-1)+j-1]*k传统做法：定义一个二维数组A[1:6][1:6]一.什么是稀疏矩阵?一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个数所占比例较大时，可以称该矩阵为一个稀疏矩阵。M=1500220-150113000000-60000000091000000028000★稀疏矩阵三元组：(i,j,value)例如：（1,1,15）表示第1行、第1列、值为15的元素。（1,4,22）表示第1行、第4列、值为22的元素。（1,6,-15）表示第1行、第6列、值为-15的元素。1500220-150113000000-60000000091000000028000二.稀疏矩阵的三元组表示(m,n,t)其中，m,n,t分别表示稀疏矩阵的总的行数、总的列数与非零元素的总个数。若一个mn阶稀疏矩阵具有t个非零元素，则用t+1个三元组来存储,其中第一个三元组分别用来给出稀疏矩阵的总行数m、总列数n以及非零元素的总个数t；第二个三元组到第t+1个三元组按行序为主序的方式依次存储t个非零元素。M=1500220-150113000000-60000000091000000028000M[1:6][1:6]6681115142216-15221134-623351916328A=A[1:9][1:3]三元组：(ijvalue)1500220-150113000000-60000000091000000028000M=1500091001100000300028220-6000000000-1500000N=表示稀疏矩阵M的三列的二维数组[1][2][3]A[0]668A[1]1115A[2]1422A[3]16-15A[4]2211A[5]233A[6]34-6A[7]5191A[8]6328[1][2][3]B[0]668B[1]1115B[2]1591B[3]2211B[4]323B[5]3628B[6]4122B[7]43-6B[8]61-15表示稀疏矩阵N的三列的二维数组A=B=三.矩阵的转置1)转置过程按照B数组中元素的最终排列顺序进行由于矩阵M的列经过转置后变为N的行,所以可以按照M的列序来转置。为了按顺序找到M中的每一列的所有非0元素,对数组A从第一行起将每行的第二列扫描n遍,每遍扫描分别找到矩阵N的从第一行到第n行的各行所有非0元素,并产生B数组相应的行。算法voidtransmat(A,B);{(m,n,t)=(A[0,1],A[0,2],A[0,3]);(B[0,1],B[0,2],B[0,3])=(n,m,t);if(t!=0){q=1;for(col=1;col=n;col++)for(p=1;p=t;p++)if(A[p][2]==col){B[q][1]=A[p][2];B[q][2]=A[p][1];B[q][3]=A[p][3];q++;}}}[1][2][3]A[0]668A[1]1115A[2]1422A[3]16-15A[4]2211A[5]233A[6]34-6A[7]5191A[8]63282)B数组中元素的生成不是顺序的而是跳跃式的即转换按数组A中行的顺序进行，但转换后的元素在B中不是连续存放，而是将它放入它在B中最终应占据的位置。设：Num[1..n]:存放矩阵m中各列非0元素的个数;Pot[1..n]:存放矩阵m中各列第一个非0元素在数组B中应占的位置。pot[1]=1pot[j]=pot[j-1]+num[j-1](2≤j≤n)1500220-150113000000-60000000091000000028000M=j123456Num[j]212201Pot[j]134688voidfasttranspo(A,B){(m,n,t)=(A[0][1],A[0][2],A[0][3]);(B[0][1],B[0][2],B[0][3])=(n,m,t);if(t!=0){for(j=1;j=n;j++)num[j]=0;for(i=1;i=t;i++)num[A[i,2]]=num[A[i,2]]+1;pot[1]=1;for(j=2;j=n;j++)pot[j]=pot[j-1]+num[j-1];for(i=1;i=t;i++){k=A[i][2];B[pot[k]][1]=A[i][2];B[pot[k]][2]=A[i][1];B[pot[k]][3]=A[i][3];pot[k]=pot[k]+1;}}}[1][2][3]A[0]668A[1]1115A[2]1422A[3]16-15A[4]2211A[5]233A[6]34-6A[7]5191A[8]6328★广义表若ai为不可再分割的原子元素，则称ai为原子元素；若ai为一个子表，则称ai为表元素。用小写字母表示原子元素，用大写字母表示表元素。一.广义表的基本概念广义表是一个长度n≥0的有限序列。记作LS=(a1,a2,……,an-1,an)其中，LS为广义表的名字,ai为表中元素；ai可以是原子元素，也可以是一个子表。n为表的长度，长度为0的表称为空表。当广义表非空时，称第一个元素a1为广义表的表头(Head)，称其余元素组成的表(a2,……,an-1,an)是广义表的表尾（Tail)。表的深度是指表中所包含的括号的层数。A=();长度为0的空表。B=(());是以空表作为唯一元素的表，长度为1。C=(a,b);有两个元素a,b长度为2。D=(a,(b,c));含有一个原子元素和一广义表，长度为2。E=(x,D,y);长度为3的广义表。F=(a,F);长度为2的递归的广义表。……广义表的例子：ababcxyabcaCDEDF表元素原子元素3.列表可以是一个递归的表，即列表可以是本身的一个子表。2.列表可以为其他表所共享。1.列表的元素可以是子表,而子表的元素还可以是子表,…。结论求下列广义表的运算结果：1.Head(p,w,h)2.tail(b,k,p,h)3.Head((a,b),(c,d))4.tail((a,b),(c,d))5.tail(Head((a,b),(c,d)))课堂练习二.广义表的链接表示法tagdatalink其中，tag为标志位,令1表示本结点为表结点0表示本结点为原子结点当tag=0时,data域存放相应原子元素的信息；当tag=1时，data域存放子表第一个元素对应的链结点的地址；link域存放本元素同一层的下一个元素所在链接点的地址，当本元素为所在层的最后一个元素时，link域为Null。flag={广义表一般采用链式存储结构，链结点的构造可以为A=()B=(())1^^BC=(a,b)0a0b^D=(a,(b,c))C0aD0b0c^1^E=(x,D,y)0xE10y^F=(a,F)0aF1^A=NULL