哈夫曼树带权路径长度_c 哈夫曼树编码_数据结构哈夫曼树编码(12)

int New1,New2;

for(i=n;i<2*n-1;i++)

{

SelectMin(New1,New2,0,i); //从0~i中选出两个权值最小的结点

root[New1].parent=root[New2].parent=i; //用两个权值最小的结点生成新结点，

新节点为其双亲

root[i].data=root[New1].data+root[New2].data;//新结点的权值为其孩子的权值的和 root[i].lchild=New1;

root[i].rchild=New2;

root[i].parent=-1;

}

CreateCodeTable(p); //创建编码表

}

时间复杂度：

在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数

的时间复杂度为O(n^2)

3.创建编码表(void HuffmanTree::CreateCodeTable(Node *p))

算法伪代码：

1.初始化编码表

2.初始化一个指针，从链表的头结点开始，遍历整个链表

2.1 将链表中指针当前所指的结点包含的字符写入编码表中

2.2 得到该结点对应的哈夫曼树的叶子结点及其双亲

2.3 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0

2.4 如果不止一个叶子结点，从当前叶子结点开始判断

2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否

则为1

2.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，

重复2.4.1的操作

2.5 将已完成的编码倒序

2.6 取得链表中的下一个字符

3.输出编码表

源代码：

void HuffmanTree::CreateCodeTable(Node *p)

{

HCodeTable=new HCode[tSize]; //初始化编码表

Node *front=p->next;

for(int i=0;i

{

HCodeTable[i].data=front->character; //将第i个字符写入编码表

int child=i; //得到第i个字符对应的叶子节点

int parent=root[i].parent; //得到第i个字符对应的叶子节点的双亲

int k=0;

if(tSize==1) //如果文本中只有一种字符，它的编码为0

{

HCodeTable[i].code[k]=0;

k++;

}

while(parent!=-1) //从第i个字符对应的叶子节点开始，寻找它到根结点的路径

{

if(child==root[parent].lchild) //如果当前结点为双亲的左孩子，则编码为0，

否则编码为1

HCodeTable[i].code[k]=0;

else

HCodeTable[i].code[k]=1;

k++;

child=parent;

parent=root[child].parent;

}

HCodeTable[i].code[k]=;

Reverse(HCodeTable[i].code); //将编码逆置

front=front->next; //得到下一个字符

}

cout<<"编码表为："<

for(i=0;i

{

cout<

parent=root[parent].lchild;

else //编码为1则寻找右孩子

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-35162-12.html