数据结构 用C语言描述 课后答案(8)

for(i=pos+t.ien;ilen;i--) /*将S中子串T后的所有字符 S->ch[i-t.len+v.len]=S->ch[i]; 前移T.len-V.len个位置*/

for(i=0;i<=V.len;i++) /*用V替换T*/ S->ch[pos+i]=V.ch[i]; S->len=S->len-T.len+V.len;

case <0: /*串T的长度小于串V的长度*/

if(S->len-T.len+V.len)<= MAXLEN /*插入后串长小于MAXLEN*/

{ /*将S中子串T后的所有字符后移V.len-T.len个位置*/ for(i=S->len-T.len+V.len;i>=pos+T.len;i--) S->ch[i]=S->ch[i-T.len+V.len];

for(i=0;i<=V.len;i++) /*用V替换T*/ S->ch[pos+i]=V.ch[i]; S->len=S->len-T.len+V.len; } else

{ /*替换后串长>MAXLEN,但串V可以全部替换*/ if(pos+V.len<=MAXLEN)

{ for(i=MAXLEN-1;i>=pos+T.len; i--) S->ch[i]=s->ch[i-T.len+V.len]

for(i=0;i<=V.len;i++) /*用V替换T*/ S->ch[pos+i]=V.ch[i]; S->len=MAXLEN;}

else /*串V的部分字符要舍弃*/ { for(i=0;ich[i+pos]=V.ch[i]; S->len=MAXLEN;} }/*switch()*/

pos=StrIndex(S,pos+V.len,T); /*求S中下一个子串T的位置*/

}/*while()*/ return(1);

}/*StrReplace()*/

三、假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A

的基地址为1000，计算： 数组A共占用多少字节；

数组A的最后一个元素的地址； 按行存储时元素A36的地址； 按列存储时元素A36的地址；

四、设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得

B[k]= aij ，求：

（1） 用i,j表示k的下标变换公式； （2） 用k表示i,j的下标变换公式。 【解答】（1）k=2(i-1)+j

(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）

五、在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法

只占用一个辅助向量空间。

六、写一个在十字链表中删除非零元素aij的算法。 【解答】算法（一）

FastTransposeTSMatrix(TSMartrix A, TSMatrix *B)

{/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/

int col,t,p,q;

int position[MAXSIZE];

B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) {

position[1]=1;

for(t=1;t<=A.len;t++)

position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数,

即利用pos[col]来记录第col-1列中非零元素的个数*/

/*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++)

position[col]=position[col]+position[col-1]; for(p=1;p

col=A.data[p].col; q=position[col];

B->data[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; Position[col]++; } } }

算法(二)

FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) {

int col,t,p,q;

int position[MAXSIZE];

B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) {

for(col=1;col<=A.n;col++) position[col]=0; for(t=1;t<=A.len;t++)

position[A.data[t].col]++; /*计算每一列的非零元素的个数*/

/*从最后一列起求每一列中第一个非零元素在B.data[]中的位置，存放在position[col]中*/

for(col=A.n,t=A.len;col>0;col--) { t=t-position[col]; position[col]=t+1; }

for(p=1;p

col=A.data[p].col; q=position[col];

B->data[q].row=A.data[p].col;

B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; Position[col]++; } }

}

七、画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 【解答】

第一种存储结构

第二种存储结构

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

（1） HEAD[((a,b),(c,d))]; （2） TAIL[((a,b),(c,d))];

（3） TAIL[HEAD[((a,b),(c,d))]];

（4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; 【解答】

（1） HEAD[((a,b),(c,d))]; (a,b) （2） TAIL[((a,b),(c,d))]; ((c,d)) （3） TAIL[HEAD[((a,b),(c,d))]]; (b) （4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]];

(d) 第五章 树和二叉树

课堂习题

1、一棵度为2的树和一棵二叉树的区别？ 【解答】略

2、画出具有3个结点的树和3个结点的二叉树的所有不同形态？并写出前序、中序和后序遍历的序列。 【解答】

具有3个结点的树 具有3个结点的二叉树

3、已知一棵树有N1个度为1的结点，N2个度为2的结点，N3个度为3的结点??NK

个度为K的结点，问树中有多少个叶子结点？ 【解答】

设树中结点总数为n,则n=n0 + n1 + …… + nk

树中分支数目为B,则B=n1 + 2n2 + 3n3 + …… + knk

因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1 即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1 由上式可得叶子结点数为：n0 = n2 + 2n3 + …… + (k-1)nk + 1 4、画出和已知序列对应的树 先序 DFKDAIEBCHJ 后序 DIAEKFCJHBG 【解答】略

5、画出和已知序列对应的森林 先序 ABCDEFGHIJKL 中序 CBEFDGAJIKLH 【解答】略

6、假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.21,0.10,试为这8个字母设计哈夫曼编码。 使用0-7的二进制表求形式是另一种方案，试比较两种方案。 【解答】

构造哈夫曼树如下：