《数据结构》课程设计模板.doc

《《数据结构》课程设计模板.doc》由会员分享，可在线阅读，更多相关《《数据结构》课程设计模板.doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计班级 学号 姓名 指导教师 时间： 年 月 日 至 年 月 日成绩 指导教师签字 年 月 日数据结构课程设计凌 璐一. 题目：压缩软件二. 算法思想描述：1.算法概述：首先输入需要压缩的文件名，对该文件中的各个字符出现的频度进行统计，然后进行Huffman编码，再读入源文件，将源文件翻译成Huffman编码文件，输出到文件2.txt，最后读入2.txt文件，将Huffman编码文件翻译成文本文件，输出到3.txt。总体思路如图1所示。扫描该文件计算压缩比：M/（N*8）源文件统计各个字符出现的次数，存放在数组a128内，并把源文件的字符数存放到N里创建Huffman树，存放在自

2、定义的存储结构closedge500内对叶子节点进行编码，编码存放在二维数组hd128100内扫描源文件，将源文件翻译成Huffman编码文件2.txt3.txt扫描2.txt，将Huffman编码文件翻译成文本文件统计2.txt的数字的个数，存放到M中 图12.算法具体分析（1） 入需要压缩的文件名（例如：e:11.cpp,转义字符表示）（2） 对该文件中的各个字符进行统计while(!feof(fp)fscanf(fp,%c,&c);ac+; 数组里存放的是该字符出现的次数，数组的下标即该字符对应的ASCII值 判断ai是否为0，对不为0的进行Huffman编码，数组值即权值（3） 根据H

3、uffman算法，建立Huffman树。（4） 给叶子节点进行编码，先用一个临时的数组来存放编码，然后把该字符的编码存入一个二维数组，直至所有的叶子结点编码完成,编码存放在二维数组hd128100内。（5） 读入源文件的内容，将字符所对应的编码（调用数组hd128100）输出到2.txt文件里。（6） 读入2.txt文件，若读入0则在Huffman树的左子树上找，否则在右子树上找,直到找到叶子结点(Huffman树存放在自定义的存储结构closedge500内)，输出叶子结点的字符到文件3.txt，直至翻译完2.txt所有内容。（7） 计算压缩比：Huffman编码文件字符数/源文件的字符数。

4、三程序结构creat_huffman()函数encode（）函数decode（）函数select()函数调用调用调用调用main()函数四 实验结果与分析上述程序在Visual C+ 6.0 环境下加以实现，经过多次的测试，程序运行正确。例如：输入文件e:11.cpp，运行结果如图2，图中显示源文件的字符数和压缩后字符数，以及压缩比。成功将源文件e:11.cpp压缩到文件2.txt(图3)里，再还原到文件3.txt。通过比较3.txt与源文件，结果一样！图2图3五体会通过这次课程设计，我有很深的体会，具体如下：1. Huffman树的建立，编码，译码有了更深层次的理解。2. 文件的打开，关闭，

5、读入，输出语句比较熟悉了。3. 统计文件中字符的个数时，根据所要统计的字符的特征（ASCII值从0到127），可以定义一个数组a128, 数组的下标即该字符对应的ASCII值，扫描源文件，扫到哪个字符对应的数组值+1，即ac+（c为字符）,最终数组里存放的是对应字符出现的次数，这样不但语句简洁，而且十分明了。4. 程序应用更广泛，比如压缩文件，只要输入文件的路径和名称，就可以对其进行压缩，而不是仅局限于某个特定文件。5. 输入文件名的时候，路径中的，应该写成(转义字符表示)，否则系统将默认和它后面的字符组成转义字符，这样就错了。6. 对文件的压缩也有了初步的了解，2.txt是Huffman编码文件，如果把0、1看成字符，那么2.txt文件的字符数增加了，如果把它看成位（bit），若一个字符对应的编码小于8位这样文件就压缩了。7. 从用户角度出发来编写程序，使结果尽量简洁明了。