哈夫曼编码与译码器数据结构课程设计报告样本.doc

资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。沈阳航空航天大学课 程 设 计 报 告课程设计名称: 数据结构课程设计课程设计题目: 实现哈夫曼编码和译码器院( 系) : 计算机学院专 业: 计算机科学与技术班 级: 24010102学 号: 姓 名: 尹伟和指导教师: 徐蕾此页为任务书目 录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附 录( 程序清单) 131. 题目分析1.1. 题目重述本次课程设计的目标是实现一个哈夫曼编码和译码器。该哈夫曼编码和译码器需要根据用户输入的字符集及相应字符出现的频率, 对字符集所包含的字符进行哈夫曼编码。同时, 作为编码器需要其对用户提供的明文字符串进行编码, 使明文字符串变为二进制密文; 作为译码器需要对用户提供的二进制密文进行译码, 使二进制密文变为字符明文。1.1.1. 系统功能需求分析经过对课程设计的题目分析, 能够得出哈夫曼编码和译码器的功能需求, 需求如下: 1) 读取用户输入的字符集和相应字符出现的频率; 2) 根据用户输入构建哈夫曼树; 3) 根据哈夫曼树构建字符-哈夫曼编码对照表; 4) 根据字符-哈夫曼编码对照表对明文字符串进行编码; 5) 根据哈夫曼树对二进制密文进行译码。1.2. 程序设计2.1. 系统功能模块说明根据对系统的分析, 哈夫曼编码与译码器系统共分为五个功能模块, 分别为: 用户输入获取模块、 哈夫曼树构造模块、 字符-哈夫曼编码对照表构造模块、 编码模块、 译码模块。2.1.1. 系统功能模块结构自底向上考虑各系统功能模块之间的依赖关系, 译码模块依赖于哈夫曼树构造模块, 编码模块依赖于字符-哈夫曼编码对照表构造模块, 字符-哈夫曼编码对照表构造模块依赖于哈夫曼编码构造模块, 哈夫曼编码构造模块依赖于用户输入获取模块。系统功能结构框图如图2-1: 图21 哈夫曼编码与译码器系统功能结构框图1.2.2.1.2.1.1.2.1.2. 系统模块功能说明1) 用户输入获取模块获取并保存用户从键盘上输入的字符集和相应字符出现的频率。2) 哈夫曼树构造模块根据用户输入获取模块保存的字符数据, 构造哈夫曼树。3) 字符-哈夫曼编码对照表构造模块根据哈夫曼树构造模块构造的哈夫曼树, 建立字符-哈夫曼编码对照表。4) 编码模块根据字符-哈夫曼编码对照表构造模块构造的字符-哈夫曼编码对照表, 对用户提供的明文进行编码。5) 译码模块根据哈夫曼树构造模块构造的哈夫曼树, 对用户提供的密文字符进行译码。2.2. 数据结构说明在程序中主要用到了二叉树和链表等数据结构。2.2.1. 结构体定义说明1) struct _NODE结构结构体定义如下: typedef struct _NODEchar word;int value;_NODE *left,*right;Node,*LPNode;结构体用途: 作为哈夫曼树的结点结构, 构成哈夫曼树。2) struct _CONTAINER结构结构体定义如下: typedef struct _CONTAINERLPNode v;struct _CONTAINER *last,*next;Container,*LPContainer;结构体用途: 用于在用户输入时保存字符信息, 并构成双向链表。3) struct _ CODENODE结构结构体定义如下: typedef struct _CODENODEchar word;char code100;struct _CODENODE *next;CodeNode,*LPCodeNode;结构体用途: 作为单链表的结点结构, 构成字符-哈夫曼编码对照表。2.2.2. 哈夫曼树在本程序中, 哈夫曼树是使用struct _NODE结构构建的二叉树, 其满足树的叶子结点的带全路径和在所有可能组成的二叉树中最小。2.2.3. 字符-哈夫曼编码对照表在本程序中, 字符-哈夫曼编码对照表是一个单链表, 用于保存字符与哈夫曼编码的对应关系。2.3. 函数说明1) GetInput函数该函数的功能是读取用户输入的字符集数据, 并构建相应的哈夫曼树。函数的返回值是哈夫曼树的指针。2) createHuffmanTree函数该函数的功能是根据用户输入构建哈夫曼树。3) createCodeList函数该函数的功能是根据哈夫曼树构建与之对应的字符-哈夫曼编码对照表。4) code函数该函数用于实现编码功能。5) uncode函数该函数用于实现译码功能。3. 算法描述3.1. 哈夫曼树的构建在本程序中, GetInput函数首先将用户输入的每个字符信息储存到struct _NODE结构中看做是哈夫曼树的叶子结点, 并将struct _NODE结构的地址储存到struct _CONTAINER结构中, 按字符出现频率升序插入到双向链表中, 然后调用createHuffmanTree函数构造哈夫曼树。在构造哈夫曼树的过程中, 首先从双向链表中选取字符出现频率最小和第二小的结点, 从中提取哈夫曼树的子树, 将两个子树合并成一个子树, 再将父节点的地址存入struct _CONTAINER结构中, 并插入到双向链表中。重复此步骤直到链表中只剩下一个结点。这样该struct _CONTAINER结构中存储的struct _NODE类型的指针就指向要得到哈夫曼树的根节点了。3.2. 字符-哈夫曼编码对照表用深度优先搜索的方法递归的遍历哈夫曼树, 展开的过程中向调用的递归函数传递要访问的结点的哈夫曼编码。当访问叶子结点时, 从结点中提取字符信息, 并和其哈夫曼编码一同储存到struct _ CODENODE结构中, 然后将struct _ CODENODE结构插入到单链表中。如此, 当遍历完成时, 字符-哈夫曼编码对照表便构造完成了。3.3. 编码从源文件中读取一个字符, 在字符-哈夫曼编码对照表中查找该字符, 将查找到的结点中储存的哈夫曼编码写入到目标文件中。 图 31 构建哈夫曼树流程图 图 32 编码流程图3.4. 译码从源文件中读取字符, 按照字符的指示访问哈夫曼树的子树, 即从根节点出发, 若读取到0则访问左子树, 若读取到1则访问右子树, 知道子树为哈夫曼树的叶子结点为止, 此时向目标文件中输出结点中的字符。图 33 译码流程图4. 程序测试4.1. 字符集输入输入的字符集及字符出现频率如表4-1所示: 表 41 字符集输入用例字符abc出现频率1035预计生成字符-哈夫曼编码对照如表4-2所示: 表 42 字符-哈夫曼编码对照表字符abc哈夫曼编码10001程序运行效果如图4-1所示: 图41 程序运行效果图4.2. 编码测试运行程序编码模块, 如图4-2所示: 图 42 程序运行编码模块效果图程序编码输入文件如图4-3所示: 图 43 程序编码输入文件截图输出分析如表4-3所示: 表 43 编码输出分析abcbcaacb100010001110100程序编码输入文件如图4-4所示: 图 44 程序编码输出文件截图4.3. 译码测试将编码后的文件逆向输入进行译码。运行程序译码模块, 如图4-5所示: 图 45 程序运行译码模块效果图程序译码输入文件如图4-6所示: 图 46 程序译码输入文件截图程序译码输出文件如图4-7所示: 图 47 程序译码输出文件截图参考文献1 严蔚敏,吴伟民.数据结构(C语言版)M.北京:清华大学出版社, 2 吕国英.算法设计与分析M.北京:清华大学出版社, 3 徐宝文,李志.C程序设计语言M.北京:机械工业出版社, 4 Erich Gamma,Richaed Helm.设计模式(英文版)M.北京:机械工业出版社, 附 录( 程序清单) #include #include #include typedef struct _NODEchar word;int value;_NODE *left,*right;Node,*LPNode;typedef struct _CONTAINERLPNode v;struct _CONTAINER *last,*next;Container,*LPContainer;typedef struct _CODENODEchar word;char code100;struct _CODENODE *next;CodeNode,*LPCodeNode;void insert(LPContainer list,LPContainer node)LPContainer p;p=list-last;while(node-v-valuev-value)p=p-last;node-last=p;node-next=p-next;p-next-last=node;p-next=node;LPNode createHuffmanTree(LPContainer list)LPContainer p;LPNode left,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);return left;LPNode GetInput()Container list;LPContainer p;LPNode head;int i,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;iv=(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);return head;void dfs(LPNode t,char *code,LPCodeNode list)LPCodeNode p;char l100,r100;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);LPCodeNode createCodeList(LPNode tree)CodeNode head;head.next=NULL;dfs(tree,&head);return head.next;void code(LPCodeNode list)FILE *sfp,*dfp;char path256,c;LPCodeNode p;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);void uncode(LPNode tree)FILE *sfp,*dfp;char path256,c;LPNode p;printf(请输入源文件路径: );scanf(%s,path);sfp=fopen(path,rt);printf(请输入目标文件路径: );scanf(%s,path);dfp=fopen(path,wt);p=tree;while(c=fgetc(sfp)!=EOF)if(c=0)p=p-left;elsep=p-right;if(p-word!=-1)fputc(p-word,dfp);p=tree;fclose(sfp);fclose(dfp);void main()LPNode tree=NULL;LPCodeNode list=NULL;int t;while(1)printf(n1.输入字符集n2.编码n3.解码n4.退出n);scanf(%d,&t);switch(t)case 1:tree=GetInput();list=createCodeList(tree);break;case 2:code(list);break;case 3:uncode(tree);break;case 4:exit(0);课程设计总结: 经过此次课程设计, 是我在数据结构的设计和算法设计等方面有了进一步的提高。关于数据结构方面, 我对于链表和树结构的理解更加深刻, 链表的建立、 遍历、 插入等操作; 树的建立、 遍历等操作更加熟练, 已能够运用自如。关于算法方面, 我对于插入排序, 深度优先搜索等算法, 已理解其原理, 并能熟练编写。同时, 我还深刻认识到, 就我们计算机专业的学生来说, 只是掌握经典的算法和数据结构是远远不够的。我们要深刻发掘创新能力, 培养创新思维, 只有这样我们才能在编程解决实际问题的道路上走的更远。指导教师评语: 指导教师(签字): 年 月 日课程设计成绩