数据结构c语言版数组和广义表

《数据结构c语言版数组和广义表》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第五章数组和广义表重点难点理解数组和广义表两种数据结构的特点，并掌握数组在"以行为主"的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。典型例题1.设有三对角矩阵Ann，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：(1)用i,j表示k的下标变换公式。(2)用k表示i,j的下标变换公式。【解】(1) 要求i,j到k的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为：(i3-1)+j-(i+1) 其中(i3-1)

2、是这个元素前面所有行的非零元素个数，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.设二维数组A56的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?解： (1)因含56=30个

3、元素，因此A共占304=120个字节。 (2)a45的起始地址为：    Loc(a45)=Loc(a00)+(in+j)d=1000+(46+5)4=1116 (3)按行优先顺序排列时，    a25=1000+(26+5)4=1068 (4)按列优先顺序排列时：(二维数组可用行列下标互换来计算)    a25=1000+(55+2)4=11083.当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。解：矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先

4、排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。#defineMaxSize10//用户自定义typedefintDataType;//用户自定义typedefstruct{//定义三元组inti,j;DataTypev;}TriTupleNode;typedefstruct{//定义三元组表TriTupleNodedata[MaxSize];intm,n,t;//矩阵行，列及三元组表长度}TriTupleTable

5、;//以下为矩阵加算法 voidAddTriTuple(TriTupleTableA,TriTupleTableB,TriTupleTableC){//三元组表表示的稀疏矩阵A,B相加intk,l;DataTypetemp;C->m=A->m;//矩阵行数C->n=A->n;//矩阵列数C->t=0;//三元组表长度k=0;l=0;while(kt&&lt){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)//相加

6、不为零，加入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].jdata[l].j))(A->data[k].idata[l].i)//将A中三元组加入C{C->data[c->t].i=A->data[k].i;C->data[c->t].j=A->data[k].j;C->data[c->t++].v=A->data[k].v;k++;}if(

7、(A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j))(A->data[k].i>B->data[l].i)//将B中三元组加入C{C->data[c->t].i=B->data[l].i;C->data[c->t].j=B->data[l].j;C->data[c->t++].v=B->data[l].v;l++;}}while(kt)//将A中剩余三元组加入C{C->da