数据结构课程设计 哈弗曼压缩+纸牌游戏

1.纸牌游戏 任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；...再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 题目比较简单。但用了MFC的一些知识，实现了图形化，比较形象。 2.哈弗曼压缩 实现哈弗曼压缩及解压缩功能，并计算压缩前后文件占用空间比 模型建立与题目分析 压缩： 以二机制可读形式打开源文件，以二进制可写形式打开压缩目标文件。每次从源文件读取八个比特（一字节），作为一个ASCII码，并统计所有出现的字节的频率，将字节作为哈夫曼数的叶子结点插入到一个链表中。然后根据链表建立哈夫曼树，按照哈夫曼算法对所有出现的字节编码。然后重新从头开始读源文件，每次读入一字节，从哈夫曼树相应叶子结点移到树的根结点，在找的过程中，把其哈夫曼编码存入一个栈，把栈中所有元素（0或1）写到缓冲区，如果缓冲区比特数到8了，则将缓冲区的8个比特（一个字节）写入压缩文件。如果最后缓冲区不到8比特，则在低位补零，补齐8位后写入压缩文件。 解压： 以二进制可读形式打开解压文件，以二进制可写形式打开解压目标文件。每次从解压文件读一个字节，放入缓冲区，然后从缓冲区每次读一个比特。在建立的哈夫曼树中，从根结点开始，取出的比特为0则取左孩子，为1取右孩子，直至到叶子结点，把叶子结点的字节（ASCII码）写入解压目标文件。读到缓冲区为空时，再读入一个字节，重复上述操作，直到读完压缩文件。 模型实质： 以二进制读取文件。从源文件每次读一个字节（8比特），并统计所有出现字节的频率，根据频率对所有字节以频率作为权值建立哈夫曼树，对每个字节重新编码。根据新的编码进行编码译码。 算法设计与分析 如果已知出现字符的出现频率，将较短的比特串分给高频字符，将较长的比特串分给低频字符，则会到压缩文件的目的。哈夫曼编码就是利用这一点，以字符作为叶子结点，以其频率作为权值，建立最优二叉树。 一 下面先重点讨论一下建立哈夫曼数的算法。哈夫曼算法： 根据给定叶子结点及其权值（这里即字符及其频率）构成二叉树的集合，每个叶子结点作为一棵树的根结点。 在二叉树集合中选取根结点权值最小的树作为左右子树构造新的二叉树，且新二叉树的权值为左右子树权值之和。 从二叉树集合中删除这两棵树，将新构造的树加入集合 4 . 重复2，3，直至二叉树集合中只有一棵树。