数据结构课件第五章数组和广义表

第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义5.5广义表的存储结构5.1数组的定义数组是大家都已经很熟悉的一种数据类型，几乎所有高级语言程序设计中都设定了数组类型。本章，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。1.一维数组一维数组可以看成是一个线性表，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。5.1数组的定义2．二维数组如下图中，A是一个m行n列的二维数组.二维数组也可以看成是一个定长的线性表.a00a01…a0,n-1a10a11…a1,n-1A=am-1,0a…am-1,1m-1,n-1…………5.1数组的定义则A可以表示为这样一个线性表：A=(a0,a1,…,an-1)其中每个数据元素aj可以是一个列向量形式的线性表:aj=(a0j,a1j,…,am-1,j)(0≤j≤n-1）5.1数组的定义或者A可以表示为这样一个线性表：A=(a0,a1,…,am-1)其中，每个数据元素ai是一个行向量形式的线性表:ai=(ai0,ai1,ai2,…,ai,n-1)(0≤i≤m-1）3.多维数组同理,三维及以上的多维数组也可作类似分析。5.1数组的定义数组的基本操作数组一旦被定义，它的维数和维界就不能再改变，因此，数组的基本操作只能是初始化、存取元素、修改元素的值,而不能够有插入、删除等操作。因此，数组总是采用顺序存储结构。由于存储单元是一维的，那么二维的数组元素怎样存储到一维的内存中？有两种存储方式：一是以行序为主序的存储方式；二是以列序为主序的存储方式。5.2数组的顺序表示和实现例如二维数组A[m][n]按行优先方式存储：a00，a01,…,a0,n-1，a10，a11，...，a1,n-1，…,am-1,0,am-1,1,…,am-1,n-1a00a01…a0,n-1a10a11…a1,n-1A=am-1,0a…am-1,1m-1,n-1…………a00a01…a0,n-1a10a1,n-1a11……5.2数组的顺序表示和实现二维数组A[m][n]按列优先方式存储：a00，a10,…,am-1,0,a01，a11，...，am-1,1，…,a0,n-1,a1,n-1,…,am-1,n-1a00a01…a0,n-1a10a11…a1,n-1A=am-1,0a…am-1,1m-1,n-1…………a00a10…am-1,0a01am-1,1a11……5.2数组的顺序表示和实现由于二维数组的每个元素在内存中是顺序存储的，因此，只要知道第一个元素的存储地址，就可以求得其它元素的地址，如何求？以行优先存储为例，假设设a00的内存地址为LOC(a00)，每个元素占用t个字节，则元素aij的存储地址应为第一个元素的地址加上排在aij前面的元素所占用的字节数，而aij的前面有i行(0~i-1)共i×n个元素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素。则aij的内存地址按等差数列计算为：LOC(aij)=LOC(a00)+（i×n+j）×t5.3矩阵的压缩存储矩阵是它是很多科学与工程计算问题中研究的数学对象。高级语言中一般都用二维数组存储矩阵，但有时候，对于一些阶数很高的矩阵，如果在矩阵中有许多值相同的元素或者是零元素，则会浪费存储空间。为了节省存储空间，可以对这类矩阵进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律。稀疏矩阵：元素分布无规律，零元素较多。5.3.1特殊矩阵1.对称矩阵若一个n阶方阵A中元素满足下列条件：aij=aji其中1≤i,j≤n，则称A为对称矩阵。如：对称矩阵只需存储它的下三角元素或上三角元素。一共只用存储n(n+1)/2个元素即可。5.3.1特殊矩阵假设以一维数组sa[0…n(n+1)/2]（图示）作为n阶对称矩阵A的存储结构，将矩阵的下三角元素按行序存储到sa[]数组中.a11……an,n-2an,n-1an,n0123……2)1(+nn-32)1(+nn-22)1(+nn-1a21a22a31则矩阵元aij存储在sa[]数组中下标为多少(设为k)的位置上呢？5.3.1特殊矩阵有如下关系：i(i-1)/2+j－1当i=jj(j-1)/2+i－1当ijk＝{那么，aij和sa[k]之间的对应关系就可以由上面的表达式确定。由此，我们称sa[n(n+1)/2]为n阶对称矩阵A的压缩存储。(1≤i,j≤n)5.2.1特殊矩阵2．三角矩阵（1）上三角矩阵即矩阵上三角部分元素是随机的，而下三角部分元素全部相同（为某常数C）或全为0，具体形式如下：221n1211..................nnacccaacaaa2n压缩存储后其存储关系如下：k＝{(i-1)*(2n-i+2)/2+j-i当i≤j(1≤i,j≤n)n(n+1)/2当ij5.2.1特殊矩阵222111.....................nnn1aaacaaccan2（2）下三角矩阵即矩阵下三角部分元素是随机的，而上三角部分元素全部相同（为某常数C）或全为0，具体形式如下：压缩存储后其存储关系如下：k＝{i(i-1)/2+j-1当i≥j(1≤i,j≤n)n(n+1)/2当ij5.3.1特殊矩阵3.对角矩阵若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。我们仅讨论三对角矩阵的压缩存储，其他可作类似分析。5.2.1特殊矩阵例如，下图为77的三对角矩阵（即有三条对角线上元素非0）。77766766655655544544433433322322211211000000000000000000000000000000aaaaaaaaaaaaaaaaaaa5.2.1特殊矩阵在一个nn的三对角矩阵中，一共有n+n-1+n-1=3n-2个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。即将其按行优先的顺序压缩存储在数组sa[3n-2]中,其存储示意图如下：即sa[k]与aij的对应关系为：k＝2(i-1)＋j-1数组sa中的元素sa[k]与三对角矩阵中的元素aij存在一一对应关系。a11……an-1,nan,n-1an,nk=0123……3n-3a12a21a223n-43n-55.3.2稀疏矩阵在上节提到的特殊矩阵中，元素的分布呈现某种规律，故一定能找到一种合适的方法，将它们进行压缩存放。但是，在实际应用中，我们还经常会遇到一类矩阵：其矩阵阶数很大，非零元个数较少，零元很多，而且非零元的排列没有一定规律，我们称这类矩阵为稀疏矩阵。按照压缩存储的概念，只需要存放稀疏矩阵中的非零元素，但由于它们的位置没有某种规律，因此，除了存放非零元的值外，还必须同时记下它所在的行和列的位置（i,j)。5.3.2稀疏矩阵由此，一个稀疏矩阵可由表示非零元的三元组序列和矩阵的行数、列数唯一确定。如下例：A：稀疏矩阵M6×7B：稀疏矩阵T7×65.3.2稀疏矩阵三元组线性表((1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7))，再加上（6,7,8）（行数、列数、非零元个数）项，便可作为矩阵M的存储描述了。同样，矩阵T也可作类似表示。三元组线性表可以采用顺序存储方式，也可以采用链式存储结构，对应的也就是稀疏矩阵常用两种压缩存储方式：三元组顺序表和十字链表.重点介绍三元组顺序表。5.3.2稀疏矩阵一、三元组顺序表此时，数据类型可描述如下：#definemaxsize12500//定义非零元的最大数目typedefstruct//定义一个三元组{inti,j;//非零元行号、列号intv;//非零元的值}Triple;typedefstruct{//定义稀疏矩阵Tripledata[maxsize];//三元组表intm,n,t;//稀疏矩阵行、列数、非零元个数}TSMatrix;TSMatrixM，N；5.3.2稀疏矩阵在结构体数组M.data[]中，表示非0元的三元组是以行序为主序排列的。其中，M.data[0]未用，可把行列值及非0元个数存入其中。M.data[0].i=6M.data[0].j=7M.data[0].v=80123456780123456785.3.2稀疏矩阵下面主要讨论稀疏矩阵在采用三元组顺序表的存储结构下的转置运算。转置是矩阵中最简单的一种运算。对于一个mn的矩阵M，它的转置矩阵N是一个nm的矩阵，且M[i][j]=N[j][i]，0i≤m,0j≤n。显然，稀疏矩阵的转置矩阵仍然是稀疏矩阵。那么用三元组顺序表存储的稀疏矩阵，要求得它的转置矩阵，也就是要求出它的转置矩阵所对应的三元组顺序表。5.3.2稀疏矩阵如何由M.data[]得到N.data[]呢？可以将M.data[]中所有三元组的i和j的值互换，则得到的N.data[]是一个按列优先顺序排列的三元组表，然后再将它按行序排序，即得到转置矩阵N的三元组顺序表。但对数组的元素进行排序的时间复杂度将会达到平方级。下面将介绍另外两种处理方法5.3.2稀疏矩阵（1）按照M的列序进行转置由于M的列即为N的行，因此，在M.data[]中，按列值顺序进行扫描，则得到的N.data[]一定是按行优先存放的。方法：扫描M.data[]第1趟，找出M中所有第1列的非0元素，交换行列值后，存入N.data[]。然后再扫描M.data[]第2趟，找出M中第2列的所有非0元素，交换行列值后，存入N.data[]。依次类推，M共有多少列，则扫描多少趟。为了能找出每一列中的所有非0元素，每趟扫描都必须从M.data[]的第一行读到最后一行。5.3.2稀疏矩阵678121213931－3361443245218611564－701234567801234567876813-3161521122518319342446-76314i(行）j(列)v(非0值)i(行）j(列)v(非0值)5.3.2稀疏矩阵算法描述如下：voidTransposeSMatrix(TSMatrixM,TSMatrix&N){intc,p,q=1;/*q存储当前转置得到的三元组应放在N.data[]中的下标号*/N.m=M.n;N.n=M.m;N.t=M.t;if(N.t!=0){for(c=1;c=M.n;c++)/*按列号扫描*/}for(p=1;p=M.t;p++)/*对三元组扫描*/if(M.data[p].j==c)/*找到第c列，进行转置*/{}N.data[q].i=M.data[p].j;N.data[q].j=M.data[p].i;N.data[q].v=M.data[p].v;q++;}5.3.2稀疏矩阵分析这个算法，主要的工作是在一个双重循环中完成的，故算法的时间复杂度是O(n*t),即和矩阵的列数和非零元个数乘积成正比。而通常的m×n阶矩阵转置算法可描述为：for(row=0;rowm;row++)for(col=0;coln;col++)b[col][row]=a[row][col];它的时间复杂度为O(m×n)。而一般的稀疏矩阵中非零元个数t通常远大于行数m，故压缩存储时，进行转置运算，虽然节省了存储单元，但增大了时间复杂度，因此此算法仅适用于tm*n的情况。5.3.2稀疏矩阵（2）快速转置算法按照M.data[]中的三元组的次序进行转置，并将转置后的三元组直接放入它应该在N.data[]中的位置上。为了确定这些位置，在转置前，我们应先求得M的每一列中的非零元的个数，进而便可求得每一列的非零元在N.data[]中的位置了。5.3.2稀疏矩阵在此，需要附设num[