数组和广义表ppt课件.ppt

《数组和广义表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章数组和广义表数组的概念数组是由下标和值组成的序对的集合数组的定义由以下三部分组成：(1)数组的名称；(2)数组的维数及各维长度；(3)数组元素的数据类型；例：ElemTypea[m][n];数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值一维数组存储方式352749186054778341020123456789llllllllllLOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0a+i*laa11a12…a1na21a22…a2n…………am1am2…amnA=A

2、=(A1，A2，……，An)其中：Ai=(a1i，a2i，……，ami)(1≤i≤n)二维数组二维数组是数据元素为线性表的线性表。a11a12…a1na21a22…a2n…………am1am2…amnA=例如，元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23，在列上有一个列前驱a12和和一个列后继a32。二维数组二维数组通常有两种顺序存储方式：（1）行优先顺序:将数组元素按行排列（2）列优先顺序:将数组元素按列排列0m-10n-1(a)二维数组LOC[i,j]前面的元素个数=阴影部分的面积=整行数×每行元素个数+本行中LOC[i,j]前面的元素个数本行中LOC

3、[i,j]前面的元素个数每行元素个数整行数按行优先存储的寻址数组的存储结构——二维数组LOC[i,j]=LOC[0,0]+(m*i+j)*LijLoc(aijk)=Loc(a000)+(i×m2×m3+j×m3+k)×cn（n＞2）维数组一般也采用按行优先和按列优先两种存储方法。请自行推导任一元素存储地址的计算方法。数组的存储结构——多维数组矩阵的压缩存储特殊矩阵：矩阵中很多值相同的元素并且它们的分布有一定的规律。稀疏矩阵：矩阵中有很多零元素。压缩存储的基本思想是：⑴为多个值相同的元素只分配一个存储空间；⑵对零元素不分配存储空间。特殊矩阵和稀疏矩阵(a)下三角矩阵(b)存储说明(c)

4、计算方法aij在一维数组中的序号=阴影部分的面积=i×(i-1)/2+j0…i-1n-10…j-1…n-1aij每行元素个数12…iaij在本行中的序号aij第1行第2行…第i-1行对称矩阵的压缩存储矩阵的压缩存储对于下三角中的元素aij（i≥j），在数组中的下标k与i、j的关系为：k＝i×(i-1)/2＋j。上三角中的元素aij（i＜j），因为aij＝aji，则访问和它对应的元素aji即可，即：k＝j×(j-1)/2＋i。如何只存储非零元素？注意：稀疏矩阵中的非零元素的分布没有规律。特殊矩阵的压缩存储——稀疏矩阵稀疏矩阵的三元组表示法每一个非零元素所在的行号、列号和值组成一个三元组

5、(i，j，aij)，下列6个三元组表示了稀疏矩阵M的6个非零元素：（1，1，5）（1,3，8）（2，5，6）（3，1，8）（4，3，4）（5，6，3）稀疏矩阵typedefstruct{introw,col;　/*该非零元素的行、列下标*/ElemTypedata;/*该非零元素的值*/}TripleTp;typedefstruct{TripleTPelem[maxsize];/*非零元素三元组表*/intm,n,t;　　/*矩阵的行数、列数和非零元素个数*/}SpmatTp稀疏矩阵图3-6稀疏矩阵的三元组表示1.设置转置后矩阵B的行数、列数和非零元个数；2.在B中设置初始存储位置q

6、；3.for(col=最小列号;col<=最大列号;col++)3.1在A中查找列号为col的三元组；3.2交换其行号和列号，存入B中q位置；3.3q++；三元组顺序表操作——转置算法1voidTransMatrix(TriTupleTable*b，TriTupleTable*a){/*a和b是矩阵A、B的三元组表表示，求A转置为B*/intp，q，col；b->m=a->n；b->n=a->m；/*A和B的行列总数互换*/b->t=a->t；/*非零元总数*/if(a->t!=0){q=0；for(col=1；coln；col++)/*对A的每一列*/for(p=0；p

7、->t；p++)/*扫描A的三元组表if(a->data[p]．j==col){/*找列号为col的三元组*/b->data[q]．i=a->data[p].j；b->data[q]．j=a->data[p].i；b->data[q]．v=a->data[p].v；q++；}}}/*TransMatrix按照a.data中三元组的次序进行转置设置两个数组num[1..n]和pot[1..n]，分别存放在矩阵M中每一列的非零元素个数和每一列第1个非零元素在b