计算机程序设计综合实验

1、计算机程序设计综合实验姓名：张起学号：201332010615班级：自动化六班撰写时间：2015年7月8日A部分一. 需求分析（一）设计要求：1、编写压缩程序, 为一个文本文件进行Huffman编码, 对其进行压缩, 将压缩后的结果存储为文件。2、编写解压程序, 将你压缩后的文件解压缩还原为原始文件。3、程序要能够处理较大的文本文件, 例如提供的“kjv.txt”。（二）问题分析：本课题是利用哈夫曼编码思想，设计对一个文本文件（kjv.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（kjv.txt）。 在了解哈夫曼压缩解压缩原理

2、之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。 在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表0和1,则从根节点到叶子节点所经历的路径分支的0和1组成的字符串，为该节点对应字符的哈夫曼编码。 统计字符中每个字符

3、在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。 哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，

4、以外还有存储相应的哈夫曼编码，为解压缩做准备。二. 设计1. 技术路线1、输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的 项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。2、读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。3、根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huff

5、man树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。4、由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。5、解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是1时，指针指向当前所指结点的右孩子，当读取的字符是0时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结

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

7、;在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。 3、 在F中删除这两棵树，同时将所得到的二叉树加入F中。 4、 重复（2）(3),直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。 为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL（树的带权路径长度）不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全

8、二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优二叉树（huffman树）。按照上面的算法，则可按照下面图的构造过程生成huffman树。图1-2 Huffman树产生流程图1-3 Hufffman编码流程图1-4 Hufffman编码流程三. 测试以下是我在上机过程中遇到的一些问题及解决方案 开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就 huffman编码是采用等长编码还是采用不等长问题，采用不登长编码要避免译码的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“01”，并译到字符0时，是立即译出对应的字符D，还是接着与

9、下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。 为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于

10、文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的 huffman树的问题。 基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些语法错误,修正后编译通过。在课程设计过程中，我选择了Huffman的压缩和解压缩这一课题，虽然这个课题所涉及的知识自己不太熟悉，属于数据结构与算法的内容，但通过借助书本，自己动手实践，还是掌握了一点关于数据结构的知识，通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，利用哈夫曼编码的思想方法，熟练掌握哈夫曼编码的过程。创建二叉树的方法和二叉

11、树的存储结构，知道压缩文件是如何进行的，解压缩即为它的逆过程。程序的模块化结构尤其重要，应掌握各个模块间的逻辑关系和整体程序的结构。其实在这次课程设计中遇到很多问题，第一就是知识不熟悉，必须从最基本的书本知识看起，通过查阅资料，使我对程序的一些算法有了最基本的了解。其次通过网络资源使我了解的知识更加丰富，增强了我对网络资源的检索能力，使我能够更好的应用网络资源来完成自己需要完成的任务。所以课程设计不仅能培养我们的专业知识，而且还能培养我们的动手能力，使我们以后能够更加适应社会的发展。通过这次课程设计，使我的自学能力有所提高，让我知道了怎么去熟练掌握知识并且能够很好的掌握它。同时也增强我的独立思

12、考能力和动手能力；通过编写程序代码和调试运行，我们可以逐步积累调试程序的经验，逐渐培养我们的编程能力和利用计算机解决实际问题的能力。课程设计为我们提供了一个自己动手实践的平台。另一方面，在课程设计的过程中，使我明白了面向对象与面向对象的差别。在面向对象过程中，类的设计是至关重要的，类设计好了等于程序就成功了一半，所以这次的课程设计帮助我复习了这一学期面向对象课程的学习，刚好可以弥补这一学期面向对象学习的不足。这次课程设计不但使我掌握了一些知识，更重要的是使我认识到了作为程序员的艰辛和辛苦。一个星期面对着电脑，在你面前只有一行行的代码，在你的耳旁只有键盘的敲击声和点击鼠标的声音，说实话确实很无聊

13、也很辛苦。但当自己看到自己编写的程序顺利通过的时候，心里的成就感就油然而生，心中的疲倦也消失了，我想，当程序员看到自己的程序能够编译成功的话，也是这种感觉吧！虽然这次课程设计结束了，但我们学习C+等语言的步伐不能停止，在今后的学习过程中，我会更加努力，争取在今后的课程中学得更好，下次的课程设计能够更加成功。（1）程序运行主界面如图4所示图1-5 程序主界面（2）编码界面图1-6 编码界面若用户想要对某一文件进行压缩，则按主界面的提示按“1”，然后界面提示输入进行压缩操作的文件名，输入完成后按回车键，此时界面会提示输入压缩后文件的文件名，输入完成后再按回车键，便可完成编码，同时会显示出各字符的哈

14、夫曼编码，系统也会提示用户压缩文件过程结束（3）解码界面图1-7 解码界面若用户想对某一压缩文件进行解压操作，则按主界面的提示按“2”，然后界面提示输入进行解压操作的文件名，完成输入后按回车键，此时界面会提示输入解压后的文件的文件名，输入完成后再按回车键，便可完成译码，系统提示用户还原文件过程结束。经过测试，程序运行稳定，符合实验要求。B部分一. 需求分析编写程序, 实现扫雷游戏, 功能上模仿winows自带的扫雷游戏（1）鼠标左击排雷，右击插小旗，打问号； （2）方格里面的数字表示方格周围的雷数；（3）能够显示未标记雷数和游戏用时；（4）雷区上面的小脸可以变化，显示微笑，惊讶，痛苦，胜利。在

15、任何情况下单击小脸可以重新开始游戏； （6）排行榜功能，扫雷成功时候，根据游戏用时更新排行榜。二. 设计1. 技术路线1、扫雷游戏是很经典也很有趣的一款游戏，这次的游戏程序设计要求设计出功能与原游戏相近的一款游戏，首先定义变量和类要画出游戏方格以及位图；然后设置随机布雷以保证每次重新开始游戏都有不同的雷区地图；另外定义鼠标左击扫雷，左击标记周围埋雷情况，右击奇数次排雷偶数次取消上次排雷，以及扫雷第一次左击不能扫到雷。2、流程规划大致上可以分为三个部分，分别为：画面初始、游戏者按下第一个方块和为非地雷方块时展开。3、画面初始时，以游戏者最后一次设定的地雷区大小为范围画出地雷区，当游戏者按下第一个

16、方块时产开始计时，接着就是如何判断按下的方块是非地雷时的处理，这也是整个游戏的技术核心，我们可以通过递归的观念来检查周边的方块是否含有地雷及是否继续往外翻开，当鼠标指针对准未翻开的方块按下左键时即表示翻开方块，当鼠标指针对准未翻开的方块按下右键时即表示标示或疑示地雷，反复按下右键则方块会以未标示标示疑似三者关系不断循环。游戏者可以通过地雷区内的数字提示了解以数字为中心的其周边八个方格内所含的地雷数，假若翻开的方块显示数字“3”，则表示以其为中心的周边方块内藏有3个地雷。当按下的方块不是地雷，且周边八个方块也都没有地雷时，方块会以被翻开方块的八个方向将空白方块翻开。2. 流程图与结构图（1）流程

17、设计流程规划大致上可以分为三个部分，分别为：画面初始、游戏者按下第一个方块和为非地雷方块时展开。是是开始依照使用者初始设定等待按键左键键右键1 布置地图2 启动计时器显示分数结束进行递归扫雷否否是否是否第一次按下按下方块最终是否为地图是否最高分扫雷英雄榜显示方块是画面初始时，以游戏者最后一次设定的地雷区大小为范围画出地雷区，但此时并未产生地雷。当游戏者按下第一个方块时产生地雷资料并启动定时器，为何在游戏者按下第一个方块才产生地雷资料呢？其主要的用意在于不要让游戏者第一次就踩到地雷，这样在某种程度上可以提高游戏者游玩的气氛。接着就是如何判断按下的方块是非地雷时的处理，这也是整个游戏的技术核心，我

18、们可以通过递归的观念来检查周边的方块是否含有地雷及是否继续往外翻开。图2-1 整体流程规划图1、游戏的操作方面主要以鼠标为主，鼠标左键按下事件的主要作用是为了点击用户认为不是地雷的方块，当鼠标左键点下后，点下的方块将从为探测状态转化为已探测状态，并可能会连带打开周围的方块。2、鼠标右键按下事件主要有两个作用，当用户对为探测方块第一次按下该时，该方块上将出现一个小红旗，代表确认该方块是地雷，若对此方块再次进行右键单击，则图标变为一个问号，表示此处是否有地雷还有待商榷，对于一些比较难解决的雷区，使用该图标有助于玩家更好的进行推理判断。图2-2 布雷流程（2）模块划分扫雷游戏共由四个类和一个模块组成

19、，帮助对话框类背景音乐播放模块英雄榜对话窗口类扫雷窗口类主界面对话框类扫雷游戏图2-4 模块划分1、 主界面对话框类：主要负责主界面、菜单及各个窗口类对象的创建和调用等处理。2、 扫雷窗口类：主要负责接收玩家鼠标输入的打开格子位置、格子变换、花费时间及扫雷格子的显示等处理。3、 英雄对话框类：主要负责游戏等级记录的更新。4、 背景音乐播放模块：主要负责游戏中背景音乐的播放。5、 帮助类对话框类：主要负责帮助提示的显示及其他辅助信息。扫雷游戏的主界面设计如图2-5所示，菜单设计如图2-6所示图2-5 扫雷游戏主界面设计图2-6 扫雷游戏菜单设计三. 测试扫雷游戏是WINDOWS系统自带的一个娱乐

20、性的小游戏，为了确保本游戏能够正常运行，需要在发布之后做一次较全面的测试。 扫雷游戏的目标是尽快找到雷区中的所有地雷，而不许踩到地雷。如果挖开的是地雷，您将输掉游戏。 扫雷游戏在程序运行后生成指定的地雷，在鼠标左键点击下寻找地雷，右键点击下标记地雷，点击笑脸的标记开始重新游戏，并给出胜利和失败的条件：标出所有的地雷和左键点中地雷。 在游戏菜单上，单击开始游戏或者，单击游戏区中的任何方块，启动计时器。通过单击即可挖开方块。如果挖开的是地雷，则您输掉游戏。如果方块上出现数字，则表示在其周围的八个方块中共有多少颗地雷。要标记您认为可能有地雷的方块，请右键单击它。 游戏区包括雷区、地雷计数器和计时器。 经过一些简单的步骤的测试，证明本游戏具有相当的稳定性。图2-7 扫雷游戏主界面和菜单图2-8 鼠标单击后事件图2-9 失败提示对话框图2-10 游戏胜利界面在本次实习过程中碰到的编译、连接的错误主要有：缺少变量定义，定义位置不正确、语法错误、注释的位置等。（1）缺少变量定义，定义位置不正确；由于该程序相对来讲稍有些长，前后有些变量不容易联系起来，但是在错误信息的提示下一般还是很容易找到。不过需要注意的是在定义的时候有些函数使用同样的变量名而表示不同的作用，因而使用要很小心，定义及定义的位置要特别留意。为减少这样的错误我后来还是用不同的