數(shù)據(jù)結(jié)構實驗報告
―― 實驗五
簡單哈夫曼編/譯碼的設計與實現(xiàn) 本實驗的目的是通過對簡單哈夫曼編/譯碼系統(tǒng)的設計與實現(xiàn)來熟練掌握樹型結(jié)構在實際問題中的應用。此實驗可以作為綜合實驗，階段性實驗時可以選擇其中的幾個功能來設計和實現(xiàn)。
一、【問題描述】
利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼，此實驗即設計這樣的一個簡單編/碼系統(tǒng)。系統(tǒng)應該具有如下的幾個功能：
1、接收原始數(shù)據(jù)。
從終端讀入字符集大小 n，以及 n 個字符和 n 個權值，建立哈夫曼樹，并將它存于文件 nodedata.dat 中。
2、編碼。
利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件 nodedata.dat 中讀入），對文件中的正文進行編碼，然后將結(jié)果存入文件 code.dat 中。
3、譯碼。利用已建好的哈夫曼樹將文件 code.dat 中的代碼進行譯碼，結(jié)果存入文件 textfile.dat 中。
4、打印編碼規(guī)則。
即字符與編碼的一一對應關系。
二、【數(shù)據(jù)結(jié)構設計】
1、構造哈夫曼樹時使用靜態(tài)鏈表作為哈夫曼樹的存儲。
在構造哈夫曼樹時，設計一個結(jié)構體數(shù)組 HuffNode 保存哈夫曼樹中各結(jié)點的信息，根據(jù)二叉樹的性質(zhì)可知，具有 n 個葉子結(jié)點的哈夫曼樹共有 2n-1 個結(jié)點，所以數(shù)組 HuffNode 的大小設置為 2n-1，描述結(jié)點的數(shù)據(jù)類型為：
typedef struct
{
int weight;//結(jié)點權值
int parent;
int lchild;
int rchild;
char inf; }HNodeType;
2、求哈夫曼編碼時使用一維結(jié)構數(shù)組 HuffCode 作為哈夫曼編碼信息的存儲。
求哈夫曼編碼，實質(zhì)上就是在已建立的哈夫曼樹中，從葉子結(jié)點開始，沿結(jié)點的雙親鏈域回退到根結(jié)點，沒回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結(jié)點到相應葉子結(jié)點所經(jīng)過的路徑上各分支所組成的 0、1 序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼位所求編碼的高位碼，所以設計如下數(shù)據(jù)類型：
#define MAXBIT 10 typedef struct
{
int bit[MAXBIT]；
int start； }HcodeType；
3、文件 nodedata.dat、code.dat 和 textfile.dat。
三、【功能（函數(shù)）設計】
1、初始化功能模塊。
此功能模塊的功能為從鍵盤接收字符集大小 n，以及 n 個字符和 n個權值。
2、建立哈夫曼樹的功能模塊。
此模塊功能為使用 1 中得到的數(shù)據(jù)按照教材中的構造哈夫曼樹的算法構造哈夫曼樹，即將 HuffNode 數(shù)組中的各個位置的各個域都添上相關的值，并將這個結(jié)構體數(shù)組存于文件 hfmtree.dat 中。
3、建立哈夫曼編碼的功能模塊。
此模塊功能為從文件 nodedata.dat 中讀入相關的字符信息進行哈夫曼編碼，然后將結(jié)果存入 code.dat 中，同時將字符與 0、1 代碼串的一一對應關系打印到屏幕上。
4、譯碼的功能模塊。
此模塊功能為接收需要譯碼的 0、1 代碼串，按照 3 中建立的編碼規(guī)則將其翻譯成字符集中字符所組成的字符串形式，存入文件
textfile.dat，同時將翻譯的結(jié)果在屏幕上打印輸出。
四、【編碼實現(xiàn)】
#include<iostream.h> #include<fstream.h> #include<string.h> #include<stdlib.h> #define MaxBit 10 #define Maxvalue 100//應該大于權重之和 #define Maxleaf 100 #define Maxnode Maxleaf*2-1 typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
char inf;
}HNodeType; struct HcodeType {
int bit[MaxBit];
int start; };
void Creat_Haffmantree(int &n) {
HNodeType *HaffNode=new HNodeType[2*n-1];
int i,j;
int m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
HaffNode[i].weight=0;
HaffNode[i].parent=-1;
HaffNode[i].lchild=-1;
HaffNode[i].rchild=-1;
HaffNode[i].inf="0";
}
for(i=0;i<n;i++)
{
cout<<"請輸入字符"<<endl;
cin>>HaffNode[i].inf;
cout<<"請輸入該字符的權值"<<endl;
cin>>HaffNode[i].weight;
}
for(i=0;i<n-1;i++)//構造哈夫曼樹
{
m1=m2=Maxvalue;
x1=x2=0;
for(j=0;j<n+i;j++)//選取最小和次小
{
if(HaffNode[j].parent==-1&&HaffNode[j].weight<m1)
{
m2=m1;
x2=x1;
m1=HaffNode[j].weight;
x1=j;
}
else
{
if(HaffNode[j].parent==-1&&HaffNode[j].weight<m2)
{
m2=HaffNode[j].weight;
x2=j;
}
}
}
//將找出的最小和次小合并，創(chuàng)造其父母結(jié)點
HaffNode[x1].parent=n+i;
HaffNode[x2].parent=n+i;
HaffNode[n+i].weight=HaffNode[x1].weight+HaffNode[x2].weight;
HaffNode[n+i].lchild=x1;
HaffNode[n+i].rchild=x2;
HaffNode[n+i].inf=NULL;
}
cout<<"顯示存儲的哈弗曼樹信息:"<<endl;
cout<<"權值 左孩子 右孩子 雙親"<<endl;
for(i=0;i<2*n-1;i++)
{
cout<<HaffNode[i].weight<<"
";
cout<<HaffNode[i].lchild<<"
";
cout<<HaffNode[i].rchild<<"
";
cout<<HaffNode[i].parent<<"
";
cout<<HaffNode[i].inf<<endl;
}
//寫入文件
fstream outfile1;
outfile1.open("E:\\nodedata.dat",ios::out|ios::trunc|ios::binary);//建立進行寫入的文件
if(!outfile1) //沒有創(chuàng)建成功則顯示相應信息
{
cout<<"nodedata.dat 文件不能打開"<<endl;
abort();
}
for(i=0;i<2*n-1;i++) //將內(nèi)存中從 HaffNode[i]地址開始的sizeof(HaffNode[i])的內(nèi)容寫入文件中
outfile1.write((char*)&HaffNode[i],sizeof(HaffNode[i]));
outfile1.close ();//關閉文件
delete []HaffNode;
} void HaffCode(int &n)//哈夫曼編碼 {
HNodeType *HaffNode=new HNodeType[Maxnode];
HcodeType *HaffCode=new HcodeType[Maxleaf];
HcodeType cd;
int i,j,c,p;
fstream in("E:\\nodedata.dat",ios::in|ios::binary);
in.read((char*)HaffNode,(2*n-1)*sizeof(HNodeType));
in.close();
fstream outfile;
outfile.open("E:\\codedata.dat",ios::out|ios::binary);//建立進行寫入的文件
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;
p=HaffNode[c].parent;
while(p!=-1)
{
if(HaffNode[p].lchild==c)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=HaffNode[c].parent;
}
for(j=cd.start+1;j<n;j++)
HaffCode[i].bit[j]=cd.bit[j];
HaffCode[i].start=cd.start;
}
for(i=0;i<n;i++)
{
outfile<<HaffNode[i].inf;
for(j=HaffCode[i].start+1;j<n;j++)
outfile<<HaffCode[i].bit[j];
}
cout<<"字符信息--編碼信息"<<endl;
for(i=0;i<n;i++)
{
cout<<HaffNode[i].inf<<"---";
for(j=HaffCode[i].start+1;j<n;j++)
cout<<HaffCode[i].bit[j];
cout<<endl;
}
outfile.close ();
cout<<"請輸入要編碼的字符串,基本元素為（";
for(i=0;i<n;i++)
cout<<HaffNode[i].inf<<",";
cout<<")"<<endl;
char inf[100];
cin>>inf;
int f=strlen(inf);
fstream outfile1;
outfile1.open("E:\\code.dat",ios::out|ios::binary);// 建立進行寫入的文件
if(!outfile1)
{
cout<<"code.dat 文件不能打開!"<<endl;
abort();
}
else
{
cout<<endl;
cout<<"字符串編碼后為:";
for(int x=0;x<f;x++)
{
for(i=0;i<n;i++)
{
if(inf[x]==HaffNode[i].inf)
{
for(j=HaffCode[i].start+1;j<n;j++)
{
outfile1.write((char*)&HaffCode[i].bit[j],sizeof(HaffCode[i].bit[j]));
cout<<HaffCode[i].bit[j];
}
}
}
}
}
cout<<endl;
cout<<"編譯后的代碼串已經(jīng)存入 code.dat 文件中!"<<endl;
cout<<endl;
outfile1.close();
delete []HaffNode;
delete []HaffCode;
} void decode( int &n)//解碼 {
int i;
HNodeType *HaffNode=new HNodeType[2*n-1];
fstream infile1;
infile1.open("E:\\nodedata.dat",ios::in|ios::binary);//讀出哈夫曼樹
if(!infile1)
{
cout<<"nodedata.dat 文件不能打開"<<endl;
abort();
}
for(i=0;i<2*n-1;i++)
infile1.read((char*)&HaffNode[i],sizeof(HNodeType));
infile1.close();
int tempcode[100];
int num=0;
for(i=0;i<100;i++)
tempcode[i]=-1;
HcodeType *Code=new HcodeType[n];
fstream infile2;//讀編碼
infile2.open("E:\\code.dat",ios::in|ios::binary);
while(!infile2.eof())
{
infile2.read((char*)&tempcode[num],sizeof(tempcode[num]));
num++;
}
infile2.close();
num--;
cout<<"從文件中讀出的編碼為"<<endl;
for(i=0;i<num;i++)
cout<<tempcode[i];
cout<<endl;
int m=2*n-2;
i=0;
cout<<endl;
cout<<"譯碼后為:"<<endl;
fstream outfile;
outfile.open("E:\\textfile.txt",ios::out);
if(!outfile)
{
cout<<"textfile.txt 文件不能打開!"<<endl;
abort();
}
while(i<num)// 小于字符串的長度
{
while(HaffNode[m].lchild!=-1&&HaffNode[m].rchild!=-1)
{
if(tempcode[i]==0)
{
m=HaffNode[m].lchild;
i++;
}
else if(tempcode[i]==1)
{
m=HaffNode[m].rchild;
i++;
}
}
cout<<HaffNode[m].inf;
outfile<<HaffNode[m].inf;
m=2*n-2;
}
cout<<endl;
outfile.close();
cout<<"譯碼后的結(jié)果已經(jīng)存入 textfile.txt 中!"<<endl;
delete []HaffNode;
}
int main() {
int n;
cout<<"************* 歡 迎 進 入 編 / 譯 碼 系 統(tǒng) ！*********************"<<endl;
int ch1;
do{
cout<<"
1.建樹"<<endl;
cout<<"
2:編碼，并顯示字符和對應的編碼"<<endl;
cout<<"
3:譯碼"<<endl;
cout<<"
0:退出"<<endl;
cout<<"********************************************************"<<endl;
cout<<"請選擇(0~3):";
cin>>ch1;
while(!(ch1<=3&&ch1>=0)) //輸入不在 0 到 4 之間無效
{
cout<<"數(shù)據(jù)輸入錯誤，請重新選擇(0~4):";
cin>>ch1;
}
switch(ch1)
{
case
1:
{
cout<<"\t\t\t請輸入編碼個數(shù)"<<endl;//葉子結(jié)點個數(shù)
cin>>n;
Creat_Haffmantree(n);
break;
}
case
2:
HaffCode(n);
break;
case
3:
decode(n);
break;
}
}while(ch1!=0);
return 0; }
五、【運行與測試】
1、令葉子結(jié)點個數(shù) n 為 4，權值集合為{1，3，5，7}，字符集合為{A，B，C，D}，并有如下對應關系，A――1、B――3，C――5，D――7，調(diào)用初始化功能模塊可以正確接收這些數(shù)據(jù)。
2、調(diào)用建立哈夫曼樹的功能模塊，構造靜態(tài)鏈表 HuffNode 的存儲。
3、調(diào)用建立哈夫曼編碼的功能模塊，在屏幕上顯示如下對應關系：
A――111、B――110、C――10、D――0
4、調(diào)用譯碼的功能模塊，輸入代碼串“111110100”后，屏幕上顯示譯碼結(jié)果：
111110100 ―――― ABCD
推薦訪問： 數(shù)據(jù)結(jié)構 編碼 實驗下一篇：統(tǒng)計學實驗報告匯總
在偉大祖國73華誕之際，我參加了單位組織的“光影鑄魂”主題黨日活動，集中觀看了抗美援朝題材影片《長津湖》，再一次重溫這段悲壯歷史，再一次深刻感悟偉大抗美援朝精神。1950年10月，新中國剛剛成立一年，
根據(jù)省局黨組《關于舉辦習近平談治國理政（第四卷）讀書班的通知》要求，我中心通過專題學習、專題研討以及交流分享等形式，系統(tǒng)的對《習近平談治國理政》（第四卷)進行了深入的學習與交流，下面我就來談一談我個人
《習近平談治國理政》（第四卷）是在百年變局和世紀疫情相互疊加的大背景下，對以習近平同志為核心的黨中央治國理政重大戰(zhàn)略部署、重大理論創(chuàng)造、重大思想引領的系統(tǒng)呈現(xiàn)。它生動記錄了新一代黨中央領導集體統(tǒng)籌兩個
《真抓實干做好新發(fā)展階段“三農(nóng)工作”》是《習近平談治國理政》第四卷中的文章，這是習近平總書記在2020年12月28日中央農(nóng)村工作會議上的集體學習時的講話。文章指出，我常講，領導干部要胸懷黨和國家工作大
在《習近平談治國理政》第四卷中，習近平總書記強調(diào)，江山就是人民，人民就是江山，打江山、守江山，守的是人民的心。從嘉興南湖中駛出的小小紅船，到世界上最大的執(zhí)政黨，在中國共產(chǎn)黨的字典里，“人民”一詞從來都
黨的十八大以來，習近平總書記以馬克思主義戰(zhàn)略家的博大胸襟和深謀遠慮，在治國理政和推動全球治理中牢固樹立戰(zhàn)略意識，在不同場合多次圍繞戰(zhàn)略策略的重要性，戰(zhàn)略和策略的關系，提高戰(zhàn)略思維、堅定戰(zhàn)略自信、強化戰(zhàn)
《習近平談治國理政》第四卷集中展示了以習近平同志為核心的黨中央在百年變局和世紀疫情相互疊加背景下，如何更好地堅持和發(fā)展中國特色社會主義而進行的生動實踐與理論探索；對于新時代堅持和發(fā)展什么樣的中國特色社
在黨組織的關懷下，我有幸參加了區(qū)委組織部組織的入黨積極分子培訓班。為期一周的學習，學習形式多樣，課程內(nèi)容豐富，各位專家的講解細致精彩，對于我加深對黨的創(chuàng)新理論的認識、對黨的歷史的深入了解、對中共黨員的
《習近平談治國理政》第四卷《共建網(wǎng)上美好精神家園》一文中指出：網(wǎng)絡玩命是新形勢下社會文明的重要內(nèi)容，是建設網(wǎng)絡強國的重要領域。截至2021年12月，我國網(wǎng)民規(guī)模達10 32億，較2020年12月增長4
剛剛召開的中國共產(chǎn)黨第十九屆中央委員會第七次全體會議上討論并通過了黨的十九屆中央委員會向中國共產(chǎn)黨第二十次全國代表大會的報告、黨的十九屆中央紀律檢查委員會向中國共產(chǎn)黨第二十次全國代表大會的工作報告和《