中南大学数据结构与算法第5章数组和广义表课后作业答案

第5章数组与广义表习题练习答案

5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。 解：

按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100 a0101 a0102 a0110 a0111 a0112 a0200 a0201 a0202 a0210 a0211 a0212 a1000 a1001 a1002 a1010 a1011 a1012 a1100 a1101 a1102 a1110 a1111 a1112 a1200 a1201 a1202 a1210 a1211 a1212

按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)： a0000 a1000 a0100 a1100 a0200 a1200 a0010 a1010 a0110 a1110 a0210 a1210 a0001 a1001 a0101 a1101

a0201 a1201 a0011 a1011 a0111 a1111 a0211 a1211 a0002 a1002 a0102 a1102 a0202 a1202 a0012 a1012 a0112 a1112 a0212 a0212

5.2 给出C语言的三维数组地址计算公式。 解：

因为C语言的数组下标下界是0，所以 Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d

其中 Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。

5.3 设有三对角矩阵 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元素所点列数就是当前列号

5.4 设二维数组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

5.5 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么? 答：

后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

5.6 简述广义表和线性表的区别与联系。 答:

广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。

5.7 画出下列广义表的图形表示：

(1) A(a,B(b,d),C(e,B(b,d),L(f,g))) (2) A(a,B(b,A)) 解:

(1)这是一个再入表。(2)则是一个递归表。

5.8 设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少? 解：

●head(L)=() ●tail(L)=(()) ●L的长度为2 ●L的深度为2

5.9 求下列广义表运算的结果：

(1)head ((p,h,w)); (2)tail((b,k,p,h)); (3) head (((a,b),(c,d))); (4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d)))); (6)tailhead)(((a,b),(c,d)))). 答：

(1)head ((p,h,w))=p; (2)tail((b,k,p,h))=(k,p,h); (3)head (((a,b),(c,d)))=(a,b);

(4)tail(((a,b),(c,d)))=((c,d)); (5)head(tail(((a,b),(c,d))))=(c,d); (6)tail(head(((a,b),(c,d))))=(b).

5.10 当三角矩阵采用题5.3所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。 解：

转置矩阵就是将矩阵元素的行号与列号互换，根据已知的三对角矩阵的特点，其转置矩阵对角线元素不变，非零的非对角线元素aij与aji互换位置。又知元素的下标和存放一维数组空间位置的关系：k=2i+j。我们可以设计出这个矩阵的转置算法：

#define N 10 //矩阵行、列数

#define Length (3*N-2)//压缩矩阵的长度 typedef struct{ int data[Length]; }DiaMatrix;

void TransMatrix(DiaMatrix * C) { //压缩三对角矩阵转置 int i, j; int t;

for(i=0; i=-1)

{ //将对应于行列号的压缩矩阵内的元素互换 t=C->data[2*i+j];

C->data[2*i+j]=C->data[2*j+i]; C->data[2*j+i]=t; }//endif }//end

5.11 当稀疏矩阵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 (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)//相加不为零，加入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 ((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->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 (lt)//将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++; } }

本文来源：https://www.bwwdw.com/article/5oz6.html