1、掌握数组元素存储位置的换算 2、了解特殊矩阵地存储方法和元素存储位置计算; 3、了解广义表的长度、深度、head、tail等概念和操作和存储结构 1、对于一个二维数组A[m][n],若按行序为主序存储,则任一元素A[i][j相对于A[0][0]的地址是 多少? 0020 3000 2、一个稀疏矩阵为 00-15|,则对应的三元组表是什么? 3、设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储,a为第一个元素,其存储地 址为0,每个元素占有一个存储地址空间,则as5的地址是多少? 4、设有上三角矩阵(a;)axn,将其上三角逐行存于数组B[m中,使得B[m]=a,且k=f(i)+f2(j)+c。 请写出函数f1,f2和常数c(f1和f2中不含常数项)。 5、求下列广义表操作的结果: (1)Head((p, h, w)) (2) Tail((b, k, p, h)) (3)Tail(((a,b),(c,d))) (4) Tail(Head(((a, b),(c, d)))) (5)Tail(Head(Tail(((a, b),(c, d))))) 6、假设稀疏矩阵A和B均以三元组顺序表作为存储结构,试写出矩阵相加的算法: int AddMatrix TSMatrix A, TSMatrix B, TSMatrix &C) 7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算 ik: int Print(Crosslist &M) 8、按照教材5.5节中图5.8所示结点结构,画出下列广义表的存储结构图,并求出它的深度。 (1)((()),a,((b,c),(),d),(((e))) (2)(((a),b)),(((),d),(e,f)) 31000 43000 9、设三角矩阵R= 采用一维数组进行压缩存储,第一个元素为R1,存储位置为1 750 每个元素占一个存储位置,则R2的存储位置为几? 参考解答: 1、&A[O][0]+(i*n+j米/L为每一数据元素所占的字节数 2、(1,3,2),(2,1,3),(3,3,-1),(3,4,5)) 3、&a;=&a+(i*(i+1)/2+j料(i>=j)//&a00为第一个元素的地址,L为每 &a;=&ao+(j*(j+1)/2+i)*L(j>=i)//元素所占存储空间 则a85的地址为0+8*9/2+5=41 4、若行号与列号均从0开始,则元素a;前有i行,各行的非0元素个数从n到n-i+1,共有 i*(n+n-i+1)/2个元素,a;所在的行中,其前面共有j个元素,但为0的元素有i个,不为0的元素 个数则为j-i个,所以在上三角中a前面共有i*(n+n-i+1)/2+j-i个非0的元素,这些元素需要存 储在一维数组B[中,且在a的前面,若一维数组的下标也从0开始,若用B[k]存储ai,则k= i*(n+n-i+1)/2+j-i=(-i2-i+2in)/2+j 即:f1(1)=(-i+2n-1)f2()=jc=08 1、掌握数组元素存储位置的换算； 2、了解特殊矩阵地存储方法和元素存储位置计算； 3、了解广义表的长度、深度、head、tail 等概念和操作和存储结构。 1、对于一个二维数组 A[m][n]，若按行序为主序存储，则任一元素 A[i][j]相对于 A[0][0]的地址是 多少？ 2、一个稀疏矩阵为             − 0 0 0 0 0 0 1 5 3 0 0 0 0 0 2 0 ，则对应的三元组表是什么？ 3、设有一个 10 阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a00 为第一个元素，其存储地 址为 0，每个元素占有一个存储地址空间，则 a85 的地址是多少？ 4、设有上三角矩阵（aij）n×n，将其上三角逐行存于数组 B[m]中，使得 B[m]= aij，且 k=f1(i)+f2(j)+c。 请写出函数 f1，f2 和常数 c（f1 和 f2 中不含常数项）。 5、求下列广义表操作的结果： （1）Head((p,h,w)); （2）Tail((b,k,p,h)); （3）Tail(((a,b),(c,d))); （4）Tail(Head(((a,b),(c,d)))); （5）Tail(Head(Tail(((a,b),(c,d))))); 6、假设稀疏矩阵 A 和 B 均以三元组顺序表作为存储结构，试写出矩阵相加的算法： int AddMatrix(TSMatrix A, TSMatrix B, TSMatrix &C); 7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算 法：int Print(CrossList &M); 8、按照教材 5.5 节中图 5.8 所示结点结构，画出下列广义表的存储结构图，并求出它的深度。 （1）（（（）），a，（（b，c），（），d），（（（e）））） （2）（（（（a），b）），（（（），d），（e，f））） 9、设三角矩阵 R=             10 14 69 91 58 36 75 0 43 0 0 0 31 0 0 0 采用一维数组进行压缩存储，第一个元素为 R11，存储位置为 1， 每个元素占一个存储位置，则 R32 的存储位置为几？ 参考解答： 1、&A[0][0]+(i*n+j)*L //L 为每一数据元素所占的字节数 2、((1,3,2),(2,1,3),(3,3,-1),(3,4,5)) 3、&aij=&a00+(i*(i+1)/2+j)*L (i>=j) //&a00 为第一个元素的地址，L 为每一 &aij=&a00+(j*(j+1)/2+i)*L (j>=i) //元素所占存储空间 则 a85 的地址为 0+8*9/2+5=41 4、若行号与列号均从 0 开始，则元素 aij 前有 i 行，各行的非 0 元素个数从 n 到 n-i+1，共有 i*(n+n-i+1)/2 个元素，aij 所在的行中，其前面共有 j 个元素，但为 0 的元素有 i 个，不为 0 的元素 个数则为 j-i 个，所以在上三角中 aij 前面共有 i*(n+n-i+1)/2+ j-i 个非 0 的元素，这些元素需要存 储在一维数组 B[]中，且在 aij 的前面，若一维数组的下标也从 0 开始，若用 B[k]存储 aij，则 k= i*(n+n-i+1)/2+ j- i =(-i 2 -i+2in)/2+j 即： ( 2 1) 2 ( ) 1 = −i + n − i f i f ( j) = j 2 c=0