数据结构课程设计 哈弗曼编译Word文档下载推荐.docx
《数据结构课程设计 哈弗曼编译Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计 哈弗曼编译Word文档下载推荐.docx（40页珍藏版）》请在冰点文库上搜索。
7、函数调用图如下：
Main
InitializationEncodingDecodingPrintTreePrint
SelectInputCodeCodepriningCoprint
Min
（main调用第二行所有函数，其余列的首字母对应的上一行函数调用下一行函数。
）
三、详细设计
哈夫曼编码是一种编码方式，它是根据每一个字符出现的概率而建立起来的。
哈夫曼编码借助树形结构构造，算法实现时使用链表或静态链表结构，空间的每个结点内有左子树、右子树、双亲指针。
在构成哈夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；
而为译码需从根出发走一条从根到叶子的路径。
要实现如上概要所说功能，需要进行如下步骤。
1、哈夫曼树及哈夫曼编码的存储表示
typedefstruct
{intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储哈夫曼树
typedefchar**HuffmanCode;
//动态分配数组存储哈夫曼编码表
2、初始化
HuffmanTreeHT;
HuffmanCodeHC;
int*w,i,j;
constintn=26;
char*z;
intflag=0;
intnumb=0;
3、定义min功能函数
intmin（HuffmanTreet,inti）
{intj,flag;
intk=UINT_MAX;
for（j=1;
j<
=i;
j++）
if（t[j].weight<
k&
&
t[j].parent==0）
k=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
}
4、定义选择权值最小的结点的函数
voidselect（HuffmanTreet,inti,int&
s1,int&
s2）
{intj;
s1=min（t,i）;
s2=min（t,i）;
if（s1>
{j=s1;
s1=s2;
s2=j;
}
}
5、编写求哈夫曼编码的算法。
voidHuffmanCoding（HuffmanTree&
HT,HuffmanCode&
HC,int*w,intn）
{intm,i,s1,s2,start;
intc,f;
HuffmanTreep;
char*cd;
if（n<
=1）
return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
for（p=HT+1,i=1;
i<
=n;
++i,++p,++w）
{p->
weight=*w;
p->
parent=0;
p->
lchild=0;
rchild=0;
for（;
=m;
++i,++p）
for（i=n+1;
++i）
{select（HT,i-1,s1,s2）;
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
cd=（char*）malloc（n*sizeof（char））;
cd[n-1]='
\0'
;
for（i=1;
i++）
{
start=n-1;
for（c=i,f=HT[i].parent;
f!
=0;
c=f,f=HT[f].parent）
if（HT[f].lchild==c）
cd[--start]='
0'
elsecd[--start]='
1'
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
strcpy（HC[i],&
cd[start]）;
free（cd）;
6、在“我的课程设计”文件夹中新建“abc.txt”文件，文件内容如下：
字符
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
13
22
32
103
21
15
47
57
1
5
20
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
63
48
51
80
23
8
18
16
7、编写初始化（Initialization）函数
voidInitialization（）
{flag=1;
intnum2;
cout<
<
"
下面初始化哈夫曼链表"
endl;
w=（int*）malloc（n*sizeof（int））;
z=（char*）malloc（n*sizeof（char））;
\n依次显示"
n<
个字符与其权值和编码\n"
charbase[2];
ifstreamfin（"
abc.txt"
）;
for（i=0;
n;
{fin>
>
base;
*（z+i）=*base;
fin>
num2;
*（w+i）=num2;
HuffmanCoding（HT,HC,w,n）;
字符"
setw（6）<
权值"
setw（11）<
编码"
{
cout<
setw（3）<
*（z+i-1）;
*（w+i-1）<
setw（12）<
HC[i]<
下面将哈夫曼编码写入文件"
endl<
...................."
FILE*htmTree;
charr[]={'
'
'
};
if（（htmTree=fopen（"
htmTree.txt"
"
w"
））==NULL）
{cout<
不能打开文件"
for（i=0;
{fputc（*（z+i）,htmTree）;
fputs（r,htmTree）;
}
i++）
{fprintf（htmTree,"
%6d"
*（w+i））;
fputs（r,htmTree）;
for（i=1;
{fputs（HC[i],htmTree）;
fclose（htmTree）;
已将字符与对应编码写入根目录下文件htmTree.txt中"
8、编写编码（Encoding）函数
voidInputCode（）
{FILE*tobetran;
charstr[100];
if（（tobetran=fopen（"
tobetran.txt"
不能打开文件"
return;
请输入你想要编码的字符"
gets（str）;
fputs（str,tobetran）;
获取报文成功"
fclose（tobetran）;
报文存入根目录下的tobetran.txt文件中"
voidEncoding（）
{cout<
下面对目录下文件tobetran.txt中的字符进行编码"
FILE*tobetran,*codefile;
if（（tobetran=fopen（"
rb"
if（（codefile=fopen（"
codefile.txt"
wb"
））==NULL）
char*tran;
i=99;
tran=（char*）malloc（100*sizeof（char））;
while（i==99）
{if（fgets（tran,100,tobetran）==NULL）
break;
*（tran+i）!
='
{for（j=0;
{if（*（z+j-1）==*（tran+i））
{fputs（HC[j],codefile）;
if（j>
n）
字符错误，无法编码!
…………编码完成…………"
编码写入目录下的codefile.txt中"
fclose（codefile）;
free（tran）;
9、编写译码（Decoding）函数
voidDecoding（）
下面对根目录下文件codefile.txt中的字符进行译码"
FILE*codef,*txtfile;
if（（txtfile=fopen（"
\\Textfile.txt"
txtfile=fopen（"
Textfile.txt"
if（（codef=fopen（"
r"
codef=fopen（"
char*work,*work2,i2;
inti4=0,i,i3;
unsignedlonglength=10000;
work=（char*）malloc（length*sizeof（char））;
fgets（work,length,codef）;
work2=（char*）malloc（length*sizeof（char））;
i3=2*n-1;
*（work+i-1）!
{i2=*（work+i）;
if（HT[i3].lchild==0）
{*（work2+i4）=*（z+i3-1）;
i4++;
i3=2*n-1;
i--;
elseif（i2=='
）i3=HT[i3].lchild;
elseif（i2=='
）i3=HT[i3].rchild;
*（work2+i4）='
fputs（work2,txtfile）;
…………译码完成…………"
内容写入根目录下的文件textfile.txt中"
free（work）;
free（work2）;
fclose（txtfile）;
fclose（codef）;
10.编写打印代码文件函数（Print）
voidCode_printing（）
下面打印根目录下文件CodePrin.txt中编码字符"
FILE*CodePrin,*codefile;
if（（CodePrin=fopen（"
CodePrin.txt"
char*work3;
work3=（char*）malloc（51*sizeof（char））;
if（fgets（work3,51,codefile）==NULL）
不能读取文件"
elsedo
fputs（work3,CodePrin）;
puts（work3）;
while（strlen（work3）==50&
fgets（work3,51,codefile）!
=NULL）;
free（work3）;
打印结束"
fclose（CodePrin）;
11、编写打印哈夫曼树（TreePrinting）函数
voidcoprint（HuffmanTreestart,HuffmanTreeHT）
{if（start!
=HT）
{FILE*TreePrint;
if（（TreePrint=fopen（"
TreePrint.txt"
a"
创建文件失败"
numb++;
coprint（HT+start->
rchild,HT）;
setw（5*numb）<
start->
weight<
fprintf（TreePrint,"
%d\n"
start->
weight）;
lchild,HT）;
numb--;
fclose（TreePrint）;
voidTree_printing（HuffmanTreeHT,intw）{HuffmanTreep;
p=HT+w;
下面打印哈夫曼树"
coprint（p,HT）;
打印工作结束"
12、编写主函数
voidmain（）
此程序实现哈夫曼编码解码功能"
charchoice;
while（choice!
q'
）
\n******************************"
哈夫曼编码解码"
******************************"
（i）初始化哈夫曼表"
（w）输入待编码的字符"
（e）进行编码、译码、打印编码"
（t）打印哈夫曼树"
（q）离开"
if（flag==0）
\n请先初始化哈夫曼链表,输入'
i'
（程序将从根目录下的abc.txt文件中读出26个字母及其权值并对字母进行编码）"
cin>
choice;
switch（choice）
{case'
:
Initialization（）;
case'
w'
InputCode（）;
break;
case'
e'
Inputcoding（）;
Decoding（）;
Code_printing（）;
t'
Tree_printing（HT,2*n-1）;
default:
输入命令错误"
free（z）;
free（w）;
free（HT）;
四、调试分析
调试过程是漫长而磨人的，以下截取少数错误以供参考：
Compiling...
aa.cpp
E:
\我的课程设计\课程设计\aa.cpp（39）:
errorC2065:
m'
:
undeclaredidentifier
\我的课程设计\课程设计\aa.cpp（41）:
p'
errorC2440:
cannotconvertfrom'
HTNode*'
to'
int'
Thisconversionrequiresareinterpret_cast,aC-stylecastorfunction-stylecast
\我的课程设计\课程设计\aa.cpp（42）:
errorC2227:
leftof'
->
weight'
mustpointtoclass/struct/union
\我的课程设计\课程设计\aa.cpp（43）:
parent'
\我的课程设计\课程设计\aa.cpp（44）:
lchild'
rchild'
\我的课程设计\课程设计\aa.cpp（46）:
\我的课程设计\课程设计\aa.cpp（48）:
s1'
s2'
\我的课程设计\课程设计\aa.cpp（55）:
cd'
char*'
\我的课程设计\课程设计\aa.cpp（56）:
errorC2109:
subscriptrequiresarrayorpointertype
errorC2106:
leftoperandmustbel-value
\我的课程设计\课程设计\aa.cpp（59）:
start'
\我的课程设计\课程设计\aa.cpp（60）:
c'
f'
\我的课程设计\课程设计\aa.cpp（63）:
\我的课程设计\课程设计\aa.cpp（6
升级会员 