《数组与广义表》PPT课件

第五章数组,5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义与存储,5.1数组的定义,维数和维界二维数组的类型定义:等价于typedefElemTypeArray1n;typedefArray1Array2m;typedefElemTypeArray2mn;Array2A;二维的数组=定长的线性表a11a12a13.a1na21a22a23.a2nAmxn=.am1am2am3.amnAmxn=(a11,a12,a13,.a1n),(a21,a22,a23,.a2n),.,(am1,am2,am3,.amn),数组的抽象数据类型,ADTArray数据对象：D=aj1j2.jn|n(0)称为数组的维数,bi是数组第i维的长度,ji是数组元素的第i维下标,aj1j2.jnElemset数据关系：R=R1,R2.RnRi=aj1.ji.jn,aj1.ji+1.jn|0jkbk-1,1kn,aj1.ji.jn,aj1.ji+1.jnD。基本操作：InitArray(Assign(求元素A3454的地址.LOC3,4,5,4=2000+(6*7*8*3+7*8*4+8*5+4)*2=2000+(336*3+56*4+8*5+1*4)*2=2000+(1008+224+40+4)*2=4552,列序为主序:(FORTRAN),Amxn=(a11,a21,a31,.am1),(a12,a22,a32,.am2),.(a1n,a2n,a3n,.amn)LOC1,1为基地址:LOCi,j=LOC1,1+(m*(j-1)+i-1)*L(1=i=m,1=j=n,每个数据元素占L个存储单元)例5.2:若L=2,LOC1,1=1000LOC3,4=LOC1,1+(4*(4-1)+3-1)*L=1000+14*2=1028LOC0,0为基地址:LOCi,j=LOC0,0+(m*j+i)*L(0=i=m,0=j0)nSqSum+=(n*n);n=va_arg(arg_ptr,int);va_end(arg_ptr);returnnSqSum;/调用时intnSqSum=SqSum(7,2,7,11,-1);,可变参数函数的原型声明格式为：typeVAFunction(typearg1,typearg2,);参数可以分为两部分：个数确定的固定参数和个数可变的可选参数。函数至少需要一个固定参数，固定参数的声明和普通函数一样；可选参数由于个数不确定，声明时用表示。固定参数和可选参数公同构成一个函数的参数列表。借助上面这个简单的例2，来看看各个va_xxx的作用。va_listarg_ptr：定义一个指向个数可变的参数列表指针；va_start(arg_ptr,argN)：使参数列表指针arg_ptr指向函数参数列表中的第一个可选参数，说明：argN是位于第一个可选参数之前的固定参数，（或者说，最后一个固定参数；之前的一个参数），函数参数列表中参数在内存中的顺序与函数声明时的顺序是一致的。如果有一va函数的声明是voidva_test(chara,charb,charc,)，则它的固定参数依次是a,b,c，最后一个固定参数argN为c，因此就是va_start(arg_ptr,c)。,va_arg(arg_ptr,type)：返回参数列表中指针arg_ptr所指的参数，返回类型为type，并使指针arg_ptr指向参数列表中下一个参数。va_copy(dest,src)：dest，src的类型都是va_list，va_copy()用于复制参数列表指针，将dest初始化为src。va_end(arg_ptr)：清空参数列表，并置参数指针arg_ptr无效。说明：指针arg_ptr被置无效后，可以通过调用va_start()、va_copy()恢复arg_ptr。每次调用va_start()/va_copy()后，必须得有相应的va_end()与之匹配。参数指针可以在参数列表中随意地来回移动，但必须在va_start()va_end()之内。,StatusDestroyArray(Array,销毁数组A,若ap所指的各下标值合法,则求出该元素在A中的位置,StatusLocate(ArrayA,va_listap,int,i,off,A是n维数组,e为元素变量,随后是n个下标值;若各下标不超界,则e赋值为所指定的A的元素值,并返回OK,StatusValue(ArrayA,ElemType,i,off,e,A是n维数组,e为元素变量,随后是n个下标值;若各下标不超界,则将e的值赋给所指定的A的元素,并返回OK,StatusAssign(Array,i,off,主程序及例子,main()ArrayA;inti,j,e;InitArray(,实验与习题,理论习题5.1,5.2,5.3,5.65.8实验题:写一个主程序来上机验证数组的顺序存储结构的四个基本操作；并计算A=B+C34569753B=78910C=24681234369125.18,5.3矩阵的压缩存储,矩阵:二维数组特殊矩阵:大量重复元素或大量0元素稀疏矩阵:大量0元素压缩存储:重复元素只分配一个存储空间,0元素不分配存储空间,5.3.1特殊矩阵,对称矩阵:aij=aji(11时,aij=0,(1=i,j=n),对称矩阵:aij=aji(1=i,j=jk=j(j-1)/2+i当ij,例5.3对称矩阵,n=5,1+2+3+4+5=5*(5+1)/2=15一维数组SA1.15作为数组A的存储结构:SA=(452313252816795)如:a5,3=a3,5=7k=5(5-1)/2+3=13故:sa13=7,下三角矩阵:当ij时,aij=0,(1=i,j=j)0(当i1时,aij=0,(1=i,j=n),a11a1200.0a21a22a230.0Anxn=0a32a33a34.0.000.ann-1ann一维数组SA1.3*n-2作为数组A下三角元素的存储结构:SAk=a11,a12,a21,a22,a23,a32,a33,a34,.,ann-1,annk=123456783n-33n-2,sak和ai,j的一一对应关系:sak,k=3*(i-1)+j-i+1,ai,j=当|i-j|1,例5.5三对角矩阵,4300052200A=010400028700095一维数组SA1.3*5-2作为数组A的存储结构:SA=(4352210428795)如:a5,4=9k=3*(5-1)+4-5+1=12故:sa12=9,5.3.2稀疏矩阵通常稀疏因子0.05时称为稀疏矩阵.,例5.60129000000-30015000000012000180M=-30000140900240000240000T=00000-7018000000000001500-70000014000000000M:muxnu(6x7)T:nuxmu(7x6)M是T的转置,稀疏矩阵的存储结构一.三元组顺序表,M:ijeT:ije121213-3139161531-3211236142518432431952183424611546-764-76314,三元组顺序表结构定义,#defineMAXSIZE12500typedefstructinti,j;Elemtypee;Triple;typedefstructTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;TSMatrixM,T;,M.datap.i.j.e,012.,maxsize,求稀疏矩阵M的转置矩阵TTSMatrixM,T;,012345678,012345678,M.datap.i.j.e,T.dataq.i.j.e,求稀疏矩阵M的转置矩阵T,StatusTransposeSMatrix(TSMatrixM,TSMatrix/TransposeSMatrix,求稀疏矩阵转置的算法复杂度,其算法复杂度是O(nu*tu)而一般矩阵的转置算法的复杂度是O(mu*nu):for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;所以,当tu=mu*nu时,算法复杂度是O(nu*nu*mu)当tumu*nu时,才适用,求稀疏矩阵M的转置矩阵T的快速方法,为了减少算法复杂度,增加两个向量num和cpot:numcol:M中第col列中非零元素的个数;cpotcol:M中第col列中的第一个非零元素在T.data中的位置;有:cpot1=1;cpotcol=cpotcol-1+numcol-12=col=m.nu,例5.60129000000-30015000000012000180M=-30000140900240000240000T=00000-7018000000000001500-70000014000000000例5.6的向量num和cpot:col1234567num2221010cpot1357889,StatusFastTransposeSMatrix(TSMatrixM,TSMatrix/FastTransposeSMatrix,col1234567num2221010cpot1357889,求稀疏矩阵转置的快速算法的算法复杂度,其算法复杂度是O(nu+tu)当tu=mu*nu时,算法复杂度是O(nu*mu)当tumu*nu时,时间复杂度将小得多,#defineMAXRC100typedefstructinti,j;Elemtypee;Triple;typedefstructTripledataMAXSIZE+1;intrposMAXRC+1;intmu,nu,tu;RLSMatrix;,二.行逻辑链接的顺序表指出每一行的第一个非零元素在三元组中的位置,M.rposrow,例5.7矩阵的乘法Q=MxNM:m1xn1N:m2xn2当n1=m2时,求两个稀疏矩阵的乘积的算法,Q初始化;if(M和N均是非零矩阵)for(arow=1;arow=M.mu;+arow)ctemp=0;计算Q中第arow行的积并存入ctemp中;将ctemp中非零元压缩存储到Q.data;,StatusMultiSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix,时间复杂度:ctemp的时间复杂度是O(M.muXN.nu);,求Q所有非零元的时间复杂度是O(M.tuXN.tu/N.mu);压缩存储的时间复杂度是O(M.tuXN.tu/N.mu);时间复杂度是:O(M.muXN.nu+M.tuXN.tu/N.mu);for(i=1;i=m1;+i)for(j=1;jrow_headi=p;else/*寻找行表中的插入位置*/for(q=M-row_headi;q-right/*完成插入*/,5.4广义表,广义表也是线性表的一种推广。广义表也是n个数据元素（d1，d2，d3，dn）的有限序列，但不同的是，广义表中的di既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，dn）。GL是广义表的名字，通常用大写字母表示。n是广义表的长度。若di是一个广义表，则称di是广义表GL的子表。在GL中，d1是GL的表头，其余部分组成的表（d2，d3，dn）称为GL的表尾。由此可见，广义表的定义是递归定义的。,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)，广义表的表尾一定是一个表。,从上面的例子可以看出：,（1）广义表的元素可以是子表，而子表还可以是子表，由此，广义表是一个多层的结构。,（2）广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。,（3）广义表具有递归性，如广义表C。,广义表中有两类结点，一类是单个元素结点，一类是子表结点。任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点只需要两个域：标志域和值域。,广义表A、B、C、D的存储结构图,形式说明如下：,/*广义表的头尾链表存储结构*/0-89typedefenumATOM,LISTElemTag;/*ATOM0，表示原子；LIST1，表示子表*/typedefstructGLNodeElemTagtag;/*标志位tag用来区别原子结点和表结点*/unionAtomTypeatom;/*原子结点的值域atom*/structstructGLNode*hp,*tp;htp;/*表结点的指针域htp，包括表头指针域hp和表尾指针域tp*/atom_htp;/*atom_htp是原子结点的值域atom和表结点的指针域htp的联合体域*/*GList；,另外，还有一种广义表存储结构，在这种结构中，无论是单元素结点还是子表结点均由三个域构成。其结点结构图为：,广义表的第二种存储结构图,type