《數(shù)據(jù)結(jié)構(gòu)實驗報告(哈夫曼樹)》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實驗報告(哈夫曼樹)（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、數(shù)據(jù)結(jié)構(gòu)實驗報告
實驗題目： Huffman編碼與解碼
姓名：
學(xué)號：
院系：
實驗名稱：
Huffman編碼與解碼實驗
問題描述：
本實驗需要以菜單形式完成以下功能：
1.輸入電文串
2.統(tǒng)計電文串中各個字符及其出現(xiàn)的次數(shù)
3.構(gòu)造哈弗曼樹
4.進行哈弗曼編碼
5.將電文翻譯成比特流并打印出來
6.將比特流還原成電文
數(shù)據(jù)結(jié)構(gòu)的描述：
邏輯結(jié)構(gòu)：
本實驗可用二叉樹實現(xiàn)，其邏輯結(jié)構(gòu)為一對二
2、的形式，即一個結(jié)點對應(yīng)兩個結(jié)點。在實驗過程中我們也應(yīng)用到了棧的概念。
存儲結(jié)構(gòu)：
使用結(jié)構(gòu)體來對數(shù)據(jù)進行存儲：
typedef struct
{
int weight;
int parent,lc,rc;
}HTNode,*HuffmanTree;
typedef struct LNode
{
char *elem;
int stacksize;
int top;
}SqStack;
在main函數(shù)里面定義一個哈弗曼樹并實現(xiàn)上述各種功能。
程序結(jié)構(gòu)的描述：
本次實驗一共構(gòu)造了10個函數(shù)：
1. void HuffTree(HuffmanTre
3、e &HT,int n[],int mun);
此函數(shù)根據(jù)給定的mun個權(quán)值構(gòu)建哈弗曼樹，n[]用于存放num個權(quán)值。
2.void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);
此函數(shù)用于在HT[1,i-1]中選擇parent為0且weight為最小的兩個結(jié)點，其 下標(biāo)分別為s1,s2.
3. void HuffmanCoding(HuffmanTree HT,char **&HC,int n);
此函數(shù)從哈弗曼樹HT上求得n 個葉子結(jié)點的哈弗曼編碼并存入數(shù)組HC中。
4. void Coding(Hu
4、ffmanTree HT,char **HC,int root,SqStack &S)；
此函數(shù)用于哈弗曼編碼，先序遍歷哈弗曼樹HT，求得每個葉子結(jié)點的編碼字符串，存入數(shù)組HC，S為一個順序棧，用來記錄遍歷路徑，root是哈弗曼數(shù)組HT中根結(jié)點的位置下標(biāo)。
5. void InitStack(SqStack &S);
此函數(shù)用于初始化一個棧。
6. void Pop(SqStack &S,char e);
此函數(shù)為出棧操作。
7. void Push(SqStack &S,char e);
此函數(shù)為進棧操作。
8. int StackLength(SqStack S);
此函
5、數(shù)用于求棧長，返回一個int型的值。
9. int Find(char a,char s[],int num);
此函數(shù)用于查找字符a在電文串中的位置。
10. int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n);
此函數(shù)用于將比特流還原成電文。
調(diào)試分析：
輸入任意一個字符串，如輸入welcometoustc:運行結(jié)果如下：
按照提示輸入任意一個或多個哈弗曼編碼，如輸入11111110101：
結(jié)果正確。
若輸入一個11111：
結(jié)果正確。
實驗完成
6、！
實驗體會和收獲：
本次實驗提高了對哈弗曼樹的認(rèn)識，同時加深了對二叉樹的理解，在棧的運用上更加熟練，對數(shù)組的應(yīng)用也有了提高。
源代碼：
#include
#include
#include
#include
typedef struct
{
int weight;
int parent,lc,rc;
}HTNode,*HuffmanTree;
typedef struct LNode
{
char *elem;
int stacksize;
int top;
}Sq
7、Stack;
#define size 20
void HuffTree(HuffmanTree &HT,int n[],int mun);
void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2);
void HuffmanCoding(HuffmanTree HT,char **&HC,int n);
void Coding(HuffmanTree HT,char **HC,int root,SqStack &S);
void InitStack(SqStack &S);
void Pop(SqStack &S,ch
8、ar e);
void Push(SqStack &S,char e);
int StackLength(SqStack S);
int Find(char a,char s[],int num);
int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n);
int main()
{
int i=0,n[size]={0},j=0,k=1,num=0;
char string[size]={0},m[size]={0},a[size]={0},b[size]={0};
char
9、** HC;
HuffmanTree HT;
printf("請輸入電文串:\n");
scanf("%s",string);
strcpy(m,string);
while(string[j])
{
if(string[j]!=#) a[k]=string[j];
i=j;
while(string[i])
{
if(string[i]==a[k])
{
string[i]=#;
n[k]++;
}
i++;
}
if(n[k]!=0)
{
printf("該電文中
10、字符%c出現(xiàn)次數(shù)為%d\n",a[k],n[k]);
num++;
k++;
}
j++;
}
printf("哈弗曼樹:\n");
HuffTree(HT,n,num);
for(i=1;i<=2*num-1;i++) printf("%d\t%d\t%d\t%d\n",HT[i].weight,HT[i].parent,HT[i].lc,HT[i].rc);
printf("哈弗曼編碼:\n");
HuffmanCoding(HT,HC,num);
for(i=1;i<=num;i++)
{
pr
11、intf("%c : %s\n",a[i],HC[i]);
}
printf("\n該電文的哈弗曼編碼為:\n");
i=0;
while(string[i])
printf("%s",HC[Find(m[i++],a,num)]);
printf("\n請輸入哈弗曼編碼：\n");
scanf("%s",string);
if(Recover(HT,HC,string,a,b,num)) printf("%s\n",b);
else printf("代碼有誤!\n");
system("pause");
return 0;
}
v
12、oid HuffTree(HuffmanTree &HT,int n[],int num)
{
int i,m,s1,s2;
m=2*num-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=m;i++)
{
HT[i].weight=i<=num?n[i]:0;
HT[i].lc=HT[i].rc=HT[i].parent=0;
}
for(i=num+1;i<=m;i++)
{
Select(HT,num,i,s1,s2);
HT[i].lc=s1;
HT[
13、i].rc=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=HT[s2].parent=i;
}
}
void Select(HuffmanTree &HT,int n,int i,int &s1,int &s2)
{
int k,t;
s1=s2=-1;
k=1;
while(s1==-1)
{
if(HT[k].parent==0)
s1=k;
k++;
}
k=1;
while(s2==-1||s2==s1)
{
if(HT[k].p
14、arent==0)
s2=k;
k++;
}
if(HT[s2].weight=HT[s1].weight&&
15、k!=s1&&k!=s2) s2=k;
}
}
}
void HuffmanCoding(HuffmanTree HT,char **&HC,int n)
{
SqStack S;
InitStack(S);
HC=(char**)malloc((n+1)*sizeof(char*));
Coding(HT,HC,2*n-1,S);
}
void Coding(HuffmanTree HT,char **HC,int root,SqStack &S)
{
if(root!=0)
{
if(HT[root].lc==0)
{
16、 Push(S,\0);
HC[root]=(char*)malloc((StackLength(S)));
strcpy(HC[root],S.elem);
Pop(S,\0);
}
Push(S,0);
Coding(HT,HC,HT[root].lc,S);
Pop(S,\0);
Push(S,1);
Coding(HT,HC,HT[root].rc,S);
Pop(S,\0);
}
}
void InitStack(SqStack &S)
{
S.elem=(char *)malloc(size*size
17、of(char));
S.stacksize=size;
S.top=-1;
}
void Push(SqStack &S,char e)
{
S.elem[++S.top]=e;
}
void Pop(SqStack &S,char e)
{
if(S.top==-1) return;
e=S.elem[S.top--];
return;
}
int StackLength(SqStack S)
{
if(S.top==-1) return(0);
return(S.top);
}
int Find(char a,char s[],int
18、 num)
{
int i;
for(i=1;i<=num;i++)
if(a==s[i]) return i;
return 0;
}
int Recover(HuffmanTree HT,char **HC,char string[],char a[],char b[],int n)
{
int i=0,j=0,k,m=0,t=0,h=0;
char s[size];
k=2*n-1;
while(string[i])
{
if(!HT[k].lc&&!HT[k].rc)
{
if(string[i]==0) {s[j]
19、=\0;k=2*n-1;t=1;j=0;}
if(string[i]==1)
{
s[j]=\0;
k=2*n-1;
t=1;
j=0;
}
for(h=1;h<=n;h++)
if(!strcmp(HC[h],s))
b[m++]=a[h];
}
else
{
if(string[i]==0) {k=HT[k].lc;s[j++]=0;}
if(string[i]==1)
{
k=HT[k].rc;
s[j]=1;
j++;
20、}
t=0;
}
if(!t)
i++;
}
if(!HT[k].lc&&!HT[k].rc)
{
if(string[i-1]==0) {s[j]=\0;k=2*n-1;j=0;}
if(string[i-1]==1)
{
s[j]=\0;
k=2*n-1;
t=1;
j=0;
}
for(h=1;h<=n;h++)
if(!strcmp(HC[h],s))
b[m++]=a[h];
}
b[m]=\0;
if(k==2*n-1) return 1;
else return 0;
}
數(shù)據(jù)結(jié)構(gòu)實驗報告(哈夫曼樹)
