数据结构实习报告

《数据结构实习报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、孫趕试针報告%4/20131002072槐级專号,，116131-12姓名/陶剑浩指务教师Z吴亮成错，肀®地质史嗲r我姝；信息工祛嗲淀2015專1用目录一、软件压缩/解压缩软件Szip（Huffman算法及应用）21.需求规格说明22.总体分析与设汁23.编码54.程序及算法分析55.d、@76.附录7二、电话簿软件的实现（动态查找表算法的应用）171.需求规格说明172.总体分析与设计183.194.程序及算法分析195.雌206.20三、管道铺设施工的最佳方案选择（选做，加分题）391.需求规格说叨392.总体分析与设计393.

2、^55414.程序及算法分析415.J、结-436.隱43，⑽51五、参考资料51软件压缩/解压缩软件Szip（Huffman算法及应用）1.需求规格说明利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现冇文件进行编码行成新的文件，也就是压缩。在文件使川吋，再对压缩文件进行解压缩，也就是译码，复原原奋文件。试为完成此功能，写一个压缩/解压缩软件。2.总体分析与设计（1）设计思想：哈夫曼树乂称最优二叉树，是带权路径长度最小的二叉树。在文本文件中多采用二进制编码。为了使文件从可能的

3、缩短，可以对文件屮每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的人小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树巾的左右分支各代表‘0’和‘r，wd从根节点到什子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。统计字符中每个字符在文件中出现的T•均概率（概率越大，要求编码越短）。利川哈夫曼树的特点：权越大

4、的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的失部开始，顺序匹配成功的部分替换成相应的字符，直至二进制转换为字符序列。哈夫曼用于文件解压缩的基础是在压缩二进制代码的同吋还必须存储相应的编码，这样就吋以根裾存储的哈夫曼编码对压缩代码进行压缩。首先要打幵要压缩的文木文件并读出其字符出现的频率，以W为权位构建哈夫曼树。W次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。（2

5、）设计表示：//huffman树的结点结构体typedefstructHTnode{longweight;//记录结点的权值intparent;//记录结点的双亲结点位置intlchild;/结点的在孩子intrchild;//结点的右孩子int*code;//kl录该结点的huffman编码intcodelen;//记录该结点huffman编码的长度//初始化结点，令其权值为无穷大，无双亲及左心孩子HTnode(){weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}JHTnod

6、e;//huffman树类及其函数classhuffmanTree{public:huffmanTreeQ;virtual〜huffmanTreeQ;boolcount(char*input);//压缩时统计各7•符出现的次数，将其写入对应结点的权值voidcreated;//AR缩吋根据各结点的权值构造:huffman树voidcodef);//压缩时利用huffman树汁算甸个字符的huffman编码voidprintcodeQ;//列出每个字符的huffman编码voidaddbitfintbit);//压缩吋对一个未满8个b

7、it的byteH1加入一个bitvoidresetbyteQ;//将byte淸空boolcompress(char*input,char*output);//压缩闲数，成功返回true失败falsebooldecompress(char*input,char*output);//恢复闲数，成功返回true失败falsevoidcompare(char*input,char*output);//将原文件与压缩后的文件比较voidcompare2(char*input,char*output);//将原文件与恢复•的文件比较privat

8、e:introot;//记录根结点的位置intleafnum;//记录不同字符的个数HTnodeHT[leaf*2-l];//HTnode绍构的数组，川来表示huffman树，树的最人绍点个数不会超过leaf*2-lcharbyte;