数据结构考研分类复习真题 第六章 答案 (五)[50]

数据结构考研分类复习真题 第六章 答案 (五)[50]  

　　 ．（ ）哈夫曼树的构造过程

　　① 根据给定的n个权值{W W W … Wn}构成n棵二叉树的集合F={T T … Tn} 其中每棵二叉树Ti只有权值为Wi的根结点 其左右子树均为空

　　② 在F中选取两棵根结点的权值最小的树作左右子树构造一棵新二叉树 新二叉树根结点的权值为其左右子树上根结点的权值之和

　　③ 在F中删除这两棵树 同时将新得到的二叉树加入F中

　　④ 重复②和③ 直到F中只剩一棵树为止 这棵树便是哈夫曼树

　　（ ）含有n个叶子结点的哈夫曼树共有 n 个结点 采用静态链表作为存储结构 设置大小为 n 的数组 现将哈夫曼树的结点及树的结构定义如下

　　typedef struct{float weight ;   //权值　　int parent lc rc;//双亲 左 右子女 }node ;　　typedef node HufmTree[ *n ];　　void Huffman(int n float w[n] HufmTree T)　　//构造n个叶子结点的哈夫曼树T n个权值己放在W[n]数组中　　{int i j p p          //p p 为最小值和次最小值的坐标　　float small small ;   //small 和small 为权值的最小值和次小值　　for(i= ;i< *n ;i++)   //置初值 结点的权 左 右子女 双亲　　{T[i] parent= ; T[i] lc= ; T[i] rc= ;　　if(i<n) T[i] weight=w[i]; else T[i] weight= ;　　}　　for (i=n ;i< *n ;i++)         //构造新二叉树　　{p =p = ;small =small =maxint; //初值　　for(j= ;j<i;j++)　　if(T[j] weight<small && T[j] parent== )           //最小值　　{p =p ; small =small ; p =j; small =T[j] weight;}　　else if(T[j] weight<small && T[j] parent== )       //次小值　　{p =j;small =T[j] weight;}　　T[i] weight=T[p ] weight+T[p ] weight;              //合并成一棵新二叉树　　T[i] lc=p ; T[i] rc=p ;                             //置双亲的左右子女　　T[p ] parent=i; T[p ] parent=i;                     //置左 右子女的双亲　　}//for(i= ;i< *n ;i++) }//结束huffman

　　求哈夫曼编码的算法

　　typedef struct {char bit[n]; int start;}codetype;　　void HuffmanCode(CodeType code[n] HufmTree T) //哈夫曼树T已求出 现求其哈夫曼编码　　{int i j c p;　　CodeType cd;　　for(i= ;i<n;i++)　　{cd start=n;c=i;p=T[i] parent;　　while(p!= )　　{cd start ;　　if(T[p] lc==c) cd bit[cd start]= //左分枝生成代码 　　else cd bit[cd start]= ;         // 右分枝生成代码 　　c=p; p=T[p] parent;                  //双亲变为新子女 再求双亲的双亲　　}　　code[i]=cd;        //成组赋值 求出一个叶子结点的哈夫曼编码　　}//for    }//结束HuffmanCode