huffman編碼c語言
㈠ 怎麼樣用c語言程序編碼哈夫曼樹
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <ctype.h>
#include<limits.h>
int function1(char ch,char *s)
{
int i;
for(i=0; s[i]!='\0'; i++)
{
if(ch==s[i])return 0;
}
return 1;
}
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 動態分配數組存儲赫夫曼樹
typedef char **HuffmanCode; // 動態分配數組存儲赫夫曼編碼表
// algo6-1.cpp 求赫夫曼編碼。實現演算法6.12的程序
int min(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為最小的兩個值中序號小的那個
s1=min(t,i);
s2=min(t,i);
/* if(s1>s2)
{
j=s1;
s1=s2;
s2=j;
}*/
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) // 演算法6.12
{
// w存放n個字元的權值(均>0),構造赫夫曼樹HT,並求出n個字元的赫夫曼編碼HC
int m,i,s1,s2,start;
unsigned 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].rchild=s1;
HT[i].lchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
// printf("HT[%d].lchild:%d HT[%d].rchild:%d\n",i,s2,i,s1);
}
// 從葉子到根逆向求每個字元的赫夫曼編碼
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]='1';
else
cd[--start]='0';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 為第i個字元編碼分配空間
strcpy(HC[i],&cd[start]); // 從cd復制編碼(串)到HC
}
free(cd); // 釋放工作空間
}
void swap1(int *a ,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void swap2(char *a,char *b)
{
char ch;
ch=*a;
*a=*b;
*b=ch;
}
int main(void)
{
HuffmanTree HT;
HuffmanCode HC;
char *s1,*s2;
int i,j=0,n,count,*m,t,flag=1;
scanf("%d",&n);
getchar();
s1=(char*)malloc((n+n)*sizeof(char));
s2=(char*)malloc(n*sizeof(char));
memset(s2,'\0',n*sizeof(char));
gets(s1);
count=strlen(s1);
for(i=0; i<count; i++)
{
if(!isspace(*(s1+i)))
{
if(function1(*(s1+i),s2))
{
*(s2+j)=*(s1+i);
j++;
}
}
else;
}
m=(int*)malloc(j*sizeof(int));
for(i=0; i<j; i++)
*(m+i)=0;
for(t=0; t<j; t++)
{
for(i=0; i<count; i++)
{
if(*(s2+t)==*(s1+i))
*(m+t)+=1;
}
}
for(i=0;i<j;i++)
while(flag)
{
flag = 0;
for (t=0; t<j-1; t++)
{
if(*(m+t)<*(m+t+1))
{
swap1(m+t,m+t+1);
swap2(s2+t,s2+t+1);
flag=1;
}
}
}
HuffmanCoding(HT,HC,m,j);
for(i=1,t=0; i<=j; i++,t++)
{
printf("%c %d %s\n",*(s2+t),*(m+t),HC[i]);
}
return 0;
}
㈡ 用c語言完成：1.哈夫曼編碼/解碼器2.內部排序演算法的性能分析
我把網上的程序修改了一下，並整合了，你看看
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000;
typedef struct
{
int weight;//結點權值
int parent,lchild,rchild;
}HTNODE,*HUFFMANTREE;
typedef char** HUFFMANCODE;//動態分配數組存儲哈夫曼編碼表
typedef struct
{
int key; /*關鍵字*/
}RecordNode; /*排序節點的類型*/
typedef struct
{
RecordNode *record;
int n; /*排序對象的大小*/
}SortObject; //待排序序列
HUFFMANTREE huffmantree(int n,int weight[])//構建哈夫曼樹
{
int m1,m2,k;
int i,j,x1,x2;
HUFFMANTREE ht;
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE));
for(i=1;i<(2*n);i++)//初始化哈夫曼樹中各結點的數據，沒初始值的賦值為0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
if(i<=n)
ht[i].weight=weight[i];
else
ht[i].weight=0;
}
for(i=1;i<n;i++)//每一重循環從森林中選擇最小的兩棵樹組建成一顆新樹
{
m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight;
x2=j;
}
}
k=n+i;
ht[x1].parent=ht[x2].parent=k;
ht[k].weight=m1+m2;
ht[k].lchild=x1;
ht[k].rchild=x2;
}
return ht;
}
void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father;
char *cd;
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*));//分配n個字元編碼的頭指針
cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]='\0';//編碼結束符
for(i=1;i<=n;++i)//逐個字元求哈夫曼編碼
{
start=n-1;
for(child=i,father=ht[i].parent;father!=0;child=father,father=ht[father].parent)/*從葉子結點到根結點求逆向編碼*/
if(ht[father].lchild==child)
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("\n%c的編碼:",str[i]);
printf("%s\n",hc[i]);
}
}
void huffman()
{
int i,j,k,m,n;
char str[50];
int weight[50];
HUFFMANCODE hc=NULL;
HUFFMANTREE ht;
fflush(stdin);
printf("\n請輸入字元(一次性連續輸入所求的字元):");/*如:abcjhjg不要輸成ab cj hig,即字元間不加空格*/
gets(str);
for(j=0;j<50;j++)
{
if(str[j]=='\0')
break;
}
n=j;
for(j=n;j>0;j--)
str[j]=str[j-1];
str[n+1]='\0';
for(k=0;k<n;k++)
{
printf("\n請輸入%c的權值:",str[k+1]);
scanf("%d",&weight[k]);
}
for(k=n;k>0;k--)
weight[k]=weight[k-1];
weight[0]=0;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
fflush(stdin);
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=1;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-1;
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++;
(*exchange)++;
pvector->record[j+1]=pvector->record[j];
j--;
}
if(j!=(i-1))
{
pvector->record[j+1]=temp;
(*exchange)++;
}
}
free(pvector);
}
void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/*復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
k=i;
for(j=i+1;j<pvector->n;j++)
{
(*compare)++;
if(pvector->record[j].key<pvector->record[k].key)
k=j;
}
if(k!=i)
{
temp=pvector->record[i];
pvector->record[i]=pvector->record[k];
pvector->record[k]=temp;
( *exchange)+=3;
}
}
free(pvector);
}
void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(i=0;i<pvector->n-1;i++)
{
noswap=1;
for(j=0;j<pvector->n-i-1;j++)
{
(*compare)++;
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j];
pvector->record[j]=pvector->record[j+1];
pvector->record[j+1]=temp;
(*exchange)+=3;
noswap=0;
}
}
if(noswap) break;
}
free(pvector);
}
void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k;
RecordNode temp;
SortObject *pvector;
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!");
getchar();
exit(1);
}
k=pvector->n;
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<p->n;i++)/* 復制數組*/
pvector->record[i]=p->record[i];
pvector->n=p->n;
*compare=0;
*exchange=0;
for(increment=d;increment>0;increment/=2)
{
for(i=increment;i<pvector->n;i++)
{
temp=pvector->record[i];
(*exchange)++;
j=i-increment;
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++;
pvector->record[j+increment]=pvector->record[j];
(*exchange)++;
j-=increment;
}
pvector->record[j+increment]=temp;
(*exchange)++;
}
}
free(pvector);
}
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j;
RecordNode temp;
if(left>=right)
return;
i=left;
j=right;
temp=pvector->record[i];
(*exchange)++;
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++;
j--;
}
if(i<j)
{
pvector->record[i++]=pvector->record[j];
(*exchange)++;
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++;
i++;
}
if(i<j)
{
pvector->record[j--]=pvector->record[i];
(*exchange)++;
}
}
pvector->record[i]=temp;
(*exchange)++;
QuickSort(pvector,left,i-1,compare,exchange);
QuickSort(pvector,i+1,right,compare,exchange);
}
void SortMethod(void)
{
int i,j,k,l;
unsigned long num[5][10]={0};
unsigned long sum[10]={0};
SortObject *pvector;
fflush(stdin);
printf("請輸入待排序的隨機數個數：\n");
scanf("%d",&k);
pvector=(SortObject *)malloc(sizeof(SortObject));
for(j=0;j<5;j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k);
for(i=0;i<k;i++)
pvector->record[i].key=rand();
pvector->n=k;
InsertSort(pvector,&num[j][0],&num[j][1]);
SelectSort(pvector,&num[j][2],&num[j][3]);
BubbleSort(pvector,&num[j][4],&num[j][5]);
ShellSort(pvector,4,&num[j][6],&num[j][7]);
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9]);
}
printf("\n排序比較如下");
for(j=0;j<5;j++)
{
printf("\n\n對%d個數進行排序，結果為：\n",k);
printf("1.插入排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][0],num[j][1]);
printf("2.選擇排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][2],num[j][3]);
printf("3.冒泡排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][4],num[j][5]);
printf("4.希爾排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][6],num[j][7]);
printf("5.快速排序：比較-->%-7ld次 移動-->%-7ld次\n",num[j][8],num[j][9]);
if(j!=5)
printf("按回車繼續\n");
getchar();
}
for(j=0;j<5;j++)
{
sum[0]=sum[0]+num[j][0];
sum[1]=sum[1]+num[j][1];
sum[2]=sum[2]+num[j][2];
sum[3]=sum[3]+num[j][3];
sum[4]=sum[4]+num[j][4];
sum[5]=sum[5]+num[j][5];
sum[6]=sum[6]+num[j][6];
sum[7]=sum[7]+num[j][7];
sum[8]=sum[8]+num[j][8];
sum[9]=sum[9]+num[j][9];
}
printf("\n\n對%d個隨機數進行5次排序，平均比較次數和平均移動次數為：\n",k);
printf("1.插入排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[0]/5,sum[1]/5);
printf("2.選擇排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[2]/5,sum[3]/5);
printf("3.冒泡排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[4]/5,sum[5]/5);
printf("4.希爾排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[6]/5,sum[7]/5);
printf("5.快速排序：平均比較-->%-7ld次 平均移動-->%-7ld次\n",sum[8]/5,sum[9]/5);
free(pvector);
}
void sort()
{
int i;
while(1)
{
SortMethod();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
main()
{
int i,j,k;
while(1)
{
printf("請選擇要運行的功能：\n");
printf("1.哈夫曼編碼解碼器\n");
printf("2.內部排序性能分析\n");
printf("3.退出該程序\n\n");
printf("你的選擇為：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:sort();break;
case 3:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}
㈢ 赫夫曼OR哈弗曼編碼 c語言 數據結構 簡單的程序設計
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman編碼
typedef struct
{
int weight;//權值
int parent;//父節節點
int LChild;//左子節點
int RChild;//右子節點
}HTNode,Huffman[M+1];//huffman樹
typedef struct Node
{
int weight; //葉子結點的權值
char c; //葉子結點
int num; //葉子結點的二進制碼的長度
}WNode,WeightNode[N];
/***產生葉子結點的字元和權值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//葉子節點個數
//統計字元出現個數,放入CW
for(i=0;ch[i]!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch[i])
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//權值累加
}
}
*s=i;//字元串長度
}
/********創建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼樹
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j; //找到第一個雙親不為零的結點
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二個雙親不為零的結點
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//權值累加
}
}
/***********葉子結點的編碼***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次從末尾開始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父親方向遍歷,直到為0
{
start--;//依次向前置值
if(ht[p].LChild==c)//與左子相同,置0
cd[start]='0';
else //否則置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二進制碼的長度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//將二進制字元串拷貝到指針數組h中
}
free(cd);//釋放cd內存
system("pause");
}
/*********所有字元的編碼*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*從weight[k].c中查找與ch[i]相等的下標K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷貝二進制編碼
}
}
/*****解碼*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;//從父親節點向下遍歷直到葉子節點
for(j=0;hc[i][j]!='\0';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*列印原信息*/
i++;
}
}
/*****釋放huffman編碼內存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//釋放葉子結點的編碼
free(h[i]);
for(i=0;i<m;i++) //釋放所有結點的編碼
free(hc[i]);
}
void print(Huffman &ht,int i,int space)//列印哈弗曼樹
{
int j;
if(i)
{
print(ht,ht[i].RChild,space+5);
for(j=0;j<=space;j++)
printf(" ");
printf("%d\n",ht[i].weight);
print(ht,ht[i].LChild,space+5);
}
return ;
}
void main()
{
int i,n=0; /*n為葉子結點的個數*/
int m=0; /*m為字元串ch[]的長度*/
char ch[N]; /*ch[N]存放輸入的字元串*/
Huffman ht; /*Huffman二叉數 */
HuffmanCode h,hc; /*h存放葉子結點的編碼，hc 存放所有結點的編碼*/
WeightNode weight; /*存放葉子結點的信息*/
printf("**********************************************\n");
printf(" 歡迎使用哈弗曼編碼解碼系統\n");
printf("**********************************************\n");
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*輸入字元串*/
CreateWeight(ch,&m,weight,&n); /*產生葉子結點信息，m為字元串ch[]的長度*/
printf("***WeightInformation***\n Node ");
for(i=1;i<=n;i++) /*輸出葉子結點的字元與權值*/
printf("%c ",weight[i].c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*產生Huffman樹*/
printf("\n***HuffamnTreeInformation***\n");
printf("\ti\tweight\tparent\tLChild\tRChild\n");
for(i=1;i<=2*n-1;i++) /*列印Huffman樹的信息*/
printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*葉子結點的編碼*/
printf(" ***NodeCode***\n"); /*列印葉子結點的編碼*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight[i].c);
printf("%s\n",h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字元的編碼*/
printf("***StringCode***\n\n"); /*列印字元串的編碼*/
for(i=0;i<m;i++)
printf("%s",hc[i]);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解碼*/
FreeHuffmanCode(h,hc,n,m);
printf("\n");
printf("\n哈弗曼樹\n");
print(ht,2*n-1,0);
system("pause");
}
㈣ 創建一個哈夫曼樹並且進行編碼權重如下w={5，29，7 8，14，13 ，3 ，11}寫出c語言代碼
#include"stdafx.h"
#include"hfm.h"
#include<string.h>
#include<malloc.h>//malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#defineTRUE1
#defineFALSE1
#defineOK1
#defineERROR1
#defineINFEASIBLE-1
typedefintStatus;
typedefintBoolean；
/************************************************************************/
/*最優二叉樹簡稱：哈夫曼樹*/
/************************************************************************/
//哈夫曼樹結構
;typedefstruct{
unsignedintweight;//權重
unsignedintparent,lchild,rchild;//樹的雙親節點，和左右孩子
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
//返回i個節點中權值最小的樹的根節點的序號，供select()調用
intMin(HuffmanTreeT,inti){
intj,flag;
unsignedintk=UINT_MAX;//%d-->UINT_MAX=-1,%u--->非常大的數
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;//將parent標志為1避免二次查找
returnflag;//返回
}
voidSelect(HuffmanTreeT,inti,int&s1,int&s2){
//在i個節點中選取2個權值最小的樹的根節點序號，s1為序號較小的那個
intj;
s1=Min(T,i);
s2=Min(T,i);
if(s1>s2){
j=s1;
s1=s2;
s2=j;
}
}
//HuffmanCode代表的樹解碼二進制值
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){
//w存放n個字元的權值(均>0),構造哈夫曼樹HT,並求出n個字元的哈夫曼編碼HC
intm,i,s1,s2,start;
unsignedc,f;
char*cd;
//分配存儲空間
HuffmanTreep;
if(n<=1)
return;
//n個字元(葉子節點)有2n-1個樹節點，所以樹節點m
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).lchild=0;
(*p).rchild=0;
(*p).parent=0;
}
//這一步是給哈夫曼樹的非葉子節點初始化
for(;i<=m;++i,++p){
(*p).parent=0;
}
/************************************************************************/
/*做完准備工作後，開始建立哈夫曼樹
/************************************************************************/
for(i=n+1;i<=m;i++)
{
//在HT[1~i-1]中選擇parent=0且weigh最小的節點，其序號分別為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;
}
/************************************************************************/
/*從葉子到根逆求每個葉子節點的哈夫曼編碼*/
/************************************************************************/
//分配n個字元編碼的頭指針向量，（[0]不用）
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));//分配求編碼的工作空間
cd[n-1]=' ';//結束符
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賦值字元串到cd
}
free(cd);//釋放資源
}
//函數聲明
intMin(HuffmanTreeT,inti);//求i個節點中的最小權重的序列號，並返回
voidSelect(HuffmanTreeT,inti,int&s1,int&s2);//從兩個最小權重中選取最小的(左邊)給s1，右邊的給s2
voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn);//哈夫曼編碼與解碼
intmain(){
HuffmanTreeHT;
HuffmanCodeHC;
int*w,n,i;
printf("請輸入權值的個數(>1):");
scanf_s("%d",&n);
w=(int*)malloc(n*sizeof(int));
printf("請依次輸入%d個權值(整形): ",n);
for(i=0;i<=n-1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT,HC,w,n);
for(i=1;i<=n;i++)
{
puts(HC[i]);
}
return0;
}
㈤ 數據結構中哈夫曼樹的應用（C語言）
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
#define N 100;
int n1=0;
char c[100];
typedef struct Node
{
DataType data;
struct Node *leftChild;
struct Node *rightChild;
}BiTreeNode;
typedef struct
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}HaffNode;
typedef struct
{
int bit[MaxN];
int start;
int weight;
}Code;
struct worder
{
char words; /*字元*/
}word[100];
struct weighted
{
int weighter; /*轉換權值有利於文件的存儲*/
}weight[100] ;
void Initiate(BiTreeNode **root) /*初始化二叉樹*/
{
*root=(BiTreeNode * )malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
}
BiTreeNode *InsertLeftNode(BiTreeNode *curr,DataType x) /*插入左子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL) return NULL;
t=curr->leftChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->leftChild=t;
s->rightChild=NULL;
curr->leftChild=s;
return curr->leftChild;
}
BiTreeNode *InsertRightNode(BiTreeNode *curr ,DataType x) /*插入右子樹*/
{
BiTreeNode *s,*t;
if(curr==NULL)
return NULL;
t=curr->rightChild;
s=(BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data=x;
s->rightChild=t;
s->leftChild=NULL;
curr->rightChild=s;
return curr->rightChild;
}
void Haffman(int weigh[],int n,HaffNode haffTree[],int a[][3]) /*建立哈夫曼樹*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)
haffTree[i].weight=weigh[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
a[i+1][0]=haffTree[x1].weight;
a[i+1][1]=haffTree[x2].weight; /*將每個權值賦值給二維數組a[][],利用這個二維數組可以進行建立二叉樹*/
a[i+1][2]=haffTree[n+i].weight;
}
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) /*對已經建立好的哈夫曼樹進行編碼*/
{
Code *cd=(Code *)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent!=-1)
{
if(haffTree[parent].leftChild==child)
cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--;
child=parent;
parent=haffTree[child].parent;
}
for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1;
haffCode[i].weight=cd->weight;
}
}
void PrintBiTree(BiTreeNode *bt ,int n) /*將哈夫曼樹轉換成的二叉樹進行列印*/
{
int i;
if(bt==NULL)
return;
PrintBiTree(bt->rightChild,n+1);
for(i=0;i<n;i++)
printf(" ");
if(bt->data!=0&&bt->data<100)
{
if(n>0)
{
printf("---");
printf("%d\n\n",bt->data);
}
}
PrintBiTree(bt->leftChild,n+1);
}
int search(int a[][3],int m) /*查找和a[][2]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][0]&&i<m)
i++;
if(i==m) return 0; /*查找失敗返回數字0 查找成功返回和a[][2]相等的數的行數 i*/
else return i;
}
int searcher(int a[][3],int m) /*查找和a[][1]相等的權值*/
{
int i=1;
if(m==1) return 0;
while(a[i][2]!=a[m][1]&&i<m) /*查找失敗返回數字0 查找成功返回和a[][1]相等的數的行數 i*/
i++;
if(i==m) return 0;
else return i;
}
void creat(BiTreeNode *p,int i,int a[][3]) /*建立哈夫曼樹*/（利用遞歸）
{
int m,n;
BiTreeNode *p1,*p2,*p3;
if(i<=0) return;
p1=p;
if(a[i][0]!=a[i][1]) /*如果a[][0]和a[][1]不相等*/
{
p2=InsertLeftNode(p,a[i][0]); /*a[][0]為左子樹*/
n=search(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]); /*a[][1]為右子樹*/
m=searcher(a,i);
if(m)
creat(p3,m,a);
} /*如果a[][0]和a[][1]相等則只要進行一個的查找*/
else
{
p2=InsertLeftNode(p,a[i][1]);
n=searcher(a,i);
if(n)
creat(p2,n,a);
p3=InsertRightNode(p1,a[i][1]);
}
}
void code(Code myHaffCode[],int n ) /*編碼*/
{
FILE *fp,*fp1,*fp2;
int i=0,k,j;
int text_len = strlen(c);
int *p2;
struct worder *p1;
if((fp2=fopen("CodeFile","wb"))==NULL) /*建立存儲編碼的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
if((fp1=fopen("hfmTree","rb"))==NULL) /*讀取存儲字元的文件*/
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p1=word;p1<word+n;p1++)
{
fread(p1,sizeof(struct worder),1,fp1) ;
printf("word=%c Weight=%d Code=",p1->words,myHaffCode[i].weight); /*輸出每個權值的編碼*/
for(j=myHaffCode[i].start;j<n;j++)
printf("%d",myHaffCode[i].bit[j]);
printf("\n");
printf("\n");
i++;
}
j=0;
printf("\n\nThe codes :") ;
for(i=0;i< text_len;i++)
{
while(c[i]!=word[j].words) /*查找字元找到對應的編碼*/
{
j++;
}
for(k=myHaffCode[j].start;k<n;k++)
{
printf("%d",myHaffCode[j].bit[k]); /*輸出相應的編碼*/
fprintf(fp2,"%d",myHaffCode[j].bit[k]);
}
j=0;
}
fclose(fp2);
}
void sava(int n) /*建立文件*/
{
FILE *fp,*fp1,*fp2;
int *p2,i,j;
struct worder *p1;
struct weighted *p3;
if((fp2=fopen("NO.","wb"))==NULL) /*建立存儲權值個數的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%d",n) ;
if((fp=fopen("hfmTree","wb"))==NULL) /*建立存儲字元的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p1=word;p1<word+n;p1++)
{
if(fwrite(p1,sizeof(struct worder),1,fp)!=1)
printf("file write error\n");
}
fclose(fp);
if((fp1=fopen("hfmTree-1","wb"))==NULL) /*建立存儲權值的文件*/
{
printf("Error,cannot open file\n" );
exit(0);
}
for(p3=weight;p3<weight+n;p3++)
{
if(fwrite(p3,sizeof(struct weighted),1,fp1)!=1)
printf("file write error\n");
}
fclose(fp1);
printf("Please input any key !\n") ;
printf("Please input any key !\n") ;
if(n>MaxN)
{
printf("error!\n\n");
exit(0);
}
}
void menu() /*界面*/
{
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\t1. To Code:\n\n"); /*編碼*/
printf("\t\t\t2. Decoding:\n\n"); /*解碼*/
printf("\t\t\t3. Output the huffman Tree:\n\n"); /*列印哈夫曼樹*/
printf("\t\t\t4. New data\n\n");
printf("\t\t\t5. Quit up...\n\n");
printf("\n\t\t************************************\n\n");
printf("Input you choice :\n");
}
void main()
{ FILE *fp,*fp1,*fp2,*fp3,*fp4;
int i,j;
int b[100][3],m=100,n,w,k=0,weigh[100];
struct worder *d;
struct weighted *p2;
char h;
BiTreeNode *root,*p;
HaffNode *myHaffTree=(HaffNode *)malloc(sizeof(HaffNode)*(2*m+1));
Code *myHaffCode=(Code *)malloc(sizeof(Code)*m);
Initiate(root);
if(((fp1=fopen("hfmTree","rb"))==NULL)&&((fp=fopen("hfmTree-1","rb"))==NULL))
{
loop:
printf("how many number do you want input?\n");
scanf("%d",&n);
if((fp=fopen("hfmTree-1","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
for(i=0;i<n;i++)
{
printf("\nword[%d]=",i) ;
scanf("%s",&word[i].words) ;
printf("\nweight[%d]=",i);
scanf("%d",&weight[i].weighter);
}
sava(n) ;
}
else
{
if((fp3=fopen("NO.","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp3,"%d",&n);
if((fp=fopen("hfmTree-1","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
for(p2=weight;p2<weight+n;p2++)
{
fread(p2,sizeof(struct weighted),1,fp) ;
weigh[k]=p2->weighter ;
k++;
}
Haffman(weigh,n,myHaffTree,b);
HaffmanCode(myHaffTree,n,myHaffCode);
while(1)
{
do
{
clrscr();
menu();
scanf("%d",&w);
}while(w!=1&&w!=2&&w!=3&&w!=4&&w!=5);
switch(w)
{
case 1: clrscr();
printf("plesase input :\n");
scanf("%s",&c) ;
if((fp2=fopen("ToBeTran","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp2,"%s",c) ;
fclose (fp2);
code(myHaffCode,n) ;
getch();
break;
case 2: if((fp2=fopen("ToBeTran","rb"))==NULL)
{
printf("\n\n Please,increase records first~!! \n" );
return;
}
fscanf(fp2,"%s",&c);
printf("The words:");
printf("%s",c);
if((fp4=fopen("TextFile.","wb"))==NULL)
{
printf("Error,cannot open file\n" );
exit(0);
}
fprintf(fp4,"%s",c) ;
fclose (fp4);
getch();
break;
case 3: clrscr();
printf("The huffman Tree:\n\n\n\n\n\n");
p=InsertLeftNode(root,b[n-1][2]);
creat(p,n-1,b);
PrintBiTree(root->leftChild,n);
printf("\n");
getch();
clrscr();
break;
case 4:goto loop;
case 5:exit(0);
}
}
}
getch();
}
㈥ 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++裡面的數據類型）裝載他們並按照權值大小進行排序，然後通過哈弗曼演算法（另用一個函數來計算）創建一個哈弗曼數，並計算出它的哈弗曼編碼並寫到結構體中，這樣就把字元進行了哈弗曼壓縮。這就是整個過程