第五章 数组与广义表
一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000。计算：
1、数组A的体积（即存储量）；
2、数组A的最后一个元素a57的第一个字节的地址；
3、按行存储时，元素a14的第一个字节的地址；
4、按列存储时，元素a47的第一个字节的地址；
答案：
1、（6*8）*6=288
2、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=1282
3、loc(a14)=1000+(1*8+4)*6=1072
4、loc(a47)=1000+(7*6+4)*6=1276
二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？
（1）a0000  (2)a1111  (3)a3125   (4)a8247
答案：（1）100
    （2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776
      (3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784
      (4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416
五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。
答：
K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i
=(i-1)(n+(n-i+2))/2+j-i
所以f1(i)=(n+1/2)i-1/2i2
    f2(j)=j
    c=-(n+1)
九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。（对角线求和）
解：
1、二维数组
  For(i=1;i<=n;i++)
    S=s+a[i][i];
  时间复杂度：O（n）
2、for(i=1;i<=m.tu;i++)
    If(a.data[k].i==a.data[k].j)  s=s+a.data[k].value;
  时间复杂度：O（n2）
二十一、当稀疏矩阵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 (k<A->t&&l<B->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].j<B->data[l].j))
      　||(A->data[k].i<B->data[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 ((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 (k<A->t)//将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++;
    　}
    while (l<B->t)//将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++;
    　}
  　}
二十六、试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。
解：
void Print_OLMatrix(OLMatrix A)//以三元组格式输出十字链表表示的矩阵
{
  for(i=0;i<A.mu;i++)
  {
    if(A.rhead[i])
      for(p=A.rhead[i];p;p=p->right) //逐次遍历每一个行链表
        printf("%d %d %d\n",i,p->j,p->e;
  }
}//Print_OLMatrix
补充题：
一、现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。
（1）三元组表示法。
（2）十字链表法。
０    0    0    22    0  -15
0    13    3    0    0    0
0      0    0    -6    0    0
0      0    0    0    0    0
91    0    0    0    0    0
0      0    28    0    0    0
① 三元组表示法
i  j  v
1
2
3
4
5
6
7
1  4 22
1  6  -15
2  2  13
2  3  3
3  4  -6
5  1  91
6  3  28
② 略

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。