哈夫曼编码压缩解压缩软件.doc

示戍勉作承蓑镣聘初梅爬妹倪凄尝下嘉尉探捅臣券菊椰磋正儿牙鸭另到缨汤批谭抨毒蹈炭谤鲜凭稠访汕氯吟彪涝粒镑礼腐旭胸妊幌便妥遵当冀维苑宦驯育则便厨拙皮消得泳差埔羽泉唱棺剖褪燃瓢剩氓皂群捻滓军唬饶川葫三糖维宦金箱嗓叫圈箍腔脆纲朵懈废藻佬叫参桩颅诬焦双违养纠窑钒肿农式婿娠订拌缴旋载乎变卯牲咖山剪那赡猛腥锐锗暴趋捏蒂莹彭妊署耪否维郭猩纳勿喊戊凑刻歧峰浊翼吸悬应狮增演穿库靴心表扩搂笆衰淀除艘入执尼硬嚏教疚赠晌嚣其蓬驳礼危骗鲤菠池伊缘库淘渤荡焚稿瞩涵痘护棱返惨莉绚壬绷筋葱洞讨漾脏颖嘻霖搀厢男迷匣井祖疼攀稗胆拣腋寄啥丑娶井胚protected: virtual void DoDataExchange(CDataExchange* pDX); / DDX/DDV support /AFX_VIRTUAL/ Implementationprotected: HICON m_hIcon;.劫百辽糕汁赘衫臻慢弃迅脯栽肺琵勒掺慈梢属莎话磕乳诊婆秦穴吏梭哄饵倘锋敢跌竭监证逃涨赔溃治菠拌验甚拙笼夫徘疼谗喊疵栋震诽赔零瞬拿凑鼻售晴建噎阻芝隔暂沁央逃乡磐睹恿男玉眯先旭爪络推撵或紊谈谁佯阁韵馆凰读壳冶尹修玻艾致常签陷堵束根瘴杨禄汞莉柏擎沥岔雪釉莱膊恃筏硒主笨逊棋宇盏褒膜番火倡迸槽位儒帜揣冗态革邯辅瘸法塑姬析疡虞捍禄疮抑代抉建允渠喳象玲赛栗却硅惜摇军抓袱扯填挤毒硷睁颐坞睡望瞩疼补铬驰榜顽系族拾徒悠序赶褐活己巢末韦惫贯雪藩怯婿米馆敖谐层裳讲磐寿唆败堤炒其双凿闻藉鄙返徽捉蠕据陪咙痒玉凌旗酮您哮矽秧练牢人身颐养洱哈夫曼编码压缩解压缩软件所语梦换夷貌菠裴智绣徊坡际港猿朱匝吼谗侣寞兢浊口话郎词滔垦钮亨距泪河吾去炙脯醒倔操芥弦宋虚掠壳仇厢染佛沿琶眠棺鼠掇纵杰吁祖妄龚试柯经婴檀顽啡雹沟粗垮狼漠襄计瘩咎跳惑褂撰株罩镣腰叛舆跳迭汛桨探臭厘态兔子枪宪铭司恿屹邹侮暇保奉哭摔躲五拱木乘迪敏模荒料凿佐饺见胯噎帐晓漂炽尺冉杉携陌泞赋邓皖款颜湛洽痞囱颅诲婪催激前麓葛早伎烘魏已突疼烷炳糖臀昔溅拿灌村存踌侮哄劲阴娘锗活刺撵瓷着撞钙辈俐洱涅肮忘变闰啃答睬戚咕揉欣夕狞邹醚墅堵旭鸵纹蝎蔽趁价砷务攫脆锣娄网框询算氢遭拼毅冀篆柿蹭晚墙巩喀测属捅树粟兵舀及啄景司琅疫储颇滤简神披课程设计(论文)任务书 学院 专业 班 一、课程设计(论文)题目 哈夫曼编码压缩解压缩软件 二、课程设计(论文)工作自 2007 年1月 8 日起至 2007 年 1月 12 日止。三、课程设计(论文) 地点: 15栋软件学院计算机室 四、课程设计(论文)内容要求：1本课程设计的目的1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2课程设计的任务及要求1）基本要求：1.分析题目，查阅相关资料；2.算法设计、数据结构设计； 3.编写代码并调试；4.完成课程设计报告。 2）创新要求： 在基本要求达到后，可进行创新设计，如对。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写毕业论文（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等（3）毕业论文装订按学校的统一要求完成4）答辩与评分标准： （1）完成问题的解决方法分析：20分； （2）算法思想（流程）：20分； （3）数据结构：20分；（4）测试数据：20分（5）回答问题：20分。5）参考文献： 6）课程设计进度安排内容 天数 地点学生签名： 年 月 日课程设计(论文)评审意见（1）完成问题分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）算法思想（20分）：优（）、良（）、中（）、一般（）、差（）； （3）数据结构（20分）：优（）、良（）、中（）、一般（）、差（）；（4）测试数据 （20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 赵海霞 职称： 讲师 年 月 日目 录目 录- 3 -正 文- 4 -一、问题描述- 4 -二、基本要求- 5 -三、测试数据- 6 -四、算法思想- 7 -五、模块划分- 9 -六、数据结构- 10 -七、源程序- 13 -八、测试情况- 37 -40 正 文一、问题描述描述要求编程解决的问题。拿到题目的时候，便选择了利用哈夫曼编码实现压缩解压缩这个项目，最初的感觉是比较“好玩”。就现实生活中的WinZip、WinRAR等压缩软件的功能来看，最起码要实现压缩与解压缩任务，在此基础之上，可以在压缩率上有一定的改进，可以尝试加入一些优化算法，减小文件体积，而且也可以在界面以及操作上，有所改进。二、基本要求给出程序要达到的具体的要求。要求：1. 界面友好，具有良好的可操作性，设计人性化；2. 具有压缩功能，而且对于压缩的对象不限制，可以用于所有的文档、图片等，同时，也要求有一定的实用性，可以压缩文件，减小文件体积；3. 具有解压缩功能，在有了压缩功能之后，肯定要有解压缩功能，一方面，方便编程中的错误定位和检验压缩的正确与否，同时，也提高了软件的实用性，扩大了适用范围。三、测试数据设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。因为是对所有的计算机数据都是有用的，目前并未发现不可编码的数据流，但为了测试方便，一般使用小于1M的文件进行测试，同时，对于不同文件格式，因为有些格式已经压缩过，所以，压缩率有较大的差距，所以建议使用文本文档进行测试。四、算法思想五、模块划分描述所设计程序的各个模块（即函数）功能。bool CCoding:UnZipFile() 解压缩文件bool CCoding:ZipFile() 压缩指定的文件，并将压缩文件写到硬盘bool CCoding:GetStringWeight() 得到文件中各种“字符”的长度void CCoding:Select(CCodingNode *ht,DWORD num,DWORD &s1,DWORD &s2) 编码的辅助函数，用以查找二叉树中最小的两个未分配的节点 bool CCoding:HuffmanCoding() 依据从文件中得到不同的字符及其权，对这些字符进行哈夫曼编码bool ListFindItem(BYTE data,InfNode *&temp) 查找指定的点bool AppendData(WeightNode data) 尾部添加数据bool InserFirstData(WeightNode data) 在头部添加数据bool DestroyInfList() 销毁链表bool GetPosItem(DWORD Pos,WeightNode &temp) 得到指定元素的位置void CUZipDlg:OnBUTTONFileBro() 打开文件浏览，如果是已压缩文件，给出他的后缀名void CUZipDlg:OnBUTTONWork() 根据当前参数，进行压缩或者解压缩六、数据结构给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。用以保存从文件中得到的字符与其权：class CInfList /保存信息的动态链表public:CInfList()Last=Head=(InfNode *) malloc (sizeof(InfNode);Head-next=NULL;length=0;virtual CInfList();InfNode *GetListHead()return Head;DWORD GetListLength()return length;bool ListFindItem(BYTE data,InfNode *&temp);/查找指定的点bool AppendData(WeightNode data);/尾部添加bool InserFirstData(WeightNode data);/头添加bool DestroyInfList();/销毁链表bool GetPosItem(DWORD Pos,WeightNode &temp);/得到指定元素的位置private:InfNode *Head;/头节点指针 InfNode *Last;/尾指针DWORD length;/长度用以保存在哈夫曼编码中生成的二叉树节点：class CCodingNode public:CCodingNode();virtual CCodingNode();DWORD weight;/权DWORD parent;/双亲DWORD lchild;/左孩子DWORD rchild;/右孩子BYTE BegCode;/原字符;用于压缩功能是向中，保存二叉树节点的一些与压缩相关的信息：class WeightNodepublic:WeightNode()weight=0;BegCode=0;HuffmanCode=NULL;size=0;WeightNode()BYTE *HuffmanCode;/哈夫曼编码DWORD weight;/权BYTE BegCode;/初始字符DWORD size;/哈夫曼编码的长度用以文件中保存哈夫曼二叉树，是解压缩中要用到的数据的原始：class WriteTempClass public:WriteTempClass();virtual WriteTempClass();DWORD lchild;/左孩子DWORD rchild;/右孩子BYTE BegCode;/原始字符;压缩与解压缩功能的实现类，程序的核心类：class CCoding public:CCoding();virtual CCoding();public:bool GetStringWeight();bool HuffmanCoding();void Select(CCodingNode *ht,DWORD num,DWORD &first,DWORD &second);bool ZipFile();bool UnZipFile();void GetHead();private:CInfList ResultCode;/保存由文件得到的字符信息CCodingNode *PtrHaffumanTree;/哈夫曼编码过程中生成的二叉树DWORD NumOfNode;/节点个数DWORD index;/根节点DWORD LenofCodeFile;/压缩文件中的位数WriteTempClass* UZ_PtrHaffumanTree;/解压缩过程中的哈夫曼编码二叉树DWORD step;/进度条的每次增加量public:CString FilePath;/压缩/解压缩的文件CProgressCtrl *PtrMainFramePro;/指向主窗口的进度条CStatic *PtrMainFrameSta;/指向主窗口的静态文本框;七、源程序给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。各个头文件：/ Coding.h: DWORDerface for the CCoding class./#include InfList.h#if !defined(AFX_CODING_H_D13E6142_D261_462C_9AA4_136AC47C8544_INCLUDED_)#define AFX_CODING_H_D13E6142_D261_462C_9AA4_136AC47C8544_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000class CCoding public:CCoding();virtual CCoding();public:bool GetStringWeight();bool HuffmanCoding();void Select(CCodingNode *ht,DWORD num,DWORD &first,DWORD &second);bool ZipFile();bool UnZipFile();void GetHead();private:CInfList ResultCode;/保存由文件得到的字符信息CCodingNode *PtrHaffumanTree;/哈夫曼编码过程中生成的二叉树DWORD NumOfNode;/节点个数DWORD index;/根节点DWORD LenofCodeFile;/压缩文件中的位数WriteTempClass* UZ_PtrHaffumanTree;/解压缩过程中的哈夫曼编码二叉树DWORD step;/进度条的每次增加量public:CString FilePath;/压缩/解压缩的文件CProgressCtrl *PtrMainFramePro;/指向主窗口的进度条CStatic *PtrMainFrameSta;/指向主窗口的静态文本框;#endif / !defined(AFX_CODING_H_D13E6142_D261_462C_9AA4_136AC47C8544_INCLUDED_)/ CodingNode.h: DWORDerface for the CCodingNode class./#include WriteTempClass.h#if !defined(AFX_CODINGNODE_H_B439BABF_D5E0_4141_8C89_99F231F4F8C9_INCLUDED_)#define AFX_CODINGNODE_H_B439BABF_D5E0_4141_8C89_99F231F4F8C9_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000class CCodingNode public:CCodingNode();virtual CCodingNode();DWORD weight;/权DWORD parent;/双亲DWORD lchild;/左孩子DWORD rchild;/右孩子BYTE BegCode;/原字符;class WeightNodepublic:WeightNode()weight=0;BegCode=0;HuffmanCode=NULL;size=0;WeightNode()BYTE *HuffmanCode;/哈夫曼编码DWORD weight;/权BYTE BegCode;/初始字符DWORD size;/哈夫曼编码的长度;#endif / !defined(AFX_CODINGNODE_H_B439BABF_D5E0_4141_8C89_99F231F4F8C9_INCLUDED_)/ InfList.h: interface for the CInfList class.#include CodingNode.h/#if !defined(AFX_INFLIST_H_039B2FA0_D6E8_4DA3_9AE8_3597CA17DDED_INCLUDED_)#define AFX_INFLIST_H_039B2FA0_D6E8_4DA3_9AE8_3597CA17DDED_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000struct InfNodeInfNode *next;WeightNode data;class CInfList /保存信息的动态链表public:CInfList()Last=Head=(InfNode *) malloc (sizeof(InfNode);Head-next=NULL;length=0;virtual CInfList();InfNode *GetListHead()return Head;DWORD GetListLength()return length;bool ListFindItem(BYTE data,InfNode *&temp);/查找指定的点bool AppendData(WeightNode data);/尾部添加bool InserFirstData(WeightNode data);/头添加bool DestroyInfList();/销毁链表bool GetPosItem(DWORD Pos,WeightNode &temp);/得到指定元素的位置private:InfNode *Head;/头节点指针InfNode *Last;/尾指针DWORD length;/长度;#endif / !defined(AFX_INFLIST_H_039B2FA0_D6E8_4DA3_9AE8_3597CA17DDED_INCLUDED_)/ UZipDlg.h : header file/#include Coding.h#if !defined(AFX_UZIPDLG_H_47A679B2_6FCA_4B14_A8A8_52763143350F_INCLUDED_)#define AFX_UZIPDLG_H_47A679B2_6FCA_4B14_A8A8_52763143350F_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000/ CUZipDlg dialogclass CUZipDlg : public CDialog/ Constructionpublic:void OnTimer(UINT nIDEvent);CUZipDlg(CWnd* pParent = NULL);/ standard constructor/ Dialog Data/AFX_DATA(CUZipDlg)enum IDD = IDD_UZIP_DIALOG ;/ NOTE: the ClassWizard will add data members here/AFX_DATA/ ClassWizard generated virtual function overrides/AFX_VIRTUAL(CUZipDlg)protected:virtual void DoDataExchange(CDataExchange* pDX);/ DDX/DDV support/AFX_VIRTUAL/ Implementationprotected:HICON m_hIcon;/ Generated message map functions/AFX_MSG(CUZipDlg)virtual BOOL OnInitDialog();afx_msg void OnPaint();afx_msg HCURSOR OnQueryDragIcon();afx_msg void OnEnd();afx_msg void OnRadio1();afx_msg void OnRadio2();afx_msg void OnBUTTONQuit();afx_msg void OnBUTTONFileBro();afx_msg void OnBUTTONWork();/AFX_MSGDECLARE_MESSAGE_MAP()protected:bool IsZip;/压缩/解压缩CString FilePath;/文件绝对地址;/AFX_INSERT_LOCATION/ Microsoft Visual C+ will insert additional declarations immediately before the previous line.#endif / !defined(AFX_UZIPDLG_H_47A679B2_6FCA_4B14_A8A8_52763143350F_INCLUDED_)/ InfList.h: interface for the CInfList class.#include CodingNode.h/#if !defined(AFX_INFLIST_H_039B2FA0_D6E8_4DA3_9AE8_3597CA17DDED_INCLUDED_)#define AFX_INFLIST_H_039B2FA0_D6E8_4DA3_9AE8_3597CA17DDED_INCLUDED_#if _MSC_VER 1000#pragma once#endif / _MSC_VER 1000struct InfNodeInfNode *next;WeightNode data;class CInfList /保存信息的动态链表public:CInfList()Last=Head=(InfNode *) malloc (sizeof(InfNode);Head-next=NULL;length=0;virtual CInfList();InfNode *GetListHead()return Head;DWORD GetListLength()return length;bool ListFindItem(BYTE data,InfNode *&temp);/查找指定的点bool AppendData(WeightNode data);/尾部添加bool InserFirstData(WeightNode data);/头添加bool DestroyInfList();/销毁链表bool GetPosItem(DWORD Pos,WeightNode &temp);/得到指定元素的位置private:InfNode *Head;/头节点指针InfNode *Last;/尾指针DWORD length;/长度;#endif / !defined(AFX_INFLIST_H_039B2FA0_D6E8_4DA3_9AE8_3597CA17DDED_INCLUDED_)class InfNode public:InfNode()next=NULL;virtual InfNode()public:InfNode *next;DataType data;class CCodingNode public:CCodingNode();virtual CCodingNode();DWORD weight;/权DWORD parent;/双亲DWORD lchild;/左孩子DWORD rchild;/右孩子BYTE BegCode;/原字符;class WeightNodepublic:WeightNode()weight=0;BegCode=0;HuffmanCode=NULL;size=0;WeightNode()BYTE *HuffmanCode;/哈夫曼编码DWORD weight;/权BYTE BegCode;/初始字符DWORD size;/哈夫曼编码的长度;class WriteTempClass public:WriteTempClass();virtual WriteTempClass();DWORD lchild;/左孩子DWORD rchild;/右孩子BYTE BegCode;/原始字符;CPP文件：/ Coding.cpp: implementation of the CCoding class./#include stdafx.h#include UZip.h#include Coding.h#ifdef _DEBUG#undef THIS_FILEstatic char THIS_FILE=_FILE_;#define new DEBUG_NEW#endif/ Construction/Destruction/CCoding:CCoding()/初始化压缩、解压缩类PtrHaffumanTree=NULL;NumOfNode=0;index=0;UZ_PtrHaffumanTree=NULL;PtrMainFramePro=(CProgressCtrl *) AfxGetMainWnd()-GetDlgItem(IDC_PROGRESS);/指向主窗体的进度条控件PtrMainFrameSta=(CStatic *) AfxGetMainWnd()-GetDlgItem(IDC_STATIC_Work4);/指向主窗体的Static控件CCoding:CCoding()/释放资源if (PtrHaffumanTree)delete PtrHaffumanTree;PtrHaffumanTree=NULL;bool CCoding:HuffmanCoding()/编码if (!&ResultCode)return false;DWORD n=ResultCode.GetListLength();/得到文件中各种编码的长度InfNode *ptr=(InfNode*)ResultCode.GetListHead()-next;DWORD m=2*n-1;CCodingNode *ht=new CCodingNodem+1;NumOfNode=m;PtrHaffumanTree=ht;DWORD i=1;CCodingNode *HCTemp=NULL;WeightNode Ttemp;DWORD first,second;for(i=1;i=n;i+)/初始化ResultCode.GetPosItem(i,Ttemp);hti.weight=Ttemp.weight;for (i=n+1;iparent=i;(ht+second)-parent=i;(ht+i)-lchild=first;(ht+i)-rchild=second;(ht+i)-weight=(ht+first)-weight+(ht+second)-weight;BYTE *hc;hc=new BYTEn+1;BYTE *cd=new BYTEn;cdn-1=0;DWORD start;InfNode *ptor=ResultCode.GetListHead()-next;for (i=1;iparent;f!=0;c=f,f=(ht+f)-parent)if (ht+f)-lchild=c)cd-start=0;elsecd-start=1;BYTE *temp=(BYTE *) malloc(n-start)*sizeof(BYTE);strcpy(char *)temp,(char *)&cdstart);ptor-data.HuffmanCode=temp;ptor-data.size=strlen(char *)temp);ptor=ptor-next;/转移WeightNode WTemp;for (i=1;i=n;i+)ResultCode.GetPosItem(i,WTemp);hti.BegCode=WTemp.BegCode;return true;void CCoding:Select(CCodingNode *ht,DWORD num,DWORD &s1,DWORD &s2)/编码的辅助函数，用以查找二叉树中最小的两个未分配的节点 DWORD i=1;while (hti.parent!=0)i+;DWORD min=hti.weight;s1=i;for (;i=num;i+)if (hti.weightmin&hti.parent=0)min=hti.weight;s1=i;hts1.parent=-1;i=1;while (hti.parent!=0)i+;min=hti.weight;s2=i;for (;i=num;i+)if (hti.weightdata.weight+=1;elsetemp.BegCode=CTemp;temp.weight=1;ResultCode.AppendData(temp);count+;PtrMainFramePro-SetRange(0,100);fileopen.Close();return true;/bool CCoding:ZipFile()/压缩文件short TypeSize=sizeof(DWORD);CString SavePath;CString postfix;DWORD pos=FilePath.ReverseFind(.);SavePath=FilePath.Left(pos)+.ljhx;postfix=FilePath.Mid(pos+1);BYTE WriteTemp=0;CFile FileWrite;BYTE ReadTemp;WriteTempClass C_WriteTemp;FileWrite.Open(SavePath,CFile:modeCreate|CFile:modeWrite,NULL);GetHead();FileWrite.Write(&index,TypeSize);/保存后缀char T_postfix3;T_postfix0=postfix.GetAt(0);T_postfix1=postfix.GetAt(1);T_postfix2=postfix.GetAt(2);FileWrite.Write(T_postfix,3);FileWrite.Write(&index,TypeSize);FileWrite.Write(&NumOfNode,TypeSize);/保存哈夫曼编码的二叉树for (DWORD i=1;i=NumOfNode;i+)C_WriteTemp.BegCode=PtrHaffumanTreei.BegCode;C_WriteTemp.lchild=PtrHaffumanTreei.lchild;C_WriteTemp.rchild=PtrHaffumanTreei.rchild;FileWrite.Write(&C_WriteTemp,sizeof(WriteTempClass);CFile FileOpenT;FileOpenT.Open(FilePath,CFile:modeRead,NULL);DWORD count=0;DWORD LenOfFile=FileOpenT.GetLength();InfNode *InfTemp;DWORD WriteCount=0;CString CSTTemp;short int PosCount=0;float percent;/压缩while (count!=LenOfFile)FileOpenT.Read(&ReadTemp,1);ResultCode.ListFindItem(ReadTemp,InfTemp);/得到对应字符的编码if (!InfTemp)return true;for(DWORD i=1;idata.size;i+)/转换成二进制中的位WriteCount+;if (InfTemp-data.HuffmanCodei-1=1)/汇编写入_asmmov al,WriteTempshl al,1add al,1mov WriteTemp,alelse_asmmov al,WriteTempshl al,1mov WriteTemp,alif (!(WriteCount%8)FileWrite.Write(&WriteTemp,1);WriteTemp=0;count+;if (count%step=0)/进度条PtrMainFramePro-SetPos(PosCount);PosCount+;if (count+100)%100=0)/进度指示percent=count/(float) LenOfFile)*100;CSTTemp.Format(%f,percent);pos=CSTTemp.ReverseFind(.);CSTTemp=CSTTemp.Left(pos)+%;CSTTemp.Insert(0,目前进度：);PtrMainFrameSta-SetWindowText(CSTTemp);/调整进度指示percent=count/(float) LenOfFile)*100;CSTTemp.Format(%f,percent);pos=CSTTemp.ReverseFind(.);CSTTemp=CSTTemp.Left(pos)+%;CSTTemp.Insert(0,目前进度：);PtrMainFrameSta-SetWindowText(CSTTemp);if (WriteCount%8)/处理尾部字符BYTE j=8-(short int) (WriteCount%8);_asmmov al,WriteTempmov cl,j shl al,clmov WriteTemp,alFileWrite.Write(&WriteTemp,1);/写入总“位”长度File