版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
沈阳航空航天大学课程设计报告课程设计名称:数据结构课程设计课程设计题目:实现哈夫曼编码和译码器院(系):计算机学院专业:计算机科学与技术班级:24010102学号:2姓名:尹伟和指导教师:徐蕾此页为任务书
目录1. 题目分析 11.1. 题目重述 11.1.1. 系统功能需求分析 12. 程序设计 22.1. 系统功能模块说明 22.1.1. 系统功能模块结构 22.1.2. 系统模块功能说明 32.2. 数据结构说明 32.2.1. 结构体定义说明 32.2.2. 哈夫曼树 42.2.3. 字符-哈夫曼编码对照表 42.3. 函数说明 43. 算法描述 63.1. 哈夫曼树的构建 63.2. 字符-哈夫曼编码对照表 63.3. 编码 63.4. 译码 74. 程序测试 84.1. 字符集输入 84.2. 编码测试 94.3. 译码测试 10参考文献 12附录(程序清单) 13题目分析题目重述本次课程设计的目的是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率,对字符集所包含的字符进行哈夫曼编码。同时,作为编码器需要其对用户提供的明文字符串进行编码,使明文字符串变为二进制密文;作为译码器需要对用户提供的二进制密文进行译码,使二进制密文变为字符明文。系统功能需求分析通过对课程设计的题目分析,可以得出哈夫曼编码和译码器的功能需求,需求如下:读取用户输入的字符集和相应字符出现的频率;根据用户输入构建哈夫曼树;根据哈夫曼树构建字符-哈夫曼编码对照表;根据字符-哈夫曼编码对照表对明文字符串进行编码;根据哈夫曼树对二进制密文进行译码。程序设计系统功能模块说明根据对系统的分析,哈夫曼编码与译码器系统共分为五个功能模块,分别为:用户输入获取模块、哈夫曼树构造模块、字符-哈夫曼编码对照表构造模块、编码模块、译码模块。系统功能模块结构自底向上考虑各系统功能模块之间的依赖关系,译码模块依赖于哈夫曼树构造模块,编码模块依赖于字符-哈夫曼编码对照表构造模块,字符-哈夫曼编码对照表构造模块依赖于哈夫曼编码构造模块,哈夫曼编码构造模块依赖于用户输入获取模块。系统功能结构框图如图2-1:图STYLEREF1\s2SEQ图\*ARABIC\s11哈夫曼编码与译码器系统功能结构框图系统模块功能说明用户输入获取模块获取并保存用户从键盘上输入的字符集和相应字符出现的频率。哈夫曼树构造模块根据用户输入获取模块保存的字符数据,构造哈夫曼树。字符-哈夫曼编码对照表构造模块根据哈夫曼树构造模块构造的哈夫曼树,建立字符-哈夫曼编码对照表。编码模块根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表,对用户提供的明文进行编码。译码模块根据哈夫曼树构造模块构造的哈夫曼树,对用户提供的密文字符进行译码。数据结构说明在程序中重要用到了二叉树和链表等数据结构。结构体定义说明struct_NODE结构结构体定义如下:typedefstruct_NODE{ charword; intvalue; _NODE*left,*right;}Node,*LPNode; 结构体用途:作为哈夫曼树的结点结构,构成哈夫曼树。struct_CONTAINER结构结构体定义如下:typedefstruct_CONTAINER{ LPNodev; struct_CONTAINER*last,*next;}Container,*LPContainer; 结构体用途:用于在用户输入时保存字符信息,并构成双向链表。struct_CODENODE结构结构体定义如下:typedefstruct_CODENODE{ charword; charcode[100]; struct_CODENODE*next;}CodeNode,*LPCodeNode; 结构体用途:作为单链表的结点结构,构成字符-哈夫曼编码对照表。哈夫曼树在本程序中,哈夫曼树是使用struct_NODE结构构建的二叉树,其满足树的叶子结点的带全途径和在所有也许组成的二叉树中最小。字符-哈夫曼编码对照表在本程序中,字符-哈夫曼编码对照表是一个单链表,用于保存字符与哈夫曼编码的相应关系。函数说明GetInput函数该函数的功能是读取用户输入的字符集数据,并构建相应的哈夫曼树。函数的返回值是哈夫曼树的指针。createHuffmanTree函数该函数的功能是根据用户输入构建哈夫曼树。createCodeList函数该函数的功能是根据哈夫曼树构建与之相应的字符-哈夫曼编码对照表。code函数该函数用于实现编码功能。uncode函数该函数用于实现译码功能。
算法描述哈夫曼树的构建在本程序中,GetInput函数一方面将用户输入的每个字符信息储存到struct_NODE结构中看做是哈夫曼树的叶子结点,并将struct_NODE结构的地址储存到struct_CONTAINER结构中,按字符出现频率升序插入到双向链表中,然后调用createHuffmanTree函数构造哈夫曼树。在构造哈夫曼树的过程中,一方面从双向链表中选取字符出现频率最小和第二小的结点,从中提取哈夫曼树的子树,将两个子树合并成一个子树,再将父节点的地址存入struct_CONTAINER结构中,并插入到双向链表中。反复此环节直到链表中只剩下一个结点。这样该struct_CONTAINER结构中存储的struct_NODE类型的指针就指向要得到哈夫曼树的根节点了。字符-哈夫曼编码对照表用深度优先搜索的方法递归的遍历哈夫曼树,展开的过程中向调用的递归函数传递要访问的结点的哈夫曼编码。当访问叶子结点时,从结点中提取字符信息,并和其哈夫曼编码一同储存到struct_CODENODE结构中,然后将struct_CODENODE结构插入到单链表中。如此,当遍历完毕时,字符-哈夫曼编码对照表便构造完毕了。编码从源文献中读取一个字符,在字符-哈夫曼编码对照表中查找该字符,将查找到的结点中储存的哈夫曼编码写入到目的文献中。图STYLEREF1\s31构建哈夫曼树流程图图STYLEREF1\s32编码流程图译码从源文献中读取字符,按照字符的指示访问哈夫曼树的子树,即从根节点出发,若读取到‘0’则访问左子树,若读取到‘1’则访问右子树,知道子树为哈夫曼树的叶子结点为止,此时向目的文献中输出结点中的字符。图STYLEREF1\s33译码流程图程序测试字符集输入输入的字符集及字符出现频率如表4-1所示:表STYLEREF1\s4SEQ表\*ARABIC\s11字符集输入用例字符abc出现频率1035预计生成字符-哈夫曼编码对照如表4-2所示:表STYLEREF1\s4SEQ表\*ARABIC\s12字符-哈夫曼编码对照表字符abc哈夫曼编码10001程序运营效果如图4-1所示:图STYLEREF1\s4SEQ图\*ARABIC\s11程序运营效果图编码测试运营程序编码模块,如图4-2所示:图STYLEREF1\s4SEQ图\*ARABIC\s12程序运营编码模块效果图程序编码输入文献如图4-3所示:图STYLEREF1\s4SEQ图\*ARABIC\s13程序编码输入文献截图输出分析如表4-3所示:表STYLEREF1\s4SEQ表\*ARABIC\s13编码输出分析abcbcaacb100010001110100程序编码输入文献如图4-4所示:图STYLEREF1\s4SEQ图\*ARABIC\s14程序编码输出文献截图译码测试将编码后的文献逆向输入进行译码。运营程序译码模块,如图4-5所示:图STYLEREF1\s4SEQ图\*ARABIC\s15程序运营译码模块效果图程序译码输入文献如图4-6所示:图STYLEREF1\s4SEQ图\*ARABIC\s16程序译码输入文献截图程序译码输出文献如图4-7所示:图STYLEREF1\s4SEQ图\*ARABIC\s17程序译码输出文献截图参考文献[1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2023[2]吕国英.算法设计与分析[M].北京:清华大学出版社,2023[3]徐宝文,李志.C程序设计语言[M].北京:机械工业出版社,2023[4]ErichGamma,RichaedHelm.设计模式(英文版)[M].北京:机械工业出版社,2023附录(程序清单)#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct_NODE{ charword; intvalue; _NODE*left,*right;}Node,*LPNode;typedefstruct_CONTAINER{ LPNodev; struct_CONTAINER*last,*next;}Container,*LPContainer;typedefstruct_CODENODE{ charword; charcode[100]; struct_CODENODE*next;}CodeNode,*LPCodeNode;voidinsert(LPContainerlist,LPContainernode){ LPContainerp; p=list->last; while(node->v->value<p->v->value) { p=p->last; } node->last=p; node->next=p->next; p->next->last=node; p->next=node;}LPNodecreateHuffmanTree(LPContainerlist){ LPContainerp; LPNodeleft,right,t; while(list->next!=list->last) { p=list->next; list->next=p->next; left=p->v; free(p); p=list->next; list->next=p->next; list->next->last=list; right=p->v; t=(LPNode)malloc(sizeof(Node)); t->word=-1; t->value=left->value+right->value; t->left=left; t->right=right; p->v=t; insert(list,p); } p=list->next; list->next=p->next; list->next->last=list; left=p->v; free(p); returnleft;}LPNodeGetInput(){ Containerlist; LPContainerp; LPNodehead; inti,num; printf("输入字符集规模:"); scanf("%d",&num); list.v=(LPNode)malloc(sizeof(Node)); list.v->word=-1; list.v->value=0; list.v->left=list.v->right=NULL; list.next=&list; list.last=&list; for(i=0;i<num;i++) { p=(LPContainer)malloc(sizeof(Container)); p->v=(LPNode)malloc(sizeof(Node)); p->v->left=p->v->right=NULL; getchar(); printf("输入字符:"); scanf("%c",&p->v->word); printf("输入该字符的权值:"); scanf("%d",&p->v->value); insert(&list,p); } printf("正在构造哈夫曼树……\n"); head=createHuffmanTree(&list); printf("哈夫曼树创建成功!\n"); free(list.v); returnhead;}voiddfs(LPNodet,char*code,LPCodeNodelist){ LPCodeNodep; charl[100],r[100]; if(t->word!=-1) { p=(LPCodeNode)malloc(sizeof(CodeNode)); p->word=t->word; strcpy(p->code,code); p->next=list->next; list->next=p; return; } strcpy(l,code); strcat(l,"0"); dfs(t->left,l,list); strcpy(r,code); strcat(r,"1"); dfs(t->right,r,list);}LPCodeNodecreateCodeList(LPNodetree){ CodeNodehead; head.next=NULL; dfs(tree,"",&head); returnhead.next;}voidcode(LPCodeNodelist){ FILE*sfp,*dfp; charpath[256],c; LPCodeNodep; printf("请输入源文献途径:"); scanf("%s",path); sfp=fopen(path,"rt"); printf("请输入目的文献途径:"); scanf("%s",path); dfp=fopen(path,"wt"); while((c=fgetc(sfp))!=EOF) { p=list; while(p->word!=c) p=p->next; fputs(p->code,dfp); } fclose(sfp); fclose(dfp);}voiduncode(LPNodetree){ FILE*sfp,*dfp; charpath[256],c; LPNodep; printf("请输入源文献途径:"); scanf("%s",path); sfp=fopen(path,"rt"); printf("请输入目的文献途径:"); scanf("%s",path);
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 农村产业融合市场分析
- 关于销售的实习报告范文集锦9篇
- 关于建筑工地实习日记三篇
- 天英学校家政服务员(初级)理论练习测试题附答案
- 2017年四川省绵阳市中考化学试卷(学生版)
- 2024-2025学年上海市杨浦区民办兰生中学六年级(上)月考数学试卷(10月份)(含解析)
- 语文统编版(2024)一年级上册汉语拼音-⑨y w 教案
- 广东高考英语语法完形阅读
- 会计数据分析 TestBank Richardson1e-Chapter06-TB-AnswerKey-06.12.19
- 宪法是根本法课件
- 2024-2030年中国钾长石行业运行动态与产销需求预测报告
- 第四章-护理人际关系伦理
- 针灸室晕针应急预案演练方案
- 第2章 第5节 科学探究:电容器2023-2024学年新教材高二物理必修第三册同步课堂高效讲义配套教学设计(鲁科版2019)
- 电动汽车充电设施及场站测试评价规范第1部分:总则
- 二次系统安全防护事故应急预案格式(标准版)
- 餐饮技能大赛(中式面点师赛项)理论考试题及答案
- 部编版2023-2024学年度六年级上册语文期中测试卷(附答案)
- 2024年共青团入团积极分子考试题库(含答案)
- 籍贯对照表完整版
- 保安队排班表
评论
0/150
提交评论