文档库

最新最全的文档下载
当前位置:文档库 > 习题五

习题五

⑴什么是广义表?请简述广义表与线性表的区别?

广义表是零至多个元素的有限序列,广义表中的元素可以是原子,也可以是子表。从“元素的有限序列”角度看,广义表满足线性结构的特性:在非空线性结构中,只有一个称为“第一个”的元素,只有一个称为“最后一个”的元素,第一元素有后继而没有前驱,最后一个元素有前驱而没有后继,其余每个元素有唯一前驱和唯一后继。从这个意义上说,广义表属于扩充的线性结构(只不过元素并不具有同一类型:可以是原子,也可以是广义表)。

当广义表中的元素都是原子时,广义表就蜕变为线性表。

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

⑵一个广义表是(a, (a, b), d, e, (a, (i, j), k)) ,请画出该广义表的链式存储结构。

习题五

⑶设有二维数组a[6][8],每个元素占相邻的4个字节,存储器按字节编址,已知a的起始地址是1000,试计算:

①数组a的最后一个元素a[5][7]起始地址;

②按行序优先时,元素a[4][6]起始地址;

③按行序优先时,元素a[4][6]起始地址。

答:

LOC(a[5][7])=LOC(a[0][0])+47*4=1188

LOC(a[4][6])=LOC(a[0][0])+(4?8+6)?4=1152

LOC(a[4][6])=LOC(a[0][0])+(6*6+4)?4=1160

⑷设A和B是稀疏矩阵,都以三元组作为存储结构,请写出矩阵相加的算法,其结果存放在三元组表C中,并分析时间复杂度。

解:

void TSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&C)//三元组表示的稀疏矩阵加法

{

C.mu=A.mu;C.nu=A.nu;C.tu=0;

pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法

{

while(A.data[pa].i

while(B.data[pb].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j)

{

ce=A.data[pa].e+B.data[pb].e;

if(ce) //和不为0

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=ce;

pa++;pb++;pc++;

}

}//if

else if(A.data[pa].j>B.data[pb].j)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

else

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e

pa++;pc++;

}

}//while

while(A.data[pa]==x) //插入A中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e

pa++;pc++;

}

while(B.data[pb]==x) //插入B中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

}//for

C.tu=pc;

}//TSMatrix_Add

答案二:

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放,在建立新的三元组表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++;

}

}

⑸设有稀疏矩阵B如下图所示,请画出该稀疏矩阵的三元组表和十字链表存储结构。

习题五

三元组表如下:

习题五

习题五

图中未标记空指针,作业中请注意标记