数据结构Huffman树三、赫夫曼编码2.不等长编码——前缀编码指的是，任何一个字符的编码都不是同一字符集中另一个字符
的编码的前缀。利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文
的总长度最短。3.赫夫曼树结点规律观察赫夫曼树可以发现，赫夫曼树中没有度为1的结点，则一棵有n个叶子结点的赫
夫曼树共有2n-1个结点。1.编码原则：等长编码和不等长编码四、赫夫曼编码的算法实现Weightlchildr
childparent1.赫夫曼树的存储结构2.赫夫曼树和赫夫曼编码的存储表示typedef
struct{unsignedintweight;unsignedintpar
ent,lchild,rchild;}HTNode,HuffmanTree;typedefc
harHuffmanCode;实现赫夫曼编码的算法分为两大部分：一是构造赫夫曼树，二是在赫夫曼树上求叶子结点的编
码3.构造赫夫曼树及求赫夫曼编码的算法思想：（1）已知n个叶子结点，可得出此Huffman树共有m
(2n-1)个结点。即:m=2n-1（2）分配m+1个存储单元（基址为HT）存储此Huffman树。约定：不用下
标为0的存储单元。（3）初始化1至n存储单元，存放叶子结点。约定：无双亲或无孩子的结点相应的域值为0（4）初始化n
+1至m存储单元，各个域值为0。（5）构造Huffman树。即：生成n+1至m结点。（6）从叶子结点到根逆向求每个字符的
Huffman编码。9257166713290000111100
0111100101练习:已知权值W={5,6,2,9,7}0123456789（
5）构造Huffman树。（约定：权值小者为左子树）生成i=n+1～m的结点。for(i=n+1;i<=m;i
++){①在HT的1到i-1中选择parent为0，且weight最小的两个结点，其序号分别为s1和s2。②按权值小
者为左子树原则生成一棵新的二叉树，修改相应结点的lchild、rchild、parent域值。}w
Lrp5HT000600020009000700000
0000000000000073166132577166488297
8995267971316（6）从叶子结点到根逆向求每个字符的Huffman编码。①分配n个
字符编码的头指针向量。②分配求编码的临时工作空间。③循环n次求n个叶子结点的编码for(i=1;i<=n;
++i){从叶子搜索到根进行编码，约定左分支为0，右分支为1。每个字
符的编码以正序存储在HC[i]数组中}012345012345678
9wLrp5HT000600020009000700
0000000000000000073166132577166488
2978995267971316HC字符数组指针01234cd‘\0’5297
1676132901000111startstart‘1’‘0’‘1’startstart
0123‘\0’‘1’‘0’‘1’012‘\0’‘0’‘0’3.求赫夫曼编码的算法描述如
下：voidHuffmanCoding(HuffmanTree&HT,Huff
manCode&HC,intw,intn){inti,j,m,s1,s2,st
art;charcd;unsignedintc,f;
if(n<=1)return;m=2n-1;
HT=(HuffmanTree)malloc((m+1)
sizeof(HTNode));for(i=1;i<=n
;i++){HT[i].weight=w[i-1];HT[i].p
arent=0;HT[i].lchild=0;HT[i].rchi
ld=0;}for(i=n+1;i<=m;i++)
{HT[i].weight=0;HT[i].parent=0;
HT[i].lchild=0;HT[i].rchild=0;}for(p=HT+1,i
=1;i<=n;++i,++P,++w)p={w,0,0,0};for(;i<
=m;++i,++p)p={0,0,0,0};for(i=n+1;i<=m;i++){//建赫
夫曼树//在HT[1..i-1]中选择parent为0且weight最
//小的两个结点，其序号分别为s1和s2。Select(HT,i-1,s1,s2);
//--从叶子到根逆向求每个字符的哈夫曼编码---HC=(HcffmanCode)malloc((n+1)size
of(char));cd=(char)malloc(nsizeof(char));cd[n-1]=''\
0'';HT[s1].parent=i;HT[s2].parent=i
;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].we
ight+HT[s2].weight;}for(i=1;i<=n;++i){start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)/
/从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]=''0'';
elsecd[--start]=''1'';free(cd);//释放工作空间}//Huffman
CodingHC[i]=(char)malloc((n-start)sizeof(char));strcp
y(HC[i],&cd[start]);printf("%s\n",HC[i]);}cn=n-start;
for(j=0;jeeHT,intj，int&s1,int&s2){k=1;while(k<=j)
{if(HT[k].parent==0){min1=HT[k].weight;min2=
HT[k].weight;break;}k++;}
for(k=1;k<=j;k++)if(HT[k].weightt==0){min1=HT[k].weight;s1=k;}for(k=
1;k<=j;k++)if(HT[k].weight){min2=HT[k].weight;s2=k;}}&&？
&&k!=s1parent为0且weight值最小者的序号赋给了s1,weight值次小者的序号赋给了s2。
如果parent为0且weight值最小的两个结点的序号，序号小的赋给s1，序号大的赋给s2。
如何修改程序？Select(HuffmanTreeHT,intj，int&s1,int&s2){k
=1;while(k<=j){if(HT[k].parent==0)
{min1=HT[k].weight;min2=HT[k].weight;s1
=s2=k;break;}k++;}for(k=1;k<=j;k++)
if(HT[k].weightin1=HT[k].weight;s1=k;}for(k=1;k<=j;k++)if
(HT[k].weight].weight;s2=k;}if(s1>s2){k=s1;s1=s2;s2=k;}}
三、习题1．基础知识题（1）判断下列叙述中哪个不正确______A
.将一棵树转换成二叉树后，根结点没有左子树；B.用树的先序和中序遍历可以导出树的后序遍历;C.一深度为K且有2K-1个
结点的二叉树为满二叉树;D.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。A（2）对一个满二
叉树，m个树叶，n个结点，深度为h，则有______.A.n=h+mB.m=2h-1
C.m=h-1D.h+m=2nB（2）高度为h的满二叉树（仅含根结点的二叉树高度为零）的结点最少是多少
_____。Ａ.h＋1B.2h＋1C.2h+1－1D.2h（3）深度为5的二叉树至多有____
_个结点。A．16B．32C．31D．10（4）任何一棵二叉树的叶结点在先
序、中序和后序遍历序列中的相对次序________。A．不发生改变B．发生改变C．不能确定
D．以上都不对CCA（5）树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后
序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论________是正确的。A．树的先根遍历序列与其对应的
二叉树的先序遍历序列相同B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同C．树的先
根遍历序列与其对应的二叉树的中序遍历序列相同D．以上都不对A2．算法设计题二叉树采用二叉链存储，试
设计一个按层次顺序（同一层次自左至右）遍历二叉树的算法。解：本算法要采用一个循环队列Q，先将二叉树根结点入队列，然后出队
列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。因为队列的特点是先
进先出，从而达到按层次顺序遍历二叉树的目的。算法如下：typedefstructBiTNode{TE
lemtypedata;structBiTNodelchild;rchild;}BiTNo
de,BiTree;#definemaxsize100typedefstruct{BiTreebas
e;intfront;intrear;}Sq
Queue;voidLevelorder(BiTreeT){}Initqueue(Q);if
(T){}Enqueue(Q,T);while(!(Q.rear==Q.fro
nt)){Dequeue(Q,T);printf(T->data);
if(T->lchild!=NULL)Enqueue(Q,T->lchile);if(T->rchild!=NULL)Enqueue(Q,T->rchile);}汇编语言程序主要是由指令和伪指令按一定结构组织而成的指令集合，其中指令是指由CPU执行的指令，伪指令是指由汇编程序解释执行的指令。由CPU所能执行的各种指令的集合称为指令系统。一条指令一般由操作码和操作数两部分构成，寻找指令中操作数的方式称为寻址方式。学习汇编语言程序设计，首先必须熟练掌握指令系统和寻址方式。本章主要以8086指令系统为基础，从汇编指令角度，详细地介绍指令的基本格式，操作数的寻址方式，8086指令系统中各类指令的功能、使用方法和应用场合。最后简单介绍80X86和Pentium微处理器中实模式下的新增及扩充的指令功能和使用方法。数据结构Huffman树 |
|
