『壹』 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語言完成：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");
}
}
『叄』 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語言編的haffuman編解碼，要求可以從文件中讀取，然後編碼/解碼，在線等，很急哈
#include <stdio.h>
#include <string.h>
#define N 50 /*葉子結點數*/
#define M 2*N-1 /*樹中結點總數*/
typedef struct
{
char data[5]; /*結點值*/
int weight; /*權重*/
int parent; /*雙親結點*/
int lchild; /*左孩子結點*/
int rchild; /*右孩子結點*/
} HTNode;
typedef struct
{
char cd[N]; /*存放哈夫曼碼*/
int start;
} HCode;
void CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode;
int min1,min2;
for (i=0;i<2*n-1;i++) /*所有結點的相關物姿核域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*構造冊陸哈夫曼樹*/
{
min1=min2=32767; /*lnode和rnode為最小權重的兩個結點位置*/
lnode=rnode=-1;
for (k=0;k<=i-1;k++)
if (ht[k].parent==-1) /*只在尚未構造二叉樹的結點中查找*/
{
if (ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0;i<n;i++) /*根據哈夫曼樹求哈夫曼編碼*/
{
hc.start=n;c=i;
f=ht[i].parent;
while (f!=-1) /*循序直到樹根結點*/
{
if (ht[f].lchild==c) /*處理左孩子結罩掘點*/
hc.cd[hc.start--]='0';
else /*處理右孩子結點*/
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;
}
hc.start++; /*start指向哈夫曼編碼最開始字元*/
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
int sum=0,m=0,j;
printf(" 輸出哈夫曼編碼:\n"); /*輸出哈夫曼編碼*/
for (i=0;i<n;i++)
{
j=0;
printf(" %s:\t",ht[i].data);
for (k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n 平均長度=%g\n",1.0*sum/m);
}
void main()
{
int n=15,i;
char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
HTNode ht[M];
HCode hcd[N];
for (i=0;i<n;i++)
{
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
}
你可以改一下從文件讀取
『伍』 求哈夫曼編譯器 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;
}
『陸』 300分高分求助，哈夫曼編/解碼，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語言哈夫曼樹的編碼及其解碼問題，數據結構與演算法，求解
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct TreeNode *HuffmanTree;
typedef HuffmanTree ElemType;
typedef struct code Code;
struct TreeNode{
char c;
int Weight;
HuffmanTree Left,Right;
};
typedef struct Heap{
ElemType Data[MAXSIZE];
int Size;
int Capacity;
}*MinHeap;
struct code{
char c;
char code[10];
};
struct TNode{
int Data;
struct TNode* lchild;
struct TNode* rchild;
};
MinHeap BuildHeap()
{
MinHeap tmpH;
tmpH=(MinHeap)malloc(sizeof(struct Heap));
ElemType Min=(ElemType)malloc(sizeof(ElemType));
Min->Weight=-1,Min->Left=Min->Right=NULL;
tmpH->Size=0;
tmpH->Capacity=MAXSIZE;
tmpH->Data[0]=Min;
return tmpH;
}
int isFull(MinHeap H)
{
return H->Size>=H->Capacity;
}
int isEmpty(MinHeap H)
{
return H->Size==0;
}
void Insert(MinHeap H,ElemType T)
{
int i;
if(isFull(H)){
printf("MinHeap is Full");
return ;
}
i=++H->Size;
for(;H->Data[i/2]->Weight>T->Weight;i/=2)
H->Data[i]=H->Data[i/2];
H->Data[i]=T;
}
ElemType DeleteMin(MinHeap H){
int Parent,child;
ElemType min,tmp;
if(isEmpty(H)){
printf("The Heap is Empty");
return NULL;
}
min=H->Data[1];
tmp=H->Data[H->Size--];
for(Parent=1;Parent*2<H->Size;Parent=child)
{
child=Parent*2;
if(child!=H->Size-1&&H->Data[child]->Weight>李缺H->哪租辯Data[child+1]->Weight)
child++;
if(tmp->Weight>H->Data[child]->Weight)
{
H->Data[Parent]=H->Data[child];
}else break;
}
H->Data[Parent]=tmp;
return min;
}
void InitHeap(MinHeap H,int n)
{
ElemType tmp;
for(int i=0;i<n;i++)
{ getchar();
tmp=(ElemType)malloc(sizeof(ElemType));
scanf("%c,%d",&tmp->c,&tmp->Weight);
tmp->Left=tmp->Right=NULL;
Insert(H,tmp);
}
}
HuffmanTree Huffman(MinHeap H)
{
int i;
HuffmanTree T;
for(i=1;i<H->Size;i++)
{
T=(HuffmanTree)malloc(sizeof(HuffmanTree));
T->Left=DeleteMin(H);
T->型基Right=DeleteMin(H);
T->Weight=T->Left->Weight+T->Right->Weight;
Insert(H,T);
}
T=DeleteMin(H);
return T;
}
int main()
{
int n;
scanf("%d",&n);
Code ans[n];
MinHeap H=BuildHeap();
HuffmanTree T;
InitHeap(H,n);
T=Huffman(H);
return 0;
}
哈夫曼樹的構造，編碼有01左右子樹之分，稍微復雜
『捌』 哈夫曼編碼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語言實現
說明：本程序是依據嚴蔚敏的數據結構（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>
#include<stdlib.h>
#define
NIL
-2
#define
Size_Max_bm
30
#define
left(i)
(2*(i)+1)
#define
right(i)
(2*(i)+2)
#define
swap(a,b)
{cjys
t;t=(a);(a)=(b);(b)=t;}
#define
parent(i)
((i)%2?((i)-1)/2:((i)-2)/2)typedef
struct
cjys
{
char
sj;
int
pl;
struct
cjys
*left;
struct
cjys
*right;
}cjys;typedef
struct
cjdl
{
int
size;
int
leapsize;
cjys
*p;
}cjdl;
cjys
*fpnn(void);
void
input(cjdl
*p);
cjys
*fpnn(void);
void
zxdwh(cjys
*p,
int
i,
int
leapsize);
void
rd(cjdl
*p,
cjys
tp);
cjys
cd(cjdl
*p);
void
hbs(cjdl
*p);
cjys
*cjs(cjdl
*p);
void
bls(cjys
*p,int
*jl,
int
i);
void
disp(char
*tp,
cjys
*p);int
main()
{
cjdl
p;
char
x[255];
cjys
*re=NULL;
int
jl[Size_Max_bm];
input(&p);
re=cjs(&p);
printf("對照編碼圖為:\n");
bls(re,jl,0);
freopen("CON","r",stdin);
printf("輸入Huffman碼(VLC):");
scanf("%s",x);
disp(x,re);
system("pause");
}
void
input(cjdl
*p)
{
int
i;
cjys
*tp;
tp=fpnn();
printf("輸入字母個數:");
scanf("%d",
&p->size);
p->p=malloc(sizeof(cjys)*p->size);
p->leapsize=0;
for(i
=
0;
i
<
p->size;i++)
{
printf("輸入第%d字母:",i+1),scanf("
%c",&tp->sj);
printf("輸入出現次數(頻率整數):"),scanf("%d",&tp->pl);
rd(p,*tp);
}
free(tp);
}
cjys
*fpnn(void)
{
cjys
*p=NULL;
p=malloc(sizeof(cjys));
p->left=NULL;
p->right=NULL;
return
p;
}
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
{
int
l=left(i),
r=right(i),
mini=i;
if(l<leapsize
&&
p[l].pl<p[mini].pl)
mini=l;
if(r<leapsize
&&
p[r].pl<p[mini].pl)
mini=r;
if(mini
!=
i)
{
swap(p[i],p[mini]);
zxdwh(p,mini,leapsize);
}
}
void
rd(cjdl
*p,
cjys
tp)
{
if(p->leapsize
==
p->size)
{
printf("隊列已滿!");
exit(0);
}
p->p[p->基棗leapsize]=tp;
int
j=p->leapsize,k=parent(j);
while(k>=0
&&
p->p[j].pl
<
p->p[k].pl)
{
swap(p->p[j],p->p[k]);
j=k;
k=parent(j);
}
p->御褲leapsize++;
}
cjys
cd(cjdl
*p)
{
if(p->leapsize
==
0)
{
printf("隊列搏拆拆已空!");
exit(0);
}
cjys
tp=p->p[0];
p->leapsize--;
p->p[0]=p->p[p->leapsize];
zxdwh(p->p,0,p->leapsize);
return
tp;
}
void
hbs(cjdl
*p)
{
cjys
*p1=NULL,
*p2=NULL;
cjys
tp;
p1=fpnn();
p2=fpnn();
*p1=cd(p);
*p2=cd(p);
tp.left=p1;
tp.right=p2;
tp.pl=p1->pl+p2->pl;
tp.sj=NIL;
rd(p,tp);
}cjys
*cjs(cjdl
*p)
{
int
i,
n=p->leapsize;
cjys
*tp=NULL;
tp=fpnn();
for(i
=
0;
i
<
n-1;
i++)
hbs(p);
*tp=p->p[0];
return
tp;
}
void
bls(cjys
*p,
int
*jl,
int
i)
{
if(p
==
NULL)
return;
if(p->sj!=NIL)
{
int
i2;
printf("%c:",p->sj);
for(i2
=
0;
i2
<
i;
i2++)
printf("%d",jl[i2]);
printf("\n");
}
jl[i]=0;
bls(p->left,jl,i+1);
jl[i]=1;
bls(p->right,jl,i+1);
}
void
disp(char
*tp,
cjys
*p)
{
cjys
*ttp=NULL;
int
pd=0;
while(1)
{
ttp=p;
while(1)
{
if(ttp->sj
!=
NIL)
{
printf("%c",ttp->sj);
break;
}
if(*tp
==
'\0')
{
pd=1;
break;
}
if(*tp++
==
'0'
)
ttp=ttp->left;
else
ttp=ttp->right;
}
if(pd)
break;
}
}