Ⅰ 怎樣使用哈夫曼樹編寫一段程序實現對信息編碼的壓縮我要代碼,謝謝了!
/**********************************************************************
*Name:哈夫曼編碼源代碼
*實現過程:著先通過HuffmanTree()函數構造哈夫曼樹,然後在主函數main()中
*自底向上開始(也就是從數組序號為零的結點開始)向上層層判斷,若在
*父結點左側,則置碼為0,若在右側,則置碼為1。最後輸出生成的編碼。
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#defineMAXBIT100
#defineMAXVALUE10000
#defineMAXLEAF30
#defineMAXNODEMAXLEAF*2-1
typedef侍跡struct
{
intbit[MAXBIT];
intstart;
}HCodeType;/*編碼結構體*/
typedefstruct
{
intweight;
intparent;
int敬談或lchild;
intrchild;
intvalue;
}HNodeType;/*結點結構體*/
/*構造一顆哈夫曼樹*/
voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn)
{
/*i、j:循環變數,m1、m2:構造哈夫曼樹不同過亮伍程中兩個最小權值結點的權值,
x1、x2:構造哈夫曼樹不同過程中兩個最小權值結點在數組中的序號。*/
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼樹數組HuffNode[]中的結點*/
for(i=0;i<2*n-1;i++)
{
HuffNode[i].weight=0;//權值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;//實際值,可根據情況替換為字母
}/*endfor*/
/*輸入n個葉子結點的權值*/
for(i=0;i<n;i++)
{
printf("Pleaseinputweightofleafnode%d: ",i);
scanf("%d",&HuffNode[i].weight);
}/*endfor*/
/*循環構造Huffman樹*/
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;/*m1、m2中存放兩個無父結點且結點權值最小的兩個結點*/
x1=x2=0;
/*找出所有結點中權值最小、無父結點的兩個結點,並合並之為一顆二叉樹*/
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}/*endfor*/
/*設置找到的兩個子結點x1、x2的父結點信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
printf("x1.weightandx2.weightinround%d:%d,%d ",i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用於測試*/
printf(" ");
}/*endfor*/
/*for(i=0;i<n+2;i++)
{
printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d ",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
}*///測試
}/*endHuffmanTree*/
//解碼
voiddecodeing(charstring[],HNodeTypeBuf[],intNum)
{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024];
for(i=0;i<strlen(string);i++)
{
if(string[i]=='0')
num[i]=0;
else
num[i]=1;
}
i=0;
nump=&num[0];
while(nump<(&num[strlen(string)]))
{tmp=m-1;
while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
{
if(*nump==0)
{
tmp=Buf[tmp].lchild;
}
elsetmp=Buf[tmp].rchild;
nump++;
}
printf("%d",Buf[tmp].value);
}
}
intmain(void)
{
HNodeTypeHuffNode[MAXNODE];/*定義一個結點結構體數組*/
HCodeTypeHuffCode[MAXLEAF],cd;/*定義一個編碼結構體數組,同時定義一個臨時變數來存放求解編碼時的信息*/
inti,j,c,p,n;
charpp[100];
printf("Pleaseinputn: ");
scanf("%d",&n);
HuffmanTree(HuffNode,n);
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1)/*父結點存在*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;/*求編碼的低一位*/
c=p;
p=HuffNode[c].parent;/*設置下一循環條件*/
}/*endwhile*/
/*保存求出的每個葉結點的哈夫曼編碼和編碼的起始位*/
for(j=cd.start+1;j<n;j++)
{HuffCode[i].bit[j]=cd.bit[j];}
HuffCode[i].start=cd.start;
}/*endfor*/
/*輸出已保存好的所有存在編碼的哈夫曼編碼*/
for(i=0;i<n;i++)
{
printf("%d'sHuffmancodeis:",i);
for(j=HuffCode[i].start+1;j<n;j++)
{
printf("%d",HuffCode[i].bit[j]);
}
printf("start:%d",HuffCode[i].start);
printf(" ");
}
printf("Decoding?PleaseEntercode: ");
scanf("%s",&pp);
decodeing(pp,HuffNode,n);
getch();
return0;
}
Ⅱ 哈夫曼樹
轉自: http://blog.csdn.net/hikvision_java_gyh/article/details/8952596
哈夫曼樹又稱最優二叉樹,是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度,就是樹中所有的葉結點的權值乘上其到根結點的路徑長度(若根結點為0層,葉結點到根結點的路徑長度為葉結點的層數)。樹的帶權路徑長度記為WPL=(W1 L1+W2 L2+W3 L3+...+ Wn Ln),N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹,相應的葉結點的路徑長度為Li(i=1,2,...n)。可以證明哈夫曼樹的WPL是最小的。【例】給定4個葉子結點a,b,c和d,分別帶權7,5,2和4。構造如下圖所示的三棵二叉樹(還有許多棵),它們的帶權路徑長度分別為: (a)WPL=7 2+5 2+2 2+4 2=36 (b)WPL=7 3+5 3+2 1+4 2=46 (c)WPL=7 1+5 2+2 3+4 3=35其中(c)樹的WPL最小,可以驗證,它就是哈夫曼樹。
構造哈夫曼樹的演算法如下: 1)對給定的n個權值{W1,W2,W3,...,Wi,...,Wn}構成n棵二叉樹的初始集合F={T1,T2,T3,...,Ti,..., Tn},其中每棵二叉樹Ti中只有一個權值為Wi的根結點,它的左右子樹均為空。 2)在F中選取兩棵根結點權值最小的樹作為新構造的二叉樹的左右子樹,新二叉樹的根結點的權值為其左右子樹的根結點的權值之和。 3)從F中刪除這兩棵樹,並把這棵新的二叉樹同樣以升序排列加入到集合F中。 4)重復2)和3),直到集合F中只有一棵二叉樹為止。 例如,對於4個權值為1、3、5、7的節點構造一棵哈夫曼樹,其構造過程如下圖所示:
可以計算得到該哈夫曼樹的路徑長度WPL=(1+3) 3+2 5+1*7=26。
哈夫曼編碼應用 大數據 量的圖像信息會給存儲器的存儲容量,通信干線信道的帶寬,以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量,提高信道帶寬以及計算機的處理速度等方法來解決這個問題是不現實的,這時就要考慮壓縮。壓縮的關鍵在於編碼,如果在對數據進行編碼時,對於常見的數據,編碼器輸出較短的碼字;而對於少見的數據則用較長的碼字表示,就能夠實現壓縮。【例】:假設一個文件中出現了8種符號S0,SQ,S2,S3,S4,S5,S6,S7,那麼每種符號要編碼,至少需要3bit。假設編碼成 000,001, 010,011,100,101,110,111。那麼符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼後變成 ,共用了42bit。我們發現S0,S1,S2這3個符號出現的頻率比較大,其它符號出現的頻率比較小,我們採用這樣的編碼方案:S0到S7的碼遼分別01,11,101,0000,0001,0010,0011, 100,那麼上述符號序列變成,共用了39bit。盡管有些碼字如 S3,S4,S5,S6變長了(由3位變成4位),但使用頻繁的幾個碼字如S0,S1變短了,所以實現了壓縮。對於上述的編碼可能導致解碼出現非單值性:比如說,如果S0的碼字為01,S2的碼字為011,那麼當序列中出現011時,你不知道是S0的碼字後面跟了個1,還是完整的一個S2的碼字。因此,編碼必須保證較短的編碼決不能是較長編碼的前綴。符合這種要求的編碼稱之為前綴編碼。要構造符合這樣的二進制編碼體系,可以通過二叉樹來實現。以下是哈夫曼樹的 Java 實現:
[java] view plain
// 二叉樹節點
public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } public int compareTo(Object o) { Node that = (Node) o; double result = this.value - that.value; return result > 0 ? 1 : result == 0 ? 0 : -1; } }
private static Node build(List<Node> nodes) {
nodes = new ArrayList<Node>(nodes);
sortList(nodes);
while (nodes.size() > 1) {
createAndReplace(nodes);
}
return nodes.get(0);
}
/**
/**
private static void sortList(List<Node> nodes) {
Collections.sort(nodes);
}
`
/**
Ⅲ 如何用哈夫曼編碼實現英文文本的壓縮和解壓縮
哈夫曼壓縮是個無損的壓縮演算法,一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號(例如,文本文件中的字元)用一個特定長度的位序列替代。因此,在文件中出現頻率高的符號,使用短的位序列,而那些很少出現的符號,則用較長的位序列。有人用C函數寫了這個編碼,見下面鏈接
http://ke..com/view/189694.htm
Ⅳ 哈夫曼實現壓縮
我的作業,哈弗曼樹的建立,不過那個字元的頻率要自己編的。
//main.cpp
#include"HuffmanTree.h"
#include<string.h>
#include<stdlib.h>
//#include<iostream>
//using namespace std;
int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n\n**********************歡迎使用哈夫曼編碼/解碼系統**********************\n"<<endl<<endl;
cout<<" 您可以進行以下操作:\n";
cout<<" 1 建立哈夫曼樹\n";
cout<<" 2 編碼(源文已在文件ToBeTran中,或鍵盤輸入)\n";
cout<<" 3 解碼(碼文已在文件CodeFile中)\n";
cout<<" 4 顯示碼文\n";
cout<<" 5 顯示哈夫曼樹\n";
cout<<" 6 退出\n\n";
cout<<" 請選擇一個操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感謝使用本系統!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
//Huffmannode.h
#ifndef _HuffmanNode_
#define _HuffmanNode_
struct HuffmanNode
{
int weight; //存放結點的權值,假設只考慮處理權值為整數的情況
int parent; //-1表示為根結點,否則表示為非根結點
int lchild,rchild; //分別存放該結點的左右孩子的所在單元的編號
};
#endif
//huffmantree.h
#ifndef _HuffmanTree_
#define _HuffmanTree_
#include"HuffmanNode.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
class HuffmanTree //哈夫曼樹
{
public:
struct HuffmanNode *Node; //Node[]存放哈夫曼樹
char *Info; //Info[]存放源文用到的字元——源碼,如'a','b','c','d','e',此內容可以放入結點中,不單獨設數組存放
int LeafNum; //哈夫曼樹的葉子個數,也是源碼個數
public:
HuffmanTree();
~HuffmanTree();
void CreateHuffmanTree(); /*在內存中建立哈夫曼樹,存放在Node[]中。 讓用戶從兩種建立哈夫曼樹的方法中選擇:
1.從鍵盤讀入源碼字元集個數,每個字元,和每個字元的權重,建立哈夫曼樹,
並將哈夫曼樹寫入文件hfmTree中。2.從文件hfmTree中讀入哈夫曼樹信息,建立哈夫曼樹*/
void CreateHuffmanTreeFromKeyboard();
void CreateHuffmanTreeFromFile();
void Encoder(); /*使用建立好的哈夫曼樹(如果不在內存,則從文件hfmTree中讀入並建立內存里的哈夫曼樹),
對文件ToBeTran中的正文進行編碼,並將碼文寫入文件CodeFile中。
ToBeTran的內容可以用記事本等程序編輯產生。*/
void Decoder(); /*待解碼的碼文存放在文件CodeFile中,使用建立好的哈夫曼樹(如果不在內存,
則從文件hfmTree中讀入並建立內存里的哈夫曼樹)將碼文解碼,
得到的源文寫入文件TextFile中,並同時輸出到屏幕上。*/
void PrintCodeFile(); /*將碼文文件CodeFile顯示在屏幕上*/
void PrintHuffmanTree(); /*將哈夫曼樹以直觀的形式(凹入表示法,或廣義表,或其他樹形表示法)顯示在屏幕上,
同時寫入文件TreePrintFile中*/
void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法顯示哈夫曼樹,由PrintHuffmanTree()調用*/
};
#endif
//huffmantree.cpp
#include"HuffmanTree.h"
#include<string>
#include<limits> //為使用整型最大值
//#include<iostream>
using namespace std;
//******************************************************
HuffmanTree::HuffmanTree()
{
LeafNum=0;
Node=NULL;
Info+NULL;
}
//******************************************************
HuffmanTree::~HuffmanTree()
{
delete []Node;
Node=NULL;
delete []Info;
Info=NULL;
}
//******************************************************
void HuffmanTree::CreateHuffmanTree()
{
char Choose;
cout<<"你要從文件中讀入哈夫曼樹(按1),還是從鍵盤輸入哈夫曼樹(按2)?";
cin>>Choose;
if(Choose=='2') {//鍵盤輸入建立哈夫曼樹
CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
}
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromKeyboard()
{
int Num;
int i,j,pos1,pos2,max1,max2;
cout<<"\n請輸入源碼字元集個數:";
cin>>Num;
if (Num<=1)
{
cout<<"無法建立少於2個葉子結點的哈夫曼樹。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
Info=new char[2*Num-1];
for( i=0;i<Num;i++) {//讀入哈夫曼樹的葉子結點信息
cout<<"請輸入第"<<i+1<<"個字元值";
getchar();
Info[i]=getchar(); //源文的字元存入字元數組Info[]
getchar();
cout<<"請輸入該字元的權值或頻度";
cin>>Node[i].weight; //源文的字元權重存入Node[].weight
Node[i].parent=-1; //為根結點
Node[i].lchild=-1; //無左孩子
Node[i].rchild=-1; //無右孩子
}
for( i=Num;i<2*Num-1;i++) //循環建立哈夫曼樹內部結點 表示需做Num-1次合並
{
pos1=-1;pos2=-1; //分別用來存放當前最小值和次小值的所在單元編號
max1=32767; max2=32767; //32767為整形數的最大值 分別用來存放當前找到的最小值和次小值
for(j=0;j<i;j++) //在根結點中選出權值最小的兩個
{
if(Node[j].parent==-1) //是否為根結點
if(Node[j].weight<max1) //是否比最小值要小
{
max2=max1; //原最小值變為次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在的單元編號
pos1=j; //修改最小值所在的單元編號
}
else
if(Node[j].weight<max2) //比原最小值大但比原此小值小
{
max2=Node[j].weight;
pos2=j;
}
}
Node[pos1].parent=i;
Node[pos2].parent=i;
Node[i].lchild=pos1;
Node[i].rchild=pos2;
Node[i].parent=-1;
Node[i].weight=Node[pos1].weight+Node[pos2].weight;
} //for
LeafNum=Num;
cout<<"哈夫曼樹已成功構造完成。\n";
//把建立好的哈夫曼樹寫入文件hfmTree.dat
char ch;
cout<<"是否要替換原來的哈夫曼樹文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打開文件
if(fop.fail()) {
cout<<"\n哈夫曼樹文件打開失敗,無法將哈夫曼樹寫入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先寫入哈夫曼樹的葉子結點個數
for( i=0;i<Num;i++) { //再寫入源文字元集的所有字元(存儲在Info[]中)
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for( i=0;i<2*Num-1;i++) { //最後寫入哈夫曼樹的各個結點(存儲在Node[]中)
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //關閉文件
cout<<"\n哈夫曼樹已成功寫入hfmTree.dat文件。\n";
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromFile()
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼樹文件hfmTree.dat打開失敗,無法建立哈夫曼樹。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼樹文件中的數據有誤,葉子結點個數少於2個,無法建立哈夫曼樹。\n";
fip.close();
return;
}
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for( int i=0;i<LeafNum;i++)
fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼樹已成功構造完成。\n";
}
//******************************************************
void HuffmanTree::Encoder()
{
if(Node==NULL) //內存沒有哈夫曼樹,則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}//if
char *SourceText; //字元串數組,用於存放源文
//讓用戶選擇源文是從鍵盤輸入,還是從源文文件ToBeTran.txt中讀入
char Choose;
cout<<"你要從文件中讀入源文(按1),還是從鍵盤輸入源文(按2)?";
cin>>Choose;
if(Choose=='1')
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail())
{
cout<<"源文文件打開失敗!無法繼續執行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次讀文件只統計文件中有多少個字元,將字元數存入k
fip1.close();
SourceText=new char[k+1]; //申請存放源文的字元數組空間
ifstream fip2("ToBeTran.txt");//第二次讀源文文件,把內容寫入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
cout<<"需編碼的源文為:";
cout<<SourceText<<endl;
}
else { //從鍵盤輸入源文
string SourceBuff;
cin.ignore();
cout<<"請輸入需要編碼的源文(可輸入任意長,按回車鍵結束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
ofstream fop("CodeFile.dat",ios::trunc); //打開碼文存放文件
char *code;
code=new char[LeafNum]; //存放一個源文字元的編碼
int k=0;
int i,j,start;
while(SourceText[k]!='\0') //源文串中從第一個字元開始逐個編碼
{
start=0;
for(i=0;i<LeafNum;i++)
if(Info[i]==SourceText[k]) //求出該文字所在單元的編號
break;
j=i;
while(Node[j].parent!=-1) //結點j非根
{
j=Node[j].parent; //求結點j的雙親結點
if(Node[j].lchild==i) //是左子樹,則生成代碼0
code[start++]='0';
else
code[start++]='1'; //是右子樹,則生成代碼1
i=j;
}
code[start]='\0'; //置串結束符
for(i=0;i<start/2;i++)
{
j=code[i];
code[i]=code[start-1-i];
code[start-1-i]=j;
}
i=0; //將源文的當前字元的對應編碼寫入碼文文件
while(code[i]!='\0')
{
fop<<code[i];
i++;
}
k++; //源文串中的字元後移一個
}
fop.close();
cout<<"已完成編碼,碼文已寫入文件CodeFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::Decoder()
{
//如果內存沒有哈夫曼樹,則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
//將碼文從文件CodeFile.dat中讀入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail())
{
cout<<"沒有碼文,無法解碼。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch))
{
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"經解碼得到的源文為:";
ofstream fop("TextFile.dat");
int j=(LeafNum-1)*2; //j指向哈夫曼樹的根
int i=0; //碼文從第一個符號開始,順著哈夫曼樹由根下行,按碼文的當前符號決定下行到左孩子還是右孩子
while(CodeStr[i]!='\0') //下行到哈夫曼樹的葉子結點處,則譯出葉子結點對應的源文字元
{
if(CodeStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到達葉子結點
{
cout<<Info[j]; //輸出葉子結點對應的字元
j=LeafNum*2-1-1; //表示重新從根結點開始往下搜索
}
i++;
}
fop.close();
cout<<"\n解碼成功且已存到文件TextFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"沒有碼文文件,無法顯示碼文文件內容。\n";
return;
}
while(fip.get(ch))
{
cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
//******************************************************
void HuffmanTree::PrintHuffmanTree()
{
//如果內存沒有哈夫曼樹,則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
//******************************************************
void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer)//凹入表示法
{
if(Node[T].lchild!=-1)
PrintHuffmanTree_aoru(Node[T].lchild,layer+1);//左子樹
for(int i=1;i<=layer;i++)// 根
cout<<'\0'<<'\0'<<'\0';
cout<<Node[T].weight<<endl;
if(Node[T].rchild!=-1)
PrintHuffmanTree_aoru(Node[T].rchild,layer+1); // 右子樹
}
Ⅳ 求助:用java實現哈夫曼編碼壓縮與解壓縮演算法。
你好,由於內容比較多,先概述一下先。如圖所示,為我寫的一個壓縮軟體,原理是利用哈弗曼演算法實現的。我將資料整理好稍後就發到你郵箱,但在這里簡要說明一下代碼。
請看我的空間
http://hi..com/%D2%B6%BF%C6%C1%BC/blog
中的文章共5篇(太長了)
http://hi..com/%D2%B6%BF%C6%C1%BC/blog/item/93c35517bb528146f2de32fd.html
1.HuffmanTextEncoder類完成壓縮功能,可直接運行,壓縮測試用文本文件。
2.HuffmanTextDecoder類完成解壓縮功能,可直接運行,解壓縮壓縮後的文本文件。
3.BitReader,工具類,實現對BufferedInputStream的按位讀取。
4.BitWriter,工具類,實現按位寫入的功能。該類來自網路。
5.MinHeap<T>,模板工具類,實現了一個最小堆。生成Huffman樹時使用。
Ⅵ (哈夫曼壓縮)將01字元串轉換為二進制文件的方法
//你沒說什麼語言!如果需要其它的話,我再翻譯一下滑老!
//沒什麼效率,但是滿足需求了
importjava.io.*;
publicclassZ{
publicstaticvoidmain(String[]args)throwsException{
//System.out.println(decode(encode("00001000")));
//System.out.println(decode(encode("11111000")));
writeHuffman("011");
System.out.println(read()Huffman());
}
//每次傳進去的字元串都是8個字元長度,剛好能夠表示一個byte
publicstaticbyteencode(Strings){
inta=0;
for(inti=0;i<8;i++){
charch=s.charAt(i);
a=a<<信塌升1;
if(ch=='1'){
a=a|0x1;
}
}
return(byte)a;
}
//上一步的逆操作
publicstaticStringdecode(byteb){
StringBuildersb=newStringBuilder();
for(inti=0;i<8;i++){
sb.append((b&(0x1<<(7-i)))>0?'1':'0');
}
returnsb.toString();
}
//再寫一下文件操作
//假設你已經得到了通過huffman樹編碼的字元串,那麼就這樣寫寫入文件
publicstaticvoidwriteHuffman(Strings)throwsException{
//因為huffman編碼字元串不總是8個字元的倍數,那麼我們不足8時補0,並記錄我們到底補了幾個。
//我們把補位數放在文件的第一個位元組
int衫賣z=8-s.length()%8;
if(z==8){
z=0;
}
byte[]buffer=newbyte[1024];
buffer[0]=(byte)z;
intpos=1,nBytes=(int)(Math.ceil(s.length()/((double)8)));
Filef=newFile("test.huffman");
FileOutputStreamos=newFileOutputStream(f);
for(inti=0;i<nBytes;i++){
Stringss;
if(s.length()>=(i+1)*8){
ss=s.substring(i*8,(i+1)*8);
}else{
ss=s.substring(i*8);
while(ss.length()<8){
ss=newStringBuilder(ss).append('0').toString();
}
}
buffer[pos]=encode(ss);
pos++;
if(pos==1024){
os.write(buffer);
pos=0;
}
}
if(pos>0){
os.write(buffer,0,pos);
}
os.close();
}
//我們把壓縮過的文本放在test.huffman裡面
publicstaticStringreadHuffman()throwsException{
Filef=newFile("test.huffman");
FileInputStreamfs=newFileInputStream(f);
byte[]buffer=newbyte[1024];
intlen=0;
StringBuildersb=newStringBuilder();
bytez=(byte)fs.read();
while((len=fs.read(buffer))!=-1){
for(inti=0;i<len;i++){
sb.append(decode(buffer[i]));
}
}
fs.close();
returnsb.substring(0,sb.length()-z);
}
}
c++ 版本
#include"stdafx.h"
#include<stdio.h>
#include<iostream>
#include<string>
#include<cmath>
usingnamespacestd;
unsignedcharencode(constchar*s){
inta=0;
for(inti=0;i<8;i++){
if(s[i]=='1'){
a=a|(0x1<<(7-i));
}
}
return(unsignedchar)a;
}
voiddecode(unsignedchara,char*buf){
for(inti=0;i<8;i++){
buf[i]=(((a>>(7-i))&0x1)!=0)?'1':'0';
}
}
voidwriteHuffman(conststring&s){
unsignedcharz=8-s.length()%8;
if(z==8){
z=0;
}
unsignedcharbuffer[1024];
buffer[0]=z;
intpos=1,nBytes=(int)(ceil(s.length()/((double)8)));
constchar*ps=s.c_str();
FILE*fp=fopen("test.huffman","wb");
charextended[8];
for(inti=0;i<nBytes;i++){
constchar*p;
if(s.length()>=(i+1)*8){
p=ps+i*8;
}
else{
char*pp=extended;
for(intj=i*8;j<s.length();j++){
*pp=s[j];
pp++;
}
for(intj=0;j<z;j++){
*pp='0';
pp++;
}
p=extended;
}
buffer[pos]=encode(p);
pos++;
if(pos==1024){
fwrite(buffer,sizeof(unsignedchar),1024,fp);
pos=0;
}
}
if(pos>0){
fwrite(buffer,sizeof(unsignedchar),pos,fp);
}
fclose(fp);
}
string&readHuffman(){
FILE*fp=fopen("test.huffman","rb");
fseek(fp,0L,SEEK_END);
size_tfileSize=ftell(fp);
rewind(fp);
unsignedcharbuffer[1024];
fread(buffer,sizeof(unsignedchar),1,fp);
unsignedcharz=buffer[0];
size_tstringSize=(fileSize-1)*8;
char*ptr=newchar[stringSize+1];
char*optr=ptr;
size_tlen;
while((len=fread(buffer,sizeof(unsignedchar),1024,fp))!=0){
for(inti=0;i<len;i++){
decode(buffer[i],ptr);
ptr=ptr+8;
}
}
fclose(fp);
ptr=ptr-z;
*ptr='