- 相關(guān)推薦
數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)五
一.實(shí)驗(yàn)內(nèi)容：
實(shí)現(xiàn)哈夫曼編碼的生成算法。
二.實(shí)驗(yàn)?zāi)康模?/strong>
1、使學(xué)生熟練掌握哈夫曼樹(shù)的生成算法。
2、熟練掌握哈夫曼編碼的方法。
三.問(wèn)題描述：
已知n個(gè)字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼。
1、讀入n個(gè)字符，以及字符的權(quán)值，試建立一棵Huffman樹(shù)。
2、根據(jù)生成的Huffman樹(shù)，求每個(gè)字符的Huffman編碼。并對(duì)給定的待編碼字符序列進(jìn)行編碼，并輸出。
四.問(wèn)題的實(shí)現(xiàn)
(1)郝夫曼樹(shù)的存儲(chǔ)表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼樹(shù)
郝夫曼編碼的存儲(chǔ)表示
typedef char* *HuffmanCode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼編碼
(2)主要的實(shí)現(xiàn)思路：
a.首先定義郝夫曼樹(shù)的存儲(chǔ)形式，這里使用了數(shù)組
b.用select()遍歷n個(gè)字符，找出權(quán)值最小的兩個(gè)
c.構(gòu)造郝夫曼樹(shù)HT，并求出n個(gè)字符的郝夫曼編碼HC
總結(jié)
1.基本上沒(méi)有什么太大的問(wèn)題，在調(diào)用select()這個(gè)函數(shù)時(shí)，想把權(quán)值最小的兩個(gè)結(jié)點(diǎn)的序號(hào)帶回HuffmanCoding()，所以把那2個(gè)序號(hào)設(shè)置成了引用。
2.在編程過(guò)程中，在什么時(shí)候分配內(nèi)存，什么時(shí)候初始化花的時(shí)間比較長(zhǎng)
3.最后基本上實(shí)現(xiàn)后，發(fā)現(xiàn)結(jié)果仍然存在問(wèn)題，經(jīng)過(guò)分步調(diào)試，發(fā)現(xiàn)了特別低級(jí)的輸入錯(cuò)誤。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2寫(xiě)成了i
附：
//動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼樹(shù)
typedef struct{
int weight; //字符的權(quán)值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//動(dòng)態(tài)分配數(shù)組存儲(chǔ)郝夫曼編碼
typedef char* *HuffmanCode;
//選擇n個(gè)(這里是k=n)節(jié)點(diǎn)中權(quán)值最小的兩個(gè)結(jié)點(diǎn)
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i<=k && HT[i].parent!=0)i++;
//下面選出權(quán)值最小的結(jié)點(diǎn)，用s1指向其序號(hào)
s1=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&HT[i].weight
}
//下面選出權(quán)值次小的結(jié)點(diǎn)，用s2指向其序號(hào)
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&i!=s1)break;
}
s2=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&i!=s1&&HT[i].weight
}
}
//構(gòu)造Huffman樹(shù)，求出n個(gè)字符的編碼
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n<=1)return;
m=2*n-1; //n個(gè)葉子n-1個(gè)結(jié)點(diǎn)
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號(hào)單元未用，預(yù)分配m+1個(gè)單元
HuffmanTree p=HT+1;
w++; //w的號(hào)單元也沒(méi)有值，所以從號(hào)單元開(kāi)始
for(i=1;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=p->parent=p->rchild=p->lchild=0;
}
for(i=n+1;i<=m;i++)
{
Select(HT,i-1,s1,s2); //選出當(dāng)前權(quán)值最小的
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;
}
//從葉子到根逆向求每個(gè)字符的郝夫曼編碼
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n個(gè)字符編碼的頭指針變量
cd=(char*)malloc(n*sizeof(char)); //分配求編碼的工作空間
cd[n-1]='';//編碼結(jié)束符
for(i=1;i<=n;i++) //逐個(gè)字符求郝夫曼編碼
{
start=n-1; //編碼結(jié)束符位置
for(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)); //為第i個(gè)字符編碼分配空間
strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼到HC
}
free(cd); //釋放工作空間
}
void main()
{ int n,i;
int* w; //記錄權(quán)值
char* ch; //記錄字符
HuffmanTree HT;
HuffmanCode HC;
cout<<"請(qǐng)輸入待編碼的字符個(gè)數(shù)n=";
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //記錄權(quán)值，號(hào)單元未用
ch=(char*)malloc((n+1)*sizeof(char));//記錄字符，號(hào)單元未用
cout<<"依次輸入待編碼的字符data及其權(quán)值weight"<
for(i=1;i<=n;i++)
{
cout<<"data["<
}
【數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)五】相關(guān)文章：
實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)心得05-21
化學(xué)實(shí)驗(yàn)報(bào)告07-03
實(shí)驗(yàn)報(bào)告總結(jié)02-14
關(guān)于實(shí)驗(yàn)報(bào)告01-27