常州大学课程设计报告

常州大学课程设计PAGEPAGE26序号:学号:12453118课程设计设计课程名称：C语言课程设计题目：DataCompression学生姓名：郭宏宇学院：数理学院专业班级：应数121指导教师：王军专业技术职务：讲师设计时间：2013年6月17日2013年6月28日目录1、引言及设计要求 31.1引言 31.2设计需求 31.2.1题目要求 31.2.2输出要求 32、概要设计 32.1数据结构的描述 32.1.1数据类型的定义 32.1.2主要算法流程描述 42.2流程图 43、详细设计及实现 54、调试分析 55、总结及心得 115.1专题总结 115.2心得体会 116、设计日志及参考文献 126.1设计日志 126.2参考文献 12附录：程序源代码 13第一部分：霍夫曼解码器的实现 13第二部分：实现霍夫曼编码器 171、引言及设计要求1.1引言在多媒体计算机系统中，信息从单一媒体转到了多种媒体，要表示、传输和处理大量的声音、图像甚至影像视频信息，其数据量之大是非常惊人的。数字化多媒体信息的数据量是如此巨大，加之信息种类多、实时性要求高，给数据的存储、传输以及加工处理均带来了巨大的压力，不仅要求计算机有更高的数据处理和数据传输能力以及巨大的存储空间，而且也要求通信信道有更高的带宽。为了解决存储、处理和传输多媒体数据的问题，除了提高计算机本身的性能以及通信信道的带宽外，更重要的则是对多媒体数据进行有效的压缩。因此数据压缩编解码自然就成为了多媒体技术中最为关键的核心技术。1.2设计需求1.2.1题目要求A:在每一次迭代过程中，我们需要跟踪的符号（或复合）的最低频率和第二频率最低的发生。这可以很容易地使用优先队列（一个链表，其中的元素总是插入正确的位置）。文件encode.c包含的模板代码（pq_insert()）的实现优先级队列。你需要填写缺少的部分。确保你照顾下列条件：（i）队列为空（ii）新的元素在开始前存储进去（iii）新元素存储在队列最后或中间。B:符号的使用优先队列的pq_pop功能删除。在一个优先队列中，元素总是从一开始就删除。文件encode.c包含模板代码来实现这个。请填写所缺的部分。确保你的更新要被删除的元素的指针。C:一旦代码树是建立在内存中，我们需要生成的每个符号的编码字符串。填入所缺的代码生成generate_code()。D:最后填写缺失的代码来释放所有资源和内存,然后退出代码。1.2.2输出要求程序输出两个文件encoded.txt含有编码的输出和code.txt显示霍夫曼编码。2、概要设计2.1数据结构的描述2.1.1数据类型的定义structtnode{structtnode*left;/*usedwhenintree*/structtnode*right;/*usedwhenintree*/structtnode*parent;/*usedwhenintree*/structtnode*next;/*usedwheninlist*/floatfreq;intisleaf;charsymbol;};structSymbol{ charsymbol; floatfreq;};/*globalvariables整体变量*/charcode[MAX_SYMBOLS][MAX_LEN];structtnode*root=NULL;/*treeofsymbols*/structtnode*qhead=NULL;/*listofcurrentsymbols*/structcnode*chead=NULL;/*listofcode*/2.1.2主要算法流程描述Main函数调用pq_insert函数频率初始化，调用pq_pop、talloc、pq_insert函数构建树，调用generate_code函数构建代码，调用dump_code函数输出代码，调用encode函数实现一个样品的字符串编码。2.2流程图3、详细设计及实现分配新的代码：动态申请一块区域，用强制类型把它转换成结构体类型structtnode的指针并赋给同类型的指针变量p，再将信息赋给申请的区域里。在代码功能中显示tnodes的列表：调用structtnode，输出字符和出现的频率。插入一个元素到优先列表中：利用全局变量qhead，分不同的情况将元素插入到优先列表中。删除第一个元素：利用全局变量qhead，分两种情况删除元素。生成的字符串的代码树：运用递归调用的方法建立一个叶子节点。输出代码文件：将code信息输出到文件（就是code.txt）。Main函数：调用不同的函数完成这个程序。4、调试分析在main函数中调用函数，结果如下：显示在二叉树中各个字符的寻找路径111101110!10111001111"1011101&01101100111101001'111100101(10111001100111101)10111001100111100,011001-101110000.1111100/01101100111101000001011100110010101101100111112101110001011003011011001111001410111001100111050110110011110116011011001111000710111001100110081011100010110191011100110011111:11110011111011;111100111111?1111001001A1111001101B0110110100C10111001101D01101100011E01101100110F111100111101G101110011000H101110010I0110001J011011001110K1011100010111L10111000100M1111001000N10111000110O10111000111P111100111100Q101110011001101R01101100010S1111001110T011011011U11110011111010V1111001111100W1111001100X0110110011110101Y0110110010Z011011001111010001a1000b1111000c101111d10110e001f100110g011010h0100i0000j10111001110k0110000l10010m111001n0101o0111p1111101q0110110000r11101s0001t1010u111111v0110111w111000x0110110101y100111z1011100010105、总结及心得5.1专题总结在本专题的课程设计中运用了C语言的知识设计了数据压缩，我们利用C语言的知识设计了可以对数据进行压缩的系统，在系统中我们了解到了霍夫曼编码（HuffmanCoding是一种编码方式，是一种用于无损数据压缩的权编码算法。1952年，DavidA.Huffman在麻省理工攻读博士时所发明的，并发表于AMethodfortheConstructionofMinimum-RedundancyCodes一文）。数据压缩包含的内容很多，我做的这个程序调用的函数也比较多。程序包含7个调用函数和一个主函数，主函数分别调用这几个不同功能的函数。分别为：分配新的代码，在代码功能中显示tnodes的列表，插入一个元素到优先列表中，删除第一个元素，生成的字符串的代码树，输出代码文件，输出压缩流。总结：获取a，b，c...的频率；根据频率做霍夫曼二叉树；根据二叉树获得a，b，c...的编码；编码到文件中在设计中我们利用使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。系统不完善，应进一步设计与细化。5.2心得体会首先感谢王老师在课程中和在为期两周的设计过程中的支持。这次是我第一次参加课程设计，因此刚完成分组拿到课题是还是很紧张的。由于五人联合完成一个课题，需要较好地处理分步完成和协调好组内同学的配合。在这一方面，数据压缩课题是不同于其他课题的。所以在此次课程设计中，对于我们各位来说团队精神都得到了很大提升。在设计的过程中，除了组内同学的配合之外，我们还得到了其他同学的答疑和帮助，在此也一并感谢。开始时，看了数据压缩的英文版解释，大致了解了这个程序分为三个部分，第一部分：霍夫曼解码器的实现：第二部分：实现霍夫曼编码器；第三部分：压缩大文件。第一部分相对其它两个部分简单点，第二部分应该是其中最难的了。而且，对于第二部分所涉及的C语言知识，我也是没有想到的，因为之前对于链表、递归我还是不了解的，我也通过这次C语言课程设计把落下的知识补上来了。也许我做的还不是很好，但是，通过这次课程设计我学会了在C语言编程中如何更好地运用所学的知识，和别人合作完成一个大的编程。学校组织我们进行课程设计的用意也是希望我们能够把在C语言课程中学到的理论知识同实践结合起来，复合地利用所学知识丰富自己的涵养，提高自己的水平。只有把所学的理论知识与实践相结合起来，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，在这次课程设计之后，我一定会完善自己的不足之处。6、设计日志及参考文献6.1设计日志六月十五号--六月十六号我们拿到题目，进行了分组。六月十七号--六月十八号将老师所给题目资料、部分程序代码进行整理和汇总，题目英文部分进行翻译，打印成册，组员每人一份。初步了解设计的要求、目的、所需知识内容，将设计分为三个部分，分配人员负责。六月十九号--六月二十号进一步了解设计，发现问题，重新部署。六月二十一号--六月二十三号查阅资料，结合老师已给程序，弄清每部分程序的职能，完成大概的程序填充。六月二十四号--六月二十五号请教高水平同学，完善粗糙的程序。六月二十六号进行程序的调试运行，纠错。六月二十七号撰写程序设计报告，编写设计心得等。六月二十八号完善设计报告和准备答辩6.2参考文献《c语言程序设计（第二版）》《数据压缩基本原理》霍夫曼代码–维基百科，自由的百科全书哈夫曼代码–百度百科附录：程序源代码第一部分：霍夫曼解码器的实现#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_SYMBOLS255#defineMAX_LEN10structtnode{structtnode*left;/*usedwhenintree*/structtnode*right;/*usedwhenintree*/intisleaf;charsymbol;};structcode{ int symbol; char strcode[MAX_LEN];};/*globalvariables*/structtnode*root=NULL;/*treeofsymbols*//*@functiontalloc@descallocatesnewnode*/structtnode*talloc(){structtnode*p=(structtnode*)malloc(sizeof(structtnode));if(p!=NULL){p->left=p->right=NULL;p->symbol=0; p->isleaf=0;}returnp;}/*@functionbuild_tree@descbuildsthesymboltreegiventhelistofsymbolsandcode.h NOTE:alterstheglobalvariablerootthathasalreadybeenallocatedinmain*/voidbuild_tree(FILE*fp){ char symbol; char strcode[MAX_LEN]; int items_read; int i,len; struct tnode*curr=NULL; while(!feof(fp)) { items_read=fscanf(fp,"%c%s\n",&symbol,strcode); if(items_read!=2)break; curr=root; len=strlen(strcode); for(i=0;i<len;i++) { /*TODO:createthetreeasyougo*/ if(strcode[i]=='0') { if(curr->left) { curr=curr->left; } else { structtnode*p=(structtnode*)malloc(sizeof(structtnode)); curr->left=p; p->left=0; p->right=0; p->symbol=0; p->isleaf=0; curr=p; } } else { if(curr->right) { curr=curr->right; } else { structtnode*p=(structtnode*)malloc(sizeof(structtnode)); curr->right=p; p->left=0; p->right=0; p->symbol=0; p->isleaf=0; curr=p; } } } /*assigncode*/ curr->isleaf=1; curr->symbol=symbol; printf("insertedsymbol:%c，%s\n",symbol,strcode); }}/* functiondecode*/voiddecode(FILE*fin,FILE*fout){ charc; structtnode*curr=root; while((c=getc(fin))!=EOF) { /*TODO: traversethetree printthesymbolsonlyifyouencounteraleafnode */ if(curr->isleaf==0) { if(c=='1') { curr=curr->right; if(curr->isleaf) { putc(curr->symbol,fout); curr=root; } } else { curr=curr->left; if(curr->isleaf) { putc(curr->symbol,fout); curr=root; } } } } curr=NULL; free(curr);}/* @functionfreetree @desc cleansupresourcesfortree*/voidfreetree(structtnode*root){ if(root==NULL) return; freetree(root->right); freetree(root->left); free(root);}intmain(){ constchar*IN_FILE="encoded.txt"; constchar*CODE_FILE="code.txt"; constchar*OUT_FILE="decoded.txt"; FILE*fout; FILE*fin; /*allocateroot*/ root=talloc(); fin=fopen(CODE_FILE,"r"); /*buildtree*/ build_tree(fin); fclose(fin); /*decode*/ fin=fopen(IN_FILE,"r"); fout=fopen(OUT_FILE,"w"); decode(fin,fout); fclose(fin); fclose(fout); /*cleanup*/ freetree(root); getchar(); return0;}第二部分：实现霍夫曼编码器#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<memory.h>#include<string.h>#defineMAX_SYMBOLS128#defineMAX_LEN20structtnode{structtnode*left;/*usedwhenintree*/structtnode*right;/*usedwhenintree*/structtnode*parent;/*usedwhenintree*/structtnode*next;/*usedwheninlist*/floatfreq;intisleaf;charsymbol;};structSymbol{ charsymbol; floatfreq;};/*globalvariables*/charcode[MAX_SYMBOLS][MAX_LEN];structtnode*root=NULL;/*treeofsymbols*/structtnode*qhead=NULL;/*listofcurrentsymbols*/structcnode*chead=NULL;/*listofcode*//*@functiontalloc@descallocatesnewnode*/structtnode*talloc(intsymbol,floatfreq){structtnode*p=(structtnode*)malloc(sizeof(structtnode));if(p!=NULL){p->left=p->right=p->parent=p->next=NULL;p->symbol=symbol;p->freq=freq; p->isleaf=1;}returnp;}/*@functiondisplay_tnode_list@descdisplaysthelistoftnodesduringcodeconstruction*/voidpq_display(structtnode*head){structtnode*p=NULL;printf("list:");for(p=head;p!=NULL;p=p->next){printf("(%c,%f)",p->symbol,p->freq);}printf("\n");}/*@functionpq_insert@descinsertsanelementintothepriorityqueueNOTE:makesuseofglobalvariableqhead*/voidpq_insert(structtnode*p){structtnode*curr=NULL;structtnode*prev=NULL;printf("inserting:%c,%f\n",p->symbol,p->freq);if(qhead==NULL)/*qheadisnull*/{ /*TODO:writecodetoinsertwhenqueueisempty*/ qhead=p;}/*TODO:writecodetofindcorrectpositiontoinsert*/else{ curr=prev=qhead; if(qhead->next==NULL||(p->freq<=qhead->freq)) { curr=qhead; } else { do { prev=curr; curr=prev->next; if((curr==NULL)||((prev->freq<=p->freq)&&(curr->freq>=p->freq))) break; }while(1); } if(curr==qhead) { /*TODO:writecodetoinsertbeforethecurrentstart*/ if(p->freq<=curr->freq) { qhead=p; qhead->next=curr; } else { qhead->next=p; p->next=NULL; } } else/*insertbetweenprevandnext*/ { /*TODO:writecodetoinsertinbetween*/ prev->next=p; p->next=curr; } }}/*@functionpq_pop@descremovesthefirstelementNOTE:makesuseofglobalvariableqhead*/structtnode*pq_pop(){structtnode*p=NULL;/*TODO:writecodetoremovefrontofthequeue*/ if(qhead->next!=NULL) { p=qhead; qhead=qhead->next; printf("popped:%c,%f\n",p->symbol,p->freq); returnp; } else { printf("popped:%c,%f\n",qhead->symbol,qhead->freq); returnqhead; }}/* @functionbuild_code @descgeneratesthestringcodesgiventhetree NOTE:makesuseoftheglobalvariableroot*/chara[MAX_LEN]=""; voidgenerate_code(structtnode*root,char*a,intdepth){ staticintsymbol; staticintlen;/*lengthofcode编码长度*/ if(root==NULL)return; if(root->isleaf) { symbol=root->symbol; len=depth; /*startbackwards开始向后*/ a[len]=0; code[symbol][len]=0; /* TODO:followparentpointertothetop togeneratethecodestring跟随父顶指针生成代码字符串 */ printf("builtcode:%c,%s\n",symbol,a); strcpy(code[symbol],a); } else { a[depth]='0'; generate_code(root->left,a,depth+1); a[depth]='1'; generate_code(root->right,a,depth+1); } }/* @func dump_code @desc outputcodefile*/voiddump_code(FILE*fp){ inti=0; for(i=0;i<MAX_SYMBOLS;i++) { if(code[i][0])/*nonempty*/ { if(i!=32) fprintf(fp,"%c%s\n",i,code[i]); else fprintf(fp,"%c%s\n",'_',code[i]); } }}/* @func encode @desc outputscompressedstream*/voidencode(char*str,FILE*fout){ while(*str) { fprintf(fout,"%s",code[*str]); str++; }}/*@functionmain*/intmain(){ structtnode*p=NULL;structtnode*lc,*rc; FILE*fout=NULL; FILE*fin=NULL; constchar*IN_FILE="..\\book.txt"; constchar*CODE_FILE="..\\code.txt"; constchar*OUT_FILE="..\\encoded.txt"; structSymbolfrequence[MAX_SYMBOLS]; structSymbolsort_temp; inti=0,j=0; charch; charcha[2]=""; intchar_num=0; doublesizein=0,sizeout=0; memset(frequence,0,sizeof(frequence)); fin=fopen(IN_FILE,"r"); for(i=0;i<MAX_SYMBOLS;i++) { frequence[i].freq=0; frequence[i].symbol=i; } while((ch=getc(fin))!=EOF) { frequence[ch].freq++; } for(i=0;i<MAX_SYMBOLS;i++) for(j=i;j<MAX_SYMBOLS;j++) if(frequence[j].freq<frequence[i].freq) { sort_tem