❶ 求幫忙用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();
}