第5章数组和广义表5.1数组的定义

第5章

数组和广义表5．1数组的定义

二维数组：我们可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。例如。图5．1

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。5．2数组的顺序表示和实现一．采用顺序存储结构：一般不作插入或删除操作,因此，采用顺序存储结构二．存储顺序：存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放数组的数据元素就有次序约定问题。

对二维数组可有两种存储方式：1．以列序为主序(co1umnmajororder)的存储方式，如图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的基地址或基址。由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。

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

ElemTypee;//非0元素的值}Triple;//三元组数据类型名typedefstruct{ intmu，nu，tu;//稀疏矩阵的行数、列数、非0元素的数目

Tripledata[MAXSIZE+1];//三元组数组，data[0]未用}TSMatrix;//三元组顺序表数据类型名矩阵转置运算：(1)将矩阵的行列值相互交换；(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(!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的列数和非零元的个数的乘积成正比。一般矩阵的转置算法为

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<<mu×nu的情况。(2)快速转置：需两个向量:num和cpotnum[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。则有cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1]2≤col≤a.nu例如，对图5.5的矩阵M，num和cpot的值如表5.1所示（下页图）1234567813-3161521122518319342446-76314000000011112221135788946297538算法5.2：StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu; T.nu=M.mu;T.tu=M.tu; if(!M.tu)returnFALSE;//三元组空

for(col=1;col<=M.nu;col++)num[col]=0;for(t=1;t<=M.tu;t++)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1]; for(p=1;k<=M.tu;++p){ col=M.data[p].j;q=cpot[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;++cpot[col]; }//得到的T也是三元组顺序表，行优先顺序

returnOK; }该算法比算法5.1多用了两个辅助向量。时间复杂度为O(nu+tu)。当非零元的个数tu和mu×nu同数量级时，算法5.2的时间复杂度为O(mu×nu)。三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需按行号存取某一行的非零元，则需从头开始进行查找。2．行逻辑链接的顺序表：为了便于随机存取任意一行的非零元，则需知道每一行的第一个非零元在三元组表中的位置。为此可将上节快速转置矩阵的算法中创建的指示“行”信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种“带行链接信息”的三元组表为行逻辑链接的顺序表，其类型描述如下；typedefstruct{intmu，nu，tu;//稀疏矩阵的行数、列数、非0元素的数目

Tripledata[MAXSIZE+1];//三元组数组，data[0]未用

intrpos[MAXRC+1];//各行第一个非零元的位置表}TSMatrix;//三元组顺序表数据类型名3．十字链表：当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。采用链式存储结构表示三元组的线性表更为恰当。例如，将矩阵B加到矩阵A上1)表示和实现：typedefstructOLNode{inti,j;ElemTypee;structOLNode*right,*down;}OLNode;*OLink;typedefstruct{OLink*rhead,*cheak;intmu,nu,tu;}CrossList;ijerightdown十字链表的结点结构

3005M=0-1002000算法5.4：创建稀疏矩阵，用十字链表存储表示StatusCreateSMatrix_OL(CrossList&M){if(M)free(M);scanf(&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;if(!(M.rhead=(OLink*)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);if(!(M.chead=(OLink*)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);M.rhead[]=M.chead[]=NULL;for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)){if(!(p=(OLNode*)malloc(sizeof(OLNode))))exit(OVERFLOW);p-->i=i;p-->j=j;p-->e=e;if((M.rhead[i]==NULL||M.rhead[i]-->j>j){p-->right=M.rhead[i];M.rhead[i]=p;}else{for(q=M.rhead[i];(q-->right)&&q-->right-->j<j;q=q-->right);p-->right=q-->right;q-->right=p;}if(M.chead[j]==NULL||M.chead[j]-->i>i){p-->down=M.chead[j];M.chead[j]=p;}else{for(q=M.chead[j];(q-->down)&&q-->down-->i<i;q=q-->down);p-->down=q-->down;q-->down=p;}}returnOK;}//CreateSMatrix_OL2)将矩阵B加到矩阵A上:十字链表表示稀疏矩阵假设两个矩阵相加后的结果为A'，则和矩阵A'中的非零元“aij'’可能有以下情况：1．aij'=aij+bij

改变结点的e域值2．aij'=aij(bij=0)结点不变3．aij'=bij(aij=0)增加结点4．aij'=0(aij=-bij)删除结点5.4广义表的定义广义表是线性表的推广。一．抽象数据类型广义表定义：(P107)二．术语：广义表记作LS=(a1,a2,…,an)LS是广义表的名称，n是其长度。ai可以是单个元素（原子），也可以是广义表（子表）。习惯上用大写字母表示广义表的名称，用小写字母表示原子。广义表非空时，称第一个元素a1为其表头，称其余元素组成的表（a2,…,an）为其表尾。例：(1)A＝()—A是一个空表，它的长度为零。(2)B＝(e)—列表B只有一个原子e，B的长度为1。(3)C＝(a，(b，c，d))—列表C的长度为2，两个元素分别为原子a和子表(b，c，d)。(4)D＝(A，B，C)—列表D的长度为3，三个元素都是列表。显然，将子表的值代入后，则有

D＝(()，(e)，(a，(b，c，d)))。(5)E＝(a，E)—这是一个递归的表，它的长度为2。E相当于一个无限的列表E＝(a，(a，(a，…)))。三．三个重要结论：(1)列表的元素可以是子表，而子表的元素还可以是子表，…。(2)列表可为其它列表所共享。(3)列表可以是一个递归的表，即列表也可以是其本身的一个子表。

根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定为列表。

A＝()B＝(e)C＝(a，(b，c，d))D＝(A，B，C)E＝(a，E)例如：

GetHead(B)=eGetTail(B)＝()GetHead(D)＝AGetTail(D)＝(B，C)由于(B，C)为非空列表，则可继续分解得到：GetHead((B,C))＝BGetTail((B,C))＝(C)列表()和(())不同。前者为空表、长度n＝0；后者长度n＝1，可分解得到其表头、表尾均为空表()。5.5广义表的存储结构由于广义表中的数据元素可以具有不同的结构，(或是原子，或是列表)，因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据