實驗四哈夫曼樹及其的應用
一、實驗目的
1．在二叉樹基本操作的基礎上，掌握對二叉樹的一些其它操作的具體實現方法。
2.掌握構造哈夫曼樹以及哈夫曼編碼的方法。
3、熟練掌握哈夫曼樹（最優二叉樹）特徵及其應用
二、實驗內容
哈夫曼樹和哈夫曼編碼：
從終端輸入若干個字元，統計（或指定）字元出現的頻率，將字元出現的頻率作為結點的權值，建立哈夫曼樹，然後對各字元進行哈夫曼編碼。最後列印哈夫曼樹和對應的哈夫曼編碼。
三、具體實現
①統計字元出現的頻率
建立結構體陣列，結點如下：
struct frequence//統計頻率
;其中a存放字元，而n存放該字元出現的次數，即權值。
具體統計實現如下：
frequence ch[27];//26個英文本母，0號位置不儲存字元，用來儲存總共的字元個數,多次出現的只記一次
int i=0;
for(;i<=26;i++)//初始化結構體陣列
cout<<"請輸入各個字元（輸入#鍵結束輸入）：";
char c;
cin>>c;
bool flag;
while(c!='#')
if(flag)//已存在
else//不存在
cin>>c;
}②根據字元出現的頻率建立哈夫曼樹
建立哈夫曼樹時需要每次求出權值最小且無雙親結點的結點，實現如下：
void select(huffman t,int n,int &m1,int &m2)//選擇parent不為0且weight最小的兩個結點,m1最小，m2次小
}for(k++;k<=n;k++)
}if(t[m1].weight>t[m2].weight)
for(k=1;k<=n;k++)
}}每次選出兩個數之後，建立哈夫曼樹：
for(i=ch[0].n+1;i<=2*ch[0].n-1;i++)
③ 對哈夫曼樹進行編碼
huffmancode hc;
hc=(huffmancode)malloc((ch[0].n+1)*sizeof(char*));
char *cd;
cd=(char *)malloc(ch[0].n*sizeof(char));
cd[ch[0].n-1]='\0';
for(i=1;i<=ch[0].n;i++)
}free(cd);
四、源程式**
#include<>
#include<>
#include<>
#include<>
struct frequence//統計頻率
;typedef struct
htnode,*huffman;
typedef char * *huffmancode;//動態分配陣列儲存哈夫曼編碼
void select(huffman t,int n,int &m1,int &m2)//選擇parent不為0且weight最小的兩個結點,m1最小，m2次小
}for(k++;k<=n;k++)
}if(t[m1].weight>t[m2].weight)
for(k=1;k<=n;k++)
}}void main()
cout<<"請輸入各個字元（輸入#鍵結束輸入）：";
char c;
cin>>c;
bool flag;
while(c!='#')
if(flag)//已存在
else//不存在
cin>>c;
}cout< for(int j=1;j<=ch[0].n;j++)
huffman t;
t=(huffman)malloc((2*ch[0].n)*sizeof(htnode));//ch[0].n個葉子結點需要2*ch[0].
n-1個結點空間，多分配乙個空間，0號位置不儲存 0-2*ch[0].n-1
for(i=1;i<=2*ch[0].n-1;i++)//初始化結點(靜態，用結構體陣列實現)
t[0].weight=ch[0].n;//0號位置儲存總共建立的結點數
int m1,m2;//m1,m2分別儲存最小和次小權值的下標
for(i=ch[0].n+1;i<=2*ch[0].n-1;i++)
cout<<"\n用陣列表示哈夫曼數如下"< cout< for(i=1;i<=2*ch[0].n-1;i++)
huffmancode hc;
hc=(huffmancode)malloc((ch[0].n+1)*sizeof(char*));
char *cd;
cd=(char *)malloc(ch[0].n*sizeof(char));
cd[ch[0].n-1]='\0';
for(i=1;i<=ch[0].n;i++)
{int start=ch[0].n-1;
for(int c=i,f=t[i].parent;f!=0;c=f,f=t[f].parent)
{if(t[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
hc[i]=(char *)malloc((ch[0].n-start)*sizeof(char));
哈弗曼樹實習報告
實習報告 三 題目 哈弗曼編解碼器 班級 計算機 班姓名 史丹丹學號 09052204 完成日期 2011.1.3 1 需求分析 1 i 初始化。從終端讀入字符集大小n，已經n個字元和n個權值，建立哈弗曼樹，並將它存於檔案hlfmtree中。2 e 編碼。利用已經建好的哈弗曼樹對檔案tobetran...
資料結構哈夫曼樹編碼解碼課程設計實驗報告
資料結構課程設計 設計題目 哈夫曼樹編碼解碼 目錄在當今資訊 時代，如何採用有效的資料壓縮技術節省資料檔案的儲存空間和計算機網路的傳送時間已越來越引起人們的重視，哈夫曼編碼正是一種應用廣泛且非常有效的資料壓縮技術。哈夫曼編碼是一種編碼方式，以哈夫曼樹 即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用...
實驗四哈夫曼樹及其的應用
一 實驗目的 1 在二叉樹基本操作的基礎上，掌握對二叉樹的一些其它操作的具體現方法.2.掌握構造哈夫曼樹以及哈夫曼編碼的方法.3 熟練掌握哈夫曼樹 最優二叉樹 特徵及其應用.二 實驗內容 哈夫曼樹和哈夫曼編碼 從終端輸入若干個字元，統計 或指定 字元出現的頻率，將字元出現的頻率作為結點的權值，建立哈...