⑴ 哈夫曼樹HT存儲結構的初態和末態怎麼寫
定義哈夫曼樹與編碼的存儲結構與數據類型
typedef struct
{
char data;//節點值
int weight; //權重
int parent; //雙親節點
int lchild; //左孩子節點
int rchild; //右孩子節點
} HTNode;
typedef struct
{
char cd[N]; //存放哈夫曼碼
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //創建哈夫曼樹
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根據哈夫曼樹計算每個元素的哈夫曼編碼
void DispHCode(HTNode ht[],HCode hcd[],int n) //輸出每個元素的哈夫曼編碼
⑵ 關於哈弗曼樹
這是我們的作業題，自己寫 的……（可能輸入的格式跟你要的不一致，自己改一下）
如果有什麼不懂的就問我，我可以把其中所有相關的文件發給你 ^^
註：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);
}
}
⑶ 哈夫曼樹的建立
給你個大概的代碼，把顯示跟調用那裡改改#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<iostream.h> typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild,ch;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表 int m,s1,s2;
HuffmanTree HT;void Select(int n){ //選擇兩個權值最小的結點
int i,j;
for(i=1;i<=n;i++){
if(!HT[i].parent){
s1 = i;break;
}
}
for(j=i+1;j<=n;j++){
if(!HT[j].parent){
s2 = j;break;
}
}
for(i=1;i<=n;i++){
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i)){
s1=i;
}
}
for(j=1;j<=n;j++){
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j)){
s2=j;
}
}
} void HuffmanCoding(HuffmanCode HC[], int *w, int n) {
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;
int start;if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) {//初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].ch=0;
}
for (i=n+1; i<=m; i++) {//初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].ch=0;
}
for (j=1,i=n+1; i<=m; i++,j++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2
Select(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;
HT[i].ch=j;
}//-----從葉子到根逆向求每個字元的哈夫曼編碼
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i){
start=n-1;
HT[i].ch=i;
for(unsigned int 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);
}
void PTree(int n){//列印樹的結構
int r=2*n-1;
printf("樹的結構為（0表示無孩子）：\n");
for(;r>0;r--){
cout<<HT[r].lchild<<"<--"<<r<<"-->"<<HT[r].rchild<<endl;
}
}void trans(){//解碼
int i=m;
char a;
printf("輸入0/1進行解碼，輸入'!'進行編碼");
cin>>a;
while(a=='0'||a=='1'){
if(a=='0')i=HT[i].lchild;
else if(a=='1') i=HT[i].rchild;
if(HT[i].lchild==0){
cout<<(char)(HT[i].ch+64);
i=m;
}
else if(a=='!') return;//當接收到的輸入為"!"時返回主函數進行編碼
cin>>a;
}
}void main() {
HuffmanTree HT;
HuffmanCode *HC;
int *w,n,i,j;
char b,c;
puts("輸入結點數：");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i=0;i<n;i++){
scanf("%d",&w[i]);
}
HuffmanCoding(HC,w,n);
puts("\n各結點的哈夫曼編碼為：");
for(i=1;i<=n;i++){
c=(char)i+64;
cout<<c<<'('<<w[i-1]<<')'<<HC[i]<<endl;
}
PTree(n);
printf("\n各結點的哈夫曼解碼為：\n");
trans();
cout<<"請輸入源碼：";//從trans函數返回進行編碼
cin>>b;
j=(int)(b-64);
while(j){
cout<<HC[j];
cin>>b;
j=(int)(b-64);
}
cout<<endl;
system("pause");
}
⑷ 關於哈夫曼樹的一題，望給出詳細解釋，感激不盡！在線等
（1）構造哈夫曼樹：從備選節點中挑出兩個權值最小的節點進行構造，構造完成後會生成新的節點（權值為和）放入備選節點中，重復操作
（2）構造哈夫曼樹後，往左節點的路徑為0往右為1，從根節點順著路徑到葉子，把路徑上的0和1組合起來得到哈夫曼編碼
（3）一個字元的編碼的長度就是佔用的二進制位數，8位為一個位元組，根據出現次數和總字元數計算得到位元組數
（4）根據（2）得到的編碼，從左到右對應就行了
⑸ 哈夫曼樹及哈夫曼編碼的C程序實現(數據結構題)
去年做的課程設計，有什麼不合要求的自己改改
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動態分配數組存儲哈夫曼樹
typedef char *HuffmanCode; //動態分配數組存儲哈夫曼編碼表
void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 演算法6.13
// w存放n個字元的權值(均>0)，構造哈夫曼樹HT，
// 並求出n個字元的哈夫曼編碼HC
int i, j;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0號單元未用
for (i=1; i<=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
puts("\n哈夫曼樹的構造過程如下所示：");
printf("HT初態:\n 結點 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼樹
// 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
// 其序號分別為s1和s2。
Select(HT, i-1);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 結點 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意鍵，繼續 ...");
getchar();
}
//------無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼
cd = (char *)malloc(n*sizeof(char)); // 分配求編碼的工作空間
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍歷哈夫曼樹時用作結點狀態標志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登記葉子結點的字元的編碼
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 復制編碼(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父結點，編碼長度減1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("輸入結點數:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("輸入%d個結點的權值\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n各結點的哈夫曼編碼:");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}