数据结构综合性实验报告格式

华北科技学院《用哈夫曼编码实现文件压缩》实验报告《用哈夫曼编码实现文件压缩》实验报告课程名称数据结构A实验学期2015至2016学年第二学期学生所在系部管理学院年级2014专业班级电商B142学生姓名梁祺学号201404064208成绩评定：1、工作量：A（），B（），C（），D（）,F()2、难易度：A（），B（），C（），D（）,F()3、答辩情况：基本操作：A（），B（），C（），D（）,F()代码理解：A（），B（），C（），D（）,F()4、报告规范度：A（），B（），C（），D（）,F()5、学习态度：A（），B（），C（），D（）,F()总评成绩:_________________________________指导教师:兰芸华北科技学院《用哈夫曼编码实现文件压缩》实验报告一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、Windows7操作系统、VisualC++6.0软件四、实验内容：根据Ascii码文件中各Ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。五、系统设计：树中从根到每个叶子都有一条路径，对路径上的个分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符编码，这就是赫夫曼编码。实验前，先统计数据出现的频率，得出权值；然后开始实验，先通过for循环结构获得所有结点中权值最小的根结点序号，再通过Select方法选择权值最小的树的根结点的序号构建赫夫曼树，之后调用HuffmanTreeCoding方法，先初始化节点，之后再利用for循环结构建赫夫曼树，待生成赫夫曼树之后，从叶子到根逆向求每个字符的赫夫曼编码，最后设计主函数，实现实验中的大概步骤。以下是实验流程图：开始定义变量得出权值最小的根节点序号华北科技学院《用哈夫曼编码实现文件压缩》实验报告初始化节点输入需要编码的字符构建赫夫曼树输出赫夫曼树构建过程表生成赫夫曼树从叶子到根逆向求每个字符的赫夫曼编码输出结果结束华北科技学院《用哈夫曼编码实现文件压缩》实验报告六、系统实现及测试结果：实验源代码：#includestdio.h#includestdlib.h#includelimits.h#includestring.htypedefintElementType;typedefstructhuffmantree{unsignedintweight;//权值unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表intMin(HuffmanTreet,inttotalNodes){//获得totalNodes个结点中权值最小的根结点序号intminIndex=0;unsignedintunWeight=UINT_MAX;//无符号整型最大值for(inti=1;i=totalNodes;i++){if(t[i].weightunWeight&&t[i].parent==0)//t[i]为根结点{unWeight=t[i].weight;minIndex=i;}}t[minIndex].parent=1;//给选中的根节点双亲赋1，避免第2次查找改点returnminIndex;}voidSelect(HuffmanTreet,intminIndex,int&minIndex1,int&minIndex2){//选择权值最小的树的根结点的序号minIndex1=Min(t,minIndex);minIndex2=Min(t,minIndex);inttempIndex;if(minIndex1minIndex2){华北科技学院《用哈夫曼编码实现文件压缩》实验报告tempIndex=minIndex1;minIndex1=minIndex2;minIndex2=tempIndex;}return;}voidHuffmanTreeCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//存放n个字符的权值,构造赫夫曼树，求出n个字符的赫夫曼编码HCif(n=1)return;intm=2*n-1;//总结点和inti;//根结点序号ints1,s2,j;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i=n;i++){//初始化HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(i=n+1;i=m;i++){//初始化HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}puts(\n哈夫曼树的构造过程如下所示：);printf(HT初态:\n结点weightparentlchildrchild);for(i=1;i=m;i++)printf(\n%4d%8d%8d%8d%8d,i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf(按任意键，继续...);getchar();for(i=n+1;i=m;i++){//建赫夫曼树//在HT[1..nodeIndexs-1]中选择parent为0且weight最小的两个结点，其序号分别为是s1,s2Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;华北科技学院《用哈夫曼编码实现文件压缩》实验报告printf(\nselect:s1=%ds2=%d\n,s1,s2);printf(结点weightparentlchildrchild);for(j=1;j=i;j++)printf(\n%4d%8d%8d%8d%8d,j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);printf(按任意键，继续...);getchar();}//------从叶子到根逆向求每个字符的赫夫曼编码---HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量([0]不用)char*cd;cd=(char*)malloc(sizeof(char)*n);//分配求编码的工作空间cd[n-1]='\0';//编码结束符for(i=1;i=n;i++){//逐个字符求赫夫曼编码intstart;unsignedintc,f;start=n-1;//编码结束位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码串到HC}}free(cd);//释放工作区间return;}intmain(void){HuffmanTreeHT;HuffmanCodeHC;intn;printf(请输入权值的个数:);scanf(%d,&n);getchar();华北科技学院《用哈夫曼编码实现文件压缩》实验报告int*w;w=(int*)malloc(n*sizeof(int));printf(请输入%d个权值：\n,n);for(inti=0;i=n-1;i++)scanf(%d,w+i);getchar();HuffmanTreeCoding(HT,HC,w,n);printf(各权值赫夫曼编码为:\n);for(i=1;i=n;i++)puts(HC[i]);return0;}测试结果：华北科技学院《用哈夫曼编码实现文件压缩》实验报告华北科技学院《用哈夫曼编码实现文件压缩》实验报告七、实验结果分析：实验过程中磕磕绊绊，总算是完成了，从一开始对程序以一知半解，到基本上掌握程序的核心，花了不少功夫。在网上参考过很多别人的作品，也许是知识层面不同，有些地方理解起来很费劲，但是程序的大体功能能够了解，因此运用起来还是没问题的。在实验中经常会出现一些小错误，得花很多精力去纠正，而且有时候产生的错误不容易发现，这就给修改程序增加了难度，感觉确实不容易。尤其是一些参数没定好带的麻烦，可能直接就影响了程序的很多部分。在实验过程中经历了很多，当然也收获了很多，对于赫夫曼树的构建和赫夫曼编码的产生相比于之前也有了更深的了解。相信在今后的学习生活中，多加接触练习，能够熟练掌握这门学科的技术。