实验报告数据结构.doc

《用哈夫曼编码实现文件压缩》
实验报告
课程名称数据结构B
实验学期 2014 至 2015 学年第二学期
学生所在系部管理学院
年级 2013 专业班级电商B133
学生姓名谷美霞学号 201304064328
任课教师兰芸
实验成绩
一、实验题目:
用哈夫曼编码实现文件压缩
二、实验目的:
了解文件的概念。
掌握线性链表的插入、删除等算法。
3、掌握Huffman树的概念及构造方法。
4、掌握二叉树的存储结构及遍历算法。
5、利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理
三、实验设备与环境:
微型计算机、Windows 系列操作系统、Visual C++
四、实验内容:
根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩
五、概要设计:
1、构建赫夫曼树HT,并求出n个字符的赫夫曼编码HC。
2、创建完毕后,!
3、进行编码,。
4、,输出在终端。
5、,。
6、先用编码中的前几个和字符的编码相比较,然后往后移。
7、最后译码结束后,!
8、如有其他情况请重新输入。
六、详细设计:
#include<>
#include<>
#include<>
#include<>
#include<>
typedef struct{ //赫夫曼树的结构体
char ch;
int weight; //权值
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;
void Select(hfmtree &HT,int a,int *p1,int *p2) //Select函数,选出HT树到a为止,权值最小且parent为0的2个节点
{
int i,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;
}
}
for(i=j+1;i<=a;++i){
if(HT[i].weight<HT[x].weight&&HT[i].parent==0){
x=i; //选出最小的节点
}
}
for(j=1;j<=a;++j) {
if(HT[j].parent==0&&x!=j)
{
y=j;
break;
}
}
for(i=j+1;i<=a;++i)
{
if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)
{
y=i; //选出次小的节点
}
}
if(x>y){
*p1=y;
*p2=x;
}
else
{
*p1=x;