❶ 求帮忙用c语言写哈夫曼编码
由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n－1个结点，可以用一个大小为2n－1的一维数组存放哈夫曼树的各个结点。在哈夫曼树构造好后，为了求得哈夫曼编码需要走一条从根结点出发到叶子结点的路径，则对每个结点既要知道其双亲还要知道孩子结点的信息。所以一维数组的每个元素包括四个数据项：结点的权值、结点的双亲结点下标号、左右孩子结点下标号。数据类型的定义如下：
typedef struct Node
{
int weight ;
int parent, LChild,RChild ;
} HTNode, * HTree;
typedef char *HuffmanCode ;
创建哈夫曼树并求哈夫曼编码的算法如下：
viod CreatHTree(HTree ht , HuffmanCode hc,int * w, int n)
{ /*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc */
int start;
m=2*n-1;
ht=(HTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;i++)
ht[i] ={ w[i],0,0,0};
for(i=n+1;i<=m;i++)(* ht)[i] ={0,0,0,0};/* 初始化*/
for(i=n+1;i<=m;i++)
{
select(ht,i-1,&s1,&s2);
/* 在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回，select函数要求在上机调试使补充定义*/
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 *));
cd=(char * )malloc(n * sizeof(char));
cd[n-1]＝’\0’；
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,p=ht[i].parent; p!=0; c=p,p=ht[p].parent)
if(ht[p].LChild==c) cd[--start]=‘0’;
else cd[--start]=‘1’;
hc[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(hc[i],&cd[start]);
}
free(cd);
}
数组ht的前n个单元存放叶子结点的信息，最后一个单元存放的是根结点。
自己写个主程序，把八个字符的频率读入，调用CreatHTree就可以了
❷ C语言编写哈夫曼树
// huffman.cpp : Defines the entry point for the console application.
//
#include <iostream.h>
#include <stdio.h>
#include <string.h>
const long wordnum = 1000;//最大不同单词数
const long code_len = wordnum/10;
const long wordlen = 30;//单词最长长度
const long codemax = 10000;//最大haffuman编码长度
const long wordmax = 10000;//最大单词数
//str类定义
class str
{
public:
str();
bool operator<(str obj);//运算符重载方便对str的排序使用二分搜索模板
bool operator>(str obj);
str operator=(char p[]);
str operator++(int);//重载后缀方式的＋＋
char *getword();
long getfre();
protected:
private:
char word[wordlen];
long frequence;
};
str::str()
{
frequence = 0;
}
//以下为重载str类中的运算符
bool str::operator<(str obj)
{
if(strcmp(word,obj.word) < 0)
return true;
else
return false;
}
bool str::operator>(str obj)
{
if(strcmp(word,obj.word) > 0)
return true;
else
return false;
}
str str::operator=(char p[])
{
strcpy(word,p);
return *this;
}
str str::operator++(int x)
{
frequence ++;
return *this;
}
char * str::getword()
{
return word;
}
long str::getfre()
{
return frequence;
}
//str类定义结束
//Node类定义
class Node
{
public:
Node();
bool operator<(Node obj);//运算符重载方便对Node的排序使用堆模板
bool operator<=(Node obj);
bool operator>(Node obj);
Node operator=(str obj);
Node operator+(Node &obj);
Node *leftp();//类外获取指向当前节点的孩子的指针
Node *rightp();
char *getword(Node *p);//类外获取节点信息
long getfrequence();
protected:
private:
char word[wordlen];
long frequence;
Node *left, *right;
};
Node::Node()
{
strcpy(word,"NULL");
left = NULL;
right = NULL;
}
//以下为重载Node类中的运算符
bool Node::operator<(Node obj)
{
if(frequence < obj.frequence)
return true;
else
return false;
}
bool Node::operator<=(Node obj)
{
if(frequence <= obj.frequence)
return true;
else
return false;
}
bool Node::operator>(Node obj)
{
if(frequence > obj.frequence)
return true;
else
return false;
}
Node Node::operator+(Node &obj)
{
Node sum;
sum.frequence = frequence + obj.frequence;//指针指向了NULL
sum.left = this;
sum.right = &obj;
return sum;
}
Node Node::operator=(str obj)
{
strcpy(word,obj.getword());
frequence = obj.getfre();
return *this;
}
Node * Node::leftp()
{
return left;
}
Node * Node::rightp()
{
return right;
}
char * Node::getword(Node *p)
{
return p->word;
}
long Node::getfrequence()
{
return frequence;
}
//Node类定义结束
//str类专门用于统计词频使用，Node则用于构造huffman树，由于两者使用的key不同，前者是word的字典序
//后者是词频，于是使用了两个类来实现。
class huffman
{
public:
huffman();
template<typename entry>
friend bool binarysearch(entry list[wordnum],entry target,long bottom,long top,long &position);
template<typename entry>
friend void buidheap(entry a[wordnum], long number);
template<typename entry>
friend void heapify(entry a[wordnum], long high, long low);
template<typename entry>
friend void swap(entry a[wordnum], long i, long j);
bool Stat();
void Encode();
bool Decode(char code[]);
Node update(long end);
void proce_code();
void Inorder(Node *current, char currentcode[], long &num);
protected:
private:
Node SortedNode[wordnum];//从中产生huffman树
char NodeCode[wordnum][wordnum/10];//相应编码
Node root;
bool sign;//用于标记是否已经建立了huffman树
long n;//叶子节点个数
};
huffman::huffman()
{
sign = false;
}
//二分用于统计词频
template<typename entry>
bool binarysearch(entry list[wordnum], entry target, long bottom, long top, long &position)
{
while(bottom <= top)
{
position = (bottom + top)/2;
if(list[position] < target)
bottom = position + 1;
else if(list[position] > target)
top = position - 1;
else
return true;
}
return false;
}
//建立最小堆及调整为最小堆
template<typename entry>
void swap(entry a[wordnum], long i, long j)
{
entry s;
s = a[i];
a[i] = a[j];
a[j] = s;
}
template<typename entry>
void buidheap(entry a[wordnum], long number)
{
long i ,j;
for(i = number/2; i >= 1; i--)
{
j = i;
while(j <= number/2)
{
if(a[j] > a[2*j] || (a[j] > a[2*j + 1] && 2*j + 1 <= number))
{
if(a[2*j] > a[2*j + 1] && 2*j + 1 <= number)
{
swap(a, j, 2*j+1);
j = 2*j + 1;
}
else
{
swap(a, j ,2*j);
j = 2*j;
}
}
else
break;
}
}
}
template<typename entry>
void heapify(entry a[wordnum], long high, long low)
{
long j = low;
while(j <= high/2)
{
if(a[j] > a[2*j] && a[j] > a[2*j + 1])
{
if(a[2*j] > a[2*j + 1] && 2*j + 1 <= high)
{
swap(a, j, 2*j+1);
j = 2*j + 1;
}
else if(2*j <= high)
{
swap(a, j, 2*j);
j = 2*j;
}
}
else if(a[j] <= a[2*j] && a[j] > a[2*j + 1] && 2*j + 1 <= high)
{
swap(a, j, 2*j+1);
j = 2*j + 1;
}
else if(a[j] <= a[2*j + 1] && a[j] > a[2*j] && 2*j <= high)
{
swap(a, j, 2*j);
j = 2*j;
}
else
break;
}
}
//词频统计函数Stat()
bool huffman::Stat()
{
long i,position;
char p[wordmax],*get;
str s[wordnum],current;
n = 0;
while(gets(p) != NULL && strcmp(p,"@") != 0)
{
get = strtok(p," ,.!/-:;?");
while(get != NULL)
{
current = get;
if(binarysearch(s,current,0,n,position) == true && n < wordnum - 1)
s[position] ++;
else
{
n ++;
if(n < wordnum - 1)
{
if(s[position] < current && current.getfre() < s[position].getfre())
position ++;
for(i = n; i >= position; i --)
s[i+1] = s[i];
s[position] = current;
s[position] ++;
}
}
get = strtok(NULL," ,.!/-:;?");
}
}
for(i = 1; i <= n && i < wordnum; i ++)
SortedNode[i] = s[i-1];
if(n < wordnum)
return true;
else
{
n = wordnum - 1;
return false;
}
}
//建立huffman树函数
void huffman::Encode()
{
int i;
sign = true;
buidheap(SortedNode,n);
for(i = 1; i < n; i ++)
root = update(n-i+1);
}
Node huffman::update(long end)
{
Node *p,*q;
Node newNode;
p = new Node;
q = new Node;
*p = SortedNode[1];
swap(SortedNode,1,end);
heapify(SortedNode,end-1,1);//取出了一个最小元，然后将堆进行了调整
*q = SortedNode[1];
newNode = *p + *q;
SortedNode[1] = newNode;
heapify(SortedNode,end-1,1);//又取出最小元，并且把新节点赋为SortedNode[1]，调整了堆
return SortedNode[1];
}
//解码函数
bool huffman::Decode(char code[codemax])
{
int i;
Node *find = &root;
Node *l = NULL,*r = NULL;
bool flag = true;
if(sign == true)
{
for(i = 0; code[i] != '\0' && flag == true; i ++)
{
l = find->leftp();
r = find->rightp();
if(code[i] == '0' && l != NULL)
find = l;
else if(code[i] == '1' && r != NULL)
find = r;
else flag = false;
if(find->leftp() == NULL && find->rightp() == NULL)
{
printf("%s ",find->getword(find));
find = &root;
}
}
if(!((find->leftp() == NULL && find->rightp() == NULL) || find == &root))
{
cout << "There are some wrong codes in th input!" << endl;
flag = false;
}
}
else
flag = false;
return flag;
}
void huffman::Inorder(Node *current, char currentcode[], long &num)
{
Node *l, *r;
char cl[code_len], cr[code_len];
if(current != NULL)
{
l = current->leftp();
r = current->rightp();
strcpy(cl,currentcode);
strcat(cl,"0");
strcpy(cr,currentcode);
strcat(cr,"1");
Inorder(l, cl, num);
if(l == NULL && r == NULL)
{
SortedNode[num] = *current;
strcpy(NodeCode[num],currentcode);
num ++;
}
Inorder(r, cr, num);
}
}
void huffman::proce_code()//利用中序遍历来得到相应的编码
{
char current[code_len] = "";
long num = 1;
Inorder(&root, current,num);
for(long i = 1; i <= n; i ++)
{
cout << SortedNode[i].getword(&SortedNode[i]) << "----" << NodeCode[i]<<" " ;
if(i%3 == 0) cout << endl;
}
}
int main()
{
huffman test;
char code[codemax];
char order;
cout << "显示编码(Show)" << " "<< "解码(Decode)" << " " <<"退出(Quit)" << endl;
cout << "Input the passage, to end with a single @ in a single line:" << endl;
test.Stat();
test.Encode();
cout << "Encoded!" << endl;
while(cin >> order)
{
if(order == 's' || order == 'S')
{
test.proce_code();
cout << "Proced!" << endl;
}
else if(order == 'd' || order == 'D')
{
cout << "Input the codes:" << endl;
cin >> code;
while(test.Decode(code))
cin >> code;
}
else if(order == 'q' || order == 'Q')
break;
}
return 0;
}
❸ c语言版 哈弗曼编码和译码
哈弗曼编码涵义是将一窜数字或者字母按哈弗曼数的形式编码，并使得这窜字符中的每个数字或者字母都能被唯一的“0，1”序列来编码，而且没有相同的前缀，这是一种非等长的编码方式。如果你觉得这样解释很难听懂的话就举个例子：如果用计算机发信息，只能用0和1，但是每个字母的使用频度又不一样，比如a ,i,o,e等这些字母使用的就多些，而z,v这样的字母使用的就少一些，如果所有字母都用等长的0,1序列来编码的话会造成浪费，那么我们就把常用的字母用少点的0,1，进行编码（比如用两个或三个），不常用的再用多点0,1编码，但是还不能造成油相同前缀的情况，这会使计算机无法识别，比如E用010，z用01001，计算机就只能识别出前面三个是E，而后面就抛弃或者识别出别的字母。哈弗曼编码就是出于这样的条件下产生的。也许这样的形容还是很抽象，那么再具体点。加入a,b,c,d,e使用的频度分别是10,7,5,5,3那么就可以构造哈弗曼数：从树顶到树根，假如左边是0，右边是1，那么就能得到他们的哈弗曼编码(就是从上到下，到达他们字母经过的路径)，分别是：a:00;b:11;c:10;d:011;e:010;你可以发现他们全部没有相同的前缀。具体的编码方式我可以大致的跟你说下，因为我还在上班所以无法使用自己的电脑进行编译，怕写的有错误，你拿到一个待编码的数据肯定有标识符（即上面的a,b,c），还有所带的权值（即3,5,5等）你需要用哈弗曼算法构造出哈弗曼编码，即每次取最小的两个数当作叶子，来生成树根（树根的值等于他们的和），整数据就少了一个，直到最后两个数相加的值作为最终的树根。然后从上往下，左边为0右边为1，到达每个树叶（即是标识符的位置），那么路径的编码就是他的哈弗曼编码。以上是算法，建议你可以用一个结构体（带标识符，权值，哈弗曼编码（编码暂时为空）），用一个vector（C++里面的数据类型）装载他们并按照权值大小进行排序，然后通过哈弗曼算法（另用一个函数来计算）创建一个哈弗曼数，并计算出它的哈弗曼编码并写到结构体中，这样就把字符进行了哈弗曼压缩。这就是整个过程
❹ 哈夫曼编码的C程序怎么写
去年做的课程设计，有什么不合要求的自己改改 x0dx0ax0dx0a#include
❺ 关于C语言建立赫夫曼树的问题，我不是很明白，下面是代码：
下面是我写程序的时候的注释，两种方法都写上了。这个程序不能运行，主要是为了理解，注释写的很清楚的。
/*这只是讲解，程序并不能运行*/
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * * HuffmanCode;
int a[100];
int s1,s2;
int Select()
/*在Select函数中，选取了两个根节点权值最小的树构造了一棵新的数，需要将这两个最小的删掉，将新的加入，再找两个最小的，但如果这样，我们就修改了树了，最后得到
的树中，我们删除了一些结点，所以我想，将这些树的权值放在一个整型数组中，去寻找最小的两个*/
{
min=a[1];
s1=1;
for(i=2;i<=a[0];++i)
if(min>a[i])
{
s2=s1;
s1=i;
}
for(i=s1;i<n;++i)
a[i]=a[i+1];
for(i=s2;i<n;++i)
a[i]=a[i+1];
a[0]=a[0]-2;
return OK;
}
HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
int m,i,j,start,t;
if(n<=1)
return OK;
m=2*n-1; /*因为有n个叶结点，所以共有2*n-1个结点*/
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*为m个节点分配空间，0结点不使用*/
if(!HT)
return ERROR;
for(p=HT,i=1;i<=n;++i,++p)
{
p->weight=w[i]; /*数组w中存放叶结点的权值，从下标1开始*/
p->parent=0;
p->lchild=0;
p->rchild=0;
} /*以上是为叶结点初始化*/
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
} /*为非叶结点初始化，非叶结点的权值是待计算的*/
a[0]=n;
for(p=HT,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select(); /*找到a数组中两个最小的元素是s1,s2，并且删除它们,a[0]中存储a中元素个数，要及时修改a[0]的值*/
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; /*将求得的新的结点的权值加入a数组中*/
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
} /*该循环是建赫夫曼树*/
/*以下从叶子到根逆向求每个字符的赫夫曼编码*/
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*为n个字符编码分配头指针向量，0号单元不使用*/
cd=(char *)malloc(n*sizeof(char));
if(!cd)
return ERROR; /*分配求编码的工作空间*/
cd[n-1]='\0'; /*编码结束符*/
for(i=1;i<=n;++i)
{
start=n-1; /*由于n-1位置已经存放了'/0'，所以下面用--start,从n-2的位置存放0,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)); /*各字符的编码长度不等，故为每一个头指针向量动态分配它所指向的空间大小，就是n-start*/
if(!H[i])
return ERROR;
t=1;
printf("\n%d:",i);
for(j=start;j<=n-2;j++)
{
HC[i][t++]=cd[j];
printf("%c",cd[j]);
}
}
free(cd);
return HT;
}
/*由此得到的赫夫曼树的前n个分量表示叶子结点，最后一个分量表示根结点*/
/*以上算法是从叶子到根逆向处理的*/
/*以下算法是从根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码*/
/*译码的过程是分解电文中字符串，从根出发，按字符'0'或'1'确定找左孩子或右孩子，直至叶子结点，便求得该子串相应的字符。*/
HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
/*HT是树，HC存放赫夫曼树的叶结点的编码，w存放叶结点的权值，n是叶结点的个数*/
{
HuffmanTree p;
char *cd;
int m,i,j,start,t,c,f;
if(n<=1)
exit(OK);
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
if(!HT)
return ERROR;
for(p=HT+1,i=1;i<=n;++i,++p)
{
p->weight=w[i];
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
a[0]=n;
for(p=HT+1,i=1;i<=a[0];++i,++p)
a[i]=p->weight;
for(i=n+1;i<=m;++i)
{
Select();
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;
a[0]=a[0]+1;
a[a[0]]=HT[i].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC)
return ERROR; /*分配n个字符编码的头指针向量*/
p=m; /*m是结点总数*/
cdlen=0; /*应该是计数每一个编码的长度*/
for(i=1;i<=m;++i)
HT[i].weight=0; /*遍历赫夫曼树时用作结点的标志(是否是weight域为0，表示没有遍历过，weight域为1，表示遍历过)*/
while(p)
{
if(HT[p].weight==0)
{
HT[p].weight=1;
if(HT[p].lchild!=0)
{
p=HT[p].lchild;
cd[cdlen++]='0';
} /*左孩子不等于0，表示没有走到左边的尽头，0就是NULL，*/
/*我们将一直执行这个if语句，直到走到左边的尽头，将所有左边的边全部赋值为0*/
else
if(HT[p].rchild==0)
{
HC[p]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[p],cd); /*当走到最左边的时候，我们就得到了最左下那个结点的编码，存储在cd数组中，将它赋值到HC[p]中*/
}
}
else
if(HT[p].weight==1)
{
HT[p].weight=2;
if(HT[p].rchild!=0)
{
p=HT[p].rchild;
cd[cdlen++]='1';
}
}
else
{
HT[p].weight=0;
p=HT[p].parent;
--cdlen; /*因为这个编码和上一个编码只有最后一位是不一样的，所以cdlen-1*/
}
}
return HT;
}
❻ 有人可以帮我注释一段关于用c语言实现哈夫曼树的代码吗
在一般的数据结构的书中，树的那章后面，着者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如
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中只有一棵二叉树为止。
简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。
C语言代码实现：
/*-------------------------------------------------------------------------
* Name: 哈夫曼编码源代码。
* Date: 2011.04.16
* Author: Jeffrey Hill+Jezze(解码部分)
* 在 Win-TC 下测试通过
* 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中
* 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在
* 父结点左侧，则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include <stdio.h>
#include<stdlib.h>
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType; /* 编码结构体 */
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
int value;
} HNodeType; /* 结点结构体 */
/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
/* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
int i, j, m1, m2, x1, x2;
/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;//权值
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].rchild =-1;
HuffNode[i].value=i; //实际值，可根据情况替换为字母
} /* end for */
/* 输入 n 个叶子结点的权值 */
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d:
", i);
scanf ("%d", &HuffNode[i].weight);
} /* end for */
/* 循环构造 Huffman 树 */
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
x1=x2=0;
/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
} /* end for */
/* 设置找到的两个子结点 x1、x2 的父结点信息 */
HuffNode[x1].parent = n+i;
HuffNode[x2].parent = n+i;
HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
printf ("x1.weight and x2.weight in round %d: %d, %d
", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */
printf ("
");
} /* end for */
/* for(i=0;i<n+2;i++)
{
printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d
",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///测试
} /* end HuffmanTree */
//解码
void decodeing(char string[],HNodeType Buf[],int Num)
{
int i,tmp=0,code[1024];
int m=2*Num-1;
char *nump;
char num[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild ;
}
else tmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
int main(void)
{
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
int i, j, c, p, n;
char pp[100];
printf ("Please input n:
");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);
for (i=0; i < n; i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while (p != -1) /* 父结点存在 */
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--; /* 求编码的低一位 */
c=p;
p=HuffNode[c].parent; /* 设置下一循环条件 */
} /* end while */
/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
} /* end for */
/* 输出已保存好的所有存在编码的哈夫曼编码 */
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf(" start:%d",HuffCode[i].start);
printf ("
");
}
/* for(i=0;i<n;i++){
for(j=0;j<n;j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf("
");
}*/
printf("Decoding?Please Enter code:
");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return 0;
}
❼ 哈夫曼编码C语言实现
我写了一个注释较为完整且压缩、解压缩比较全面的：
#include <stdio.h>
#include <conio.h>
#define MAX_FILE 5000/* 假设的文件最大长度 */
#define MAXLIST 256/* 最大MAP值 */
#define MAX_HOFFMAN_LENGTH 50/* 哈夫曼编码长度 */
char dictionary[MAXLIST][2]={0};/* Hash映射,[][0]为权值,[][1]为字符 */
char fileContent[MAX_FILE];/* 处理的字符串大小 */
int Hoffman[MAXLIST][MAX_HOFFMAN_LENGTH]={2};/* 哈夫曼编码序列 */
char HoffmanList[MAXLIST]={0};/* 哈夫曼编码对应的字符有序序列 */
char HoffFileCode[MAX_FILE]={0};/* 哈夫曼编码字符串序列 */
char HoffFile[MAX_FILE]={0};
/* 编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串 */
char GetFile[MAX_FILE]={0};/* 解码序列 */
void ShellSort(char pData[MAXLIST][2],int Count)/* Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备 */
{
int step[4]={9,5,3,1};/* 增量序列 */
int iTemp,cTemp;
int k,s,w,i,j;
for(i=0;i<4;i++)
{
k=step[i];
s=-k;
for(j=k;j<Count;j++)
{iTemp=pData[j][0];
cTemp=pData[j][1];
w=j-k;
if(s==0)
{
s=-k;
s++;
pData[s][0]=iTemp;
pData[s][1]=cTemp;
}
while((iTemp<pData[w][0])&&(w>=0)&&(w<=Count))
{
pData[w+k][0]=pData[w][0];/* 权值交换 */
pData[w+k][1]=pData[w][1];/* 字符交换 */
w=w-k;
}
pData[w+k][0]=iTemp;
pData[w+k][1]=cTemp;
}
}
}
struct TNode/* 哈夫曼树结点 */
{
struct TNode* pNode;
struct TNode* lNode;
struct TNode* rNode;
char dictionary;
char weight;
};
void TNode_init(struct TNode*tn,char dic,char wei)
{
tn->pNode=0;
tn->lNode=0;
tn->rNode=0;
tn->dictionary=dic;
tn->weight=wei;
}
struct LNode/* 链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的) */
{
struct LNode* prev;
struct LNode* next;
struct TNode* tnode;
};
void LNode_init(struct LNode* ln)
{
ln->prev=ln->next=0;
ln->tnode=0;
}
int len=0;/* 哈夫曼编码数 */
int deep=-1;/* 深度 */
void Preorder(struct TNode * p);/* 前序遍历 */
void byLeft(struct TNode*p)/* 经由左结点 */
{
deep++;
Hoffman[len][deep]=0;
Preorder(p);
Hoffman[len][deep]=2;
deep--;
}
void byRight(struct TNode*p)/* 经由右结点 */
{
deep++;
Hoffman[len][deep]=1;
Preorder(p);
Hoffman[len][deep]=2;
deep--;
}
void Preorder(struct TNode * p)
{
int i;
if(p->lNode!=0)/* 当左子结点非空则遍历 */
{
byLeft(p->lNode);
}
if(p->rNode!=0)/* 当右子结点非空则遍历 */
{
byRight(p->rNode);
}
if((p->lNode==0)&&(p->rNode==0))/* 当左右结点都为空，则增加哈夫曼编码数到另一个记录 */
{
Hoffman[len][deep+1]=2;
i=0;
for(;Hoffman[len][i]!=2;i++)
{
Hoffman[len+1][i]=Hoffman[len][i];
}
Hoffman[len+1][i]=2;
HoffmanList[len]=p->dictionary;
len++;
}
}
char generateOne(int k)/* 产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件 */
{
char c=0;
for(;k!=0;k--)
{
c|=(1<<(k-1));
}
return c;
}
int compareBits(char b1,char b2,char c,int l,int d)/* 判断由 [b1,b2] 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀 */
{
unsigned char t=(((((0x00ff&b1)<<8)|(0x00ff&b2))>>(8-d))&0x00ff);
return (((t)&((generateOne(l)<<(8-l))&0xff))==((c<<(8-l))&0xff));
}
int main()
{
struct LNode* t,*p;
struct LNode* head;
struct TNode *tempTNode,*k1;
int i=0,j,k;
unsigned short fileLen=0;
int len=0,l,b1,b2,d;
char c;
int code[500],h=0;
int codeLen=0,total=0;
/* 或许假定的文件字符串向量中的字符串 */
printf("please Enter string to be pressed:");
scanf("%s",&fileContent);
/* Hash进dictionary */
for(;fileContent[i]!='\0';i++,fileLen++)
{
++dictionary[fileContent[i]][0];
dictionary[fileContent[i]][1]=fileContent[i];
}
/* 把Hash了的dictionary向前靠拢 */
{
for(i=0;i!=MAXLIST;i++)
{
if(dictionary[i][0]!=0)
{
dictionary[len][0]=dictionary[i][0];
dictionary[len][1]=dictionary[i][1];
len++;
}
}
}
printf("the number of Huffman's codes:%d\n",len);
/* 对dictionary按权值进行排序 */
ShellSort(dictionary,len);
/* 构造链表,链表中放有序dictionary权值的树结点 */
head=(struct LNode*)malloc(sizeof(struct LNode)),p=head;
LNode_init(head);
head->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(head->next);
tempTNode=(struct TNode*)malloc(sizeof(struct LNode));
TNode_init(tempTNode,dictionary[0][1],dictionary[0][0]);
head->tnode=tempTNode;
{
for(i=0;i!=len-1;i++)
{
p->next->prev=p->next;
p=p->next;
p->next=(struct LNode*)malloc(sizeof(struct LNode));
LNode_init(p->next);
tempTNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(tempTNode,dictionary[i+1][1],dictionary[i+1][0]);
p->tnode=tempTNode;
}
}
free(p->next);
p->next=0;
/* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/
for(p=head;p->next!=0;)
{
p->tnode->pNode=(struct TNode*)malloc(sizeof(struct TNode)) ;
TNode_init(p->tnode->pNode,'\0',(p->tnode->weight)+(p->next->tnode->weight));
p->next->tnode->pNode=p->tnode->pNode;
p->tnode->pNode->lNode=p->tnode;
p->tnode->pNode->rNode=p->next->tnode;
head=p->next;
free(p);
p=head;
p->tnode=p->tnode->pNode;
for(t=head;t->next!=0;t=t->next)
{
if(t->tnode->weight>t->next->tnode->weight)
{
k1=t->tnode;
t->tnode=t->next->tnode;
t->next->tnode=k1;
}
}
}
/* 前序遍历构造哈夫曼编码 */
Preorder(p->tnode);
{
for(i=0;i!=len;i++)
dictionary[HoffmanList[i]][0]=i;
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */
{
for(i=0;i!=fileLen;i++)
{
int j=dictionary[fileContent[i]][0];
for(k=0;Hoffman[j][k]!=2;k++)
{
HoffFileCode[codeLen]|=(Hoffman[j][k]<<(7-total%8));
code[h++]=Hoffman[j][k];
if(((total+1)%8)==0)
{
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
codeLen++;
}
total++;
}
}
}
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
HoffFile[0]=(fileLen);
/* 解压缩假定的文件HoffFile成为原字符串序列 */
printf("Huffman's code list:\n");
HoffFile[1]=len;
{
for(i=0,j=0;i!=len;i++,j=0)
{
for(;Hoffman[i][j]!=2;j++);
HoffFile[i+2]=j;
HoffFile[i+2+2*len]=HoffmanList[i];
for( k=0;k!=j;k++)
{
printf("%d",Hoffman[i][k]);
HoffFile[i+2+len]|=(Hoffman[i][k]<<(j-1-k));
}
printf(":%d\n",HoffmanList[i]);
}
}
{
for(i=0,j=0;i!=(HoffFile[0]&0xff);i++)
{
for(k=0;k!=HoffFile[1];k++)
{
l=HoffFile[2+k],d=j%8,b1=HoffFile[j/8+2+HoffFile[1]*3],b2=HoffFile[j/8+1+2+HoffFile[1]*3];
c=HoffFile[HoffFile[1]+2+k];
if(compareBits(b1,b2,c,l,d))
{
j+=HoffFile[2+k];
GetFile[i]=HoffFile[2+HoffFile[1]*2+k];
break;
}
}
}
}
{
printf("Huffman code List Pressed :\n");
for(i=0;i!=h;i++)
{
printf("%c",code[i]);
if((i+1)%8==0)
printf(" ");
}
}
printf("\n");
{
printf("Huffman code packaged:\n");
for(i=0;i!=HoffFile[0]+HoffFile[1]*3;i++)
{
printf("%c",HoffFile[i]);
}
printf("\n");
}
printf("The initial len :%d\n",fileLen);
printf("The string len pressed:%d\n",(h)/8+1);
printf("The rate%.2f\%",((h/8.0+1)/fileLen)*100);
{
printf("The number of bytes:%d\n",(HoffFile[0]&0xff));
printf("The string decoded:");
for(i=0;i!=(HoffFile[0]&0xff);i++)
{
printf("%c",GetFile[i]);
}
printf("\n");
}
getch();
return 1;
}
❽ 哈夫曼编码的C程序怎么写
去年做的课程设计，有什么不合要求的自己改改
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表
void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
int i, j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼树的构造过程如下所示：");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
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;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("输入结点数:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("输入%d个结点的权值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各结点的哈夫曼编码:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}