文档介绍：杨玉森实验报告（刘改）
《数据结构》Huffman树实验报吿
班级：电信0608
姓名：杨玉森
学号:0**********
完成日期：2007年12月1日
指导教师：刘玉
目录
需求分
析
1
2详细设
计
1
1程序简单流程
图
1
?
1
3调试分
析
5
1出现的问题及解
决
5
3. 2算法分
析
5经验和体
会
4用户使用说
明
7
5测试结
果
8附录9 1
数据结构实验报告
1需求分析
本实验要求建一棵Huffman树并求树屮各节点字符的Huffman编码并打卬输出，木程序完成了此项要求。
程序要求输入一字符串，以#结束，其屮用户可以输入任何字符，但本程序仅视小写英文字母和空格键为有效值，将其读入指定位置对其他形式的输入不作处理，即视为不存在，不做保存。
程序的输岀位用户输入的有效字符，并统计其出现的次数（权值）一并输出到屏幕上；然后，程序对输入的字符进行Huffman编码并输出。
本程序能成功的完成一段任意字符串的录入并记录其中出现过的小写英文字母和空格，然后统计上述字符出现的次数（权值），然后根据以上得到的信息对有效字符（小写英文字母和空格）进行Huffman编码并输出其编码。
一、详细设计
1•程序简单流程图如下：
2.
木程序可分为主程序、数据输入、建Huffman树并进行Huffman编码这三个模块，各模块具体说明如下：
1
1）主函数模块：
完成各个函数的调用，及输出经处理后的输入字符，以及它们对应的权值和Huffman编码。伪码如下：
void main()
getdata(&da) ; //调川函数完成数据的输入
Huff mancoding (&IIT, &IIC, count, da) ; //调 Jlj Huffmancoding 函数
Printf(整理后的输入数据)；
(Huffman 编码)；//输出 Huffman 编码
}
数据输入模块：
完成从键盘输入一任意长度的字符串，并对其进行处理，从屮提取有效的字符，并按其 ASCII码的先后顺序存入数组da的数据域屮，同时统计各有效字符的权值，将其存到da 屮和字符对应的权值域中。伪码如下：
void getdata(HTdata **da)
I
if (! (dal = (HTdata *)malloc (28*sizeof (HTdata)))) 〃给 dal 分配存储空间
I
error;
}
dal [1]. data =''; 〃初始化 dal
dal[1]. w = 0;
for(i = 2;i <= 27;i++)
{
dal[i]. data 二'『+ i - 2;
dal[i].w = 0;
}
wh订e(l) //从键盘输入数据，并将其临时存
//放在血1屮并统计各个字母的权值
{ ch = getcharO ; if (ch == ' #') //# 为输入结束标志 break; else if (ch ='') { if (dal [1]. w == 0) count ++; //count用于记录输入字符的个数(不包括重复的) dal[1]. data = ch; dal[1]. w ++; } else if(ch >二's' && ch〈二'z') { 2
数据结构实验报告
if (dal [ch -，a' + 2]. w == 0)
count ++;
dal [ch - ，a， + 2]. w ++;
}
}
if (! (*da = (HTdata *)malloc ((count + 1) *sizeof (HTdata))))//da 用于存放经处理过的
//数据及其权值
I
error;
}
for(i = l;i <= 27; i ++) //将dal中的数据及其权值整理后存入da中{
if (dal [i]. w)
{
(*da)[j]. data = dal[i]. data;
(*da)[j++]. w = dal[i]. w;
}
}
}
3）建Huffman树并进彳亍Huffman编码模块:
木程序的关键函数，用于根据个字符对应的权值生成一棵Huffman树，并求各字符所对应的Huffman编码。伪码如下：
void Huffmancoding(HTnode **ht, Huffmancode *hc, int n, HTdata *da)
I
if(n <= 1) 〃若结点数为一或数为空，给