logo资料库

哈夫曼与文件压缩课程设计报告.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.66M 资料格式：doc 举报 版权申诉
第1页 / 共21页
第2页 / 共21页
第3页 / 共21页
第4页 / 共21页
第5页 / 共21页
第6页 / 共21页
第7页 / 共21页
第8页 / 共21页
资料共21页，剩余部分请下载后查看
    目录
    数据结构课程设计报告 题目: 哈夫曼编码与文件压缩 学号: 姓名: u201014516 董贝青 指导老师: 许贵平 院系班级: 计科 1010
    目录 一、实验目的………………………………………………………1 二、实验环境………………………………………………………1 三、实验内容………………………………………………………1 四、实验要求………………………………………………………1 五、设计概要………………………………………………………1 六、源代码及流程图………………………………………………2 七、数据测试………………………………………………………16 八、实验感受………………………………………………………19
    一、实验目的 1、掌握二叉树、哈夫曼树的概念、性质与存储结构 2、掌握哈夫曼算法，能够利用其实现哈夫曼编码，并应用于文件压缩。 3、提高综合运用只是的技能与实践能力。 二、实验环境 1、Windows 7 2、Visual Studio 2012 三、 实验内容 分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功 能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩 得到解压文件。 四、实验要求 （1）要求界面友好，输入文本文件可带路径（如：D:\doc\original.txt），哈夫曼 算法所得到的压缩文件名为*.cod，哈夫曼树也以文件形式保存，文件名为*.hfm。 （2）显示压缩比、压缩时间、解压时间与对应的编码表。 五、设计概要 统计文本文件中各字符的频度并作为权值生成哈夫曼树，并利用哈夫曼树进 行二进制编码。 压缩部分 1. 构造哈夫曼树，对其进行前缀编码 （1）扫描待压缩文件，得出各字符出现频率。 （2）根据给定的 n 个权值{W1,W2,...Wn}构成 n 棵二叉树的集合 F={T1，T2，…， Tn}，每棵二叉树 Ti 中只有一个带权为 Wi 的根节点，其左右子树均空。 （3）在 F 中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二 叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。 （4）在 F 中删除这两棵树。同时将新得到的二叉树加入 F 中。 重置（2）和（3），直到 F 只含一棵树为止。这棵树便是哈夫曼树。 2. 由 Huffman 树得到各字符前缀编码。 3. 根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩 文件。 4. 处理剩余不到八位部分，写入压缩文件。 5. 将前缀编码及相关信息写入压缩文件。 1
    6. 关闭指针，完成压缩。计算压缩率。 解压部分 1. 读入压缩文件长度和源文件长度。读入前缀编码。 2. 对文件中各字符解码，写入解压文件。 3. 判断解压文件是否完好（对比压缩前文件长度），关闭指针，完成解压。 六、源码及注释 #include #include #include #include #include #include #define N 255 #define M 2*N - 1 void Initiate(); void Compress(); void Uncompress(); void CreateHFMtree(); void CreateHFMcode(); void SaveHFMcode(); void PrintHFMcode(); void PrintHFMtree(); void SaveHFMtree(); //哈夫曼树初始化函数 //压缩文件 //解压文件 //生成哈夫曼树 //生成哈夫曼编码 //保存哈夫曼编码表 //打印哈夫曼编码 //打印哈夫曼树 //保存哈夫曼树 FILE *fp; int flag=0; int n1; int total = 0; clock_t begin,finish; double duration; typedef struct { //文件字节总长 //计时 //字符 //权值 char ch; int weight; int parent,lchild,rchild; char code[N]; }HFMtree; HFMtree tree[M],ex; //哈夫曼树 //ex 为排序时交换所用的临时变量 2
    int main() { int x,n=0; while(1) { system("cls"); printf("--------哈夫曼压缩与解压--------\n\n"); printf("1.载入文件\t"); printf("2.显示哈夫曼编码表\n"); printf("3.显示哈夫曼树\t"); printf("4.压缩文件\n"); printf("5.解压文件\t"); printf("6.退出\n\n"); printf("---------------------------------\n"); printf("请输入功能号 1-6:"); scanf("%d", &x); switch(x) { case 1: Initiate(); if(flag==1){ CreateHFMtree(); CreateHFMcode(); SaveHFMcode(); SaveHFMtree(); //生成哈夫曼树 //生成哈夫曼编码 //保存哈夫曼编码 //保存哈夫曼树 } system("pause"); break; case 2: system("cls"); PrintHFMcode(); system("pause"); break; case 3: system("cls"); PrintHFMtree(); system("pause"); break; case 4: begin = clock(); 3
    Compress(); finish = clock(); duration = (double)(finish - begin) / CLOCKS_PER_SEC; printf("压缩用时%lf 秒\n",duration); system("pause"); break; case 5: Uncompress(); system("pause"); break; case 6: return 0; default: fflush(stdin); } } return 0; } void Initiate() { //记录文本中的字符 char filename1[20]; char c; int i; getchar(); printf("请输入需要被压缩的文件的路径:"); gets(filename1); fp=fopen(filename1,"rb"); if(fp==NULL){ //以只读方式打开二进制文件 printf("\n 文件打开失败! "); return; } while(!feof(fp)){ fread(&c,1,1,fp); tree[c].weight++; total++; } total--; tree[c].weight--; for(i=0;i
    tree[i].ch=0; tree[i].parent=-1; tree[i].lchild=-1; tree[i].rchild=-1; } flag=1; } void CreateHFMtree() { int i, min, n, m, j, temp; for(i=0;itree[j].weight){ temp=j; min=tree[j].weight; continue; } } tree[i].weight=tree[temp].weight; tree[temp].parent=i; tree[i].lchild=temp; min=10000000; for(j=0;j
    continue; if(min>tree[j].weight){ temp=j; min=tree[j].weight; continue; } } tree[i].weight+=tree[temp].weight; tree[i].rchild=temp; tree[temp].parent=i; } } void CreateHFMcode() { int i, j, f, n; n = n1; for(i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料