计算机程序设计综合实验姓名：张起学号：201332010615班级：自动化六班撰写时间：2015年7月8日A部分一. 需求分析（一）设计要求：1、编写压缩程序, 为一个文本文件进行Huffman编码, 对其进行压缩, 将压缩后的结果存储为文件。

2、编写解压程序, 将你压缩后的文件解压缩还原为原始文件。

3、程序要能够处理较大的文本文件, 例如提供的“kjv.txt”。

（二）问题分析：本课题是利用哈夫曼编码思想，设计对一个文本文件（kjv.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（kjv.txt）。

在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。

哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。

在文本文件中多采用二进制编码。

为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。

设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。

若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。

为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。

哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。

统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。

利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。

则概率越大的节点，路径越短。

哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。

哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。

总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。

其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。

二. 设计1. 技术路线1、输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。

第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。

若打不开，则继续输入。

2、读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率。

3、根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。

4、由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。

读取文件，依次将每个字符用他们的编码表示，即完成一次编码。

5、解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。

从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。

将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件图1-1 哈夫曼设计思想2. 流程图与结构图（1）函数流程图主要步骤：编码和解码核心算法----huffman算法：1、根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。

2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。

3、在F中删除这两棵树，同时将所得到的二叉树加入F中。

4、重复（2）(3),直到F中只含一棵树为止。

这棵树便是Huffman树。

Huffman树可用于构造代码总长度最短的编码方案。

为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL（树的带权路径长度）不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。

权值越大的结点离根越近的二叉树才是最优二叉树（huffman树）。

按照上面的算法，则可按照下面图的构造过程生成huffman树。

图1-2 Huffman树产生流程图1-3 Hufffman编码流程图1-4 Hufffman编码流程三. 测试以下是我在上机过程中遇到的一些问题及解决方案开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就huffman编码是采用等长编码还是采用不等长问题，采用不登长编码要避免译码的二义性或多义性。

假设用0表示字符D,用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。

因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。

符合此要求的编码叫做前缀编码。

显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。

为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。

因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的 huffman树的问题。

基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误,修正后编译通过。

在课程设计过程中，我选择了《Huffman的压缩和解压缩》这一课题，虽然这个课题所涉及的知识自己不太熟悉，属于数据结构与算法的内容，但通过借助书本，自己动手实践，还是掌握了一点关于数据结构的知识，通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，利用哈夫曼编码的思想方法，熟练掌握哈夫曼编码的过程。

创建二叉树的方法和二叉树的存储结构，知道压缩文件是如何进行的，解压缩即为它的逆过程。

程序的模块化结构尤其重要，应掌握各个模块间的逻辑关系和整体程序的结构。

其实在这次课程设计中遇到很多问题，第一就是知识不熟悉，必须从最基本的书本知识看起，通过查阅资料，使我对程序的一些算法有了最基本的了解。

其次通过网络资源使我了解的知识更加丰富，增强了我对网络资源的检索能力，使我能够更好的应用网络资源来完成自己需要完成的任务。

所以课程设计不仅能培养我们的专业知识，而且还能培养我们的动手能力，使我们以后能够更加适应社会的发展。

通过这次课程设计，使我的自学能力有所提高，让我知道了怎么去熟练掌握知识并且能够很好的掌握它。

同时也增强我的独立思考能力和动手能力；通过编写程序代码和调试运行，我们可以逐步积累调试程序的经验，逐渐培养我们的编程能力和利用计算机解决实际问题的能力。

课程设计为我们提供了一个自己动手实践的平台。

另一方面，在课程设计的过程中，使我明白了面向对象与面向对象的差别。

在面向对象过程中，类的设计是至关重要的，类设计好了等于程序就成功了一半，所以这次的课程设计帮助我复习了这一学期面向对象课程的学习，刚好可以弥补这一学期面向对象学习的不足。

这次课程设计不但使我掌握了一些知识，更重要的是使我认识到了作为程序员的艰辛和辛苦。

一个星期面对着电脑，在你面前只有一行行的代码，在你的耳旁只有键盘的敲击声和点击鼠标的声音，说实话确实很无聊也很辛苦。

但当自己看到自己编写的程序顺利通过的时候，心里的成就感就油然而生，心中的疲倦也消失了，我想，当程序员看到自己的程序能够编译成功的话，也是这种感觉吧！虽然这次课程设计结束了，但我们学习C++等语言的步伐不能停止，在今后的学习过程中，我会更加努力，争取在今后的课程中学得更好，下次的课程设计能够更加成功。

（1）程序运行主界面如图4所示图1-5 程序主界面（2）编码界面图1-6 编码界面若用户想要对某一文件进行压缩，则按主界面的提示按“1”，然后界面提示输入进行压缩操作的文件名，输入完成后按回车键，此时界面会提示输入压缩后文件的文件名，输入完成后再按回车键，便可完成编码，同时会显示出各字符的哈夫曼编码，系统也会提示用户压缩文件过程结束（3）解码界面图1-7 解码界面若用户想对某一压缩文件进行解压操作，则按主界面的提示按“2”，然后界面提示输入进行解压操作的文件名，完成输入后按回车键，此时界面会提示输入解压后的文件的文件名，输入完成后再按回车键，便可完成译码，系统提示用户还原文件过程结束。

经过测试，程序运行稳定，符合实验要求。

B部分一. 需求分析编写程序, 实现扫雷游戏, 功能上模仿winows自带的扫雷游戏（1）鼠标左击排雷，右击插小旗，打问号；（2）方格里面的数字表示方格周围的雷数；（3）能够显示未标记雷数和游戏用时；（4）雷区上面的小脸可以变化，显示微笑，惊讶，痛苦，胜利。

在任何情况下单击小脸可以重新开始游戏；（6）排行榜功能，扫雷成功时候，根据游戏用时更新排行榜。

二. 设计1. 技术路线1、扫雷游戏是很经典也很有趣的一款游戏，这次的游戏程序设计要求设计出功能与原游戏相近的一款游戏，首先定义变量和类要画出游戏方格以及位图；然后设置随机布雷以保证每次重新开始游戏都有不同的雷区地图；另外定义鼠标左击扫雷，左击标记周围埋雷情况，右击奇数次排雷偶数次取消上次排雷，以及扫雷第一次左击不能扫到雷。

2、流程规划大致上可以分为三个部分，分别为：画面初始、游戏者按下第一个方块和为非地雷方块时展开。

3、画面初始时，以游戏者最后一次设定的地雷区大小为范围画出地雷区，当游戏者按下第一个方块时产开始计时，接着就是如何判断按下的方块是非地雷时的处理，这也是整个游戏的技术核心，我们可以通过递归的观念来检查周边的方块是否含有地雷及是否继续往外翻开，当鼠标指针对准未翻开的方块按下左键时即表示翻开方块，当鼠标指针对准未翻开的方块按下右键时即表示标示或疑示地雷，反复按下右键则方块会以未标示→标示→疑似三者关系不断循环。