数据结构课后习题与解析第五章.doc

第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A36的地址； 按列存储时元素A36的地址； 5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij ，求： （1）?????? 用i,j表示k的下标变换公式； （2）?????? 用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 5.5写一个在十字链表中删除非零元素aij的算法。 5.6画出下面广义表的两种存储结构图示： ?? ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）?????? HEAD[((a,b),(c,d))]; （2）?????? TAIL[((a,b),(c,d))]; （3）?????? TAIL[HEAD[((a,b),(c,d))]]; （4）?????? HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）?????? TAIL[HEAD[TAIL[((a,b),(c,d))]]]; ? ? 实习题 若矩阵Am×n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 ? 第五章答案 5.2设有三对角矩阵An×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。 【解答】（1）k=2(i-1)+j (2) i=[k/3]+1, j=[k/3]+k%3? （[ ]取整，%取余） 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一） ?? FastTransposeTSMatrix(TSMartrix? A,? TSMatrix? *B) ?? {/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/ int col,t,p,q; int position[MAXSIZE]; B-len=A.len;? B-n=A.m;? B-m=A.n; if(B-len0) { ? position[1]=1; ? for(t=1;t=A.len;t++) ???? position[A.data[t].col+1]++;?? /*position[col]存放第col-1列非零元素的个数, 即利用pos[col]来记录第col-1列中非零元素的个数*/ /*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col=A.n;col++)??? ???? position[col]=position[col]+position[col-1]; for(p=1;pA.len;p++) { ?? col=A.data[p].col; ?? q=position[col]; ?? B-data[q].row=A.data[p].col; ?? B-data[q].col=A.data[p].row; ?? B-data[q].e=A.data[p].e; ?? Position[col]++; } } } ? 算法(二) FastTransposeTSMatrix(TSMartrix? A,? TSMatrix? *B) ?? { int col,t,p,q; int position[MAXSIZE]; B-len=A.len;? B-n=A.m;? B-m=A.n; if(B-len0) { ? for(col=1;col=A.n;col++) ???? position[col]=0; ? for(t=1;t=A.len;t++) ?? position[A.data[t].col]++;??????? /*计算每一列的非零元素的个数*/ /*从最后一列起求每一列中第一个非零元素在B.data[]中的位置，存放在position[col]中*/ for(col=A.n,t=A.len;col0;col--)? {? t=t-position[col]; ?? position[col]=t+1; } for(p=1;pA.le