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

throw exception("堆空间用尽");

New1->character=ch; //将第一个字符插入链表

New1->count=1;

New1->next=pfront->next;

pfront->next=New1;

bool replace=0; //判断在已经写入链表的字符中是否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数

for(int i=1;i

{

ch=Input[i]; //获得第i个字符

do

{

pfront=pfront->next;

if((int)pfront->character == (int)ch) //如果在链表中有与当前字符相同的字符，

该字符权值加1

{

pfront->count++;

replace=1;

break;

}

}while(pfront->next);

if(!replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表

{

Node* New=new Node;

if(!New)

throw exception("堆空间用尽");

New->character=ch;

New->count=1;

New->next=pfront->next;

pfront->next=New;

n++;

}

pfront=front; //重置pfront和replace变量为默认值 replace=0;

}

tSize=n; //tSize记录的是编码表中字符个数

CreateHTree(front,n); //创建哈夫曼树

pfront=front;

while(pfront) //销毁整个链表

{

front=pfront;

pfront=pfront->next;

front;

}

时间复杂度：

若输入的字符串长度为n，则时间复杂度为O(n)

2.创建哈夫曼树(void HuffmanTree::CreateCodeTable(Node *p))

算法伪代码：

1. 创建一个长度为2*tSize-1的三叉链表

2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点

的data域，并将对应结点的孩子域和双亲域赋为空

3. 从三叉链表的第tSize个结点开始，i=tSize

3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其

下标x,y。

3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点

3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为

i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i

结点的双亲设置为空

4. 根据哈夫曼树创建编码表

源代码：

void HuffmanTree::CreateHTree(Node *p,int n)

{

root= new BiNode[2*n-1]; //初始化哈夫曼树

Node *front=p->next;

if(n==0)

throw exception("没有输入字符");

for(int i=0;i

root[i].data=front->count;

root[i].lchild=-1;

root[i].rchild=-1;

root[i].parent=-1;

front=front->next;

}

front=p;

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