发布时间 : 星期日 文章北邮数据结构实验报告更新完毕开始阅读897193b19a89680203d8ce2f0066f5335b81676f
Node *front=p->next; if(n==0)
throw exception(\没有输入字符\ for(int i=0;i
root.data=front->count; root.lchild=-1; root.rchild=-1; root.parent=-1; front=front->next; } front=p; int New1,New2; for(i=n;i {
SelectMin(New1,New2,0,i); //从0~i中选出两个权值最小的结点
root.parent=root.parent=i; //用两个权值最小的结点生成新结点， 新节点为其双亲
root.data=root.data+root.data;//新结点的权值为其孩子的权值的和 root.lchild=New1; root.rchild=New2; root.parent=-1;
}
CreateCodeTable(p); //创建编码表 }
时间复杂度：
在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数 的时间复杂度为O(n^2)
3.
创
建
编
码
表
(void
HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码： 1.初始化编码表
2.初始化一个指针，从链表的头结点开始，遍历整个链表
将链表中指针当前所指的结点包含的字符写入编码表中
得到该结点对应的哈夫曼树的叶子结点及其双亲 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0
如果不止一个叶子结点，从当前叶子结点开始判断 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否 则为1
child指针指向叶子结点的双亲，parent指针指向child指针的双亲， 重复的操作
将已完成的编码倒序 取得链表中的下一个字符 3.输出编码表 源代码：
void HuffmanTree::CreateCodeTable(Node *p) {
HCodeTable=new HCode; //初始化编码表 Node *front=p->next; for(int i=0;i {
HCodeTable.data=front->character; //将第i个字符写入编码表
int child=i; //得到第i个字符对应的叶子节点 int parent=root.parent; //得到第i个字符对应的叶子节点的双亲 int k=0;
if(tSize==1) //如果文本中只有一种字符，它的编码为0 {
HCodeTable.code='0'; k++; }
while(parent!=-1) //从第i个字符对应的叶子节点开始，寻找它到根结点的路径 {
if(child==root.lchild) //如果当前结点为双亲的左孩子，则编码为0， 否则编码为1
HCodeTable.code='0'; else
HCodeTable.code='1'; k++;
child=parent; parent=root.parent; }
HCodeTable.code='';
Reverse(HCodeTable.code); //将编码逆置 front=front->next; //得到下一个字符 }
cout for(i=0;i {