哈夫曼树的顺序存储形式

⑴ 哈夫曼树，我这样构造对不对，如果对，还有另外的一种形式吗

八个权值是529781423311

(1)从小到大排序357811142329(这是有序序列)
(2)每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8,
取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.
(3)将新结点N8放入有序序列,保持从小到大排序:
78N811142329[注意,新结点N8排在原结点8的后面]
(4)重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15,
结点7的数值较小,将结点7作为左分支,结点8就作为右分支.
(5)将新结点N15放入有序序列,保持从小到大排序:
N81114N152329
(6)重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19,
N8的数值较小,作为左分支,结点11就作为右分支.
(7)将新结点N19放入有序序列,保持从小到大排序:
14N15N192329
(8)重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29,
结点14的数值较小,作为左分支,N15就作为右分支.
(9)将新结点N29放入有序序列,保持从小到大排序:
N192329N29[注意,新结点N29排在原结点29的后面]
(10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42,
N19的数值较小,作为左分支,结点23就作为右分支.
(11)将新结点N42放入有序序列,保持从小到大排序:
29N29N42
(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58,
结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.
(13)将新结点N58放入有序序列,保持从小到大排序:
N42N58
(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100,
数值较小的N42作为左分支,N58就作为右分支.
最后得到"哈夫曼树":

N100
/
N42N58
//
N192329N29
//
N81114N15
//
3578

带权路径长度(WPL):
根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2
根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2
根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3
根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3
根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4
根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4
根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4
根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4
所以,哈夫曼树的带权路径长度(WPL)等于
29*2+23*2+14*3+11*3+8*4+7*4+5*4+3*4=271

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10
从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01
从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110
如此类推,得出所有结点的"哈夫曼编码":
权值29:10
权值23:01
权值14:110
权值11:001
权值8:1111
权值7:1110
权值5:0001
权值3:0000


//C语言测试程序:

//输入叶子结点的总个数:8
//连续输入8个权值:529781423311
//Weight=5Code=0001
//Weight=29Code=10
//Weight=7Code=1110
//Weight=8Code=1111
//Weight=14Code=110
//Weight=23Code=01
//Weight=3Code=0000
//Weight=11Code=001
//huffman'sWPLis:271

#include<stdio.h>
#include<stdlib.h>

#defineMaxValue10000//初始设定的权值最大值
#defineMaxBit10//初始设定的最大编码位数
#defineMaxN10//初始设定的最大结点个数
structHuffNode//哈夫曼树的结点结构
{
intweight;//权值
intflag;//标记
intparent;//双亲结点下标
intleftChild;//左孩子下标
intrightChild;//右孩子下标
};
structCode//存放哈夫曼编码的数据元素结构
{
intbit[MaxBit];//数组
intstart;//编码的起始下标
intweight;//字符的权值
};

//建立叶结点个数为n权值为weight的哈夫曼树huffTree
voidHuffman(intweight[],intn,structHuffNodehuffTree[])
{
inti,j,m1,m2,x1,x2;
//哈夫曼树huffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点
for(i=0;i<2*n-1;i++)
{
if(i<n)
{
huffTree[i].weight=weight[i];
}
else
{
huffTree[i].weight=0;
}
huffTree[i].parent=0;
huffTree[i].flag=0;
huffTree[i].leftChild=-1;
huffTree[i].rightChild=-1;
}
//构造哈夫曼树huffTree的n-1个非叶结点
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;//Maxvalue=10000;(就是一个相当大的数)
x1=x2=0;//x1、x2是用来保存最小的两个值在数组对应的下标

for(j=0;j<n+i;j++)//循环找出所有权重中，最小的二个值
{
if(huffTree[j].weight<m1&&huffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=huffTree[j].weight;
x1=j;
}
elseif(huffTree[j].weight<m2&&huffTree[j].flag==0)
{
m2=huffTree[j].weight;
x2=j;
}
}
//将找出的两棵权值最小的子树合并为一棵子树
huffTree[x1].parent=n+i;
huffTree[x2].parent=n+i;
huffTree[x1].flag=1;
huffTree[x2].flag=1;
huffTree[n+i].weight=huffTree[x1].weight+huffTree[x2].weight;
huffTree[n+i].leftChild=x1;
huffTree[n+i].rightChild=x2;
}
}
//由n个结点的哈夫曼树huffTree构造哈夫曼编码huffCode
voidHuffmanCode(structHuffNodehuffTree[],intn,structCodehuffCode[])
{
structCode*cd=(structCode*)malloc(sizeof(structCode));
intchild,parent;
inti,j;
//求n个叶结点的哈夫曼编码
for(i=0;i<n;i++)
{
cd->start=0;//从0开始计数
cd->weight=huffTree[i].weight;//取得编码对应权值的字符
child=i;
parent=huffTree[child].parent;
//由叶结点向上直到根结点
while(parent!=0)
{
if(huffTree[parent].leftChild==child)
{
cd->bit[cd->start]=0;//左孩子结点编码0
}
else
{
cd->bit[cd->start]=1;//右孩子结点编码1
}
cd->start++;//编码自增
child=parent;
parent=huffTree[child].parent;
}
//重新修改编码，从根结点开始计数
for(j=cd->start-1;j>=0;j--)
{
huffCode[i].bit[cd->start-j-1]=cd->bit[j];
}
huffCode[i].start=cd->start;
huffCode[i].weight=cd->weight;//保存编码对应的权值
}
}
intmain()
{
inti,j;
intm=0;
intn=0;
intweight[20];

printf("输入叶子结点的总个数:");
scanf("%d",&n);
printf("连续输入%d个权值:",n);
for(i=0;i<n;i++)
{
scanf("%d",&weight[i]);
}
structHuffNode*myHuffTree=(structHuffNode*)malloc((2*n-1)*sizeof(structHuffNode));
structCode*myHuffCode=(structCode*)malloc(n*sizeof(structCode));
if(n>MaxN)
{
printf("
定义的n越界，修改MaxN!
");
exit(0);
}
Huffman(weight,n,myHuffTree);
HuffmanCode(myHuffTree,n,myHuffCode);
//输出每个叶结点的哈夫曼编码
for(i=0;i<n;i++)
{
printf("Weight=%-4dCode=",myHuffCode[i].weight);
for(j=0;j<myHuffCode[i].start;j++)
{
printf("%d",myHuffCode[i].bit[j]);
}m=m+myHuffCode[i].weight*myHuffCode[i].start;

printf("
");
}
printf("huffman'sWPLis:%d
",m);

	getchar();

return0;
}

⑵ 哈夫曼树

这是我们的作业题，自己写 的……（可能输入的格式跟你要的不一致，自己改一下）

如果有什么不懂的就问我，我可以把其中所有相关的文件发给你 ^^

注：1、 初始化创建哈夫曼树有三种选择，其中选择编译课本测试数据时和编译源文件是，调用的输入文件分别是：test.txt和input.txt；字母的哈夫曼编码都保存在文件：hmfTree.txt；
2、 用户自定义模式下，需要编码的文件内容保存在ToBeTran.txt中；课本测试数据和源文件代码分别保存在course.txt和sorse.txt中，在（1）中选择不同的选项，则在编码时调用相应的文件进行编码，编码结果保存在文件CodeFile.txt中。
3、 文件译码时，调用文件CodeFile.txt进行译码，得到的结果保存在文件TextFile.txt中。
4、 打印代码文件：调用CodeFile.txt，结果显示在终端并保存在文件CodePrin.txt中。
5、 打印哈夫曼树：用凹入表形式把哈夫曼树显示在终端，同时将它保存在文件TreePrint..txt中。

#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;

typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

typedef struct {
char ch;
char code[7];
}codenode,*code;

void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}

void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}

void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
int i=0;
cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}

void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数: ");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;
HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}

void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}

void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}

void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}

void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}

void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}

}

注：
input.txt文件中保存一下数据：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}

⑶ 哈夫曼树HT存储结构的初态和末态怎么写

定义哈夫曼树与编码的存储结构与数据类型
typedef struct
{
char data;//节点值
int weight; //权重
int parent; //双亲节点
int lchild; //左孩子节点
int rchild; //右孩子节点
} HTNode;

typedef struct
{
char cd[N]; //存放哈夫曼码
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //创建哈夫曼树
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根据哈夫曼树计算每个元素的哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n) //输出每个元素的哈夫曼编码

⑷ 数据结构-构造哈夫曼树

填空题
1.2的k-1次幂
2.根
3.中续
4.(log2n)+1
5.链式存储
6.最小
7.n-1
8.5
9.每个顶点的访问次数
10.任意
单选
1.B
2.D
3.C
4.B
5.A
6.A
7.B
8.B
9.B
10.C
判断
1.对
2.对
3.对
4.错
5.对
6.对
7.对
8.错
9.对
10.对
综合
36
有的不确定啊！

⑸ 哈夫曼编码

/* algo6-1.c 求哈夫曼编码。实现算法6.12的程序 */
//------------------- 公用的常量和类型 ----------------------------
#include<stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define UINT_MAX 1000
typedef int Status;

/* c6-7.h 哈夫曼树和哈夫曼编码的存储表示 */
typedef struct HTNode
{
char leaf;
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; /* 动态分配数组存储哈夫曼编码表 */

typedef char **HuffmanCode; /* 动态分配数组存储哈夫曼编码表 */
typedef struct Node
{
char leaf;
unsigned int weight;
struct Node * next;
}LeafNode,*LeafLink;

typedef struct
{
LeafLink head;
unsigned len;
}LeafLinkList;

int min1(HuffmanTree t,int i)
{ /* 函数void select()调用 */
int j,flag;
unsigned int k=UINT_MAX; /* 取k为不小于可能的值 */
for(j=1;j<=i;j++)
if(t[j].weight<k&&t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
return flag;
}

void select(HuffmanTree t,int i,int *s1,int *s2)
{ /* s1为最小的两个值中序号小的那个 */
int j;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) /* 算法6.12 */
{ /* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*/
int m,i,s1,s2,start;
int n=L.len;
unsigned c,f;
LeafLink ptr;
HuffmanTree p;
char *cd;
if(n<=1)
return;
m=2*n-1;
printf("表长为%d\t哈夫曼树含节点数为%d\n",n,m);
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0号单元未用 */
ptr=L.head->next;
for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next)
{
(*p).leaf=ptr->leaf;
printf("%d\t",(*p).leaf);
(*p).weight=ptr->weight;
printf("%d\n",(*p).weight);
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<=m;++i,++p)
{
(*p).parent=0;
(*p).leaf=0;
}
for(i=n+1;i<=m;++i) /* 建哈夫曼树 */
{ /* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 */
select(HT,i-1,&s1,&s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
/* 从叶子到根逆向求每个字符的哈夫曼编码 */
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/* 分配n个字符编码的头指针向量([0]不用) */
cd=(char*)malloc(n*sizeof(char)); /* 分配求编码的工作空间 */
cd[n-1]='\0'; /* 编码结束符 */
for(i=1;i<=n;i++)
{ /* 逐个字符求哈夫曼编码 */
start=n-1; /* 编码结束符位置 */
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
/* 从叶子到根逆向求编码 */
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
/* 为第i个字符编码分配空间 */
strcpy(HC[i],&cd[start]); /* 从cd复制编码(串)到HC */
}
free(cd); /* 释放工作空间 */
for(i=1;i<=n;i++)
{
printf("%c编码为%s:\n",HT[i].leaf,HC[i]);
}
}

void InitLeafList(LeafLinkList &L)
{
L.head=(LeafLink)malloc(sizeof(LeafLink));
L.head->next=NULL;
L.len=0;
}
void PrintList(LeafLinkList L)
{
LeafLink p;
p=L.head->next;
printf("打印链表\n");
printf("表长为%d\n",L.len);
while(p!=NULL)
{
printf("%c or %d,%u\t",p->leaf,p->leaf,p->weight);
printf("打印一个节点\n");
p=p->next;
}
printf("打印结束\n");
printf("\n");
}

void EnLeafList(LeafLinkList &L,char ch)
{
LeafLink p,pre,temp;
int flag=0;
pre=p=L.head;
printf("%d即为%c******\n\n",ch,ch);
if(p->next==NULL) //p->next=NULL则为第一次插入操作
{
printf("第一次插入\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
p->next=temp;
L.len++;
}

else
{

p=p->next;
while(p!=NULL)
{

if(ch==p->leaf)
{
p->weight++;
printf("加权\n");
p=NULL;
flag=1;
} //权重加一
else if(ch<p->leaf) //插入
{
printf("插入A\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=p;
pre->next=temp;
L.len++;
flag=1;
p=NULL;
}
else //继续寻找插入点
{
pre=p;
p=p->next;
}
}

if(p==NULL&&flag!=1) //若p=NULL则插到链尾
{
printf("插入B\n");
temp=(LeafLink)malloc(sizeof(LeafNode));
temp->leaf=ch;
temp->weight=1;
temp->next=NULL;
pre->next=temp;
L.len++;
}
}

}
void EnCoding()
{
FILE *fp,*fr,*fc;
HuffmanTree HT;
HuffmanCode HC;
int i,n;
LeafLinkList L;
InitLeafList(L);
char filename[15];
char ch;
printf("请输入文件名:\n ");
scanf("%s",filename);
if( !(fp=fopen(filename,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("文件已经打开\n");
while(!feof(fp))
{

ch=fgetc(fp);
if(ch==-1)
{
printf("结束统计\n");
}
else
{
EnLeafList(L,ch);
}
}
PrintList(L);
HuffmanCoding(HT,HC, L);
n=L.len;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
char TreeName[15];
printf("把哈夫曼树存入文件，请输入文件名:\n ");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"wb")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("文件已经打开\n");
//把哈夫曼树存入文件
printf("%d\n",n);
printf("把树的长度先存入\n");
putw(n,fr); //把树的长度先存入
for(i=1;i<=2*n-1;i++)
if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件写入出错\n");
fclose(fr);

printf("打印原来的树\n");
for(i=1;i<=2*n-1;i++)
printf("%c %u %u %u %u\n",HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild );
fclose(fr);

printf("把编码结果存入文件，请输入文件名:\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"wb")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符

printf("待编码的文件位置指针重新指向开始位置\n");
printf("对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\n");
rewind(fp);
while(!feof(fp))
{

ch=fgetc(fp);
printf("%c\n",ch);
if(ch==-1)
{
printf("结束编码\n");
}
else
{
for(int tap=0,i=1;tap==0&&i<=n;) //查找，该叶子对应的编码串
{
if(ch==HT[i].leaf) //找到，打印出对应的编码，并存入文件
{
printf("%s\n",HC[i]);
fputs(HC[i],fc); //将编码字符串存入文件

tap=1;
}
else
{
i++;
}
}
}
}
fclose(fp); //关闭文件
fclose(fc); //关闭文件
}
int decode(FILE *fc,HuffmanTree HT,int n)
{
while(!feof(fc))
{
char ch=fgetc(fc);
if(ch=='0')
{
n=HT[n].lchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else if(ch=='1')
{

n=HT[n].rchild;
if(HT[n].leaf!=0)
{
printf("%c",HT[n].leaf);
return OK;
}
else
{
decode(fc,HT,n);
return OK;
}
}
else return OK;
}
return ERROR;
}

void Decoding() //解码文件，并将结果显示出来
{
FILE *fc,*fr;
char CodeFileName[15],ch,TreeName[15];
int i;
printf("解码文件，请输入文件名(如*.dat):\n ");
scanf("%s",CodeFileName);
if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("存放编码结果文件已经打开\n");

//读入哈夫曼树

HuffmanTree HT;
printf("取出对应的哈夫曼树文件，请输入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
int n=getw(fr); //将叶子数目取出
printf("叶子数目%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */

for(i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件读出出错\n");
int length=2*n-1; //总长度
printf("总结点数目为：%d\n",n);
printf("该文件译码后得到的源文件为：\n");
printf("**************************************\n");
while(!feof(fc))
{
decode(fc,HT,length);
}
printf("**************************************\n");
printf("\n\n");
}

int PreOrderPrint(HuffmanTree HT,int n,int count)
{
if(HT[n].lchild)
{
for(int i=0;i<count;i++)
printf(" ");
printf("%u\n",HT[n].weight);
if( PreOrderPrint(HT,HT[n].lchild, ++count) )
if (PreOrderPrint(HT,HT[n].rchild, ++count))
return OK;
return ERROR;
}
else return OK;
}
void PrintTree()
{
//读入哈夫曼树
FILE *fr;
char TreeName[15];
HuffmanTree HT;
printf("取出对应的哈夫曼树文件(如*.dat)，请输入文件名,\n");
scanf("%s",TreeName);
if( !(fr=fopen(TreeName,"rb")) ) //打开存放哈夫曼树的文件
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}
int n=getw(fr); //将叶子数目取出
printf("含叶子数%d\n",n);
HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); /* 然后分配空间，0号单元未用 */

for(int i=1;i<=2*n-1;i++)
if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1)
printf("文件读出出错\n");
int count=0;
n=2*n-1;
printf("总结点数目为；%d\n",n);
printf("哈夫曼树的存储形式为：\n");
for(i=1;i<=n;i++)
{
printf("%c,%u,%u,%u,%u\n",HT[i].leaf,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
printf("哈夫曼树的凹入表形式为：\n");
PreOrderPrint(HT,n,count);
}
void PrintCodeFile()
{
FILE *fc;
printf("打印编码后的文件，请输入文件名(如*.dat):\n ");
char CodeFileName[15];
scanf("%s",CodeFileName);

if( !(fc=fopen(CodeFileName,"r")) )
{
printf("打开文件失败，请输入正确的文件名!! ");
exit(0);
}

char ch=getchar(); //接收执行scanf语句时最后输入的回车符
printf("打印编码后的文件，打印方法一\n");
int flag=1;
while(!feof(fc))
{

ch=fgetc(fc);
if(ch==-1)
{
printf("结束打印\n");
}
else
{
printf("%c",ch);
if(flag<=49)
flag++;
else
{
flag=1;
printf("\n");
}
}
}
printf("打印编码后的文件，打印方法二\n");
rewind(fc);
char str[50];
while(!feof(fc))
{
fgets(str,51,fc);
puts(str);
}
fclose(fc); //关闭文件
}

void Initialization() //系统初始化
{
printf("**************************************\n");
printf("*编码文件请输入e\n*译码文件请输入d\n*打印编码后的文件请输入p\n*打印哈夫曼树请输入t\n*结束请输入q \n");
printf("**************************************\n");
printf("\n\n\t\t字符:\n\n\n");
printf("**************************************\n");
printf("* 输入一个字符:e,d,p,t or q *\n");
printf("**************************************\n");
}

int read(char cmd)
{
int i,flag=0;
char choice[10]={'e','E','d','D','p','P','T','t','Q','q'};
for(i=0;i<10;i++)
{
if(cmd==choice[i]) flag++;
}
if(flag==1) return FALSE;
else return TRUE;
}
void ReadCommand(char &cmd) // 读入操作命令符
{
do
{
cmd=getchar();
}
while(read(cmd));
}
void Interpret(char cmd) //解释执行操作命令
{
switch(cmd)
{
case 'e':case'E':
EnCoding();
Initialization();
break;
case 'd':case'D':
Decoding();
Initialization();
break;
case 'p':case'P':
PrintCodeFile();
Initialization();
break;
case't':case'T':
PrintTree(); // Print();
Initialization();
break;
case 'q': case'Q': exit(0);
break;
default: printf("Error\n");break;
}
}
void main() //用户驱式
{
char cmd;
Initialization(); //初始化
do
{
ReadCommand(cmd); //读入一个操作命令符
Interpret(cmd); //解释执行操作命令符
}
while(cmd!='q'&&cmd!='Q');
EnCoding();
Decoding();

}

⑹ 什么是哈夫曼树呢

夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。
普通二叉树的用途也普通，比较通用，就是信息存储和查找。
普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。

⑺ “哈夫曼树”的建立方法是什么

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 k1、k2、…、kn，则哈夫曼树的构造规则为：

(1) 将k1、k2、…，kn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

⑻ 哈夫曼树是什么求解

哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。
首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。（注：码字即为符号经哈夫曼编码后得到的编码，其长度是因符号出现的概率而不同，所以说哈夫曼编码是变长的编码。）
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构： struct tree{
float weight; /*权值*/union{char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/};struct tree *right; /*树的右结点*/};struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/};例：若字母A，B，Z，C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
构造好哈夫曼树后，就可根据哈夫曼树进行编码。例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。例如：a,b,c,d的编码为：0，10，101，11，对于编码串：1010就可翻译为bb或ca，因为b的编码是c的编码的前缀。刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径，向左孩子前进编码为0，向右孩子前进编码为1，当然你也可以反过来规定。
这种编码方法是静态的哈夫曼编码，它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。 静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码，存储编码信息时，若用与通讯网络，就会引起较大的延时；三、对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。
因此，后来有人提出了一种动态的哈夫曼编码方法。动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。动态哈夫曼编码比静态哈夫曼编码复杂的多，有兴趣的读者可参考有关数据结构与算法的书籍。
前面提到的JPEG中用到了哈夫曼编码，并不是说JPEG就只用哈夫曼编码就可以了，而是一幅图片经过多个步骤后得到它的一列数值，对这些数值进行哈夫曼编码，以便存储或传输。哈夫曼编码方法比较易懂，大家可以根据它的编码方法，自己编写哈夫曼编码和解码的程序。

⑼ 【问题描述】

nan