① 哈夫曼樹及哈夫曼編碼的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();
}
② Huffman編碼c語言實現
說明：本程序是依據嚴蔚敏的數據結構（C語言版）上的代碼實現的。
#pragmaonce
#include<stdio.h>
#include<tchar.h>
#include<stdlib.h>
#define MAX 100
typedefstruct{ //節點
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedefchar **HuffmanCode; //字元串數組，用於存儲葉子節點的編碼
void SelectMinNode(HuffmanTree &HT, int m, int &i1, int &i2) //找出權值最小的兩個節點對應的數組下標
{
HuffmanTree p = HT;
int s1, s2;
s1 = s2 = MAX;
i1 = i2 = 1;
for(int i=1; i<=m; i++)
{
if(!(p+i)->parent)
{
if((p+i)->weight < s1)
{
i2 = i;
s1 = (p+i)->weight ;
}
}
}
for(int i=1; i<=m; i++)
{
if(!(p+i)->parent && i!=i2)
{
if((p+i)->weight < s2)
{
i1 = i;
s2 = (p+i)->weight ;
}
}
}
}
void StrCopy(char *p, char *q, int start) //從字元數組中第start個字元開始復制
{
char *c1, *c2;
c1 = p;
while(q[start] != '\0')
{
*c1 = q[start];
c1++;
start++;
}
*c1 = q[start];//別忘了將『\n』復制過來
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{ //HT赫夫曼樹節點數組，HC存儲赫夫曼編碼，*w 節點權值數組的首地址，n節點個數
int i, i1, i2, m;
HuffmanTree p;
if(n<=1) return;
m = 2 * n -1; //n個葉子節點的赫夫曼樹的節點總數為2n-1，可以結合樹的度為n-1自己證明。
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //數組首元素不使用，故多分配一個空間
p = HT + 1;
for(i=1;i<=n;++i,++p,++w) //n個葉子節點初始化
{
p->weight = *w;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
for(;i<=m;++i,++p) //非葉子節點初始化
{
p->weight = 0;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
for(i=n+1;i<=m;++i) //對非葉子節點重新計算
{
SelectMinNode(HT, i-1, i1, i2);
HT[i1].parent = i;
HT[i2].parent = i;
HT[i].lchild = i1;
HT[i].rchild = i2;
HT[i].weight = HT[i1].weight + HT[i2].weight ;
}
///從葉子節點到根節點求赫夫曼編碼
char* cd;
int start, c, f;
HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字元指針數組，同樣多分配一個
cd = (char*)malloc(n*sizeof(char)); //零時變數，用於存儲當前葉子節點的赫夫曼編碼
cd[n-1] = '\0';
for(int 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));
StrCopy(HC[i], cd, start); //將存儲的編碼給HC的第i個數組
}
free(cd);
}
void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //列印各節點的赫夫曼編碼
{
HuffmanCode p;
for(int i=1; i<=n; i++)
{
p = HC;
printf("The weight %d HuffmanCode is: ", HT[i]);
while(*p[i]!='\0')
{
printf("%c",*p[i]);
p[i]++;
}
printf("\n");
}
}
void main()
{
int n = 8;
HuffmanTree HT;
HuffmanCode HC;
int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信號源的概率分布，即P={p0, p1,…, pK-1}
HuffmanCoding(HT, HC, a, n);
PrintHuffmanCode(HT, HC, n);
system("pause");}
③ 哈夫曼編碼 C源代碼
#include <stdio.h>
#define MAXBIT 10 /*定義哈夫曼編碼的最大長度*/
#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;
}Hnodetype;
void huffmantree(Hnodetype huffnode[MAXNODE],int n) /*構造哈夫曼樹的函數*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) /*存放哈夫曼樹結點的數組huffnode[]初始化*/
{
huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
for(i=0;i<n;i++) /*輸入入N個葉子節點的權值*/
{
printf("please input %d character's weight\n",i);
scanf("%d",&huffnode[i].weight);
}
for(i=0;i<n-1;i++) /*開始循環構造哈夫曼樹*/
{
m1=m2=MAXVALUE;
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;
}
}
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;
}
}
void main()
{
Hnodetype huffnode[MAXNODE];
Hcodetype huffcode[MAXLEAF],cd;
int i,j,c,p,n;
printf("please input n\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;
}
for(j=cd.start+1;j<n;j++) /*保存求出的每個葉節點的哈夫曼編碼和編碼的起始位*/
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
for(i=0;i<n;i++) /*輸出每個葉子節點的哈夫曼編碼*/
{
printf("%d character is:",i);
for(j=huffcode[i].start+1;j<n;j++)
printf("%d",huffcode[i].bit[j]);
printf("\n");
}
}
④ 哈夫曼編碼和解碼c語言的源程序
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 10000
#define MAX 60
typedef int Status;
typedef char **HuffmanCode;
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct{
HuffmanTree HT;
char *c;
int longth;
HuffmanCode HC;
}Huffman;
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)
{
if (HT[i].parent==0&&HT[i].weight<min1)
{
*s1=i;
min1=HT[i].weight;
}
}
min2=MAX_NUM;
for(i=1;i<=end;i++)
{
if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
{
*s2=i;
min2=HT[i].weight;
}
}
}
Huffman HuffmanCoding(Huffman Hfm)
{
/*---------------------------------*/
int i,n,m,s1,s2,start;
int c,f;
char *cd;
n=Hfm.longth;
if(n<=1) return Hfm;
m=2*n-1;
for(i=n+1;i<=m;++i)
{
Select(Hfm.HT,i-1,&s1,&s2);
Hfm.HT[s1].parent=i;
Hfm.HT[s2].parent=i;
Hfm.HT[i].lchild=s1;
Hfm.HT[i].rchild=s2;
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
}
/*------------------------------------------*/
Hfm.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,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
{
if(c==Hfm.HT[f].lchild) cd[--start]='0';
else cd[--start]='1';
}
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hfm.HC[i],&cd[start]);
}
free(cd);
return Hfm;
}
Huffman InputHuffman(Huffman Hfm)
{
int i,n;
clrscr();
printf("\n\n\t\t********************Initial*********************\n");
printf("\tThe chars and weights will be saved in the file \"hfmTree\"\n");
printf("Please input the number of the chars: ");
scanf("%d",&n);
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
Hfm.c=(char *)malloc((n+1)*sizeof(char));
for(i=1;i<=n;i++)
{
printf("Please input the char: ");
scanf("%s",&Hfm.c[i]);
printf("Please input the weight of the char: ");
scanf("%d",&Hfm.HT[i].weight);
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
return Hfm;
}
Huffman InitHuffman(Huffman Hfm)
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","rt");
if(fp==NULL)
{
Hfm=InputHuffman(Hfm);
fp=fopen("hfmTree","wt");
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}
else
{
fscanf(fp,"%d\n",&n);
Hfm.c=(char *)malloc((n+1)*sizeof(char));
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++)
fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight);
for(i=1;i<=n;i++)
{
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
}
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
void Output(Huffman Hfm)
{
int i,n;
n=Hfm.longth;
printf("\n\n******************Output the code of the chars****************\n\n");
for(i=1;i<=n;i++)
{
printf("\n");
printf("Char: %c\t",Hfm.c[i]);
printf("Weight: %d\t",Hfm.HT[i].weight);
printf("Code: ");
puts(Hfm.HC[i]);
}
}
void Encoding(Huffman Hfm)
{
int i=0,j=0,n;
char ch[MAX];
FILE *fp,*ffp;
n=Hfm.longth;
printf("\n\n*******************Encoding**************************\n\n");
if((ffp=fopen("ToBeTran","rt"))==NULL)
{
printf("\nPlease input the sentence: ");
scanf("%s",&ch);
printf("\n");
fp=fopen("CodeFile","wt+");
}
else
{
fscanf(ffp,"%s",ch);
fclose(ffp);
}
while(ch[j])
{
for(i=1;i<=n;i++)
if(ch[j]==Hfm.c[i])
{
printf("%s",Hfm.HC[i]);
fprintf(fp,"%s",Hfm.HC[i]);
break;
}
j++;
}
rewind(fp);
fclose(fp);
}
void Decoding(Huffman Hfm)
{
HuffmanTree p;
int i,n;
int j=0;
char d[50];
FILE *fp;
n=Hfm.longth;
printf("\n\n******************Decoding************************\n\n");
if((fp=fopen("CodeFile","rt"))==NULL)
{
printf("Please input the code:");
scanf("%s",&d);
}
else
{
fscanf(fp,"%s",d);
fclose(fp);
}
printf("\nThe file is : ");
fp=fopen("TextFile","wt+");
while(d[j])
{
p=&Hfm.HT[2*n-1];
while(p->lchild||p->rchild)
{
if(d[j]=='0')
{ i=p->lchild; p=&Hfm.HT[i]; }
else
{ i=p->rchild; p=&Hfm.HT[i]; }
j++;
}
printf("%c",Hfm.c[i]);
fprintf(fp,"%c",Hfm.c[i]);
}
fclose(fp);
}
Huffman RebuildHuffman(Huffman Hfm)
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","wt");
Hfm=InputHuffman(Hfm);
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
int main()
{
Huffman Hfm;
char choice='a';
Hfm=InitHuffman(Hfm);
while(choice!='q')
{
clrscr();
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\ta. Encoding:\n\n");
printf("\t\t\tb. Decoding:\n\n");
printf("\t\t\tc. Print all codes:\n\n");
printf("\t\t\td. Rebuild the huffmantree:\n\n");
printf("\t\t\tq. Quit...\n\n");
printf("\n\t\t************************************\n\n");
printf("Please enter your choice: ");
scanf("%s",&choice);
switch(choice)
{
case 'a':
clrscr();
Encoding(Hfm);
printf("\n\n*******Please enter anykey to continue*******\n");
getch(); break;
case 'b':
clrscr();
Decoding(Hfm);
printf("\n\n*******Please enter anykey to continue********\n");
getch(); break;
case 'c':
clrscr();
Output(Hfm);
printf("\n\n*******Please enter anykey to continue********\n");
getch(); break;
case 'd':
clrscr();
Hfm=RebuildHuffman(Hfm);
printf("\n\n********************Initial*********************\n");
getch(); break;
case 'q':
break;
default:
printf(" Your choice is wrong!\n Please enter anykey to choice again!\n");
getch(); break;
}
}
return 0;
}
⑤ 數據結構（C語言）－哈夫曼編碼求助！！
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* HuffmanCode;/*動態分配數組，存儲哈夫曼編碼*/
typedef struct
{
unsigned int weight ; /* 用來存放各個結點的權值*/
unsigned int parent, LChild,RChild ; /*指向雙親、孩子結點的指針*/
}HTNode, * HuffmanTree; /*動態分配數組，存儲哈夫曼樹*/
void select(HuffmanTree *ht,int n, int *s1, int *s2)
{
int i;
int min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0)
{
min = i;
i = n+1;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0)
{
if((*ht)[i].weight < (*ht)[min].weight)
min = i;
}
}
*s1 = min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0 && i!=(*s1))
{
min = i;
i = n+1;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent == 0 && i!=(*s1))
{
if((*ht)[i].weight < (*ht)[min].weight)
min = i;
}
}
*s2 = min;
}
void CrtHuffmanTree(HuffmanTree *ht , int *w, int n)
{ /* w存放已知的n個權值，構造哈夫曼樹ht */
int m,i;
int s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0號單元未使用*/
for(i=1;i<=n;i++)
{/*1-n號放葉子結點，初始化*/
(*ht)[i].weight = w[i];
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
}
for(i=n+1;i<=m;i++)
{
(*ht)[i].weight = 0;
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0;
} /*非葉子結點初始化*/
/* ------------初始化完畢！對應演算法步驟1---------*/
for(i=n+1;i<=m;i++) /*創建非葉子結點,建哈夫曼樹*/
{ /*在(*ht)[1]~(*ht)[i-1]的范圍內選擇兩個parent為0且weight最小的結點，其序號分別賦值給s1、s2返回*/
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;
}
}/*哈夫曼樹建立完畢*/
void outputHuffman(HuffmanTree HT, int m)
{
if(m!=0)
{
printf("%d ", HT[m].weight);
outputHuffman(HT,HT[m].LChild);
outputHuffman(HT,HT[m].RChild);
}
}
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
/*從葉子結點到根，逆向求每個葉子結點對應的哈夫曼編碼*/
{
char *cd;
int i;
unsigned int c;
int start;
int p;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); /*分配n個編碼的頭指針*/
cd=(char * )malloc(n * sizeof(char )); /*分配求當前編碼的工作空間*/
cd[n-1]='\0'; /*從右向左逐位存放編碼，首先存放編碼結束符*/
for(i=1;i<=n;i++) /*求n個葉子結點對應的哈夫曼編碼*/
{
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'; /*左分支標0*/
else
cd[--start]='1'; /*右分支標1*/
hc[i]=(char *)malloc((n-start)*sizeof(char)); /*為第i個編碼分配空間*/
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1;i<=n;i++)
printf("%d編碼為%s\n",(*ht)[i].weight,hc[i]);
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w;
int i,n; // the number of elements;
int wei; // the weight of a element;
int m;
printf("input the total number of the Huffman Tree:" );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
for(i=1;i<=n;i++)
{
printf("input the %d element's weight:",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
m = 2*n-1;
outputHuffman(HT,m);
printf("\n");
CrtHuffmanCode(&HT,&HC,n);
}
⑥ 哈夫曼編碼的C語言實現
排序；
生成編碼表；
讀取數據比較，編碼。
這個題目建議你好好做做，做了水平會提高不少的。
⑦ c語言編程程序（關於哈夫曼編碼）
你好!
這是要完成的程序嗎？直接可以運行，還是要介紹
⑧ 哈夫曼編碼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;
}
⑨ huffman編碼解碼的c語言實現
留個腳印，晚上回去看看
#include <iostream.h>
#include <iomanip.h>
#include <string.h>
#include <malloc.h>
#include <stdio.h>
//typedef int TElemType;
const int UINT_MAX=1000;
char str[50];
typedef struct
{
int weight,K;
int parent,lchild,rchild;
}HTNode,* HuffmanTree;
typedef char **HuffmanCode;
//-----------全局變數-----------------------
HuffmanTree HT;
HuffmanCode HC;
int w[50],i,j,n;
char z[50];
int flag=0;
int numb=0;
// -----------------求赫夫曼編碼-----------------------
struct cou{
char data;
int count;
}cou[50];
int min(HuffmanTree t,int i)
{ // 函數void select()調用
int j,flag;
int k=UINT_MAX; // 取k為不小於可能的值,即k為最大的權值1000
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;
}
//--------------------slect函數----------------------
void select(HuffmanTree t,int i,int &s1,int &s2)
{ // s1為最小的兩個值中序號小的那個
int j;
s1=min(t,i);
s2=min(t,i);
if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}
}
// --------------演算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{ // w存放n個字元的權值(均>0),構造赫夫曼樹HT,並求出n個字元的赫夫曼編碼HC
int m,i,s1,s2,start;
//unsigned c,f;
int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;//檢測結點數是否可以構成樹
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0號單元未用
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
p->parent=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); // 釋放工作空間
}
//---------------------獲取報文並寫入文件---------------------------------
int InputCode()
{
//cout<<"請輸入你想要編碼的字元"<<endl;
FILE *tobetran;
if((tobetran=fopen("tobetran.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
return 0;
}
cout<<"請輸入你想要編碼的字元"<<endl;
gets(str);
fputs(str,tobetran);
cout<<"獲取報文成功"<<endl;
fclose(tobetran);
return strlen(str);
}
//--------------初始化赫夫曼鏈表---------------------------------
void Initialization()
{ int a,k,flag,len;
a=0;
len=InputCode();
for(i=0;i<len;i++)
{k=0;flag=1;
cou[i-a].data=str[i];
cou[i-a].count=1;
while(i>k)
{
if(str[i]==str[k])
{
a++;
flag=0;
}
k++;
if(flag==0)
break;
}
if(flag)
{
for(j=i+1;j<len;j++)
{if(str[i]==str[j])
++cou[i-a].count;}
}
}
n=len-a;
for(i=0;i<n;i++)
{ cout<<cou[i].data<<" ";
cout<<cou[i].count<<endl;
}
for(i=0;i<=n;i++)
{*(z+i)=cou[i].data;
*(w+i)=cou[i].count;
}
/* 原來未修改的初始化程序段:
flag=1;
int num;
int num2;
cout<<"下面初始化赫夫曼鏈表"<<endl<<"請輸入結點的個數n：";
cin>>num;
n=num;
w=(int*)malloc(n*sizeof(int));
z=(char*)malloc(n*sizeof(char));
cout<<"\n請依次輸入"<<n<<"個字元(字元型)："<<endl;
char base[2];
for(i=0;i<n;i++)
{
cout<<"第"<<i+1<<"個字元:"<<endl;
gets(base);
*(z+i)=*base;
}
for(i=0;i<=n-1;i++)
{
cout<<setw(6)<<*(z+i);
}
cout<<"\n請依次輸入"<<n<<"個權值："<<endl;
for(i=0;i<=n-1;i++)
{
cout<<endl<<"第"<<i+1<<"個字元的權值:";
cin>>num2;
*(w+i)=num2;
}*/
HuffmanCoding(HT,HC,w,n);
//------------------------列印編碼-------------------------------------------
cout<<"字元對應的編碼為:"<<endl;
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
//--------------------------將赫夫曼編碼寫入文件------------------------
cout<<"下面將赫夫曼編碼寫入文件"<<endl<<"...................."<<endl;
FILE *htmTree;
char r[]={' ','\0'};
if((htmTree=fopen("htmTree.txt","w"))==NULL)
{
cout<<"can not open file"<<endl;
return;
}
fputs(z,htmTree);
for(i=0;i<n+1;i++)
{
fprintf(htmTree,"%6d",*(w+i));
fputs(r,htmTree);
}
for(i=1;i<=n;i++)
{
fputs(HC[i],htmTree);
fputs(r,htmTree);
}
fclose(htmTree);
cout<<"已將字元與對應編碼寫入根目錄下文件htmTree.txt中"<<endl<<endl;
}
//---------------------編碼函數---------------------------------
void Encoding()
{
cout<<"下面對目錄下文件tobetran.txt中的字元進行編碼"<<endl;
FILE *tobetran,*codefile;
if((tobetran=fopen("tobetran.txt","rb"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
if((codefile=fopen("codefile.txt","wb"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
char *tran;
i=99;
tran=(char*)malloc(100*sizeof(char));
while(i==99)
{
if(fgets(tran,100,tobetran)==NULL)
{
cout<<"不能打開文件"<<endl;
break;
}
for(i=0;*(tran+i)!='\0';i++)
{
for(j=0;j<=n;j++)
{
if(*(z+j-1)==*(tran+i))
{
fputs(HC[j],codefile);
if(j>n)
{
cout<<"字元錯誤，無法編碼!"<<endl;
break;
}
}
}
}
}
cout<<"編碼工作完成"<<endl<<"編碼寫入目錄下的codefile.txt中"<<endl<<endl;
fclose(tobetran);
fclose(codefile);
free(tran);
}
//-----------------解碼函數---------------------------------
void Decoding()
{
cout<<"下面對根目錄下文件codefile.txt中的字元進行解碼"<<endl;
FILE *codef,*txtfile;
if((txtfile=fopen("txtfile.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
if ((codef=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打開文件"<<endl;
}
char *work,*work2,i2;
int i4=0,i,i3;
unsigned long length=10000;
work=(char*)malloc(length*sizeof(char));
fgets(work,length,codef);
work2=(char*)malloc(length*sizeof(char));
i3=2*n-1;
for(i=0;*(work+i-1)!='\0';i++)
{
i2=*(work+i);
if(HT[i3].lchild==0)
{
*(work2+i4)=*(z+i3-1);
i4++;
i3=2*n-1;
i--;
}
else if(i2=='0') i3=HT[i3].lchild;
else if(i2=='1') i3=HT[i3].rchild;
}
*(work2+i4)='\0';
fputs(work2,txtfile);
cout<<"解碼完成"<<endl<<"內容寫入根目錄下的文件txtfile.txt中"<<endl<<endl;
free(work);
free(work2);
fclose(txtfile);
fclose(codef);
}
//-----------------------列印編碼的函數----------------------
void Code_printing()
{
cout<<"下面列印根目錄下文件CodePrin.txt中編碼字元"<<endl;
FILE * CodePrin,* codefile;
if((CodePrin=fopen("CodePrin.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
if((codefile=fopen("codefile.txt","r"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
char *work3;
work3=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work3,51,codefile)==NULL)
{
cout<<"不能讀取文件"<<endl;
break;
}
fputs(work3,CodePrin);
puts(work3);
}while(strlen(work3)==50);
free(work3);
cout<<"列印工作結束"<<endl<<endl;
fclose(CodePrin);
fclose(codefile);
}
//-------------------------------列印解碼函數---------------------------------------------
void Code_printing1()
{
cout<<"下面列印根目錄下文件txtfile.txt中解碼字元"<<endl;
FILE * CodePrin1,* txtfile;
if((CodePrin1=fopen("CodePrin1.txt","w"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
if((txtfile=fopen("txtfile.txt","r"))==NULL)
{
cout<<"不能打開文件"<<endl;
return;
}
char *work5;
work5=(char*)malloc(51*sizeof(char));
do
{
if(fgets(work5,51,txtfile)==NULL)
{
cout<<"不能讀取文件"<<endl;
break;
}
fputs(work5,CodePrin1);
puts(work5);
}while(strlen(work5)==50);
free(work5);
cout<<"列印工作結束"<<endl<<endl;
fclose(CodePrin1);
fclose(txtfile);
}
//------------------------列印赫夫曼樹的函數-----------------------
void coprint(HuffmanTree start,HuffmanTree HT)
{
if(start!=HT)
{
FILE * TreePrint;
if((TreePrint=fopen("TreePrint.txt","a"))==NULL)
{cout<<"創建文件失敗"<<endl;
return;
}
numb++;//該變數為已被聲明為全局變數
coprint(HT+start->rchild,HT);
cout<<setw(5*numb)<<start->weight<<endl;
fprintf(TreePrint,"%d\n",start->weight);
coprint(HT+start->lchild,HT);
numb--;
fclose(TreePrint);
}
}
void Tree_printing(HuffmanTree HT,int w)
{
HuffmanTree p;
p=HT+w;
cout<<"下面列印赫夫曼樹"<<endl;
coprint(p,HT);
cout<<"列印工作結束"<<endl;
}
//------------------------主函數------------------------------------
void main()
{
char choice;
while(choice!='q')
{ cout<<"\n******************************"<<endl;
cout<<" 歡迎使用赫夫曼編碼解碼系統"<<endl;
cout<<"******************************"<<endl;
cout<<"(1)要初始化赫夫曼鏈表請輸入'i'"<<endl;
cout<<"(2)要編碼請輸入'e'"<<endl;
cout<<"(3)要解碼請輸入'd'"<<endl;
cout<<"(4)要列印編碼請輸入'p'"<<endl;
cout<<"(5)要列印赫夫曼樹請輸入't'"<<endl;
cout<<"(6)要列印解碼請輸入'y'"<<endl;
if(flag==0)cout<<"\n請先初始化赫夫曼鏈表,輸入'i'"<<endl;
cin>>choice;
switch(choice)
{
case 'i':
Initialization();
break;
case 'e':
Encoding();
break;
case 'd':
Decoding();
break;
case 'p':
Code_printing();
break;
case 't':
Tree_printing(HT,2*n-1);
break;
case 'y':
Code_printing1();
break;
default:
cout<<"input error"<<endl;
}
}
free(z);
free(w);
free(HT);
}
⑩ 哈夫曼編碼 c語言 求改正
我這有C++的哈夫曼樹，前一段時間的數據結構的作業。