数据结构 第5章 数组和广义表

《数据结构 第5章 数组和广义表》由会员分享，可在线阅读，更多相关《数据结构 第5章 数组和广义表（51页珍藏版）》请在金锄头文库上搜索。

1、下一页下一页结结 束束上一页上一页要要 点点第第5章章 数组和广义表数组和广义表5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4 广义表的定义广义表的定义第 5 章7/27/27/27/20240241 1 1 1下一页下一页结结 束束上一页上一页要要 点点2.1 数组的定义数组的定义从逻辑结构上，数组可以看作从逻辑结构上，数组可以看作是一般线性表的扩充。一维数组是一般线性表的扩充。一维数组即为线性定义表，而二维数组可即为线性定义表，而二维数组可以为以为“其数据元素为一维数组其数据元素为一维数组（线性表）（线性表）”的线性表

2、。依此类的线性表。依此类推，即可得到多维数组的定义。推，即可得到多维数组的定义。7/27/27/27/20240242 2 2 2下一页下一页结结 束束上一页上一页要要 点点以二维数组为例：以二维数组为例：7/27/27/27/20240243 3 3 3下一页下一页结结 束束上一页上一页要要 点点我们可以把二维数组看成一个线性表：我们可以把二维数组看成一个线性表：A=(a1 a2 ajan),其中其中aj(1jn)本身也是一个线性表，称为列向量。本身也是一个线性表，称为列向量。矩阵矩阵Amn看成看成n个列向量的线性表，即个列向量的线性表，即aj=(a1j,a2j amj)7/27/27/27

3、/20240244 4 4 4下一页下一页结结 束束上一页上一页要要 点点我们可以把二维数组看成一个线性表：我们可以把二维数组看成一个线性表：B=(b1 b2 bjbm),其中其中bj(1jm)本身也是一个线性表，称为行向量。本身也是一个线性表，称为行向量。7/27/27/27/20240245 5 5 5下一页下一页结结 束束上一页上一页要要 点点ADT Array 数据对象数据对象： D = aD = aj1j1 j2j2jnjn| | n(0)n(0)称为数组的维数，称为数组的维数， j ji i是数组元素第是数组元素第i i维的下标，维的下标， j ji i= = 0,1,b0,1,b

4、i i-1 , i=1,2,n, bi-1 , i=1,2,n, bi是数组第是数组第i i维的长度，维的长度，a aj1j1 j2j2jnjn ElemSetElemSet 数据关系数据关系： R = R1, R2, , R = R1, R2, , RnRn RiRi=a=| 0 0j jk k b bk k-1 -1 ，1 1 k k n n且且kiki， 0 0 j ji i b bi i-2-2， a aj1j1jijijn,jn,a aj j1 1jiji+ +1 1j jn nDD ,i,i= =2,n2,n 抽抽象象数数据据类类型型定定义义7/27/27/27/20240246

5、6 6 6下一页下一页结结 束束上一页上一页要要 点点基本操作：InitAarray( &A,n,bound1,boundn )操作结果：若维数操作结果：若维数n和各维数长度合法，和各维数长度合法，则构造相应的数组则构造相应的数组A，并返回，并返回OK。DestroyArray(&A)操作结果：销毁数组操作结果：销毁数组A。7/27/27/27/20240247 7 7 7下一页下一页结结 束束上一页上一页要要 点点Value(A,&e,index1,indexn)初时条件初时条件：A是是n维数组，维数组，e为元素变量，随后为元素变量，随后是是n个下标值。个下标值。操作结果操作结果：若各下标不

6、超界，则：若各下标不超界，则e赋值为所指赋值为所指定的定的A的元素值，并返回的元素值，并返回OK。Assign(&A,e,index1,indexn)初时条件初时条件： A是是n维数组，维数组，e为元素变量，为元素变量，随后是随后是n个下标值。个下标值。操作结果操作结果：若各下标不超界，则将若各下标不超界，则将e的值赋的值赋给所指定的给所指定的A的元素值，并返回的元素值，并返回OK 。7/27/27/27/20240248 8 8 8下一页下一页结结 束束上一页上一页要要 点点 数组一旦被定义，它的维数和维数组一旦被定义，它的维数和维界不再改变。因此，除了结构的界不再改变。因此，除了结构的初始

7、化和销毁之外，数组只有存初始化和销毁之外，数组只有存取元素和修改元素值的操作。取元素和修改元素值的操作。7/27/27/27/20240249 9 9 9下一页下一页结结 束束上一页上一页要要 点点5.2 数组的顺序表示和实现数组的顺序表示和实现类型特点：类型特点：1）只有引用型操作，没有加工型操作；）只有引用型操作，没有加工型操作；2）数组是多维的结构，而存储空间是一）数组是多维的结构，而存储空间是一个一维的结构。个一维的结构。 有两种顺序映像的方式：有两种顺序映像的方式：1）以行序为主序（低下标优先）；）以行序为主序（低下标优先）；2）以列序为主序（高下标优先）；）以列序为主序（高下标优先

8、）；7/27/27/27/202402410101010下一页下一页结结 束束上一页上一页要要 点点a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,0 am-1,n-1A=二维数组的表示形式二维数组的表示形式行优先顺序存储行优先顺序存储a00a01 a0n-1第第 1行行a10 a11 a1,n-1第第 2行行am-1,0 am-1,1 am-1,n-1 第第 m行行a00 a10 am-1,0第第 1列列a01 a11 am-1,1第第 2列列a0,n-1 a1,n-1 am-1,n-1第第 n列列列优先顺序存储列优先顺序存储7/27/27/27/20240

9、2411111111下一页下一页结结 束束上一页上一页要要 点点以行序为主序以行序为主序二维数组二维数组A中任一元素中任一元素aij的存储位置的存储位置LOC(i,j) =LOC(0,0) + (b2i+j)L基地址或基址基地址或基址7/27/27/27/202402412121212下一页下一页结结 束束上一页上一页要要 点点推广到一般情况，可得到推广到一般情况，可得到n维数组数据元维数组数据元素存储位置：素存储位置：LOC(j1,j2,jn) =LOC(0,0,0) +(b2bnj1+ b3bnj2 + + bnjn-1+jn)L可缩写成可缩写成LOC(j1,j2,jn) =LOC(0,0

10、,0) + 其中，其中，cn =L，ci1 =bici，iin 称为称为n维数组的映像函数，数组元素的存储维数组的映像函数，数组元素的存储位置是其下标的线性函数位置是其下标的线性函数7/27/27/27/202402413131313下一页下一页结结 束束上一页上一页要要 点点5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储假设假设m行行n列的矩阵含列的矩阵含t个非零元素，则称个非零元素，则称 =为为稀疏因子稀疏因子 通常认为通常认为=0.05的矩阵为稀疏矩阵的矩阵为稀疏矩阵 以常规方法，即以二维数组表示高阶的稀疏以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题：矩阵时产生的问题：1）零值元

11、素占的空间很大；）零值元素占的空间很大；2）计算中进行了很多和零值的运算；）计算中进行了很多和零值的运算；7/27/27/27/202402414141414下一页下一页结结 束束上一页上一页要要 点点解决问题的原则：解决问题的原则：1）尽可能少存或不存零值元素；）尽可能少存或不存零值元素；2）尽可能减少没有实际意义的运）尽可能减少没有实际意义的运算；算；3）运算方便；即：）运算方便；即： 能尽可能快地找到与下标值能尽可能快地找到与下标值(i,j)对应的元素；对应的元素； 能尽可能快地找到同一行或同能尽可能快地找到同一行或同一列的非零值元；一列的非零值元；7/27/27/27/20240241

12、5151515下一页下一页结结 束束上一页上一页要要 点点1）特殊矩阵的压缩存储）特殊矩阵的压缩存储例如：三角矩阵例如：三角矩阵 对角矩阵对角矩阵2）随机稀疏矩阵的压缩存储）随机稀疏矩阵的压缩存储 随机矩阵中的非零随机矩阵中的非零 元分布不规则元分布不规则7/27/27/27/202402416161616下一页下一页结结 束束上一页上一页要要 点点一一.三元组顺序表三元组顺序表#define MAXSIZE 12500typedef structint i,j;/该非零元的行下标和列下标该非零元的行下标和列下标ElemType e;Triple;/三元组类型三元组类型typedef stru

13、ctTriple dataMAXSIZE+1;/非零元三元非零元三元 /组表，组表，data0未用未用int mu,nu,tu; /矩阵的行数、列数和非矩阵的行数、列数和非 /零元个数零元个数TSMatrix;/稀疏矩阵类型稀疏矩阵类型7/27/27/27/202402417171717下一页下一页结结 束束上一页上一页要要 点点 0 3 0 0 -5 0 -1 0 0 0 6 0 0 8 0(1,2,3) (1,5,-5) (2,2-1) (3,1,6) (3,4,8)3行行 5列列 5个非零元个非零元7/27/27/27/202402418181818下一页下一页结结 束束上一页上一页要要

14、 点点求转置矩阵的操作：求转置矩阵的操作：用常规的二维数组表示时的算法用常规的二维数组表示时的算法for(col=1;col=nu; +col) for(row=1;row=mu;+row) Tcolrow =Mrowcol;其时间复杂度为：其时间复杂度为：O(munu)7/27/27/27/202402419191919下一页下一页结结 束束上一页上一页要要 点点M = 0 3 0 0 -5 T = 0 0 6 -4 0 -1 0 0 0 3 -1 0 0 6 0 0 8 0 0 0 0 0 -4 0 0 0 7 0 0 8 0 -5 0 0 7 M.Data ( (以行序为主序以行序为主序

15、以行序为主序以行序为主序) ) T.data ( (以行序为主以行序为主以行序为主以行序为主序序序序) ) 1 2 3 1 5 -5 2 2 -13 1 6 3 4 8 4 1 -44 5 7 2 1 3 5 1 -5 2 2 -1 1 3 6 4 3 8 1 4 -4 5 4 7 7/27/27/27/202402420202020下一页下一页结结 束束上一页上一页要要 点点M.Data (以行序为主序以行序为主序) T.data (以行序为以行序为主序主序) 1 2 3 1 5 -5 2 2 -13 1 6 3 4 8 4 1 -44 5 7 2 1 3 1 3 6 5 1 -51 4 -

16、4 2 2 -1 2 1 3 1 3 62 2 -1 4 3 8 4 3 8 1 4 -4 5 1 -55 4 7 5 4 7 Col 1 2 3 4 5Num 0+1+1 0+1+1 0 0+1 0+1+1 cPot 1 1+2=3 3+2=5 5+0=5 5+1=6pq4727/27/27/27/202402421212121下一页下一页结结 束束上一页上一页要要 点点Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)/采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵M的转的转置矩阵置矩阵T. T.mu=M.nu;

17、T.nu=M.mu;T.tu=M.tu; if(T.tu) for(col=1;col=M.nu; +col) numcol =0; for(t=1;t=M.tu; +t) +numM.datat.j;/求求M中每一列含非中每一列含非 /零元个数零元个数 cpot1 =1;/求第求第col列中第一个非零元在列中第一个非零元在 /b.data中的序号中的序号 for(col =2;col=M.nu; +col) cpotcol = cpotcol-1 +numcol-1; 7/27/27/27/202402422222222下一页下一页结结 束束上一页上一页要要 点点 for(p =1;p=M.

18、tu; +p) col=M.datap.j; q=cpotcol; T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; /for if return OK; / FastTransposeSMatrix7/27/27/27/202402423232323下一页下一页结结 束束上一页上一页要要 点点三元组顺序表又称有序的双下三元组顺序表又称有序的双下标法，它的特点是，非零元在表标法，它的特点是，非零元在表中按行序有序存储，因此便于进中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然行依行顺序处理的

19、矩阵运算。然而，若需随机存取某一行中的非而，若需随机存取某一行中的非零元，则需从头开始进行查找。零元，则需从头开始进行查找。7/27/27/27/202402424242424下一页下一页结结 束束上一页上一页要要 点点二二.行逻辑联接的顺序表行逻辑联接的顺序表修改前述的稀疏矩阵的结构定义，增加一个修改前述的稀疏矩阵的结构定义，增加一个数据成员数据成员rpos,其值在稀疏矩阵的初始化函其值在稀疏矩阵的初始化函数中确定。数中确定。#define MAXRC 500typedef struct Triple dataMAXSIZE+1;/非零元三非零元三 /元组表元组表 int rposMAXRC

20、+1;/各行第一个非零各行第一个非零 /元的位置表元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型行逻辑链接顺序表类型7/27/27/27/202402425252525下一页下一页结结 束束上一页上一页要要 点点M.Data (以行序为主序以行序为主序) T.data (以行序为以行序为主序主序) 1 2 3 1 5 -5 2 2 -13 1 6 3 4 8 4 1 -44 5 7 2 1 3 1 3 6 5 1 -51 4 -4 2 2 -1 2 1 3 1 3 62 2 -1 4 3 8 4 3 8 1 4 -4 5 1 -55 4 7 5 4 7 Col

21、 1 2 3 4 5Num 0+1+1 0+1+1 0 0+1 0+1+1 cPot 1 1+2=3 3+2=5 5+0=5 5+1=6pqrpos7/27/27/27/202402426262626下一页下一页结结 束束上一页上一页要要 点点M = 0 2 0 0 3 N = 0 3 Q =4 2 0 -1 5 0 0 2 4 3 -4 4 0 0 7 6 1 0 0 0 0 0 -3 0 0 0 0 -3 0 0 -2 M.Data NN.data 1 2 21 5 3 2 2 -12 3 53 1 43 4 73 5 6 1 2 3 2 1 22 2 4 3 1 1 5 2 -2 4 3

22、 -3 7/27/27/27/202402427272727下一页下一页结结 束束上一页上一页要要 点点矩阵乘法的经典算法：矩阵乘法的经典算法：for(i=1;i=m1; +i )for(j=1;j=n2; +j) Qij =0; for(k=1;k=n1; +k) Qij+=Mik* Nkj;其时间复杂度为：其时间复杂度为：O(m1n2n1)7/27/27/27/202402428282828下一页下一页结结 束束上一页上一页要要 点点1）对）对M矩阵的非零元进行处理矩阵的非零元进行处理2）每一个非零元找行号和列号对）每一个非零元找行号和列号对应的元素相乘应的元素相乘3）对）对Q一行一行处理

23、一行一行处理7/27/27/27/202402429292929下一页下一页结结 束束上一页上一页要要 点点M.Data N.data Q.data1 2 21 5 3 2 2 -12 3 53 1 43 4 73 5 6 1 2 3 2 1 22 2 4 3 1 1 5 2 -2 4 3 -3 0+4 =40+8 +(-6) =20 +(-2) +5 =30 -31 1 4 1 2 2 2 1 3 2 2 -44 1 -3 pq0+(-4) =-4 0+12+(-12) =0 ctemp7/27/27/27/202402430303030下一页下一页结结 束束上一页上一页要要 点点两个稀疏矩

24、阵相乘（两个稀疏矩阵相乘（Q=MN）的过程可）的过程可大致描述如下：大致描述如下：Q初始化：初始化：if (Q是非零矩阵是非零矩阵)/逐行求积逐行求积 for(arow=1;arow=M.mu; +arow) /处理处理M的每一行的每一行 ctemp =0;/累加器清零累加器清零 计算计算Q中第中第arow行的积并存入行的积并存入ctemp中中; 将将ctemp中非零元压缩存储到中非零元压缩存储到Q.data; /for arow/if7/27/27/27/202402431313131下一页下一页结结 束束上一页上一页要要 点点Status MultSMatrix(RLSMatrix M,R

25、LSMatrix N,RLSMatrix &Q)if(M.nu! =N.mu) return ERROR;Q.mu =M.mu;Q.nu =N.nu;Q.tu =0;if(M.tu*N.tu! =0)/Q是非零矩阵是非零矩阵for(arow =1;arow=M.mu; +arow)/处理处理M的每一行的每一行 ctemp =0;/当前行各元素累加器清零当前行各元素累加器清零 Q.rposarow=Q.tu+1; if(arowM.mu) tp=M.rposarow+1 ; else tp=M.tu+1; 7/27/27/27/202402432323232下一页下一页结结 束束上一页上一页要要

26、 点点for(p=M.rposarow;ptp; +p)/对当对当/前行中每一个非零元找到对应元在前行中每一个非零元找到对应元在N中的行号中的行号brow=M.datap.j; ; if(browN.mu) t=N.rposbrow+1; else t=N.tu+1; for(q=N.rposbrow;qt; +q) ccol=N.dataq.j; ctempccol +=M.datap.e*N.dataq.e; /for q/求得求得Q中第中第crow(=arow)行的非零元行的非零元7/27/27/27/202402433333333下一页下一页结结 束束上一页上一页要要 点点for(cc

27、ol=1;ccolMAXSIZE) return ERROR; Q.dataQ.tu =(arow,ccol,ctempccol); /if /for arow /if return OK;/MultSMatrix7/27/27/27/202402434343434下一页下一页结结 束束上一页上一页要要 点点分析上述算法的时间复杂度分析上述算法的时间复杂度累加器累加器ctemp初始化的时间复杂度为初始化的时间复杂度为O(M.muN.nu)，求求Q的所有非零元的时间复杂度为的所有非零元的时间复杂度为O(M.tuN.tu/N.mu),进行压缩存储的时间复杂度为进行压缩存储的时间复杂度为O(M.mu

28、N.nu),总的时间复杂度就是总的时间复杂度就是O(M.muN.nu+M.tuN.tu/N.mu),若若M是是m行行n列的稀疏矩阵，列的稀疏矩阵，N是是n行行p列的稀疏矩阵，列的稀疏矩阵，则则M中非零元的个数中非零元的个数M.tu= Mmn，N中非零元的个数中非零元的个数N.tu = nnp,相乘算法的时间复杂度就是相乘算法的时间复杂度就是O(mp(1+nMn),当当M0。05和和n0。05及及n1000时，时，相乘算法的时间复杂度就相当于相乘算法的时间复杂度就相当于O(mp)。7/27/27/27/202402435353535下一页下一页结结 束束上一页上一页要要 点点 三三.十字链表十字

29、链表 对于稀疏矩阵，当非对于稀疏矩阵，当非0元素的个数和位元素的个数和位置在操作过程中变化较大时，采用链式存置在操作过程中变化较大时，采用链式存储结构表示比三元组的线性表更方便。储结构表示比三元组的线性表更方便。 矩阵中非矩阵中非0元素的结点所含的域有：元素的结点所含的域有：行行、列列、值值、行指针行指针(指向同一行的下一个非指向同一行的下一个非0元元)、列指针列指针(指向同一列的下一个非指向同一列的下一个非0元元)。其次，十字交叉链表还有一个头结点其次，十字交叉链表还有一个头结点。7/27/27/27/202402436363636下一页下一页结结 束束上一页上一页要要 点点0 0 1212

30、 0 0 0 00 00 0 0 0 0 0 -4 0 0 -40 5 0 0 00 5 0 0 00 0 3 0 00 0 3 0 0稀疏稀疏矩阵矩阵A A(b) 稀疏稀疏矩阵的十字交叉链表矩阵的十字交叉链表A.cheadA.rchead 1 2 12 3 2 5 2 5 -4 4 3 3 7/27/27/27/202402437373737下一页下一页结结 束束上一页上一页要要 点点5.4广义表的定义广义表的定义ADT GList 数据对象：数据对象：D=eii=1,2,n;n0; eiAtomSet或或eiGList， AtomSet为某个数据对象为某个数据对象 数据关系：数据关系：LR

31、= ei-1, ei D,2in广义表是广义表是递归递归定义的定义的线性结构线性结构，一般情况下，广义表写成一般情况下，广义表写成LS=(1, 2, n)其中：其中：i或为原子或为广义表或为原子或为广义表7/27/27/27/202402438383838下一页下一页结结 束束上一页上一页要要 点点广义表是一个广义表是一个多层次多层次的线性结构的线性结构例如：例如：D=(E,F)E=(a,(b,c)F=(d,(e)abecdEFD( )( )7/27/27/27/202402439393939下一页下一页结结 束束上一页上一页要要 点点其他如：其他如：A=( ) 空表空表B=(a,B) =(a

32、,(a,(a,)无限表无限表C=(A,D,F)7/27/27/27/202402440404040下一页下一页结结 束束上一页上一页要要 点点广义表广义表 LS=(1, 2, n)的结构特点：的结构特点：1）广义表中的数据元素有相对）广义表中的数据元素有相对次序次序；2）广义表的）广义表的长度长度定义为最外层包含元素个数定义为最外层包含元素个数（即为（即为n）3）广义表的）广义表的深度深度定义为所含括弧的重数：定义为所含括弧的重数：注意：注意：“原子原子”的深度为的深度为“0”； “空表空表”的深度为的深度为14）广义表可以）广义表可以共享共享；5）广义表可以是一个）广义表可以是一个递归递归的

33、表；的表；递归表的深度为无穷值，长度是有限值。递归表的深度为无穷值，长度是有限值。7/27/27/27/202402441414141下一页下一页结结 束束上一页上一页要要 点点6）任何一个非空广义表）任何一个非空广义表LS=(1, 2, n)均可分解为均可分解为 表头表头 Head(LS) = 1和和 表尾表尾Tail(LS) =(2, n)两部分两部分例如：例如：LS=(A,D) =(),(E,F) =(),(a,(b,c),F)Head(LS) =A Tail(LS) =(D)Head(D) =E Tail(D) =(F)Head(E) =a Tail(E) =(b,c)Head(b,c

34、) =(b,c) Tail(b,c) =( )Head(b,c) =b Tail(b,c) =(c)Head(c) =c Tail(c) =()7/27/27/27/202402442424242下一页下一页结结 束束上一页上一页要要 点点l l结构的创建和销毁结构的创建和销毁InitGList(&L);DestroyGList(&L);CreateGList(&L,S);CopyGList(&T,L);l l状态函数状态函数GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);l l插入和删除操作插入和删除操作Ins

35、ertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);l l遍历遍历Traverse_GL(L,Visit();ADT GList基基本本操操作作7/27/27/27/202402443434343下一页下一页结结 束束上一页上一页要要 点点5.5广义表的存储结构广义表的存储结构头、尾指针的链表结构头、尾指针的链表结构标志标志tag=0 tag=0 原子的值原子的值datadata 标志标志tagtag=1 =1 表头指针表头指针hphp 表尾指针表尾指针tptp 表结点：表结点：原子结点：原子结点：7/27/27/27/202402444444444下一页下一页结结

36、 束束上一页上一页要要 点点构造存储结构的两种分析方法：构造存储结构的两种分析方法：1）空表）空表 ls=NIL 非空表非空表 ls若表头为原子，则为若表头为原子，则为否则，依次类推。否则，依次类推。1 1表头表头表尾表尾0 0 data data 7/27/27/27/202402445454545下一页下一页结结 束束上一页上一页要要 点点例如：例如：L=(a,(x,y),(x) )a(x,y),(x)(x,y)( (x) )x(y)y( ) (x)( ) (x)( )x( )7/27/27/27/202402446464646下一页下一页结结 束束上一页上一页要要 点点L=(a,(x,y

37、),(x)1 1L1 1(x,y)(x,y),(x)( (x)0 0 a a 7/27/27/27/202402447474747下一页下一页结结 束束上一页上一页要要 点点Ls=(a,(x,y),(x) (x,y)a (x)7/27/27/27/202402448484848下一页下一页结结 束束上一页上一页要要 点点1.了解数组的两种存储表示（行列），并掌握了解数组的两种存储表示（行列），并掌握数组在以行为主的存储结构中的地址计算方数组在以行为主的存储结构中的地址计算方法。法。2.掌握三元组顺序表、行逻辑链接的顺序表。掌握三元组顺序表、行逻辑链接的顺序表。3.了解十字链表了解十字链表4.了

38、解广义表的定义和存储结构了解广义表的定义和存储结构本章复习要点本章复习要点7/27/27/27/202402449494949下一页下一页结结 束束上一页上一页要要 点点习题(1)(1)设有二维数组设有二维数组a68a68，每个元素占相邻，每个元素占相邻的的4 4个字节，存储器按字节编址，已知个字节，存储器按字节编址，已知a a的起始的起始地址是地址是10001000，试计算：，试计算： 数组数组a a的最后一个元素的最后一个元素a57a57起始地址起始地址; ; 按行序优先时，元素按行序优先时，元素a46a46起始地址起始地址; ; 按行序优先时，元素按行序优先时，元素a46a46起始地址起

39、始地址. .(2)(2) 一个广义表是一个广义表是(a, (a, b), d, e, (a, (a, (a, b), d, e, (a, (i, j), k) (i, j), k) , ,请画出该广义表的链式存储结请画出该广义表的链式存储结构构. .下一页下一页结结 束束上一页上一页要要 点点0 3 0 0 0 0 0 00 0 0 0 0 0 0 0-3 0 0 0 0 0 0 40 0 2 0 0 2 0 00 18 0 0 0 0 0 00 0 0 0 4 0 5 0A=0 0 -3 0 0 0 0 0(2)(2) 设有稀疏矩阵设有稀疏矩阵B B如下图所示如下图所示，请画出该稀疏矩阵的三元组表和请画出该稀疏矩阵的三元组表和十字链表存储结构十字链表存储结构。