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