数据结构C语言版第5章数组和广义表.docVIP

第五章 数组和广义表 重点难点 理解数组和广义表两种数据结构的特点，并掌握数组在以行为主的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。 典型例题 1. 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求： 　　(1)用i , j 表示k的下标变换公式。 　　(2)用 k 表示 i,j 的下标变换公式。 【解】(1)? 　　要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为： 　　　　(i*3-1)+j-(i+1)? 　　其中 (i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数 　　化简可得： 　　　　k=2i+j; // c下标是从0开始的。 　(2) 因为K和i,j是一一对应的关系，因此这也不难算出： 　　　　i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号 　　　　j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素， 　　　　　　　　　　　　　　　　//加上前面的0元素所点列数就是当前列号 2. 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何? 解： ? (1)因含5*6=30个元素，因此A共占30*4=120个字节。 ? (2)a45的起始地址为： ???? Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116 ? (3)按行优先顺序排列时， ???? a25=1000+(2*6+5)*4=1068 ? (4)按列优先顺序排列时：(二维数组可用行列下标互换来计算) ???? a25=1000+(5*5+2)*4=1108 3. 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。 解： 　　矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。 　　#define MaxSize 10 //用户自定义 　　typedef int DataType; //用户自定义 　　typedef struct 　　　{ //定义三元组 　　　　int i,j; 　　　　DataType v; 　　　}TriTupleNode; 　　typedef struct 　　　{ //定义三元组表 　　　　TriTupleNode data[MaxSize]; 　　　　int m,n,t;//矩阵行，列及三元组表长度 　　　}TriTupleTable; 　　//以下为矩阵加算法? 　　void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C) 　　　{//三元组表表示的稀疏矩阵A,B相加 　　　　int k,l; 　　　　DataType temp; 　　　　C-m=A-m;//矩阵行数 　　　　C-n=A-n;//矩阵列数 　　　　C-t=0; //三元组表长度 　　　　k=0; l=0; 　　　　while (kA-tlB-t) 　　　　　{if((A-data[k].i==B-data[l].i)(A-data[k].j==B-data[l].j)) 　　　　　　　{temp=A-data[k].v+B-data[l].v; 　　　　　　　　if (!temp)//相加不为零，加入C 　　　　　　　　　{C-data[c-t].i=A-data[k].i; 　　　　　　　　　　C-data[c-t].j=A-data[k].j; 　　　　　　　　　　C-data[c-t++].v=temp; 　　　　　　　　　} 　　　　　　　　k++;l++;　 　　　　　　　} 　　　　　if ((A-data[k].i==B-data[l].i)(A-data[k].jB-data[l].j)) 　　　　　　　||(A-data[k].iB-data[l].i)//将A中三元组加入C 　　　　　　{C-data[c-t].i