哈夫曼樹編譯器實驗心得體會
⑴ 哈夫曼樹
這是我們的作業題，自己寫 的……（可能輸入的格式跟你要的不一致，自己改一下）
如果有什麼不懂的就問我，我可以把其中所有相關的文件發給你 ^^
註：1、 初始化創建哈夫曼樹有三種選擇，其中選擇編譯課本測試數據時和編譯源文件是，調用的輸入文件分別是：test.txt和input.txt；字母的哈夫曼編碼都保存在文件：hmfTree.txt；
2、 用戶自定義模式下，需要編碼的文件內容保存在ToBeTran.txt中；課本測試數據和源文件代碼分別保存在course.txt和sorse.txt中，在（1）中選擇不同的選項，則在編碼時調用相應的文件進行編碼，編碼結果保存在文件CodeFile.txt中。
3、 文件解碼時，調用文件CodeFile.txt進行解碼，得到的結果保存在文件TextFile.txt中。
4、 列印代碼文件：調用CodeFile.txt，結果顯示在終端並保存在文件CodePrin.txt中。
5、 列印哈夫曼樹：用凹入表形式把哈夫曼樹顯示在終端，同時將它保存在文件TreePrint..txt中。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //從哈夫曼樹中選擇出最小的兩個節點
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //對數組進行遍歷，尋找最小的兩個節點
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //終端輸出選擇菜單
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---創建哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件編碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件解碼 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---列印代碼文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼樹 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼樹的存儲結構 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("選擇菜單功能選項：");
}
void output (HuffmanTree th,int n){ //輸出哈夫曼樹的存儲結構
int i=0;
cout<<"序號"<<" "<<"字元"<<" "<<"雙親"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"權值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //創建哈夫曼樹
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定義 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---編碼課本測試數據 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---編碼源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("選擇菜單功能選項：");
scanf("%d",&k);
if(k==1){
printf("輸入需要編碼的字元總數: ");
scanf("%d",&n);
printf("\n輸入需要編碼字元的權值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n輸入需要編碼的字元串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;i++){
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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //編碼：對文件TobeTran.txt進行解碼
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //解碼：對CodeFile.txt文件進行解碼
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //列印代碼文件，顯示在終端，每行50個代碼
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //列印哈夫曼樹形（在參數的傳遞上，是文科給自己提出的意見才很好的解決了之後的操作難題^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//這個挺有用的：在文件末尾加入內容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
註：
input.txt文件中保存一下數據：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}
⑵ 哈夫曼編/解碼器問題:C語言版的數據結構，我急啊！那位朋友幫幫忙，結果必需是我的問題的結果，不能有錯啊
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//////////////////////////////////////////////////////////////////////////////
/*定義赫夫曼樹結點的結構體變數，存放結點的權值、字元、雙親、坐孩子和右孩子*/
typedef struct{
int weight;
char ch; //增加一個域用於存放該節點的字元
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; //指向赫夫曼編碼的指針
//////////////////////////////////////////////////////////////////////////////
/*本程序用到的函數原型*/
void welcome(); //列印操作選擇界面
void HuffmanCoding(HuffmanTree &,char *,int *,int);//建立赫夫曼樹的演算法
void select(HuffmanTree HT,int j,int *s1,int *s2); //從目前已建好的赫夫曼樹中選擇parent為0且weight最小的兩個結點
void Init(); //輸入n個字元及其對應的權值，根據權值建立哈夫曼樹
void Coding(); //編碼
void Decoding(); //解碼
void Print_code(); //列印解碼好的代碼文件
void Print_tree(); //以凹凸表形式列印哈夫曼樹
int Read_tree(HuffmanTree &); //從文件中讀入赫夫曼樹
void find(HuffmanTree &HT,char *code,char *text,int i,int m);//解碼時根據01字元串尋找相應葉子節點的遞歸演算法
void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//將內存中的赫夫曼樹轉換成凹凸表形式的赫夫曼樹
HuffmanTree HT; //全局變數，指向存放赫夫曼樹的存儲空間
int n=0; //全局變數，存放赫夫曼樹葉子結點的數目
int main()
{
char select;
while(1)
{
welcome();
scanf("%c",&select);
switch(select)
{
case 'i':
case 'I':Init();break;
case 'c':
case 'C':Coding();break;
case 'd':
case 'D':Decoding();break;
case 'p':
case 'P':Print_code();break;
case 't':
case 'T':Print_tree();break;
case 'e':
case 'E':exit(1);
default :printf("Input error!\n");
}
getchar();
}
return 0;
}
void welcome() //列印操作選擇界面
{
printf("*-----------------------------------------------------*\n");
printf("| What do you want to do? |\n");
printf("|-----------------------------------------------------|\n");
printf("| |\n");
printf("| I--------------------------Init the Huffman tree. |\n");
printf("| C--------------------------Code your file. |\n");
printf("| D--------------------------Decode the code. |\n");
printf("| P--------------------------Print the codefile. |\n");
printf("| T--------------------------Print the Huffman tree. |\n");
printf("| |\n");
printf("*-----------------------------------------------------*\n");
}
//////////////////////////////////////////////////////////////////////////////////////
/*初始化函數，輸入n個字元及其對應的權值，根據權值建立哈夫曼樹，並將其存於文件hfmtree中*/
void Init()
{
FILE *fp;
int i,n,w[52]; //w數組存放n個字元的權值
char character[52]; //存放n個字元
printf("\n輸入字元個數 n:");
scanf("%d",&n); //輸入字元集大小
printf("輸入%d個字元及其對應的權值:\n",n);
for (i=0;i<n;i++)
{
char b=getchar();
scanf("%c",&character[i]);
scanf("%d",&w[i]); //輸入n個字元和對應的權值
}
HuffmanCoding(HT,character,w,n); //建立赫夫曼樹
if((fp=fopen("hfmtree.txt","w"))==NULL)
printf("Open file hfmtree.txt error!\n");
for (i=1;i<=2*n-1;i++)
{
if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //將建立的赫夫曼樹存入文件hfmtree.txt中
printf("File write error!\n");
}
printf("\n建立赫夫曼樹成功，已將其存於文件hfmtree.txt中\n");
fclose(fp);
}
///////////////////////////////////////////////////////////////////////////////////
//////建立赫夫曼樹的演算法///////////////////////////////////////////////////////////
void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)
{
int m,i,s1,s2;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;++i,++p,++character,++w)
{p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}
for(;i<=m;++i,++p) {p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}
for(i=n+1;i<=m;++i)
{
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;
}
}
///////////////////////////////////////////////////////////////////////////////
/*從HT[1]到HT[j]中選擇parent為0且weight最小的兩個結點，用s1和s2返回其序號*/
void select(HuffmanTree HT,int j,int *s1,int *s2)
{
int i;
//找weight最小的結點
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s1=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))
*s1=i;
HT[*s1].parent=1;
//找weight次小的結點
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s2=i;break;}
for (;i<=j;i++)
if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight))
*s2=i;
}
///////////////////////////////////////////////////////////////////////////////
/*對文件tobetrans中的正文進行編碼，然後將結果存入文件codefile中*/
void Coding()
{
FILE *fp,*fw;
int i,f,c,start;
char *cd;
HuffmanCode HC;
if(n==0)
n=Read_tree(HT);//從文件hfmtree.txt中讀入赫夫曼樹,返回葉子結點數
/////以下程序段求赫夫曼樹中各葉子節點的字元對應的的編碼，並存於HC指向的空間中
{
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=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));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
/////////////////////////////////////////////////////////////////////////////////////
if((fp=fopen("tobetrans.txt","rb"))==NULL)
printf("Open file tobetrans.txt error!\n");
if((fw=fopen("codefile.txt","wb+"))==NULL)
printf("Open file codefile.txt error!\n");
char temp;
fscanf(fp,"%c",&temp); //從文件讀入第一個字元
while(!feof(fp))
{
for(i=1;i<=n;i++)
if(HT[i].ch==temp) break; //在赫夫曼樹中查找字元所在的位置
for(int r=0;HC[i][r]!='\0';r++) //將字元對應的編碼存入文件
fputc(HC[i][r],fw);
fscanf(fp,"%c",&temp); //從文件讀入下一個字元
}
fclose(fw);
fclose(fp);
printf("\n對文件hfmtree.txt編碼成功,結果已存入codefile.txt中。\n\n");
}
/////////////////////////////////////////////////////////////////////////
/*將文件codefile中的代碼進行解碼，結果存入文件textfile中*/
void Decoding()
{
FILE *fp,*fw;
int m,i;
char *code,*text,*p;
if(n==0)
n=Read_tree(HT);//從文件hfmtree.txt中讀入赫夫曼樹,返回葉子結點數
if((fp=fopen("codefile.txt","rb"))==NULL)
printf("Open file codefile.txt error!\n");
if((fw=fopen("textfile.txt","wb+"))==NULL)
printf("Open file textfile.txt error!\n");
code=(char *)malloc(sizeof(char));
fscanf(fp,"%c",code); //從文件讀入一個字元
for(i=1;!feof(fp);i++)
{
code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空間
fscanf(fp,"%c",&code[i]); //從文件讀入下一個字元
}
code[i-1]='\0';
/////////到此codefile.txt文件中的字元已全部讀入，存放在code數組中
text=(char *)malloc(100*sizeof(char));
p=text;
m=2*n-1;
if(*code=='0')
find(HT,code,text,HT[m].lchild,m); //從根節點的左子樹去找
else
find(HT,code,text,HT[m].rchild,m); //從根節點的右子樹去找
for(i=0;p[i]!='\0';i++) //把解碼好的字元存入文件textfile.txt中
fputc(p[i],fw);
fclose(fp);
fclose(fw);
printf("\n對codefile.txt文件解碼成功，結果已存入textfile.txt文件。\n\n");
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
/*將文件codefi1e以緊湊格式顯示在終端上,每行50個代碼。同時將此字元形式的編碼文件寫入文件codeprint中。*/
void Print_code()
{
FILE *fp,*fw;
char temp;
int i;
if((fp=fopen("codefile.txt","rb"))==NULL)
printf("Open file codefile.txt error!\n");
if((fw=fopen("codeprint.txt","wb+"))==NULL)
printf("Open file codeprint.txt error!\n");
printf("\n文件codefi1e以緊湊格式顯示如下:\n");
fscanf(fp,"%c",&temp); //從文件讀入一個字元
for (i=1;!feof(fp);i++)
{
printf("%c",temp);
if(i%50==0) printf("\n");
fputc(temp,fw); //將該字元存入文件codeprint.txt中
fscanf(fp,"%c",&temp); //從文件讀入一個字元
}
printf("\n\n此字元形式的編碼已寫入文件codeprint.txt中.\n\n");
fclose(fp);
fclose(fw);
}
//////////////////////////////////////////////////////////////////////////////////////////////////
/*將已在內存中的哈夫曼樹以凹凸表形式顯示在屏幕上，同時將此字元形式的哈夫曼樹寫入文件treeprint中。*/
void Print_tree()
{
unsigned char T[100][100];
int i,j,m=0;
FILE *fp;
if(n==0)
n=Read_tree(HT);//從文件hfmtree.txt中讀入赫夫曼樹,返回葉子結點數
Convert_tree(T,0,&m,2*n-1); //將內存中的赫夫曼樹轉換成凹凸表形式的樹，存於數組T中
if((fp=fopen("treeprint.txt","wb+"))==NULL)
printf("Open file treeprint.txt error!\n");
printf("\n以凹凸表形式列印已建好的赫夫曼樹：\n");
for(i=1;i<=2*n-1;i++)
{
for (j=0;T[i][j]!=0;j++)
{
if(T[i][j]==' ') {printf(" ");fputc(T[i][j],fp);}
else
{printf("%d",T[i][j]);fprintf(fp,"%d\n",T[i][j]);}
}
printf("\n");
}
fclose(fp);
printf("\n此字元形式的哈夫曼樹已寫入文件treeprint.txt中.\n\n");
}
//////////////////////////////////////////////////////////////////////////////////
/*從文件hfmtree.txt中讀入赫夫曼樹，返回葉子節點數*/
int Read_tree(HuffmanTree &HT)
{
FILE *fp;
int i,n;
HT=(HuffmanTree)malloc(sizeof(HTNode));
if((fp=fopen("hfmtree.txt","r"))==NULL)
printf("Open file hfmtree.txt error!\n");
for (i=1;!feof(fp);i++)
{
HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空間
fread(&HT[i],sizeof(HTNode),1,fp); //讀入一個節點信息
}
fclose(fp);
n=(i-1)/2;
return n;
}
////////////////////////////////////////////////////////////////
/*解碼時根據01字元串尋找相應葉子節點的遞歸演算法*/
void find(HuffmanTree &HT,char *code,char *text,int i,int m)
{
if(*code!='\0') //若解碼未結束
{
code++;
if(HT[i].lchild==0&&HT[i].rchild==0) //若找到葉子節點
{
*text=HT[i].ch; //將葉子節點的字元存入text中
text++;
if((*code=='0'))
find(HT,code,text,HT[m].lchild,m); //繼續從根節點的左子樹找
else
find(HT,code,text,HT[m].rchild,m); //繼續從根節點的右子樹找
}
else //如果不是葉子節點
if(*code=='0')
find(HT,code,text,HT[i].lchild,m); //從該節點的左子樹去找
else
find(HT,code,text,HT[i].rchild,m); //從該節點的右子樹去找
}
else
*text='\0'; //解碼結束
}
////////////////////////////////////////////////////////////////////////
/*將內存中的赫夫曼樹轉換成凹凸表形式的赫夫曼樹*/
void Convert_tree(unsigned char T[100][100],int s,int *i,int j)
{
int k,l;
l=++(*i);
for(k=0;k<s;k++)
T[l][k]=' ';
T[l][k]=HT[j].weight;
if(HT[j].lchild)
Convert_tree(T,s+1,i,HT[j].lchild);
if(HT[j].rchild)
Convert_tree(T,s+1,i,HT[j].rchild);
T[l][++k]='\0';
}
為了您的安全，請只打開來源可靠的網址
打開網站 取消
來自: http://hi..com/laij/blog/item/4f3edefb6008321e6c22eb34.html
⑶ 哈夫曼編/解碼器的問題：請求高手幫幫忙，課程設計用的，自己寫的錯誤太多了，萬分感謝，c描述。拜託了
以下程序在c-free下測試成功。
演算法參考 數據結構（C語言版）——清華大學出版社
請根據題目具體要求進行修改！有問題找我……
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char ElemType;
typedef char** HuffmanCode;
typedef int Status;
typedef struct
{
ElemType elem;
unsigned int m_weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight;
void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);
void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
//w存放n個字元的權值（均>0），構造Huffman樹HT，並求出n個字元的Huffman編碼HC
int i,m,s1,s2,start,c,f;
char *cd;
HuffmanTree p;
if(n<=1) return;
m=2*n-1;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用
for(p=HT,i=1;i<=n;++i,++p,++w)
{
(*HT)[i].elem=w[i-1].elem;
(*HT)[i].m_weight=w[i-1].m_weight;
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
}
for(;i<=m;++i,++p)
{
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=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=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
}
//從葉子到根逆向求每個字元的Huffman編碼
(*HC)=(HuffmanCode)malloc(n*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=(*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));
strcpy((*HC)[i],&cd[start]); //從cd復制編碼到HC
}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
int i;
(*s1)=(*s2)=0;
for(i=1;i<=n;i++)
{
if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else
(*s2)=i;
}
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
if((*s1)==0) (*s1)=i;
else
if((*s2)==0)
{
if(HT[i].m_weight<HT[(*s1)].m_weight)
{
(*s2)=(*s1);
(*s1)=i;
}
else (*s2)=i;
}
}
}
if((*s1)>(*s2))
{
i=(*s1);
(*s1)=(*s2);
(*s2)=i;
}
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}
Status main(void)
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c;
int i,n;
int wei;
printf("input the tatol number of the Huffman Tree:" );
scanf("%d",&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
printf("input the element & its weight:");
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1;
}
⑷ 哈夫曼編碼的解碼過程的大致思路是什麼（不要代碼）
哈夫曼樹和字元編碼對應你都弄完了，得到是如a :01 b :101對應關系，通過這個關系直接將像「asdsdfdfg」直接轉換為「01110101」這樣二進制編碼。解碼的時候，讀取二進制編碼，先讀取一位，然後在關系表中查找該二進制數對應的字元，如果沒有找到，繼續讀取二位，然後繼續在關系表中查找該二位二進制對應的字元。如此循環，知道找到字元位置，然後將二進制數替換為相應的字元，知道所有的數都替換完為止。
⑸ 哈夫曼樹編碼如何保證通信過程中以及解碼的時候順序不變呢
知道了編碼用的哈夫曼樹後。從根結點出發，逐個讀入接收電文中的二進制碼；然後又重新從根結點開始繼續解碼，直到二進制電文結束。 Huffman 編碼 一
⑹ 題目：哈夫曼編碼，解碼系統
/* 哈夫曼編碼*/
#include "graphics.h"
#include "stdlib.h"
#include "Stdio.h"
#include "Conio.h"
#define MAX 53
char bmfile[10];
char a[100];
typedef struct
{char c,s[10];}MM;
MM mm[53];
typedef struct /*以數組存儲哈夫曼樹時的結點類型*/
{char ch;
int w,lcd,rcd,pt; /*權值、左孩子、右孩子、雙親*/
}HuffNode;
HuffNode Hm[MAX];
typedef struct CNode /*Auffman編碼的結點類型*/
{ char c;
struct CNode *prv;
}CODE;
CODE *cd;
wjbm1 (char a[])/*從文件中讀取要進行編碼的字元*/
{FILE *fp3;
char ch;
int i=0,n=0,k,t,m;
/*printf("\n輸入要編碼的文件名：");
scanf("%s",bmfile);*/
if((fp3=fopen("bmfile.txt","r"))==NULL)
{printf("\n文件不存在");
exit(0);}
while(!feof(fp3))
a[i++]=fgetc(fp3);
a[i]='\0';
for(i=0;a[i]!='\0';i++)
{if(a[i]>='A'&&a[i]<='Z') {Hm[a[i]-65].ch=a[i]; Hm[a[i]-65].w++;}
if(a[i]>='a'&&a[i]<='z') {Hm[a[i]-71].ch=a[i]; Hm[a[i]-71].w++;}
if(a[i]==' ') {Hm[52].ch=' ';Hm[52].w++;}
}
for(i=0;i<53;i++)
if(Hm[i].w!=0)
{ Hm[n].ch=Hm[i].ch;
Hm[n].w=Hm[i].w;
Hm[n].lcd=-1;
Hm[n].rcd=-1;
Hm[n].pt=-1;
n++;}
fclose(fp3);
return n;
}
zfbm1(char a[])
{
int n=0,i;
gets(a);
for(i=0;a[i]!='\0';i++)
{if(a[i]>='A'&&a[i]<='Z') {Hm[a[i]-65].ch=a[i]; Hm[a[i]-65].w++;}
if(a[i]>='a'&&a[i]<='z') {Hm[a[i]-71].ch=a[i]; Hm[a[i]-71].w++;}
if(a[i]==' ') {Hm[52].ch=' ';Hm[52].w++;}
}
printf("\n葉字信息(字元、權值):");
for(i=0;i<53;i++)
if(Hm[i].w!=0)
{printf("(%c,%d)",Hm[i].ch,Hm[i].w);
Hm[n].ch=Hm[i].ch;
Hm[n].w=Hm[i].w;
Hm[n].lcd=-1;
Hm[n].rcd=-1;
Hm[n].pt=-1;
n++;}
return n;
}
charTJ()
{char c;
int i;
printf("\n1-從文件中讀取字元生成樹;2-從鍵輸入字母生成樹;3-退出;\n");
while(1)
switch(c=getch())
{case '1':wjbm1(a);return;
case '2':puts("\n輸入字母");zfbm1(a);return;
case '3':return;
default:printf("\n輸入無效,重新輸入");scanf("%d",&c);}
}
void HuffmanCode(int n) /*哈夫曼編碼。n為哈夫曼樹的葉子數*/
{ int i,k,t;
CODE *p,*h;
cd=(CODE*)malloc(sizeof(CODE)*n);/*用於存儲每個葉子的編碼(鏈棧)*/
for(i=0;i<n;i++) /*搜索第i+1個葉子*/
{ k=i;h=0;
while((Hm+k)->pt>=0)
{ if((Hm+(Hm+k)->pt)->lcd==k)t=0;else t=1;
p=(CODE*)malloc(sizeof(CODE));
p->c=48+t;p->prv=h;h=p;
k=(Hm+k)->pt;
}
cd[i].prv=h;
}
}
void dispCodes(int n) /*顯示*/
{ int i,j=0;
CODE *p;
for(i=0;i<n;i++)
{ p=cd[i].prv;
/*printf("\n%c:",Hm[i].ch); */
mm[i].c=Hm[i].ch;
j=0;
while(p)
{{/*printf("%c",p->c);*/ mm[i].s[j++]=p->c;}
mm[i].s[j]='\0';
p=p->prv;
}
}
puts("\n顯示結果：");
for(i=0;i<n;i++)
printf("(%c,%s) ",mm[i].c,mm[i].s);
dispCode(n);
}
dispCode(int n) /*將各字元的編碼存入數組mm*/
{ int i,j;
CODE *p;
for(i=0;i<n;i++)
{ p=cd[i].prv;
/*printf("\n%c:",Hm[i].ch); */
mm[i].c=Hm[i].ch;
j=0;
while(p)
{{/*printf("%c",p->c);*/ mm[i].s[j++]=p->c;}
mm[i].s[j]='\0';
p=p->prv;
} }
}
Huffmanshu(int n) /*顯示哈夫曼樹的字元編碼*/
{int i;
HuffmanCode(n);
dispCodes(n);
}
wjbm(int n)
{FILE *fp4;
char ch;
int i=0,j;
wjbm1(a);
HuffmanCode(n);
dispCode(n);
fp4=fopen("stfile.txt","w");
for(i=0;a[i]!='\0';i++)
{for(j=0;j<n;j++)
if(a[i]==mm[j].c) fputs(mm[j].s,fp4);
}
puts("結果已寫入文件");
fclose(fp4);
}
zfbm(int n)
{int i,j;
puts(a);
HuffmanCode(n);
dispCode(n);
printf("解碼:");
for(i=0;a[i]!='\0';i++)
{for(j=0;j<n;j++)
if(a[i]==mm[j].c) printf("%s",mm[j].s);}
}
Huffmanbm(int n,HuffNode Hm[])/*哈夫曼編碼*/
{
int k;
char ch;
printf("\n1-結果輸出到文件；2-結果顯示在屏幕;3-退出;\n");
while(1)
switch(ch=getch())
{case '1':wjbm(n);return 0;
case '2':printf("\n源碼:");zfbm(n);return;
case '3':return 0;
default:printf("輸入無效,重新輸入");scanf("%d",&ch);}
}
wjjm(int n,char a[])
{FILE *fp1,*fp2;
char ch;
int i=0,k,t,m;
if((fp1=fopen("jmfile.txt","r"))==NULL)
{printf("\n文件不存在");
exit(0);}
fp2=fopen("st.txt","w");
while(!feof(fp1)) a[i++]=fgetc(fp1);
a[i]='\0'; k=i;
printf("\n1-結果輸出到文件；2-結果顯示在屏幕;3-退出;\n");
t=2*n-2;
while(1)
switch(ch=getch())
{case '1':
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { putc(Hm[t].c,fp2); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { fputc(Hm[t].c,fp2); t=2*n-2;}else {t=Hm[t].rcd;i++;}
} return;
case'2':
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].rcd;i++;}
} return;
case'3':return 0;
}
fclose(fp1);
fclose(fp2);
}
zfjm(int n,char a[])/*對輸入的字元進行解碼*/
{int i,t,k;
printf("\n輸入要解碼的信息:");
scanf("%s",a);
k=strlen(a);
t=2*n-2;
printf("生成源代碼：");
for(i=0;i<=k;)
{ if(a[i]=='0')
if(Hm[t].lcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].lcd;i++;}
else
if(Hm[t].rcd==-1) { printf("%c",Hm[t].c); t=2*n-2;}else {t=Hm[t].rcd;i++;}
}
}
void Huffmanjm(int n,HuffNode Hm[]) /*哈夫曼解碼。n為哈夫曼樹的葉子數*/
{ int m=n;
char *a,ch;
printf("\n1-對文件解碼；2-對字元解碼;3-退出;\n");
while(1)
switch(ch=getch())
{case '1':wjjm(m,a);return 0;
case '2':zfjm(m,a);return;
case '3':return 0;
}
}
void HuffmanTree() /*生成哈夫曼樹*/
{ int i,j,x,y,n;
char c;
n=charTJ();
for(i=0;i<n-1;i++)
{ x=0;
while((Hm+x)->pt>=0)x++; /*搜索第一個未處理的結點*/
y=x+1;
while((Hm+y)->pt>=0)y++; /*搜索第二個未處理的結點*/
j=y;
if((Hm+x)->w>(Hm+y)->w){j=y;y=x;x=j;}
for(j=j+1;j<n+i;j++) /*搜索兩個未處理且權值最小的結點*/
{ if((Hm+j)->pt<0&&(Hm+j)->w<(Hm+x)->w) {y=x;x=j;}
else
if((Hm+j)->pt<0&&(Hm+j)->w<(Hm+y)->w) y=j;
}
(Hm+x)->pt=n+i;(Hm+y)->pt=n+i;(Hm+n+i)->w=(Hm+x)->w+(Hm+y)->w;
(Hm+n+i)->lcd=x;(Hm+n+i)->rcd=y;(Hm+n+i)->pt=-1;
}
puts("\n1-顯示字元的編碼;2-編碼;3-解碼;4-退出;");
while(1)
switch(c=getch())
{case '1':Huffmanshu(n);break;
case '2':Huffmanbm(n,Hm);break;
case '3':Huffmanjm(n,Hm);break;
case '4':return;
}
}
int main()
{ char c;
gotoxy(29,1);
puts("文件編碼解碼系統");
window(1,3,80,25);
HuffmanTree();
getch();
clrscr();
}
⑺ 哈夫曼編碼/解碼器
注釋非常詳細，希望對你有所幫助！
#ifndef Huffman_Tree_h
#define Huffman_Tree_h
#endif
#include <stdio.h>
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree; //存儲赫夫曼樹的結點類型
typedef char * * HuffmanCode; //用於存儲字元集中各個字元相應的赫夫曼編碼
void strcpy(char *S1,char *S2){ //將字元串S2復制到S1
int i = 0;
while( S2[i] != '\0' ){
S1[i] = S2[i];
i++;
}
S1[i] = '\0';
}
void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出權值最小的兩個S1和S2
int i = 1;
s1 = s2 = 0;
HT[0].weight = 65535;
while( i <= t ){ //遍歷查找權值最小的結點S1
if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight )
s1 = i;
i++;
}
i = 1;
while( i <= t ){ //遍歷查找除S1外權值最小的結點S2
if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight )
s2 = i;
i++;
}
}
int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根據各個字元的權值構造赫夫曼樹HT，將對應的赫夫曼編碼存儲在HC中
int s1,s2,m,i,start;
unsigned int c,f;
HTNode * p;
char *cd;
if( n <= 1 ) return 0;
m = 2 * n - 1; //赫夫曼樹的總結點樹為m
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申請存儲赫夫曼樹的空間
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //將各個葉子結點的weight賦以相應的權值，parent,lchild,rchild均賦為0
p->weight = *(w+1);
p->parent = p->lchild = p->rchild = 0;
}
for( ; i <= m; ++i, ++p ){ //將各個非葉子結點的weight,parent,lchild,rchild均賦為0
p->weight = p->parent = p->lchild = p->rchild = 0;
}
for( i = n + 1; i <= m; ++i ){ //構造赫夫曼樹，給各個非葉子結點賦值
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;
}
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; //編碼在數組cd[]中的最前位置
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[]數組的start位置到n-1位置復制給HC[i]
}
free(cd); //釋放空間
return 1;
}
以上為第一部分
#include <stdio.h>
#include <stdlib.h>
#include "Huffman_Tree.h"
#define Yes 1 //當程序已經調用過初始化赫夫曼樹的InitHuff_T()函數，或已從htfTree文件讀取過，則將Init_Mode置為Yes，否則為No
#define No 0
void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼數，要求用戶輸入字元和相應權值
int i = 1,w[100],tem,j;
char a[20];
FILE *save;
printf("請輸入編碼字元集的大小n:");
scanf("%d",&n); //獲取用戶輸入的字元集個數
while( i <= n ){ //獲取用戶輸入的字元和相應權值，分別存儲在ch[]和w[]數組中
printf("請輸入第%d個字元和該字元的權值w:",i);
fflush(stdin);
scanf("%c%d",&ch[i],&w[i]);
i++;
}
ch[i] = '\0';
HuffmanCoding(HT,HC,w,n); //根據用戶的輸入，生成赫夫曼數及各個字元相應的赫夫曼編碼，分別存在HT樹和HC中
if(( save = fopen("htfTree","w")) == NULL ){ //打開用於存儲赫夫曼樹的文件
printf("Open file fail......\n");
exit(0);
}
tem = n; //接下來的14行是將字元集大小轉換成字元形式寫入到文件中
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = n;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
printf("%d\n",n); //向屏幕輸出字元集大小n
fputc('\n',save);
for( i = 1; i <= n; i++ ){ //分別向文件和屏幕輸出各個字元和相應的赫夫曼編碼
fputc(ch[i],save); printf("%c\t",ch[i]);
fputc('\t',save);
fputs(HC[i],save); printf("%s\n",HC[i]);
fputc('\n',save);
}
for(i = 1; i <= 2 * n - 1; i++ ){ //將赫夫曼樹各個結點的parent,lchild,rchild分別寫入到文件中
tem = HT[i].parent; //將i結點的parent轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].parent;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].lchild; //將i結點的lchild轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc(' ',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].lchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc(' ',save);
}
tem = HT[i].rchild; //將i結點的rchild轉換成字元並寫入到文件中
if(tem == 0){
fputc(tem + 48,save);
fputc('\n',save);
}
else{
j = 0;
while( tem != 0 ){
tem = tem / 10;
j++;
}
tem = HT[i].rchild;
a[j] = '\0';
while( tem != 0 ){
a[j - 1] = (char)(tem % 10 + 48);
tem = tem / 10;
j--;
}
fputs(a,save);
fputc('\n',save);
}
}
fclose(save);
}
void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根據赫夫曼編碼將用戶指定的文件中的字元編成相應的編碼,並將所得編碼存儲到用戶指定文件
FILE *ToBeTran,*CodeFile;
char ToBeTran_Name[100],CodeFile_Name[100]; //存儲用戶指定文件的文件名
int i;
char c;
printf("請輸入所要進行編碼的文件的文件名:");
scanf("%s",ToBeTran_Name); //獲得所要進行編碼的文件的文件名
if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
printf("請輸入編碼後編碼表示的信息所存儲到的文件的文件名:");
scanf("%s",CodeFile_Name); //獲得編碼後編碼表示的信息所存儲到的文件的文件名
if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(ToBeTran); //從文件讀取一個字元
while( c != EOF ){ //對文件中的各個字元進行編碼，直至文件結尾
i = 1;
while( c != ch[i] && ch[i] != '\0' ) //在ch[]數組中查找從文件讀取的字元
i++;
if(ch[i] == '\0'){ //未找到，c不在ch[]數組中，c無法被識別，程序出錯，退出
printf("字元%c無法識別，程序將退出。\n",c);
exit(0);
}
fputs(HC[i],CodeFile); //若找到，則將c相應的赫夫曼編碼寫入到文件中
printf("%s",HC[i]); //將c相應的赫夫曼編碼輸出到屏幕
c = fgetc(ToBeTran); //讀入文件中的下一個字元
}
printf("\n");
fclose(ToBeTran);
fclose(CodeFile);
}
void Decoding(HuffmanTree HT, char ch[] , int n){ //對指定的存儲由赫夫曼編碼表示的信息的文件進行解碼，翻譯成相應的字元表示，並存儲到指定文件
int p,i = 1;
char code[1000],c;
char CodeFile_Name[100],TextFile_Name[100]; //存儲用戶指定文件的文件名
p = 2 * n - 1;
FILE *CodeFile,*TextFile;
printf("請輸入所要譯的文件名:");
scanf("%s",CodeFile_Name); //獲得所要譯的文件的文件名
if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
printf("請輸入譯後的字元存儲到的文件的文件名:");
scanf("%s",TextFile_Name); //獲得譯後的字元存儲到的文件的文件名
if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打開文件
printf("Open file fail......\n");
exit(0);
}
c = fgetc(CodeFile);
while( c != EOF ){
code[i] = c;
i++;
c = fgetc(CodeFile);
}
code[i] = '\0'; //從文件讀取字元，存儲在code[]數組中
i = 1;
while ( code[i] != '\0' && p != 0 ){ //對數組code[]中的赫夫曼編碼進行解碼
if ( code[i] == '0' )
p=HT[p].lchild; //進入左分支
else
p = HT[p].rchild; //進入右分支
if (!HT[p].lchild&& !HT[p].rchild){ //進入葉子結點
fputc(ch[p], TextFile); //將相應的字元寫入到文件中
printf("%c",ch[p]); //將相應的字元輸出到屏幕
p = 2 * n - 1; //重新從樹根出發進行解碼
}
i++;
}
printf("\n");
}
void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //從文件讀取赫夫曼樹
FILE *htfTree;
char c[100],ch1;
int i,j,t;
if(( htfTree = fopen("htfTree","r")) == NULL ){ //打開存有赫夫曼樹信息的文件
printf("Open file fail......\n");
exit(0);
}
fgets(c,10,htfTree); //獲取赫夫曼樹葉子結點個數的字元串表示形式
i = 0; //以下6行將字元串形式轉換成整數形式
while( c[i] != '\n' )
i++;
n = 0;
for( j = 0; j < i; j++ )
n = 10 * n + c[j] - '0'; //求出葉子結點數n
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申請HC空間
HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申請赫夫曼樹存儲空間
i = 1;
while( i <= n ){
ch[i] = fgetc(htfTree); //讀取字元集中的一個字元
HC[i] = (char *)malloc((10)*sizeof(char)); //申請用於存儲讀取到的字元集中的字元的赫夫曼編碼的空間
fgetc(htfTree); //將『\t』輸出
ch1 = fgetc(htfTree); //讀取赫夫曼編碼，存儲在相應的HC[i][]數組里
int j = 0;
while( ch1 != '\n' ){
HC[i][j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HC[i][j] = '\0';
i++;
}
ch[i] = '\0';
i = 0;
while( i < 2 * n - 1 ){ //讀取赫夫曼樹的各個結點的parent,lchild,rchild.並賦值到赫夫曼樹HT中
ch1 = fgetc(htfTree); //讀取parent的字元串形式,存儲在c[]中，並將其轉換成整數形式，賦給HT[i].parent
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].parent = 0;
for( t = 0; t < j; t++ )
HT[i+1].parent = 10 * HT[i+1].parent + c[t] - '0';
ch1 = fgetc(htfTree); //讀取lchild的字元串形式，並將其轉換成整數形式，賦給HT[i].lchild
j = 0;
while( ch1 != ' ' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].lchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - '0';
ch1 = fgetc(htfTree); //讀取rchild的字元串形式，並將其轉換成整數形式，賦給HT[i].rchild
j = 0;
while( ch1 != '\n' ){
c[j] = ch1;
j++;
ch1 = fgetc(htfTree);
}
HT[i+1].rchild = 0;
for( t = 0; t < j; t++ )
HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - '0';
i++;
}
}
int main(){
HuffmanTree HT;
HuffmanCode HC;
char ch[100]; //用於存儲字元集
int n,Init_Mode = No; //n為字元集的大小，Init_Mode = No 表示內存中沒有赫夫曼樹的信息
char mode; //讓用戶選擇不同的操作
printf("請輸入你要選擇的功能\n");
printf("\t\tI -- 初始化\t\tE -- 編碼\n");
printf("\t\tD -- 解碼 \t\tQ -- 退出程序\n");
scanf("%c",&mode); //獲得用戶選擇的操作
while( mode != 'Q' && mode != 'q' ){ //當用戶輸入不為Q或q時，執行相應操作
switch(mode){
case 'I' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'i' :
InitHuff_T(HT,HC,ch,n);
Init_Mode = Yes;
break;
case 'E' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'e' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Encoding(HT,HC,ch);
Init_Mode = Yes;
break;
case 'D' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
break;
case 'd' :
if( No == Init_Mode )
ReadHuff_T(HT,HC,ch,n);
Decoding(HT,ch,n);
Init_Mode = Yes;
default :
printf("您的輸入有錯，請重新選擇.\n");
}
printf("請輸入你要選擇的功能\n");
printf("\tI -- 初始化\tE -- 編碼\n");
printf("\tD -- 解碼 \tQ -- 退出程序\n");
fflush(stdin);
scanf("%c",&mode); //讓用戶繼續選擇相應的操作，直至用戶選擇退出
}
return 0;
}
⑻ 利用 數據結構 實現 哈夫曼編碼/解碼實現
//D:\2010 代碼\haffman\haffman\Node_statement.h
#define MAXVALUE 1000//定義最大權值
#define MAXBIT 100//定義哈夫曼樹中葉子結點個數
typedef struct
{
char data;//字元值
int num;//某個值的字元出現的次數
}TotalNode;
//統計結點，包括字元種類和出現次數
typedef struct
{
TotalNode tot[300];//統計結點數組
int num;//統計數組中含有的字元個數
}Total;
//統計結構體，包括統計數組和字元種類數
typedef struct
{
char mes[300];//字元數組
int num;//總字元數
}Message;
//信息結構體，包括字元數組和總字元數
typedef struct{
int locked[500];//密碼數組
int num;//密碼總數
}Locking;
//哈夫曼編碼後的密文信息
typedef struct
{
char data;//字元
int weight;//權值
int parent;//雙親結點在數組HuffNode[]中的序號
int lchild;//左孩子結點在數組HuffNode[]中的序號
int rchild;//右孩子結點在數組HuffNode[]中的序號
}HNodetype;
//哈夫曼樹結點類型，包括左右孩子，權值和信息
typedef struct
{
int bit[MAXBIT];
int start;
}HCodetype;
//哈夫曼編碼結構體，包括編碼數組和起始位
void reading_file(Message *message);//從文件中讀取信息
int writing_file(Message *message);//將信息寫進文件
void total_message(Message *message,Total *total);//統計信息中各字元的次數
void HaffmanTree(Total *total,HNodetype HuffNode[]);//構建哈夫曼樹
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//建立哈夫曼編碼
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total);//將編碼規則寫進文件
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking);//給文件信息加密編碼
void writing_lock(Locking *locking);//將已編碼信息寫進文件
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message);
void display(Total *total,HNodetype HuffNode[]);
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total);//將已編碼信息翻譯過來並寫進文
//D:\2010 代碼\haffman\haffman\function_mian.cpp
#include"Node_statement.h"
#include<iostream>
#include<fstream>
#include "cstdlib"
using namespace std;
int main()
{
int i,j,choice,mark=0;//mark標記文件信息是否讀入到內存中
HNodetype HuffNode[500];//保存哈夫曼樹中各結點信息
HCodetype HuffCode[300];
Locking *locking;
Total *total;
Message *message;
locking=new Locking;
locking->num=0;
total=new Total;
total->num=0;
message=new Message;
message->num=0;
//初始化變數
printf("┏ ┓\n");
printf("┣ haffman_code system ┫ \n");
printf("┗ ┛\n");
printf("\n\n");
choice=0;
while(choice!=7 )
{
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" 0:go \n");
printf("※********** 1：從文件讀取信息**********************※\n");
printf(" *********** 2：顯示編碼規則 ********************* \n");
printf(" ********** 3：將原文件信息寫進文件 ************ \n");
printf(" ********* 4：將編碼規則寫進文件 ************ \n");
printf(" ********** 5：將編碼後的信息寫進文件 ********** \n");
printf(" *********** 6：將解碼後的信息寫進文件 *********\n");
printf("※***********7：退出 *****************************※\n");
printf("＃〓§〓〓〓〓〓§〓〓〓〓§〓〓〓〓§〓＃ \n ");
printf(" please input the choice ");
cin>>choice;
switch(choice)
{
case 1:
reading_file(message);//從文件中讀取信息
mark=1;
break;
case 2://顯示編碼規則
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
cout<<"編碼規則為"<<endl;
for(i=0;i<total->num;i++)//顯示編碼規則
{
cout<<total->tot[i].data<<" ";
for(j=HuffCode[i].start+1;j<total->num;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
}
break;
case 3://將原文件信息寫進文件a_test1.txt
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
writing_file(message);//將信息寫進文件
break;
case 4://將編碼規則寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_HCode(HuffNode,HuffCode,total);//將編碼規則寫進文件
}
break;
case 5://將編碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_lock(locking);//將已編碼信息寫進文件
}
break;
case 6://將解碼後的信息寫進文件
if(mark==0)cout<<"請先從文件中讀取信息!"<<endl;
else
{
first_function(HuffNode,HuffCode,total,message);
writing_translate(locking,HuffCode,HuffNode,total);//將已編碼信息翻譯過來並寫進文件
}
break;
}
}
/**
列印haffman樹
**/
display(total,HuffNode);
system("PAUSE");
return 0;
}
void display(Total *total,HNodetype HuffNode[])
{
int i,j;
for(i=0;i<2*total->num-1;i++)
{
printf("data weight lchild rchild parent \n");
printf(" %c %d %d %d %d\n",HuffNode[i].data,HuffNode[i].weight,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].parent);
}
}
void reading_file(Message *message)
/**
絕對路徑下讀取a_test.txt file
message 中的num記錄suoyou字元總數 ，放在nes【】中
equal to the buffer
**/
{
int i=0;
char ch;
ifstream infile("a_test.txt",ios::in | ios::out);
if(!infile)//打開失敗則結束
{
cout<<"打開a_test.txt文件失敗"<<endl;
exit(1);
}
else
cout<<"讀取文件成功"<<endl;
while(infile.get(ch) && ch!='#')//讀取字元直到遇到#
{
message->mes[i]=ch;
i++;
}
message->num=i;//記錄總字元數
infile.close();//關閉文件
}
int writing_file(Message *message)
/**
把從數組message 的信息write to disk，a_test1.txt to save
**/
{ /*
int i;
ifstream outfile("a_test1.txt",ios::in ); //打開文件
if( !outfile )//打開失敗則結束
{
cout<<"打開a_test1.txt文件失敗"<<endl;
return -1;
}
for(i=0;i<message->num;i++)//寫文件
outfile.put(message->mes[i]);
cout<<"信息寫進文件成功"<<endl;
outfile.close();//關閉文件
return 0;*/
int i;
FILE *fp1=NULL;
if((fp1 = fopen("a_test1.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<message->num;i++)
fprintf(fp1,"%d ",message->mes[i]);
printf("文件寫入成功!\n");
i=fclose(fp1);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void total_message(Message *message,Total *total)
/**
統計message中不同字元 的個數，和相同字元重復的次數，重復字元用mark標記，
total.tot[] 放不同字元，TotalNode 類型（char，num）
total.num 統計不同字元個數
使total這塊內存空間有數據，
**/
{
int i,j,mark;
for(i=0;i<message->num;i++)//遍歷message中的所有字元信息
{
if(message->mes[i]!=' ')//字元不為空格時
{
mark=0;
for(j=0;j<total->num;j++)//在total中搜索當前字元
if(total->tot[j].data==message->mes[i])//搜索到，則此字元次數加1，mark標志為1
{
total->tot[j].num++;
mark=1;
break;
}
if(mark==0)//未搜索到，新建字元種類，保存進total中，字元類加1
{
total->tot[total->num].data=message->mes[i];
total->tot[total->num].num=1;
total->num++;
}
}
}
}
void HaffmanTree(Total *total,HNodetype HuffNode[])
/**create the haffman tree
不同字元個數為葉子節點個數對應書上的n，
相同字元的個數為其權值weight；
get HuffNode to store the tree
**/
{
int i,j,min1,min2,x1,x2;
for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼樹並存入葉子結點權值和信息
{
if(i<=total->num-1)
HuffNode[i].data=total->tot[i].data;
HuffNode[i].weight=total->tot[i].num;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
for(i=0;i<total->num-1;i++)
{
min1=min2=MAXVALUE;
x1=x2=0;
for(j=0;j<total->num+i;j++)//選取最小x1和次小x2的兩權值
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1)
{
min2=min1;
x2=x1;
min1=HuffNode[j].weight;
x1=j;
}
else
if(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)
{
min2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent=total->num+i;//修改親人結點位置
HuffNode[x2].parent=total->num+i;
HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[total->num+i].lchild=x1;//左孩子比右孩子權值小
HuffNode[total->num+i].rchild=x2;
}
}
void HaffmanCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/***
haffman to code (0,10,110,)
得到每個不同字元（葉子）的編碼，
存貯在數組HuffCode【】中,bit[] store the char,start store the loction
**/
{
int i,j,c,p;
HCodetype cd;
for(i=0;i<total->num;i++)//建立葉子結點個數的編碼
{
cd.start=total->num-1;//起始位初始化
p=HuffNode[i].parent;
c=i;
while(p!=-1)//從葉結點向上爬直到到達根結點
{
if(HuffNode[p].lchild==c)//左分支則為0
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;//右分支則為1
cd.start--;//起始位向前移動
c=p;
p=HuffNode[p].parent;
}
for(j=cd.start+1;j<total->num;j++)//保存求出的每個葉結點編碼和起始位
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
}
void writing_HCode(HNodetype HuffNode[],HCodetype HuffCode[],Total *total)
/**
HuffNode[]to input the leaf
HuffCode[]to input the code
all is to the a_test2.txt ,save the code
**/
{
/*打開HCode文件，失敗則結束。將信息寫進文件*/
int i,j;
FILE *fp2=NULL;
if((fp2 = fopen("a_test2.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)
{fprintf(fp2,"%d ",HuffNode[i].data);
printf(" ");
for(j=HuffCode[i].start+1;j<total->num;j++)
fprintf(fp2,"%d ",HuffCode[i].bit[j]);
}
printf("編碼規則寫進文件成功!\n");
i=fclose(fp2);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void lock(Message *message,HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Locking *locking)
/***
對messag操作，對所有字元加密，
結果存貯在數組locked[]中，locking 記錄已經加密後的密文
**/
{
int i,j,m;
for(i=0;i<message->num;i++)//把相同的不同的字元全部 遍歷
{
if(message->mes[i]==' ')//碰到空格則以-1形式保存進locked數組中
{
locking->locked[locking->num]=-1;
locking->num++;
}
else
for(j=0;j<total->num;j++)//從total中找到對應的字元
{
if(HuffNode[j].data==message->mes[i])
//找到在HuffNode 中對應字元，找到下標j
// 在HuffCode
for(m=HuffCode[j].start+1;m<total->num;m++)///////// !
{
locking->locked[locking->num]=HuffCode[j].bit[m];//加密
locking->num++;
}
}
}
}
void writing_lock(Locking *locking)
/*
將密文寫到a_test3.txt
*/
{
int i;
FILE *fp3=NULL;
if((fp3= fopen("a_test3.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<locking->num;i++)
{
if(locking->locked[i]==-1)
printf(" ");
else
fprintf(fp3,"%d ",locking->locked[i]);
}
printf("已編碼信息寫進文件成功!\n");
i=fclose(fp3);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void writing_translate(Locking *locking,HCodetype HuffCode[],HNodetype HuffNode[],Total *total)
/**
密文翻譯成明文，然後存到文件 a_test4.txt
**/
{
int i,j,mark[100],start[100],min,max;
FILE *fp4=NULL;
if((fp4 = fopen("a_test4.txt","at"))==NULL)
{
printf("can't open the file\n");
exit(0);
}
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;//。。。。
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
min=0;
for(max=0;max<locking->num;max++)//寫文件
{
if(locking->locked[max]==-1)//碰到空格信息則直接輸出空格
{
printf(" ");//把空格寫到文件
min++;
}
else
{
for(i=min;i<=max;i++)//查找從min開始到max的編碼對應的信息
{
for(j=0;j<total->num;j++)
{
if(start[j] == total->num+1)
mark[j]=0; //對應編碼比所給編碼短則不在比較
if(mark[j]==1&&locking->locked[i]==HuffCode[j].bit[start[j]])
start[j]++;
else
mark[j]=0;
}
}
for(i=0;i<total->num;i++)//找到對應信息，則寫進文件
{
if(mark[i]==1&&start[i]==total->num)
{
fprintf(fp4,"%d ",HuffNode[i].data);//寫到文件outfile
break;
}
}
if(i!=total->num)
min=max+1;
for(i=0;i<total->num;i++)//start數組初始化
{
start[i]=HuffCode[i].start+1;
}
for(i=0;i<total->num;i++)//mark數組初始化
{
mark[i]=1;
}
}
}
printf("文件寫入成功!\n");
i=fclose(fp4);
if(i==0)
printf("文件關閉成功!\n");
else
printf("文件關閉失敗!\n");
}
void first_function(HNodetype HuffNode[],HCodetype HuffCode[],Total *total,Message *message)
{
total_message(message,total);//統計信息中各字元的出現次數
HaffmanTree(total,HuffNode);//構建哈夫曼樹
HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼編碼
}
⑼ 在VC6.0下編的程序報錯 cannot open file '.\Debug\StdAfx.sbr': No such file or directory
有如下幾種解決辦法:1.把release文件夾刪掉,重新編譯2.如果你有以前編譯好的,找個StdAfx.sbr文件放到debug下.如果沒有,你另存工程編譯.3.打個sp6補丁
⑽ 哈夫曼樹及哈夫曼編碼解碼的實現（根據程序畫流程圖及對每句程序注釋）
這是以前寫的，可是我不想加註釋了，Huffman編碼其實原理很簡單的，你自己好好學下吧，一句一句注釋也太誇張了啊。
#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==0)
{s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(HT[j].parent==0)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
{
if(HT[i].parent==0)
if(HT[s1].weight>HT[i].weight)
if(s2!=i)
s1=i;
}
for(j=1;j<=n;j++)
{
if(HT[j].parent==0)
if(HT[s2].weight>HT[j].weight)
if(s1!=j)
s2=j;
}
if(s1>s2)
{
int temp=s1;
s1=s2;
s2=temp;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int i,j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
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;
}
//添加查看，便於調試
printf("構造過程顯示：\n");
for(i=1;i<=m;i++)
printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild);
system("pause");
for(i=n+1;i<=m;i++)
{
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("s1=%d,s2=%d\n",s1,s2);
for(j=1;j<=i;j++)
printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
system("pause");
*/
}
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=0;
p=HT[p].parent;
--cdlen;
}
}
}
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("請輸入節點數：\n");
scanf("%d",&n);
HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode));
w=(int *)malloc(n*sizeof(int));
printf("請輸入節點的權值：\n");
for(i=0;i<n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
printf("輸出編碼：\n");
for(i=1;i<=n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
return 0;
system("pause");
}