数据结构实验报告
实验题目：Huffma
编码与解码
姓名：学号：院系：
f实验名称：
Huffma
编码与解码实验
问题描述：
本实验需要以菜单形式完成以下功能：1输入电文串2统计电文串中各个字符及其出现的次数3构造哈弗曼树4进行哈弗曼编码5将电文翻译成比特流并打印出来6将比特流还原成电文
数据结构的描述：
逻辑结构：
本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。在实验过程中我们也应用到了栈的概念。
存储结构：
使用结构体来对数据进行存储：typedefstructi
tweighti
tpare
tlcrcHTNodeHuffma
Tree
typedefstructLNode
charelemi
tstacksizei
ttopSqStack在mai
函数里面定义一个哈弗曼树并实现上述各种功能。
程序结构的描述：
本次实验一共构造了10个函数：1voidHuffTreeHuffma
TreeHTi
t
i
tmu
此函数根据给定的mu
个权值构建哈弗曼树，
用于存放
um个权值。2voidSelectHuffma
TreeHTi
t
i
tii
ts1i
ts2
f此函数用于在HT1i1中选择pare
t为0且weight为最小的两个结点，其下标分别为s1s2
3voidHuffma
Codi
gHuffma
TreeHTcharHCi
t
此函数从哈弗曼树HT上求得
个叶子结点的哈弗曼编码并存入数组HC中。4voidCodi
gHuffma
TreeHTcharHCi
trootSqStackS；此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。5voidI
itStackSqStackS此函数用于初始化一个栈。
6voidPopSqStackSchare此函数为出栈操作。
7voidPushSqStackSchare此函数为进栈操作。
8i
tStackLe
gthSqStackS此函数用于求栈长，返回一个i
t型的值。9i
tFi
dcharacharsi
t
um此函数用于查找字符a在电文串中的位置。10i
tRecoverHuffma
TreeHTcharHCcharstri
gcharacharbi
t
此函数用于将比特流还原成电文。
调试分析：
输入任意一个字符串，如输入welcometoustc运行结果如下：
f按照提示输入任意一个或多个哈弗曼编码，如输入11111110101：
结果正确。若输入一个11111：
结果正确。实验完成！
实验体会和收获：
本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上更加熟练，对数组的应用也有了提高。
源代码：
i
cludestdiohi
cludestdlibhi
cludemallochi
cludestri
ghtypedefstruct
i
tweighti
tpare
tlcrcHTNodeHuffma
Tree
typedefstructLNode
fcharelemi
tstacksizei
ttopSqStack
defi
esize20voidHuffTreeHuffma
TreeHTi
t
i
tmu
voidSelectHuffma
TreeHTi
t
i
tii
ts1i
ts2vor