第5章数组和广义表

第5章数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。5.1数组的定义和特点定义数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()5.2数组的顺序表示和实现次序约定以行序为主序以列序为主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)*n+j-1]*l

按行序为主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

按列序为主序存放01m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)*m+i-1)]*l

5.3矩阵的压缩存储矩阵是很多科学与工程计算问题中研究的数学对象,本节讨论如何存储矩阵的元,从而对矩阵进行各种有效运算；对一些特殊矩阵我们可以用很少的空间来存储以到达压缩的目的。5.3.1特殊矩阵对称矩阵〔相同元素取一次，实现了压缩〕

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：三角矩阵

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对角矩阵

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：M由{(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〕唯一确定5.3.2稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原那么：只存矩阵的行列维数和每个非零元的行列下标及其值稀疏程度的计算：稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数利用三元组表求稀疏矩阵的转置〔1〕P98~996

7

8

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值带辅助行向量的二元组增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元在二元组表中的起始地址〔m为行数〕显然有：NRA[1]=1NRA[i]=NRA[i-1]+第i-1行非零元个数(i2)0123456NRA1335676

7

8

212391-36143242181154-7majv012345678矩阵列数和非零元个数列下标和非零元值NRA[0]不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+1伪地址表示法伪地址：本元素在矩阵中〔包括零元素在内〕按行优先顺序的相对位置〔如-3,按行优先顺序为15〕

6

7

2123915-3201424243018361539-7maaddrv伪地址非零元值矩阵行列维数012345678伪地址表示法需存储单元个数为2(t+1)求转置矩阵P98问题描述：一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)n[col][row]=m[row][col];T(n)=O(mn)对于一个m×n的矩阵M，它的转置矩阵T是一个n×m矩阵，且T(i,j)=M(j,i)，1≤i≤n，1≤j≤m。一个稀疏矩阵的转置矩阵仍然是稀疏矩阵。例：上述矩阵M＝的转置矩阵为：T＝由a转置到b只需：i.将矩阵的行列值相互交换；ii.将每个三元组中的i和j相互调换； iii.重排三元组之间的次序便可实现矩阵的转置。(6×7)6行7列(7×6)7行6列 (7×6)7行6列

ijvaluei(j)j(i)valuei(j)j(i)value

12 12211213－313 9319161531 －313－3211243 24342431952 182518342461 15161546－7i.和ii.iii.36 146314251864－746－76314假设a和b是TSMatrix型的变量，分别表示矩阵M和T。图5.5 矩阵a转置到矩阵b的过程实现方法：i.直接取顺序存算法思想：按照b.data中三元组的次序依次在a.data中找到相应的三元组进行转置。算法5.1如下：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ //采用三元组表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){ q=1; for(col=1;col<=M.nu;++col) for(p=1;p<=M.tu;++p) if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].j; T.data[q].e=M.data[p].e; ++q; } } returnOK;}//TransposeSMatrixMrow

colelem

1

212

1

39

3

1–3

3

614

4

324

5

218

6

115

6

4-7M’row

colelem

2

112

3

19

1

3–3

6

314

3

424

2

518

1

615

4

6-7Mrow

colelem

1

212

1

39

3

1–3

3

614

4

324

5

218

6

115

6

4-7M’row

colelem

1

3

-3

1

615

2

112

2

5

18

3

19

3

424

4

6-7

6

3146

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2

时间复杂度：O(nu×tu)，即和M的列数及非零元的个数的乘积乘正比。当非零元的个数tu和mu×nu同数量级时，算法5.1的时间复杂度就为O(mu×)了（例如，假设在100×500的矩阵中有tu＝10000个非零元），虽然节省了存储空间，但时间复杂度提高了。因此，该算法仅适于tu<<mu×nu的情况。ii.顺序取直接存 算法思想：按照a.data中三元组的次序进行转置，并将转置后的三元组置入b中适当的位置。在此，附设了num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数，cpot[col]指示M中第col列的第一个非零元在b.data中的恰当位置。显然有：cpot[1]=1;cpot[col]=cpot[col－1]+num[col－1]2≤col≤a.nu例如，对上述矩阵M，num和cpot的值如表5.1所示。表5.1 矩阵M的向量cpot的值col 1 2 3 4 5 6 7num[col] 2 2 2 1 0 1 0cpot[col]1 3 5 7 8 8 96

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp4629753StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){ //采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){ for(col=1;col<=M.nu;++col) num[col]=0; for(t=1;t<=M.tu;++t) ++num[M.data[t].j]; //求M中每一列含非零元个数 cpot[1]=1; //求第col列中第一个非零元在b.data中的序号 for(col=2;col<=M.nu;++col) cpot[col]=cpot[col－1]+num[col－1]; for(p=1;p<=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]; }//for }//if returnOK;}//FastTransposeSMatrix算法5.2时间复杂度：O(nu＋tu).在M的非零元个数tu和mu×nu等数量级时,其时间复杂度为O(mu×nu).②行逻辑链接的顺序表1．定义行逻辑链接的顺序表：带行链接信息的三元组表。2．C语言描述typedefstruct{ Triple data[MAXSIZE+1]; //非零元三元组表 int rpos[MAXRC+1]; //各行第一个非零元的位置表 int mu,nu,tu; //矩阵的行数、列数和非零元个数}RLSMatrix3．矩阵相乘运算时间复杂度是O()i.经典算法若设Q=M×N，其中，M是矩阵，N是矩阵。当n1＝m2时有： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j){ Q[i][j]=0; for(k=1;k<=n1;++k) Q[i][j]+=M[i][k]*N[k][j]; } ii.稀疏矩阵相乘算法当M和N是稀疏矩阵并用三元组表作存储结构时，不能套用上述算法。例如，×

=两个稀疏矩阵相乘所得的乘积矩阵不是稀疏矩阵，故乘积矩阵不应采用压缩存储，而应以二维数组表示。算法思想：对于M中每个元素M.data[p](p=1,2,…,M.tu)，找到N中所有满足条件M.data[p].j=N.data[q].i〔即M.data中的j值和N.data中的i值相等〕的元素N.data[q]，求得M.data[p].v和N.data[q].v的乘积。乘积矩阵Q中每个元素的值是个累计和，这个乘积M.data[p].v×N.data[q].v只是Q[i][j]中的一局部。为便于操作，并对每个元素设一累计和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。乘积矩阵Q中的元素是否为非零元，只有在求得其累加和后才能得知。由于Q中元素的行号和M中元素的行号一致，又M中元素排列是以M的行序为主序的，由此可对Q中元素进行逐行处理，先求得累计求和的中间结果〔Q的一行〕，然后再压缩存储到Q.data中去。

找M.data中的j值和N.data中的i值相等的非零元相乘。如：P101的M.data[1]:1,1,3中的j=1N.data[1]:1,2,2中的i=1那么这两个非零元值相乘得6，该值为乘积矩阵的第1行第2列。如此下去，只进行三次的乘积运算即可得矩阵的积。结论：两个稀疏矩阵的乘积不一定是稀疏矩阵。

StatusMlutSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){ //求矩阵乘积Q=M×N，采用逻辑链接存储表示。 if(M.nu!=N.mu) returnERROR; Q.mu=M.mu; Q.nu=M.nu; Q.tu=0; //Q初始化 if(M.tu*N.tu!=0){ //Q是非零矩阵 for(arow=1;arow<=M.mu;++arow){ //处理M的每一行 ctemp[]=0; //当前各元素累加器清零 Q.rpos[arow]=Q.tu+1;if(arow<M.mu) tp=M.rpos[arow+1];两个稀疏矩阵相乘(Q=M×N)的过程可大致描述如下：Q初始化；if(Q是非零矩阵){ //逐行求积 for(arow=1;arow<=M.mu;++arow){ //处理M的每一行 ctemp[]=0; //累加器清零 计算Q中第arow行的积并存入ctemp[]中； 将ctemp[]中非零元压缩存储到Q.data；}//forarow}//if算法5.3是上述过程求精的结果。算法5.3如下： else tp=M.tu+1; for(p=M.rpos[arow];p<tp;++p){

//为当前行中每一个非零元找到对应元在N中的行号 brow=M.data[p].j; if(brow<N.mu) t=N.rpos[brow+1]; else t=N.tu+1; for(q=N.rpos[brow];q<t;++q){ ccol=N.data[q].j; //乘积元素在Q中的列号 ctemp[ccol]+=M.data[p].e*N.data[q].e; }//forq }//求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol<=Q.nu;++ccol) //压缩存储该行非零元 if(ctemp[ccol]){ if(++Q.tu>MAXSIZE) returnERROR; Q.data[Q.tu]=(arow,ccol,ctemp[ccol]); }//if }//forarow }//ifreturnOK;}//MlutSMatrix时间复杂度：O(M.mu×N.nu+M.tu×N.tu/N.mu)。其中累加器ctemp初始化的时间复杂度为O(M.mu×N.nu)，求Q的所有非零元的时间复杂度为O(M.tu×N.tu/N.mu)，进行压缩存储的时间复杂度为O(M.mu×N.nu)。链式存储结构带行指针向量的单链表表示每行的非零元用一个单链表存放设置一个行指针数组，指向本行第一个非零元结点；假设本行无非零元，那么指针为空表头结点与单链表结点类型定义typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存储单元个数为3t+m十字链表1．定义

十字链表：在链表中，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，这个矩阵构成了一个十字交叉的链表结构。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。2．结点结构rowcolvaldownright其中，row，col和val分别表示该非零元所在的行、列和非零元的值。right域，用以链接同一行中下一个非零元。down域，用以链接同一列中下一个非零元。结点定义tpedefstructnode{introw,col,val;structnode*down,*right;}JD;113418225234^^^^^^^217^^从键盘接收信息建立十字链表算法算法分析：T(n)=o(ts)

其中：t——非零元个数

s=max(m,n)令q=NULL,p=rh[r-1],〔1〕寻找插入位置：当p!=NULL且c>p->col时，p和q右移〔2〕插入：a、假设p==NULL且q==NULL，即本行空，那么rh[r-1]==s;b、假设p==NULL,q!=NULL，即走到行末，那么q->right=sc、假设c==p->col，那么修改p->vald、假设c<p->col且q==NULL，那么在p之前插入s，即s是行链表中第一个结点，令rh[r-1]=s;s->right=p;e、假设c<p->col且q!=NULL，那么在p之前插入s，即s->right=p;q->right=s;418^^234^^m=4,n=31,1,32,1,72,2,52,3,44,1,8Ch4_3.c113^^217^^225^^

例：写出矩阵的三元组表和十字链表

5

6

6

115144168233347516三元组表ijv0123456115^516^^^347^^144168^233^^^^十字链表5.4广义表的定义（1）定义广义表又称列表，是线性表的推广。一般记作：其中，LS是广义表的名称（用大写字母表示），n是它的长度。可以是单个元素，也可以是另一个广义表。原子：广义表LS中是单个元素，则称为原子。用小写字母表示。

子表：广义表LS中是广义表，则称为子表。

表头（Head）：当广义表LS非空时，其第一个元素即为表头。表尾（Tail）：广义表LS中除表头元素外，其余元素组成的表。由表头、表尾的定义易知：任何一个非空列表其表头可能是原子，也可能是列表，而其表尾必定是列表。广义表的长度：表中元素的个数，深度：层次数，即括号的个数。例如：①A=()——A是一个空表，它的长度为零，深度为1。②B=(e)——列表B只有一个原子e，B的长度为1，深度也为1。③C=(a,(b,c,d))——列表C的长度为2，深度为2，两个元素分别为原子a和子表(b,c,d)。④D=(A,B,C)——列表D的长度为3，深度为1，3个元素都是列表。将子表的值带入后，那么有D=((),(e),(a,(b,c,d)))。⑤E=(a,E)——这是一个递归的表，它的长度为2，深度为∞。E相当于一个无限的列表E=(a,(a,(a,…)))。〔2〕广义表的抽象数据类型定义ADTGList{ 数据对象：D={ei|i=1,2,…,n；n≥0；ei∈AtomSet或ei∈GList;} 数据关系：R1＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n} 根本操作： InitGList(&L); 操作结果：创立空的广义表L。 CreateGList(&L,S); 初始条件：S是广义表的书写形式串。 操作结果：由S创立广义表L。DestroyGList(&L); 初始条件：广义表L已存在。 操作结果：销毁广义表L。CopyGList(&T,L); 初始条件：广义表L已存在。 操作结果：由广义表L复制得到广义表T。GListLength(L); 初始条件：广义表L已存在。 操作结果：求广义表L的长度，即元素个数。GListDepth(L); 初始条件：广义表L已存在。 操作结果：求广义表L的深度。GListEmpty(L); 初始条件：广义表L已存在。 操作结果：判定广义表L是否为空。GetHead(L); 初始条件：广义表L已存在。 操作结果：取广义表L的头。GetTail(L); 初始条件：广义表L已存在。 操作结果：取广义表L的尾。InsertFirst_GL(&L,e); 初始条件：广义表L已存在。 操作结果：插入元素e作为广义表L的第一个元素。DeleteFirst_GL(&L,&e); 初始条件：广义表L已存在。 操作结果：删除广义表L的第一个元素，并用e返回其值。Traverse_GL(L,visit()); 初始条件：广义表L已存在。 操作结果：遍历广义表L，用函数visit处理每个元素，}ADTGList①列表的元素可以是子表，而子表的元素还可以是子表……故，列表是一个多层次的结构。如图5.7所示的列表D。图中圆圈表示列表，以方块表示原子。②列表可为其他列表所共享。③列表可以是一个递归的表，即列表也可以是其本身的一个子表。〔3〕3个重要结论：D

ABCE

ea

bcd

图5.7 列表的图形表示5.5广义表的存储结构

因为广义表的数据元素是不定的，所以通常采用链式存储结构来表示。〔1〕头尾链表存储表示①结点结构原子结点tag=0atomtag=1hptp

表结点tag：标志域。tag＝1表示表结点；tag＝0表示原子结点。hp：指示表头的指针域。tp：指示表尾的指针域。atom：值域。②C语言描述 typedefenum{ATOM,LIST}ElemTag;//ATO