数组和广义表1数组的定义ppt课件.ppt

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

1、第5章数组和广义表5．1数组的定义二维数组：我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。例如。图5．1数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5．2数组的顺序表示和实现一．采用顺序存储结构：一般不作插入或删除操作,因此，采用顺序存储结构二．存储顺序：存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放数组的数据元素就有次序约定问题。对二维数组可有两种存储方式：1．以列序为主序(co

2、1umnmajororder)的存储方式，如图5．2(a)所示2．以行序为主序(rowmajororder)的存储方式，如图5．2(b)所示。三．元素存储位置计算：以行序为主序的二维数组存储结构为例:二维数组A中任一元素aij的存储位置可由下式确定LOC(i,j)＝LOC(0,0)十(b2×i十j)L(5-1)式中：b2是数组的第二维长度，即列数；L是每个数据元素占的存储单元个数；LOC(i,j)是aij的存储位置；LOC(0,0)是a00的存储位置，即二维数组A的基地址或基址。由于计算各个元素存储

3、位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。5．3矩阵的压缩存储压缩存储是指：为多个值相同的元只分配一个存储空间；对零元不分配空间。5．3．1特殊矩阵：一．对称矩阵：1．特点：aij=aji1≤i,j≤n2．存储：可压缩存储，不失一般性，以行主序存储下三角中的元（包括对角线上的元）。3．映像关系：以数组sa[n(n+1)/2]存储n阶对称矩阵A，称sa[n(n+1)/2]为n阶对称矩阵A的压缩存储。（图5.3）则sa[k]和矩阵元aij间关系：二．

4、三角矩阵：1．特点：下(上)三角矩阵指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵。2．存储：存储其下(上)三角中的元和常数c。3．映像关系：以数组sa[n(n+1)/2]存储，sa[0]可用来存储常数c三．对角矩阵：1．特点：所有的非零元都集中在以主对角线为中心的带状区域中。如图5．4所示。2．存储：亦可按某个原则(或以行为主，或以对角线的顺序)将其压缩存储到一维数组上。5．3．2稀疏矩阵：一．什么是稀疏矩阵：二．抽象数据类型稀疏矩阵的定义：（P96）三．稀疏矩阵压缩存储：只存

5、非零元。以图5.5矩阵为例1．三元组顺序表：#defineMAXSIZE12500//稀疏矩阵中非0元素的最大数目typedefstruct{inti,j;//非0元素的行号、列号ElemTypee;//非0元素的值}Triple;//三元组数据类型名typedefstruct{intmu，nu，tu;//稀疏矩阵的行数、列数、非0元素的数目Tripledata[MAXSIZE+1];//三元组数组，data[0]未用}TSMatrix;//三元组顺序表数据类型名矩阵转置运算：(1)将矩阵的行列值相

6、互交换；(2)将每个三元组中的i和j相互调换；(3)重排三元组之间的次序。实现第三条有两种处理方法：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。121213931-3361443245218611564-713-3161521122518319342446-76314算法5.1:StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//M为原三元组顺序表，行优先顺序T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(!

7、M.tu)returnFALSE;//三元组空q=1;for(col=1;col<=M.nu;col++)for(p=1;k<=M.tu;++p){if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;q++;}}returnOK;}这个算法主要的工作是在p和col的两重循环中完成的，故算法的时间复杂度为O(nu×tu)，即和M的列数和非零元的个数的乘积成正比。一般矩阵

8、的转置算法为for(col＝1;col＜=nu;++colfor(row＝1;row＜=mu;++rowT[col][row]＝M[row][col];其时间复杂度为O(mu×nu)。当非零元的个数tu和mu×nu同数量级时，算法5．1的时间复杂度就为O(mu×nu2)了(例如，假设在100×500的矩阵中有tu＝10000个非零元)，虽然节省了存储空间，但时间复杂度提高了，因此算法5．1仅适于tu<