首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的内容补充完整。 【说明】 对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的内容补充完整。 【说明】 对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图
admin
2009-02-15
46
问题
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的内容补充完整。
【说明】
对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图6-15所示的最优二叉树,以及相应的结构数组Ht(如表6-14所示,其中数组元素Ht[0]不用)。
结构数组Ht的类型定义如下:
#define MAXLEAFNUM 20
struct node{
char ch; /*扫当前节点表示的字符,对于非叶子节点,此域不用*/
Int weight; /*当前节点的权值*/
int parent; /*当前节点的父节点的下标,为0时表示无父节点*/
int lchild, rchild;
/*当前节点的左、右孩子节点的下标,为0时表示无对应的孩子节点*/
)Ht[2*MAXLEAFNUM];
用“0”或“广标识最优二叉树中分支的规则是:从一个节点进入其左(右)孩子节点,就用“0”(或“1”)标识该分支,如图6-15所示。
若用上述规则标识最优二叉树的每条分支后,从根节点开始到叶子节点为止,按经过分支的次序将相应标识依次排列,可得到由“0”、“1”组成的一个序列,称此序列为该叶子节点的前缀编码。例如,图6-15所示的叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
函数void LeafCode(int root,int n)的功能是:采用非递归方法,遍历最优二叉树的全部叶子节点,为所有的叶子节点构造前缀编码。其中,形参root为最优二叉树的根节点下标;形参n为叶子节点个数。在函数void LeafCode(int root,int n)构造过程中,将Ht[p].weight域用做被遍历节点的遍历状态标志。
函数void Decode(char *buff,int root)的功能是:将前缀编码序列翻译成叶子节点的字符序列,并输出。其中,形参root为最优二叉树的根节点下标;形参buff指向前缀编码序列。
【函数4.1】
char **HC;
void LeafCode(int root, int n)
{ /*为最优二叉树中的n个叶子节点构造前缀编码,root是树的根节点下标*/
int I,p=root,cdlen=0;
char code[20];
Hc = (char **)malloc((n+1)*sizeof(char *)); /*申请字符指针数组*/
For(i = 1;i<= p;++I)
Ht
. weight = 0; /*遍历最优二叉树时用做被遍历节点的状态标志* /
While (p) { /*以非递归方法遍历最优二叉树,求树中每个叶子节点的编码*/
If(Ht[p].weight == 0) { /*向左*/
Ht[p].weight = 1;
If(Ht[p].lchild != 0) {
p = Ht[p].lchild;
code[cdlen++] = ’0’;
}
else if(Ht[p].rchild == 0) { /*若是叶子节点,则保存其前缀编码*/
Hc[p] = (char *)malloc((cdlen+1)*sizeof(char));
(1);
strcpy (Hc [p],code);
}
}
else if(Ht[p].weight == 1) { /*向右*/
Ht [p].weight = 2;
If(Ht[p].rchild != 0) {
p = Ht [p].rchild;
code[cdlen++] =’1’;
}
}
else { /*Ht[p].weight == 2,回退/
Ht [p].weight = 0;
p =(2);
(3); /*退回父节点*/
}
} / *while .结束* /
}
【函数4.2】
void Decode(char *buff,int root)
{ int pre = root,p;
while(*buff != ’\0’) {
p = root;
while(p != 0) { /*存在下标为p的节点*/
pre = p;
if( (4) )
p = Ht[p].lchild; /*进入左子树*/
else
p = Ht[p].rchild; /*进入右子树*/
else
buff++; /*指向前缀编码序列的下一个字符*/
}
(5);
printf("%c", Hr[pre].ch);
}
}
选项
答案
(1)code[cdlen]=’\0’或code[cdlen]=0 (2)Ht[p].parent (3)—cdlen或其等价形式 (4)*buff=’0’或其等价形式 (5)buff—或其等价形式
解析
这是一道要求读者在用哈夫曼算法构造的最优二叉树上进行编码和译码的程序设计题。本题的解答思路如下。
哈夫曼算法构造最优二叉树的过程如下。
1)根据给定的n个权值{W1,W2,W3,...Wn)构成n棵二叉树的集合F=(T1,T2,T3,...Tn),其中每棵二叉树引中只有一个带权为Wi的根节点,其左、右子树均为空。
2)在F中选取两棵根节点权值最小的树作为左、右子树构造一棵新的二叉树,且设置新的二叉树的根节点的权值为其左、右子树根节点的权值之和。
3)在F中删除这两棵二叉树,同时将新得到的二叉树加入F中。
4)重复步骤2)和3),直到F只含一棵树为止。这棵树便是最优二叉树。
综上所述,最优二叉树是从叶子到根构造起来的,每次都是先确定一棵二叉树的左、右子树,然后再构造出树根节点,因此最优二叉树中只有叶子节点和分支数为2的内部节点。若已知叶子的数目为n,则内部节点数比叶子少1,因此整棵树所需的存储空间规模是确定的,可以采用数组空间来存储最优二叉树。
例如,给定字符集合{a,b,c,d)及其权值2、7、4、5,构造最优二叉树的过程如图6-19所示。
由于算法中对构成左、右子树的二叉树不进行限定,因此用哈夫曼算法构造出的最优二叉树的形态不是唯一的。另外,题干中已给出了存放最优二叉树的结构数组Ht的类型定义,以及存储图6-19所构造出的最优二叉树的结构数组Ht(见表6-14)。
由于二叉树中的节点最多只有两个分支,若用“0”和“1”分别标识最优二叉树中的左子树分支和右子树分支,那么从根节点开始到叶子节点为止,按经过分支的次序将相应标识依次排列,可得到由“0”和“1”组成的一个序列,称此序列为该叶子节点的前缀编码。例如,如图6-15所示的最优二叉树叶子节点a、b、c、d的前缀编码分别是110、0、111、10。
当最优二叉树的构造完成后,每个节点的weight域就可挪做他用,在构造哈夫曼编码的过程中,weight域用做被遍历节点的遍历状态标志。从树根出发,以非递归方式遍历最优二叉树的方法是:先沿着树根的左分支向叶子方向搜索,并用code[]记下所经过的分支的标识,同时用cdlen记录节点的路径长度,一直到叶子节点为止,即可得到当前正在访问的叶子的编码。然后,从该叶子节点回退到其父节点F。若刚才是从F的左子树回到F,则下一次应进入F的右子树进行遍历;若是从F的右子树回到F节点,则下一步应继续向F的父节点回退。
由以上分析可知,对于节点F,遍历过程中最多可能以3种不同的情况经过该节点,因此要为F节点的weight域赋予不同的值进行标识。初始时weight=0,当沿遍历路径到达该节点时其weight域值等于0,则进入其左子树分支进行遍历,并将weight置为1:若沿遍历路径到达该节点时其weight域值等于1,则说明刚从其左子树返回,下面应进入其右子树进行遍历并将weight置为2;若沿遍历路径到达该节点时其 weight域值等于2,则说明刚从其右子树返回,下面应继续向该节点的父节点回退,并将weight置为0。遍历路线如图6-20中箭头方向所示。
函数void LeafCode(int root,int n)的功能是:采用非递归方法,遍历最优二叉树的全部叶子节点,为所有的叶子节点构造前缀编码。由于在该函数(1)空缺处之后的语句“strcpy(Hc[p1,code);”,是进行字符串的复制运算,则需要对源串中的串结束标志进行设置,因此(1)空缺处所填写的语句是“code[cdlen]=’\0’”或“code[cdlen]=0”。
(2)空缺处是从右子树向父节点回退的处理,因此该空缺处所填入的内容是“Ht[p].parent”。由于每向上层回退一次,节点的路径长度就会减1,因此(3)空缺处所填写的语句是“—cdlen”或其等价形式。
函数void Decode(char *buff,int root)的功能是:将前缀编码序列翻译成叶子节点的字符序列,并输出。译码的过程是:从根出发,若编码序列的当前字符是“0”,则进入左子树分支,否则进入右子树分支,直到到达一个叶子节点时为止,此时叶子所表示的字符就是翻译出的字符。若编码序列还没有结束,则重新从树根出发,重复上述过程,直到将编码序列结束。所以(4)空缺处所填写的语句是“*buff==’0’”或其等价形式。
由于到达一个叶子节点时,超前读入了一个编码序列中的字符,因此(5)空缺处所填写的语句是“buff—”或其等价形式。
转载请注明原文地址:https://kaotiyun.com/show/yojZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
目前广泛使用的触摸屏技术属于计算机技术中的(2)。
下列选项中,不属于信息处理基本要求的是(22)。
数据展现常需要图表化。美化图表的原则不包括()。
《信息处理系统一开放系统互连一基本参考模型》(ISO7498-2:1989)属于(63)________________。
某企业要求将各销售部门上月的销售额制作成图表。________________能直观形象地体现各销售部门的业绩以及在企业总销售额中的比例。
在Word2010编辑状态下,打开MyDoc.DOCX文档,若要把编辑后的文档以文件名“W1.htm”存盘,可以执行“文件”菜单中的________________命令。
________________不属于移动终端设备。
在Word2007中,若用户需要将一篇文章中的字符串“Internet”全部替换为字符串“因特网”,则可以在编辑菜单中选择()命令。
为了调查某学校3000名学生的身高,抽取了100名学生进行身高测量,以下叙述中正确的是(23)。
在文档中插入形状“圆”后,在圆心位置输入了字符C却看不到,为将字符C显示出来,可以右击该形状,选择将其__________。
随机试题
我国人大常委会已制定的卫生法律共有
企业按月计提无形资产的摊销,应借记“管理费用”等科目,贷记()
A.海金沙B.儿茶C.芦荟D.冰片E.青黛浸火柴杆于本品水浸液中,使着色,干后再浸入盐酸中立即取出,于火焰附近烤,杆上发生深红色反应的药材是
女,26岁,咳嗽、咳脓痰12年,间断咯血,痰量40ml/天。胸片示:两肺下部紊乱。
关于《放射性药品管理办法》,以下哪项不正确?()
我国西南某新建机场为高填方机场,在施工前和施工过程中发生了以下事件:事件一:在机场高填方工程大面积施工前,施工单位在适宜地段开展了高填方试验工作。事件二:为了追赶工期,在土石方施工完成2个月后,施工单位提出了立刻开始摊铺基层与面层施工的申请。事件三:
长城公司为上市公司,2012~2013年发生的与投资相关的交易或事项如下。 (1)2012年7月1日,长城公司向万达公司的控股股东中达公司以每股15元的发行价格定向增发本公司普通股股票500万股(每股面值1元),取得万达公司25%的股权。增发完成后,长
甲偿还了其对乙的赌债1000元,则下列说法正确的是()
甲在2000年6月立下遗嘱,将其遗产的一半由其子乙继承。甲2003年不幸死亡,现甲的继承人与乙在权利上发生纠纷,则()。
坚持按劳分配的主体地位对于坚持中国特色社会主义经济的性质具有重要意义。按劳分配是社会主义公有制在分配领域的体现,坚持按劳分配主体地位的意义是
最新回复
(
0
)