数据结构实习报告

《数据结构与算法》课程设计报告学号：20131002072班级序号：116131-12姓名：陶剑浩指导教师：吴亮成绩：中国地质大学（武汉）信息工程学院2015年1月中国地质大学数据结构实习报告陶剑浩-1-目录一、软件压缩/解压缩软件Szip（Huffman算法及应用）.................................................21．需求规格说明..............................................................................................................22．总体分析与设计..........................................................................................................23．编码..............................................................................................................................54．程序及算法分析..........................................................................................................55．小结..............................................................................................................................76．附录..............................................................................................................................7二、电话簿软件的实现（动态查找表算法的应用）..........................................................171．需求规格说明............................................................................................................172．总体分析与设计........................................................................................................183．编码............................................................................................................................194．程序及算法分析........................................................................................................195．小结............................................................................................................................206．附录............................................................................................................................20三、管道铺设施工的最佳方案选择（选做，加分题）......................................................391．需求规格说明............................................................................................................392．总体分析与设计........................................................................................................393．编码............................................................................................................................414．程序及算法分析........................................................................................................415．小结............................................................................................................................436．附录............................................................................................................................43四、总结..................................................................................................................................51五、参考资料..........................................................................................................................51中国地质大学数据结构实习报告陶剑浩-2-一、软件压缩/解压缩软件Szip（Huffman算法及应用）1．需求规格说明利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。2．总体分析与设计（1）设计思想：哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成功的部分替换成相应的字符，直至二进制转换为字符序列。哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。（2）设计表示：//huffman树的结点结构体typedefstructHTnode{longweight;//记录结点的权值intparent;//记录结点的双亲结点位置中国地质大学数据结构实习报告陶剑浩-3-intlchild;/结点的左孩子intrchild;//结点的右孩子int*code;//记录该结点的huffman编码intcodelen;//记录该结点huffman编码的长度//初始化结点，令其权值为无穷大，无双亲及左右孩子HTnode(){weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;//huffman树类及其函数classhuffmanTree{public:huffmanTree();virtual~huffmanTree();boolcount(char*input);//压缩时统计各字符出现的次数，将其写入对应结点的权值voidcreate();//压缩时根据各结点的权值构造huffman树voidcode();//压缩时利用huffman树计算每个字符的huffman编码voidprintcode();//列出每个字符的huffman编码voidaddbit(intbit);//压缩时对一个未满8个bit的byte中加入一个bitvoidresetbyte();//将byte清空boolcompress(char*input,char*output);//压缩函数,成功返回true失败falsebooldecompress(char*input,char*output);//恢复函数,成功返回true失败falsevoidcompare(char*input,char*output);//将原文件与压缩后的文件比较voidcompare2(char*input,char*output);//将原文件与恢复后的文件比较private:introot;//记录根结点的位置intleafnum;//记录不同字符的个数HTnodeHT[leaf*2-1];//HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1charbyte;//压缩文件时用来缓冲bit的变量intbitsnum;//byte中bit的个数intlacknum;//压缩到最后byte中的bit不满8个时填充的0的个数};主程序的流程及模块间关系：主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：1:压缩函数boolcompress(char*input,char*output)2:恢复函数booldecompress(char*input,char*output)3:恢复文件与原文件的对比函数voidcompare2(char*input,char*output)中国地质大学数据结构实习报告陶剑浩-4-并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。（3）详细设计表示：核心算法----huffman算法：根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树