《数据结》课程设计.doc

《《数据结》课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计——压缩软件学号：06040510姓名：吴丹指导老师：王琼2006年9月（一）课题：压缩软件准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。Huffman编码是一种可变长编码方式，是由美国数学家DavidHuffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的

2、最根本的原则是：累计的(字符的统计数字字符的编码长度)为最小，也就是权值(字符的统计数字字符的编码长度)的和最小。编码：将ABCDEFGH用Huffman树产生的编码对应着写到文件中，并且保留原始的Huffman树，主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树，每个Huffman树都必须有以下的结构：code,char,left,right,probability(出现次数)，通常情况是利用一个数组结构。因为在解码的时候只需要用到code，所以只需要记录每个元素的编码

3、就可以了。解码：利用文件中保存的Huffman编码，一一对应，解读编码，把可变长编码转换为定长编码。（二）功能设计⑴源文件=》Huffman编码文件①准备源文件程序文件②扫描源文件，统计其中各字符频率③建立Huffman树，计算Huffman编码④生成目标文件的文件头⑤扫描源文件，翻译成Huffman编码文件⑵Huffman编码文件=》源文件①读Huffman编码文件头，重建Huffman树②扫描Huffman编码文件，翻译成源文件（三）结构框图读取源文件对哈夫曼树进行编码将密码保存至文件统计源文件字符权值

4、根据频率表建立哈夫曼树将解码文档保存至文件对密码文档进行解码打开密码文档（四）程序（1）读取源文件voidOutput1(){FILEfp;chara;fp=fopen("1.txt","r");if(fp==NULL){printf("can'topenthefile");exit(0);}do{fscanf(fp,"%c",&a);printf("%c",a);}while(!feof(fp));printf("");}（2）统计源文件字符权值huffnodesetWeight(charstring

5、){inti=0;huffnodetree,ptr,beforeptr;huffnodenode;if((tree=(huffnode)malloc(sizeof(huffnode)))==NULL)returnNULL;tree->next=NULL;for(i=0;string[i]!='';i++){ptr=tree;beforeptr=tree;if((node=(HTNode)malloc(sizeof(huffnode)))==NULL)returnNULL;node->next=NULL;

6、node->parent=NULL;node->lchild=NULL;node->rchild=NULL;node->mark=0;node->ch=string[i];node->weight=1;if(tree->next==NULL)tree->next=node;else{ptr=tree->next;while(ptr&&ptr->ch!=node->ch){ptr=ptr->next;beforeptr=beforeptr->next;}if(ptr&&ptr->ch==node->ch){p

7、tr->weight++;free(node);}else{node->next=beforeptr->next;beforeptr->next=node;}}}returntree;}（3）根据频率表建立哈夫曼树voidhaffmantree(intweight[],intn,structhaffnodehafftree[],chardata[]){inti,j,m1,m2,x1,x2;for(i=0;i<2n-1;i++){if(i

8、e[i].weight=weight[i];}else{hafftree[i].weight=0;hafftree[i].data='';}hafftree[i].parent=0;hafftree[i].flag=0;hafftree[i].leftchild=-1;hafftree[i].rightchild=-1;}for(i=0;i