严蔚敏++数据结构习题集答案(5)

q=p->rchild; /*右子树为空*/

else

{ if(p->ltag==list)

q=p->lchild； /*左子树非空*/

if(p->ltag==Thread)

q=p->rchild; /*左子树为空*/

}

return(q); }

②找结点p的后序继

BinTheNode * PostorderSuccssor(BinThrNode *p) {

BinThrNode *q;

if(p->ltag==Thread)

q=p->lchild; /*左子树为空*/ else

{if(p->rtag==list)

q=p->rchild; /*右子树非空*/ if(p->ltag==Thread)

q=p->lchild; /*右子树为空*/ }

return(q); }

/*说明：list\\Thread为特殊标志，其值分别为0与1.*/ 6．32 完成6.6.1 节算法CreateHuffmanTree中调用的三个函数：InputWeight,SelecMin和InitHuffmanTree. 解：

① 初始化

InitHuffmanTree(HuffmanTree T) { int i;

for(i=0;iparent=-1;

T[i]->lchild=-1; T[i]->rchild=-1; T[i]->weigh=0;

} }

② 读入叶子结点权值

InputWeigh(HuffmanTree T)

{ int I;

for(i=0;i

scanf(“%d”,&T[i]->weigh);

}

③ 选出两个权至最小的根结点

SelecMin(HuffmanTree T,i-1,&p1,&p2) int i,p1,p2;

{ int j,small1,small2;

small1=small2=max; /*设max为整型最大值*/

for(j=0;j

if(T[j]->parent==-1)

if(T[j]->weigh

{small2=small1; /*改变最小权、次小权及对应位置*/ small1=t[j]->weigh; p2=p1; p1=j; }

else

if(T[j]->weigh

{small2=T[j]->weigh; /*改变最小权及对应位置*/ p2=j; }

} 6．33 分别写出对文件进行哈夫谩码的算法，以及对编码文件进行解码的算法。为简单起见，可以假设文件存放在一个字符向量。 解：

① 编码算法

设哈夫曼树已求出。

HuffmanCode(code,tree) Codetype code[];

Huffmantype tree[] /*以求出*/ { int I,j,c,p;

codetype cd; /*缓冲区变量*/ for(i=0;istart=n; c=i+1;

p=tyee[i]->parent; while(p!=0) { cd->start=n; c=i+1;

p=tyee[i]->parent; while(p!=0)

{ cd->start--;

if(tree[p-1]->lchild==c)

cd->bit[cd-start]=’0’;/*type[i]是左子树，生成代码为‘0’*/ else

cd->bit[cd->start]=’1’；/*type[i]是右子树，生成代码为‘1’*/

c=p;

p=tree[p-1]->parent; }

code[i]=cd; } } 注：结构体 typedef struct

{ char bit[n]; /*位串*/

int start; /*编码在位串的起始位置*/

char ch; /*字库*/

}codetype;

codetype code[n]; ② 译码算法

Decode(code,tree) Codetype code[]; Huffmantype tree[]; { int I,j,c,p,b;

int endfily=-1; /*电文结束标志*/

i=m; /*从根结点开始往下搜索*/ scanf(“d”，&b); /*读入一个二进制代码*/ while(b!=endfily) { if(b==0)

i=tyee[i]->lchild-1; /*走向左孩子*/ else

i=tyee[i]->rchild-1; /*走向右孩子*/

if(tyee[i].child==0) /*tyee[i]为叶结点*/

{ outchar(code[i]->ch); /*译码，即输出叶结点对应的字符*/ i=m; /*回归根结点*/ P=tyee[p-1]->parent; }

scanf(“%d”,&b); /*读入下一个二进制代码*/

}

if(tyee[i].lchild!=0) /*电文读完但未到叶结点*/

printf(“\\n ERRoR\\n”); /*输出电文有错信息*/

}

同步综合练习及参考答案 （一） 基础知识题

7．1 在图7.23所是的各无向图中：

（1） 找出所有的简单环。

（2） 那些图是连通图？对非连通图给出其连通分量。

（3） 那些图是自由树（或森林）？ //自由树的概念见 7.4节 解：

（1） 简单环 （a）(1 2 3 1)

(b) 无

(c) （1 2 3 1） （2 3 4 2） （1 2 4 3 1） (d) 无

（2） 连通图（a）（c）（d） 非连通图（b）的连通分量为 （3） 自由树 （d）

森林 （b）

7．2 在图7.24所是的有向图中：

（1） 该图是强连通的码？若不是，则给出其强连通分量。 （2） 请给出所有简单路径及有向环。 （3） 请给出每个顶点的度、入度和出度。 （4） 请给出其邻接表、邻接矩阵及逆邻接表。 解：

（1） 图是强连通的。

（2） 所有简单路径（重复环未计算）

（v1）（v2）（v3）（v4）

(v1 v2)(v2 v3)(v3 v1)(v1 v4)(v4 v3)

(v1 v2 v3)(v2 v3 v1)(v3 v1 v4)(v3 v1 v2)(v1 v4 v3)(v4 v3 v1)

（v1 v2 v3 v1）（v2 v3 v1 v4）（v3 v1 v4 v3）（v4 v3 v1 v2） 有向环

（v1 v2 v4 v1）（v4 v1 v4 v4） (3) 各顶点的度、入度、和出度。 (4) ①邻接表

② 邻接矩阵集。 ③ 逆邻接表

7．3 假设图的顶点是A,B,?,请根据下属的邻接矩阵画出相应的无向图或有向图。 解：

7．4 假设一颗完全二叉树包含A,B,?,G第七个结点，写出其邻接表和邻接矩阵。 解：

① 完全二叉树 ② 邻接矩阵 ③ 邻接表

7．5 对n各顶点的无向图和有向图，采用邻接矩阵和邻接表表示，如何判别下列有关问题：

（1） 图中有多少条边？

（2） 任意两个顶点I和j是否有边相连？ （3） 任意一个顶点的度是多少？ 解：

① 对于无向图

（1） 图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的

一半。

（2） 若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。

（3） 顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j. ② 对于有向图

（1） 图中边树等于邻接矩阵中的个数；邻接表中的出边表中结点数。 （2） 若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连；

邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。

（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；

邻接表中i得出边表结点个数加上边表中结点I的个数之和。

7．6 n个顶点的连通图至少有几条边？强连通图呢？ 解：

①n个顶点的连通图至少有n-1条边。 ②n个顶点的强连通图至少有n条边。

7．7 DFS …… 此处隐藏：2987字，全部文档内容请下载后查看。喜欢就下载吧 ……