北邮信通院数据结构实验报告三哈夫曼编码器.docx

北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北京邮电大学电信工程学院
数据结构实验报告
实验名称：实验三树——哈夫曼tr[i++]=ch;//记录原始字符串
ch=();//读取下一个字符
}
str[i]='\0';
n=0;
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
4
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
-
for(i=0;i<256;i++)
{
if(nNum[i]>0)//若nNum[i]==0，字符未出现
{
l[n]=(char)i;
a[n]=nNum[i];
n++;
}
}
}
时间复杂度为O（1）；
2）创立哈夫曼树：算法过程：
Huffman树采用次序存储---数组；
数组的前n个结点存储叶子结点，然后是分支结点，最后是根结点；
首先初始化叶子结点元素—循环实现；
以循环结构，实现分支结点的合成，合成规则按照huffman树组成规则进行。
重点点：选择最小和次小结点合成。
voidHuffman::CreateHTree()
{
HTree=newHNode[2*n-1];//根据权重数组a[0..n-1]初始化Huffman树
for(intj=0;j<n;j++)
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
5
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
-
{
HTree[j].weight=a[j];
HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1;
}
intx,y;
for(inti=n;i<2*n-1;i++)//开始建Huffman树
{
SelectMin(HTree,i,x,y);//从1~i中选出两个权值最小的结点
HTree[x].parent=HTree[y].parent=i;
HTree[i].weight=HTree[x].weight+HTree[y].weight;
HTree[i].LChild=x;
HTree[i].RChild=y;
HTree[i].parent=-1;
}
}
2
时间复杂度为O(n)
voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2)
{
inti;
找一个比较值的开端值
for(i=0;i<n;i++)//找i1
{if(hTree[i].parent==-1)
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
6
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
-
{i1=i;break;}
}
i++;
for(;i<n;i++)//找i2
{if(hTree[i].parent==-1)
{i2=i;break;}
}
if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的
{intj=i2;i2=i1;i1=j;}
开始找最小的两个
i++;