Huffman编码译码实现

Huffman编码译码实现 南阳理工学院 数据结构课程 哈夫曼编码和译码的实现 移动1班 李保 1115115607 2012/5/16 努力造就辉煌 编程成就梦想 移动1班 李保 1115115607 哈夫曼编码和译码的实现 ------------------------------------------------------------------------------------------------------ 目录 ------------------------------------------------------------------------------------------------------ 一,题目介绍.......................................3 二,需求分析.......................................4 三,系统设计................................. ......5 四，程序图.....................................9 五,代码.......................................... 10 六，..........................................28 七，参考书目......................................29 - 2 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 一、题目: 哈夫曼编码/译码的设计与实现 构建一棵哈夫曼树，并用哈夫曼树来实现编码各译码的功能 二、目的与要求 1、目的: 通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用;使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。 2、要求: 基本要求: 1. 要求利用C\C++语言来完成系统的设计; 2. 突出C语言的函数特征(以多个函数实现每一个子功能)或者 C++语言面向对象的编程思想; 3. 画出功能模块图; 4. 进行简单界面设计，能够实现友好的交互; 5. 具有清晰的程序和数据结构的详细定义; 6. 熟练掌握C语言或者C++语言的各种操作。 创新要求: 在基本要求达到后，可进行创新设计，如系统用户功能控制，改 进算法的实现，实现友好的人机交互等等 - 3 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 二，需求分析 哈夫曼树，又称最优二叉树。上课时我了解了哈夫曼树的某些奇特而强大的功能 ，通过哈夫曼树构造的编码译码系统具有加密的特性，而且加密性非常好，在某些领域中应用非常广泛～ 而且哈夫曼树的还有很大的功能就是压缩性很好～压缩性能可以达到20%至80%～ 而且通信的数码拨号时，我通常会用到十进制、八进制、或者十六进制数等。而输入数字后，数据将以二进制数编码后进行远距离通信传送。电文传输过程中，为了提高通讯效率，通常会要求所传输的二进制数码尽可能的短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但是同时要求各数字编码之间互不为前缀，从而不出现误码。设计一个程序构建一个赫夫曼树输出最优传输码。 因此我们应该能把哈夫曼树应用到我们的生活中～ - 4 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 三，系统设计 1,分别定义两个结构体， typedef struct { char data; int weight; int parent; int lchild; int rchild; }HuffNode;//定义哈夫曼树节点的相关信息 HuffNode结构 data weight parent lchild rchild /*哈夫曼编码存储结构*/ typedef struct { int cd[MAXNUM];//存放HUFFMAN编码的数组 int begin; }HuffCode; - 5 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 HuffCode结点结构 cd[] begin 3、程序所用各函数功能: (1)创建赫夫曼树 Int HuffmanCreate ( HuffNode *ht ) 输入用线性表HuffNode *ht存储的n个只含根结点的二叉树，及其权值。函数将各个根结点的父节点及孩子都初始化为0，由Huffman树的特性可知,创建Huffman树的总的结点数为2*n-1. 然后用for循环,从输入的n个结点中找到最小值min1和次小值min2,用p1和p2记录min1和min2的下标.然后将min1和min2的权值相加做为新的哈夫曼树的结点值,并将新的结点的权值插入到n到2*n-1剩下的空间中.通过逐步循环便可创建一棵哈夫曼树. (2)给哈夫曼树中各个节点的编码 void HuffmanCode(HuffNode ht[],HuffCode hcd[],int n) 该函数是给哈夫曼树的结点进行编码.编码的规划是先对所有的结点循环,从下开始比较,若该结点的双亲的左孩子等于该结点,则标记为’0’且存入数组中,若不等于,则标记为’1’,也存入数组中.直到ht[i].parent=0时,即一直找到根结点.此时哈夫曼树编码成功! - 6 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 /*哈夫曼译码函数*/ void Huffmandecode(HuffNode ht[],HuffCode hcd[], int n) 首先要求输入哈夫曼编码,如:1011110101101等,将它存到数组ch[]里面.然后从哈夫曼的根节点开始,遇到0”走向”左孩子,遇到”1”走向右孩子.走到头时输出最终节点的值.这时哈夫妻曼译码完成 /*定义获取系统时间的函数*/ void Gettime() 这个是系统时间获取函数,为了使程序更加有实用性,更加人性化,这个是我附加的程序功能. /*密码设定函数*/ void SecretCode() 这个是密码设定函数,我认为一个完整的程序应该 有它的安全性.因此为自己的程序加上密码是非常有必要的. - 7 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 函数功能示意图 测试数据:假设输入的的节点的权值是:7 4 2 5 8 26 8 18 11 7 6 5 4 2 这个是根据节点的权值构造的一棵哈夫曼树, - 8 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 四.程序流程图. 1、程序流程图 开始 选择菜单 输入n n=1 Y N 构建只含根结点 的带权二叉树 N n=2 N n=3 Y N n=4 输出对应二叉树Y 的赫夫曼树 i=其他 Y 赫夫曼树在电报 通信中的应用 退出菜单 结束 - 9 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 五,源代码 /********************************************************************* * * 努力造就辉煌 编程成就梦想 * * 程序功能:哈夫曼编码/译码的设计与实现 * * 作者:李保 * * 程序版本:v006 * * 完成日期:2012-05-11 * * * * * ********************************************************************/ #include #include #include #include #include #define MAXNUM 100 /*哈夫曼结点的结构*/ typedef struct { char data; - 10 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 int weight; int parent; int lchild; int rchild; }HuffNode; /*哈夫曼编码存储结构*/ typedef struct { int cd[MAXNUM];//存放HUFFMAN编码的数组 int begin; }HuffCode; /*哈夫曼树的构造函数*/ int HuffmanCreate(HuffNode *ht) { int min1,min2,p1,p2,i,k,n; system("CLS"); printf("\t请输入要编码的数据的个数:"); scanf("%d",&n); - 11 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 if(n <= 1) do { printf("\n输入的数据元素个数太少!请重新输入!\n\n"); printf("\t请输入要编码的数据的个数:"); scanf("%d",&n); }while(n <= 1); for(i = 1;i<=n;i++) { getchar(); system("CLS"); printf("\n\t\t=================================== =\n"); printf("\t\t\t第%d个元素的=>\n\t\t\t\t结点的值:",i); scanf("%c",&ht[i].data); printf("\t\t\t\t节点权重:"); scanf("%d",&ht[i].weight); - 12 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 printf("\n\t\t=================================== =\n"); } for(i = 1;i<= 2 * n - 1; i++) ht[i].parent = ht[i].lchild = ht[i].rchild = 0; for(i = n+1;i<= 2 * n - 1;i++)//产生新的Huffman节点 { min1 = min2 = 32767;//min1和min2开始赋最大值 p1=p2=1; for(k = 1;k<=i-1;k++)//在输入的节点中选取权值最小的值min1和min2 { if(ht[k].parent == 0) if(ht[k].weight < min1)//运用选择排序生成HUFFMAN树 { min2 = min1; p2 = p1; min1 = ht[k].weight; p1 = k; - 13 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 } else if(ht[k].weight < min2) { min2 =ht[k].weight; p2 = k; } } ht[p1].parent = i; ht[p2].parent = i; ht[i].weight = min1 + min2; ht[i].lchild = p1; ht[i].rchild = p2; } printf("\n\n\n\t\t\t提示:哈夫曼树构建成功～\n\n\n\n"); system("PAUSE"); return n; } /*哈夫曼编码函数*/ void HuffmanCode(HuffNode ht[],HuffCode hcd[],int n) - 14 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 { system("CLS"); HuffCode d; int i,f,c,k; for(i = 1;i <= n; i++ ) { d.begin = n + 1; c = i; f = ht[i].parent ; while(f!=0) { if(ht[f].lchild == c) d.cd[--d.begin] = '0'; else d.cd[--d.begin] = '1'; c = f; f = ht[i].parent ; //printf("aaaaa=%d",d.begin); if(d.begin == 0) break; } hcd[i] = d; } - 15 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 printf("\t输出哈夫曼编码:\n"); for(i = 1;i <= n; i++) { printf("%c:",ht[i].data); for(k = hcd[i].begin;k <= n; k++) printf("%c",hcd[i].cd[k]); printf("\t\n"); } printf("\n提示: 编码成功!\n"); printf("\t\n\n\n\n\n"); system("PAUSE"); } /*哈夫曼译码函数*/ void Huffmandecode(HuffNode ht[],HuffCode hcd[], int n) { system("CLS"); int f,m,k; char c,ch[100]; printf("\t请输入电文发译码的数据(0 or 1),\n\t以# - 16 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 为结束标志:"); c = getchar(); k = 1; while(c != '#') { ch[k] = c; c = getchar(); k = k + 1; } m = k; f = 2 * n - 1; k = 1; printf("\t输出哈夫曼译码:\n"); printf("\n"); while(k < m) { while(ht[f].lchild != 0) { if(ch[k] == '0') f = ht[f].lchild; if(ch[k] == '1') - 17 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 f = ht[f].rchild; k++; } printf("%c",ht[f].data); f = 2 * n - 1; } printf("\t\n\n\n"); printf("提示: 译码成功!\n\n"); system("PAUSE"); } /*定义获取系统时间的函数*/ void Gettime() { time_t rawtime; struct tm * timeinfo; time ( &rawtime ); timeinfo = localtime ( &rawtime ); printf ( "\n\t (@_@)现在的时间是: %s", asctime (timeinfo) ); } - 18 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 /*密码设定函数*/ void SecretCode() { char mi[20]; fflush(stdin); system("CLS"); printf("\n\n\n\n\n\n\n\n\t信息无价:请知道加密的重要性,保护好我们的信息!(^_^)\n\n"); getch(); system("CLS"); while(1) { system("CLS"); fflush(stdin); printf("\n\n\n\n\n\n\t\t\t密码提示:qiancheng\n"); printf("\t\t\t请输入密码以继续:"); gets(mi); if(strcmp(mi,"qiancheng") == 0) break; - 19 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 else { printf("\t\t\t密码输入错误!请重新输入!\n");getch(); } } } /*主函数*/ int main(int argc ,char *argv[]) { SecretCode(); system("CLS"); system("color 0A"); int n,select,flag = 0; HuffNode ht[2*MAXNUM]; HuffCode hcd[MAXNUM]; while(1) { system("CLS"); - 20 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 printf("\n\t======================欢迎使用 =====================\n"); Gettime(); printf("\n\t===================================================\n"); fflush(stdin); printf("\t\t\t哈夫曼编码译码系统"); printf("\n\t************************菜单 ***********************\n"); printf("\t* *\n"); printf("\t* 1----------建立哈夫曼树 *\n"); printf("\t* 2----------编码 *\n"); printf("\t* 3----------译码 *\n"); printf("\t* 4----------退出系统 *\n"); printf("\t* *\n"); - 21 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 printf("\t*************************************** ************\n"); printf("\t* 移动1班 * 1115115607 * 李保 制作 *\n"); printf("\t*************************************** ************\n"); printf("\t请选择你所要实现的功能(请输入1~4数 字):[ ]\b\b"); scanf("%d",&select); if(select != 1 && select != 4 && flag == 0) { printf("\n\t~_~ 输入有误!请先选择建立哈夫曼 树再选择其它功能～\n\n"); getch(); continue; } flag = 1; switch(select) - 22 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 { case 1:n = HuffmanCreate(ht);break; case 2:HuffmanCode(ht,hcd,n);break; case 3:Huffmandecode(ht,hcd,n);break; case 4:printf("\n\t\t\t谢谢使用!再见^ _ ^\n\n\t"); exit(0); } } return 0; } - 23 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 2,程序演示结果: (一)开始时:对该程序做简单的介绍 (二)要求输入密码: (三)程序的主界面: - 24 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 (四)创建Huffman树: - 25 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 (五)对Huffman树进行编码: (六)对Huffman树进行译码 - 26 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 (七)退出系统 - 27 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 六.总结 我喜欢课程设计!课程设计可以提高我们的能力.通过二个星期的数据结构课程设计的学习，我对C语言、数据结构对程序的编写有了更深刻的了解，一个完整的，健壮的程序需要有合理的算法和数据结构作为基础，算法是程序的灵魂，是程序的主线，是实现问题的方法和基本步骤的描述，而一个好的算法的实现要建立在合理熟练的逻辑结构和存储结构上 编写代码前之前要对所要编译的程序有个整体的了解，需要用什么样的逻辑结构和存储结构，用什么样的算法去实现。C语言的重要特征是函数.能过这次课程设计我对C语言的函数有了很深刻的了解!要重视对结构体变量的运用，因为无论是线形结构还是链式结构都难免用到结构体变量，结构体中要包含所要描述问题的各个数据域和指针域的指向;关于数组，在调用函数实参时也容易出错，因为在用数组做实参时传递的是数组指针，而这一点在本次课程设计中，当我用到文件包含的方式，让主函数main()调用子文件中的子函数是，数组做参数传递过程中遇到了许多细节问题，对编程的进度造成了很大的阻碍。 要想编译出一个好的程序真不是一件简单的事情，这次的作业又花了我大量的时间，但是无论是C语言还是数据结构，在学习过程中收获最大的还是最后的大作业，通过大作业，对一些实际操作中算法的描述，数据结构的使用才有了更深一层的了解，同时也积累了一些在解决实际问题中的经验，处理一般的编译，连接错误的方法，并能够一步一步的进行调试，编程的过程确实很辛苦，但是有了成果之后又觉得很轻松。所以感觉要是投入进去的话编程还不是很难的，只要能够把基础的知识学好，多在操作中练习，多积累些解决实际问题的经验，以后再做这方面的工作就简单多了。 课题设计使得我对这学期所学的专业课有了更为深刻的认识，对于我来说这不仅仅是一次课程设计，更重要的是使我明白了在学习的过程中，所有的问题要一个人去面对，有问题要想尽各种办法解决，克服困难，在解决这些困难的过程中提高了我学习的能力、解决问题的能力和实际工作的能力，学到了许多书本以外的 - 28 - 移动1班 李保 1115115607 哈夫曼编码和译码的实现 认识。通过这次课程设计我觉得我学习《数据结构》的方法存在一定的弊端,《数据结构》的效果直接影响到我对其它专业课的学习和今后业务的成长。我觉得我对于《数据结构》的学习不仅包括理论部分的学习，还要让我勤动手，多实践。最后我要衷心的感谢所有给予我帮助和指导的莫老师，我的同学:雷艳雄、黎盛才、刘宇等人,没有他们的帮助我的课程设计也不会完成得这么顺利! 最后，通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正学以致用，从而提高自己的实际动手能力和独立思考的能力。而且，编程非常考验人的耐心和信心,这也在性格方面给了我很多磨练。通过这次课程设计之后，我把前面所学过的知识又重新温故了一遍，可以说是收获不少。 七.参考书目 严蔚敏 吴伟民 <<数据结构>>(c语言版) 清华大学出版社 滕国文 <<数据结构课程设计>> 清华大学出版社 刘克成 <> 中国铁道出版社 - 29 -