数据结构课设-用哈夫曼实现软件压缩

-.z.-----总结资料**师范大学"数据构造"课程设计报告**：**：学院：计算机科学与技术学院题目：排序算法比拟与压缩软件的实现指导教师：二〇一四年九月一日目录必做题3一、设计内容3二、设计思想描述31希尔排序32快速排序33堆排序44二路归并排序7三、程序构造81类设计82主程序设计83流程图9四、系统环境与程序测试案例9五、设计中遇到的问题及解决方案121测时间的函数不准确12其他测试运行时间的方式：132什么是"真随机〞，什么是"伪随机〞？143如何根据文档构造图生成目录14六、参考文献15选做题15一、设计内容15二、设计思想描述151Huffman树与Huffman编码152Huffman算法的思想153现有的压缩软件及其压缩比16三、程序构造171类设计172主程序设计183流程图20四、系统环境与程序测试案例20五、设计中遇到的问题及解决方案23六、收获与体会24七、参考文献24必做题设计内容编程实现希尔、快速、堆排序、归并排序算法。要求随机产生10000个数据存入磁盘文件，然后读入数据文件，分别采用不同的排序方法进展排序，并将结果存入文件中。设计思想描述1希尔排序希尔排序是对直接插入排序的改良。根本思想是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组，所有距离为d1的倍数的记录放在同一个组中。先在各组内进展直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进展直接插入排序为止。该方法实质上是一种分组插入方法。举例数据序列为〔12，5，9，20，6，31，24〕，对该数据序列进展希尔排序：12125 9 20 6 3124125 9206 312456 9122024 31初始键值序列第一趟排序结果〔d1=3〕〕第二趟排序结果〔d2=1〕〕具体代码见Sort代码.t*t！2快速排序根本思想是：通过一趟排序将要排序的数据分割成独立的两局部，其中一局部的所有数据都比另外一局部的所有数据都要小，然后再按此方法对这两局部数据分别进展快速排序，整个排序过程可以递归进展，以此到达整个数据变成有序序列。举例数据序列为〔12，5，9，20，6，31，24〕，对该数据序列进展快速排序：一次划分12125 9 20 6 31 24125 9 20 6 31 24125 9 20 6 31 2465 9 20 1231 2465 9 20 1231 2465 9 20 1231 2465 9 12 2031 24对轴值两侧分别进展快速排序665 965 9569 592031 242031 2431 24242431 3堆排序堆排序〔Heapsort〕是指利用堆这种数据构造所设计的一种排序算法。堆是一个近似完全二叉树的构造，并同时满足堆性质：即子结点的键值或索引总是小于〔或者大于〕它的父结点。举例数据序列为〔12，5，9，20，6，31，24〕，对该数据序列进展堆排序：初始：512初始：512924206311调整成小根堆659242012312525与24换624952012313调整成小根堆126952024311231195202465调整成小根堆1293152024646与31换121224195203167调整成小根堆2093152412669与24换202024195123169调整成小根堆24931524206812与24换24319512206820与31换10调整成小根堆31241124和31换951220631241212排序结果9512206244二路归并排序将两个按值有序序列合并成一个按值有序序列，则称之为二路归并排序。〔1〕归并子算法：把位置相邻的两个按值有序序列合并成一个按值有序序列。voidMerge(intr[],intr1[],ints,intm,intt); //一次归并算法〔2〕一趟归并扫描子算法：将参加排序的序列分成假设干个长度为t的，且各自按值有序的子序列，然后屡次调用归并子算法merge将所有两两相邻成对的子序列合并成假设干个长度为2t的，且各自按值有序的子序列。假设*一趟归并扫描到最后，剩下的元素个数缺乏两个子序列的长度时：•假设剩下的元素个数大于一个子序列的长度t时，则再调用一次归并子算法merge将剩下的两个不等长的子序列合并成一个有序子序列•假设剩下的元素个数小于或者等于一个子序列的长度t时，只须将剩下的元素依次复制到前一个子序列后面。voidMergePass(intr[],intr1[],intn,inth); //一趟归并排序算法〔3〕二路归并排序算法：将参加排序的初始序列分成长度为1的子序列使用MergePass函数进展第一趟排序，得到n/2个长度为2的各自有序的子序列〔假设n为奇数，还会存在一个最后元素的子序列〕，再一次调用mergePass函数进展第二趟排序，得到n/4个长度为4的各自有序的子序列，第i趟排序就是两两归并长度为2^(i-1)的子序列得到n/(2^i)长度为2^i的子序列，直到最后只剩一个长度为n的子序列。由此看出，一共需要log2n趟排序，每一趟排序的时间复杂度是O(n)。voidMergeSort1(intr[],intr1[],intn); //归并排序非递归算法举例数据序列为〔12，5，9，20，6，31，24〕，对该数据序列进展堆排序：1212592063124512920631245912206243156912202431程序构造1类设计本程序中只含有一个类，即测执行时间的类CTimer：classCTimer //测执行时间的类{public: CTimer() { QueryPerformanceFrequency(&m_Frequency); Start(); } voidStart() { QueryPerformanceCounter(&m_StartCount); } doubleEnd() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); returndouble(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart; } voidShowNow() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); cout<<"TimerCountis:"<<double(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart<<endl; }private: LARGE_INTEGERm_Frequency; LARGE_INTEGERm_StartCount;};2主程序设计Sort.h文件中包含所有排序算法，具体代码见Sort.h文件。test.cpp文件中包含产生随机数，读写文件，main函数和菜单控制程序。函数声明如下：intMenu();voidMainMenuCtrl();voidWriteFile(intn);voidSaveFile(intr[],intn,charfilename[]);voidReadFile(intr[],intn);voidPrint(intr[],intn);测试时间的代码如下：CTimert;t.Start();ShellSort(r,n); //希尔排序cout<<"希尔排序执行时间为:"<<t.End()<<"s"<<endl;3流程图菜单菜单产生随机数并写入文件读文件希尔排序快速排序堆排序归并排序将排序结果写入文件开场完毕系统环境与程序测试案例硬件环境截图如下：软件环境：MicrosoftVisualC++6.0110000个随机数排序220000个随机数排序3100000个随机数排序测试结果数据分析：时间复杂度10000个数据20000个数据100000个数据希尔排序O(n2)0.00276598秒0.0060197秒0.0395745秒快速排序O(n)0.00172446秒0.00374468秒0.021415秒堆排序O(n)0.00263925秒0.00568505秒0.0337188秒非递归的归并排序O(n)0.00174817秒0.00374692秒0.0208593秒递归的归并排序O(n)0.00266666秒0.00581711秒0.0313498秒表1、各种排序执行时间比照表图1、各种排序执行时间比照图由上图得，快速排序和非递归的归并排序的排序效率高，其他3种排序速度较慢。设计中遇到的问题及解决方案1测时间的函数不准确不准确的函数如下：clock_tstart,finish;//定义开场，完毕时间doubleduration; //持续时间//测量一个事件持续的时间start=clock();ShellSort(r,n); //希尔排序finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;//CLK_TCK毫秒CLOCKS_PER_SEC秒cout<<"希尔排序执行时间为:"<<duration<<"ms"<<endl;截图如下：分析：使用clock_tclock()得到的是CPU时间，准确到1/CLOCKS_PER_SEC秒，但实际上会有误差。clock()函数clock()定义于time.h中，clock()返回从程序运行时刻开场的时钟周期数，CLOCKS_PER_SEC定义了每秒钟包含多少了时钟单元数。所以得到的时间差其实是从时钟周期数转换过来的。CPU执行时间=程序所含时钟周期数×时钟周期程序总时钟周期数=程序所含指令条数=此时的CPI是该机器指令集中的所有指令执行所用的平均时钟周期数，是一个平均数，即可近似的认为三次排序时的CPI一样。时钟周期即CPU主频的倒数，为一个定值。所以三次排序下此条件一样。所以得到如下结论：当程序所含的指令条数越多时，此种方法测到的时钟周期数越多，所反映的时间越长，造成了实验结果的不准确。其他测试运行时间的方式：〔1〕GetTickCount()函数：GetTickCount记录了从系统启动时经过的时间，准确到毫秒。在windows下实现(毫秒级)：注意要添加头文件<windows.h>。DWORDdwStart=GetTickCount(); //取windows启动到现在的流逝时间(毫秒)Run_Your_Func(...);//运行你的函数DWORDdwUsed=GetTickCount()-dwStart; //计算该函数所消耗的时间〔2〕对于一般的实时控制，使用GetTickCount()函数就可以满足精度要求，但要进一步提高计时精度，就要采用QueryPerformanceFrequency()函数和QueryPerformanceCounter()函数。这两个函数是VC提供的仅供Windows9*使用的高精度时间函数，并要求计算机从硬件上支持高精度计时器。CTimer类如下：classCTimer //测执行时间的类{public: CTimer() { QueryPerformanceFrequency(&m_Frequency); Start(); } voidStart() { QueryPerformanceCounter(&m_StartCount); } doubleEnd() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); returndouble(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart; } voidShowNow() { LARGE_INTEGERCurrentCount; QueryPerformanceCounter(&CurrentCount); cout<<"TimerCountis:"<<double(CurrentCount.LowPart-m_StartCount.LowPart)/(double)m_Frequency.LowPart<<endl; }private: LARGE_INTEGERm_Frequency; LARGE_INTEGERm_StartCount;};〔3〕写一个测试执行时间的宏#include"window.h"#defineBEGIN_RECORD\{\long____temp_begin_time___;\____temp_begin_time___=::GetTickCount();#defineEND_RECORD(dtime)\dtime=::GetTickCount()-____temp_begin_time___;\}用法:longtim;BEGIN_RECORD被测函数；END_RECORD(tim); //tim就是所求的时间差！2什么是"真随机〞，什么是"伪随机〞？(1)、伪随机数：一方面它是可以预先确定的，并且是可以重复地生产和复制的；一方面它又具有*种随机序列的随机特性。(2)、真随机数：它是相对于伪随机数而言的，不具有规律，但计算机不会产生绝对随机的随机数。MicrosoftVC++产生随机数的原理： Srand()和Rand()函数。它本质上是利用线性同余法，y=a*+b(modm)。其中a，b，m都是常数。因此rand的产生决定于*，*被称为Seed。Seed需要程序中设定，一般情况下取系统时间作为种子。它产生的随机数之间的相关性很小，取值范围是0—32767〔int〕，即双字节〔16位数〕，假设用unsignedint双字节是65535，四字节是4294967295，一般可以满足要求。一样种子下产生的随机寻列是一样的。3如何根据文档构造图生成目录 电子版文档点击"视图〞→"文档构造图〞编成目录，点击可快速，且目录随时能够看到；纸质版文档点击"插入〞→"引用〞→"索引和目录〞。二者前提都要点击"视图〞→"大纲〞，编辑标题级别。参考文献[1]DoubleLi——c++计算代码执行时间的方法〔毫秒级〕：.blogs./lidabo/archive/2013/01/08/2850418.html[2]aaronalan的专栏——GetTickCount()用法：[3]许明吉博客——GetTickCount()函数的作用和用法.blogs./j*soft/archive/2011/10/17/2215366.html选做题设计内容设有一个文本文件A〔可以是C源程序〕，统计该文件中各字符的频率，对各字符进展Huffman编码，将该文件翻译成Huffman编码文件B，再将Huffman编码文件译码成文件C，并对文件A与C进展比拟。设计思想描述1Huffman编码Huffman树是在叶子结点集合确定的前提下，所有可能的二叉树形态中树的带权路径长度最小的二叉树。当Huffman树应用于信息编码领域时，叶子结点被用于表示待编码的符号。将每个结点的左分支记作0，右分支记作1，则每个叶子结点的路径可以用一个0/1串的编码来表示，称为Huffman编码。Huffman编码是一种可变长编码方式，编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。2Huffman算法的思想Huffman算法的思想可以概括为2次扫描。第一次是根据输入的字符计算各个字符的频率，并根据频率给每个字符编码；第二次扫描时对每个输入的字符进展匹配，并把输入的字符转换为编码输出到压缩文件中。为了得到文本中字符出现的频率，一般的做法是扫描整个文本进展统计，编写程序统计文本中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共有256个状态。所以直接向系统静态的申请一个长度为256的整数数组，用于存放相应的频率。得到频率后进展哈夫曼编码，然后将数据输出到文件保存。3现有的压缩软件及其压缩比〔1〕WinZIPZIP是最常见的压缩文件格式，Windows系统已经集成了对ZIP压缩格式的支持。经历过DOS时代的用户可能还记得ARJ格式，它根本就是DOS时代的ZIP，直到ZIP格式出现，以更高的压缩效率取代了ARJ，成为用户的首选。现在大多数操作系统都会集成对ZIP文件的支持，而所有的压缩软件也都会提供对ZIP文件的支持，这些足以表达出ZIP格式的地位。ZIP时代最知名的压缩软件就要数WinZIP了，它几乎是当时每台电脑都必备的软件。直到Windows系统开场集成了对ZIP文件的支持，以及后起之秀RAR格式的出现，使得WinZIP不再是则必要，才让它逐渐淡出了大家的视线。〔2〕WinRARRAR格式的文件压缩率比ZIP更高。同样的文件使用RAR格式进展压缩后得到的大小通常都会比使用ZIP压缩后更小，而用户对文件进展压缩的主要目的就是要减小文件大小以便于网络传输，正巧RAR格式又出现在网络刚刚开场普及之时，所以RAR逐渐取代ZIP的地位也就是情理之中的事了。对RAR文件进展压缩或者解压缩，首选的软件当然是WinRAR。与之前的WinZIP一样，它几乎也是现在每台电脑都必装的软件。图2WinZip12.0和WinRAR压缩视频文件最终结果图表图3WinZip12.0和WinRAR压缩视频文件最终结果图表图4WinZip12.0和WinRAR压缩文档文件最终结果图表〔3〕7Z作为压缩格式的后起新秀，7Z有着比RAR更高的压缩率，能够将文件压缩得更加小巧。不过因为RAR格式已经高度普及，7Z想要取代RAR目前的地位相当不容易。与之前两种格式一样，7Z也有着专门支持它的软件：7-zip。使用7-zip可以解压缩RAR格式的压缩文件，而WinRAR也同样可以解压缩7Z格式的压缩文件。大概因为直接使用现有的Win-RAR就可以处理网络上下载到的7Z格式文件，而要将文件压缩成7Z格式的话却需要额外安装7-zip，所以也间接阻碍了7Z格式的普及。〔4〕CABCAB是微软的一种安装文件压缩格式，主要应用于软件的安装程序中。因为涉及到安装程序，所以CAB文件中包含的文件通常都不是简单的直接压缩，而是对文件名等都进展了处理，所以虽然可以对其直接解压缩，但解压后得到的文件通常都无法直接使用。和ZIP一样，Windows系统自身就可以翻开CAB格式的文件，而几乎所有压缩软件也都可以对CAB文件进展解压。〔5〕WinMount最后单独介绍一个软件：Win-Mount。当解压缩一个文件时，就必然会多占用一些磁盘空间，因为磁盘上同时存在了压缩文件和解压后的文件。而WinMount的特点就是能够将压缩文件以类似虚拟光驱的方式挂接为一个虚拟磁盘供用户使用，因为所有的操作都是在内存中进展的，并没有实际执行任何的解压缩操作，所以不会占用额外的磁盘空间。这对于一些用户来说，可能还是很有帮助的。程序构造1类设计哈夫曼树的结点构造如下：structHuffNode //哈夫曼树结点的定义{ chardata; //待编码的符号 doubleweight; //符号出现的频率 intlchild,rchild,parent; //父结点左右孩子结点的位置};哈夫曼树类的构造如下：classHuffTree{public: HuffTree(vector<HuffNode>&leaves); //构造函数 vector<int>Getcode(inti); //取编码 stringDecode(vector<int>&source); //译码 stringDecode(string&source); //译码 ~HuffTree(){} intGetn(){returnn;} //返回叶子结点数 charGetData(inti){returnhufftree[i].data;} //返回叶子结点的值 HuffNodeGetNode(inti){returnhufftree[i];}private: voidSelectSmall(int&least,int&less,inti);private: vector<HuffNode>hufftree; //所有结点的存储空间 intn; //叶子结点数};哈夫曼树类有2个私有成员vector<HuffNode>类型的hufftree〔所有结点的存储空间〕和int类型的n〔叶子结点数〕。有1个编码函数vector<int>Getcode(inti)和2个译码函数，如下：stringDecode(vector<int>&source); //哈夫曼编码是vector<int>类型stringDecode(string&source); //哈夫曼编码是string类型2主程序设计主程序中有4个重要函数，如下：〔1〕计算待解压字符出现的频度voidGetFrequency(intfrequency[],charfilename[]); //统计各字符出现的频度。先初始化用于统计每个ASCII码字符个数的数组frequencyvoidGetFrequency(intfrequency[],charfilename[]){ for(inti=0;i<256;i++) frequency[i]=0; //初始化frequency数组 charch; //用于读入每个字符 ifstreaminfile(filename); //翻开待压缩的文件 infile>>noskipws; //noskipws:不忽略空白，把每行最后那个‘\n‘也读进来 while(infile>>ch) frequency[ch]++; //统计每个ASCII码字符的个数 infile.close(); //关闭文件}〔2〕压缩voidpression(HuffTreehf,vector<HuffNode>leaves,charfilename[],charfilename2[]);//压缩voidpression(HuffTreehf,vector<HuffNode>leaves,charfilename[],charfilename2[]){ ifstreaminfile2(filename); //翻开待压缩文件 ofstreamoutfile; outfile.open(filename2); //翻开压缩后文件 charch; infile2>>noskipws; //noskipws:不忽略空白，把每行最后那个‘\n‘也读进来 while(infile2>>ch) //逐个读入字符 { for(inti=0;i<leaves.size();i++) if(ch==leaves[i].data) //找到字符对应的叶子结点 { for(intj=0;j<hf.Getcode(i).size();j++) outfile<<hf.Getcode(i)[j]; //将对应Huffman编码写入文件 } } infile2.close(); //关闭待压缩文件 outfile.close(); //关闭压缩后文件 cout<<endl<<endl<<endl; cout<<"压缩文件"<<filename<<"成功,"; cout<<"生成了已压缩文件"<<filename2<<"!"<<endl<<endl<<endl;}〔3〕解压1voidDepression1(HuffTreehf,charfilename2[],charfilename3[]);解压方法1:Huffman编码储存为vector<int>类型从压缩后的文件中读入Huffman编码,使用HuffTree类中的解码函数将Huffman编码转换成对应的ASCII码字符写入解压后的文件。voidDepression1(HuffTreehf,charfilename2[],charfilename3[]){ charc; //暂时储存读入的字符 intt; //储存读入字符对应的整数 vector<int>source; //储存Huffman编码 ifstreaminfile(filename2); //翻开压缩后的文件 while(infile>>c) //逐个读入Huffman码的0/1符 { t=c-'0'; //将字符转换成整数 source.push_back(t); //将整数插入Huffman编码中 } infile.close(); //关闭压缩后的文件 stringtarget; target=hf.Decode(source); //得到Huffman编码对应的字符 ofstreamoutfile(filename3); outfile<<target; //解压后的字符串写入解压后文件 outfile.close(); //关闭解压后的文件 cout<<"已成功解压生成文件"<<filename3<<"!"<<endl<<endl<<endl;}〔4〕解压2voidDepression2(HuffTreehf,charfilename2[],charfilename3[]); 解压方法2:Huffman编码储存为string类型voidDepression2(HuffTreehf,charfilename2[],charfilename3[]){ charc; //暂时储存读入的字符 stringsource; //储存Huffman编码 ifstreaminfile(filename2); //翻开压缩后的文件 while(infile>>c) //逐个读入Huffman码的0/1符 { source=source+c; } //将整数插入Huffman编码中 infile.close(); //关闭压缩后的文件 stringtarget; target=hf.Decode(source); //得到Huffman编码对应的字符 ofstreamoutfile(filename3); outfile<<target; //解压后的字符串写入解压后文件 outfile.close(); //关闭解压后的文件 cout<<"已成功解压生成文件"<<filename3<<"!"<<endl<<endl<<endl;}3流程图读取文本中待压缩的数据读取文本中待压缩的数据开场完毕统计各字符的频率建哈夫曼树得到哈夫曼编码通过哈夫曼树解码系统环境与程序测试案例硬件环境截图如下：软件环境：MicrosoftVisualC++6.0软件使用界面：1待压缩的文件为Data.t*t，如下：压缩后的文件为：pressionData.t*t解压后的文件为：DepressionData1.t*t中