数据结构C语言版课程综合性实验报告

1、.华北科技学院计算机系综合性实验实 验 报 告 课程名称数据结构（C语言版） 实验学期2009至2010学年 第2学期学生所在系部计算机系年级大二专业班级信管B-081学生XX尹芳学号3 任课教师兰芸 实验成绩计算机系制实验报告须知1、 学生上交实验报告时，必须为打印稿（A4纸）。页面空间不够，可以顺延。2、 学生应该填写的内容包括：封面相关栏目、实验地点、时间、目的、设备环境、内容、结果及分析等。3、 教师应该填写的内容包括：实验成绩、教师评价等。4、 教师根据本课程的综合性实验指导单中实验内容的要求，评定学生的综合性实验成绩；要求在该课程期末考试前将实验报告交给任课教师。综合性实验中，所涉

2、及的程序，文档等在交实验报告前，拷贝给任课教师。任课教师统一刻录成光盘，与该课程的期末考试成绩一同上交到系里存档。5、 未尽事宜，请参考该课程的实验大纲和教学大纲。 数据结构（C语言版） 课程综合性实验报告开课实验室：基础一2010年 6月 22 日实验题目用哈夫曼编码实现文件压缩一、实验目的1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。二、设备与环境微型计算机、Windows 系列操作系统 、Visual C+6.0软件三、实验内容

3、根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。四、功能模块简介和系统结构图：哈夫曼 压缩、解压缩压缩 解压缩退出五、实验结果及分析（1）系统的主要界面设计及运行说明按屏幕提示进行文件压缩操作。按屏幕提示进行文件解压缩操作。（2）程序的主要代码*include <stdio.h>*include <string.h>*include <stdlib.h>*include <conio.h>struct headunsigned char b; /记录字符在数组中的位置

4、long count; /字符出现频率（权值） long parent,lch,rch; /定义哈夫曼树指针变量 char bits256; /定义存储哈夫曼编码的数组header512,tmp;void unpress() /文字解压函数char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf("t请输入您要解压缩的文件名："); gets(filename); ifp=fopen(strcat

5、(filename,".txt"),"rb"); if(ifp=NULL)printf("nt文件打开失败!n"); return;printf("t请输入您解压缩后的文件名："); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp=NULL)printf("nt操作失败!n"); return;fread(&flength,sizeof(long),1,ifp); /读取原文件长度，对文件进行定位 fread(

6、&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i<n;i+)fread(&headeri.b,1,1,ifp); fread(&c,1,1,ifp); p=(long)c; /读取原文件字符的权值 headeri.count=p; headeri.bits0=0; if(p%8>0) m=p/8+1; else m=p/8; for(j=0;j<m;j+)fread(&c,1,1,ifp); f=c; itoa(f

7、,buf,2); /将f转换为二进制表示的字符串 f=strlen(buf); for(l=8;l>f;l-)strcat(headeri.bits,"0");strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;i<n;i+) /根据哈夫曼编码的长短，对结点进行排序for(j=i+1;j<n;j+)if(strlen(headeri.bits)>strlen(headerj.bits);tmp=headeri; headeri=headerj; headerj=tmp; p=strlen(header

8、n-1.bits); fseek(ifp,8,SEEK_SET); m=0; bx0=0;while(1) /通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp); f=c; itoa(f,buf,2); f=strlen(buf); for(l=8;l>f;l-) /在单字节内对相应位置补0strcat(bx,"0");strcat(bx,buf);for(i=0;i<n;i+)if(memcmp(headeri.bits,bx,heade

9、ri.count)=0) break;strcpy(bx,bx+headeri.count); c=headeri.b; fwrite(&c,1,1,ofp); m+; /统计解压缩后文件的长度 if(m=flength) break; /flength是原文件长度 fclose(ifp); fclose(ofp); printf("nt解压缩文件成功!n"); if(m=flength) /对解压缩后文件和原文件相同性比较进行判断（根据文件大小）printf("t解压缩文件与原文件相同!nn");else printf("t解压缩文件

10、与原文件不同!nn"); return;void press() /文件压缩函数long i,j,m,n,f; unsigned char c; long min1,pt1,flength,length1,length2;double div;char filename255,outputfile255,buf512; FILE *ifp,*ofp; printf("t请您输入需要压缩的文件名(格式如:*.txt)："); gets(filename); ifp=fopen(filename,"r"); if(ifp=NULL)printf(&

11、quot;nt文件打开失败!nn"); return;printf("t请您输入压缩后的文件名(格式如:'*')："); gets(outputfile); ofp=fopen(strcat(outputfile,".txt"),"w"); if(ofp=NULL)printf("nt压缩文件失败!nn"); return;flength=0; while(!feof(ifp)fread(&c,1,1,ifp); headerc.count+; /字符重复出现频率+1 flengt

12、h+; /字符出现原文件长度+1 flength-; length1=flength; /原文件长度用作求压缩率的分母 headerc.count-; for(i=0;i<512;i+)if(headeri.count!=0) headeri.b=(unsigned char)i; else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化 for(i=0;i<256;i+) /根据频率（权值）大小，对结点进行排序，选择较小的结点进树for(j=i+1;j<256;j+)if(header

13、i.count<headerj.count)tmp=headeri;headeri=headerj;headerj=tmp;for(i=0;i<256;i+) if(headeri.count=0) break; n=i; /外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1. m=2*n-1; for(i=n;i<m;i+) /构建哈夫曼树min1=999999999; /预设的最大权值，即结点出现的最大次数 for(j=0;j<i;j+)if(headerj.parent!=-1) continue; /parent!=-1说明该结点

14、已存在哈夫曼树中，跳出循环重新选择新结点*/ if(min1>headerj.count)pt1=j; min1=headerj.count; continue;headeri.count=headerpt1.count; headerpt1.parent=i; /依据parent域值（结点层数）确定树中结点之间的关系 headeri.lch=pt1; /计算左分支权值大小 min1=999999999; for(j=0;j<i;j+)if(headerj.parent!=-1) continue;if(min1>headerj.count)pt1=j;min1=header

15、j.count;continue;headeri.count+=headerpt1.count; headeri.rch=pt1; /计算右分支权值大小 headerpt1.parent=i;for(i=0;i<n;i+) /哈夫曼无重复前缀编码f=i; headeri.bits0=0; /根结点编码0 while(headerf.parent!=-1)j=f; f=headerf.parent; if(headerf.lch=j) /置左分支编码0j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1);/依次存储

16、连接“0”“1”编码 headeri.bits0='0'else /置右分支编码1j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0='1'fseek(ifp,0,SEEK_SET); /从文件开始位置向前移动0字节，即定位到文件开始位置 fwrite(&flength,sizeof(int),1,ofp); fseek(ofp,8,SEEK_SET); buf0=0; /定义缓冲区,它的二进制表示00000000 f=0; pt1=8; whil

17、e(!feof(ifp)c=fgetc(ifp); f+; for(i=0;i<n;i+)if(c=headeri.b) break;strcat(buf,headeri.bits); j=strlen(buf); c=0;while(j>=8) /对哈夫曼编码位操作进行压缩存储for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1; else c=c<<1;fwrite(&c,1,1,ofp); pt1+; /统计压缩后文件的长度 strcpy(buf,buf+8); /一个字节一个字节拼接 j=strl

18、en(buf);if(f=flength) break;if(j>0) /对哈夫曼编码位操作进行压缩存储strcat(buf,"00000000"); for(i=0;i<8;i+)if(bufi='1') c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp); pt1+;fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(lo

19、ng),1,ofp); for(i=0;i<n;i+)fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /若存储的位数不是8的倍数，则补0 for(f=j%8;f<8;f+) strcat(headeri.bits,"0");while(headeri.bits0!=0)c=0; for(j=0;j<8;j+) /字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接

20、if(headeri.bitsj='1') c=(c<<1)|1; /|1不改变原位置上的“0”“1”值 else c=c<<1;strcpy(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接 fwrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率 fclose(ifp); fclose(ofp); printf("nt压缩文件成功!n"); pri

21、ntf("t压缩率为 %f%nn",div*100); return;int main()int c; while(1) /菜单工具栏printf("t n"); printf("t * 哈夫曼 压缩、解压缩 * n"); printf("t n"); printf("t _n"); printf("t| |n"); printf("t| 1.压缩 |n"); printf("t| 2.解压缩 |n"); printf("t| 0.退出 |n"); printf("t|_|n");printf("n");printf("t 说明：（1）采用哈夫曼编码n");printf("t （2）适用于字符型文本文件n");printf("n"); do /对用户输入进行容错处理printf("nt*请选择相应功能(0-2):"); c=getch();printf("%cn",c); if(